Metody odkrywania wiedzy: wykład 12
Sieci bayesowskie

Paweł Cichosz

Date: 2001/2002

Wykład jest poświęcony bardziej zaawansowanym probabilistycznym metodom odkrywania wiedzy i wnioskowania opartym na twierdzeniu wiedzy, czyli sieciom bayesowskim. Umożliwiają one reprezentowanie probabilistycznych zależności przyczynowych między dowolnymi atrybutami oraz wnioskowanie o rozkładzie prawdopodobieństwa nieznanych wartości atrybutów na podstawie znanych wartości atrybutów.

Uwagi terminologiczne

Mówiąc o sieciach bayesowskich będziemy, jak dotychczas, zakładać, że dana jest dziedzina $X$, na której określony jest pewien rozkład prawdopodobieństwa $\Omega$ oraz atrybuty $a_1,a_2,\dots,a_n$, $a_i:X\mapsto A_i$ dla $i=1,2,\dots,n$. Przyjmiemy ponadto, że są to wyłącznie atrybuty nominalne (lub atrybuty porządkowe, które, pomijając relację porządku, traktujemy jak nominalne). Nie będziemy natomiast włączać do tych rozważań żadnych pojęć docelowych, gdyż zamiast zależności takiego pojęcia od atrybutów interesować nas będą zależności między dowolnymi atrybutami. Ewentualne pojęcie docelowe może być wówczas traktowane jako jeden z atrybutów, w żaden sposób nie wyróżniany spośród innych. W ten sposób będzie możliwe prowadzenie rozważań na temat sieci bayesowskich bez zasadniczej zmiany terminologii i notacji przyjętej wcześniej dla indukcyjnego uczenia się. Ponieważ w badaniach dotyczących sieci bayesowskich dopiero od niedawna problemy uczenia się zyskały znaczącą pozycję, przyjmowana w nich tradycyjna terminologia jest nieco odmienna -- mówi się zazwyczaj o zmiennych zamiast o atrybutach, a dziedziną jest zbiór wszystkich możliwych przypisań wartości zmiennym. W naszym przypadku oznaczałoby to utożsamienie:

$$X \equiv{} A_1\times A_2\times\dots\times A_n$$ (1)

$$x \equiv{} \langle a_1(x),a_2(x),\dots,a_n(x)\rangle$$ (2)

Wówczas atrybuty mogłyby być traktowane istotnie nie jako funkcje, lecz jako zmienne, które mogą przyjmować wartości z odpowiednich przeciwdziedzin, zaś rozkład $\Omega$ jako łączny rozkład prawdopodobieństwa wartości tych zmiennych.

Struktura i interpretacja sieci bayesowskiej

Sieć bayesowska jest acyklicznym grafem skierowanym, złożonym z węzłów i łączących je krawędzi. Węzły odpowiadają wszystkim określonym na dziedzinie atrybutom. Możemy w związku z tym mówić dla wygody krótko o węźle $a_i$, mając na myśli węzeł odpowiadający atrybutowi $a_i$ dla dowolnego $i=1,2,\dots,n$. Krawędź skierowana od węzła $a_i$ do węzła $a_j$ może być intuicyjnie interpretowana jako reprezentacja bezpośredniej przyczynowej zależności atrybutu $a_j$ od atrybutu $a_i$, chociaż podamy bardziej ścisłą i formalną interpretację. Występowanie takiej krawędzi w sieci będziemy wyrażać pisząc $a_i\rightarrow a_j$.

Następniki i poprzedniki

Dla węzłów sieci można wprowadzić relację następstwa, oznaczaną za pomocą symbolu $\dashrightarrow$ i określoną w następujący sposób:

Węzeł $a_j$ jest następnikiem węzła $a_i$ (lub równoważnie węzeł $a_i$ jest poprzednikiem węzła $a_j$) w sieci bayesowskiej, co oznacza się przez $a_i\dashrightarrow a_j$, jeśli jest spełniony jeden z następujących warunków:

1. w sieci istnieje krawędź skierowana od węzła $a_i$ do węzła $a_j$, czyli $a_i\rightarrow a_j$,
2. w sieci istnieje krawędź skierowana od węzła $a_i$ do pewnego węzła $a_k$ i węzeł $a_j$ jest następnikiem węzła $a_k$, czyli $a_i\rightarrow a_k$ i  $a_k\dashrightarrow a_j$.

Zgodnie z tą definicją węzeł $a_j$ jest następnikiem węzła $a_i$, jeśli istnieje ścieżka złożona ze skierowanych krawędzi sieci, prowadząca od węzła $a_i$ do węzła $a_j$. Gdy $a_i\rightarrow a_j$, powiemy, że węzeł $a_j$ jest bezpośrednim następnikiem węzła $a_i$ oraz węzeł $a_i$ jest bezpośrednim poprzednikiem węzła $a_j$.

Dla dowolnego węzła $a_i$ zbiór numerów jego bezpośrednich poprzedników będziemy oznaczać przez $U_i$:

$$U_i = \{j\in N \;\vert\; a_j\rightarrow a_i\}$$ (3)

przy czym $N=\{1,2,\dots,n\}$ oznacza zbiór numerów wszystkich atrybutów. Z kolei zbiór numerów wszystkich, bezpośrednich lub pośrednich, następników węzła $a_i$ oznaczany będzie przez $S_i$:

$$S_i = \{j\in N \;\vert\; a_i\dashrightarrow a_j\}$$ (4)

Oczywiście $S_i\cap U_i=\emptyset$ dla dowolnego węzła $a_i$, gdyż z założenia sieć bayesowska jest grafem acyklicznym. Stąd natychmiast wynika, że $U_i\subseteq N-S_i$.

Warunkowa niezależność węzłów

Wprowadzona relacja następstwa jest ważna przede wszystkim dlatego, że umożliwia zdefiniowanie w ścisły, sformalizowany sposób semantyki sieci bayesowskiej, czyli intepretację występujących w niej krawędzi. Otóż sieć taką interpretuje się jako stwierdzenie warunkowej niezależności każdego węzła od wszystkich węzłów nie będących jego następnikami, przy danych wartościach jego bezpośrednich poprzedników.

Korzystając z oznaczeń $U_i$ i $S_i$ dla węzła $a_i$ oraz uwzględniając, że $U_i\subseteq N-S_i$, możemy warunek ten zapisać następująco:

$$\begin{split}&\mathrm{Pr}_{x\in\Omega} \Big(a_i(x)=v_i\,\vert... ...v_i\,\big\vert\,\bigwedge_{j\in U_i}a_j(x)=v_j\Big) \end{split}$$ (5)

dla wszystkich $i=1,2,\dots,n$, $v_i\in A_i$, $v_j\in A_j$. Mniej formalnie, lecz krócej możemy przedstawić to w postaci:

$$\mathrm{Pr}(a_i\,\vert\,N-\{i\}-S_i) = \mathrm{Pr}(a_i\,\vert\,U_i)$$ (6)

Zwróćmy uwagę, że sieć bayesowska w żaden sposób nie wpływa na występowanie między atrybutami zależności lub ich brak -- należy ją traktować jako wyraz przyjętych na ten temat założeń, które mogą być spełnione lub nie, zupełnie tak samo jak założenie o niezależności naiwnego klasyfikatora bayesowskiego. Będą nas tu interesować sieci, dla których założenia te są spełnione. Wówczas struktura sieci poprawnie reprezentuje zależności występujące w rozważanej dziedzinie. Sieć taką nazwiemy siecią o poprawnej strukturze.

Łączny rozkład prawdopodobieństwa

O użyteczności sieci bayesowskich o poprawnej strukturze decyduje możliwość pośredniego reprezentowania za ich pomocą w oszczędny sposób łącznego rozkładu prawdopodobieństwa dla wszystkich atrybutów. Rozkład ten to zbiór prawdopodobieństw postaci:

$$\mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i=1}^n a_i(x)=v_i\Big)$$ (7)

dla wszystkich atrybutów $a_i$ oraz ich wszystkich wartości $v_i\in A_i$, $i=1,2,\dots,n$. Łatwo się przekonać, że znajomość takiego rozkładu umożliwia przeprowadzanie wnioskowania probabilistycznego o wartościach dowolnie wybranych atrybutów przy danych wartościach innych atrybutów. Załóżmy bowiem, że $N_o(x_q)$ oznacza numery atrybutów o znanych wartościach i $N_h(x_q)=N-N_o(x_q)$ numery atrybutów, których wartości nie są znane dla pewnego przykładu $x_q\in X$, którego dotyczy zapytanie. Nazwiemy je w tym kontekście odpowiednio atrybutami obserwowalnymi i ukrytymi. Wówczas oczywiście interesuje nas rozkład prawdopodobieństwa wartości atrybutów o numerach ze zbioru $N_h(x_q)$ przy danych wartościach atrybutów o numerach ze zbioru $N_o(x_q)$. Aby go wyznaczyć, wystarczy skorzystać w odpowiedni sposób z reguły iloczynu:

$$\begin{split}&\mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i\in N_... ...mega}\Big(\bigwedge_{i\in N_o(x_q)}a_i(x)=v_i\Big)} \end{split}$$ (8)

dla wszystkich możliwych wartości $v_i\in A_i$, jeśli $i\in N_h(x_q)$, oraz dla ustalonych, znanych wartości $v_i=a_i(x_q)$, jeśli $i\in N_o(x_q)$. Mianownik powyższego ułamka można wyznaczyć sumując prawdopodobieństwa

$$\mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i\in N_o(x_q)}a_i(x)=v_i\land \bigwedge_{i\in N_h(x_q)}a_i(x)=v_i\Big)$$ (9)

dla wszystkich możliwych kombinacji wartości atrybutów o numerach ze zbioru $N_h(x_q)$. Jeśli zatem rzeczywiście za pomocą sieci bayesowskiej można reprezentować łączny rozkład prawdopodobieństwa atrybutów, to można również, przynajmniej teoretycznie, wykorzystać ją do wnioskowania probabilistycznego w celu uzyskania odpowiedzi na dowolne zapytanie dotyczące dziedziny.

W istocie można udowodnić w prosty sposób, że jeśli sieć bayesowska dla dziedziny $X$, na której jest określony rozkład prawdopodobieństwa $\Omega$ i atrybuty $a_i:X\mapsto A_i$, $i=1,2,\dots,n$, ma poprawną strukturę, to

$$\begin{split}&\mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i=1}^n ... ..._i \,\big\vert\,\bigwedge_{j\in U_i}a_j(x)=v_j\Big) \end{split}$$ (10)

dla wszystkich wartości $v_i\in A_i$, $i=1,2,\dots,n$. Wynika z tego, że do reprezentowania za pomocą sieci bayesowskiej łącznego rozkładu prawdopodobieństwa wystarczy znajomość dla każdego węzła $a_i$ warunkowych prawdopodobieństw jego wartości przy danych wartościach jego bezpośrednich poprzedników:

$$\mathrm{Pr}_{x\in\Omega}\Big(a_i(x)=v_i \,\big\vert\,\bigwedge_{j\in U_i}a_j(x)=v_j\Big)$$ (11)

W związku z tym przyjmuje się, że odpowiednie tablice prawdopodobieństw warunkowych są przechowywane w każdym węźle sieci. Liczba prawdopodobieństw, jakie należy przechowywać w całej sieci, wynosi

$$\begin{split}\sum_{i=1}^n\vert A_i\vert\cdot\prod_{j\in U_i}\... ...ots,n}\vert U_i\vert} = {}\\ ={}& nv^{u+1}\text{,} \end{split}$$ (12)

przy czym:

$$v ={} \max_{i=1,\dots,n}\vert A_i\vert$$ (13)

$$u ={} \max_{i=1,\dots,n}\vert U_i\vert$$ (14)

Bezpośrednie reprezentowanie łącznego rozkładu prawdopodobieństwa bez używania sieci bayesowskiej oznaczałoby przechowywanie w pamięci liczby prawdopodobieństw równej

$$\prod_{i=1}^n\vert A_i\vert\leq v^n$$ (15)

Oszczędność związana z użyciem sieci bayesowskiej może być więc znaczna, jeśli $u\ll n$. Przykładowo dla $n=10$, $v=3$ i $u=3$ otrzymujemy $10\cdot 3^4=810$ zamiast $3^{10}=59049$ prawdopodobieństw.

Wnioskowanie w sieciach bayesowskich

Wiemy, że sieć bayesowska reprezentuje w skompresowany sposób łączny rozkład prawdopodobieństwa atrybutów i że taki łączny rozkład wystarcza do przeprowadzenia dowolnego rodzaju wnioskowania na temat wartości atrybutów. Odpowiedź na dowolne zapytanie można zatem uzyskać, wyznaczając na podstawie sieci łączny rozkład prawdopodobieństwa i wykorzystując go do odpowiednich obliczeń. Niestety, takie bezpośrednie podejście oznacza rezygnację z jednej z najważniejszych korzyści, jaką daje reprezentacja łącznego rozkładu za pomocą sieci, polegającej na jej oszczędności. Oczywiście sieci bayesowskie dają także inne korzyści, w szczególności czytelną i intuicyjnie zrozumiałą graficzną reprezentację wiedzy o zachodzących w dziedzinie bezpośrednich zależnościach przyczynowych, lecz względy efektywnościowe uniemożliwiają bezpośrednie posługiwanie się łącznym rozkładem w praktyce z wyjątkiem bardzo niewielkiej liczby atrybutów. Są więc potrzebne inne algorytmy wnioskowania za pomocą sieci bayesowskich.

Niestety, w ogólnym przypadku problem wnioskowania w dowolnych sieciach bayesowskich jest NP-trudny. Problem ten staje się prostszy dla szczególnego rodzaju sieci, nazywanych sieciami z pojedynczymi połączeniami. W takich sieciach dowolne dwa węzły są połączone co najwyżej jedną ścieżką, złożoną z dowolnie skierowanych krawędzi. Dla takich sieci znane są efektywne algorytmy wnioskowania. Nie będą one tu przedstawiane ze względu na matematyczną złożoność ich wyprowadzenia. Dla dowolnych sieci mogą być stosowane algorytmy przybliżone, oparte na podejściu Monte-Carlo, i na takich się tu skupimy.

Logiczne próbkowanie

Podstawowa koncepcja polega na tym, aby posługując się siecią bayesowską wygenerować w sposób losowy, zgodnie z przechowywanymi w jej węzłach tablicami prawdopodobieństw warunkowych, pewną liczbę wektorów wartości atrybutów (,,sztucznych'' przykładów), a następnie poszukiwany rozkład prawdopodobieństwa oszacować w zwykły sposób na podstawie tak uzyskanej losowej próby danych, wyznaczając względną częstość, z jaką wystąpiły interesujące nas wartości atrybutów. Generowanie każdego wektora danych należałoby rozpocząć od węzłów, które nie mają poprzedników, a więc dla których tablice prawdopodobieństw zawierają w istocie rozkłady bezwarunkowe. Na ich podstawie można wylosować wartości dla tych węzłów. W kolejnych krokach należy dokonywać losowania dla tych węzłów, których bezpośrednie poprzedniki mają już wcześniej wylosowaną wartość, tak aby można się było posłużyć odpowiednimi rozkładami warunkwymi. Metoda ta nazywana jest logicznym próbkowaniem

Załóżmy dla większej konkretności, że należy oszacować rozkład prawdopodobieństwa

$$\mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i\in N_h(x_q)}a_i(x)=v_i\,\big\vert\, \bigwedge_{i\in N_o(x_q)}a_i(x)=v_i\Big)$$ (16)

dla danych wartości $v_i=a_i(x_q)$ dla $i\in N_o(x_q)$. Jeśli za pomocą sieci bayesowskiej został wygenerowany pewien zbiór danych $D$, to prawdopodobieństwo to może być oszacowane przez ułamek:

$$\frac{\Big\vert\bigcap_{i\in N_h(x_q)\cup N_o(x_q)}D_{a_iv_i}\Big\vert} {\Big\vert\bigcap_{i\in N_o(x_q)}D_{a_iv_i}\Big\vert}.$$ (17)

Traktujemy tu zbiór $D$ tak jakby był zbiorem ,,sztucznych'' przykładów z dziedziny i stosujemy w związku z tym naszą standardową notację do oznaczenia jego podzbiorów wyznaczonych przez określone wartości poszczególnych atrybutów.

Sposób generowania zbioru $D$, na podstawie którego powyższe oszacowanie jest wyznaczane, podaje algorytm poniższy algorytm.

Pierwszym argumentem przedstawionej funkcji jest przykład $x_q\in X$ reprezentujący zapytanie, dla którego należy wyznaczyć rozkład prawdopodobieństwa nieznanych wartości atrybutów o numerach ze zbioru $N_h(x_q)$ przy znanych wartościach atrybutów o numerach ze zbioru $N_o(x_q)$. Główna pętla algorytmu powinna być wykonywana tak długo, dopóki zbiór $D$ nie osiągnie dostatecznie dużego rozmiaru.

Oczywiście w praktycznej implementacji nie ma potrzeby przechowywać zbioru $D$, wystarczy tylko na bieżąco po wygenerowaniu każdego przykładu zwiększać odpowiednie liczniki używane do szacowania prawdopodobieństw. Niestety, im więcej jest obserwowalnych atrybutów, których numery zawiera zbiór $N_o$, tym bardziej znikomym ułamkiem ogólnej liczby wygenerowanych przykładów będzie liczba występująca w mianowniku podanego wyżej ułamka i w celu osiągnięcia wiarygodnych oszacowań tą metodą wymagany rozmiar zbioru $D$ może być rzeczywiście bardzo duży.

Ważone próbkowanie

Trudności związanej z naszkicowaną wyżej metodą wnioskowania pozwala uniknąć jej prosta modyfikacja, nazywana ważonym próbkowaniem. W tym podejściu generuje się próbę danych $D$ zawierającą wyłącznie przykłady, dla których obserwowalne atrybuty mają określone zadane wartości. Wartości tych atrybutów nie są losowane, jak wszystkich pozostałych, lecz odpowiednio ustalane. Uwzględnia się jednak ich prawdopodobieństwa przypisując tak wygenerowanemu przykładowi wagę, z jaką następnie jest wykorzystywany przy szacowaniu. Jeśli przez $w_x$ oznaczymy wagę przypisaną przykładowi $x\in D$, to zmodyfikowane oszacowanie przybiera postać:

$$\frac{\sum_{x\in\bigcap_{i\in N_h\cup N_o}D_{a_iv_i}} w_x} {\sum_{x\in\bigcap_{i\in N_o}D_{a_iv_i}} w_x},$$ (18)

przy czym tym razem sposób generowania zbioru $D$ zapewnia, że

$$\bigcap_{i\in N_o}D_{a_iv_i} = D,$$ (19)

co pozwala poprzednie równanie uprościć do postaci:

$$\frac{\sum_{x\in\bigcap_{i\in N_h}D_{a_iv_i}} w_x} {\sum_{x\in D} w_x}.$$ (20)

Szczegóły algorytmu ważonego próbkowania przedstawione są poniżej.

Indukcja sieci bayesowskich

Mimo że w sporej części zwłaszcza wczesnych badań nad sieciami bayesowskimi zakładano, że w praktyce takie sieci mogą być projektowane przez ekspertów w dziedzinie, możliwość automatyzacji ich konstruowania na podstawie danych trenujących znacznie zwiększa szansę na ich udane zastosowania. Zatem przestrzeń możliwych sieci bayesowskich dla danej dziedziny potraktujemy jako przestrzeń hipotez, z której należy wybrać sieć najlepiej odpowiadającą danym trenującym. Dochodzimy w ten sposób do sformułowania zadania automatycznego konstruowania sieci bayesowskich jako szczególnej odmiany zadania indukcyjnego uczenia się. W istocie można sformułować różne wersje zadania uczenia się sieci bayesowskich, różniące się przyjmowanymi założeniami i trudnością.

Zadania uczenia się sieci bayesowskich

Są dwa zasadnicze kryteria różnicowania wersji zadania uczenia się sieci bayesowskich: znajomość struktury sieci lub jej brak oraz pełna lub częściowa obserwowalność atrybutów w danych trenujących. Cztery możliwe kombinacje tych kryteriów prowadzą do czterech wariantów zadania indukcji sieci bayesowskich.

Znana struktura i pełna obserwowalność.

To wariant najprostszy, w którym zakłada się, że została określona poprawna struktura sieci bayesowskiej, w postaci krawędzi spełniających podane wcześniej warunki. Struktura ta stanowi wiedzę wrodzoną ucznia. Dostępny jest także zbiór trenujący $T\subseteq X$, przy czym dla przykładów z tego zbioru znane są wartości wszystkich atrybutów. Przy takich założeniach oszacowanie prawdopodobieństw dla węzłów sieci jest trywialne i sprowadza się do policzenia przykładów trenujących, dla których wartości atrybutów spełniają odpowiednie warunki. W najprostszym przypadku oszacujemy element tablicy prawdopodobieństw warunkowych dla węzła $a_i$ jako następujący ułamek:

$$\mathrm{Pr}_{x\in\Omega} \Big(a_i(x)=v_i\,\big\vert\,\bigwedge_{j... ...{j\in U_i}T_{a_jv_j}\Big\vert} {\Big\vert\bigcap_{j\in U_i}T_{a_jv_j}\Big\vert}$$ (21)

W bardziej wyrafinowanym podejściu można użyć $m$-szacowania. Niestety, z taką prostą wersją zadania uczenia się niezbyt często można się spotkać w praktyce, gdyż najczęściej potrzeba stosowania sieci bayesowskich występuje dla dziedzin z częściową obserwowalnością, również jeśli chodzi o przykłady trenujące.

Nieznana struktura i pełna obserwowalność.

W tym przypadku jest również dostępny zbiór trenujący $T$ ze znanymi wartościami wszystkich atrybutów, lecz struktura sieci nie jest znana i musi być określona przez ucznia. W związku z tym należy przeszukać w pewien sposób przestrzeń możliwych struktur w poszukiwaniu takiej, która będzie najbardziej zgodna z danymi trenującymi. Dla każdej rozważanej struktury można oszacować odpowiednie tablice prawdopodobieństw warunkowych w podany wyżej prosty sposób i dla tak uzyskanej sieci-hipotezy $h$ obliczyć prawdopodobieństwo $\mathrm{Pr}(T\,\vert\,h)$ następująco:

$$\prod_{x_*\in T} \mathrm{Pr}_{x\in\Omega}\Big(\bigwedge_{i\in N}a_i(x)=a_i(x_*)\Big)$$ (22)

Preferowane byłyby hipotezy o największych wartościach tego prawdopodobieństwa. Gdyby możliwe było w sensowny sposób przypisanie również prawdopodobieństw a priori poszczególnym sieciom, można byłoby oceniać sieci według maksymalnego prawdopodbieństwa a posteriori $\mathrm{Pr}(T\,\vert\,h)$ określanego w zwykły sposób za pomocą wzoru Bayesa. Wybraną probabilistyczną funkcję oceny hipotez w celu uzyskania pełnego algorytmu należy połączyć z pewną heurystyczną strategią przeszukiwania przestrzeni możliwych struktur, gdyż wyczerpujący przegląd wszystkich możliwych dla danego zestawu atrybutów struktur jest z oczywistych względów niemożliwy.

Znana struktura i częściowa obserwowalność.

Ten wariant ponownie zakłada znajomość poprawnej struktury sieci, lecz niepełną obserwowalność atrybutów dla przykładów trenujących. Jest to zadanie bardziej interesujące z praktycznego punktu widzenia niż poprzednie, gdyż o ile dość często jest dostępna wiedza o dziedzinie wystarczająca do określenia struktury, o tyle pełna obserwowalność jest spotykana raczej rzadko. Znane są skuteczne algorytmy wyznaczania tablic prawdopodobieństw warunkowych dla sieci o znanej strukturze na podstawie zbioru trenującego $T$ z częściową obserwowalnością i jeden z nich, polegający na modyfikowaniu wartości przechowywanych w tych tablicach w kierunku rosnącego gradientu prawdopodobieństwa $\mathrm{Pr}(T\,\vert\,h)$, zostanie dalej omówiony.

Nieznana struktura i częściowa obserwowalność.

Jest to z oczywistych względów najtrudniejszy wariant zadania uczenia się sieci bayesowskich. Przy częściowej obserwowalności danych znalezienie poprawnej struktury w sposób analogiczny do tego, jaki był proponowany dla przypadku pełnej obserwowalności, okazuje się trudne do realizacji. Poszukiwanie skutecznych i ogólnych algorytmów dla tego problemu jest przedmiotem aktualnych prac badawczych.

Gradientowe uczenie się prawdopodobieństw

Rozważmy problem wyznaczenia tablic prawdopodobieństw warunkowych dla sieci bayesowskiej o ustalonej poprawnej strukturze na podstawie zbioru trenującego $T\subseteq X$, przy czym dla wszystkich lub niektórych przykładów część atrybutów może nie być obserwowalna. Za cel uczenia się przyjmiemy znalezienie hipotezy $h$, która jest w maksymalnym stopniu zgodna z danymi trenującymi, czyli maksymalizuje prawdopodobieństwo $\mathrm{Pr}(T\,\vert\,h)$. Hipoteza jest w tym przypadku w pełni określana przez tablice prawdopodobieństw warunkowych, które docelowo mają zawierać jak najlepsze przybliżenie prawdziwych prawdopodobieństw warunkowych wartości atrybutów. Wartość takiego prawdopodobieństwa dla hipotezy $h$ zapiszemy jako

$$\mathrm{Pr}^h_{x\in\Omega} \Big(a_i(x)=v_i\,\big\vert\,\bigwedge_{j\in U_i}a_j(x)=v_j\Big)$$ (23)

czyli dodając $h$ w górnym indeksie przy symbolu prawdopodobieństwa.

Jedną z metod (lokalnej) optymalizacji funkcji jest modyfikowanie jej argumentów w kierunku wyznaczonym przez spadek, jeśli chodzi o minimalizację, albo wzrost, jeśli chodzi o maksymalizację, jej gradientu. Popularne algorytmy uczenia się dla wielowarstwowych sieci neuronowych są oparte na metodach spadku gradientu. W naszym przypadku interesować nas będzie wzrost gradientu prawdopodobieństwa $\mathrm{Pr}(T\,\vert\,h)$ względem argumentów, jakie stanowią prawdopodobieństwa warunkowe dla węzłów sieci. Weźmy pod uwagę jedno z tych prawopodobieństw, dla pewnego węzła $a_i$ i jego wartości $v_i\in A_i$, przy pewnych ustalonych wartościach atrybutów $a_j$ dla $j\in U_i$, tak jak jest to zapisane w powyższym równaniu, i oznaczmy je dla zaoszczędzenia miejsca przez $w_i$. Okazuje się, że ze względów technicznych najwygodniej jest wyznaczać gradient logarytmu prawdopodobieństwa $\mathrm{Pr}(T\,\vert\,h)$, które oznaczymy przez $\mathrm{Pr}^h(T)$, względem prawdopodobieństw $w_i$. Zajmiemy się zatem pochodną cząstkową $\frac{\partial\ln\mathrm{Pr}^h(T)}{\partial w_i}$, z zamiarem zastosowania do modyfikacji $w_i$ reguły wzrostu gradientu w następującej postaci:

$$w_i := w_i + \beta\frac{\partial\ln\mathrm{Pr}^h(T)}{\partial w_i}$$ (24)

Takiej modyfikacji towarzyszyć powinna odpowiednia normalizacja wag w poszczególnych węzłach, zapewniająca sumowanie się odpowiednich prawdopodobieństw poszczególnych wartości atrybutu do $1$.

Pozostaje przekształcić pochodną cząstkową do postaci, w której będzie możliwe jej bezpośrednie obliczenie. Przedstawiając $\mathrm{Pr}^h(T)$ jako iloczyn prawdopodobieństw dla poszczególnych przykładów trenujących i różniczkując logarytm naturalny otrzymujemy:

$$\begin{split}\frac{\partial\ln\mathrm{Pr}^h(T)}{\partial w_i}... ...c{\partial\mathrm{Pr}^h(x_*)}{\partial w_i}\text{.} \end{split}$$

Występujące w powyższych wzorach prawdopodobieństwo $\mathrm{Pr}^h(x_*)$ jest dla przykładu $x_*\in T$ notacyjnym skrótem następującego prawdopodobieństwa:

$$\mathrm{Pr}^h_{x\in\Omega} \Big(\bigwedge_{j\in N_o(x_*)}a_j(x)=a_j(x_*)\Big)$$ (25)

przy czym $N_o(x_*)$ oznacza zbiór numerów obserwowalnych atrybutów dla przykładu $x_*$, czyli atrybutów, których wartości są dla tego przykładu znane. Po dalszych przekształceniach można dojść do równości:

$$\begin{split}\frac{\partial\ln\mathrm{Pr}^h(T)}{\partial w_i}... ...igwedge_{j\in N_o(x_*)}a_j(x)=a_j(x_*)\Big)\text{.} \end{split}$$ (26)

Występujące w uzyskanym wyrażeniu prawdopodobieństwo jest takiej samej postaci jak prawdopodobieństwa wykorzystywane przy wnioskowaniu w sieciach bayesowskich. Jest to prawdopodobieństwo warunkowe wartości pewnych atrybutów przy danych wartościach innych atrybutów. Jego wyznaczenie jest trywialne dla przykładów w pełni obserwowalnych, kiedy $N_o(x_*)=\{1,2,\dots,n\}$, lecz w ogólnym przypadku musi być wyznaczone w taki sam sposób, w jaki odpowiada się na zapytania za pomocą sieci bayesowskich. Często systemy uczące się sieci bayesowskich łączą więc wnioskowanie i gradientową modyfikację wag.

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdział 5.4).
2. Mitchell, T. M. Machine Learning. McGraw-Hill, 1995. (Podrozdział 6.11).
3. Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
4. Russell, S., Binder, J., Koller, D., Kanazawa, K. Local learning in probabilistic networks with hidden variables. Proceedings of the 14th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, 1995.

About this document ...

Metody odkrywania wiedzy: wykład 12
Sieci bayesowskie

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-w12.tex

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