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)
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 neuronu (tedy X, Y c Z)
► jednotlivé neurony budeme značit indexy i, j apod.
► £; je vnitřní potenciál neuronu j po skončení výpočtu
► 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
2
Vícevrstvá síť
Aktivní dynamika:
► vnitřní potenciál neuronu j:
► aktivaCní funkce oj pro neuron j je libovolná diferencovatelná funkce (upřesním pozdeji)
► Stav nevstupního neuronu j e Z \ X po skoncení výpoctu je
yj = oj {íi)
(yj závisí na konfiguraci w a vstupu x, proto budu obcas psát y(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.
3
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
4
Vícevrstvá síť - učící algoritmus
Dávkový algoritmus (gradientní sestup):
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
je zmena váhy wy; v f-tém kroku a 0 < e(f) < 1 je rychlost učení v f-tém kroku.
Všimnete si, že jWL(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)).
5
Vícevrstvá síť - učí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:
Wř} = W(f-1) + Aw(ř} JI JI
kde
kde k = ((f - 1) mod p) + 1 a 0 < e(f) < 1 je rychlost 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}.
6
Vícevrstvá sít' - gradient chybové funkce
Pro každé Wp máme
kde pro každé k = 1,...,p platí -Ek    dEk        . y
a pro každé j e Z \ X dostaneme Ek
— = y - dkj pro j e Y
(Zde všechna yj jsou ve skutecnosti y(W,xk)).
7
Vícevrstvá síť - gradient chybové funkce
Pokud oj(£) =   J_A.( pro každé y e Z pak o^y)= AjYj(1 _ yy)
a dostaneme přesně gradient z minulé prednášky. Pokud oj (Z) = a • tanh(b • Zy) pro každé y e Z pak
o;(Zy) = a (a _ yy )(a + yy)
8
Vícevrstvá síť - výpočet gradientu
Algoritmicky lze jWL spočítat takto: Polož Sjj := 0  (na konci výpočtu bude &jj = jWj)
Pro každé k = 1,...,p udeiej následující
1. spočítej y/ pro každé j e Z a k-tý vzor, tedy y = y(w,xk) (tj. vyhodnoť sít' ve standardním aktivním režimu)
2. pro všechna j e Z spočítej     pomocí zpetného šíření
(viz. následující slajd!)
3. spocítej jWj pro všechna Wjj pomocí vzorce
dEk :   dEk    ,   ) y
4. Ejj := ejj + j|
Výsledné Ejj se rovná j-j.
9
Vícevrstvá sít' - zpetné šíření
^ lze spočítat v lineárním čase (s jednotkovou aritmetikou) pomocí zpetného šíření:
► spočítáme ^ pro j e Y pomočí vzorče dE- = yj - dkj
► rekurzivne spočítáme zbylé ^:
dyj
Nečhť j je v l-té vrstve a predpokládejme, že ^ už máme spočítáno pro všečhny neurony z vyššíčh vrstev (tedy vrstev l + 1,1 + 2,...). Pak lze ^ spočítat pomočí vzorče
protože všečhny neurony r e j- patří do vrstvy l + 1.
10
Praktické otázky gradientního sestupu
► Otázky týkající se efektivity ucení:
► Dávkový nebo online algoritmus?
► Je nutné data předzpracovat?
► Jak volit iniciální váhy?
► Je nutné vhodne volit požadované hodnoty síte?
- Jak volit rychlost ucení e (t) ?
► Dává gradient nejlepší smeřr zmeřny vah?
► Otázky týkající se výsledného modelu:
► Kdy zastavit ucení?
- Kolik vrstev síte a jak velkých?
► Jak velkou tréninkovou množinu použít?
► Jak zlepšit vlastnosti (prřesnost a schopnost generalizace) výsledného modelu?
11
Poznámky o konvergenci gradientního sestupu
► Chybová funkce muže být velmi komplikovaná:
► muže obsahovat mnoho lokálních minim, učící algoritmus v nich muže skoncit
► muže obsahovat mnoho „plochých" míst s velmimalým gradientem, zejména pokud se aktivacní funkce tzv. saturují (tedy jejich hodnoty jsou blízko extrémum; v případe sigmoidálních funkcí to znamená, že mají velké argumenty)
► muže obsahovat velmistrmá místa, což vede k preskocení minim gradientním sestupem
► pro velmi malou rychlost ucení máme vetší šanci dokonvergovat do lokálního minima, ale konvergence je hodne pomalá
Teorie: pokud e(f) = j pak dávkový i stochastický gradientní sestup konvergují k lokálnímu minimu (nicméne extrémne pomalu).
► pro príliš velkou rychlost ucení muže vektor vah strídave přeskakovat minimum nebo dokonce divergovat
12
Gradientní sestup - ilustrace
Gradientní sestup s malou rychlostí učení:
Více méne hladká krivka, každý krok je kolmý na vrstevnici.
Obrázek: Neural Computation, Dr John A. Bullinaria 13
Gradientní sestup - ilustrace
Gradientní sestup s příliš velkou rychlostí učení:
-►
Wj
Jednotlivé kroky přeskakují minimum, učení je pomalé.
Obrázek: Neural Computation, Dr John A. Bullinaria
14
Gradientní sestup - ilustrace
Online učení:
Kroky nemusí být kolmé na vrstevnice, muže hodne kličkovat.
Obrázek: Neural Computation, Dr John A. Bullinaria
pH   r        m r mm \s r      r m m a
Dávkový vs online ucici algoritmus
Výhody dávkového:
► realizuje přesne gradientní sestup pro chybovou fci(vetšinou konverguje k lokálnímu minimu)
► snadno paralelizovatelný (vzory je možné zpracovávat oddelene) Nevýhody dávkového:
► pamet'ová nároccnost (musí sipamatovat chyby všech vzoru)
► redundantní data nepřidávají informacike gradientu. Výhody online (stochastického)
► stochastický má šanci uniknout z okolí meřlkého minima (protože nerealizuje přresný grad. sestup)
► má menší pamet'ovou nároccnost a snadno se implementuje
► je rychlejší, zejména na hodne redundantních datech Nevýhody online (stochastického)
► není vhodný pro paralelizaci
► muže hodne „klickovat" (více než gradientní sestup)
16
Moment
Problémy s gradientním sestupem:
► MUže se stát, že gradient VE(w(t)) neustále mení smer, ale chyba se postupne zmenšuje.
Toto Často nastává, pokud jsme v melkém údolí, které se mírne svažuje jedním smerem (neco jako U-rampa pro snowboarding, učící algoritmus potom opisuje dráhu snowboardisty)
► Online algoritmus také muže zbytečne kličkovat.
Tento algoritmus se vubec nemusí pohybovat ve smeru nejvetšího spádu!
Řešení: Ke zmene vah dané gradientním sestupem přicteme cást zmeny v predchozím kroku, tedy definujeme
kde 0 < a < 1.
17
Moment - ilustrace
Bez momentu:
S momentem:
18
Volba aktivační funkce
► Z hlediska rychlosti konvergence je výhodné volit lichou aktivační funkci.
► Standardní sigmoida není lichá, vhodnejší je použít hyperbolický tangens:
o(£) = a • tanh(b • £)
► Při optimalizaci lze předpokládat, že sigmoidální funkce jsou fixní a „hýbat" pouze dalšími paramtery.
► Z technických duvodu budeme dále předpokládaf, že všechny akfivaCní funkce jsou fvaru
oj (fy) = a • tanh(b • £y)
kde a = 1.7159 a b = 2.
19
Volba aktivační funkce
1.5
1.0
0.5
0.0
-0.5
-10
-1.5
■4-3-2-1 0 1 2 3
a(B) = 1.7159 • tanh(§ • B), platí lim^, a(B) = 1.7159 a lim^-c a(B) = -1.7159
20
Volba aktivační funkce
■1.0 -0.8 -0.6 -0.4 -0.2 0.0 0.2 0.4 0.6 0.8 1.0
o(E) = 1.7159 • tanh(§ • E) je téměř lineární na [-1,1]
21
Volba aktivační funkce
1.2
1.0
0.8
0.6
0.4
0.2
0.0
-0.2
■4-3-2-10123
první derivace funkce o(E) = 1.7159 • tanh(§ • E)
22
Volba aktivační funkce
Předzpracování vstupu
► Nekteré vstupy mohou být mnohem vetší než jiné
Pr.: Výška cloveka vs délka chodidla (oboje v cm), maximální rychlost auta (v km/h) vs cena (v Kc), apod.
► Velké komponenty vstupu ovlivnují ucení více, než ty malé. Navíc príliš velké vstupy mohou zpomalit ucení.
► Numerická data se obvykle normalizují tak, že mají
► prumernou hodnotu = 0 (normalizace odectením paimeru)
► rozptyl = 1 (normalizace podeřlením smeřrodatnou odchylkou)
Zde prumer a smerodatná odchylka mohou být odhadnuty z náhodného vzorku (např. z tréninkové množiny).
► Jednotlivé komponenty vstupu by mely mít co nejmenší korelaci (tj. vzájemnou závislost).
(Metody pro odstraneení korelace dat jsou napr. analýza hlavních komponent (Principal Component Analysis, PCA). Lze ji implementovat i pomocí neuronových sítí (probereme pozdeeji)).
24
Iniciální volba vah
► Iniciálne jsou váhy nastaveny náhodne z daného intervalu [-w, w] kde w závisí na poctu vstupu daného neuronu. Jaké je vhodné w?
► Uvažujeme aktivacní funkci 1.7159 • tanh(§ • £) pro všechny neurony.
► na intervalu [-1,1] se o chová témer lineárne,
► extrémy o" jsou približne v bodech -1 a 1,
► mimo interval [-4,4] je o blízko extrémních hodnot. Tedy
- Pro velmimalé w hrozí, že obdržíme témer lineární model (to bychom mohlidostat s použitím jednovrstvé síte). Navíc chybová funkce je velmiplochá v blízkosti 0 (malý gradient).
► Pro w mnohem vetší než 1 hrozí, že vnitrní potenciály budou vždy příliš velké a sít' se nebude ucit (gradient chyby E bude velmimalý, protože hodnota síte se témeř nezmení se zmeřnou vah).
Chceme tedy zvolit w tak, aby vnitřní potenciály byly zhruba z intervalu [-1,1].
25
Iniciální volba vah
► Data mají po normalizaci (zhruba) nulovou střední hodnotu, rozptyl (zhruba) 1 a předpokládejme, že jednotlivé komponenty vstupu jsou (témer) nekorelované.
► Uvažme neuron j z první vrstvy s d vstupy, prředpokládejme, že jeho váhy jsou voleny uniformneř z intervalu [-w, w].
► Pravidlo: w je dobré volit tak, že směrodatná odchylka vnitrního potenciálu lj (oznacme ji Oj) leží na hranici intervalu, na nemž je aktivacní funkce oj témer lineární tj. v našem prípade chceme Oj ~ 1.
tj. v našem případe položíme w = -^=.
► Totéž funguje pro vyšší vrstvy, d potom odpovídá poctu neuronu ve vrstve o jedna nižší.
(Zde je důležité, že je aktivacní funkce lichá)
► Z našich předpokladu plyne Oj
w.
26
Požadované hodnoty
► Požadované hodnoty dkj by mely být voleny v oboru hodnot aktivacních funkcí, což je v našem případe [-1.716,1.716].
► Požadované hodnoty příliš blízko extrémum ±1.716 zpusobí, že váhy neomezene porostou, vnitrní neurony budou mít velké potenciály, gradient chybové funkce bude malý a ucření se zpomalí.
► Proto je vhodné volit požadované hodnoty z intervalu [-1.716 + b, 1.716 - b]. Optimální je, když tento interval odpovídá maximálnímu intervalu na neřmž jsou aktivacřní fce lineární. Tedy v našem případe b ~ 0.716, tj. hodnoty dkj je dobré brát z intervalu [-1,1].
27
Rychlost ucení
Obecné zásady pro volbu a zmeny rychlosti ucení e
► Je dobré zacít s malou rychlostí (napr. e = 0.1).
► Pokud se chyba znatelne zmenšuje (ucení konverguje), mužeme rychlost nepatrne zvýšit.
► Pokud se chyba zjevnee zveetšuje (ucení diverguje), mužeme rychlost snížit.
► Krátkodobé zvýšení chyby nemusí nutne znamenat divergenci.
E
Obr. 2.3: Typický vývoj chyby v čase při učení pomocí backpropagation.
28
Rychlost učeni
Chceme, aby se neurony ucily pokud možno stejne rychle. Více vstupu obvykle znamená rychlejší ucení.
Pro každou váhu wpi mužeme mít zvláštní rychlost ucení ep
► e ji lze iniciovat napr. 1       kde     je pocet vstupu neuronu p.
► Po zahájení ucení váhu zvolna zvyšujeme
(treba ep(t) = Kef (t - 1) kde K > 1)
► Jakmile se zmení znaménko Awp(t) (tedy Aw..-1) • Aw.. ^ < 0), váhu snížíme (třeba takto ep-(t) = 1 ep-(t - 1))
29
Řychlost a smíír - přesneJi
Na gradientní sestup se mužeme dívat obecneji takto:
Aw(t) = r(t) • s (t)
kde r(t) je rychlost zmeny vah a s(t) je smer zmeny vah. V našem případe: r(t) = e(ř) a s (t) = _VE (w(t (nebo s(t) = _VEk(w(tpro online ucení).
► Ideální by bylo volit r(t) tak, abychom minimalizovali E (w(t _1) + r (t) • s (t)).
Nebo se asponř chceme prřesunout (ve smeřru s(t)) do místa, v nemž zacne gradient opet rust.
► Toho lze (přibližne) dosáhnout malými presuny bez zmeny smeřru - nedostaneme ovšem o mnoho lepší algoritmus než standardní grad. sestup (který stále meřní smeř r).
► Existují lepší metody, např. parabolická interpolace chybové funkce.
30
Rychlost a smer - parabolická interpolace
Označme E (r) = E (w(t_1) + r • s{t)); minimalizujeme E (r).
Predpokládejme, že jsme schopni nalézt body A, B, C takové, že E (A) > E (B) a E(C) > E (B). Pak lze tyto body proložit parabolou a nalézt její minimum D. Toto D je dobrým odhadem minima E(r).
Obrázek: Neural Computation, Dr John A. Bullinaria
31
Rychlost a smer - parabolická interpolace
Parabolickou interpolaci lze dále iterovat, čímž dosáhneme ještě lepšího odhadu:
E (r )f
r
Je jasné, že E (B) > E (D) a E (C) > E (D), proto lze použít stejný postup jako prředtím.
Obrázek: Neural Computation, Dr John A. Bullinaria
32
Optimální směr
Zbývá otázka, jestli je záporný gradient správným smerem. Rychlost r(t) jsme volili tak, abychom minimalizovali
E (w(t))  =  E(w(t -1) + r (t) • s (t))
=  E (vČ(t-1) + r(t) • (-VE(v^(t-1)))
To ovšem znamená, že derivace E(rô(t)) podle r(t) (zde bereme r(t) jako nezávislou promennou) bude 0, tedy
b4- (w(t)) = E ^ (w(t)) •(-^ (ww(t-'))\
=  VE(w(t)) • (-VE(w(t-1)))
=0
Tj. nový a starý smeřr jsou vzájemneř kolmé, výpocřet tedy „klickuje".
33
Gradientní sestup s optimální rychlostí
34
Rychlost a smer - přesněji
Rešení: Do nového smeru zahrneme částečne i predčhozí smeřr a tím zmenšíme kličřkování.
s(t ) = -VE (W(t-1)) + p- s (t - 1)
Jak určit p ? Metoda sdružených gradientů je založena na tom, že nový smeřr by meřl čo nejméneř kazit minimalizači dosaženou v predčhozím smeru. Chčeme nalézt nový smer s(t) takový, že gradient funkče funkče E v novém bode W(t) = W(t-1) + r (t) ■ s(t) ve starém smeru s (t - 1) je nulový:
s(t - 1)- VE (W(t}) = 0
Vhodné p, které to splnuje je dáno následujíčím pravidlem (Polak-Ribiere):
= (VE(w(t)) - VE(w(t-1))) ■ VE(w(t)) P =        VE (W(t-VE (W(t (Pokud by E byla kvadratičká funkče, pak to konverguje v nejvýše n kročíčh)
35
Gradientní sestup s optimální rychlostí
36
Další metody
Existuje mnoho metod druhého rádu, které jsou přesnější, ale obvykle výpocetne mnohem náročnejší (příliš se nepoužívají). Např. Newtonova metoda, Levenberg-Marquardt, atd.
Vetšina techto metod vyžaduje výpočet (nebo aspon aproximaci) druhé derivace chybové funkce nebo funkce síte (tj. Hessián).
Lze nalézt v literature, např.
Haykin, Neural Neworks and Learning Machines
37
Schopnost generalizace
V klasifikacních problémech se dá generalizace popsat jako schopnost vyrovnat se s novými vzory.
Pokud sít trénujeme na náhodneř vybraných datech, není ideální presne klasifikovat tréninkové vzory.
Pokud aproximujeme funkcní závislost vstupu a ocekávaných výstupu pak obvykle nechceme aby funkce síte vracela presné hodnoty pro tréninkové vzory.
Exaktneji: Obvykle se predpokládá, že tréninková množina byla generována takto:
dkj = Qj (Xk) + Qkj
kde Qj je „správná" funkce výstupního neuronu j e Y a Qkj je náhodný šum. Chceme, aby sít' pokud možno realizovala funkce Qj.
38
Kdy zastavit ucení?
Standardní kritérium: Chyba E je dostatecne malá.
Další možnost: po nekolik iterací je gradient chyby malý.
(Výhodou tohoto kritéria je, že se nemusí pocítat chyba E)
Problém: Príliš dlouhé ucení zpusobí, že sít' „opisuje" tréninkové vzory (je pretrénovaná). Dusledkem je špatná generalizace.
Rešení: Množinu vzoru rozdelíme do následujících množin
► tréninková (např. 60%) - podle techto vzoru se síť ucí
► validacní (např. 20%) - používá se k zastavení ucení.
► testovací (napr. 20%) - používá se po skoncení ucení k testování presnosti síte, tedy srovnání nekolika natrénovaných sítí.
39
Trénink, testování, validace
Obvykle se realizuje nekolik iterací (cca 5) tréninku na tréninkové množine. Poté se vyhodnotí chyba E na validacní množine.
Ideálne chceme zastavit v minimu chyby na validacní množine. V praxi se sleduje, zda chyba na validacní množine klesá. Jakmile zacne nůst (nebo roste po nekolik iterací za sebou), ucení zastavíme.
Problém: Co když máme príliš málo vzoru?
Mužeme tréninkovou množinu rozdelit na K skupin S1,..., SK. Trénujeme v K fázích, v ^-té fázi provedeme následující:
► trénujeme na S1 u ... u Sŕ-1 u Sŕ+1 u ... u SK
► spocteme chybu e( funkce E na skupine S( Celková chyba je potom prumer e = K LK=1 .
Extrémní verze: K = pocet vzoru (používá se pri extrémne málo vzorech)
40
Velikost sítě
Podobný problém jako v případe délky ucení:
► Prříliš malá sít není schopna dostatecřneř zachytit tréninkovou množinu a bude mít stále velkou chybu
► Prříliš velká sít má tendenci prřesneř opsat tréninkové vzory - špatná generalizace
Řešení: Optimální pocet neuronu :-)
► teoretické výsledky existují, ale jsou vetšinou nepoužitelné
► existují ucřící algoritmy, které postupneř prřidávají neurony (konstruktivní algoritmy) nebo odstranují spoje a neurony (prořezávání)
► V praxi se pocet vrstev a neuronu stanovuje experimentálne (proste se to zkusí, uvidí, opraví) a/nebo na základeř zkušeností.
41
Velikost tréninkové množiny
Príliš malá nebo nereprezentativní tréninková množina vede ke špatné generalizaci
Príliš velká zvyšuje složitost ucení. V případe dávkového algoritmu zpusobuje velkou chybu (chyby na vzorech se scítají), což muže vést k přetrénování.
Pravidlo pro klasifikační úlohy: pocet vzoru by mel zhruba odpovídat W/b kde
► W je pocet vah v síti
► 0 < b < 1 je tolerovaná chyba na testovací množine
(tj. tolerujeme b chybne klasifikovaných vzoru z testovací množiny)
42
Regularizace - upadání vah (weight decay)
Generalizaci lze zlepšit tak, že v síti necháme jen „nutné" neurony a spoje. Možná heuristika spocívá v odstranení malých vah. Penalizací velkých vah dostaneme silnejší indikaci duležitosti vah.
V každém kroku ucření zmenšíme umeřle všechny váhy
= (1 _ awT1) +Awf})
Idea: Neduležité váhy budou velmi rychle klesat k 0 (potom je mužeme vyhodit). Duležité váhy dokážou „pretlacit" klesání a zustanou dostatecne velké.
Toto je ekvivalentní gradientnímu sestupu s konstantní rychlostí ucení e, pokud chybovou funkci modifikujeme takto:
E'(W) = E(W) + y (W •W)
Zde regularizacní clen ^(W • W) penalizuje velké váhy.
43
Praxe - Matice zmätenosti
Confusion matrix
Síť má za úkol klasifikovat objekty do K tříd T1,..., TK. Confusion matrix je tabulka, jejíž pole v /'-tém řádku a j-tém sloupci obsahuje počet objektu z třídy T, které byly klasifikovány jako objekty z třídy Tj.
Example confusion matrix
		Predicted		
		Cat	Dog	Rabbit
Actual	Cat	5	3	0
	Dog	2	3	1
	Rabbit	0	2	11
Zdroj: http://en.wikipedia.org/wiki/Confusion_matrix
44