Vícevrstvá síť Organizační dynamika: Výstupní Skryté Vstupní OD 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 kroku ř + 1 (zde ř = 0,1,...) 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 f + 1 kroku lze zapsat také takto: w(í+1) = w(í) - e(t) ■ V£( 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.o = _e(ř). ^>«) kde k = (ř 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}. 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 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(wW) (nebo s(ř) = -VE/<(wW) pro online učení). ► Ideální by bylo volit r(t) tak, abychom minimalizovali + 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(t) + r ■ s(ř)); minimalizujeme E(r). ^0 Předpokládejme, že jsme schopni nalézt body A, B, C takové, že E(A) > E(B) a £(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(w<ř+1)) = E(wW + r(ř)-s(ř)) = E(wW + r(t)-{-VE(wW)) To ovšem znamená, že derivace E(w(ř+1)) podle r(t) (zde bereme r(ř) jako nezávislou proměnnou) bude 0, tedy brK tyf bwSj \ bwSj 7 = VE(w<ř+1)) • (-VE(w«)) = 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(wM)+j3-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ě vv(ř+1) = vvW + r(t) ■ s(ř) ve starém směru s(ř - 1) je nulový: s(ř-1)-VE(w(ř+1)) = 0 Vhodné j3, které to splňuje je dáno následujícím pravidlem (Polak-Ribiere): _ (VE(vy(r+1)) - VE(w(r))) • VE(vy(r+1)) ^~ VE(w(0).VE(w(0) (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 vvf1) = (1-q(vf+ Avvf) 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