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: £ = w0 + L"=i w,x; = £"=0 w,x,- = w-x
Í1   £ > 0;
► aktivační funkce: a(£) = <
KJ    |0 £<0.
► funkce sítě: y[vv](x) = o(E) = o(w ■ x)
Adaptivní dynamika:
► Dána množina tréninkových vzorů
T = {(xA,dA),{x2,d2),...,(xp,dp)]
Zde xk = {xk0lxki.. .,xkn) e Rn+1, xk0 = 1, je vstup /c-tého vzoru ací)(£J0,1) je očekávaný výstup.
(dk určuje, do které ze dvou kategorií dané xk = (xk0,xki . ..,xkn) patří).
► Vektor vah w e Rn+1 je konzistentní s T pokud y[w](xk) = 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 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 kroku ř + 1 je w(ř+1) vypočteno takto:
vč(ř+1)  =  tf(0 - e-(y[w^}(>Ík)-dk)-xk
=  #0 - e-(a(w^-xk)-dk)-xk
Zde k = (ř mod p) + 1 (tj. cyklické procházení vzorů) a 0 < £ < 1 je rychlost učení.
Věta (Rosenblatt)
Jestliže je T vnitřně konzistentní, pak existuje t* takové, že w(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
► váhy v w(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 je w(ř+1) vypočteno takto:
► Jestliže cr(w(ř) • xk) = dk, pak w(ř+1) = w(ř)
► Jestliže cr(wW • xk) + dk, pak
► w('+1) = w^ + xk^odk = } - w('+1) =      - xk pro dk = 0
(Řekneme, že nastala korekce.) kde k = (ř mod p) + 1.
Důkaz Rosenblattovy věty
(Pro daný vektor á= (a0,...,an) označme ||a|| jeho eukleidovskou normu Va-a = ^LLo af)
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 ř + 1 ke korekci vah (tedy buď w(ř+1) =      + xk nebo w(ř+1) =      - xk), pak
w^'-'-w     < \\wv) _ w \\ - max x,
Všimněte si, že max,- x,- > 0 nezávisí na ř.
► Z toho plyne, že algoritmus nemůže udělat nekonečně mnoho korekcí.
Perceptron - adaptivní dynamika
Dávkový učící algoritmus:
Vypočte posloupnost w^°\      w^2\... váhových vektorů.
► váhy v vv(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 je w(ř+1) vypočteno takto:
vČ(ř+1) =       - e ■ £(a(w« • xk) - dk) ■ xk
Zde k = (ř mod p) + 1
a 0 < £ < 1 je rychlost učení.
7
DALINE
Organizační dynamika:
x0 = 1
wo
Q
O o
O
Xn
w = (w0/w1ř...,w„)ax = (xo,x1(...,x„) kde Aktivní dynamika:
► vnitřní potenciál: l = w0 + L/Li wíxí = L
► aktivační funkce: a(£) = 4
► funkce sítě: y[vv](x) = o{E) = w ■ x
ADALINE
Adaptivní dynamika: ► Dána množina tréninkových vzorů
T = {(xA,dA),{x2,d2),...,(xp,dp)]
Zde xk = {xk0lxki.. .,xkn) e Rn+1, xk0 = 1, je vstup /c-tého vzoru a dk e R 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:
( n
1 \ < 2        1 . ,    _ ,
E(^) = 2 Yj     '    ~ dk)   = 2 ^ ^ W'Xki ~ dk ► 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). Vektory xk zde slouží pouze jako parametry funkce E(w) a jsou tedy fixní!
Fakt
Pokud VE(vv) = 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.
10
Gradient - ilustrace
ADALINE - adaptivní dynamika
Dávkový algoritmus (gradientní sestup):
► váhy v vv(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 je w(ř+1) vypočteno takto:
Zde k = (ř mod p) + 1
a 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 w(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 je      vypočteno takto:
kde k = (ř + 1) mod p
a 0 < e(ř) < 1 je rychlost učení v kroku ř + 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 e(t) = | pak w(°\      w^2\... konverguje ke globálnímu minimu chybové funkce E.
->
= tf(0 - £(ř) • (tfO • xk - dk) ■ xk
13
ADALINE - klasifikace
► Množina tréninkových vzorů je
T = {[^ld^l(x2ld2),...l(xpldp)}
kde xk = {xkQ,xk^,...,xkn) e Rn+1 a dk e {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 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).
14