Perceptron a ADALINE
► Perceptron
► Perceptronové uCící pravidlo
► Konvergence uCení perceptronu
► ADALINE
► Ucení ADALINE
1
Perceptron
Organizační dynamika:
Xo = 1
W ^ W2
O o
X2
Xn
W = (wo, wi,..., Wn) aX = (xo,xi,...,Xn) kde xo = 1. Aktivní dynamika:
► vnitrní potenciál: £ = wo + £n=1 w,x; = £n=o WX = W • X
fl £ > o ; [o   £< o.
► funkce síte: y[w](x1,...,Xn) = o(£) = o( W • X)
aktivaCní funkce: o(£) =
y
2
Perceptron
Adaptivní dynamika:
► Dána množina tréninkových vzorů
T = { (xi, di) ,(x2, Č2j ,...,(XP, dp))
Zde xk = (xk 1..., xkn) g Rn je vstup k-tého vzoru a dk g {0,1} je očekávaný výstup.
(dk určuje, do které ze dvou kategorií dané xk patří).
► Označme: Xk = (xk0,xk 1...,xkn) g Rn+1 kde xk0 = 1.
► Vektor vah w je konzistentní s T pokud
y[W](xk 1...,xkn) = o(W • Xk) = dk pro každé k = 1,...,p.
Množina T je vnitrné konzistentní pokud existuje vektor W, který je s ní konzistentní.
► Cílem je nalézt vektor X, který je konzistentní s T za předpokladu, že T je vnitrne konzistentní.
3
Perceptron - adaptivní dynamika
Online uCící algoritmus:
Idea: Cyklicky prochází vzory a adaptuje podle nich váhy, tj. otáčí deiící nadrovinu tak, aby se zmenšila vzdálenost špatne klasifikovaného vzoru od jeho príslušného poloprostoru.
Prakticky pocítá posloupnost vektoru vah w(0), w(1), w(2),....
► váhy v W(0) jsou inicializovány náhodne blízko 0
► v m-tém kroku je w(m vypocteno takto:
W(m) = w(m-1) - e • (o(w(m-1) • Xk) - dk) • Xk
Zde k = ((m - 1) mod p) + 1 (tj. cyklické procházení vzoru) a 0 < e < 1 je rychlost uCení.
veta (Rosenblatt)
Jestliže je T vnitřně konzistentní, pak existuje m* takové, že w(m*) je konzistentní s T.
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éne kompaktní formy. Označme
Xk dk = 1 -Xk  dk = 0
Pak lze online učíčí algoritmus přepsat takto:
► váhy v X(0) jsou inicializovány náhodne blízko 0
► v m-tém kroku je X(m) vypočteno takto:
► Jestliže cj( X(m-1) • Xk) = dk, pak X(m) = X(m-1)
► Jestliže o(X(m-1) • X) * dk, pak X(m) = X(m-1) + Zk (Řekneme, že nastala korekce.)
kde k = ((m - 1) mod p) + 1.
5
Důkaz Rosenblattovy věty
Idea:
► Pro daný vektor w = (w0,wn) označme ||w || jeho Euklidovskou délku Vw • W =   £n=0 w2
► Uvážíme hodně dlouhý vektor (spočítáme jak dlouhý) w*, který je konzistentní s T.
► Ukážeme, že pokud došlo v m-tém kroku ke korekci vah (tedy W(m) = W(m-1) + Zk), pak
w(m) - wf < ||w(m-1) - w*H2 - ô
kde ô > 0 je fixní hodnota (kterou také spočítáme).
► Z toho plyne, že algoritmus nemuže udelat nekonečne mnoho korekčí.
6
Perceptron - adaptivní dynamika
Dávkový uCící algoritmus:
Vypočte posloupnost W(0), W(1), W(2),... váhových vektoru.
► váhy v W(0) jsou inicializovány náhodne blízko 0
► v m-tém kroku je W(m) vypočteno takto:
p
W(m) = W(m-1) - c Y, (o(w(m-1) • Xk) - dk) • Xk
k=1
Zde 0 < c < 1 je rychlost uCení.
7
ADALINE
Organizační dynamika:
y
W0
o o - O
w = (W0, wn) aX = (x0,X1,...,Xn) kde X0 = 1.
Aktivní dynamika:
► vnitrní potenciál: £ = w0 + £n= w,x; = Ln=0 w,x; = W • X
► aktivaCní funkce: ct(£) = £
► funkce sítě: y[X](x1,...,xn) = a(£) = W • X
8
ADALINE
Adaptivní dynamika: ► Dána množina tréninkových vzorů
T = { (xi, di) ,(x2,02) ,...,(xp, dp
Zde xk = (xk 1..., xkn) e Rn, xko = 1, je vstup k-tého vzoru a dk e R je očekávaný výstup.
Intuice: chceme, aby sít' počítala afinní aproximaci funkce, jejíž (nekteré) hodnoty nám předepisuje tréninková množina.
► Oznacme: Xk = (xk0,xk 1...,xkn) e Rn+1 kde xk0 = 1.
► Chybová fůnkce:
Cílem je nalézt w, které minimalizuje E(w).
9
Gradient chybové funkce
Uvažme gradient chybové funkce:
d w0
dE
■)) = Yj (w • Xk - dk) • Xk
' k=1
Intuice: VE(X) je vektor ve váhovém prostorů, který ukazuje smerem nejstrmejšího „rustu" funkce E (X). Uvedomte si, že vektory Xk zde slouží pouze jako parametry funkce E(X) 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( X) 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 X(0) jsou inicializovány náhodně blízko 0
► v m-tém kroku jě X(m) vypoCtěno takto:
Zdě 0 < c < 1 jě rychlost uCění.
(Všimnětě si, žě těnto algoritmus jě téměř stějný jako pro pěrcěptron, protožě w<m-1' • Xk jě hodnota funkcě sítě (tědy ff(w(m-1' • Xk) kdě a(Vj = {).)
Tvrzení
Pro dostatečně malé c > 0 posloupnost X(0), XX(2),... konverguje (po složkách) ke globálnímu minimu funkce E (tedy k vektoru X, který spln uje VE (X) = 0).
k=1
12
ADALINE - adaptivní dynamika
Online algoritmus (Delta-rule, Widrow-Hoff rule):
► váhy v X(0) jsou inicializovány náhodne blízko 0
► v m-tém kroku je X(m) vypočteno takto:
w(m) = w(m-1) - e(m) • (W(m-1) • Xk - dk) • Xk
kde k = ((m - 1) mod p) + 1 a 0 < e (m) < 1 je rychlost učení v m-tém kroku.
Všimnete si, že tento algoritmus nepracuje s celým gradientem, ale jenom s jeho cástí, která přísluší práve zpracovávanému vzoru!
Veta (Widrow & Hoff)
Pokud e(m) = m pak X(0), XX(2),... konverguje ke globálnímu minimu chybové funkce E.
13
ADALINE - klasifikace
► Množina tréninkových vzorU je
kde wxk = ► Oznacme
► Síť se natrénuje ADALINE algoritmem.
► Oceká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 casto platí. Výhoda je, že se ADALINE algoritmus postupne stabilizuje i v neseparabilním případe (na rozdíl od perceptronového algoritmu).
14