Metody odkrywania wiedzy: wykład 6
Klasyfikacja bayesowska

Paweł Cichosz

Date: 2001/2002

Przedmiotem wykładu są metody uczenia się pojęć polegające na określaniu prawdopodobieństw kategorii w zależności od wartości atrybutów na podstawie danych trenujących bez tworzenia symbolicznej reprezentacji hipotezy.

Twierdzenie Bayesa

Podstawą probabilistycznych metod uczenia się jest twierdzenie podane przez Thomasa Bayesa, XVIII-wiecznego matematyka angielskiego. W kontekście metod uczenia się i odkrywania wiedzy wzór będący treścią tego twierdzenia podaje się zazwyczaj w postaci:

$$\mathrm{Pr}(h\,\vert\,D) = \frac{\mathrm{Pr}(h)\mathrm{Pr}(D\,\vert\,h)} {\mathrm{Pr}(D)}$$ (1)

gdzie $h$ oznacza pewną hipotezę i $D$ oznacza dane (fakty, obserwacje), które mogą wpłynąć na ocenę prawdopodobieństwa tej hipotezy. $\mathrm{Pr}(h)$ jest prawdopodobieństwem a priori hipotezy $h$, określonym bez uwzględniania jakichkolwiek danych. $\mathrm{Pr}(h\,\vert\,D)$ jest prawdopodobieństwem a posteriori hipotezy $h$ przy znajomości danych $D$. Określa się je zgodnie ze wzorem Bayesa na podstawie jej prawdopodobieństwa a priori oraz prawdopodobieństwa danych $D$ przy założeniu prawdziwości hipotesy $h$, $\mathrm{Pr}(D\,\vert\,h)$, i prawdopodobieństwa danych $D$, $\mathrm{Pr}(D)$.

W większości przypadków celem wyznaczania prawdopodobieństw a posteriori jest wybór hipotezy najbardziej prawdopodobnej w świetle zaobserwowanych danych. Wówczas, ponieważ interesują nas nie tyle bezwzględne wartości tych prawdopodobieństw, co raczej ich porównywanie, występujące w mianowniku we wzorze Bayesa prawdopodobieństwo danych $\mathrm{Pr}(D)$, skoro nie zależy od hipotez, nie wpływa na wynik i może być pominięte. Przy porównaniu wystarczy uwzględnić występujący we wzorze w liczniku iloczyn $\mathrm{Pr}(h)\mathrm{Pr}(D\,\vert\,h)$.

Jeśli z pewnych względów interesuje nas bezwzględna wartość $\mathrm{Pr}(h\,\vert\,D)$, to potrzebne do jej obliczenia prawdopodobieństwo $\mathrm{Pr}(D)$ może być przy pewnych założeniach uzyskane na podstawie łatwiejszych na ogół do wyznaczenia prawdopodobieństw $\mathrm{Pr}(D\,\vert\,h)$ dla różnych hipotez $h$. Załóżmy mianowicie, dostępna jest wyłącznie skończona liczba wykluczających się parami hipotez, które wyczerpują wszystkie możliwości, czyli

$$(\forall h_1,h_2)\;\mathrm{Pr}(h_1\land h_2) ={}$$ 0, (2)

$$\sum_h\mathrm{Pr}(h) ={} 1$$ (3)

Pierwszy z powyższych warunków mówi, że żadne dwie hipotezy nie są jednocześnie poprawne, drugi zaś, że poprawna jest przynajmniej jedna z nich. Przyjmując te założenia możemy obliczyć $\mathrm{Pr}(D)$ ze wzoru na prawdopodobieństwo całkowite:

$$\mathrm{Pr}(D) = \sum_h\mathrm{Pr}(h)\mathrm{Pr}(D\,\vert\,h)$$ (4)

Prawdopodobieństwa hipotez w uczeniu się pojęć

Interpretując wzór Bayesa w kontekściu uczenia się pojęć rozważamy oczywiście hipotezy jako funkcje klasyfikujące elementy dziedziny $X$ do kategorii z pewnego zbioru $C$, a rolę danych pełni zbiór trenujący $T\subset X$ z danymi etykietami pojęcia docelowego.

Klasyfikator MAP

Najbardziej bezpośrednie zastosowanie wzoru Bayesa do uczenia się klasyfikacji polegałoby na określaniu prawdopodobieństw poszczególnych hipotez na podstawie zbioru trenującego i wyborze hipotezy o maksymalnym prawdopodobieństwie a posteriori. Taki algorytm uczenia się klasyfikacji jest nazywany algorytmem MAP. Jego wynikiem jest hipoteza określona w następujący sposób:

$$h_{\mathrm{MAP}}=\mathrm{arg}\max_h\mathrm{Pr}(h\,\vert\,T)$$ (5)

Takie podejście ma niestety poważne wady: można je zastosować tylko wtedy, gdy liczba możliwych hipotez jest skończona i na tyle niewielka, aby koszt obliczeniowy wyboru najbardziej prawdopodobnej był do przyjęcia. Z kolei takie zawężenie przestrzeni rozważanych hipotez zmniejsza szansę na wystarczająco dokładne przybliżenie pojęcia docelowego.

Optymalny klasyfikator bayesowski

Algorytm MAP polega na wyborze spośród ustalonego zestawu możliwych hipotez jednej, uznanej za najbardziej prawdopodobną. Jest jednak możliwe inne podejście, polegające na sformułowaniu na podstawie tych hipotez, z uwzględnieniem ich prawdopodobieństw, nowej hipotezy, która mogłaby być lepsza od najlepszej z nich. W ten sposób działa optymalny klasyfikator bayesowski, który zamiast szukać najbardziej prawdopodobnej hipotezy, dla każdego klasyfikowanego przykładu szuka najbardziej prawdopodobnej kategorii.

Najbardziej prawdopodobną kategorię dowolnego przykładu $x$ otrzymuje się uwzględniając kategorie, do których zaliczają ten przykład wszystkie hipotezy rozważanej przestrzeni hipotez, dla każdej z tych kategorii sumując prawdopodobieństwa a posteriori wszystkich hipotez, według których przykład do niej należy. Kategorią najbardziej prawdopodobną jest oczywiście ta, dla której uzyskana suma prawdopodobieństw jest największa. Bardziej formalnie prawdopodobieństwo tego, że pewien dowolnie wybrany przykład $x\in X$ należy do kategorii $d\in C$ pojęcia docelowego $c$ szacowane na podstawie zbioru $T$ etykietowanych przykładów tego pojęcia, możemy wyrazić w następujący sposób:

$$\mathrm{Pr}\big(c(x)=d\,\vert\,T\big) = \sum_h\mathrm{Pr}\big(c(x)=d\,\vert\,h\big)\mathrm{Pr}(h\,\vert\,T)$$ (6)

przy czym dla każdej hipotezy $h$

$$\mathrm{Pr}\big(c(x)=d\,\vert\,h\big) = \begin{cases}1 & \text{jeśli $h(x)=d$,}\\ 0 & \text{w przeciwnym przypadku.} \end{cases}$$ (7)

Algorytm ten również obarczony jest tą wadą, że ze względu na koszt obliczeniowy liczba rozważanych w nim hipotez nie może być zbyt wielka, lecz jego zaletą jest to, że klasyfikując przykłady potrafi poza ten przyjęty ograniczony zestaw hipotez wykroczyć.

Prawdopodobieństwo danych

Do stosowania dwóch sformułowanych wyżej metod klasyfikacji probabilistycznej nie jest potrzebne wyznaczanie prawdopodobieństwa zbioru trenującego $\mathrm{Pr}(T)$, ale niezbędne jest wyznaczenie warunkowych prawdopodobieństw $\mathrm{Pr}(T\,\vert\,h)$ dla poszczególnych hipotez $h$.

Prawdopodobieństwo danych trenujących do uczenia się pojęć jest w istocie prawdopodobieństwem zawartej w nich w postaci etykiet przykładów informacji wpływającej na ocenę hipotez. Ważne jest więc tylko, jak prawdopodobne są takie a nie inne etykiety przykładów w zbiorze $T$, a nie same przykłady wchodzące w jego skład. Pozostaje określić, jak na ocenę prawdopodobieństwa etykiet przykładów trenujących wpływają hipotezy. Prawdopodobieństwo $\mathrm{Pr}(T\,\vert\,h)$ mówi o tym, jak bardzo prawdopodobne jest, aby przykłady ze zbioru $T$ miały takie etykiety kategorii, jakie faktycznie występują w zbiorze $T$, jeśli poprawna jest hipoteza $h$, czyli jeśli hipoteza $h$ jest identyczna z pojęciem docelowym. Jeśli przy tym zbiór trenujący jest poprawny, czyli występujące w nim etykiety przykładów są rzeczywiście etykietami kategorii, jakie przyporządkowuje im pojęcie $c$, to dla dowolnej hipotezy $h$

$$\mathrm{Pr}(T\,\vert\,h) = \begin{cases}1 & \text{jeśli $h$\ jest spójna z $c$\ na zbiorze $T$,}\\ 0 & \text{w przeciwnym przypadku.} \end{cases}$$ (8)

Ta prosta sytuacja komplikuje się, jeśli dopuścimy niepoprawność zbioru trenującego. Aby wówczas móc również wyznaczyć interesujące nas prawdopodobieństwa, musimy znać probabilistyczny model przekłamań, jakie mogą występować w zbiorze trenującym. Rozważymy tu najprostszy przypadek, kiedy każdy przykład $x\in T$ może mieć z takim samym prawdopodobieństwem $0\leq p\leq 1$ etykietę w zbiorze $T$ różną od poprawnej etykiety $c(x)$. Dla hipotez spójnych ze zbiorem trenującym warunkowe prawdopodobieństwo tego zbioru może być wówczas mniejsze niż $1$, zaś dla hipotez niespójnych może być większe niż 0. Niech $r^c_T(h)$ oznacza liczbę pomyłek hipotezy $h$ na zbiorze $T$, czyli liczbę przypadków niezgodności etykiet przypisywanych przykładom przez tę hipotezę z ich poprawnymi kategoriami pojęcia docelowego $c$. Jeśli $c'$ oznacza pojęcie ,,przekłamane'', którego etykiety faktycznie występują w dostarczonym uczniowi zbiorze trenującym, to możemy zapisać:

$$\mathrm{Pr}(T\,\vert\,h) = (1-p)^{\vert T\vert-r^{c'}_T(h)}p^{r^{c'}_T(h)}$$ (9)

Jeśli $p<0.5$, czyli wystąpienie przekłamania jest mniej prawdopodobne niż jego brak, prawdopodobieństwo a posteriori hipotezy jest tym większe, im mniejsza jest liczba jej pomyłek, co jest całkiem rozsądną zależnością.

Naiwny klasyfikator bayesowski

Naiwny klasyfikator bayesowski jest wolny od problemów związanych z obliczaniem prawdopodobieństw a posteriori dla wszystkich hipotez pewnej ustalonej przestrzeni dzięki temu, że żadnej takiej przestrzeni nie rozważa, lecz raczej reprezentuje hipotezy za pomocą tworzonych na podstawie zbioru trenującego oszacowań pewnych prawdopodobieństw i klasyfikuje przykłady, wybierając dla nich kategorie najbardziej prawdopodobne w świetle tych oszacowań. Pod tym względem przypomina optymalny klasyfikator bayesowski, różni się jednak od niego tym, że nie wykorzystuje żadnych innych hipotez nawet w celach pomocniczych.

Szacowanie prawdopodobieństw

Naiwny klasyfikator bayesowski zakłada, tak jak wcześniej poznane przez nas algorytmy indukcji, że przykłady są opisane za pomocą pewnego zestawu atrybutów $a_1,a_2,\dots,a_n$, przy czym ograniczamy się tymczasem do atrybutów o wartościach dyskretnych (nominalnych lub porządkowych). Na podstawie zbioru trenującego $T$ są szacowane prawdopodobieństwa poszczególnych kategorii pojęcia docelowego $c$ oraz prawdopodobieństwa poszczególnych wartości wszystkich atrybutów dla przykładów różnych kategorii. Założymy, że zbiór trenujący składa się z przykładów wybranych z dziedziny zgodnie z pewnym rozkładem prawdopodobieństwa $\Omega$ i w związku z tym prawdopodobieństwa szacowane podczas uczenia się będą prawdopodobieństwami przy założeniu wyboru przykładów zgodnie z tym rozkładem. Interesujące nas oszacowania dotyczą prawdopodobieństw $\mathrm{Pr}_{x\in\Omega}(c(x)=d)$ dla wszystkich kategorii $d\in C$ pojęcia docelowego $c$ oraz $\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,c(x)=d\big)$ dla wszystkich kategorii $d\in C$ oraz wartości $v\in A_i$ dla $i=1,2,\dots,n$, przy czym $A_i$ jest przeciwdziedziną atrybutu $a_i$. Prawdopodobieństwa te szacuje się na podstawie częstości występowania w zbiorze trenującym przykładów o odpowiednich kategoriach i wartościach atrybutów, przy czym można stosować albo bezpośrednie szacowanie, albo $m$-szacowanie. Przy pierwszym podejściu należy zapobiec występowaniu prawdopodobieństw równych 0 w sytuacji, gdy w zbiorze $T$ nie ma żadnego przykładu spełniającego określone warunku, zastępując je pewną niewielką, lecz dodatnią wartościa $\epsilon$ (mniejszą niż prawdopodobieństwo, jakie otrzymalibyśmy, gdyby znalazł się $1$ taki przykład). Przy drugim podejściu prawdopodobieństwa zerowe nie wystąpią.

Szacowanie prawdopodobieństw wartości atrybutów ma sens wyłącznie dla atrybutów nominalnych i porządkowych, nie zaś ciągłych. Nie jest jednak przy tym w praktyce konieczne, aby atrybuty miały skończoną liczbę wartości. Do oszacowania prawdopodobieństw wystarczy, że w zbiorze trenującym występuje ich skończona liczba. Dla wszystkich wartości nie występujących w zbiorze trenującym można przyjąć ustalone małe prawdopodobieństwo $\epsilon$.

Klasyfikowanie przykładów

Załóżmy, że dany jest pewien przykład $x_*\in X$ i należy, przy dostępnych oszacowaniach prawdopodobieństw $\mathrm{Pr}_{x\in\Omega}(c(x)=d)$ dla wszystkich $d\in C$ oraz $\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v\,\vert\,c(x)=d\big)$ dla $i=1,2,\dots,n$, wszystkich $v\in A_i$ i $d\in C$, wyznaczyć kategorię tego przykładu. Naiwny klasyfikator bayesowski wybiera wówczas kategorię najbardziej prawdopodobną, przy czym chodzi o wybór kategorii najbardziej prawdopodobnej dla przykładu o znanych wartościach atrybutów. Definicję odpowiedniej hipotezy $h$ możemy zapisać następująco:

$$\begin{split}h(x_*) ={}& \mathrm{arg}\max_{d\in C} \mathrm{Pr... ...t\,} {}\land\dots\land a_n(x)=a_n(x_*)\big)\text{,} \end{split}$$ (10)

lub krócej

$$h(x_*) = \mathrm{arg}\max_{d\in C} \mathrm{Pr}_{x\in\Omega}\Big(c(x)=d \,\big\vert\,\bigwedge_{i=1}^na_i(x)=a_i(x_*)\Big)$$ (11)

przy czym symbol $\bigwedge$ służy do zwartego zapisu koniunkcji $n$ równości. Oznacza to wybór dla przykładu $x_*$ kategorii najbardziej prawdopodobnej dla dowolnego przykładu wybranego z dziedziny $X$ według rozkładu $\Omega$, który jest opisany przez wektor wartości atrybutów $\langle a_1(x_*),a_2(x_*),\dots,a_n(x_*)\rangle$. Występujące w powyższym równaniu prawdopodobieństwo można z kolei korzystając ze wzoru Bayesa przekształcić do postaci:

$$\frac{\mathrm{Pr}_{x\in\Omega}(c(x)=d)\cdot \mathrm{Pr}_{x\in\Ome... ...)=d\Big)} {\mathrm{Pr}_{x\in\Omega} \Big(\bigwedge_{i=1}^na_i(x)=a_i(x_*)\Big)}$$ (12)

przy czym w dalszym ciągu możemy się zajmować wyłącznie licznikiem tego ułamka, gdyż mianownik, który nie zależy od kategorii, nie wpływa na maksymalizację prawdopodobieństwa dla $d\in C$.

Ponieważ wartości $\mathrm{Pr}_{x\in\Omega}(c(x)=d)$ znamy, pozostaje określić sposób obliczania prawdopodobieństw postaci

$$\mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i=1}^na_i(x)=v_i\,\big\vert\,c(x)=d\Big)$$ (13)

dla dowolnych $v_i\in A_i$, $i=1,2,\dots,n$, i $d\in C$. Naiwny sklasyfikator bayesowski zakłada, że wartości poszczególnych atrybutów są od siebie warunkowo (względem kategorii) niezależne, czyli że zachodzi następująca równość:

$$\begin{split}&\mathrm{Pr}_{x\in\Omega} \Big(\bigwedge_{i=1}^n... ...\Omega} \big(a_i(x)=v_i\,\vert\,c(x)=d\big)\text{.} \end{split}$$ (14)

Na ogół trudno określić, czy założenie to jest spełnione i można przypuszczać, że dla wielu dziedzin spełnione nie jest. Na przyjęciu mimo to takiego założenia polega właśnie ,,naiwność'', która znalazła odzwierciedlenie w zwyczajowej nazwie algorytmu. Nawet jednak jeśli założenie to jest samo w sobie istotnie naiwne, oparty na nim algorytm okazał się na tyle skuteczny, aby był stosowany mimo zniechęcającej nazwy. Ostateczną postać hipotezy reprezentowanej przez rozkłady prawdopodobieństw szacowane przez naiwny klasyfikator bayesowski można zapisać następująco:

$$\begin{split}h(x_*) ={}& \mathrm{arg}\max_{d\in C} \mathrm{Pr... ...ga}\big(a_i(x)=a_i(x_*)\,\vert\,c(x)=d\big)\text{.} \end{split}$$ (15)

Dokonanie klasyfikacji przykładu wymaga więc wymnożenia dla każdej kategorii pewnej liczby oszacowanych na podstawie zbioru trenującego prawdopodobieństw, wybieranych w zależności od wartości atrybutów klasyfikowanego przykładu. W podejściu tym w wyjątkowo prosty sposób można traktować brakujące wartości atrybutów. Jeśli dla przykładu $x_*$ wartość pewnego atrybutu $a_i$ nie jest znana, wystarczy przyjąć $\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=a_i(x_*)\,\vert\,c(x)=d\big)=1$, zapewniając w ten sposób, że atrybut ten nie będzie uwzględniany przy jego klasyfikacji. Klasyfikacja zostanie wówczas dokonana na podstawie znanych wartości atrybutów.

W wielu zastosowaniach, nawet kiedy założenie o niezależności jest w oczywisty sposób nie spełnione, naiwny klasyfikator bayesowski okazuje się bardzo skutecznym algorytmem, czasem nawet porównywalnym z omawianymi przez nas wcześniej zaawansowanymi algorytmami indukcji drzew decyzyjnych lub reguł. Przy tym wymagany nakład obliczeń jest znacznie mniejszy. Szczególnie dobre efekty osiągano stosując naiwny klasyfikator bayesowski do klasyfikacji tekstów, o czym powiemy więcej w jednym z przykładów.

Zagadnienia praktyczne

Brakujące wartości atrybutów

W naiwnym klasyfikarorze bayesowskim w wyjątkowo prosty sposób można traktować brakujące wartości atrybutów przy klasyfikacji przykładu. Jeśli dla przykładu $x_*$ wartość pewnego atrybutu $a_i$ nie jest znana, wystarczy przyjąć $\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=a_i(x_*)\,\vert\,c(x)=d\big)=1$, zapewniając w ten sposób, że atrybut ten nie będzie uwzględniany przy jego klasyfikacji (nie wpłynie na obliczany iloczyn prawdopodobieństw). Klasyfikacja zostanie wówczas dokonana na podstawie znanych wartości atrybutów.

Atrybuty ciągłe

W przedstawionej wcześniej postaci naiwny klasyfikator bayesowski, prezentowany jako praktyczny algorytm uczenia się pojęć, może być stosowany dla dziedzin opisywanych wyłącznie przez atrybuty nominalne lub porządkowe, przy czym w tym drugim przypadku relacja porządku nie jest w żaden sposób wykorzystywana, co może niekorzystnie wpływać na jakość uzyskiwanej hipotezy. Jeśli jednak algorytm ma być rzeczywiście w pełni praktyczny, należy wskazać możliwości przezwyciężenia lub ominięcia tego ograniczenia, tak aby było możliwe korzystanie z niego dla dowolnej dziedziny, dla której może być określone zadanie uczenia się pojęć.

Aby możliwe było stosowanie naiwnego klasyfikatora bayesowskiego dla dziedzin opisanych przez atrybuty ciągłe, możemy zastąpić prawdopodobieństwa wartości atrybutów odpowiednimi funkcjami gęstości. Umożliwia to sformułowanie zmodyfikowanej hipotezy:

$$h(x_*) = \mathrm{arg}\max_{d\in C} \mathrm{Pr}_{x\in\Omega}(c(x)=d)\cdot \prod_{i=1}^n g^{i,d}_{\Omega}(a_i(x_*))$$ (16)

przy czym $g^{i,d}_{\Omega}$ jest warunkową funkcją gęstości prawdopodobieństwa wartości ciągłego atrybutu $a_i$ przy danej kategorii przykładu $d$ dla przykładów wybranych z dziedziny zgodnie z rozkładem $\Omega$. Oczywiście nie ma żadnych przeszkód w stosowaniu naiwnego klasyfikatora bayesowskiego także do mieszanych przestrzeni atrybutów. Wówczas dla atrybutów ciągłych do obliczania powyższego iloczyny brane będą wartości funkcji gęstości, a dla atrybutów nominalnych i porządkowych -- prawdopodobieństwa.

Funkcja gęstości dla każdego atrybutu i każdej kategorii musi oczywiście zostać wyznaczona na podstawie zbioru trenującego. W tym celu, oddzielnie dla przykładów każdej kategorii, należy określić rozkład prawdopodobieństwa wartości atrybutu $a_i$ dla każdego $i=1,2,\dots,n$. Najprostsze podejście polega na założeniu pewnego standardowego rozkładu prawdopodobieństwa (zazwyczaj normalnego), dla którego funkcja gęstości jest wyrażona znanym wzorem zależnym od pewnych parametrów rozkładu. Na podstawie obserwowanych wartości atrybutu należy następnie oszacować te parametry. W szczególności w przypadku rozkładu normalnego wystarczy wyznaczyć wartość średnią i odchylenie standardowe. Problem występuje wtedy, kiedy nie wiadomo, do jakiego standardowego rozkładu prawdopodobieństwa obserwowane wartości atrybutu najlepiej pasują. W takiej sytuacji można ,,na próbę'' określić parametry różnych rozkładów i następnie zastosować test statystycznej zgodności, mierzący zgodność obserowanych wartości z wyznaczonym rozkładem. Dla atrybutu byłaby wtedy przyjmowana funkcja gęstości dla tego rozkładu prawdopodobieństwa, dla którego uzyskano największą zgodność. W praktyce najczęściej jednak odstępuje się od takiej próby dopasowania, zakładając rozkład normalny.

Często bardziej skuteczną alternatywą wykorzystania funkcji gęstości, zwłaszcza jeśli rozkłady prawdopodobieństwa dla wartości atrybutów nie są znane, jest poddanie tych atrybutów dyskretyzacji. Z kolei dla atrybutów porządkowych o dużej liczbie wartości można dokonać, korzystając z podobnych metod, ich agregacji.

Uwzględnianie kosztów pomyłek

Nawet najlepszy algorytm uczenia się, korzystający z ograniczonego zbioru trenującego, nie będzie mógł w każdej sytuacji wygenerować hipotezy, która klasyfikowałaby poprawnie dowolne przykłady spoza tego zbioru. Pomyłki przy klasyfikacji zawsze mogą wystąpić, chociaż oczywiście algorytmy projektuje się tak, aby zminimalizować ich oczekiwaną liczbę, czyli uzyskać hipotezy o jak najmniejszym błędzie rzeczywistym. Niekiedy jednak nie wszystkie pomyłki są traktowane tak samo. Niektóre rodzaje pomyłek mogą być w pewnych zastosowaniach bardziej groźne od innych. Zależy to na ogół od specyficznych cech dziedziny i sposobu, w jaki hipoteza ma być praktycznie używana. W systemie wykrywania nadużyć fałszywy alarm może być na przykład mniej groźny niż przeoczenie faktycznego nadużycia. Podobnie w systemie wspomagania diagnostyki medycznej błędna diagnoza w przypadku groźnych chorób niesie ze sobą znacznie poważniejsze skutki niż w przypadku drobnych dolegliwości. Uwzględnienie kosztów pomyłek przy uczeniu się pojęć może być w ogólny sposób zrealizowane przez określenie dla każdych dwóch kategorii $d_1,d_2\in C$ kosztu $\rho(d_1,d_2)$ związanego z pomyłkowym podaniem kategorii $d_1$ dla przykładu, którego poprawną kategorią jest $d_2$. Koszty mogą być dowolnymi liczbami dodatnimi, chociaż wygodnie jest ograniczyć się do wartości z przedziału $[0,1]$.

Naiwny klasyfikator bayesowski umożliwia uwzględnienie kosztów pomyłek przy wyborze kategorii w bardzo bezpośredni sposób. Jeśli sformułujemy cel, jakim należy się kierować przy wyborze kategorii dla klasyfikowanego przykładu, jako minimalizację oczekiwanego kosztu pomyłki, to definicję realizującej ten cel hipotezy możemy zapisać następująco:

$$\begin{split}h(x_*) ={}& \mathrm{arg}\min_{d\in C}\sum_{d'\in... ...vert\,\bigwedge_{i=1}^na_i(x)=a_i(x_*)\Big)\text{.} \end{split}$$ (17)

Korzystając z twierdzenia Bayesa i zakładając ,,naiwnie'' niezależność wartości atrybutów, uzyskujemy uwzględniającą koszty pomyłek wersję naiwnego klasyfikatora bayesowskiego zdefiniowaną za pomocą formuły:

$$\begin{split}h(x_*) ={}& \mathrm{arg}\min_{d\in C}\sum_{d'\in... ...} \big(a_i(x)=a_i(x_*)\,\vert\,c(x)=d'\big)\text{.} \end{split}$$ (18)

Problemy obliczeniowe

Implementując naiwny klasyfikator bayesowski można spodziewać się trudności przy jego stosowaniu, objawiających się niepoprawnymi wynikami lub błędami występującymi podczas wykonywania programu. Przyczynę tych trudności można dostrzec w obliczaniu iloczynu prawdopodobieństw:

$$\prod_{i=1}^n\mathrm{Pr}_{x\in\Omega}\big(a_i(x)=v_i\,\vert\,c(x)=d\big)$$ (19)

Jeśli każde z mnożonych w ten sposób prawdopodobieństw jest małe, czego można się na ogół spodziewać, a ponadto liczba określonych na dziedzinie atrybutów jest znaczna (powiedzmy, kilkanaście lub więcej), to podczas obliczania takiego iloczynu może wystąpić błąd niedomiaru związany z ograniczoną precyzją arytmetyki zmiennopozycyjnej komputerów. Zależnie od implementacji arytmetyki w używanym języku programowania może to spowodować bądź przyjęcie wartości 0 dla obliczanego iloczynu, bądź zgłoszenie błędu wykonania programu.

Dość prostym, ale skutecznym wybiegiem, który może wskazany problem wyeliminować, jest zastąpienie w implementacji algorytmu prawdopodobieństw ich logarytmami i konsekwentnie iloczynów sumami. Opisujące sposób klasyfikowania przykładów przez naiwny klasyfikator bayeswski równanie można przepisać wówczas w następującej postaci:

$$\begin{split}h(x_*) ={}&\mathrm{arg}\max_{d\in C}\bigg[\log\m... ...g(a_i(x)=a_i(x_*)\,\vert\,c(x)=d\big)\bigg]\text{.} \end{split}$$ (20)

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdziały 5.2, 5.3, 5.6, 5.7).
2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdział 4.2.)

About this document ...

Metody odkrywania wiedzy: wykład 6
Klasyfikacja bayesowska

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w6.tex

The translation was initiated by Pawel Cichosz on 2004-02-12