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. i 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 ► Velmi vysoká teplota T(ř) znamená, že P [yp = 1J « ^ 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}|N|. 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í. Rovnovážný stav Fixujme teplotu T (tj. T(ř) = T pro ř = 1,2,...). Boltzmannův stroj se po jisté době dostane do tzv. termální rovnováhy. Tj. existuje čas ť takový, že pro libovolný stav stroje y* e {-1,1}|N| a libovolné ř* > ť platí, že PN(7):=P[y(r)=y] splňuje Pw(y*) ~ 2e~£^/T kde Z= £ e-W E(7) = _^^yryr ye(-1,1)lNl y 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^. 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 divergence) «£(-1,1)1^1 Pd{a) pv{a) Boltzmannův stroj - učení £(w) budeme minimalizovat pomocí gradientního sestupu, tj. budeme počítat poslounost matic vah \A/(°\ ... ► váhy v jsou inicializovány náhodně blízko 0 ► v í-lém kroku (zde l = 1,2,...) je vypočteno takto: kde AlVW = _řM.^(w/(M)) J' y ' dWjjy ' je změna váhy w,, v £-tém kroku a 0 < e(£) < 1 je rychlost učení v &\érr\ kroku. Zbývá spočítat (odhadnout) 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 (yj* Vf ^)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ů 3. přičti aktuální hodnotu yj* V,-ř ^ 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). Boltzmannův stroj - uče Pro upřesnění analytická verze: