Asociativní sítě Cílem je uchovat množinu vzorů {(xk,dk) \ k = 1,...,p} tak, aby platilo následující: Po předložení nového vstupu x, který je „blízko" některému xk bude výstup sítě roven (nebo alespoň blízko) dk. Zejména by síť měla mít schopnost reprodukce: Pro vstup Xk by měla dát výstup dk- i Lineární asociativní síť (alias ADALINE s Hebbovým učením) (Pro jednoduchost a srovnání s ADALINE uvážíme pouze jeden výstup) Organizační dynamika LAS: y w0 xo = i —K) w = (wQ,wA,...,wn) ax = (%x1(...,jfn) kdex0 = 1. Aktivní dynamika: funkce sítě: y[vv](x) = w ■ x = £"=0 w,x Hebbovo učení Adaptivní dynamika: Dána množina tréninkových vzorů T = {(xA,dA),{x2,d2),...,(xp,dp)] Zde xk = {xk0,xki.. .,xkn)T e Rn+1, x^o = 1, je vstup /c-tého vzoru a dk e R je očekávaný výstup. Intuice: chceme, aby síť počítala afinní aproximaci funkce, jejíž (některé) hodnoty nám předepisuje tréninková množina. 3 Hebbovo učení Hebbův zákon: When an axon of a cell A is near enough to excite a 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. Zákon formuloval neuropsycholog Donald Hebb v knize „tne organization of Behavior" z roku 1949. Jinými slovy: Cells that fire together, wire together. Formulace používaná v umělých NS: Změna váhy spoje mezi dvěma neurony je úměrná jejich souhlasné aktivitě. Hebb se snažil vysvětlit podmíněné reflexy: Současná aktivita/pasivita presynaptického neuronu (příčina) a postsynaptického neuronu (reakce) posiluje/zeslabuje synaptickou vazbu. 4 Hebbovo učení LAS Algoritmus počítá posloupnost vektorů vah w^°\ w^\..., : ► v^0) = o pro 0 < ;' < n, - v kroku k (zde k = 1,2,...) je síti předložen vzor (Xk,dk) a váhy se adaptují podle Hebbova zákona: tfCO = w^+lkdk Výsledný vektor: p tf = tf(P) = YjXkdk =XTd kde X je matice, která má v i-tém řádku vektor xj a d = {d,,...,dPY LAS a ortonormální vstupy Pokud jsou i?i,..., xp ortonormální, tedy x; Xj [0 \*\ pak LAS má schopnost reprodukce: p p ...a asociace: Uvažme vstup: xr + ú kde norma ||u|| je malá. Chyba sítě pro r-tý vzor perturbovaný vektorem u: r := \w (xr + u) - dr\ = \w xr + w u - dr\ = \w u\ Pokud dr e {-1,1}, pak Er = \wTú\ ( p p k=1 < £ \dk(^Ú)\ < £ \dk\ pk\\\\Ú\\ < n\\Ú\\ (Zde první nerovnost plyne z trojúhelníkové nerovnosti, druhá z Cauchyho-Schwarzovy nerovnosti a poslední z p < n, protože mohutnost množiny ortonormálních vektorů v R" nemůže být větší než n.) Tedy pro vstupy blízké vzorům odpovídá přibližně požadovaným výstupem Hopfieldova síť ► Definice Energetická funkce ► Reprodukce ► Asociace Hopfieldova síť Autoasociativní síť. Organizační dynamika: ► úplná topologie, tj. každý neuron je spojen s každým všechny neurony jsou současně vstupní i výstupní ► označme £1, • • •, £„ vnitřní potenciály a /i,..., y„ výstupy (stavy) jednotlivých neuronů ► označme w,, celočíselnou váhu spoje od neuronu ;' £ {1,.. . ,nj k neuronu j e {1,.. .,n) ► Zatím: žádný neuron nemá bias a přepokládáme w# = 0 pro každé j = 1,..., n Hopfieldova síť Adaptivní dynamika: Dána tréninková množina T = {xk\xk = (xkA,...,xkn) e {-1,1}n,/c = 1,...,p} Adaptace probíhá podle Hebbova zákona (podobně jako u LAS). Výsledná konfigurace je Všimněte si, že w,, = Wy, tedy matice vah je symetrická. Adaptaci lze vidět jako hlasování vzorů o vazbách neuronů: Wjj = Wjj se rovná rozdílu mezi počtem souhlasných stavů xkj = xkj neuronů ;' a j a počtem rozdílných stavů xkj + xkj. p 1 0 ^(,) = 0 -1 < 0 11 Hopfieldova síť - aktivní dynamika Výpočet končí v kroku ř* pokud se síť nachází (poprvé) ve stabilním stavu, tj. yf+n) = yf] (i = i.....") Věta Za předpokladu symetrie vah, výpočet Hopfieldovy sítě skončí pro každý vstup. Z toho plyne, že Hopfieldova síť počítá funkci z {-1,1}" do {-1,1}" (která závisí na hodnotách vah neuronů). Označme ý(W,x) = (y|ř \...,y\* ^ hodnotu funkce sítě pro vstup x a matici vah W. Dále označme yj(W,x) = yjř ^ složku hodnoty funkce sítě, která odpovídá neuronu j. Pokud bude W jasné z kontextu, budu psát jen y(x) a y;(x) 12 Fyzikální analogie (Isingův model) Jednoduché modely magnetických materiálů připomínají Hopfieldovu síť. ► atomické magnety poskládané do mřížky ► každý magnet může mít pouze jednu ze dvou orientací (v Hopfieldově síti+1 a-1) * T t t T T *~ onentac' každého magnetu ovlivňuje jednak vnější magnetické pole ' T T T T T (vstup sítě), jednak magnetické pole ostatních magnetů (závisí na jejich '????? orientaci) ► synaptické váhy modelují vzájemnou interakci magnetů Energetická funkce Energetická funkce E přiřazuje každému stavu sítě ý e {-1,1}n potenciálni energii danou ► stavy s nízkou energií jsou stabilní (málo neuronů „chce" změnit svůj stav), stavy s vysokou energií jsou nestabilní ► tj. velké (kladné) w/yy/y, je stabilní a malé (záporné) w/iyy nestabilní V průběhu výpočtu se energie nezvyšuje: E(ý^) > E(ý(ŕ+1)), stav ý(r) odpovídá lokálnímu minimu funkce E. 14 Energetická plocha Hopfield - příklad yz E 1 1 1 1 1 1 -1 1 1 -1 1 -3 1 -1 -1 1 -1 1 1 1 -1 1 -1 -3 -1 -1 1 1 -1 -1 -1 1 Hopfieldova síť se třemi neurony naučili jsme ji jeden vzor (1,-1,1) pomocí Hebbova učení (síť se automaticky „naučila" i vzor (-1,1,-1)) 16 Energetická funkce - konvergence výpočtu sítě Pomocí pojmu energie lze snadno dokázat, že výpočet Hopfieldovy sítě vždy zastaví: ► v průběhu výpočtu se energie nezvyšuje: E(>W) > E(/ř+1)) pokud dojde v kroku ř + 1 ke změně stavu, pak E(yM) > E(ý(f+1)) ► existuje pouze konečně mnoho stavů sítě: výpočet dosáhne lokálního minima funkce E, ze kterého už se nedostane Hopfieldova síť - odučování Při učení podle Hebbova zákona mohou vznikat lokální minima funkce E, tzv. nepravé vzory (fantomy), které neodpovídají tréninkovým vzorům. Fantomy je možné odučovat např. pomocí následujícího pravidla: Mějme fantom (x-i,.. .,xn) e {-1,1 }n a váhy Wp, pak nové váhy w'- spočítáme pomocí Wjl = Wfl - XjXj (tj. podobně jako při adaptaci podle Hebbova zákona, ale s opačným znaménkem) Reprodukce - statistická analýza Kapacita Hopfieldovy paměti je dána poměrem p/n. Zde n je počet neuronů a p je počet vzorů. Předpokládejme, že tréninkové vzory jsou voleny náhodně takto: při volbě x k volím postupně (nezávisle) jednotlivé složky (1 s pravd. 1/2 a -1 s pravd. 1/2). Uvažme konfiguraci W, kterou obdržíme Hebbovským učením na zvolených vzorech. Označme p = p[2k=ý{W,)tk)prok = J\,...,P\ Pak pro n —> oo a p < n/(4 log n) dostaneme j3 —> 1. Tj. maximální počet vzorů, které lze věrně uložit do Hopfieldovy paměti je úměrný n/(4 log n). 19 Hopfieldova síť - asociace Problém: ► příliš mnoho vzorů implikuje existenci lokálních minim funkce E, která neodpovídají vzorům (tzv. fantomy) *■ lokální minima pro vzory mohou dokonce zanikat Podrobná analýza ukazuje následující ► Pro p < 0.138n tréninkové vzory zhruba odpovídají lokálním minimům funkce E *■ Pro p > 0.138n lokální minima podobající se vzorům zanikají (ostrá nespojitost v 0.138) ► Pro p < 0.05n energie stavů podobajících se tréninkovým vzorům odpovídají globálním minimům £ a fantomy mají ostře větší energii Tj. pro dobré zapamatování 10 vzorů je potřeba 200 neuronů a tedy 40000 spojů ohodnocených celočíselnými váhami Pozn. Nevýhodou Hopfieldovy sítě je deterministický výpočet, který může skončit v mělkém lokálním minimu £ bez možnosti uniknout. Tento problém částečně vyřeší stochastická verze aktivní dynamiky. 20 Hopfieldova síť - příklad kódování 333 ► číslice 12x10 bodů (120 neuronů, -1 je bílá a 1 je černá) ► naučeno 8 číslic ► vstup vygenerován ze vzoru 25% šumem ► obrázek ukazuje postup výpočtu Hopfieldovy sítě 21 22 23 Hopfieldova síť (pro optimalizační úlohy) Autoasociativní síť. Organizační dynamika: ► úplná topologie, tj. každý neuron je spojen s každým všechny neurony jsou současně vstupní i výstupní ► označme £1,• • •,£„ vnitřní potenciály ay-\,...,yn výstupy (stavy) jednotlivých neuronů ► označme wp celočíselnou váhu spoje od neuronu ;' £ {1,.. . ,nj k neuronu j e {1,.. .,n). *■ přepokládáme Wjj = 0 pro každé j = 1,..., n. ► Nyní: ► každý neuron má bias 9, - stavy neuronů jsou z {0,1} 24 Aktivní dynamika: Iniciálně jsou neurony nastaveny na vstup x = (xi,... ,x„) e {0,1 }n sítě, tedy yf] = x] pro j = 1,..., n. V kroku ř + 1 aktualizujeme neuron j, t. ž. j = (t mod p) + 1, takto: nejprve vypočteme vnitřní potenciál a poté (ř+1) ď} > 0 yf) €j«)=0 I < 0 Hopfieldova síť - aktivní dynamika Výpočet končí v kroku ř* pokud se síť nachází (poprvé) ve stabilním stavu, tj. yf+n) = yf] (i = i.....") Energetická funkce E přiřazuje každému stavu sítě y e {0,1}n potenciální energii danou ^ n n n EW = ~ 2 T T W'iY'yi + T 6iYi y'=1 i=1 /'=1 V průběhu výpočtu se energie nezvyšuje: E(ýW) > E(ý(ř+1)), stav ý(r) odpovídá lokálnímu minimu funkce E. Věta Za předpokladu symetrie vah, výpočet Hopfieldovy sítě skončí pro každý vstup. (Důkaz stejný jako předtím) 26 Hopfieldova síť a optimalizační úlohy Optimalizační úloha je zadána množinou přípustných řešení a účelovou funkcí. Cílem je nalézt přípustné řešení, které minimalizuje účelovou funkci U. Pro mnoho optimalizačních úloh lze nalézt Hopfieldovu síť takovou, že ► minima E « přípustná řešení vzhledem k U ► globální minima E « řešení minimalizující U Cílem je nalézt globální minimum funkce E (a tedy i U). 27 Příklad: multiflop Cílem je nalézt vektor z {0,1 }n, který má všechny složky nulové kromě právě jedné. Definujeme účelovou funkci U : {0,1}n —> JR takto: (( n \ U0) ,/=1 1 Požadované vektory jsou právě minima této funkce. Ale n n 2 .n n a tedy U (ú) - 1 je energetickou funkcí sítě (viz. následující slajd). Příklad: multiflop (síť) Příklad: n věží Cílem je rozmístit n věží na šachovnici n x n tak, aby se vzájemně neohrožovaly. Definujeme účelovou funkci : {0,1}nn —> R: n (( n \ ^ aU2:{0,1] R: n íY n 1 ^ ^(u)=£ -1 i=1 ^y=1 Požadované vektory jsou právě minima funkce U = L/i + L^-Minima U odpovídají stavům s minimální energií v síti na tabuli. Příklad: n věží (síť) E(u) = U{ú) - 2n (Tento příklad se dá zobecnit na problém obchodního cestujícího) Hopfieldova síť a lokální minima Hledáme (globální) minima energie E .... Problém: není jasné, v jakém stavu začít, abychom dosáhli globálního minima. Síť může skončit v mělkém minimu. Řešení: V každém stavu umožníme s malou pravděpodobností přechod do stavů s vyšší energií. Tuto pravděpodobnost budeme postupně snižovat. Využijeme dynamiku Boltzmannova stroje ... 32 „Boltzmannovská" aktivní dynamika Aktivní dynamika: Stavy neuronů jsou iniciálně nastaveny hodnoty z množiny {0,1}, tj. e {0,1} pro j e {1,...,n}. V kroku ř + 1 aktualizujeme náhodně vybraný neuron j e {1,.. . ,n} takto: nejprve vypočteme vnitřní potenciál a poté náhodně zvolíme hodnotu yjt+^ e {0,1} tak, že P [^D = ,]=„(,<')) kde °& = 1 + e-2í/T(t) Parametr T(ř) se nazývá teplota v čase ř. Teplota a energie ► Velmi vysoká teplota 7~(ŕ) znamená, že P[y-t+^ — i] ~ \ a síť se chová téměř (uniformně) náhodně. ► Velmi nízká teplota T(t) znamená, že buď P[y|ř+1^ — i] ~ 1 nebo P[y|ř+1^ = l]«0v závislosti na tom, jestli ^ > 0 nebo S^p < 0. Potom se sít chová téměř deterministicky (tj. jako v původní aktivní dynamice). Poznámky: ► Boltzmannovská aktivní dynamika funguje jako deterministická dynamika s náhodným šumem, ► energie E(ý) = -\£"=i E"=i + L"=i Q M se může (s pravděpodobností závislou na teplotě) zvýšit, pravděpodobnost přechodů do vyšší energetické hladiny se exponenciálně zmenšuje s velikostí energetického skoku. Simulované žíhání Následujícím postupem lze dosáhnout globálního minima funkce E: ► Na začátku výpočtu nastavíme vysokou teplotu T(ř) ► Teplotu postupně snižujeme, např takto: ► r(ř) = i]ř • 7(0) kde i] < 1 je blízko 1 ► nebo 7(ř) = 7(0)/log(1 +0 Lze dokázat, že při vhodném postupu chlazení dosáhneme globálního minima. Pozn: Tento proces je analogií žíhání používané při výrobě tvrdých kovových materiálů s krystalickou strukturou: materiál se nejprve zahřeje, čímž se poruší vazby mezi atomy, v průběhu následného pomalého chlazení se materiál „usadí" do stavu s minimální vnitřní energií a s pravidelnou vnitřní strukturou. ► Jedná se také o rozšíření fyzikální motivace Hopfieldovy sítě: orientace magnetů jsou ovlivněny nejen vnitřním a vnějším magnetickým polem, ale také termálními fluktuacemi.