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)
i
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
Vícevrstvá síť
Aktivní dynamika:
► vnitřní potenciál neuronu j:
ti=E wJiYi
*■ aktivační funkce as pro neuron y je libovolná diferencovatelná funkce (upřesním později)
► Stav nevstupního neuronu j e Z \ X po skončení výpočtu je
Ti = ofá)
(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.
3
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
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 ř-tém kroku (zde ř = 1,2,...) je      vypočteno takto:
p       p ji
kde
Aw{t) = -e(t)-^-(w^)
je změna váhy w,, v ř-tém kroku a 0 < e(t) < 1 je rychlost učení v ř-tém kroku.
Všimněte si, že je komponenta gradientu VE, tedy změnu vah v
f-tém kroku lze zapsat také takto: w(í) =        - e(t) ■ VE(w(M)).
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 ř-tém kroku (zde ř = 1,2,...) je      vypočteno takto:
kde
ji      v; dwj-r 11
kde k = ((ŕ - 1) mod p) + 1 a 0 < e(t) < 1 je rychlost učení v ř-tém kroku.
Lze použít i stochastickou verzi tohoto algoritmu, v níž je k voleno náhodně z {1,.. .,p}.
Vícevrstvá síť - gradient chybové funkce
Pro každé w,, máme
dwJi ~ dWi' kde pro každé k = 1,..., p platí dEk dEk
a pro každé j e Z\X dostaneme
— =yj- dkj pro y e 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é y e Z pak
^■) = W- yy)
a dostaneme přesně gradient z minulé přednášky. Pokud a/(£) = a • tanh(r> • £y) pro každé j e Z pak
aý(^) = ^(a-y/)(a + yy)
Ilustrace gradientního sestupu - XOR
Zdroj: Pattern Classification (2nd Edition); Richard O. Duda, Peter E. Hart, David G. Stork
Praktické otázky gradientního sestupu
► Otázky týkající se efektivity učení:
► Dávkový nebo online algoritmus?
► Je nutné data předzpracovat?
► Jak volit iniciální váhy?
► Je nutné vhodně volit požadované hodnoty sítě?
► Jak volit rychlost učení e (t) ?
► Dává gradient nejlepší směr změny vah?
► Otázky týkající se výsledného modelu:
► Kdy zastavit učení?
► Kolik vrstev sítě a jak velkých?
► Jak velkou tréninkovou množinu použít?
► Jak zlepšit vlastnosti (přesnost a schopnost generalizace) výsledného modelu?
10
Poznámky o konvergenci gradientního sestupu
► Chybová funkce může být velmi komplikovaná:
► může obsahovat mnoho lokálních minim, učící algoritmus v nich může skončit
► může obsahovat mnoho „plochých" míst s velmi malým gradientem, zejména pokud se aktivační funkce tzv saturují (tedy jejich hodnoty jsou blízko extrémům; v případě sigmoidálních funkcí to znamená, že mají velké argumenty)
► může obsahovat velmi strmá místa, což vede k přeskočení minim gradientním sestupem
► pro velmi malou rychlost učení máme větší šanci dokonvergovat do lokálního minima, ale konvergence je hodně pomalá
Teorie: pokud e(t) = { pak dávkový i stochastický gradientní sestup konvergují k lokálnímu minimu (nicméně extrémně pomalu).
► pro příliš velkou rychlost učení může vektor vah střídavě přeskakovat minimum nebo dokonce divergovat
radientní sestup - ilustrace
Gradientní sestup s malou rychlostí učení:
>
Více méně hladká křivka, každý krok je kolmý na vrstevnici.
Obrázek: Neural Computation, Dr John A. Bullinaria
Gradientní sestup - ilustrace
Gradientní sestup s příliš velkou rychlostí učení:
-►
Jednotlivé kroky přeskakují minimum, učení je pomalé.
Obrázek: Neural Computation, Dr John A. Bullinaria
13
Gradientní sestup - ilustrace
Online učení:
-►
Kroky nemusí být kolmé na vrstevnice, může hodně kličkovat.
Obrázek: Neural Computation, Dr John A. Bullinaria
Dávkový vs online učící algoritmus
Výhody dávkového:
realizuje přesně gradientní sestup pro chybovou fci (většinou konverguje k lokálnímu minimu)
snadno paralelizovatelný (vzory je možné zpracovávat odděleně) Nevýhody dávkového:
► paměťová náročnost (musí si pamatovat chyby všech vzorů)
► redundantní data nepřidávají informaci ke gradientu. Výhody online (stochastického)
► stochastický má šanci uniknout z okolí mělkého minima (protože nerealizuje přesný grad. sestup)
► má menší paměťovou náročnost a snadno se implementuje
► je rychlejší, zejména na hodně redundantních datech Nevýhody online (stochastického)
► není vhodný pro paralelizaci
► může hodně „kličkovat" (více než gradientní sestup)
15
Moment
Problémy s gradientním sestupem:
► Může se stát, že gradient VE(vvW) neustále mění směr, ale chyba se postupně zmenšuje.
Toto často nastává, pokud jsme v mělkém údolí, které se mírně svažuje jedním směrem (něco jako U-rampa pro snowboarding, učící algoritmus potom opisuje dráhu snowboardisty)
► Online algoritmus také může zbytečně kličkovat. Tento algoritmus se vůbec nemusí pohybovat ve směru největšího spádu!
Řešení: Ke změně vah dané gradientním sestupem přičteme část změny v předchozím kroku, tedy definujeme
Aw(í)=Aií<')+a'Aiv(M) ji ji
kde 0 < a < 1.
16
17
Volba aktivační funkce
Požadavky na vhodnou aktivační funkci a(E,)\
1. diferencovatelnost (jinak neuděláme gradientní sestup)
2. nelinearita (jinak by vícevrstvé sítě byly ekvivalentní jednovrstvým)
3. omezenost (váhy a potenciály budou také omezené => konečnost učení)
4. monotónnost (lokální extrémy fce a zanáší nové lokální extrémy do chybové funkce)
5. linearita pro malé £ (umožní lineární model, pokud stačí k řešení úlohy)
Sigmoidální funkce splňují všechny požadavky.
Síť se sigmoidálními funkcemi obvykle reprezentuje data distribuované (tj. více neuronů vrací větší hodnotu pro daný vstup).
Později se seznámíme se sítěmi, jejichž aktivační funkce porušují některé požadavky (Gaussovy funkce) - používá se jiný typ učení.
18
Volba aktivační funkce
► Z hlediska rychlosti konvergence je výhodné volit lichou aktivační funkci.
► Standardní sigmoida není lichá, vhodnější je použít hyperbolický tangens:
a(£) = 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 důvodů budeme dále předpokládat, že všechny aktivační funkce jsou tvaru
a;(£;) = a-tanh(*>■£;)
kde a = 1.7159 a b = §.
19
Volba aktivační funkce
Volba aktivační funkce
Volba aktivační funkce
1-2—I
1.0
0.8
0.6
0.4
0.2
0.0
první derivace funkce a(£) = 1.7159 • tanh(| • £)
Volba aktivační funkce
Předzpracování vstupů
► Některé vstupy mohou být mnohem větší než jiné
Př.: Výška člověka vs délka chodidla (oboje v cm), maximální rychlost auta (v km/h) vs cena (v Kč), apod.
► Velké komponenty vstupů ovlivňují učení více, než ty malé. Navíc příliš velké vstupy mohou zpomalit učení.
► Numerická data se obvykle normalizují tak, že mají
► průměrnou hodnotu — 0 (normalizace odečtením průměru)
► rozptyl — 1 (normalizace podělením směrodatnou odchylkou)
Zde průměr a směrodatná odchylka mohou být odhadnuty z náhodného vzorku (např. z tréninkové množiny).
► Jednotlivé komponenty vstupu by měly mít co nejmenší korelaci (tj. vzájemnou závislost).
(Metody pro odstranění korelace dat jsou např. analýza hlavních komponent (Principal Component Analysis, PCA). Lze ji implementovat i pomocí neuronových sítí (probereme později)).
24
I n i c i á I n i volba vah
► Iniciálně jsou váhy nastaveny náhodně z daného intervalu [-w, w] kde w závisí na počtu vstupů daného neuronu. Jaké je vhodné w?
*■ Uvažujeme aktivační funkci 1.7159 • tanh(| • £) pro všechny neurony.
► na intervalu [-1,1 ] se a chová téměř lineárně,
► extrémy a" jsou přibližně v bodech -1 a 1,
mimo interval [-4,4] je a blízko extrémních hodnot. Tedy
► Pro velmi malé w hrozí, že obdržíme téměř lineární model (to bychom mohli dostat s použitím jednovrstvé sítě). Navíc chybová funkce je velmi plochá v blízkosti 0 (malý gradient).
► Pro w mnohem větší než 1 hrozí, že vnitřní potenciály budou vždy příliš velké a síť se nebude učit (gradient chyby E bude velmi malý, protože hodnota sítě se téměř nezmění se změnou vah).
Chceme tedy zvolit w tak, aby vnitřní potenciály byly zhruba z intervalu [-1,1].
25
I n i c i á I n i volba vah
► Data mají po normalizaci (zhruba) nulovou střední hodnotu, rozptyl (zhruba) 1 a předpokládejme, že jednotlivé komponenty vstupů jsou (téměř) nekorelované.
► Uvažme neuron j z první vrstvy s d vstupy, předpokládejme, že jeho váhy jsou voleny uniformně z intervalu [-w, w].
► Pravidlo: w je dobré volit tak, že směrodatná odchylka vnitřního potenciálu £y (označme ji oj) leží na hranici intervalu, na němž je aktivační funkce os téměř lineární tj. v našem případě chceme os « 1.
► Totéž funguje pro vyšší vrstvy, d potom odpovídá počtu neuronů ve vrstvě o jedna nižší.
(Zde je důležité, že je aktivační funkce lichá)
► Z našich předpokladů plyne Oj = y^f • tj. v našem prípade polozíme w = -*=.
• w.
26
Požadované hodnoty
Požadované hodnoty by měly být voleny v oboru hodnot aktivačních funkcí, což je v našem případě [-1.716,1.716].
► Požadované hodnoty příliš blízko extrémům +1.716 způsobí, že váhy neomezeně porostou, vnitřní neurony budou mít velké potenciály, gradient chybové funkce bude malý a učení se zpomalí.
► Proto je vhodné volit požadované hodnoty z intervalu [-1.716 + 6,1.716 - 6]. Optimální je, když tento interval odpovídá maximálnímu intervalu na němž jsou aktivační fce lineární. Tedy v našem případě 5 « 0.716, tj. hodnoty dkj je dobré brát z intervalu [-1,1].
Rychlost učení
Obecné zásady pro volbu a změny rychlosti učení e *- Je dobré začít s malou rychlostí (např. £ = 0.1).
► Pokud se chyba znatelně zmenšuje (učení konverguje), můžeme rychlost nepatrně zvýšit.
► Pokud se chyba zjevně zvětšuje (učení diverguje), můžeme rychlost snížit.
*- Krátkodobé zvýšení chyby nemusí nutně znamenat divergenci.
E
Obr. 2.3: Typický vývoj chyby v čase při učení pomocí backpropagatíon.
28
Rychlost učení
Chceme, aby se neurony učily pokud možno stejně rychle. Více vstupů obvykle znamená rychlejší učení.
Pro každou váhu Wp můžeme mít zvláštní rychlost učení ep
*■ ej, lze iniciovat např. 1 /\j^\, kde |y'^| je počet vstupů neuronu j.
► Po zahájení učení váhu zvolna zvyšujeme
(třeba £;,(r) = Ke,(t - 1) kde K > 1)
► Jakmile se změní znaménko Av/ř^ (tedy Awjř~1^ • Awjp < 0), váhu snížíme (třeba takto £;/(f) = Í£yř(t - 1))
29
Rychlost a směr - přesněji
Na gradientní sestup se můžeme dívat obecněji takto:
AwW = r(ř) • s(ř)
kde r(t) je rychlost změny vah a s(ř) je směr změny vah. V našem případě: r(ř) = e(t) a s(ř) = -VE(w(ř~1)) (nebo s(ř) = -VE/<(w(ř~1)) pro online učení).
► Ideální by bylo volit r(t) tak, abychom minimalizovali E(w(ř"1) + r(ř)-s(ř)).
Nebo se aspoň chceme přesunout (ve směru s(ř)) do místa, v němž začne gradient opět růst.
► Toho lze (přibližně) dosáhnout malými přesuny bez změny směru - nedostaneme ovšem o mnoho lepší algoritmus než standardní grad. sestup (který stále mění směr).
► Existují lepší metody, např. parabolická interpolace chybové funkce.
Rychlost a směr - parabolická interpolace
Označme E(r) = E(w(ř_1) + r ■ s(ř)); minimalizujeme E(r
Předpoklá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
Rychlost a směr - parabolická interpolace
Parabolickou interpolaci lze dále iterovat, čímž dosáhneme ještě lepšího odhadu:
Je jasné, že E(B) > £(D) a £(C) > £(D). Pokud £(6) > £(D)
lze použít stejný postup jako předtím
(jinak je nutné nalézt nový bod B' t. ž. E(B') > E(D)).
Optimální směr
Zbývá otázka, jestli je záporný gradient správným směrem. Rychlost r(t) jsme volili tak, abychom minimalizovali
E(wW)  =  E(w^ + r(ř)-s(ř))
=  E(^ř-1) + r(ř)-(-VE(^ř"1)))
To ovšem znamená, že derivace E(vvW) podle r(t) (zde bereme r(ř) jako nezávislou proměnnou) bude 0, tedy
f<*("> - E||(*(')>-(-||<*('-,)>)
= VE(w(ř))-(-VE(w(ř"1))) = 0
Tj. nový a starý směr jsou vzájemně kolmé, výpočet tedy „kličkuje".
Gradientní sestup s optimální rychlostí
Rychlost a směr - přesněji
Řešení: Do nového směru zahrneme částečně i předchozí směr a tím zmenšíme kličkování.
s(ř) = -VE(w(ř-1)) + jg-s(ř-1)
Jak určit j3 ? Metoda sdružených gradientů je založena na tom, že nový směr by měl co nejméně kazit minimalizaci dosaženou v předchozím směru. Chceme nalézt nový směr s(ř) takový, že gradient funkce funkce E v novém bodě vy(0 = vv(ř_1) + r(t) ■ s(ř) ve starém směru s(ř - 1) je nulový:
s(r-1)-VE(wW) = 0
Vhodné j3, které to splňuje je dáno následujícím pravidlem (Polak-Ribiere):
_ (VE(wW) - VE(vy(ŕ~1))) ■ VE(wW) ^ ~ VE(w(ř"1))-VE(w(ř-1)) (Pokud by £ byla kvadratická funkce, pak to konverguje v nejvýše n krocích)
35
Existuje mnoho metod druhého řádu, které jsou přesnější, ale obvykle výpočetně mnohem náročnější (příliš se nepoužívají). Např. Newtonova metoda, Levenberg-Marquardt, atd.
Většina těchto metod vyžaduje výpočet (nebo aspoň aproximaci) druhé derivace chybové funkce nebo funkce sítě (tj. Hessián).
Lze nalézt v literatuře, např.
Haykin, Neural Neworks and Learning Machines
Schopnost generalizace
V klasifikačních problémech se dá generalizace popsat jako schopnost vyrovnat se s novými vzory.
Pokud síť trénujeme na náhodně vybraných datech, není ideální přesně klasifikovat tréninkové vzory.
Pokud aproximujeme funkční závislost vstupů a očekávaných výstupů pak obvykle nechceme aby funkce sítě vracela přesné hodnoty pro tréninkové vzory.
Exaktněji: Obvykle se předpokládá, že tréninková množina byla generována takto:
dkj = 9i(xk) + Qkj
kde gs je „správná" funkce výstupního neuronu j e Y a O q je náhodný šum. Chceme, aby síť pokud možno realizovala funkce gs.
38
Kdy zastavit učení?
Standardní kritérium: Chyba E je dostatečně malá.
Další možnost: po několik iterací je gradient chyby malý.
(Výhodou tohoto kritéria je, že se nemusí počítat chyba £)
Problém: Příliš dlouhé učení způsobí, že síť „opisuje" tréninkové vzory (je přetrénovaná). Důsledkem je špatná generalizace.
Řešení: Množinu vzorů rozdělíme do následujících množin
► tréninková (např. 60%) - podle těchto vzorů se síť učí
► validační (např. 20%) - používá se k zastavení učení.
► testovací (např. 20%) - používá se po skončení učení k testování přesnosti sítě, tedy srovnání několika natrénovaných sítí.
39
Trénink, testování, validace
Obvykle se realizuje několik iterací (cca 5) tréninku na tréninkové množině. Poté se vyhodnotí chyba E na validační množině.
Ideálně chceme zastavit v minimu chyby na validační množině. V praxi se sleduje, zda chyba na validační množině klesá. Jakmile začne růst (nebo roste po několik iterací za sebou), učení zastavíme.
Problém: Co když máme příliš málo vzorů?
Můžeme tréninkovou množinu rozdělit na K skupin S-i,..., Sk-Trénujeme v K fázích, v i-\é fázi provedeme následující:
► trénujeme na    u ... u Sŕ_-| u Sŕ+1 u ... u SK
*■ spočteme chybu ee funkce E na skupině Se
Celková chyba je potom průměr e = ^ ee.
Extrémní verze: K = počet vzorů (používá se při extrémně málo vzorech)
40
Velikost sítě
Podobný problém jako v případě délky učení:
► Příliš malá síť není schopna dostatečně zachytit tréninkovou množinu a bude mít stále velkou chybu
► Příliš velká síť má tendenci přesně opsat tréninkové vzory - špatná generalizace
Řešení: Optimální počet neuronů :-)
► teoretické výsledky existují, ale jsou většinou nepoužitelné
► existují učící algoritmy, které postupně přidávají neurony (konstruktivní algoritmy) nebo odstraňují spoje a neurony (prořezávání)
► V praxi se počet vrstev a neuronů stanovuje experimentálně (prostě se to zkusí, uvidí, opraví) a/nebo na základě zkušeností.
41
Velikost sítě
Uvažme dvouvrstvou síť. Neurony ve vnitřní vrtvě často reprezentují "vzory" ve vstupní množině.
Př.: Síť 64-2-3 pro klasifikaci písmen:
sample training patterns
							~~l
							
							
							
							
							
							
							
learned input-to-hidden weights
Velikost tréninkové množiny
Příliš malá nebo nereprezentativní tréninková množina vede ke špatné generalizaci
Příliš velká zvyšuje složitost učení. V případě dávkového algoritmu způsobuje velkou chybu (chyby na vzorech se sčítají), což může vést k přetrénování.
Pravidlo pro klasifikační úlohy: počet vzorů by měl zhruba odpovídat W/ô kde
► W je počet vah v síti
► 0 < ô < 1 je tolerovaná chyba na testovací množině
(tj. tolerujeme ô chybně klasifikovaných vzorů z testovací množiny)
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 spočívá v odstranění malých vah. Penalizací velkých vah dostaneme silnější indikaci důležitosti vah.
V každém kroku učení zmenšíme uměle všechny váhy
wf) = (1 - + Awf))
Idea: Nedůležité váhy budou velmi rychle klesat k 0 (potom je můžeme vyhodit). Důležité váhy dokážou „přetlačit" klesání a zůstanou dostatečně velké.
Toto je ekvivalentní gradientnímu sestupu s konstantní rychlostí učení £, pokud chybovou funkci modifikujeme takto:
E'(w) = E(w) + ^(w- w)
Zde regularizační člen ^(w-w) penalizuje velké váhy.
44
Praxe - Matice zmätenosti
Confusion matrix
Síť má za úkol klasifikovat objekty do K tříd Ti,..., TK. Confusion matrix je tabulka, jejíž pole v Mém řádku a y-tém sloupci obsahuje počet objektů z třídy Tf, které byly klasifikovány jako objekty z třídy Ty.
Example confusion matrix
		Predicted		
		Cat	Dog	Rabbit
	Cat	5	3	0
Actual	Dog	2	3	1
	Rabbit	0	2	11
Zdroj: http://en.wikipedia.org/wiki/Confusion_matrix
45