Uczenie maszynowe i sztuczne sieci neuronowe/Wykład 7

Wstęp: generatywne algorytmy uczące

Dotychczas mówiliśmy tylko o algorytmach uczących bazujących na modelowaniu rozkładów warunkowych zmiennych zależnych [math]y[/math] przy zadanym [math]x[/math] i sparametryzowanych przez [math]\theta [/math]: [math]p(y|x;\theta )[/math], np.: regresja liniowa, logistyczna czy softmax.

Na podstawie przykładów z ciągu uczącego estymowana jest pewna granica między dwoma obszarami przestrzeni wejść. Decyzja co do klasy, którą reprezentuje nowy przypadek zależy tylko od tego, po której stronie granicy znajduje się ten przypadek.

W tym wykładzie zajmiemy się odmiennym podejściem. Na podstawie ciągu uczącego stworzymy osobne modele tego, jakim rozkładom podlegają cechy w poszczególnych klasach. Po otrzymaniu nowego przypadku patrzymy, do której klasy jest on najbardziej podobny.

Algorytmy, które estymują wprost rozkłady [math](y|x)[/math] czy też mapowania z [math]X \rightarrow \lbrace 0,1\rbrace [/math] nazywamy algorytmami dyskryminacyjnymi.

Dziś będziemy mówić o drugiej grupie algorytmów, tzw. algorytmach generatywnych. Modelują one:

• rozkłady cech w klasach: [math]p(x|y)[/math] oraz
• prawdopodobieństwa występowania klas: [math]p(y)[/math].

Rozważmy przykład. Chcemy odróżniać psy ([math]y=0[/math]) od kotów ([math]y=1[/math]). Umiemy określać cechy [math]x[/math] tych zwierząt. Budujemy rozkłady tych cech dla psów: [math]p(x|y=0)[/math] i dla kotów [math]p(x|y=1)[/math]. Modelujemy także prawdopodobieństwo tego, że losowo wybrane zwierzę będzie psem lub kotem (np. na podstawie liczebności obu gatunków): [math]p(y)[/math] (jest to tzw. prawdopodobieństwo apriori). Wtedy można na podstawie wzoru Bayesa obliczyć prawdopodobieństwo a posteriori:

[math] p(y|x) = \frac{p(x|y)p(y)}{p(x)} [/math]

Prawdopodobieństwo [math]p(x)[/math] można także wyrazić za pomocą prawdopodobieństwa [math]p(x|y)[/math] i [math]p(y)[/math] następująco: [math]p(x) = p(x|y=0)p(y=0) + p(x|y=1)p(y=1)[/math]. Warto jednak zauważyć, że w problemie klasyfikacji nie interesuje nas tak naprawdę [math]p(x)[/math]. Dlaczego? W klasyfikacji chcemy odpowiedzieć na pytanie, która z klas jest najbardziej prawdopodobna, czyli dla jakiego [math]y[/math] [math]p(y|x)[/math] jest maksymalne. Ponieważ mianownik wyrażenia (%i 1) , tzn. [math]p(x)[/math] nie zależy od [math]y[/math] więc jest jednakowy dla wszystkich klas. Można to zapisać tak:

[math] \arg \max _y p(y|x) = \arg \max _y \frac{p(x|y)p(y)}{p(x)} = \arg \max _y p(x|y) p(y)[/math]

Gaussowska analiza dyskryminacyjna

Pierwszym algorytmem generatywnym, z którym się zapoznamy będzie gaussowska analiza dyskryminacyjna (GAD). W tej analizie zakładamy, że dane niezależne, przy ustalonej klasie, pochodzą z wielowymiarowego rozkładu normalnego: [math]p(x|y) \sim N(\mu , \Sigma )[/math].

Dla przypomnienia funkcja gęstości prawdopodobieństwa dla [math]n[/math]-wymiarowego rozkładu o wektorze średnim [math]\mu \in \mathcal {R}^n[/math] i macierzy kowariancji [math]\Sigma [/math] dana jest przez:

[math] p(x;\mu ,\Sigma ) = \frac{1}{(2\pi )^{n/2} |\Sigma |^{1/2}} \exp \left( -\frac{1}{2}(x-\mu )^T \Sigma ^{-1}(x-\mu )\right)[/math]

gdzie: [math]|\Sigma |[/math] oznacza wyznacznik macierzy [math]\Sigma [/math]. Oczywiście [math]\mu [/math] równe jest wartości oczekiwanej zmiennych z tego rozkładu:

[math]E[X] = \int _x x p(x;\mu ,\Sigma )dx = \mu [/math]

Macierz kowariancji natomiast dana jest wzorem:

[math]\Sigma = E[(X-E[X])^T(X-E[X])][/math]

''': Kod do prezentacji dwuwymiarowych rozkładów normalnych:'''
# -*- coding: utf-8 -*-
import numpy as np
import pylab as py

#parametry rozkładu
# wektor średnich:
mu = [-2,-3]

# macierz kowariancji:
Sigma = np.array([[1, 0.5],
                  [0.5, 1]])
# generujemy dane: 
z1 = np.random.multivariate_normal(mu, Sigma, 10) #

# Rysujemy każdą realizację zmiennej jako punkt 
# z1 to macierz taka, że
# kolejne współrzędne zmiennej losowej są ułożone w kolejnych kolumnach
py.plot(z1[:,0],z1[:,1],'g.')
py.axis('equal')
py.show()

Dla pełnej specyfikacji modelu gaussowskiej analizy dyskryminacyjnej musimy założyć, że następujące zmienne mają wskazane rozkłady:

[math]\begin{matrix} y &\sim & \textrm {Bernoulli}(\phi ) \\ (x|y) &\sim & N(\mu _0,\Sigma ) \\ (x|y) &\sim & N(\mu _1,\Sigma ) \end{matrix}[/math]

zapisując to przy pomocy odpowiednich funkcji gęstości prawdopodobieństwa mamy:

[math]\begin{matrix} p(y) &=& \phi ^y (1-\phi )^{1-y} \\ p(x|y=0) &=& \frac{1}{(2\pi )^{n/2} |\Sigma |^{1/2}} \exp \left( -\frac{1}{2}(x-\mu _0)^T \Sigma ^{-1}(x-\mu _0)\right)\\ p(x|y=1) &=& \frac{1}{(2\pi )^{n/2} |\Sigma |^{1/2}} \exp \left( -\frac{1}{2}(x-\mu _1)^T \Sigma ^{-1}(x-\mu _1)\right) \end{matrix}[/math]

Oznacza to, że nasz model jest sparametryzowany przez [math]\phi [/math], [math]\mu _0[/math], [math]\mu _1[/math] i [math]\Sigma [/math]. (Zazwyczaj w modelu tym przyjmuje się, że średnie są różne ale macierz kowariancji jest dla obu klas taka sama.) Do wyznaczenie parametrów możemy zastosować metodę największej wiarygodności. Mając do dyspozycji zbiór uczący [math]\left\lbrace \left(x^{(j)},y^{(j)}\right) \right\rbrace _{j=1,\dots ,m}[/math] możemy zapisać funkcję log-wiarygodności:

[math]\begin{matrix} l(\phi ,\mu _0,\mu _1,\Sigma ) &=& \log \prod _{j=1}^m p \left( x^{(j)}, y^{(j)}; \phi ,\mu _0,\mu _1,\Sigma \right)\\ &=& \log \prod _{j=1}^m p \left( x^{(j)}|y^{(j)}; \mu _0,\mu _1,\Sigma \right)p(y^{(j)};\phi ) \end{matrix}[/math]

Wielkości występujące w tym wzorze dane są przez równania (%i 3). Porównajmy tą funkcję z analogiczną funkcją dla regresji logistycznej:

[math] l({\theta }) = \log \prod _{j=1}^{m}p(y^{(j)}|x^{(j)};\theta ) [/math]

Zwróćmy uwagę, że w tym wzorze, jak i we wszystkich wzorach na funkcję log-wiarygodności w algorytmach dyskryminacyjnych, występuje prawdopodobieństwo warunkowe klasy [math]y[/math] mając dany [math]x[/math]: [math]p(y|x)[/math], zaś w przypadku algorytmów generatywnych mamy prawdopodobieństwa łączne [math]p(x,y)[/math].

Maksymalizując tą funkcję (%i 4) względem parametrów otrzymujemy:

[math]\begin{matrix} \phi &=& \frac{\sum _{j=1}^m 1\lbrace y^{(j)}==1\rbrace }{m}\\ \mu _0 &=& \frac{\sum _{j=1}^m 1\lbrace y^{(j)} ==0\rbrace x^{(j)} }{\sum _{j=1}^{m} 1\lbrace y^{(j)}==0\rbrace }\\ \mu _{1} &=& \frac{\sum _{j=1}^{m}1\lbrace y^{(j)}==1\rbrace x^{(j)}}{\sum _{j=1}^{m} 1\lbrace y^{(j)}==1\rbrace }\\ \Sigma &=& \frac{1}{m}\sum _{j=1}^{m}(x^{(j)} - \mu _{y^{(j)}})^{T}(x^{(j)} - \mu _{y^{(j)}}) \end{matrix}[/math]

Kiedy już mamy dopasowane parametry modelu możemy robić przy jego pomocy klasyfikację (przewidywania) co od nowych przypadków. Przewidywaną klasą będzie, zgodnie z tym co mówiliśmy na początku wykładu:

[math] y_{przewidywane} = \arg \max _y p(y|x) = \arg \max _y \frac{p(x|y)p(y)}{p(x)} = \arg \max _y p(x|y) p(y) [/math]

Gaussowska analiza dyskryminacyjna a regresja logistyczna

(Przykładowy rysunek w 1-D, dwa gaussy , pierwszy [math]p(x|y=0)[/math] odpowiada klasie y = 0 , a drugi [math]p(x|y=1)[/math] klasie [math]y = 1[/math]. Zastanówmy się jakie jest prawdopodobieństwo [math]p(y=1|x) = \frac{p(x|y=1)p(y=1)}{p(x)}[/math] dla różnych wartości [math]x[/math] ? : Otrzymujemy sigmiodę!)

Istnieje ciekawa relacja między GAD a regresją logistyczną. Obie metody dają w efekcie pewną hiperpowierzchnię separującą obszary przestrzeni wejść na przynależną do klasy 0 bądź 1. Prawdopodobieństwo warunkowe klasy w modelu GAD można też wyrazić w postaci:

[math] p(y|x;\phi ,\Sigma ,\mu _{0},\mu _{1}) = \frac{1}{1+\exp(\theta ^{T}x)} [/math]

przy czym [math]\theta [/math] jest pewną funkcją parametrów modelu [math]\phi , \Sigma , \mu _{0},\mu _{1}[/math]. Co do formy uzyskujemy analogiczny wynik, chociaż w ogólności wynikające z tego proste (hiperpowierzchnie) decyzyjne będą różne dla GAD i regresji logistycznej, pomimo użycia tego samego zbioru uczącego. Który model jest lepszy ?

Możemy narysować taki schemat:

[math]\begin{matrix} (x|y) &\sim & Gaussowski\\ &\Downarrow & \textrm { ale } \Uparrow \textrm { nie zachodzi} \\ p(y|x) &\sim &f. logistyczna \end{matrix}[/math]

Dla wielu rozkładów [math](x|y)[/math] należących do rodziny wykładniczej otrzymujemy [math]p(y|x)[/math] w postaci logistycznej. Wynika stąd, że założenie gaussowskiej postaci [math](x|y)[/math] jest mocniejszym założeniem niż logistyczna postać [math]p(y|x)[/math].

Zatem odpowiedź, które podejście jest lepsze zależy od danych. Model GAD oparty jest o założenie, że rozkłady warunkowe danych [math]p(x|y)[/math] są wielowymiarowymi rozkładami normalnymi. Jeśli to założenie jest prawdziwe, to model GAD wykorzystuje więcej informacji, bo ”zna” cały rozkład danych - dane ze zbioru uczącego służą jedynie do estymacji parametrów tego rozkładu. Z drugiej strony regresja logistyczna robi znacznie słabsze założenia co do danych w związku z czym jest bardziej odporna na odstępstwa rozkładów danych wejściowych od założeń.

Naiwny Klasyfikator Bayesa

Klasyfikator GDA działał na danych ciągłych. Jak można zbudować kalsyfikator generatywny dla danych dyskretnych? Jako przykład omówimy naiwny klasyfikator Bayesa. Klasyfikator ten zaprezentujemy na przykładzie filtru antyspamowego. Załóżmy, że jako zbiór uczący mamy kolekcję listów oznaczonych jako spam albo nie-spam Najpierw musimy się zastanowić jak można reprezentować listy? Jednym z popularnych podejść jest metoda słownikowa. Przeglądamy duży zestaw listów, sporządzamy listę słów, które wystąpiły w tych listach, porządkujemy alfabetycznie i otrzymujemy słownik.

Mając taki słownik możemy każdy list zakodować jako wektor kolumnowy złożony z zer i jedynek. Jedynka na i-tej pozycji oznacza, że w liście wystąpiło i-te słowo z naszego słownika. Przykładowy list mógłby wyglądać tak:

[math] x = \left[ \begin{array}{c} 0 \\ 0 \\ \vdots \\ 1 \\ \vdots \\ 1 \\ \vdots \\ 1 \\ \vdots \end{array} \right] \begin{array}{l} aby \\ ale \\ \vdots \\ pozdrawiam \\ \vdots \\ witaj \\ \vdots \\ widzialem \\ \vdots \end{array} [/math]

Każdy [math]x_{i}[/math] ([math]i[/math]-ta współrzędna wektora [math]x[/math]) może przyjąć wartość 1 albo 0 w zależności od tego czy [math]i[/math]-te słowo ze słownika wystąpiło w liście czy też nie. Zauważmy, że kodowanie to pomija informację o częstości danego słowa w liście. Widać, że rozmiar [math]x[/math] może być bardzo duży. Jest on równy rozmiarowi słownika. Mając wybrany sposób reprezentacji listów możemy przystąpić do budowania modelu dyskryminacyjnego. Czyli potrzebjemy wyznaczyć [math]p(x|y)[/math]. Jeśli rozmiar naszego słownika to 5000 słów to [math]x[/math] są 5000-wymiarowymi wektorami z wartościami 0 i 1. Gdzybyśmy chcieli zamodelować to rozkładem wielorakim to mielibyśmy [math]2^{5000}-1[/math] możliwych stanów do zareprezentowania i tyle potrzebowalibyśmy oszacować parametrów. To zdecydowanie za dużo.

Aby sobie jakoś z tym problemem poradzić posłużymy się tzw. naiwnym założeniem Bayesa. Założymy mianowicie, że słowa są warunkowo niezależne. W praktyce oznacza to tyle, że jeśli wiem, że dany list jest spamem, to dodatkowa wiedza, że występuje w nim słowo 'wygrałeś' ([math]x_{3000}[/math]) nie wpływa na moje oszacowanie prawdopodobieństwa, że w tym liście występuje słowo 'kliknij' ([math]x_{1234}[/math]). Formalnie oznacza to, że [math]p(x_{1234}|y) = p(x_{1234}|y,x_{3000})[/math]. Uwaga: Nie jest to to samo co założenie, że słowa te są od siebie niezależne. Niezależność słów zapisalibyśmy jako [math]p(x_{1234}) = p(x_{1234}|x_{3000})[/math].

Dzięki założeniu warunkowej niezależności możemy zapisać:

[math]\begin{matrix} p(x_{1},\dots ,x_{5000}|y) &=& p(x_{1}|y)p(x_{2}|y,x_{1})p(x_{3}|y,x_{1},x_{2}),\dots ,p(x_{5000}|y,x_{1},\dots ,x_{4999})\\ &=& p(x_{1}|y)p(x_{2}|y)p(x_{3}|y),\dots ,p(x_{5000}|y) \\ &=& \prod _{i=1}^{n}p(x_{i}|y) \end{matrix}[/math]

Ostatecznie nasz model jest sparametryzowany przez:

[math]\begin{matrix} \phi _{i|y=0} &=& p(x_{i}=1|y=0) \\ \phi _{i|y=1} &=& p(x_{i}=1|y=1) \\ \phi _{y} &=& p(y=1) \end{matrix}[/math]

Mając dany zbiór uczący [math]\left\lbrace \left( x^{(j)},y^{(j)} \right)\right\rbrace _{j=1,\dots ,m}[/math] możemy wypisać funkcję wiarygodności:

[math] L(\phi _{y}, \phi _{i|y=0},\phi _{i|y=1}) = \prod _{j=1}^{m} p(x^{(j)},y^{(j)}) [/math]

Maksymalizując tą fuknkcję za względu na parametry [math]\phi _{y}, \phi _{i|y=0},\phi _{i|y=1}[/math] otrzymujemy:

[math]\begin{matrix} \phi _{i|y=0} &=& \frac{ \sum _{j=1}^m 1\lbrace x_i^{(j)} ==1 \wedge y^{(j)}==0 \rbrace }{\sum _{j=1}^{m} 1\lbrace y^{(j)}==0\rbrace } \\ \phi _{i|y=1} &=& \frac{ \sum _{j=1}^m 1\lbrace x_i^{(j)} ==1 \wedge y^{(j)}==1 \rbrace }{\sum _{j=1}^{m} 1\lbrace y^{(j)}==1\rbrace } \\ \phi _{y} &=& \frac{ \sum _{j=1}^m 1\lbrace y^{(j)}==1 \rbrace }{m } \end{matrix}[/math]

Teraz aby sklasyfikować nowy list z cechami [math]x[/math] obliczamy:

[math]\begin{matrix} p(y=1|x) &=& \frac{p(x|y=1)p(y=1)}{p(x)}\\ &=& \frac{\prod _{i=1}^{n} p(x_{i}|y=1)p(y=1)}{( \prod _{i=1}^{n}p(x_{i}|y=0))p(y=0)+(\prod _{i=1}^{n}p(x|y=1))p(y=1)} \end{matrix}[/math]

(aby obliczyć prawdopodobieństwo przynależności do klasy 0 możemy skorzystać z: [math]p(y=0|x) = 1-p(y=1|x)[/math]) i wybieram klasę do której przynależność jest bardziej prawdopodobna.

W tym przykładzie rozważaliśmy sytuację gdy prawdopodobieństwa warunkowe poszczególnych [math]x_{i}[/math] były modelowane rozkładem Bernoulliego. Widać, że gdyby [math]x_{i}[/math] mogło przyjmować [math]k[/math] dyskretnych wartości to należałoby modelować je za pomocą rozkładu wielorakiego.

Wygładzanie Laplace'a

Chociaż opisany przed chwilą model zazwyczaj działa dobrze, to jest z nim czasem w praktycznych zastosowaniach problem. Wyobraźmy sobie, że słownik zawiera słowo 'niezapominajka' ale, że zbiór uczący nie zawierał listu w którym słowo to by wystąpiło, załóżmy że ma ono indeks 2576 w naszym słowniku. Wówczas oszacowane parametry [math]\phi [/math] dla tego słowa to:

[math]\begin{matrix} \phi _{2576|y=0} &=& \frac{ \sum _{j=1}^m 1\lbrace x_{2576}^{(j)} ==1 \wedge y^{(j)}==0 \rbrace }{\sum _{j=1}^{m} 1\lbrace y^{(j)}==0\rbrace } = 0 \\ \phi _{2576|y=1} &=& \frac{ \sum _{j=1}^m 1\lbrace x_{2576}^{(j)} ==1 \wedge y^{(j)}==1 \rbrace }{\sum _{j=1}^{m} 1\lbrace y^{(j)}==1\rbrace } = 0 \end{matrix}[/math]

bo nigdy się nie zdarzyło aby słowo to wystąpiło w klasie spam i w klasie nie-spam.

Jeżeli teraz policzymy dla tego słowa prawdopodobieństwo klasy 1 to :

[math] p(y=1|x) = \frac{\prod _{i=1}^{n} p(x_{i}|y=1)p(y=1)}{( \prod _{i=1}^{n}p(x_{i}|y=0))p(y=0)+(\prod _{i=1}^{n}p(x_{i}|y=1))p(y=1)} =\frac{0}{0} [/math]

ponieważ w każdym z iloczynów [math]\prod _{i=1}^{n} p(x_{i}|y=1)[/math] występuje czynnik [math]p(x_{2576}|y)=0[/math]. Czyli nie da się określić prawdopodobieństwa przynależności listu [math]x[/math] do klasy spam albo nie-spam ze względu na jedno słowo, które nie występowało w zbiorze uczącym! W tym przykładzie można by oczywiście zaproponować inny sposób konstrukcji słownika aby do takiej sytuacji nie doszło.

Można też przyjrzeć się temu problemowi bardziej ogólnie. Problem ten bierze się ze sposobu szacowania parametrów [math]\phi _{i}[/math]. Rozważmy zagadnienie oszacowania średniej w rozkładzie wielorakim, w którym zmienna [math]z[/math] przyjmuje jedną z [math]\lbrace 1,\dots ,k\rbrace [/math] wartości i rozkład ten jest sparametryzowany przez [math]\phi _{i} = p(z=i)[/math]. Do dyspozycji mamy [math]m[/math] niezależnych obserwacji [math]\lbrace z^{(1)},\dots ,z^{(m)}\rbrace [/math]. Z metody największej wiarygodności otrzymujemy estymaty (stosunek liczby [math]z =i[/math] do liczby wszystkich obserwacji):

[math] \phi _{i} = \frac{\sum _{j=1}^{m} 1\lbrace z^{(j)}==i\rbrace }{m} [/math]

Jednak fakt, że w skończonym zbiorze obserwacji nie wystąpiła ani razu któraś z możliwych wartości [math]z[/math] nie powinien skutkować tym, że przypisujemy zerowe prawdopodobieństwo tej możliwości. Metodą powszechnie stosowaną na poprawę tej estymaty jest tzw. wygładzanie Laplacea. Modyfikuje ono estymatę otrzymaną metodą największej wiarygodności w następujący sposób:

[math] \phi _{i} = \frac{\sum _{j=1}^{m} 1\lbrace z^{(j)}==1\rbrace +1 }{m+k} [/math]

Łatwo zauważyć, że ten estymator też spełnia warunki narzucone przez interpretację probabilistyczną:

[math] \sum _{i=1}^{k} \phi _{i} =1 [/math]