Perceptron a ADALINE ► Perceptron ► Perceptronové učící pravidlo ► Konvergence učení perceptronu ► ADALINE ► Učení ADALINE 1 Perceptron Organizační dynamika: y x0 = 1 —HTj \N\ / W2 O o X! X2 'O Aktivní dynamika: ► vnitřní potenciál: £ = w0 + L/Li w,-x/ = ^/Lo W/X/ = w • x aktivační funkce: a(£) = 11 ^ " °' 0 £<0. funkce sítě: y[w](x) = o(£) = c j (vv • x) Perceptron Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {(x1/di)/(x2/d2)/.../(xp/dp)} Zde xk = (xk0, x/c1..., xkn) e Rn+1, x^o = 1, je vstup /c-tého vzoru a d/c g {0,1} je očekávaný výstup. (ok určuje, do které ze dvou kategorií dané xk = {xk0/x^ . ..,xkn) patří). ► Vektor vah w e Rn+1 je konzistentní s T pokud y[w](x/() = o{w • xk) = dk pro každé k = 1,.. .,p. Množina T je vnitřně konzistentní pokud existuje vektor w, který je s ní konzistentní. ► Cílem je nalézt vektor vv5 který je konzistentní s T za předpokladu, že T je vnitřně konzistentní. Perceptron - adaptivní dynamika Online učící algoritmus: Idea: Cyklicky prochází vzory a adaptuje podle nich váhy, tj. otáčí dělící nadrovinu tak, aby se zmenšila vzdálenost špatně klasifikovaného vzoru od jeho příslušného poloprostoru. Prakticky počítá posloupnost vektorů vah w(°\ w^2\.... ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: Zde k = (ř mod p) + 1 (tj. cyklické procházení vzorů) a 0 < e < 1 je rychlost učení. Věta (Rosenblatt) Jestliže je T vnitřně konzistentní, pak existuje ľ takové, že je konzistentní s T. w 4 Důkaz Rosenblattovy věty Pro zjednodušení budeme dále předpokládat, že e = 1. Nejprve si algoritmus přepíšeme do méně kompaktní formy ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: ► Jestliže (j(w(r) • Xk) = ck, pak w(ŕ+1) = w(ř) ► Jestliže • xk) ± dk, pak ► Ň/(ř+1) = w(ř) + xk pro c/k = 1 ► w(ř+1) = w(f) - xk pro dk = 0 (Řekneme, že nastala korekce.) kde k = (ř mod p) + 1. Důkaz Rosenblattovy věty (Pro daný vektor a = (a0,..., an) označme normu Va • a = ylXo af) a jeho eukleidovskou Idea: Uvážíme hodná dlouhý vektor (spočítáme jak dlouhý) w*, který je konzistentní s T. Ukážeme, že pokud došlo v kroku t + 1 ke korekci vah (tedy buď w(ř+1) = w(ř) + xk nebo w(ř+1) = w(ř) - x/<), pak < ^(0 max X, Všimněte si, že max / Xi > 0 nezávisí na t. ► Z toho plyne, že algoritmus nemůže udělat nekonečně mnoho korekcí. Důkaz Rosenblattovy věty Uvažme vektor w* konzistentní s T. Búno předpokládejme, že w* • xk ž 0 pro k = 1,..., p. Předp., že v kroku ř + 1 došlo ke korekci, a že k = (ř mod p) + 1 Ukážeme, že w < w (0 _ + 2i -> \W • Xfc (Potom bude k důkazu věty stačit nahlédnout, že pro "dlouhý" vektor w* je \w* - xk\ "velké" kladné číslo.) Rozlišíme dva případy: dk = 1 a 4 = 0. Důkaz Rosenblattovy věty Předpokládejme dk = 1 : Došlo ke korekci, tedy w(ř+1) = vv(ř) + xk a tedy = (vř(0-vř*) + 4. Pak 2 1/1/ = I -w) + xk\ i2 - [ - w*) + xk] - vř*) + i4] - I 2 1 +1 \*k\ |2 + 2(i#ř> - #*) • j?fc — - vř*) 2 + Xk 2 + 2vr<ř> • j?fc - 2& < -w*) 2 + 2 -2\w*-xk\ Poslední nerovnost plyne z toho, že: ► došlo ke korekci při dk = 1, tedy muselo platit • < 0, ► w* je konzistentní s T a tedy w* • i4 > 0. 8 Důkaz Rosenblattovy věty Předpokládejme dk = 0 : Došlo ke korekci, tedy w(f+1) = wW - xk a tedy = (wM-w*)-xk. Pak - w" = I - IV ) -•&| i2 -1 -#)• - w*) - 4] - I 2 i + 1 |xřc| i2 2(vv(f) - vř*) • x,, — 2 + Xk 2 2w<ř' • xk + 2w* < 2 + Xk 2 2\w*-xk\ Poslední nerovnost plyne z toho, že: ► došlo ke korekci při dk = 0, tedy muselo platit • xk > 0, ► w* je konzistentní s T a tedy w* • i4 < 0. Důkaz Rosenblattovy věty Máme dokázáno w (f+i)_tf» < + Xk -2\w*-xk Nechť nyní w* = a ■ w+ kde a > 0. Pak Iv < + 2i -»4- -» • xk Nyní stačí uvážit a max/c x/< miriff |w+-Xfc| a dostaneme 21 -»4- ^ i ^ a|w+-X/c| < -2 max i -> i 2 W+-X/< -- ^ < min/c |w+ • x/c Což dá w < tf<ř> - vř- - max kdykoliv došlo ke korekci. Z toho plyne, že nemůže dojít k nekonečně mnoha korekcím, Perceptron - adaptivní dynamika Davkový ucici algoritmus: Vypočte posloupnost w(°\ w^2\... váhových vektorů ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: v^+1) = v^) - £-f^{o{Ú^-Žk)-dk)-Žk /c=1 Zde k = (t mod p) + 1 a 0 < e < 1 je rychlost učení. Organizační dynamika: w= (wo,wi,...,wn) ax = (xo,xi,...,xn) kde x0 = 1. Aktivní dynamika: ► vnitřní potenciál: l = w0 + £"=1 w-,Xj = E/Lo w;x; = w • x ► aktivační funkce: a(£) = £ ► funkce sítě: y[w](x) = o{E) = w • x 12 ADALINE Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {(x1/di)/(x2/d2)/.../(xp/dp)} Zde xk = (xk0, x/c1..., xkn) e Rn+1, x^o = 1, je vstup /c-tého vzoru a dk e IR je očekávaný výstup. Intuice: chceme, aby síť počítala afinní aproximaci funkce, jejíž (některé) hodnoty nám předepisuje tréninková množina. Chybová funkce: 1 p 2 1 p ( n \ /c=i fc=i v/=o y Cílem je nalézt w, které minimalizuje E(w). Gradient chybové funkce Uvažme gradient chybové funkce: Intuice: VE(w) je vektor ve váhovém prostoru, který ukazuje směrem nejstrmějšího „růstu" funkce E(w). Vektory xk zde slouží pouze jako parametry funkce E(w) a jsou tedy fixní! Fakt Pokud VE(w) = 0 = (0,..., 0), pak w je globální minimum funkce E. Námi uvažovaná chybová funkce E(w) má globální minimum, protože je konvexním paraboloidem. 14 Pozor! Tento obrázek pouze ilustruje pojem gradientu, nezobrazuje chybovou funkci E(w) Gradient chybové funkce ADALINE 1 P ôE ( n f pL^: LWiXki~dk 2 f-1 óWí , . fc=i c V/=o " 5Eín fc=1 v/=o p /n /c=1 WjXki - dk ?L2 Zw,xto"dfc Z V/=0 V/=o V/=0 (ÔE ÔE -dk)xki k=\ Tedy VE(w) ADALINE - adaptivní dynamika Dávkový algoritmus (gradientní sestup): ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: vr(ř+1) = vř(0-£.VE(vřW) p /c=1 Zde /c = (ř mod p) + 1 a 0 < e < 1 je rychlost učení. (Všimněte si, že tento algoritmus je téměř stejný jako pro perceptron, protože w(ř) • xk je hodnota funkce sítě (tedy cr(w(ř) • xk) kde o(£) = £)■) Tvrzení Pro dostatečně malé £ > 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(w) = 0). 17 ADALINE - adaptivní dynamika Online algoritmus (Delta-rule, Widrow-Hoff rule): ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: V^+1) = tf(0 - £(ř) ' (tfW ' 4 - Cfc) ' Xk kde /c = t mod p + 1 a 0 < e(t) < 1 je rychlost učení v kroku t + 1. Všimněte si, že tento algoritmus nepracuje s celým gradientem, ale jenom s jeho částí, která přísluší právě zpracovávanému vzoru! Věta (Widrow & Hoff) Pokud t(t) = j pak w(°\ w^2\... konverguje ke globálnímu minimu chybové funkce E. ADALINE - klasifikace ► Množina tréninkových vzorů je T = {(x1/di)/(x2/d2)/.../(xp/dp)} kde x/c = (XfrOxXfM,...^) e Rn+1 adke {1,-1}. ► Síť se natrénuje ADALINE algoritmem. ► Očekáváme, že bude platit následující: ► jestliže dk = 1, pak w • xk > 0 jestliže dk = -1, pak vv • xk < 0 ► To nemusí vždy platit, ale často platí. Výhoda je, že se ADALINE algoritmus postupně stabilizuje i v neseparabilním případě (na rozdíl od perceptronového algoritmu). 19 ADALINE Organizační dynamika x0 = 1 X1 x2 w= (w0,wu...,wn) ax = (xcx^-.^Xn) kdex0 = 1 Aktivní dynamika: funkce sítě: y[w](x) = w • x 20 ADALINE Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {(x1/di)/(x2/d2)/.../(xp/dp)} Zde xk = (xk0, x/c1..., xkn) e Rn+1, x^o = 1, je vstup /c-tého vzoru a dk e IR je očekávaný výstup. Intuice: chceme, aby síť počítala afinní aproximaci funkce, jejíž (některé) hodnoty nám předepisuje tréninková množina. Chybová funkce: 1 p 2 1 p ( n \ /c=i fc=i v/=o y Cílem je nalézt w, které minimalizuje E(w). Dimenze n = 1 Dále budeme uvažovat pouze n = 1. Hodnota sítě pro daný vstup (1,x-i) bude w0 + w/1x1 Tedy množina tréninkových vzorů T = {(x1/d1)/(x2/d2)/.../(xp/dp)} splňuje 4 = (Uid)elR2adi(GlR Zjednodušíme si notaci a budeme předpokládat T = {(x1/di),.../(xp/dp)) kde x/c g IR a d/c g IR pro /c = 1,..., p. Hodnota sítě s váhami w0, wi pro Ac-tý vzor bude w0 + w^Xk. Chybová funkce pro n = 1 1 p E(w0, wi) = - J^ÍWq + wixk- dky Minimalizujeme E vzhledem k w0 a wi: SE n z, - z, -- = 0 <=> Wn = Cl - W-i X <=> O = Wn + W-i X kde x = l £jj=1 x* a ď = J L{J=1 cfc <5E i lLi (d* _ d)(x* _ *) -- =0 <=> Wi = -:----- (tj. Wi = cov(cf,x)/var(x)) Normální rozdělení pravděpodobnosti Rozdělení spojité náhodné veličiny (tj. s hodnotami v R) Hustota pravděpodobnosti ř(x> = ^expf^) == n["'°2i(x) \i je střední hodnota, a2 rozptyl Pokud má náhodná veličina X normální rozdělení, pak Jrx2 Často se používá k vyjádření náhodné chyby, např. chyby měření, způsobené velkým počtem neznámých a vzájemně nezávislých příčin. Normální rozdělení pravděpodobnosti Věrohodnost (likelihood) Fixujme T = {{xi,di),{x2,d2),...,(xp,dp)} Předpokládejme, že dk bylo vygenerováno náhodně takto dk = w0 + WiXfc + ejc Zde ► w0, wi jsou neznámé konstanty ► €k jsou generována náhodně s hustotou pravděpodobnosti N[0, a2] kde a2 je neznámý rozptyl Snadno se ukáže, že hustota pravděpodobnosti, se kterou je vygenerováno dk splňuje p(dk | w0,wi,o2) = N[w0 + wixk,(r](dk) Předpokládejme, že pro fixní w0, wi,o2 jsou e\,...,ep generována nezávisle. Pak hustota pravděpodobnosti, se kterou jsou vygenerována všechna d\,...,d9 splňuje p p(di,...,dp | w0/wi, w0,wi,o2 maximalizují log(í_(w0, w-i,tf2)) Maximální log-věrohodnost (log-likelihood) Ukážeme, že log(L(w0, , a2)) = -- log 2n - p log a - — Wi x/< /c=1 a tedy pro každé a2 w0/Wi maximalizují L(w0/ w-|,(j2) <^> Wo, wi maximalizují log(L(w0,w-^a2)) <^> w0,w-i minimalizují E(w0,w-i) Tj. maximalizující w0, wi nezávisí na a2. Maximalizujeme-li vzhledem k a2, dostaneme 1 p -J^idk-Wo-wiXk)2 P /c=1 CT2 = (tj. průměrná čtvercová odchylka od žádaných hodnot dk, jak se dalo čekat) Věrohodnost (likelihood) - libovolná dimenze dat Fixujme T = {(x1/di)/(x2/d2),...,(xp/dp)} kde xk g Rn+1 ad/( eR pro k = 1,..., p. Předpokládejme, že d/< bylo vygenerováno náhodně takto dk = w • xk + ek = wkxk/ + ek /=0 Zde ► w je vektor neznámých vah ► ek jsou generována náhodně s hustotou pravděpodobnosti N[0, a2] kde a2 je neznámý rozptyl Pro fixní w,o2 jsou e\,...,ep generována nezávisle. Pak d\,...,d9 jsou generována s hustotou p p(di,...,dp | W,cr2) = J^N^X^cr2]^) 29 Maximálni log-verohodnost (log-likelihood) Pro p L(Ú,02) :=p{d,,...,dp I ú, o2) = Y[N[tí.)tk,(ŕ](dk) /c=1 platí P 1 p log(L(vŕ,a2)) = -^log27i - ploga - — J^(dk - vr• 4)2 /c=1 a tedy pro každé a2 w maximalizuje L{w,o2) <^> w maximalizuje log(L(w,(j2)) w minimalizuje Tj. maximalizující w nezávisí na a . Max. a2 splňuje a2 = ^ ££=1 (c/^ - Ň/ • x/<)2