Boltzmannův stroj - opakování Organizační dynamika: ► Cyklická síť se symetrickými spoji (tj. libovolný neorientovaný graf) ► Množinu všech neuronů značíme N *■ označme £y vnitřní potenciál a ys výstup (stav) neuronu j *■ stav stroje: ý e {-1,1 }|N|. ► označme w,, reálnou váhu spoje od neuronu ;' k neuronu j. *■ žádný neuron nemá bias a přepokládáme Wý = 0 pro j e N. i Botzmannův stroj - opakování Aktivní dynamika: Stavy neuronů jsou iniciálně nastaveny na hodnoty z množiny {-1,1}, tj. y^ e {-1,1} pro j e N. V ř-tém kroku aktualizujeme náhodně vybraný neuron j e N takto: nejprve vypočteme vnitřní potenciál ťP = 2>yíM a poté náhodně zvolíme hodnotu e {-1,1} tak, že (0 1 a(£{í-1)) kde 1 1 + e-2í/T(í) Parametr T(ř) se nazývá teplota v čase ř. Boltzmannův stroj - opakování ► Velmi vysoká teplota T(ř) znamená, že P [yp = i] « \ a stroj se chová téměř náhodně. ► Velmi nízká teplota T(ř) znamená, že buď P[y^ = i] « 1 nebo P [yí^ = i] « 0 v závislosti na tom, jestli EJp > 0 nebo < 0. Potom se stroj chová téměř deterministicky (tj. jako Hopfieldova síť). 3 Boltzmannův stroj - reprezentace rozložení Cíl: Chceme sestrojit síť, která bude reprezentovat dané pravděpodobnostní rozložení na množině vektorů {-1,1}". Velmi hrubá a nepřesná idea: Boltzmannův stroj mění náhodně svůj stav z množiny {-1,1 }n. Když necháme B. stroj běžet dost dlouho s fixní teplotou, potom budou frekvence návštěv jednotlivých stavů nezávislé na iniciálním stavu. Tyto frekvence budeme považovat za pravděpodobnostní rozložení na {-1,1}n reprezentované B. strojem. V adaptivním režimu bude zadáno nějaké rozložení na stavech a cílem bude nalézt konfiguraci takovou, že rozložení reprezentované strojem bude odpovídat zadanému rozložení. Fixujme teplotu T (tj. T(ŕ) = T pro ŕ = 1,2,...). Boltzmannův stroj se po jisté době dostane do tzv. termálni 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í Pozn.: Teorie Markovových řetězců říká, že P [ý(f) = 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í p^. P =/]*pN(/) Zde pN(y*) = le-£(y*)/Tkde Boltzmannův stroj - učení Problém: Tak jak jsme si jej definovali má Boltzmannův stroj omezenou schopnost reprezentovat daná rozložení. Proto množinu neuronů N disjunktně rozdělíme na ► množinu viditelných neuronů V ► množinu skrytých neuronů S. Pro daný stav viditelných neuronů a e {-1,1}'V| označme pravděpodobnost stavu viditelných neuronů a v termálním ekvilibriu bez ohledu na stav skrytých neuronů. Cílem bude adaptovat síť podle daného rozložení na {-1,1} /?e(-1,1)lsl Boltzmannův stroj - učení 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) Pd{a) pv{a) Boltzmannův stroj - učení £(w) budeme minimalizovat pomocí gradientního sestupu, tj. budeme počítat poslounost vektorů vah 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 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). Boltzmannův stroj - učení Formálním derivováním funkce £ lze ukázat, že ► (y^ V-ř ^)f. d je průměrná hodnota y^ř ^ v termální rovnováze za předpokladu, že hodnoty viditelných neuronů jsou fixovány na počátku výpočtu dle rozložení p^. ► (y^ V-ř je průměrná hodnota yj* ^ v termální rovnováze bez fixace viditelných neuronů. Celkově 9 Boltzmannův stroj - učení Pro výpočet (y^ ^)fj d Proveď následující: ► Polož J/ := 0 a proveď následující akce q krát: 1. fixuj náhodně hodnoty viditelných neuronů dle rozložení pd (tj. v průběhu následujících kroků je neaktualizuj) 2. simuluj stroj po ľ kroků [ Lepší způsob: simuluj stroj tak dlouho, dokud nedosáhne termální rovnováhy při nízké teplotě (zde je možné použít simulované žíhání, tedy pomalé snižování teploty). ] 3. přičti aktuální hodnotu yy k proměnné J/. ► J//q bude dobrým odhadem (y.'ř V-ř ^) z& předpokladu, \ I 1 I fixed že q je dostatečně velké číslo. (yf ^)free se odhadne podobně, pouze se nefixují viditelné neurony (tj. v kroku 1. se zvolí libovolný startovní stav a v následném výpočtu se mohou aktualizovat všechny neurony). 10 Boltzmannův stroj - uče Pro upřesnění analytická verze: ,(0 _ argmin/=1.....h xt - w (ř-1) pak w, (ř-1) + 0(ř)-(x-w[ř-1)) jinak vv^ = vv; »,(f-i) Parametr 0 < 9 < 1 určuje míru změny vah ve směru ke vstupnímu vzoru. Na začátku učení se obvykle volí blízko 1 a postupně se zmenšuje. Efektivita Kohonenova učení ► Funguje dobře pokud většina vstupu zhruba rovnoměrně pokrývá jednu konvexní oblast. ► V případě dvou a více oddělených shluků nemusí hustota reprezentantů odpovídat hustotě rozložení: ► Př. dvě oddělené oblasti se stejnou hustotou. ► Předp., že vzory jsou iniciálně rozmístěny v jedné oblasti. ► Druhá potom přitáhne jednoho reprezentanta, který poté vždy vyhraje soutěž. ► Výsledek: jedna oblast bude reprezentována jedním reprezentantem, druhá zbytkem reprezentantů (hustota reprezentantů tedy neodpovídá hustotě pravděpodobnosti). Částečná zlepšení Kohonenova učen' Tyto nedostatky lze částečně odstranit např. ► přidáním šumu k tréninkovým vzorům - obvykle se přidávají náhodně generované vektory k tréninkovým vzorům, na počátku učení náhodné vektory převažují a postupně je jejich počet snižován ► radiální růst ► začínáme s váhovými vektory blízko 0 ► všechny tréninkové vzory násobíme faktorem jS, který je na počátku blízko 0 a postupně roste (váhy se musí postupně vzdalovat od 0) ► lokální paměť: Cílem je, aby pravděpodobnost vítězství každého z h neuronů (reprezentantů) byla zhruba 1 /h. Každý neuron si udržuje přehled o tom kolikrát vyhrál v soutěži. Pokud je četnost výher příliš vysoká, na nějakou dobu vypadne ze soutěže. 21 Kohonenova mapa 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. Kohonenova mapa - ilustrace Kohonenova mapa - bio odbočka posterior cortex (lobjs occipitalis) visual field of the right eye 0 center of the visual field and corresponding cortex region visual field and corresponding cortex region Fig. 15.2. Mapping of the visual field on the cortex Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996 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: w, (0 >(f-i) wr ' + 0(c,/c)-(x-vv[ř-1)) kde c = arg min,-^..^ odpovídá xt - w (ř-1) . Předchozí případ potom e(c,/c) \e keNs(c) lO jinak Obvykle se používá plynulejší přechod mezi nenulovými a nulovými hodnotami, např. ®(c,k) = 6q ■ 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). Příklad 1 Vstupy jsou uniformně rozloženy v trojúhelníku. Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996 28 Příklad 3 Příklad 4 Příklad - defekt Překroucená síť - topologický defekt. Zdroj obrázku: Neural Networks - A Systematic Introduction, Raul Rojas, Springer, 1996 Kohonenova mapa - parametry - pohled praktika Iniciální váhy (prý) nejsou příliš důležité, pokud jsou různé. Učení se obvykle sestává ze dvou fází: hrubé učení: ► obvykle cca 1000 kroků rychlost učení 9 by měla začít kolem 0.1 a postupně klesat k 0.01 ► okolí každého neuronu (dané parametrem s nebo případně šířkou o) by mělo zpočátku obsahovat většinu neuronů a postupně se zmenšovat tak, aby ke konci této fáze obsahovalo nejvýše několik neuronů dolaďování: *■ počet kroků je obvykle volen jako 500 násobek počtu neuronů v síti ► 9 by se měla držet kolem 0.01 jinak hrozí topologický defekt (zmačkaná síť) ► okolí každého neuronů by mělo obsahovat jen pár dalších neuronů (nebo jen ten jeden) Kohonenova mapa - pohled teoretika Předpokládáme náhodně generované vstupy s hustotou pravděpodobnosti p(x). Platí Jp(x)dx = 1. Definujeme hustotu bodů m(x) = #(x)/dx kde #(x) je počet neuronů jejichž váhové vektory leží v malém okolí dx bodu x ve vstupním prostoru. Platí kde h je počet neuronů (reprezentantů). Pokud je dimenze mapy rovna jedné (tj. mapa je řetězcem neuronů) pak po natrénování m(x) cc p2/3(x) Kohonenova mapa - pohled teoretika ► Konvergenci k uspořádanému stavu se podařilo dokázat pouze pro jednorozměrnou topologii a různá rozložení vstupů (první výsledky byly pro uniformní rozložení) a fixní okolí velikosti 1 a konstantní rychlost učení Lze nalézt velice jednoduché protipříklady pokud tyto podmínky nejsou splněny. ► Ve vícerozměrném případě žádné obecné výsledky neexistují, konvergence do uspořádaného stavu je ovlivněna mnoha faktory: ► iniciální rozložení neuronů ► velikost okolí ► rychlost učení ► Jakou dimenzi topologie zvolit? Drtivá většina aplikací je založena na jedné nebo dvoudimenzionální mapě. Experimenty prokázaly, že ideální dimenze topologie odpovídá (Haussdorfově) dimenzi dat. 34 LV - klasifikace pomocí Kohonenovy mapy Přepodkládejme, že máme náhodně generované vzory tvaru (xř/ dt) kde xt e Rn je vektor vlastností a dt e {d,..., 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 xř 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ř, dř) kde ► x( e R2, 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 najdou dvě jablka se stejnými mírami. Cílem je třídit ovoce na základě hmotnosti a průměru. 35 LV - klasifikace pomocí Kohonenovy mapy 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 (viz. dále) 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. LVQ1 Postupně projdi tréninkové vzory. Pro vzor (xtldt) urči nejbližší neuron c c = arg min ||x(-vv/|| 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. Co to je?? ;=1,...,/! Potom uprav váhy neuronu c takto: dt = vc dt * v c 37 Bayesovský klasifikátor Mějme pouze dvě třídy Co a C| (např. J a M). Nechť P(C, | x) je pravděpodobnost, že je vstup z třídy C, za přepodkladu, že má vlastnost x. (např. P(Co | (a,b)) vyjadřuje pravděpodobnost, že ovoce s hmotností a a průměrem b je jablko) Bayesovský klasifikátor přiřadí vstupu s vektorem vlastností x třídu Q, která splňuje P(C, | x) > P(Ci_; | x). Označme R0 množinu všech x, která splňují P(C0 | x) > P(Ci | x) a Pn = Rn \ fí0- Bayesovský klasifikátor minimalizuje pravděpodobnost chyby: P(x £ R0 a d ) + P(x £ Rt a C0) Bayesovská hranice je hranicí mezi množinami R0 a Ri. 38 Bayesovská hranice a LVQ1 - příklad Aproximaci bayesovské hranice je možné zlepšit následujícím způsobem: Pro vzor (xt, dt) určíme dva nejbližší neurony řekněme ; a j s aktuálními váhami vvíř~1^ a vvíř~1^. Jestliže jsou splněny následující dvě podmínky ► xt se nachází v okně okolo nadroviny umístěné ve středu ■ ■ ->(f-l) -»(ř-i) spojnice wy ' a vir 'a jeden z neuronů ;' a j klasifikuje správně a druhý špatně pak aktualizujeme váhy takto (bez újmy na obecnosti předpokládejme, že neuron ;' klasifikuje správně): v5jt) = v5řt-1)+a(i?t-v5řt)) = wj^ - a(xt - ^) 40 LVQ2 Okno je obvykle definováno takto: Řekneme, že xt se nachází v okně relativní šířky q mezi wjl~^ a vv'ř~1^ pokud d i dj\ ^ 1 -q 1 +Q kde d (ř-i) a d, xt - wj (ř-1) Obvykle se volí q mezi 0.1 až 0.3. LVQ2 zlepšuje pozici rozhodovací hranice tím, že ji posunuje k bayesovské hranici, ale jen do určitého počtu kroků. Později se neurony začínají vzdalovat (typicky se používá kolem 10 000 iterací). 41 LVQ3 LVQ3 se snaží odstranit defekt LVQ2 tím, že dobře klasifikující dvojici nejbližších neuronů posunuje směrem k vzoru (LVQ2 v takovém případě nedělá nic): Nejprve „LVQ2 část": v5jt) = v5řt-1)+a(i?t-v5řt)) ^ = ^-a{xt-wf)) pokud ;' a y je pár výstupních neuronů nejblíže k xt, v, = dt, Vj + dt a xt patří do okna mezi a wjl\ Navíc: = ^ + ea(xt - 4t]) pokud r e [i, j} a vf- = vs = dt. e se doporučuje nastavit dle šířky okna mezi 0.1 až 0.5 a nechat konstantní. 42