Lineární asociativní síť ► Lineární asociativní síť (LAS) ► Hebbův zákon ► Učení LAS podle Hebbova zákona ► Pseudohebbovská adaptace LAS Asociativní sítě - obecně 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. V připadě tvz. autoasociativnísítě předpokládáme Xk = dk- 2 Lineární asociativní síť - matice Označme x = • *■ váhy tvoří matici W danou ^11 ••• wAn\ W mnj Aktivní dynamiku potom lze zapsat takto: Ym) W-x Občas budu psát jen ý(x) pokud bude W jasné z kontextu. LAS - adaptivní dynamika Dána množina T tréninkových vzorů tvaru {(xkldk) | 1^ = },...^] (xkA kde každé xk je vstupní vektor a každé dk y^kn, očekávaný výstup sítě. dkm, je V případě autoasociativní paměti předpokládáme dk = xk pro k = 1,...,p. Cílem je nalézt váhy W takové, že dk = ý(W,xk) = W ■ xk. Adaptace podle Hebbova zákona Hebbův zákon: When an axon of cell A is near enough to excite 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 „The 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. Hebbovská adaptivní dynamika LAS Počítáme posloupnost matic vah W(°), kde 0 -1 l < 0 funkce není identita, ale Předpokládejme, že £ j-1,1|"a4 e {-1,1}m. Pak hodnota funkce sítě pro r-tý vzor je ý{xr) = sgn(Wxr) = sgn cřf + ^ dkj^f7\ k+r \Xrxr)/ Nyní dk = y{Xk) pro každé k pokud < 1 (tato hodnota se nazývá přeslech) kázka LAS s nelineární aktivací Experiment: vzorové vektory z {-1,1 }10 byly postupně ukládány Hebbovským učením. Poté byl síti předložen nový vektor a očekávala se jeho asociace s nejbližším vzorovým vektorem vzhledem k Hammingově vzdálenosti. ► po každém uložení vzorového vektoru byla síť otestována na velkém množství vektorů, jejichž Hamingova vzdálenost od vzorů byla 0-4. ► tabulka udává procento správně asociovaných vektorů z dané H. vzdálenosti od některého vzoru (řádky) ve chvíli, kdy síť byla naučena daný počet vzorů (sloupce) II 1 2 3 4 5 6 7 8 9 10 0 100.0100.0100.0100.0100.0100.0100.0100.0100.0100.0 1 100.0100.0 90.0 85.0 60.0 60.0 54.3 56.2 45.5 33.0 2 100.0 86.7 64.4 57.2 40.0 31.8 22.5 23.1 17.0 13.3 3 100.0 50.0 38.6 25.4 13.5 8.3 4.8 5.9 3.1 2.4 4 100.0 0.0 9.7 7.4 4.5 2.7 0.9 0.8 0.3 0.2 Pseudohebbovská adaptace ► Alternativní způsob učení LAS ► Nevyžaduje ortonormalitu vzorů (jen lineární nezávislost) ► Poněkud se vzdaluje od biologické motivace Pseudohebbovská adaptace Uvážíme autoasociativní případ: T = {(xklxk) | k = 1,...,p} Předpokládejme, že množina {xi,...,xp} je lineárně nezávislá. Potom p < n a {xi,... ,xp} je bází vektorového prostoru Vp, který je podprostorem Rn. Idea: Během adaptace budeme postupně konstruovat ortogonálníbáz\ {z-i,...,zp} prostoru Vp pomocí Gram-Schmidtova ortogonalizačního procesu. 15 Pseudohebbovská adaptace Počítáme posloupnost matic vah W(°), \A/(p\ ► Na začátku nastav = 0. p ► V /c-tém kroku (zde k = 1,..., p) je síti předložen /c-tý vzor a váhy se adaptují takto: W{k) = W(k-:) + ZkZi zTkzk Pseudohebbovská adaptace - reprodukce Označme výslednou matici Chceme Wxk = xk pro každé k = 1,... ,p. Tvrzení {z-i,..., Zfc} je ortogonální bází vektorového prostoru Vp (tj. prostoru s bází{x-\,...,xk}). Důsledek Pro x e Vp platí Wx = x. Zejména Wxk = xk, tedy síť má schopnost reprodukce. 17 Pseudohebbovská adaptace - asociace Uvažme vstup: xr + ú kde norma je malá. Chyba sítě pro r-tý vzor perturbovaný vektorem u: Er(ů) = ||ý(xr + u)-xr|| = \\Wxr + Wů-xr\\ = || UVl7|| Pak pro každé r = 1,..., p platí Er{ú) < n\\ú\\ Tedy pro vstupy blízké vzorům síť odpovídá přibližně požadovaným výstupem. 18 Pseudohebbovská adaptace - pseudoinverze W(p) = XX+ kde X+ = (XTX)-1XT je Moore-Penroseova pseudoinverze matice X. Matice (XTX)~1 existuje, protože jsou sloupce matice X lineárně nezávislé. Matice W = XX+ je řešením rovnice WX = X (tj. přesně problém autoasociace) 19 Pseudohebbovská adaptace - heteroasociativní Uvážíme heteroasociativní případ: T = {(xk,dk) | k = l,...,p) Předpokládejme, že množina {xi,...,xp} je lineárně nezávislá. Hledáme matici W takovou, že pro k = 1,.. . ,p platí Wxk = dk-Tj. WX = D kde X = • D = 'Cřn • • cřPr • xpn/ dpm, Matice W = DX+ = D{XTX)~^XT řeší rovnici l/l/X = D 20 Pseudohebbovská adaptace - heteroasociativní Poznámka: Problém asociace lze řešit, i když XTX není invertibilní (tj. bez předpokladu nezávislosti {xi,...,xp}). Vždy existuje unikátní matice (tzv. pseudoinverze), která splňuje následující: ► XX+X=X *> X+XX+=X+ ► X+X a XX+ jsou symetrické Matice W = DX+ potom minimalizuje m p \\WX - D||2 = £ Ypj{W,5tk) - dkj)2 y'=1 fc=1 Tedy matici W lze počítat pomocí gradientního sestupu. Pseudohebbovská adaptace - heteroasociativní W lze počítat také pomocí pseudohebbovské adaptace. Počítáme dvě posloupnosti matic vah W'^, W'^ a ► Na začátku nastav = 0. p ► V /c-tém kroku (zde k = 1,..., p) je síti předložen /c-tý vzor a váhy se adaptují takto: *fc = jřfc-w.jřfc zjz, Výsledná matice je W = W^p\ Tj. zk se počítají v autoasociatvnísíti a poté se použijí k výpočtu tV(k) Hopfieldova síť ► Definice Energetická funkce 23 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 yi,..., yn 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. 24 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. Poznámka: Stav y^ neuronu j odpovídá opačnému znamínku gradientu E v bodě ý(ř"1): fg(ý(ř_1)) = - L"=1 vty-yj .(f-i) 29 Energetická plocha