ADALINE
Organizační dynamika:
xo = 1
W0
Q
O o
w = (wb,wi,...fwn) ax = (x0fxi,...fxn) kdex0 = 1. Aktivní dynamika:
funkce sítě: y[vv](x) = w ■ x
Poznámka: násobení vektorů
Pokud nebude řečeno jinak, budeme uvažovat všechny vektory jako sloupcové
ao
3a
pak  a = (a0,a1/.../am)1
Skalární součin lze chápat jako součin matic:
m
a ■ b = ^ akbk = aTb = bTa
k=0
bovolná dimenze - adaptivní dynamika - shrnut
Tréninková množina:
T = {(xi/d1)/(x2/Cř2)/.../(xp/clp)}
Zde xk = {xkQlxkA ...,xkn)T eRn+\xk0 = 1, je vstup /c-tého vzoru a dk e IR je očekávaný výstup.
Chybová funkce:
1    P 2        1    P  í -
Gradient E:
VE
Minimalizace chyby
Nechť X je matice p x (n + 1) (tj. p řádků, n + 1 sloupců), jejíž k-tý řádek je tvořen vektorem x£
Nechť d = (cři,...,^)7" Pak
VE(w) = 0  o  (XTX)w = XTď o XT(Xw) = XTď o  w = (XTX)"1XTď pokud (XTX)_1 existuje.
(pak (XTX)~1XT je tzv. Moore-Penrose pseudoinverse matice X) Všimněte si, že
p p (XTX);,-   =   Y^xkixkj      a      (XTd),-   = £xtócfc
(zde (XTX),y je prvek matice XTX na /-tém řádku a y-tém sloupci)
ADALINE - statistické učení
Uvažme následující modifikaci adaptivní dynamiky:
► Síti je předkládána (nekonečná) posloupnost tréninkových vzorů (x-\ , d-i), (x2, cfe),... kde
► vstupy xk — (xk0r Xfc-i,..., xkn)T e R" jsou generovány náhodně s fixním rozdělením pravděpodobností
► každý vstup xk má přiřazen požadovaný výstup dk e R.
► Pro danou konfiguraci w definujeme chybu:
Poznámka: Podle zákona o velkých číslech je E(w) střední hodnota proměnné, která vrací \ (wTxk - ck) , tedy E(w) = E | (wTxk - ck) ► Gradient E:
1 p
VEÍvv)   =    lim — 7 (wTXk - dk)xk
p->oo n X—< v /
DALINE - statistické učení
Nechť A je matice (n + 1) x (n + 1) splňující
a D e Rn+1 vektor splňující
Pak VE(w) = Aw - D a tedy E{w) = 0  o  Aw = D
Problémy:
1. neznáme /\ a D
2. nemusí existovat i přesto, že E má vždy jednoznačně určené minimum
Pokud lze odhadnout Aír a D-„ můžeme použít gradientní sestup stejně jako v případě normálního ADALINE učení:
► váhy v w(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 (zde ř = 0,1,2,...) je w(ř+1) vypočteno takto
Co když ani nelze odhadnout Aír a D, ?
ADALINE - statistické učení
Naštěstí funguje online algoritmus (Widrow & Hoff), který je úplně stejný jako v předchozí „nestatistické" variantě!
► váhy v vv(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 (zde ř = 0,1,2,...) je w(ř+1) vypočteno takto:
vč(ř+1) = tf(0 - £(ř) • (tfO •      - cří+1) ■ xř+1 kde 0 < e(t) < 1 je rychlost učení v kroku ř + 1. Věta (Widrow & Hoff)
Pro e(t) = j posloupnost w^°\      w^2\... konverguje ke globálnímu minimu chybové funkce E(w).
Matematická poznámka: zde se nejedná o konvergenci po složkách, ale o konvergenci průměru čtverců vzdálenosti (mean square convergence).
8
Vícevrstvá síť a zpětná propagace
► Vícevrstvé sítě - značení
► učící pravidlo zpětné propagace
► algoritmus zpětné propagace
Vícevrstvá síť
Organizační dynamika:
Výstupní
Q O
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á
► Např. třívrstvá síť se skládá z
jedné vstupní, dvou skrytých a
jedné výstupní vrstvy.
Neurony v i-\é vrstvě jsou spojeny se všemi neurony ve vrstvě l + 1.
Vícevrstvou síť lze zadat počty neuronů v jednotlivých vrstvách (např. 2-4-3-2)
10
Vícevrstvá síť
Značení:
► Označme
► X množinu vstupních neuronů
► Y množinu výstupních neuronů
Z množinu všech neuronů (tedy X, Y c Z)
► jednotlivé neurony budeme značit indexy i, j apod.
► £y je vnitřní potenciál neuronu j po skončení výpočtu
► y j je stav (výstup) neuronu j po skončení výpočtu
(zde definujeme y0 = 1 jako hodnotu formálního jednotkového vstupu)
► Wjj je váha spoje od neuronu ;' do neuronu j
(zejména wj0 je váha speciálního jednotkového vstupu, tj. wj0 = -ty kde bj je bias neuronu j)
► y«_ je množina všech neuronů, z nichž vede spoj do j (zejména 0 e y<_)
► y-_> je množina všech neuronů, do nichž vede spoj z j
11
Vícevrstvá síť
Aktivní dynamika:
► vnitřní potenciál neuronu j:
ti=E wJiYi
*■ aktivační funkce a j pro neuron y je libovolná diferencovatelná funkce [ např. logistická sigmoida a/(£) = 1 J-a^ ]
*■ Stav nevstupního neuronu j e Z \ X po skončení výpočtu je
Yj =
(yy- závisí na konfiguraci w a vstupu x, proto budu občas psát y,{w,x))
*■ Síť počítá funkci z R|X| do R|Y|. Výpočet probíhá po vrstvách. Na začátku jsou hodnoty vstupních neuronů nastaveny na vstup sítě. V kroku i jsou vyhodnoceny neurony z i-lé vrstvy.
12
Vícevrstvá síť
Adaptivní dynamika:
► Dána množina T tréninkových vzorů tvaru
{(xkldk)   |  1^ = },...^]
kde každé xk e IR|X| je vstupní vektor a každé dk e IR|y| je očekávaný výstup sítě. Pro každé j e Y označme dkj očekávaný výstup neuronu j pro vstup xk (vektor dk lze tedy psát jako (cfo/) ).
► Chybová funkce:
p
E(Ú) = YJEk(Ú)
kde
jeY
13
Vícevrstvá síť - učící algoritmus
Dávkový algoritmus (gradientní sestup):
Algoritmus počítá posloupnost vektorů vah w(°\      ....
► váhy v vv(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 (zde ř = 0,1,2...) je w(ř+1) vypočteno takto
li kde
Aw{t) = -e(t)-^-(w^)
je změna váhy wp v kroku ř + 1 a 0 < e(t) < 1 je rychlost učení v kroku ř + 1.
Všimněte si, že |f-(w(í)) je komponenta gradientu VE, tedy změnu vah v kroku f + 1 lze zapsat také takto: w(í+1) = w(í) - e(t) ■ VE(w^).
Vícevrstvá síť - gradient chybové funkce
Pro každé w,, máme
— - V —
dwii ~ J3 5w/v
kde pro každé k = 1,..., p platí
a pro každé j e Z\X dostaneme
— =yj-dkj proyeY
d-Ě = L^-^)-n ProyeZx(Y (Zde všechna y; jsou ve skutečnosti yj(w,xk)).
Vícevrstvá síť - gradient chybové funkce
► Pokud a/(£) = 1 J-Ajč Pro každé j e Z pak
a dostaneme pro každé j e Z\X:
— =yj-dkj proyeY
^ = E§7L-^yr(1-yr)-wfí- proyeZ\(YuX)
► Pokud a/(£) = a • tanh(r> • £y) pro každé y e Z pak
Vícevrstvá síť - výpočet gradientu
Algoritmicky lze J| = LjJ=1 §§J spočítat takto: Polož Sjj := 0  (na konci výpočtu bude £/,- =
Pro každé k = 1,... ,p udělej následující
1. spočítej y, pro každé j e Z a k-lý vzor, tedy y, = yj{w,Xk) (tj. vyhodnoť síť ve standardním aktivním režimu)
2. pro všechna j e Z spočítej ^ pomocí zpětného šíření
(viz. následující slajd!)
3. spočítej ^| pro všechna w,, pomocí vzorce
fay — +
Výsledné Ey; se rovná
Vícevrstvá síť - zpětné šíření
^ lze spočítat pomocí zpětného šíření:
► spočítáme ^ pro j e V pomocí vzorce ^ = y,- -
► rekurzivně spočítáme zbylé
Nechť j je v £-té vrstvě a předpokládejme, že ^ už máme spočítáno pro všechny neurony z vyšších vrstev (tedy vrstev i+ 1,^ + 2,...). Pak lze ^ spočítat pomocí vzorce
protože všechny neurony r e y-_> patří do vrstvy l + 1.
Složitost dávkového algoritmu
Výpočet hodnoty Jf:(w(ř~1)) probíhá v lineárním čase vzhledem k velikosti sítě a počtu tréninkových vzorů
(za předpokladu jednotkové ceny operací včetně vyhodnocení a'r(£r) pro dané £r)
Zdůvodnění: Algoritmus provede p krát následující
1. vyhodnocení sítě (tj. výpočet y,(w,x^))
2. výpočet ^ zpětným šířením
3. výpočet §jj
4. přičtení §| k Gji
Kroky 1.-3. proběhnou v lineárním čase a krok 4. v konstantním vzhledem k velikosti sítě.
Počet iterací gradientního sestupu pro přiblížení se (lokálnímu) minimu může být velký...
19
Vícevrstvá síť - učící algoritmus
Online algoritmus:
Algoritmus počítá posloupnost vektorů vah w(°\      ....
► váhy v vv(°) jsou inicializovány náhodně blízko 0
► v kroku ř + 1 (zde ř = 0,1,2,...) je w(ř+1) vypočteno takto:
= rf(f) + Aw{t)
kde
W.0 = _e(ř). ^>«)
kde k = (t mod p) + 1 a 0 < e(t) < 1 je rychlost učení v kroku ř + 1.
Lze použít i stochastickou verzi tohoto algoritmu, v níž je k voleno náhodně z {1,.. .,p}.