Naiwny klasyfikator bayesowski

Z Wikipedii

Naiwny klasyfikator bayesowski jest prostym probabilistycznym klasyfikatorem. Naiwne klasyfikatory bayesowskie są oparte na założeniu o wzajemnej niezależności predyktorów (zmiennych niezależnych). Często nie mają one żadnego związku z rzeczywistością i właśnie z tego powodu nazywamy je naiwnymi. Bardziej opisowe może być określenie - "model cech niezależnych". Ponadto model prawdopodobieństwa można wyprowadzić korzystając z twierdzenia Bayesa.

W zależności od rodzaju dokładności modelu prawdopodobieństwa, naiwne klasyfikatory bayesowskie można "uczyć" bardzo skutecznie w trybie uczenia z nadzorem. W wielu praktycznych aplikacjach, estymacja parametru dla naiwnych modeli Bayesa używa metody maksymalnego prawdopodobienstwa a posteriori; inaczej mówiąc, może pracować z naiwnym modelem Bayesa bez wierzenia w twierdzenie Bayesa albo używania jakichś metod Bayesa.

Pomimo ich naiwnego projektowania i bardzo uproszczonych założeń, naiwne klasyfikatory Bayesa często pracują dużo lepiej w wielu rzeczywistych sytuacjach niż można było tego oczekiwać.

Spis treści

1 Naiwny model probabilistyczny Bayesa
2 Estymacja parametru
3 Konstrukcja klasyfikatora z modelu probabilistycznego
4 Omówienie
5 Przykład: klasyfikacja dokumentu
6 Linki zewnętrzne

[edytuj] Naiwny model probabilistyczny Bayesa

Model prawdopodobieństwa dla klasyfikatora jest modelem warunkowym

$p(C \vert F_1,\dots,F_n)\,$

przez zmienną zależną klasy $C$ z niewielu rezultatów albo " klas", zależnych od kilku opisujących zmiennych $F 1$ do $F n$ . Problem pojawia się, gdy liczba cech $n$ jest duża lub gdy cecha może przyjmować dużą liczbę wartości. Wtedy opieranie się na modelu tablic prawdopodobieństw jest niewykonalne. Dlatego też inaczej formułujemy taki model, by był bardziej przystępny.

Korzystając z twierdzenia Bayesa piszemy:

$p(C \vert F_1,\dots,F_n) = \frac{p(C) \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)}. \,$

W praktyce interesuje nas tylko licznik ułamka, bo mianownik nie zależy od $C$ i wartości cechy $F i$ sa dane. Mianownik jest więc stały. Licznik ułamka jest równoważny do łącznego modelu prawdopodobieństwa

$p(C, F_1, \dots, F_n)\,$

który można zapisać, wykorzystując prawdopodobieństwo warunkowe

$p(C, F_1, \dots, F_n)\,$

$= p(C) \ p(F_1,\dots,F_n\vert C)$

$= p(C) \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1)$

$= p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3,\dots,F_n\vert C, F_1, F_2)$

$= p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3)$

i tak dalej . Włączamy teraz "naiwną" warunkową zależność. Zakładając, że każda cecha $F i$ jest warunkowo niezależnaod każdej innej cechy

F j

dla $j\neq i$ . Oznacza to

$p(F_i \vert C, F_j) = p(F_i \vert C)\,$

więc model można wyrazić jako

$p(C, F_1, \dots, F_n) = p(C) \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots\,$

$= p(C) \prod_{i=1}^n p(F_i \vert C).\,$

Oznacza to, że pod powyższymi niezależnymi założeniami, warunkowe rozmieszczenie nad klasą zmiennych $C$ można zapisać

$p(C \vert F_1,\dots,F_n) = \frac{1}{Z} p(C) \prod_{i=1}^n p(F_i \vert C)$

gdzie $Z$ jest współczynnikiem skalowania zależnym wyłącznie od $F_1,\dots,F_n$ .

Modele tej formy są łatwiejsze do zrealizowania, gdy rozłożymy je na czynniki zwane klasą "prior" $p (C)$ i niezależny rozkład prawdopodobieństwa $p(F_i\vert C)$ . Jeśli są klasy $k$ i jeśli model dla $p (F i)$ może być wyrażony przez parametr $r$ , wtedy odpowiadający naiwny model Bayesa ma (k − 1) + n r k parametrów. W praktyce często $k = 2$ (klasyfikacja binarna) i $r = 1$ (zmienna Bernouliego jako cecha), wtedy całkowita liczba parametrów naiwnego modelu Bayesa to $2 n + 1$ , gdzie $n$ jest liczbą binarnych użytych cech.

[edytuj] Estymacja parametru

W przypadku uczenia z nadzorem, chcemy ocenić parametry probabilistycznego modelu. Z powodu niezależnych cech założenia, wystarczy ocenić klasę poprzednią i zależną cechę modelu niezależnie, wykorzystując metodę maksimum prawdopodobieństwa a posteriori (MAP), wnioskowanie Bayesa lub inną parametryczną procedurę estymacji.

[edytuj] Konstrukcja klasyfikatora z modelu probabilistycznego

Dotychczasowe omówienie problemu wyprowadziło model niezależnych cech, które są naiwnym probabilistycznym modelem Bayesa. Naiwny klasyfikator bayesowski łączy ten model z regułą decyzyjną. Jedna, ogólna reguła ma wydobyć hipotezę najbardziej prawdopodobną. Odpowiadający klasyfikator jest funkcją $classify$ , zdefiniowaną

$\mathrm{classify}(f_1,\dots,f_n) = \mathop{\mathrm{argmax}}_c \ p(C=c) \prod_{i=1}^n p(F_i=f_i\vert C=c)$

[edytuj] Omówienie

Naiwny klasyfikator bayesowski ma wiele własności, które okazują się zaskakująco przydatne w praktyce, pomimo faktu, że niezależne założenia często są naruszone. Jak wszystkie probabilistyczne klasyfikatory, wykorzystujące regułą decyzyjną MAP, klasyfikacja jest tak długo poprawna, jak długo poprawna klasa jest bardziej prawdopodobna od innych (prawdopodobieństwa poszczególnych klas nie muszą być oceniane zbyt dokładnie). Inaczej mówiąc, klasyfikator jest wystarczająco mocny, by zignorować poważne niedociągnięcia naiwnego probabilistycznego modelu.

[edytuj] Przykład: klasyfikacja dokumentu

Przedstawiony zostawnie tu problem klasyfikacji dokumentów metodą naiwnego klasyfikatora Bayesa. Rozważać będziemy klasyfikację poczty email pod względem zawartości i oceniać czy poszczególne wiadomości są chcianą pocztą czy też spamem. Wyobraźmy sobie, że dokumenty są przypisane do pewnej liczby klas dokumentów, które mogą być modelowane jako komplety słów, gdzie (niezależne) prawdopodobieństwo, że i-te słowo danego dokumentu zdarza się w dokumencie klasy C zapisujemy, jako

$p(w_i \vert C)\,$

Zakładamy, że prawdopodobieństwo wystąpienia słowa w dokumencie jest niezależne od długości dokumentu lub też, że wszystkie dokumenty mają tę samą długość.

Wtedy prawdopodobieństwo danego dokumentu "D", klasy "C"

$p(D\vert C)=\prod_i p(w_i \vert C)\,$

Pytanie, na które chcemy odpowiedzieć to: "jakie jest prawdopodobieństwo, że dany dokument D należy do danej klasy C?"

Korzystając z definicji

$p(D\vert C)={p(D\cap C)\over p(C)}$

$p(C\vert D)={p(D\cap C)\over p(D)}$

$p(C\vert D)={p(C)\over p(D)}\,p(D\vert C)$

Przyjmijmy założenie, że są tylko dwie klasy: S i ¬S (w naszym przykładzie: spam i nie-spam).

$p(D\vert S)=\prod_i p(w_i \vert S)\,$

$p(D\vert\neg S)=\prod_i p(w_i\vert\neg S)\,$

Korzystając z Bayesianu, powyższy rezultat zapisać możemy jako

$p(S\vert D)={p(S)\over p(D)}\,\prod_i p(w_i \vert S)$

$p(\neg S\vert D)={p(\neg S)\over p(D)}\,\prod_i p(w_i \vert\neg S)$

Dzieląc jeden przez drugi otrzymujemy:

${p(S\vert D)\over p(\neg S\vert D)}={p(S)\,\prod_i p(w_i \vert S)\over p(\neg S)\,\prod_i p(w_i \vert\neg S)}$

Możemy to przekształcić do postaci

${p(S)\over p(\neg S)}\,\prod_i {p(w_i \vert S)\over p(w_i \vert\neg S)}$

W ten sposób, prawdopodobieństwo stosunku p(S | D) / p(¬S | D) może być wyrażone jako stosunek prawdopodobieństw. Bieżące prawdopodobieństwo p(S | D) można obliczyć jako log (p(S | D) / p(¬S | D)), korzystając z własności, że p(S | D) + p(¬S | D) = 1.

Otrzymujemy więc:

$\ln{p(S\vert D)\over p(\neg S\vert D)}=\ln{p(S)\over p(\neg S)}+\sum_i \ln{p(w_i\vert S)\over p(w_i\vert\neg S)}$

W końcu możemy sklasyfikować dany dokument. Jest to spam, jeśli $\ln{p(S\vert D)\over p(\neg S\vert D)} > 0$ . W innym wypadku dokument spamem nie jest.