ADALINE
Organizační dynamika:
y
Wo
o o - o
Xi X2 Xn
W = (wo, wi,..., Wn) aX = (xo,xi,...,Xn) kde Xo = 1. Aktivní dynamika:
► vnitrní potenciál: £ = w0 + £n=1 w,-x; = Ln=0 w;X; = W • X
► aktivacní funkce: o(£) = £
► funkce síte: y[W](x1xn) = o(£) = W• X
ADALINE - statistické uceni
Uvažme následující modifikaci adaptivní dynamiky:
► Síti je předkládána (nekoneCná) posloupnost tréninkových
vzorU {x1,d1),(x2,d2)kde
► vstupy Xk = (xk1,...,xkn) e Rn jsou generovány náhodne s
daným rozdelením pravdepodobností - každý vstup Xk má přiřazen požadovaný výstup dk e R.
- OznaCme Xk = (xko, xk 1,..., xkn) kde Xko = 1.
Výstup sítě pro k-tý vzor je potom w • Xk.
► Pro danou konfiguraci W definujeme chybu:
E (W ) = ímL1 ■ t \ (w ■ Xk- dk )2
H k=1
Poznámka: Podle zákona o velkých císlech je E(W) střední hodnota promeenné, která vrací1 (w • Xk -     , tedy E(X) = e 2    • Xk - dk^J
2
ADALINE - statistické učeni
Vypočteme gradient VE (w) = d| (w),j§- (w)) :
kde
p
E
k =1
r=0
Cj —
3
ADALINE - statistické uceni
Hledáme minimum E(w), tedy w* takové, že VE(w*) = 0.
Pokud dokážeme statisticky odhadnout Ar/ a C/ pak mUžeme rovnou položit:
a dostat w* jako rešení systému lineárních rovnic.
Toto není príliš praktické protože
► rešení nemusí existovat (přestože minimum funkce E vždy existuje)
► systém rovnic je obvykle hodne velký
3E_
n
0=
r=0
4
ADALINE - statistické uceni
Obvykle se používá gradientní sestup stejně jako v případě normálního ADALINE učení:
► váhy v X(0) jsou inicializovány náhodne blízko 0
► v f-tém kroku (zde f = 1,2,...) je w(f) vypočteno takto:
X(f)   =  W(f-1) - e •VE(v^(f-1))
n
1
w(f    - e • lim - • > (X(l |; • Xk -
í(f-1) - e • lim - Y (X(f-1) • Xk - dk) • X
H k=1
Problém: Gradient je pmmer nekonečne mnoha hodnot!
5
ADALINE - statistické uceni
Naštěstí funguje online algoritmus (Widrow & Hoff), který je úplne stejný jako v předchozí „nestatistické" variante!
► váhy v w(0) jsou inicializovány náhodne blízko 0
► v t-tém kroku (zde t = 1,2,...) je w(t) vypoCteno takto:
ww(t) = ww(t-1) - e(t) • (ww(t-1) • Xk - dk) • Xk
kde k = ((t - 1) mod p) + 1 a 0 < e(t) < 1 je rychlost uCení v t-tém kroku.
veta (Widrow & Hoff)
Pro e (t) = j posloupnost wv(0), Xwv(2),... konverguje ke globálnímu minimu chybové funkce E(wv).
Matematická poznámka: zde se nejedná o konvergenci po složkách, ale o konvergenci prumeru ctvercu vzdálenosti (mean square convergence).
6
Vícevrstvá síť a zpětná propagace
► Vícevrstvé sítě - značení
► učící pravidlo zpětné propagace
► algoritmus zpětné propagace
7
Vícevrstvá síť
Organizační dynamika:
Výstupní
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á
► Napr. třívrstvá sít' se skládá z jedné vstupní, dvou skrytých a jedné výstupní vrstvy.
► Neurony v i-té vrstve jsou spojeny se všemi neurony ve vrstve i + 1.
► Vícevrstvou sít' lze zadat počty neuronu v jednotlivých vrstvách (napr. 2-4-3-2)
8
Vícevrstvá síť
Zde je formálnější definice vícevrstvé síte: Definice
K-vrstvá sít' je acyklická síť jejíž množinu neuronů (s biasy) je možné zapsat jako V0 u V1 u ... u VK kde
► množiny Vi jsou vzájemne disjunktní
► všechny neurony z V0 jsou vstupní
► všechny neurony z VK jsou výstupní
► všechny neurony z V-\ u ... u VK _i jsou skryté (tedy zejména nejsou ani vstupní ani výstupní)
► pro každé i = 0,..., K _ 1 platí, že výstup každého neuronu z Vi je vstupem každého neuronu z Vi+1 (a v síti nejsou žádné další spoje)
9
Vícevrstvá sít'
ZnaCení:
► OznaCme
► X množinu vstupních neuronů
► Y množinu výstupních neuronů
► Z množinu všech neuronu (tedy X, Y c Z)
► jednotlivé neurony budeme znacit indexy i, j apod.
► fy je vnitřní potenciál neuronu j po skoncení výpoctu
► yj je stav (výstup) neuronu j po skoncení výpoctu
(zde definujeme y0 = 1 jako hodnotu formálního jednotkového vstupu)
► Wji je váha spoje od neuronu i do neuronu j
(zejména wj0 je váha speciálního jednotkového vstupu, tj. wj0 = _bj kde bj je bias neuronu j)
► j_ je množina všech neuronu, z nichž vede spoj do j (zejména 0 e j_)
► j-" je množina všech neuronu, do nichž vede spoj z j
10
Vícevrstvá sít'
Aktivní dynamika:
► vnitřní potenciál neuronu j:
► aktivacní funkce o j pro neuron j:
0j(í) = TT^
(obvykle se uvažuje Aj = 1 pro všechna j, ale obecne mohou být rázné)
► Stav nevstupního neuronu j e Z \ X po skoncení výpoctu je
yj = 0j {íj) = YV^j
(yj závisí na konfiguraci w a vstupu X, proto budu obcas psát yj(W,X))
► Sít' pocítá funkci z r|x| do r|y|. Výpocet probíhá po vrstvách. Na zacátku jsou hodnoty vstupních neuronu nastaveny na vstup síte. V kroku l jsou vyhodnoceny neurony z l-té vrstvy.
Vícevrstvá síť
Adaptivní dynamika:
► Dána množina T tréninkových vzorů tvaru
{(4       |  k = 1,..., p]
kde každé xk e R|X| je vstupní vektor a každé dk e R|Y| je očekávaný výstup sítě. Pro každé j e Y označme dky očekávaný výstup neuronu j pro vstup xk (vektor dk lze tedy psát jako (dky)jeY).
► Chybová fůnkce:
E(W) = £ Ek(W)
k =1
kde
Ek (W) = 2 ^ (yy (W,Xk) - dkj)2
je Y
12
Vícevrstvá sít' - uďcí algoritmus
Dávkový algoritmus (gradientní sestup):
Algoritmus pocítá posloupnost vektoru vah W(0), W....
► váhy v w(0) jsou inicializovány náhodne blízko 0
► v f-tém kroku (zde f = 1,2,...) je w(f) vypocteno takto:
Wf) = w(f-1) + Aw(ř )
kde
je zmena váhy Wj/ v f-tém kroku a 0 < e(f) < 1 je rychlost ucření v f-tém kroku.
Všimnete si, že ^e.(W(f-1)) je komponenta gradientu vE, tedy zmenu vah v f -tém kroku lze zapsat také takto: w(f) = w(f-1) - e(f) • vE (w(f-1)).
13
Vícevrstvá sít' - gradient chybové funkce
Pro každé wji máme
kde pro každé k = 1 , . . . , p platí
a pro každé j e Z \ X dostaneme
-fy = y - dk pro j e Y
d-fy7 = Yj      ArVr(1 - Vr)wj      pro j e Z \ (Y U X)
(Zde všechna y jsou ve skutecnosti y(ww,Xk)).
14
Vícevrstvá síť - výpočet gradientu
Algoritmicky lze j-jj spočítat takto: Polož Sjj := 0  (na konci výpočtu bude Ej = jWj)
Pro každé k — 1,...,p udeiej následující
1. spočítej yj pro každé j e Z a k-tý vzor, tedy y — yj(w,xk) (tj. vyhodnoť sít' ve standardním aktivním režimu)
2. pro všechna j e Z spočítej ^ pomočí zpetného šíření
(viz. následující slajd!)
3. spočítej |Wl pro všechna Wjj pomočí vzorče
-inr Ajyj(1 - y )y
dwjj ' dyj
4 e;< := ej<+Ur
Výsledné    se rovná j-j.
15
Vícevrstvá sít' - zpetné šíření
-jj lze spocítat v lineárním case (s jednotkovou aritmetikou) pomocí zpetného šírení:
► spocítáme     pro j e Y pomocí vzorce     = yj - dkj
► rekurzivne spocítáme zbylé :
Nechť j je v i-té vrstve a předpokládejme, že ^ už máme spocítáno pro všechny neurony z vyšších vrstev (tedy vrstev i + 1,i + 2,...). Pak lze     spocítat pomocí vzorce
j rej-
protože všechny neurony r e j-" patří do vrstvy i + 1.
16
Složitost dávkového algoritmu
Výpočet hodnoty JWĹ(X(f-1)) probíhá v lineárním čase vzhledem k velikosti síte a počtu tréninkovýčh vzoru.
(předpokládáme jednotkovou čenu aritmetičkýčh operačí)
ZdUvodnení: Algoritmus provede p krát následujíčí
1. vyhodnočení síte (tj. výpočet y(w,xk))
2. výpočet ddyk zpetným šířením
3. výpočet JEk
d Wji
4.   pričtení II k Eji
Kroky 1.-3. probehnou v lineárním čase a krok 4. v konstantním vzhledem k velikosti síteř.
Počet iterací gradientního sestupu pro přiblížení se (lokálnímu) minimu může být velký...
17
Vícevrstvá sít' - ůCící algoritmus
Online algoritmus:
Algoritmus počítá posloupnost vektoru vah W(0), W....
► váhy v w(0) jsou inicializovány náhodne blízko 0
► v f-tém kroku (zde f = 1,2,...) je W(f) vypočteno takto:
Wf} = W(f-1) + Aw(ř}
kde
kde k = ((f - 1) mod p) + 1 a 0 < e(f) < 1 je ryčhlost učení v f-tém kroku.
Lze použít i stochastickou verzi tohoto algoritmu, v níž je k voleno náhodne z {1,...,p}.
18