Robocikowo>ROBOCIKOWO
Architektura

Naive Bayes

Historyczny
Probabilistyczny klasyfikator oparty na twierdzeniu Bayesa z założeniem warunkowej niezależności cech — prosty, szybki i mimo "naiwności" zaskakująco skuteczny baseline w klasyfikacji tekstu.
Kategoria
Architektura
Poziom abstrakcji
Primitive
Poziom operacji
ModelInferencjaDane
Zastosowania
Filtrowanie spamu e-mailKlasyfikacja dokumentów i kategoryzacja tematycznaAnaliza sentymentuKlasyfikacja medyczna i diagnostyka wstępnaSzybki baseline w benchmarkach NLP

Jak działa

1. Trening: dla każdej klasy C oblicz a priori P(C) jako częstość klasy w zbiorze treningowym. Dla każdej cechy x_i oblicz warunkowe prawdopodobieństwo P(x_i|C) z częstości (multinomial) lub parametrów rozkładu (Gaussian). 2. Wygładzanie Laplace'a: dodaj stałą α (domyślnie 1) do licznika, żeby uniknąć zerowych prawdopodobieństw dla niewidzianych cech. 3. Predykcja: dla nowego przykładu x zastosuj regułę MAP — wybierz klasę maksymalizującą P(C)·∏P(x_i|C). W praktyce liczymy log-sumy, żeby uniknąć underflow: log P(C) + Σ log P(x_i|C). 4. Warianty rozkładu: multinomial (zliczenia tokenów — NLP), Bernoulli (cechy binarne), Gaussian (cechy ciągłe — zakłada normalność).

Rozwiązany problem

Klasyfikacja obiektów do kategorii wymaga metody, która oszacuje prawdopodobieństwo przynależności do klasy na podstawie obserwowanych cech. Tradycyjne podejścia wymagały modelowania pełnego rozkładu łącznego cech — co jest obliczeniowo niewykonalne przy dużej liczbie wymiarów. Naive Bayes rozwiązuje ten problem przez założenie warunkowej niezależności cech, redukując złożoność estymacji z wykładniczej do liniowej.

Kluczowe mechanizmy

Twierdzenie Bayesa: P(C|x) ∝ P(C)·∏P(x_i|C)
Założenie warunkowej niezależności cech pod warunkiem klasy
Estymacja prawdopodobieństw a priori i warunkowych z częstości w danych treningowych
Wygładzanie Laplace'a / Lidstone'a dla nieobserwowanych cech
Decyzja MAP (maximum a posteriori) — wybór klasy o największym prawdopodobieństwie posterior
Warianty rozkładów: Multinomial (zliczenia), Bernoulli (binarne), Gaussian (ciągłe)

Mocne strony i ograniczenia

Mocne strony
✓Bardzo szybki trening i predykcja — liniowy względem liczby cech
✓Minimalne wymagania co do ilości danych treningowych
✓Łatwa implementacja i interpretowalność
✓Dobre wyniki w klasyfikacji tekstu mimo naiwnego założenia
✓Naturalna obsługa wielu klas
✓Niskie wymagania pamięciowe
Ograniczenia
✗Założenie niezależności cech jest prawie zawsze naruszone
✗Słabo skalibrowane prawdopodobieństwa posterior (skrajne wartości 0/1)
✗Problem zerowej częstości — wymaga wygładzania
✗Niska zdolność modelowania interakcji między cechami
✗Gaussian NB zakłada normalność cech ciągłych, co rzadko jest prawdą
✗Gorsze wyniki niż modele dyskryminatywne (regresja logistyczna, SVM) gdy danych jest dużo

Implementacja

Pułapki implementacyjne
Zero probability — niewidziane słowa zerują cały rozkładŚrednia

Jeśli słowo z testu nie wystąpiło w treningu, P(słowo|klasa)=0 zeruje cały iloczyn prawdopodobieństw. Wymaga smoothing (Laplace/add-k) — bez niego klasyfikator jest bezużyteczny na nowych tekstach.

Założenie niezależności cech rzadko spełnione w językuŚrednia

Słowa w zdaniu są silnie skorelowane ("nie" przed "dobry" zmienia semantykę). Naruszenie założenia niezależności degraduje kalibrację prawdopodobieństw — model może klasyfikować poprawnie, ale z błędnymi pewnościami.

Ewolucja

Oryginalny paper · 1961 · Journal of the ACM · Marvin E. Maron
Automatic Indexing: An Experimental Inquiry
Marvin E. Maron
1961
Marvin Maron publikuje "Automatic Indexing" — wczesne zastosowanie klasyfikatora bayesowskiego do automatycznej kategoryzacji dokumentów.
1973
Duda i Hart formalizują Naive Bayes w klasycznym podręczniku "Pattern Classification and Scene Analysis".
1997
Domingos i Pazzani publikują "On the Optimality of the Simple Bayesian Classifier under Zero-One Loss", tłumacząc dlaczego NB działa dobrze mimo naruszenia założenia niezależności.
1998
McCallum i Nigam porównują modele multinomial i Bernoulli NB do klasyfikacji tekstu — praca staje się standardowym odniesieniem w NLP.
2002
Paul Graham publikuje "A Plan for Spam" — bayesowskie filtry spamu stają się powszechne w klientach pocztowych.

Złożoność obliczeniowa

Charakterystyki obliczeniowe
→Złożoność treningu: O(N·d), gdzie N to liczba przykładów, d to liczba cech
→Złożoność predykcji: O(d·C), gdzie C to liczba klas
→Pamięć: O(d·C) — tablica prawdopodobieństw warunkowych
→Brak iteracji optymalizacyjnych — trening to pojedyncze zliczenie statystyk
→Trywialnie zrównoleglalny po cechach i po klasach
Uwagi do benchmarku

W klasyfikacji tekstu (np. 20 Newsgroups, Reuters-21578) multinomial Naive Bayes osiąga zwykle 70–85% trafności, ustępując regresji logistycznej i SVM o kilka punktów procentowych przy dużych zbiorach danych. W filtrowaniu spamu historycznie osiągał >95% precyzji, co zapoczątkowało erę bayesowskich filtrów e-mail. Jako baseline w NLP nadal wykorzystywany w pracach naukowych.