Kohonenova mapa - opakování Organizační dynamika: Jednovrstvá síť yi y k y h X^ X; xn ► Mezi neurony je navíc zavedena topologická struktura (tj. neurony tvoří uzly neorientovaného grafu). ► V drtivé většině případů je tato struktura buď jednorozměrná řada jednotek nebo dvojrozměrná mřížka. i Kohonenova mapa Aktivní dynamika: Pro vstup x e R" a k fl k = argminf=1/..v/l ||x- w,|| lO jinak \,...,h: Adaptivní dynamika: V adaptivním režimu využijeme topologickou strukturu. ► Označme d(c,k) délku nejkratší cesty z neuronu c do neuronu k v topologické struktuře. ► Pro neuron c a dané s £ No definujeme okolí neuronu c velikosti s takto: Ns(c) = [k \ d{c,k) < s] V kroku ř po předložení vstupu xt adaptujeme každé wk takto: w, (0 w, w, (t-1) k (f-1) + 0-(xř-4ř_1)) k£Ns(c) kde c = arg min/=1/..v/l xř - .(t-1) jinak a kde 0 e R a s £ N0 jsou parametry, které se mohou v průběhu učení měnit. Kohonenova mapa - adaptivní dynamika Obecnější formulace adaptivní dynamiky: <) = <-1) + 0(c,/c).(x-<-1)) kde c = arg min,=-| odpovídá Q{c,k) xt - w; \9 keNs(c) lO jinak (ř-1) . Předchozí případ potom Obvykle se používá plynulejší přechod mezi nenulovými a nulovými hodnotami, např. 0(c,/c) = 0O • exP -d{c,kf kde 0O e K určuje maximální míru změny vah a o e R je šířka (oba parametry se mohou v průběhu měnit). 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 {C-i,..., Cq} určuje jednu z q tříd. Cílem je klasifikovat vstupy do tříd na základě znalosti vlastností, tj. každému xt chceme přiřadit třídu tak, abychom minimalizovali pravděpodobnost chyby. Př.: Po pásu jede náhodně „naházené" ovoce dvou druhů: jablka a meruňky. Námi sledovaná data budou (x(,c/() kde ► xt e IR2, první vlastnost je hmotnost, druhá je průměr ► dt je buď J nebo M v závislosti na tom, jestli je daný kus jablko nebo meruňka 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ákladě hmotnosti a průměru. LVQ - klasifikace - opakování Využijeme vektorovou kvantizaci (Kohonenovu mapu) takto: 1. Natrénujeme mapu na vektorech vlastností xt kde \ = \,...,l. 2. Jednotlivé neurony označíme třídami. Třídu vc neuronu c nalezneme takto: Pro každý neuron c a třídu C, spočítáme četnost vzorů třídy Q, které jsou reprezentovány neuronem c. Toto lze provést jedním průchodem přes vzory Neuronu c přiřadíme třídu s maximální četností. 3. Doladíme síť pomocí algoritmu LVQ. Klasifikaci pomocí natrénované sítě provádíme takto: Na vektor vlastností x aplikujeme natrénovanou síť v aktivním režimu. Právě jeden neuron, řekněme c, bude mít výstup 1. Potom vstup zařadíme do třídy vc. Postupně projdi tréninkové vzory. Pro vzor (xt,dt) urči nejbližší neuron c c = arg min ||xř - w,|| /=i,...,/iM Potom uprav váhy neuronu c takto: (ř)_ (w^+aixt-^) dt = vc 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 poměrně dobrou aproximací bayesovské rozhodovací hranice. Klasická aplikace - fonetický psací stroj Zdroj: The Self-Organizing Map. T. Kohonen, IEEE, 1990 Cílem je automaticky zapisovat diktovaný text (v originále buď 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 (FFT) ► 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é střední hodnoty komponent a konstantní délku vektorů. 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é přiřazeny fonémy jednotlivým neuronům, doladěno pomocí LVQ. ©00®©©000000 0©0©0 00000©0 00000000000© 00000000000© ©©©©©©©q©®©© ©©©©©©©©©©©© ©©000©©00©©0 OO000 0000000 Klasická aplikace - fonetický psací stroj Mapu lze vyžít k vizualizaci mluveného slova (zde Humpilla): a PP 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 LVQ3 Test 1 12.1 12.0 10.2 9,8 9.6 Test 2 13.8 12.1 13.2 12.0 11.5 9 Oceánografická 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) Oceánografická data ► 11 měřicích stanic, 3 hloubky (hladina, dno, mezi) ► data: 2D vektory rychlosti (a směru) proudění ► měřeno po hodinách, 25585 hodin Celkově tedy 25585 řádků 66 dimenzionálních položek. Kohonenova mapa: ► mřížka 3x4 ► okolí dána Gaussovou funkcí se zmenšující se šířkou (navíc je tam lineárně se zmenšující rychlost učení, kterou se násobí změna polohy neuronů) 11 Oceánografická data x s xxxxwqmí cxxxxkxk XX xwsí »xxx Xí x x hxx x x 36« kxx » * xxx XXXÄOC x x3cxxxs9í xxc^kx x*aKxc« xxx-c-skhm: x xxxw xxxx xw; wok-xxcxxxhkx xxkxixx x st #xxxxo*svxx x 7 -xx *>x«xx>;»x >3k xX xx x JIKx)*séx *Ht«MnnMe; xxmoíx - xxxacK x xx xfsťxcxx xaoK^nxc^oocxxoc xk -m x je\xkxxxxxj&xxxsosocx x xx .:-xx x 4 - XXXXWKSřSKXX xxxwk x skx )* xxxxxxxwc« x xx* XX xx x xx »x )»(KXXMK Xí xxx 3 - xxx x *x xwmc yaw x x*x * xx m x>xxx^x xxxxx x% x . x»xxxxx >ac x x- «<*xx x 2 - x %xxx xkx wxxk xx xx x xxxkx^ skoe 3k -XüSiC 1 -XH XXJQtCX jkxxk JKX X x xx *xxx x:«.x Mwoacxx* >ac x x< »owxx * x XX xxx *SS< »cx xx xx v|t NDJ FMAMJJ ASONDJ FMAMJ JASONDJ FMAMJ JAS 1998 1999 2000 2001 ► 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étě neurony 10-12 (severo-západ) 13 Oceánografická data -2 - ^ X-~ Srovnání směru větru a proudění vody (znatelná korelace) ► vítr: směr čáry = směr větru ; délka čáry = intenzita ► proudění vody v procentech úspěšnosti skupin neuronů 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ří Grimmů (srozumitelně kódované pomocí proudu 270-dimenzionálních vektorů) ► každé slovo se zakóduje pomocí náhodně vybraného 90-dimenzionálního vektoru ► uvažují se trojice slov (předchůdce, klíč, následník) ► každá položka v trojici se reprezentuje 90-dimenzionálním reálným vektorem (trojice má tedy dimenzi 270) Síť: Kohonenova mapa, 42 x 36 neuronů, váhy neuronů jsou tvaru w = (Wp, wkl wn) kde wp, wkl wn e R90. 15 Analýza pohádek bratří Grimmů Adaptace: Síť je natrénována na trojicích po sobě jdoucích slov z pohádek Hrubé učení: 600 000 iterací; Dolaďování: 400 000 Nakonec 150 nejčastěji použitých slov označuje neurony: slovem uje označen ten neuron, pro jehož váhy w = (Wp, Wk, wn) platí, že Wk je nejblíže kódu slova u. 16 RBF sítě Organizační dynamika: ► Dvouvrstvá síť (výstupní neuron má bias) ► vstupy: x = (xi,...,x„) ► m skrytých neuronů Jejich hodnoty značíme (po,(p^,...,(pm kde o(x),i(x),.. .,m(x) abych zdůraznil, že se jedná o hodnoty skrytých neuronů pro vstup sítě x. ► jeden výstup: y (pro jednoduchost; lze zobecnit na libovolný počet) Parametry sítě: ► Výstupní neuron je jako ADALINE: má váhový vektor w e rm+1 ► Každý skrytý neuron má tzv. střed q e r" (odpovídá váhám ve standardní vícevrstvé síti) a šířku (odpovídá strmosti ve standardní síti, tj. je to parametr aktivační funkce) 18 RBF site Aktivní dynamika: Vnitřní potenciály skrytých neuronů: X - C; Zde q je střed skrytého neuronu j. Aktivační funkce skrytých neuronů cpo, E a každé e > 0 existuje RBF síť taková, že její funkce y splňuje: \f(it)-y()t)\ - d) ■ T kde d = {d^,...,dp), w = (wo,...,wm) a <í> je matice (m +1) x p jejíž ;'-tý sloupec obsahuje hodnoty skrytých neuronů pro ;'-tý vstup, tj. pro každé j = 1,.. .,m a ;' = 1,.. .,p máme Vektor wT = d ■ í>+ kde <í>+ = 7 • (<$> • 7) 1 potom řeší (vv • <í> - d) ■ T = 0 a tedy minimalizuje E(w). p = (pj(Xi) = exp - 24 Sítě 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: Rychlost tohoto učení je ovšem srovnatelná s rychlostí zpětné propagace pro standardní (sigmoidální) sítě. 25 Naučená síť by měla dobře generalizovat. Neměla by příliš „opisovat" tréninkové vzory (tj. neměla by být přetrénovaná). Intuice: Funkce sítě, která příliš opisuje vzory se hodně kroutí -omezíme kroucení. Definujeme novou chybovou fci 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)) i 26 RBF sítě - výhody Srovnejme s vícevrstvou sítí se sigmoidálními jednotkami (dále budu značit MP (multi-layer perceptron)) ► Teoreticky lze aproximovat libovolnou spojitou fci (stejně jako MP) ► Dvoufázové učení: jednotlivé fáze jsou řádově rychlejší než učení MP (tj. zpětná propagace) ► RBF sítě jsou vhodné pro klasifikaci (více než MP) díky jejich lokálnímu charakteru. Vektory které jsou daleko od tréninkových vzorů, dostanou malou hodnotu (toto nemusí platit pro MP). ► jsou vhodné pro aplikace s měnícími se daty (rychlé učení umožňuje on-line adaptaci na nová data - téměř nemožné s MP) ► snadná regularizace (lineární) RBF sítě - nevýhody Opět srovnejme s MR ► Teoretické výsledky o aproximaci nefungují v praxi (odhady na potřebný počet neuronů jsou nadsazené podobně jako u MP) ► Dvoufázové učení může být deformované pokud požadované funkční hodnoty nerespektují rozmístění vstupů (např. pokud je požadovaná funkce konstantní v oblasti s mnoha vzory, ale velmi variabilní v oblasti s málo vzory) ► RBF potřebují mnohem více dat i neuronů pro stejnou přesnost jako MP. ► MP aproximují funkci globálně: každý vzor adaptuje většinu neuronů a informace je tedy distribuována po síti ► RBF aproximují lokálně: pouze několik málo neuronů reaguje na daný vstup Z toho také plynou lepší extrapolační vlastnosti MP. ► RBF sítě mají větší problém s prokletím dimenzionality (exponenciální nárůst jednotek s počtem dimenzí). Nejsou schopny odhalit nízkou variabilitu předepsané funkce v daném směru. RBF sítě - nevýhody Omezený Boltzmannův stroj (OBS) Organizační dynamika: ► Cyklická síť se symetrickými spoji, neurony jsou rozděleny do dvou skupin: ► V - viditelné ► S - skryté Množina spojů je V x S (tj. úplný bipartitní graf) ► Množinu všech neuronů značíme N *■ označme £y vnitřní potenciál a y, výstup (stav) neuronu j - stav stroje: ý e {-1,1 }|N|. ► označme wp váhu spoje od neuronu ;' k neuronu j. ► obvykle se uvažuje bias, pro zjednodušení jej vynecháme. 30 mezený Botzmannův stroj Aktivní dynamika: Stavy viditelných neuronů jsou iniciálně nastaveny na hodnoty z množiny {-1,1}. V ř-tém kroku aktualizujeme neurony takto: ► ř liché: náhodně zvolíme nové hodnoty skrytých neuronů, pro j e S í ( 1 + exp ieV *■ t sudé: náhodně zvolíme nové hodnoty viditelných neuronů, pro j e V P[>f = i] = i/ í ( 1 + exp ieS Rovnovážný stav Omezený Boltzmannův stroj se po jisté době dostane do termální rovnováhy. Tj. existuje čas ř* takový, že pro libovolný stav stroje y* e {-1,1 }|N| platí ye(-1,1)lNl tj. Boltzmannovo rozložení Teorie Markovových řetězců říká, že P [ý(r) = y*] je také dlouhodobá frekvence návštěv stavu y*. Toto platí bez ohledu na iniciální nastavení neuronů! Síť tedy reprezentuje rozložení pN. P [;('*> =/]*pN(/) Zde pN{y*) = ^e-£^*)/Tkde 32 Omezený Boltzmannův stroj - učení Pro daný stav viditelných neuronů a e {-1,1}'V| označme pravděpodobnost stavu viditelných neuronů a v termální rovnováze bez ohledu na stav skrytých neuronů. Adaptivní dynamika: Nechť Pd je pravděpodobnostní rozložení na množině stavů viditelných neuronů, tj. na {-1, Cílem je nalézt konfiguraci sítě W takovou, že pv odpovídá p^. Vhodnou mírou rozdílu mezi rozděleními pv a p^ je relativní entropie zvážená pravděpodobnostmi vzorů (tzv. Kullback Leibler distance) /?e(-1,1)lsl Pd{a) pv{a) 33 Omezený Boltzmannův stroj - učení £(w) budeme minimalizovat pomocí gradientního sestupu, tj. budeme počítat posloupnost vektorů vah w(°\ w^\... ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku (zde ř = 1,2,...) je vypočteno takto: p p ji kde Aw(0 = _£(ř).^(^(ř-1)) j' y ' dWjjy ' je změna váhy w,, v ř-tém kroku a 0 < e(t) < 1 je rychlost učení v ř-tém kroku. Zbývá spočítat (odhadnout) ^(w). (mezený Boltzmannův stroj - učení Lze ukázat, že d8 dWjj V" Hixed V] Ji llree " {yjy)fixed Je Poměrná hodnota y/y, po jednom kroku výpočtu za předpokladu, že hodnoty viditelných neuronů jsou fixovány dle rozložení pd. ► (y^ V-ř je průměrná hodnota yjl ^ v termální rovnováze bez fixace viditelných neuronů. Problém: výpočet (y^ trvá dlouho (musíme opakovaně přivést stroj do termální rovnováhy). (yf Vf ^)free se proto nahrazuje (yjyi)recon c°ž je průměrná hodnota y-3V^ za předpokladu, že iniciální hodnoty viditelných neuronů jsou voleny dle p