Perceptron a ADALINE ► Perceptron ► Perceptronové učící pravidlo ► Konvergence učení perceptronu ► ADALINE ► Učení ADALINE Organizační dynamika: y X^ X2 Xn w = (%w1(...,w„) aX = (x0,Xi,---,Xn) kde x0 = 1 Aktivní dynamika: ► vnitřní potenciál: l = w0 + L/Li w,x; = LýLo w/x/ ► aktivační funkce: o(E) = ► funkce sítě: y[w](x^,...,xn) = a{E,) = a(w■ X) Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {(xA,dA),{x2,d2),...,(xp,dp)] Zde xk = (Xfci... ,xkn) e Rn je vstup /c-tého vzoru a dk e {0,1} je očekávaný výstup. (dk určuje, do které ze dvou kategorií dané xk = (xki.. .,xkn) patří). ► Označme: Xk = {Xko,x^ .. .,Xkn) e IRn+1 kde Xko = 1 ■ ► Vektor vah w je konzistentní s T pokud /[tfKxfc! ...,xkn) = o{w-Xk) = dk pro každé k = 1,...,p. Množina 7" je vnitřně konzistentní pokud existuje vektor w, který je s ní konzistentní. ► Cílem je nalézt vektor w, 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 vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku je vypočteno takto: tf(0 = tf(f-i) _ £ . (a(tf(f-i). xk) - dk) ■ Xk Zde k = ((ŕ - 1) 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 t* takové, že vv(f) je konzistentní s T. 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. Označme Pak lze online učící algoritmus přepsat takto: ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku je vypočteno takto: ► Jestliže cj(w(ř-1) • Xk) = dk, pak #(0 = w(M) ► Jestliže a(w^ ■ Xk) + dk, pak #M = w(M) + zk (Řekneme, že nastala korekce.) kde k = ((ŕ - 1) mod p) + 1. -> ( xk dk = ^ -xk dk = o -> Důkaz Rosenblattovy věty Idea: ► Pro daný vektor w = (wQ,...,wn) označme ||w|| jeho Euklidovskou délku Vvv • w = -^LýLo wf ► Uvážíme hodně dlouhý vektor (spočítáme jak dlouhý) w*, který je konzistentní s T. ► Ukážeme, že pokud došlo v ř-tém kroku ke korekci vah (tedy = vč(ř-1) +zk), pak ||v^(0 _ v^*||2 < ||vv(ř_1) - vv*||2 - ô kde ô > 0 je fixní hodnota (kterou také spočítáme). ► Z toho plyne, že algoritmus nemůže udělat nekonečně mnoho korekcí. Perceptron - adaptivní dynamika Dávkový učící algoritmus: Vypočte posloupnost vv(°), w^2\... váhových vektorů. ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku je vypočteno takto: tf(0 = v^"1) - e ■ £(a(v^-1) • Xk) - dk) ■ Xk Zde 0 < £ < 1 je rychlost učení. 7 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). Gradient chybové funkce Uvažme gradient chybové funkce: Intuice: VE(vv) je vektor ve váhovém prostoru, který ukazuje směrem nejstrmějšího „růstu" funkce E(w). Uvědomte si, že 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 kvadratickou funkcí (konvexní paraboloid). 10 Gradient - ilustrace ADALINE - adaptivní dynamika Dávkový algoritmus (gradientní sestup): ► váhy v w(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku je vypočteno takto: = ^ř-1)-£-^(^ř-1)-X,-d,)-X, Zde 0 < £ < 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 a{w<-'-^ ■ Xk) kde a(í) = £).) Tvrzení Pro dostatečně malé e > 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. 12 ADALINE - adaptivní dynamika Online algoritmus (Delta-rule, Widrow-Hoff rule): ► váhy v vv(°) jsou inicializovány náhodně blízko 0 ► v ř-tém kroku je vypočteno takto: tf(0 = w«-V - e(t) ■ (w^ ■ Xk - dk) ■ Xk kde k = ((ŕ - 1) mod p) + 1 a 0 < e(t) < 1 je rychlost učení v ř-tém kroku. 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 e(t) = \ pak w(°\ w^2\... konverguje ke globálnímu minimu chybové funkce E. 13 ADALINE - klasifikace ► Množina tréninkových vzorů je T = {[^ld^l(x2ld2),...l(xpldp)} kde xk = (xki,...,xkn) eK"acíke {1,-1}. ► Označme Xk = {xk0,xk^,.. .,xkn) e Rn+1 kde xk0 = 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 w ■ 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 perceptranového algoritmu).