Hopfieldova síť - opakování 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 y-\,..., 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). *■ žádný neuron nemá bias a přepokládáme w# = 0 pro každé j = 1,..., n. Hopfieldova síť - opakování 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 matice W vah 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 -i) = 0 -i í- -i) < 0 Hopfieldova síť - opakování 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. Dokážeme později pomocí energetické funkce. 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 y(W,x) = (y|ř \...,y^) hodnotu funkce sítě pro vstup x a matici vah W. Pokud bude W jasné z kontextu, budu psát jen y(x). Energetická funkce - opakování Energetická funkce E přiřazuje každému stavu sítě ý e {-1,1}n potenciální energii danou ► velké (kladné) w/yy-y je stabilní a malé (záporné) w/;yy nestabilní stavy s nízkou energií jsou relativně stabilní (málo neuronů „chce" změnit svůj stav), stavy s vysokou energií jsou nestabilní V ideálním případě Hebbovo učení zakóduje vzory jako (globální) minima funkce E. 5 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)) 6 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) 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). 10 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ě 12 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 ... 13 Boltzmannův stroj 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: Sestrojíme generalizaci Hopfieldovy sítě, jejíž stavy budou z množiny {-1,1}n a která bude svoje stavy měnit náhodně (podle přechodových pravděpodobností daných konfigurací sítě). Když takovou síť necháme běžet dost dlouho, 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í reprezentované sítí. 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é sítí bude odpovídat zadanému rozložení. 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. 15 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. 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í 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í p^. P =/]*pN(/) Zde pN(y*) = le-£(y*)/Tkde 19 Boltzmannůuv 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 20 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) 21 Boltzmannůuv 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: 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). .(f-1) kde 22 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 yj* ^ 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ě 23 Boltzmannův stroj - učení Pro upřesnění: / (n (m = \ ' Ji /fixed - L "<«> L p-^yfyf «£{-1,1)1^1 /Se{-1,1}isi Hvy ' kde y0^ je výstup neuronu j ve stavu (a,/3). ye(-1,1)lNl 24 Boltzmannův stroj - učení Výpočet Awjj lze realizovat pomocí simulace. 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 tak dlouho, dokud nedosáhne termální rovnováhy při nízké teplotě (zde je možné použít tzv. simulované žíhání, tedy pomalé snižování teploty). 3. simuluj stroj po dalších £ kroků a v každém z těchto kroků přičti aktuální hodnotu yyy,- k proměnné J/. ► y/q£ bude dobrým odhadem (y^ V-ř ^)ftxed za předpokladu, že q a l jsou dostatečně velká čísla. (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). 25