Autoasociativní sítě - obecně Cílem je uchovat množinu vzorů {Xk \ k = ],...,p] tak, aby platilo následující: Po předložení nového vstupu x, který je „blízko" některému bude výstup sítě roven Xk. Zejména by síť měla mít schopnost reprodukce: Pro vstup Xk by měla dát výstup Xk- 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). *■ žá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 (stejně 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 E(ý(ŕ+1)), stav ý(r) odpovídá lokálnímu minimu funkce E. 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)) 10 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(/ř"1)) > E(>W) pokud dojde v kroku ř ke změně stavu, pak E(y(ř"1)) > E(yW) ► 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) 12 Hopfieldova sít - reprodukce Matice všech vah v síti W je dána W = Yfk^ > oo a p < n/(4 log n) dostaneme j3 —> 1. Tj. maximální počet vzorů, které lze uložit do Hopfieldovy paměti je úměrný n/(4 log n). 14 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 odpovídají lokálním minimům funkce E ► Pro p > 0.138n lokální minima příslušející vzorům zanikají ► Pro p < 0.05n tréninkové vzory odpovádají globálním minimům E 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 (autorovi knihy z roku 1996 to připadalo nepříliš praktické :-)) Pozn. Nevýhodou Hopfieldovy sítě je deterministický výpočet, který může skončit v mělkém lokálním minimu E bez možnosti uniknout. Tento problém částečně vyřeší Boltzmannův stroj -stochastické rozšíření Hopfieldovy sítě. 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ě 16 17 18 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. Pro mnoho optimalizačních úloh lze nalézt Hopfieldovu síť (obvykle je nutné přidat biasy) takovou, že energetická funkce E = účelová funkce ► minima E « přípustná řešení Cílem je nalézt globální minimum funkce 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. Tohoto je schopen Boltzmannův stroj, viz. dále ... 19 Boltzmannův stroj 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. 20 Botzmannův stroj 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 a poté náhodně zvolíme hodnotu yj^ e {-1,1} tak, že P[y/ř) = l] = a(^-1)) kde a& = 1 + e-zí/rw Parametr T(ř) se nazývá teplota v čase ř. Boltzmannův stroj - teplota a energie ► Velmi vysoká teplota T(ř) znamená, že P [yí^ = 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 ép > 0 nebo E,p < 0. Potom se stroj chová téměř deterministicky (tj. jako Hopfieldova síť). Podobně jako u Hopfieldovy sítě definujeme energetickou funkci E jeN iej^ Boltzmannův stroj funguje jako Hopfieldova síť rozšířená o náhodný šum na přechodech, tj. energie se může občas 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.