Uczenie maszynowe i sztuczne sieci neuronowe/Wykład 10

powrót

Uczenie bez nadzoru

W tym wykładzie zajmiemy się problemem następującym. Czy można skonstruować algorytm, który uczy się czegoś na temat wektorów wejściowych nie mając określonych wartości wyjściowych? Jako inspirację biologiczną możemy sobie wyobrazić to jak kot, który jak wiadomo rodzi się ślepy, uczy się postrzegać obiekty.

Formalnie będziemy myśleć o algorytmach, które po prezentacji ciągu uczącego składającego się z samych wektorów wejściowych [math]\lbrace x^{(j)}\rbrace _{1=1,\dots ,m}[/math] "nauczą się" wyróżniać w tym zbiorze pewną strukturę. Będziemy mówić, że algorytm dokonał podziału zbioru uczącego na skupiska (klastry). W statystyce podejście takie nazywane jest analizą skupień. Może ona być przydatna zarówno ze względów poznawczych - kiedy próbujemy wydobyć jakąś wiedzę na temat zbioru uczącego (data mining), jak i w zastosowaniach utylitarnych, kiedy stosujemy analizę skupień np. w celu segmentacji obrazu lub klasyfikacji.

Reguła Hebba

Zaczniemy od omówienia metody inspirowanej hipotezą biologiczną:

"When an axon of cell A is near enough to excite cell B and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that A's efficiency, as one of the cells firing B, is increased." Koncepcja ta pochodzi od Kanadyjskiego psychologa Donalda Oldinga Hebba, stąd jej nazwa. Najprościej można ją ująć tak, że synapsa łącząca dwa neurony ulega wzmocnieniu jeśli neuron pre- i post synaptyczny są jednocześnie aktywne. Innymi słowy siłą napędową uczenia Hebbowskiego są korelacje aktywności neuronów pre- i post synaptycznych.

W kontekście sztucznej sieci neuronowej można ją wyrazić następująco: Niech [math]m[/math] - indeks neuronu, [math]x_{i}^{(j)}[/math] - [math]i[/math]-te wejście do tego neuronu pochodzące z [math]j[/math]-ego przykładu, [math]y_{m}^{(j)}[/math] wyjście wytworzone przez [math]m[/math]-ty neuron na [math]j[/math]-ty przykład. Wtedy hebbowska reguła zmiany wag jest następująca:

[math] \Delta w_{i}^{(m)(j)} = \eta x_{i}^{(j)}y_{m}^{(j)} [/math]

Dlaczego ta reguła działa?

Jeśli w chwili początkowej, któryś neuron miał zestaw wag zbliżony do prezentowanego sygnału to w następnych pokazach tego samego sygnału “reakcja” tego neuronu na ten sygnał będzie coraz silniejsza. Sieć tak uczona zaczyna klasyfikować sygnały.

Ograniczenia:

• przebieg uczenia zależy od wartości początkowych wag
• nie ma gwarancji, że jednej klasie wzorców będzie odpowiadał jeden neuron
• nie ma gwarancji, że wszystkie klasy wzorców będą miały oddzielne reprezentacje w postaci oddzielnych zbiorów aktywnych neuronów

Uczenie z rywalizacją: sieci Kohonena

Częściowe rozwiązanie wymienionych powyżej ograniczeń można uzyskać stosując tzw. uczenie z rywalizacją w sieciach liniowych Kohonena. Reguła zmiany wag jest w tym przypadku następująca:

[math] \Delta w_{i}^{(m^{*})(j)} = \eta (\tilde{x}_{i}^{(j)} - w_{i}^{(m^{*})(j)}) [/math]

• W danym kroku uczenia modyfikacjom podlegają wagi tylko jednego "zwycięskiego" neuronu [math]m^{*}[/math], tzn. tego który daje największe wyjście:

  [math]y_{m^{*}}^{(j)} = \max _{m} y_{m}^{(j)} [/math]

• wektor wejściowy jest znormalizowany (to symbolizuje [math]\tilde{x}[/math]). Dzięki temu mamy gwarancję, że zwycięski neuron to ten, którego wektor wag jest najbardziej podobny do wejścia.

Dzięki powyższym warunkom uzyskujemy następującą własność: jeśli w zbiorze uczącym występują jakieś skupiska to wektory wag są modyfikowane w kierunku wartości średnich w tych skupiskach.

Analiza skupień: [math]k[/math]-średnich

Jednym z podstawowych algorytmów stosowanych w analizie skupień jest analiza metodą [math]k[/math]-średnich (ang. [math]k[/math]-means). Podobnie jak w poprzedniej sekcji załóżmy, że mamy zbiór treningowy: [math]\lbrace x^{(j)}\rbrace _{j=1,\dots ,m}[/math]. Zakładamy, że występuje w nim [math]k[/math] skupisk (ta wiedza jest zewnętrzna względem algorytmu). Chcielibyśmy każdemu punktowi ze zbioru uczącego przyporządkować jakąś etykietkę [math]\lbrace {1}, \dots ,{k}\rbrace [/math], ale nie mamy wiedzy o jakimś "prawidłowym" podziale.

Algorytm [math]k[/math]-średnich:

1. W losowy sposób zainicjuj centra skupisk: [math]\mu _{1},\dots ,\mu _{k}[/math]. Centra są punktami w przestrzeni o tej samej wymiarowości co punkty zbioru uczącego, np. można wybrać w sposób losowy [math]k[/math] punktów spośród elementów zbioru uczącego.
2. Powtarzaj,aż zbiegniesz:
   • Dla każdego punktu [math]x^{(j)}[/math] ze zbioru uczącego przypisz etykietkę [math]c^{(j)}[/math] najbliższego centrum:

     [math]c^{j} = \arg \min _{i}||x^{(j)} - \mu _{i}||^{2}[/math]

   • Zauktualizuj położenia centrów każdego skupiska, tak aby były środkiem ciężkości punktów należących do danego skupiska:

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

Jako miarę jakości podziału można wprowadzić sumę kwadratów odległości punktów od centrów skupisk, do których zostały przypisane:

[math] J(c,\mu ) = \sum _{j=1}^{m} ||x^{(j)}-\mu _{c^{(j)}}||^{2} [/math]

W tym kontekście można na algorytm [math]k[/math]-średnich patrzeć jak na algorytm spadku osiowego, gdzie osiami są etykietki [math]c[/math] i centra [math]\mu [/math]. Widać, że dwa kroki wewnętrznej pętli to optymalizacja [math]c[/math] i [math]\mu [/math] na zmianę. Algorytm [math]k[/math]-średnich jest zbieżny w takim sensie, że po każdym kroku iteracji funkcja [math]J[/math] maleje, więc ostatecznie osiągnie jakieś minimum. Teoretycznie możliwe jest, że algorytm wpadnie w oscylacje pomiędzy dwoma podziałami, które maja dokładnie takie samo [math]J[/math], ale jest to bardzo mało prawdopodobne. Niestety optymalizacja [math]k[/math]-średnich nie jest optymalizacją wypukłą, ą co za tym idzie jest podatna na występowanie lokalnych minimów. Najprostszym środkiem zaradczym jest wielokrotne wystartowanie algorytmu z różnych losowych zestawów centrów i wybór takiej parametryzacji, która daje najmniejsze [math]J[/math].

Klasyfikacja:

Po znalezieniu optymalnych położeń centrów, mogą one być wykorzystane do klasyfikacji nowych przypadków. Wystarczy policzyć odległość rozważanego punktu od każdego z centrów i przypisanie mu klasy związanej z najbliższym centrum.

Gaussowski model mieszany

W tej sekcji rozważymy jak zamodelować rozkład gęstości prawdopodobieństwa, który nie ma jakiejś konkretnej postaci. Będziemy modelować ten rozkład jako sumę rozkładów gaussowskich. Taki rozkład może się nam przydać np. do wykrywania artefaktów. Załóżmy że mamy sygnały EEG, o których wiemy, że nie zawierają artefaktów. Możemy je scharakteryzować za pomocą pewnych wektorów cech (np. współczynniki Fourierowskie). Jeśli uda nam się opisać jakoś sensownie rozkład prawdopodobieństwa tych cech to można go potem użyć do testowania jakie jest prawdopodobieństwo, że czy nowy fragment sygnału również jest z tego rozkładu, tzn. jest wolny od artefaktów.

W bardziej zaawansowanych zastosowaniach można sobie wyobrazić rozszerzenie gaussowskiej analizy dyskryminacyjnej (model generatywny) na przypadki gdzie prawdopodobieństwa apriori opisywane są przez modele mieszane.

Sformułowanie problemu

Po tym wstępie przystąpmy do sformalizowania rozważań. Załóżmy, że jak zwykle mamy dany zbiór treningowy: [math]\lbrace x^{(j)}\rbrace _{j=1,\dots ,m}[/math]. Chcemy zamodelować te dane przy pomocy rozkładu prawdopodobieństwa [math]p(x^{(j)},z^{(j)}) = p(x^{(j)}|z^{(j)})p(z^{(j)})[/math]. Zmienna [math]z^{(j)}[/math] pochodzi z rozkładu wielorakiego parametryzowanego przez [math]\lbrace \phi _{i}\rbrace _{i = 1,\dots ,k}[/math] ([math]\phi _{i }= p(z^{(j)}=i)[/math], [math]\phi _{i}\gt 0, \sum _{i}\phi _{i}=1[/math]). O rozkładach warunkowych zakładamy, że są Gaussowskie: [math](x^{(j)}|z^{j}=i) \sim \mathcal {N}(\mu _{i},\Sigma _{i})[/math]. Innymi słowy: myślimy o zmiennych ze zbioru treningowego, że powstały w następujący sposób: najpierw z rozkładu wielorakiego została wylosowana zmienna [math]z^{(j)}[/math], wskazując na konkretny rozkład Gaussa [math]\mathcal {N}(\mu _{i},\Sigma _{i})[/math]. Następnie ze wskazanego rozkładu Gaussa została wylosowana zmienna [math]x^{(j)}[/math]. Zmienne losowe [math]z[/math] są w tym problemie zmiennymi ukrytymi, tzn. nie możemy ich obserwować.

Model jest zatem opisywany przez parametry [math]\phi ,\mu ,\Sigma [/math]. Możemy dla nich napisać funkcję log-wiarygodności:

[math]\begin{matrix} l (\phi ,\mu , \Sigma ) &=& \sum _{j=1}^{m} \log p(x^{(j)};\phi ,\mu \Sigma ) \\ &=& \sum _{j=1}^{m}\log \sum _{z^{(j)}=1}^{k}p(x^{(j)}|z^{(j)};\mu ,\Sigma )p(z^{(j)};\phi ) \end{matrix}[/math]

Zobaczmy, że gdybyśmy znali [math]z^{(j)}[/math] problem byłby prosty. Można by wówczas przepisać funkcję log-wiarygodności do postaci:

[math] l (\phi ,\mu , \Sigma ) = \sum _{j=1}^{m}\left( \log p(x^{(j)}|z^{(j)};\mu ,\Sigma ) + \log p(z^{(j)};\phi )\right) [/math]

Licząc pochodne cząstkowe po parametrach i kładąc je równe zero otrzymalibyśmy:

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

Niestety to, że nie znamy wartości [math]z^{(j)}[/math] powoduje, że funkcji (%i 1) nie da się zmaksymalizować w tak prosty sposób.

Algorytm expectation maximization (EM)

Rozwiązanie sformułowanego powyżej problemu można uzyskać w sposób iteracyjny. Na przemian trzeba wykonywać kroki [math]E[/math] i [math]M[/math]. Krok [math]E[/math] polega na "zgadnięciu" wartości [math]z^{(j)}[/math], a w kroku [math]M[/math] uaktualniane są parametry modelu przez maksymalizację funkcji log-wiarygodności (dla właśnie odgadniętych [math]z^{(j)}[/math]). Zatem algorytm wygląda następująco:

Powtarzaj, aż zbiegniesz {

krok [math]E[/math]

Dla każdego [math]i,j[/math] oblicz:

[math] w_{i}^{(j)} = p(z^{(j)}=i|x^{(j)}; \phi ,\mu ,\Sigma ) [/math]

Gdzie prawdopodobieństwa warunkowe [math]z[/math]:

[math] p(z^{(j)}=i|x^{(j)};\phi ,\mu ,\Sigma ) = \frac{p(x^{(j)}|z^{(j)}=i;\mu ,\Sigma ) p(z^{(j)}=i;\phi )}{\sum _{l=1}^{k} p(x^{(j)}|z^{(j)}=l; \mu ,\Sigma )p(z^{(j)}=l;\phi )} [/math]

tu poszczególne wyrażenia to:

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

  jest równa gęstści prawdopodobieństwa rozkładu Gaussa o parametrach [math]\mu _{i}[/math] i [math]\Sigma_{i}[/math] dla [math]x^{(j)}[/math]

• [math]p(z^{(j)}=i;\phi ) = \phi _{i}[/math]

krok [math]M[/math]

uaktualnij parametry:

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

[math] \mu _{i} = \frac{\sum _{j=1}^{m} w_{i}^{(j)} x^{(j)}}{\sum _{j=1}^{m} w_{i}^{(j)}} [/math]

[math] \Sigma _{i} = \frac{\sum _{j=1}^{m} w_{i}^{(j)} (x^{(j)}-\mu _{i})(x^{(j)}-\mu _{i})^{T} }{\sum _{j=1}^{m} w_{i}^{(j)}} [/math]

}

Algorytm EM jest podatny na lokalne minima, więc dobrze jest stosować go z kilkukrotnym losowym wyborem początkowych parametrów.