Kohonenova mapa - opakování Organizační dynamika: Jednovrstvá sít' yi yk yh Xi Xi Xn ► Mezi neurony je navíc zavedena topologická struktura (tj. neurony tvorí uzly neorientovaného grafu). ► V drtivé vetšine prípadu je tato struktura bud' jednorozmerná rada jednotek nebo dvojrozmerná mřížka. i Kohonenova mapa Aktivní dynamika: Pro vstup x e Rn a k = 1,..., h: Adaptivní dynamika: V adaptivním režimu využijeme topologickou strukturu. ► OznaCme d (c, k) délku nejkratší cesty z neuronu c do neuronu k v topologické struktuře. ► Pro neuron c a dané s e No definujeme okolí neuronu c velikosti s takto: Ns(c) = {k | d(c, k) < s} V kroku f po predložení vstupu xf adaptujeme každé wk takto: k e Ns (c) jinak kde c = arg min/=1.....h ||xř - w> ;|| a kde 0 e R a s e N0 jsou parametry, které se mohou v prUbehu učení menit. 2 Kohonenova mapa - adaptivní dynamika Obecnější formulace adaptivní dynamiky: + e(c, k) • (x - wk' í'1 = wk'-1) kde c = arg min/=1.....h X' - w(' 1) . Předchozí případ potom odpovídá e(c, k) = í8 k e Ns(c) v ' [0 jinak Obvykle se používá plynulejší přechod mezi nenulovými a nulovými hodnotami, např. e(c, k) = 8o • exp() kde 0o e R urCuje maximální míru zmeny vah a o e R je šířka (oba parametry se mohou v prubehu menit). 3 LVQ - klasifikace - opakování Přepodkládejme, že máme náhodně generované vzory tvaru (xt, dt) kde xt e Rn je vektor vlastností a dt e (Ci,..., Cq} určuje jednu z q tríd. Cílem je klasifikovat vstupy do tříd na základe znalosti vlastností, tj. každému xt chceme přiřadit třídu tak, abychom minimalizovali pravdepodobnost chyby. Pr.: Po pásu jede náhodne „naházené" ovoce dvou druhu: jablka a melouny. Námi sledovaná data budou (xt, dt) kde ► xt e R2, první vlastnost je hmotnost, druhá je průmer ► dt je bud' J nebo M v závislosti na tom, jestli je daný kus jablko nebo meloun Připouštíme možnost, že se najde jablko a meloun se stejnými mírami. Cílem je třídit ovoce na základe hmotnosti a prumeru. 4 LVQ - klasifikace - opakování Využijeme vektorovou kvantizaci (Kohonenovu mapu) takto: 1. Natrénujeme mapu na vektorech vlastností Xř kde f = 1,...,t. 2. Jednotlivé neurony oznaCíme třídami. Trídu vc neuronu c nalezneme takto: Pro každý neuron c a trídu Ci spoCítáme Četnost vzoru trídy Ci, které jsou reprezentovány neuronem c. Toto lze provést jedním průchodem pres vzory Neuronu c přiřadíme třídu s maximální cetností. 3. Doladíme síť pomocí algoritmu LVQ. Klasifikaci pomocí natrénované síte provádíme takto: Na vektor vlastností X aplikujeme natrénovanou sít v aktivním režimu. Práve jeden neuron, řekneme c, bude mít výstup 1. Potom vstup zařradíme do trřídy vc. 5 LVQ1 - opakování Postupně projdi tréninkové vzory. Pro vzor (xt, dt) urči nejbližší neuron c c = arg min \\xt - W/II /=1,...,h" 11 Potom uprav váhy neuronu c takto: Parametr a by měl být od počátku malý (cca 0.01 - 0.02) a postupně klesnout k 0. Hranice mezi třídami vytvořená pomocí LVQ1 je pomerne dobrou aproximací bayesovské rozhodovací hranice. dt = vc dt ŕ vc 6 Klasická aplikace - fonetický psací stroj Zdroj: The Self-Organizing Map. T. Kohonen, IEEE, 1990 Cílem je automaticky zapisovat diktovaný text (v originále bud' Finština nebo Japonština) Zvuk byl nejprve předzpracován: ► 5.3 kHz low-pass filter ► digitalizace (12-bit, 13.02-kHz sampling rate) ► spektrální rozklad (Fourierova transformace každých 9.83 ms) ► spektrum „zkombinováno" do 15 komponent od 200 Hz po 5 kHz -> 15 dimenzionální vstupy pro Kohonenovu mapu Byla také provedena normalizace na nulové strední hodnoty komponent a konstantní délku vektoru. 7 Klasická aplikace - fonetický psací stroj Vytvořena Kohonenova mapa 8 x 12 jednotek, hexagonální Trénována na toku 15 dim vektoru v jejich přirozeném pořadí (pouze samoorganizace) Poté prirazeny fonémy jednotlivým neuronUm, doladeno pomocí LVQ. 0©0©©0©0®000 ©©©©©©©©©©©© 8 Klasická aplikace - fonetický psací stroj Mapu lze vyžít k vizualizaci mluveného slova (zde Humpilla): Může být využito k rozpoznávání mluvených slov s použitím klasifikátoru natrénovaného na mnoha překladech. Table 2 Speech Recognition Experiments with Error Percentages for Independent Test Data Parametric Bayes kNN LVQ1 LVQ2 LVQ.i Test 1 Test 2 12.1 13.8 12.0 12.1 10.2 13.2 9.8 12.0 9 Oceánograf ická data Zdroj: Patterns of ocean current variability on the West Florida Shelf using the self-organizing map. Y. Liu a R. H. Weisberg, JOURNAL OF GEOPHYSICAL RESEARCH, 2005 Zkoumá se vývoj proudění vod v oceánu kolem pobřeží Floridy 84 83 82 Longitude (°W) 10 Oceánografická data ► 11 meřicích stanic, 3 hloubky (hladina, dno, mezi) ► data: 2D vektory rychlosti (a smeru) proudení ► mereno po hodinách, 25585 hodin Celkove tedy 25585 řádku 66 dimenzionálních položek. Kohonenova mapa: ► mřížka 3 x 4 ► okolí dána Gaussovou funkcí 0(c, k) = 0o • exp( ) se zmenšující se šírkou (navíc je tam lineárne se zmenšující rychlost uičení, kterou se násobí zmena polohy neuronu) 11 Oceánografická data ► křížky označují „vítězné" neurony (po hodinách) ► ovlivněno lokálními fluktuacemi ► pozorovatelný trend: ► v zimě neurony 1-6 (jiho-východ) ► v léte neurony 10-12 (severo-západ) 13 Oceánografická data Srovnání smeru vetru a proudení vody (znatelná korelace) ► vítr: smer cáry = smer vetru ; délka cáry = intenzita ► proudení vody v procentech úspešnosti skupin neuronu 14 Robotická ruka Zdroj: Neural Networks - A Systematic Introduction, R. Rojas, Springer, 1996 Cílem je rídit robotickou ruku s jedním kloubem na Čtvercové pracovní ploše: Pozice ruky je dána dvema úhly a a jS. 15 Robotická ruka - idea Topologie Kohonenovy mapy zde odpovídá pracovní ploše Váhy neuronu odpovídají příslušným úhlum a a jS. Adaptace: ► ruka je nastavena na náhodné místo na pracovní ploše, tj. ukazuje na vybraný neuron v topologické struktuřre ► váhy tohoto neuronu (a neuronu v jeho okolí) jsou potom adaptovány podle aktuálních úhlu ruky Ruka se tedy naucí mapovat souradnice na pracovní ploše (topologie) na úhlové sourřadnice. 16 Robotická ruka - idea Cestu z bodu A do bodu B na pracovní ploše lze snadno namapovat na cestu v úhlovém prostoru: Chybějící body v úhlovém prostoru se dostanou interpolací. 17 Analýza pohádek bratří Grimmú Zdroj: Contextual Relations of Words in Grimm Tales, Analyzed by Self-Organizing Map. T. Kohonen, T. Honkela a V. Pulkki, ICANN, 1995 Cílem je vizualizovat syntaktické a sémantické kategorie slov v pohádkách (v závislosti na kontextu). Vstup: Pohádky bratří Grimmu (srozumitelne kódované pomocí proudu 270-dimenzionálních vektoru) ► uvažují se trojice slov (predchudce, klíc, následník) ► každá položka v trojici se zakóduje náhodne vybraným 90-dimenzionálním reálným vektorem (trojice má tedy dimenzi 270) Síť: Kohonenova mapa, 42 x 36 neuronu, váhy neuronu jsou tvaru w = (wp, wk, wn) kde Wp, wk, wn e R90. 18 Analýza pohádek bratří GrimmU Adaptace: Síť je inicializována takto: nejprve je identifikován dvojrozmerný podprostor prostoru R270 jehož osy jsou ve smeru nejvetší variability dat. V tomto podprostoru tvoří váhy neuronu pravidelnou mřrížku se strředem ve strřední hodnoteř dat (rozloha mřrížky je odvozena z variability dat) Sít je natrénována na trojicích po sobe jdoucích slov z pohádek Pozn. Trojice byly agregovány pomocí pnjmeérování predchudcu a následníku apod. Hrubé ucení: 600 000 iterací; Dolad' ování: 400 000 Nakonec je vybráno 150 nejcasteji použitých slov, kterými jsou oznacřeny neurony: slovem u je oznacen ten neuron, pro jehož váhy w = (wp, wk, wn) platí, že wk je nejblíže kódu slova u. 19 Sítě s nervovým plynem :-) (Neural gas networks) Organizační dynamika: Jednovrstvá sít' yi yk yh 21 Neural gas Adaptivní dynamika: Inicializace: náhodně vygeneruj váhy neuronu. V kroku f po predložení Xf proved': ► uspořádej neurony od nejbližšího k nejvzdálenejšímu, tj. vypoCti ň,k,...ih t.ž. xf - w (f-i) < xf - w (f-i) i2 << xf - w (f-i) ih Dále pro každý neuron j urči počet kj ostatních neuronů, které jsou blíže k xř než neuron j, tj. i I xf - w (f-i) i < xf - w (f-i) j adaptuj váhy všech neuronu j takto: -1) + E • e-kJ/A • (Xf - w^(f Zde e,A e R+ jsou parametry uCení. 22 Neural gas s Hebbovským učením Pridáme topologickou strukturu: neorientovaný graf G G se bude konstruovat v prubehu ucení (neovlivnuje ucení), jeho smyslem je zvýraznit sousednost neuronu (podobne jako v naucřené Kohonenoveř mapeř) Adaptivní dynamika je stejná jako pro neural gas net, pouze přridáme manipulaci s grafem G ► iniciálne nemá G žádné hrany, v prubehu výpoctu budou mít hrany prirazen vek fij e N0 ► v každém kroku: ► přidáme hranu mezinejbližším a druhým nejbližším neuronem, tj. {ii, i2}, ke grafu G a vynulujeme vek této hrany: fili2 := 0 ► zvýšíme veřk ostatním hranám ► vyhodíme staré hrany (tj. ty co mají veřk vyšší než dané T) Pozn.: z duvodu vypocetní nárocnosti se aktualizace veeku a vyhazování hran obvykle delá pouze pro hrany vedoucí z neuronu i1. 23 RBF síte OrganizaCní dynamika: ► Dvouvrstvá sít (výstupní neuron má bias) - vstupy: x = (X1,...,xn) ► m skrytých neuronu Jejich hodnoty znacíme R a každé e > 0 existuje RBF sít' taková, že její funkce y splnuje: Vxe Rn 26 RBF sítě Adaptivní dynamika: Dána množina tréninkových vzorů Zde Xk = (xk!..., xkn) e Rn je vstup k-tého vzoru a dk e R je očekávaný výstup. Chybová fůnkcě: Cílem je nalézt následující parametry tak, aby byla chyba E minimalizována: ► váhy Wj výstupního neuronu ► středy Cj skrytých neuronu ► šířky oj skrytých neuronu T = E 27 RBF - dvoufázový trénink Velkou výhodou RBF sítí je, že jejich trénink lze rozdelit do dvou (témer) nezávislých fází: ► trénink skrytých neuronu, tj. ► umístení stredu q ► nastavení velikostišířek o j ► trénink vah Wj výstupního neuronu 28 RBF - stredy a šířky Rozmístění středU: Pozorování: Máme velké množství dat (vstupu), pro malou cást z nich máme prředepsán požadovaný výstup (tréninková množina). Je dobré umístit stredy neuronu do oblastí, které obsahují hodne datových bodu. Středy lze proto umístit pomocí ucení bez ucitele - Kohonenovo ucení (tj. k-means clustering), mapy, plyny apod. Toto lze provádet na mnohem vetší množine dat, pro které nepotřebujeme predepsaný výstup Často se ovšem používá i jednoduché rovnomerné rozmístení stredu (pokud víme, že data jsou více méne pravidelne rozmístěna) nebo umístení středu do pozice náhodne vybraných vstupu. Nastavení šírek: Aktivacní funkce by nemely být ani príliš strmé ani příliš ploché. Údajne dobrou heuristikou je jednotná šírka o = Dmax/ V2m kde Dmax je maximální (Euklidovská) vzdálenost středu a m je pocet skrytých neuronu. 29 RBF - váhy Pro fixní hodnoty parametru skrytých neuronu (tj. fixní stredy a šírky) se jedná o ADALINE. Mužeme proto použít príslušné metody k minimalizaci chyby E. Lze také nalézt analytické řešení: Pokud fixujeme všechny středy a šírky, chyba E je funkcí w (píšeme E(w)). Gradient funkce E(W) je roven (W • * - d) • *T kde d = (d1,..., dp), W = (w0,..., wm) a * je matice (m +1) x p jejíž i-tý sloupec obsahuje hodnoty skrytých neuronu pro i-tý vstup, tj. pro každé j = 1,..., m a i = 1,..., p máme / llX. C.lh *ji = (pj (Xi) = exp |X/ - Cj1 Vektor wwT = d • *+ kde *+ = *T • (* • *T)-1 potom reší (ww • * - d) • *T = 0 a tedy minimalizuje E(w). 30 Site typu RBF - gradient Učení lze také provádět pomocí standardního gradientního sestupu. Gradient lze snadno spočítat přímým derivováním: ÔE ÖOj k=G P k=G P ||Xk -CjH ||Xk -Cj| k=G \*k - Cj| (Xki - Cji)2 02 Rychlost tohoto učení je ovšem srovnatelná s rychlostí zpetné propagace pro standardní (sigmoidální) síte. 31 RBF sítě - regularizace Naučená síť by mela dobře generalizovať. Nemela by příliš „opisovat" tréninkové vzory (tj. nemela by být přetrénovaná). Intuice: Funkče síte, která príliš opisuje vzory se hodne kroutí -omezíme kroučení. Definujeme novou chybovou fči Zde y > 0 je míra vlivu regularizace. Váhy, které minimalizují E'(w), jsou řešením: w• M = d• <ř>T kde (Pozn. pro y = 0 dostaneme M = <ř> • <ř>T, tj. minimalizaci E(w)) E' = E + y 2 32 RBF síte - výhody Srovnejme s vícevrstvou sítí se sigmoidálními jednotkami (dále budu znacit MP (multi-layer perceptron)) ► Teoreticky lze aproximovat libovolnou spojitou fci (stejne jako MP) ► Dvoufázové ucení: jednotlivé fáze jsou rádove rychlejší než ucení MP (tj. zpetná propagace) ► RBF síte jsou vhodné pro klasifikaci (více než MP) díky jejich lokálnímu charakteru. Vektory, které jsou daleko od tréninkových vzoru, dostanou malou hodnotu (toto nemusí platit pro MP). ► jsou vhodné pro aplikace s menícími se daty (rychlé ucení umožnuje on-line adaptaci na nová data - témer nemožné s MP) ► snadná regularizace (lineární) 33 RBF síte - nevýhody Opet srovnejme s MP. ► Teoretické výsledky o aproximacinefungují v praxi(odhady na potrebný pocet neuronu jsou nadsazené podobne jako u MP) ► Dvoufázové ucení muže být deformované pokud požadované funkcní hodnoty nerespektují rozmístění vstupu (napr. pokud je požadovaná funkce konstantní v oblastis mnoha vzory, ale velmi variabilní v oblastis málo vzory) ► RBF potrebují mnohem více dat i neuronu pro stejnou presnost jako MP. ► MP aproximují funkciglobálne: každý vzor adaptuje vetšinu neuronu a informace je tedy distribuována po síti ► RBF aproximují lokálne: pouze nekolik málo neuronu reaguje na daný vstup Z toho také plynou lepší extrapolacní vlastnostiMP. ► RBF síte mají vetší problém s prokletím dimenzionality (exponenciální nárust jednotek s poctem dimenzí). Nejsou schopny odhalit nízkou variabilitu predepsané funkce v daném smeru. 34 RBF síte - nevýhody kvadratický nárust poctu neuronu; RBF neumí poznat, že je funkce (v podstate) konstantní v x2 (MP to umí) 35