ADALINE Organizační dynamika: y X! X2 Xn w = (wQ/w^...,wn) aX = (xo,x^...,xn) kde x0 = 1. Aktivní dynamika: ► vnitřní potenciál: í, = w0 + X,"=1 w,x; = L[Lo w/x/ = w • X ► aktivační funkce: o(£,) = £ ► funkce sítě: y[w](x^,...,xn) = o(£.) = w-X ADALINE Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {[^ld^l(x2ld2),...l(xpldp)} Zde xk = (x/ 2 Z. Cílem je nalézt w, které minimalizuje E(w). ADALINE - adaptivní dynamika Dávkový algoritmus (gradientní sestup): ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku je vypočteno takto: tf(0 = tf(ř-1)-£-VE(w(ř-1)) - *M,-<-(£(*).....n<*> = tf«-1)_£.£ (Ä(M). X(,- 0 posloupnost w(°\ w(2\... konverguje (po složkách) ke globálnímu minimu funkce E (tedy k vektoru w, který splňuje VE(vv) = Oj. ADALINE - statistické učení Uvažme následující modifikaci adaptivní dynamiky: ► Síti je předkládána (nekonečná) posloupnost tréninkových vzorů (x-\,d-i),(x2,d2),... kde ► vstupy xk — (Xfci,..., xkn) e R" jsou generovány náhodně s daným rozdělením pravděpodobností ► každý vstup xk má přiřazen požadovaný výstup dk e IR. ► Označme Xk = {xk0,xk^,.. .,xkn) kde xk0 = 1. Výstup sítě pro k-tý vzor'\e potom w ■ Xk. ► Pro danou konfiguraci w definujeme chybu: Poznámka: Podle zákona o velkých číslech je E(w) střední hodnota proměnné, která vrací \ (w ■ Xk - dk} , tedy E(w) = E \ (w ■ Xk - dk)j ADALINE - statistické učení Vypočteme gradient VE(vfr) = (ij^{w),...,j^n{w)) : ^-(w) = lim - • Y (w ■ Xk - dk) ■ xki n = ^ Wr • /V/ - C; r=0 kde A - 1 " n = lim - • V xkr ■ xki 1 p C, = lim - • Y dk ■ xki ADALINE - statistické učení Hledáme minimum E(w), tedy w* takové, že VE(vv*) = 0. Pokud dokážeme statisticky odhadnout Arj a C, pak můžeme rovnou položit: a dostat w* jako řešení systému lineárních rovnic. Problémy: 1. řešení nemusí existovat (přestože minimum funkce E vždy existuje) 2. nemusíme mít odhad pro Arj a C, Pokud lze odhadnout Ar; a Q, můžeme použít gradientní sestup stejně jako v případě normálního ADALINE učení: ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku (zde ř = 1,2,...) je vypočteno takto w (0 w (t-1) p w (f-1) _ £ • lim p—>« (f-1) 1 Vr=0 Co když ani nelze odhadnout Ar; a C, ? ADALINE - statistické učení Naštěstí funguje online algoritmus (Widrow & Hoff), který je úplně stejný jako v předchozí „nestatistické" variantě! ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku (zde ř = 1,2,...) je vypočteno takto: ^ř) = ^ř-1)-£(ř)-(^ř-1)-xř-dř)-xř kde 0 < e(t) < 1 je rychlost učení v ř-tém kroku. Věta (Widrow & Hoff) Pro e(t) = j posloupnost w(°\ w(2\... konverguje ke globálnímu minimu chybové funkce E(w). Matematická poznámka: zde se nejedná o konvergenci po složkách, ale o konvergenci průměru čtverců vzdálenosti (mean square convergence). 8 Vícevrstvá síť a zpětná propagace ► Vícevrstvé sítě - značení ► učící pravidlo zpětné propagace ► algoritmus zpětné propagace Vícevrstvá síť Organizační dynamika: Výstupní Q O Skryté Vstupní Neurony jsou rozděleny do vrstev (vstupní a výstupní vrstva, obecně několik skrytých vrstev) Vrstvy číslujeme od 0; vstupní vrstva je nultá ► Např. třívrstvá síť se skládá z jedné vstupní, dvou skrytých a jedné výstupní vrstvy. Neurony v i-\é vrstvě jsou spojeny se všemi neurony ve vrstvě l + 1. Vícevrstvou síť lze zadat počty neuronů v jednotlivých vrstvách (např. 2-4-3-2) 10 Vícevrstvá síť Značení: ► Označme ► X množinu vstupních neuronů ► Y množinu výstupních neuronů Z množinu všech neuronů (tedy X, Y c Z) ► jednotlivé neurony budeme značit indexy i, j apod. ► £y je vnitřní potenciál neuronu j po skončení výpočtu ► y j je stav (výstup) neuronu j po skončení výpočtu (zde definujeme y0 = 1 jako hodnotu formálního jednotkového vstupu) ► Wjj je váha spoje od neuronu ;' do neuronu j (zejména wj0 je váha speciálního jednotkového vstupu, tj. wj0 = -b; kde bj je bias neuronu j) ► y«_ je množina všech neuronů, z nichž vede spoj do j (zejména 0 e y<_) ► y-_> je množina všech neuronů, do nichž vede spoj z j 11 Vícevrstvá síť Aktivní dynamika: ► vnitřní potenciál neuronu j: ti=E wJiYi *■ aktivační funkce a j pro neuron y je libovolná diferencovatelná funkce [ např. logistická sigmoida a/(£) = 1 J-a^ ] ► Stav nevstupního neuronu j e Z \ X po skončení výpočtu je (yy- závisí na konfiguraci w a vstupu x, proto budu občas psát y,{w,x)) *■ Síť počítá funkci z R|X| do R|Y|. Výpočet probíhá po vrstvách. Na začátku jsou hodnoty vstupních neuronů nastaveny na vstup sítě. V kroku i jsou vyhodnoceny neurony z i-lé vrstvy. 12 Vícevrstvá síť Adaptivní dynamika: ► Dána množina T tréninkových vzorů tvaru {(xkldk) | 1^ = },...^] kde každé xk e IR|X| je vstupní vektor a každé dk e IR|y| je očekávaný výstup sítě. Pro každé j e Y označme dkj očekávaný výstup neuronu j pro vstup xk (vektor dk lze tedy psát jako (cfo/) ). ► Chybová funkce: p E(Ú) = YJEk(Ú) kde jeY 13 Vícevrstvá síť - učící algoritmus Dávkový algoritmus (gradientní sestup): Algoritmus počítá posloupnost 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. Všimněte si, že je komponenta gradientu VE, tedy změnu vah v f-tém kroku lze zapsat také takto: w(í) = - £(f) • VE(w(M)). .(f-1) kde Aw{t) = -e(t)-^-(w^) 14 Vícevrstvá síť - gradient chybové funkce Pro každé w,, máme — - V — dwii ~ J3 5w/v kde pro každé k = 1,..., p platí a pro každé j e Z\X dostaneme — =yj-dkj proyeY d-Ě = L^-^)-n ProyeZx(Y (Zde všechna y; jsou ve skutečnosti yj(w,xk)). Vícevrstvá síť - gradient chybové funkce ► Pokud a/(£) = 1 J-Ajč Pro každé j e Z pak a dostaneme pro každé j e Z\X: — =yj-dkj proyeY ^ = E§7L-^yr(1-yr)-wfí- proyeZ\(YuX) ► Pokud a/(£) = a • tanh(r> • £y) pro každé y e Z pak Vícevrstvá síť - výpočet gradientu Algoritmicky lze J| = LjJ=1 §§J spočítat takto: Polož Sjj := 0 (na konci výpočtu bude £/,- = Pro každé k = 1,... ,p udělej následující 1. spočítej y, pro každé j e Z a k-lý vzor, tedy y, = yj{w,Xk) (tj. vyhodnoť síť ve standardním aktivním režimu) 2. pro všechna j e Z spočítej ^ pomocí zpětného šíření (viz. následující slajd!) 3. spočítej ^| pro všechna w,, pomocí vzorce fay — + Výsledné Ey; se rovná Vícevrstvá síť - zpětné šíření ^ lze spočítat pomocí zpětného šíření: ► spočítáme ^ pro j e V pomocí vzorce ^ = y,- - ► rekurzivně spočítáme zbylé ^-: Nechť j je v £-té vrstvě a předpokládejme, že ^ už máme spočítáno pro všechny neurony z vyšších vrstev (tedy vrstev i+ 1,^ + 2,...). Pak lze ^ spočítat pomocí vzorce 5Efc ví dEk protože všechny neurony r e y-_> patří do vrstvy £ + 1. Složitost dávkového algoritmu Výpočet hodnoty Jf:(w(ř~1)) probíhá v lineárním čase vzhledem k velikosti sítě a počtu tréninkových vzorů (za předpokladu jednotkové ceny operací včetně vyhodnocení a'r(£r) pro dané £r) Zdůvodnění: Algoritmus provede p krát následující 1. vyhodnocení sítě (tj. výpočet y}(w,x^)) 2. výpočet ^ zpětným šířením 3. výpočet §jj 4. přičtení §| k Gji Kroky 1.-3. proběhnou v lineárním čase a krok 4. v konstantním vzhledem k velikosti sítě. Počet iterací gradientního sestupu pro přiblížení se (lokálnímu) minimu může být velký... 19 Vícevrstvá síť - učící algoritmus Online algoritmus: Algoritmus počítá posloupnost 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: kde ji v; dwj-r 11 kde k = ((ŕ - 1) mod p) + 1 a 0 < e(t) < 1 je rychlost učení v ř-tém kroku. Lze použít i stochastickou verzi tohoto algoritmu, v níž je k voleno náhodně z {1,.. .,p}.