Omezený Boltzmannův stroj (OBS)
Organizační dynamika:
► Cyklická sít' se symetrickými spoji, neurony jsou rozděleny do dvou skupin:
► V - viditelné
► S - skryté
Množina spoju je V x S (tj. úplný bipartitní graf)
► Množinu všech neuronu znaCíme N
► oznaCme £y vnitřní potenciál a y, výstup (stav) neuronu j
► stav stroje: y e {-1,1}|N|.
► označme Wji váhu spoje od neuronu i k neuronu j.
► obvykle se uvažuje bias, pro zjednodušení jej vynecháme.
Omezený Botzmannúv stroj
Aktivní dynamika: Stavy viditelných neuronů jsou iniciálne nastaveny na hodnoty z množiny {-1,1}.
V f-tém kroku aktualizujeme neurony takto:
► f liché: náhodne zvolíme nové hodnoty skrytých neuronu, pro j e S
► f sudé: náhodne zvolíme nové hodnoty viditelných neuronu, pro j e V
P y(ff = 1 = 1
.(f)
2
Rovnovážný stav
Omezený Boltzmannův stroj se po jisté dobe dostane do termální rovnováhy. Tj. existuje čas t* takový, že pro libovolný stav stroje y* e {-1,1}|N| platí
P [y(t*) = y*] x pN(y*) Zde pn(y*) = Z e-E(y*VT kde
Z = £ e-E(y^'T
ye{—1,1 }INI tj. Boltzmannovo rozložení
Teorie Markovových retezců říká, že P [y(r) = y*] je také dlouhodobá frekvence návštev stavů y*.
Toto platí bez ohledu na iniciální nastavení neuronů! Síť tedy reprezentůje rozložení pN.
3
Omezený Boltzmannův stroj - učení
Pro daný stav viditelných neuronů a e {-1,1 označme
pravděpodobnost stavu viditelných neuronů a v termální rovnováze bez ohledu na stav skrytých neuronů.
Adaptivní dynamika:
Nechť pd je pravdepodobnostní rozložení na množine stavů viditelných neuronů, tj. na {-1,
Cílem je nalézt konfiguraci síte W takovou, že pV odpovídá pd.
Vhodnou mírou rozdílu mezi rozdeleními pV a pd je relativní entropie zvážená pravdepodobnostmi vzoru (tzv. Kullback Leibler distance)
4
Omezený Boltzmannův stroj - učení
S(w) budeme minimalizovat pomocí gradientního sestupu, tj. budeme poCítat poslounost vektoru vah w(0), w...
► váhy v w(0) jsou inicializovány náhodne blízko 0
► v f-tém kroku (zde f = 1,2,...) je w(f) vypoCteno takto:
kde
je zmena váhy w,-, v f-tém kroku a 0 < e(f) < 1 je rychlost uCení v f-tém kroku.
Zbývá spoCítat (odhadnout) ^(w).
5
Omezený Boltzmannův stroj - učení
Lze ukázat, že
MM- W )yír')
dwy/     V>"lfixed    Ví   Ji Ifree
*■ (yíYi)fjxed je prUmerná hodnota yy po jednom kroku výpočtu za předpokladu, že hodnoty viditelných neuronU jsou fixovány dle rozložení pd.
** (y(jt Vf ^)free je prumerná hodnota y(t Vf) v termální rovnováze bez fixace viditelných neuronu.
Problém: výpočet (y(t )y(t ^frgg trvá dlouho (musíme opakovane přivést stroj do termální rovnováhy).
(yf )y(t ^)free se proto nahrazuje (yjyi)recon což je prumerná
hodnota y(3)y(3) za předpokladu, že iniciální hodnoty viditelných neuronu jsou voleny dle pd.
6
Omezený Boltzmannův stroj - učení
Tedy
Awf > = -e(ř) • ((yyy()     - (yyy,))
► (yjYi)fjxed se vypočte takto: Polož Y := 0 a opakuj q krát:
► fixuj náhodne hodnoty viditelných neuronu dle pd
► simuluj jeden krok výpočtu a přičti aktuální hodnotu yy k Y
Pro vhodné q bude Y/q dobrým odhadem (x/X/)^
► (xx)     se vypočte takto: Polož Y := 0 a opakuj q krát:
- nastav náhodne hodnoty viditelných neuronu dle pd
► simuluj třri kroky výpočřtu a přričřti aktuální hodnotu yjyi k Y (tj. vypočtihodnoty skrytých neuronu, potom hodnoty viditelných (tzv. rekonstrukčivstupu) a potom hodnoty skrytýčh)
Pro vhodné q bude Y/q dobrým odhadem yjyi reco
7
Hlúboké síte
Problém: Omezením BS jsme (potenciálne) omezilivyjadrovací sílu. lešení: OBS se skládají nad sebe do tzv. hlubokých sítí
1. OBS se natrénuje na vstupních datech
2. pridá se další vrstva, skryté neurony starého OBS budou nyní uvažovány jako viditelné neurony pro nejvyšší OBS. Natrénuje se nejvyšší OBS
3. iterováním bodu 1. a 2. se přidává více a více vrstev
Na koncidostaneme jednu mnohovrstvou sít', která reprezentuje rozložení na datech. Z tohoto rozložení se dá samplovat takto:
► přived' nejvyšší OBS do termální rovnováhy (to dá hodnoty neuronu v nejvyšších dvou vrstvách)
► propaguj hodnoty do nižších vrstev (tj. proved' jeden krok aktualizace stavu mezilehlých OBS)
► stav neuronu v nejspodnejší vrstve potom bude představovat vzorek dat; pravdepodobnost s jakou se tam objeví konkrétní stav je pravdeřpodností onoho stavu v rozložení reprezentovaném sítí
8
Hlúboké síte - klasifikace
Predpokládejme, že každý vstup patrí do jedné ze dvou tríd. Chceme vstupy klasifikovat pomocí vícevrstvé síte.
Vícevrstvou síť lze trénovat pomocí zpetné propagace. Taje silne závislá na vhodné inicializaci, casto hrozí dosažení melkého lokálního minima apod. Dobre fungující sít si vyvine systém extraktom vlastností (tj. každý neuron reaguje na nejakou vlastnost vstupu). Jak toho dosáhnout?
► Natrénuj hlubokou sít na datech (v této fázi ignoruj příslušnost do tríd)
► Uvažuj výslednou sít jako obycejnou vícevrstvou sít', tj. zamen dynamiku Boltzmannova stroje za sigmoidální aktivacřní funkce a obvyklé vyhodnocení zdola nahoru
► přidej výstupní vrstvu s jedním neuronem
► dolad' sít pomocí zpetné propagace (malá rychlost ucení pro skryté vrstvy, velká pro výstupní vrstvu): Pro vstupy z jedné třrídy uvažujeme ocřekávaný výstup 1 pro ostatní -1.
9
Spojitá Hopfieldova sít'
Organizační dynamika:
► úplná topologie, tj. každý neuron je spojen s každým
► všechny neurony jsou souCasne vstupní i výstupní
► oznaCme ^1 vnitřní potenciály a y1,..., yn výstupy (stavy) jednotlivých neuronu
► oznaCme w,i reálnou váhu spoje od neuronu i e {1,..., n} k neuronu j e {1,...,n}.
► každý neuron j má bias wj0 odpovídající formálnímu jednotkovému vstupu y0 = 1
► přepokládáme wj = 0 pro každé j = 1,..., n.
10
Spojitá Hopfieldova sít'
Aktivní dynamika: Iniciálne jsoů neurony nastaveny navstůp síte x, tedy y(0) = x.
Vývoj stavů síte y(t) je spojitoů fůnkcí casů t > 0, která je dána následůjící soůstavoů diferenciálních rovnic:
Zde t j > 0 jsoů vhodné konstanty, o je spojitá aktivacní fůnkce, napřr.
o(i) = TT"e-Äí Platí, že stavy neůronů jsoů z intervalů (0,1).
dyj
Spojitá Hopfieldova síť
Tvrzení: Sít' konverguje k stavu v němž platí ^ = 0. Definujeme energii pomocí Ljapunovy funkce:
E = " P Tj Tj Wiiyiyi ~Yj Wi0yi + S í    °~1(y)dy 7=1 /=1 7=1 7=1 ^°
Dá se ukázat, že
7=1 x i
Energie E (f) behem aktivního režimu klesá až do chvíle, kdy se sít' dostane do lokálního minima fce E, kde platí d = 0, což
odpovídá ^ = ^ = 0.
Díky poslednímu clenu v definici E jsou stavy splnující ^ = 0 (témer) binární, tj. y ~ 1 nebo y ~ 0.
12
Analýza hlavních komponent (PCA)
Mějme množinu vstupních dat (xi,... ,xp} kde každé x e Rn. j-tou složku vektoru x, budu znaCit Xj.
OznaCme x pruměrnou hodnotu vstupu:
Jednotlivé složky vektoru x budu znaCit Xj. Předpokládejme, že Xj = 0 pro každé j = 1,..., n.
Naším cílem je lineárne transformovat množinu {x1,.. .,xp} na množinu {z1,... ,zp} kde z,- e Rŕ pro i < n.
Tato transformace by mela zachovat „informaCní obsah".
p
P
,=1
13
Analýza hlavních komponent (PCA)
Idea: Pokusme se nalézt smery maximálního rozptylu vstupu (tyto smery by se mely stát osamibáze do níž budeme transformovat vstupy, smery s malým rozptylem budou ignorovány)
Uvažme projekce XiTq vstupu x na fixní vektor q délky 1. Protože x = 0, prumer hodnot xTq je roven 0.
Označme Vq rozptyl vstupů xi ve smeru q:
Nalezneme vektory c1,...,cn e Rn takové, že
► ||C/|| = 1 pro každé i = 1,..., n
► C maximalizuje Vq mezi všemi vektory q, které jsou kolmé na c1,...,ci-1 a mají normu 1.
Zejména c1 maximalizuje rozptyl Vq mezi všemi vektory q s normou 1.
14
Analýza huních komponent (pCA)
Definujeme kovariancní matici C kde Cij = 1L k=1 xkixkj.
Vektor q je vlastním vektorem matice C pokud existuje A > 0 taková, že Cq = Aq
(q je potom vlastní vektor příslušný vlastní hodnote A).
Matice C je reálná a symetrická, má tedy n reálných vlastních hodnot A1 > A2 > • • • > An a ortonormální bázi vlastních vektoru: c1 ,...,cn, tj.
i   j   \0  i + j
► vektor c je vlastním vektorem matice C, který prísluší vlastní hodnoteř Ai
veta
Každé c maximalizuje Vq mezi všemi vektory q, které jsou kolmé na cc1 ,...,ci-1 a mají normu 1.
15
Oznacme C = {c1,...,cn} ortonormální bázi prostorů Rn složenoů z vlastních vektorů kovariancní matice C.
Oznacme Q matici n x n jejíž sloůpce jsoů tvořeny vektory cj, tj.
Q = (c1 • • • cn)   kde vektory c jsoů sloůpcové
Množina vektorů ..., ap}, kde Xj = Qáj, je vyjádřením množiny vstůpů v bázi C. Potom j-tá složka vektorů aj se nazývá j-tá hlavní komponenta vstůpů xj.
Navíc platí:
► QTQ = QQT = I a tedy áj = QTxj
QT je maticí přechodů ze standardní báze prostorů Rn do báze C; všimnete si, že Q je maticí otocení
► ajj = cT • xj, tj. projekce vektorů Xj na osů Cj
► C = QAQT kde A je diagonální matice taková, že Ajj = Aj
16
Redukce dimenze dat
Kovarianční maticí množiny transformovaných vstupu {a1,..., ap} je diagonální matice A kde A,,- = A;. Zejména jsou jednotlivé složky vektorU a, vzájemné nekorelované a rozptyl i-té složky je A;.
Vektor x; e Rn zakódujeme pomocí vektoru z, = (a/i,...,a,t) e R.
VektorZ; = (a;1ai() e Rŕ dekódujeme do vektoru
(0 je prumerná hodnota složek vektoru a; = QTx;).
(pokud jsou hodnoty A(+1,...,An hodne malé, pak 0 dává dobrou aproximaci skutecných souřadnic v bázi C)
n
17
Redukce dimenze dat
Definujeme chybu rekonstrukce vstupu
c     1 Y1 II-    ~ II2
E = 2L||x/ - x/ W
Dá se ukázat, že báze C = {c1,..., cn} minimalizuje chybu E mezi všemi ortonormálními bázemi prostoru Rn.
Navíc platí
n
E = EA'
\=i+i
18
Redukce dimenze dat - kódování
Kódování z Rn do Rr:
Vstup: Množina dat {x1,... ,xp} kde xi e Rn Algoritmus:
1. (Normalizace vstupu odectením prumeru)
2. Výpocet kovariancní matice C
3. Výpocet (aproximace) ortonormální báze C = (Ci,..., cn} vlastních vektoru a transformacní matice Q = (c1 • • • cn)
4. Výpocet vektoru hlavních komponent každého vstupu ai = QTxi kde i = 1,...,p
Výstup: Množina {(ái1,...,áií) | i = 1,...,p} avektory c1,...,c(
19
Redukce dimenze dat - dekódování
Dekódování z Rt do Rn:
Vstup: Množina {z1,... ,zp} kde z, e Rt a vektory c1,...,Ce Algoritmus:
1. Výpocet
t
x, =    ZijCj      pro i = 1,...,p
j=1
Výstup: {X1,...,Xp}
20
Redukce dimenze dat a neuronové sítě
Uvažme vícevrstvou síť n - i - n s lineárními aktivačními funkcemi.
Předpokládejme, že je trénována na množine vzorU
T = {(X,X) | X e Rn,i = 1,...,p} pomocí algoritmu, který minimalizuje chybu
Existuje globální minimum chybové funkce. Dá se ukázat, že po natrénování sít realizuje projekci na podprostor generovaný vektory c1,...,ci (ne nutne ortogonální).
To stejné platí i pro sigmoidální aktivacní funkce ve skrytých neuronech.
p
n
E
21
Redukce dimenze dat a Hebbovské učení
Uvažme jednovrstvou sít' s jedním lineárním výstupním neuronem:
y = I n=i WiXi
a
		/w2j
	ď	O
	Xi	X2
Mejme vstupy T	= {Xi,..	.,Xp}.
Hebbovské učen	í: w(t+1)	= w(t)
O
Xn
Normalizované Hebbovské učení:
w
f n
= (w(ř) + n • y(Xk) • xtó) /1 £ (wf) + n • y(Xk) • xtó)
kde k je voleno uniformne náhodne z {1,...,p}.
22
Redukce dimenze dat a Hebbovské učení
Pro malé n platí
( n 2\5
£ «} + n • y (Xk) • xto)   = i + n • y2(Xk) + O(n2)
což pro malé n dá
= w(t} + n • y(Xk) • (xk/ - y(Xk) • wf}) + O(n2)
tedy ignorováním O(n2) dostaneme
Ojovo pravidlo: w(ř+1) = w(t) + n • y(xk) • (xk/-y(xk) • w(t^ kde k je náhodne vybrané z množiny {1,...,p}.
Tvrzení: Pokud A1 > A2 a An > 0 pak w(ř) konverguje (s pravd.
1) k vlastnímu vektoru c1 kovariaCní matice C
(tj. k vlastnímu vektoru s maximálním vlastním Císlem).
23
Redukce dimenze dat a Sangerovo pravidlo
y1
Q
Ym
O
X1
Xn
Sangerovo pravidlo:
w
(t+1) ji
j
Xki Yt(Xk)
w
kde k je náhodne vybrané z množiny {1,...,p}.
Tvrzení: Pro A1 > • • • > An > 0 a j](t) = { konverguje Wj(t) (s pravd. 1) k vlastnímu vektoru C kovariacní matice C.
24
Nelineární redukce dimenze dat
► Vícevrstvé síte
► sít' n -l - k -l - n, kde n > l > k, se sigmoidálními aktivaCnímifunkcemiprovádí nelineární redukciz Rn do Rk
*■ dolní polovina síte zobrazí vstupy z Rn do Rk
► horní polovina dekóduje z Rk do Rn - uCí se jako autoasociativní sít'
► lze použít i více vrstev - klasická aplikace hlubokých sítí a omezených Boltzmannových strojů
► Kohonenova mapa
► k-rozmerná mapa na datech dimenze n provádí nelineární redukcidimenze dat z Rn do Rk
► Př. Kohonenova mapa jako mřížka k x k. Necht' pro vstup x je aktivní neuron se souřadnicemi(i', j). Vektor x je potom transformován do bodu (i, j).
25