Aplikace vícevrstvých sítí ► Diagnostika v medicíně ► Predikce časových řad ► ALVINN ► Rozpoznávání směrovacích čísel ► Komprese dat Zdroj: Fundamentals of Artificial Neural Networks. Mohamad H. Hassoun, The MIT Press Diagnostika pomocí neuronových sítí Database Cleaning Out her (s) elimination Features selection i Patients data collection DATABASE building I Preprocessing ANN training and verification YES TRAINING NO Verified DATABASE ANN and DATABASE 1 Diagnosis Evaluation by Medical doctor Positive Negativ* uncertain VES DIAGNOSU 2 Diagnóza srdečního infarktu ► infarkt není jednoduché diagnostikovat ► expert (údajně) pozná infarkt ve zhruba 88% případů, planý poplach nastává ve zhruba 29%. ► neuronové sítě to počátkem devadesátých let zvládly lépe Organizační dynamika: ► Třívrstvá síť 41 -10-10-1 ► Vstupy jsou různé atributy pacientů přijatých na kardiológii: ► např. věk, pohlaví, nevolnost, zvracení, dusnost, cukrovka, vysoký tlak, ... ► binární vstupy jako např. přítomnost cukrovky nebo pohlaví jsou kódovány pomocí 0 a 1 ► ostatní jsou normalizovány do intervalu [0,1] Aktivní dynamika: ► aktivační funkce: standardní logistické sigmoidy Diagnóza srdečního infarktu Adaptivní dynamika: trénink: ► tréninková množina obsahovala 356 pacientů, 236 bez infarktu, 120 s infarktem ► gradientní sestup na náhodně vybrané polovině pacientů (půl s a půl bez infarktu) ► očekávané výstupy 1 nebo 0 podle toho, zda pacient měl či neměl infarkt výsledky: ► testováno na 178 pacientech, kteří nebyli součástí tréninkové množiny (60 s infarktem, 118 bez) ► 92% korektní identifikace infarktu (oproti 88% u expertů) ► 4% falešný poplach (oproti 29% u expertů) Existuje velké množství podobných aplikací neuronových sítí v diagnostice, viz. např. http://jab.zsf.jcu.ez//ll_2/havel.pdf Predikce časových řad Např. se jedná o předvídání vývoje počasí, hodnot akcií, měnových kurzů, počtu zákazníků apod. (hrubá) matematická formulace: ► Mějme numerickou řadu x[1 ],x[2],x[3],... (např. hodnota koruny vůči euru po jednotlivých dnech) ► Chceme odhadnout x[i + 1] na základě x\l\x\l- 1],...,x[£-fc] Uvažme síť s k vstupními a jedním výstupním neuronem. Tuto síť natrénujeme na části řady tak, že jí budeme předkládat x[ť\, x\l-\\,...,x\l- k] na vstupy ax[f+1] očekávaný výstup. (V případě měnových kurzů použijeme historii vývoje cen za minulé období.) Sítě pro predikci časových řad se obvykle rozšiřují o další vlastnosti: ► další vstupy modelující prostředí v němž se řada vyvíjí (např. hospodářské parametry státu), chyby předchozích odhadů (ARMA(p,q) a další metody) ► výstup se často vrací zpět jako další vstup, čímž lze dosáhnout predikce na více kroků ARMA(p,q) ilustrace o -o ■40 subtract A ftř-3] Te[t - 1] :[i-3] r[ť-2] »[* - 1] 7 ALVINN Organizační dynamika: ► vícevrstvá síť, 960 - 4 - 30 (někdy 960 - 5 - 30) ► komponenty vstupu odpovídají bodům obrazu z kamery Aktivní dynamika: ► aktivační funkce: skryté neurony mají sigmoidální funkce, výstupní mají lineární ► Směr jízdy odpovídá těžišti všech výstupních neuronů tj. výstupní neurony lze uvažovat jako hmotné body umístěné na přímce se stejným rozestupem, hmotnost neuronu se rovná jeho hodnotě Adaptivní dynamika: Trénováno za jízdy. ► Aktuální výhled na silnici snímán kamerou, zhruba 25 obrazů za vteřinu ► Tréninkové vzory tvaru (Xk.dk) kde ► Xk = obraz silnice ► dk = příslušné natočení volantu řidiče ► natočení volantu distribuováno pomocí Gaussova rozložení na výstupy: dki = e-°f/10 kde Dj je vzdálenost Mého výstupu od toho, který odpovídá natočení volantu (Toto je lepší než binární výstup, protože reakce na podobné silnice jsou velmi blízké.) Výběr vzorů Naivní přístup: brát vstupy z kamery a podle nich adaptovat. To vede k následujícím problémům: ► Jestliže řidič jede dobře, síť se nenaučí řešit odchylky od trasy Možná drsná řešení jsou ► vypnout přechodně učení a sjet z trasy, poté zapnout učení a nechat síť sledovat, jak se s tím řidič vyrovná ► nechat řidiče jezdit divoce (poněkud nebezpečné, drahé, nespolehlivé) ► aktuální výhledy z okna jsou poněkud repetitivní, síť se může přetrénovat na málo vzorech 10 Výběr vzorů Problém s příliš „správnou" jízdou řidiče se řeší takto: ► každý výhled na silnici je posouváním rozmnožen na 15 podobných kopií Original Image yir/iriHMíMY ► požadovaný výstup se vygeneruje pro každou kopii Repetitivnost aktuálních výhledů z okna se řeší takto: ► systém má buffer 200 obrázků (včetně 15 kopií aktuálního), v každém kole tréninku se trénuje na těchto vzorech ► po tréninku se sejme nový obraz, udělá se 15 kopií a těmi se nahradí 15 obrazů z bufferu (10 s nejmenší chybou, 5 náhodně) ALVINN - učení ► standardní zpětná propagace ► konstantní rychlost učení pro každý neuron zvlášť, úměrná počtu vstupů ► pomalu rostoucí moment Výsledek: ► Trénink trval 5 minut, řidič jel rychlostí 4 míle za hodinu ► ALVINN byl schopen jet i po částech silnice, které nikdy „neviděl" a za rozličného počasí ► v době vzniku byl schopen jet maximální rychlostí, kterou zvládal hydraulický ovladač 12 ALVINN - vývoj vah h2 h3 h4 h5 kolo 0 kolo 10 kolo 20 kolo 50 Zde Aí1 ,..., h5 jsou skryté neurony. 13 ALVINN - komentáře Srovnání ALVINNa s „explicitním programováním". Pro efektivní řízení je potřeba: ► najít vlastnosti obrázků důležité pro řízení (ALVINN najde sám) ► tyto vlastnosti detekovat v aktuálních obrazech (ALVINN si vytvoří vlastní detektory) ► implementovat řízení v reakci na vlastnosti obrázků (ALVINN se to naučí sám od řidiče (rychle)) Nevýhody ALVINNa (později řešené celou škálou rozšíření) ► uměl jezdit jen po jednom typu silnice (různý povrch, počet pruhů, atd.) Později řešeno pomocí slučování více ALVINNů spojených do jedné sítě, každý natrénován na jiný typ silnice (MANIAC) ► nebyl nijak napojen na „vyšší" řízení, například sledování cesty po mapě apod. Řešeno např. včleněním ALVINNa do většího učícího systému. Rozpoznávání směrovacích čísel Cílem je rozpoznat rukou psané číslice ► vstupy: obrázky číslic 16x16, stupně šedi normalizovány do [-1,1] i U / r f k É íf \ 6 7 5 7 ? & 3 4 % ? -2 r 7 9 n / * ^ v e 1 £ I y / ti f 15 á o 1 S<1 2 é f % I ) = Y4>tkdk = XTB /c=1 kde X je matice, která má v i-tém řádku vektor xj a d = (d1/.../dp)T LAS a ortonormální vstupy Pokud jsou ,..., xp ortonormální, tedy xJxí = 0 i±j 1 i = j pak LAS má schopnost reprodukce: wTXi = YjČkdkYxi = dk(x^Xi) = dj k=-\ řc=1 30 LAS a ortonormální vstupy ...a asociace: Uvažme vstup: xr + u kde norma u je malá. Chyba sítě pro r-tý vzor perturbovaný vektorem u: r := \ w (Xr + U) - dr\ = \ W Xr + W U - dr\ = \ W U Pokud dr e {-1,1}, pak r = \W U ( P \ p T L/ ŕc=1 L/ /c=1 /c=1 (Zde první nerovnost plyne z trojúhelníkové nerovnosti, druhá z Cauchyho-Schwarzovy nerovnosti a poslední z p < n, protože mohutnost množiny ortonormálních vektorů v Rn nemůže být větší než n.) Tedy pro vstupy blízké vzorům odpovídá přibližně požadovaným výstupem Hopf ieldova síť ► Definice ► Energetická funkce ► Reprodukce ► Asociace 32 Hopf ieldova síť Autoasociativní síť. Organizační dynamika: ► úplná topologie, tj. každý neuron je spojen s každým ► všechny neurony jsou současně vstupní i výstupní ► označme £1,..., £n vnitřní potenciály a y-i,..., yn výstupy (stavy) jednotlivých neuronů ► označme w}i celočíselnou váhu spoje od neuronu / e {1,..., n] k neuronu j e {1,..., n] ► Zatím: žádný neuron nemá bias a přepokládáme w}} = 0 pro každé j = 1,..., n 33 Hopfieldova síť Adaptivní dynamika: Dána tréninková množina T — [Xk | Xk = (XM,...,Xkn) G {-1, 1}n,/c = 1,. . .,p} Adaptace probíhá podle Hebbova zákona (podobně jako u LAS). Výsledná konfigurace je p /c=1 Všimněte si, že W]-, = wy, tedy matice vah je symetrická. Adaptaci lze vidět jako hlasování vzorů o vazbách neuronů: Wjj = Wjj se rovná rozdílu mezi počtem souhlasných stavů xkj = xkj neuronů / a j a počtem rozdílných stavů xkj ± xkj. Hopf ieldova síť Aktivní dynamika: Iniciálně jsou neurony nastaveny na vstup x = (x-i,..., xn) sítě, tedy = xy- pro každé j = 1,..., n. Cyklicky aktualizujeme stavy neuronů, tedy v kroku ř + 1 aktualizujeme neuron j, t. ž. j = (ř mod p) + 1, takto: nejprve vypočteme vnitřní potenciál n /=1 a poté (ř+1) Hopf ieldova síť - aktivní dynamika Výpočet končí v kroku ŕ* pokud se síť nachází (poprvé) ve stabilním stavu, tj. Věta Za předpokladu symetrie vah, výpočet Hopfieldovy sítě skončí pro každý vstup. Z toho plyne, že Hopfieldova síť počítá funkci z {-1,1}n do {-1,1}n (která závisí na hodnotách vah neuronů). Označme ý(W,x) = (yjř \.. .,y£ř ^ hodnotu funkce sítě pro vstup x a matici vah W. Dále označme yj(W,x) = yfř ^ složku hodnoty funkce sítě, která odpovídá neuronu y. Pokud bude w jasné z kontextu, budu psát jen y(x) a yy(x) 36 Fyzikální analogie (Isingův model) Jednoduché modely magnetických materiálů připomínají Hopfieldovu síť. ► atomické magnety poskládané do mrizky T T T T T ► každý magnet může mít pouze 11111 jednu ze dvou orientací (v T T T T T Hopfieldově síti+1 a-1) í T f T T f * orientaci každého magnetu ovlivňuje lilii jednak vnější magnetické pole * T t f f t (vstup sítě), jednak magnetické pole 11111 ostatních magnetů (závisí na jejich ' T T T T T orientaci) ► synaptické váhy modelují vzájemnou interakci magnetů 37 Energetická funkce Energetická funkce E přiřazuje každému stavu sítě y e {-1,1}n potenciálni energii danou ► stavy s nízkou energií jsou stabilní (málo neuronů „chce" změnit svůj stav), stavy s vysokou energií jsou nestabilní ► tj. velké (kladné) w^yj je stabilní a malé (záporné) w^yj nestabilní V průběhu výpočtu se energie nezvyšuje: E(ý(ŕ)) > E(ý(ŕ+1)), stav ý(r) odpovídá lokálnímu minimu funkce E. n n Energetická plocha Obr. 3.4: Energetická plocha. 39 Hopfield - příklad Y2 E 1 1 1 1 1 1 -1 1 1 -1 1 -3 1 -1 -1 1 -1 1 1 1 -1 1 -1 -3 -1 -1 1 1 -1 -1 -1 1 ► Hopfieldova síť se třemi neurony ► naučili jsme ji jeden vzor (1,-1,1) pomocí Hebbova učení (síť se automaticky „naučila" i vzor (-1,1,-1)) Energetická funkce - konvergence výpočtu sítě Pomocí pojmu energie lze snadno dokázat, že výpočet Hopfieldovy sítě vždy zastaví: ► v průběhu výpočtu se energie nezvyšuje: E(ýW)>E$^) ► pokud dojde v kroku t + 1 ke změně stavu, pak E(ýW)>E$^) ► existuje pouze konečně mnoho stavů sítě: výpočet dosáhne lokálního minima funkce E, ze kterého už se nedostane 41 Hopfieldova síť - odučování Při učení podle Hebbova zákona mohou vznikat lokální minima funkce E, tzv. nepravé vzory (fantomy), které neodpovídají tréninkovým vzorům. Fantomy je možné odučovat např. pomocí následujícího pravidla: Mějme fantom (x-i,...,xn) e {-1,1}n a váhy w}h pak nové váhy wj. spočítáme pomocí Wjj = Wji - XíXj (tj. podobně jako při adaptaci podle Hebbova zákona, ale s opačným znaménkem) 42 Reprodukce - statistická analýza Kapacita Hopfieldovy paměti je dána poměrem p/n. Zde n je počet neuronů a p je počet vzorů. Předpokládejme, že tréninkové vzory jsou voleny náhodně takto: při volbě xk volím postupně (nezávisle) jednotlivé složky (1 s pravd. 1 /2 a -1 s pravd. 1 /2). Uvažme konfiguraci W, kterou obdržíme Hebbovským učením na zvolených vzorech. Označme p = p[Zk=ý(W,)tk)prok = Jl,...,p\ Pak pro n -> oo a p < n/(4 log n) dostaneme /3 —> 1. Tj. maximální počet vzorů, které lze věrně uložit do Hopfieldovy paměti je úměrný n/(4 log n). 43 Hopf ieldova síť - asociace Problém: ► příliš mnoho vzorů implikuje existenci lokálních minim funkce E, která neodpovídají vzorům (tzv. fantomy) ► lokální minima pro vzory mohou dokonce zanikat Podrobná analýza ukazuje následující ► Pro p < 0.138n tréninkové vzory zhruba odpovídají lokálním minimům funkce E ► Pro p > 0.138n lokální minima podobající se vzorům zanikají (ostrá nespojitost v 0.138) ► Pro p < 0.05n energie stavů podobajících se tréninkovým vzorům odpovídají globálním minimům E a fantomy mají ostře větší energii Tj. pro dobré zapamatování 10 vzorů je potřeba 200 neuronů a tedy 40000 spojů ohodnocených celočíselnými váhami Pozn. Nevýhodou Hopfieldovy sítě je deterministický výpočet, který může skončit v mělkém lokálním minimu E bez možnosti uniknout. Tento problém částečně vyřeší stochastická verze aktivní dynamiky. kódování číslice 12x10 bodů (120 neuronů, -1 je bílá a 1 je černá) naučeno 8 číslic vstup vygenerován ze vzoru 25% šumem obrázek ukazuje postup výpočtu Hopfieldovy sítě 45 Hopf ieldova síť - příklad obnovení vzoru Hopfieldova síť - příklad rekonstrukce vzoru 47 Hopfieldova síť (pro optimalizační úlohy) Autoasociativní síť. Organizační dynamika: ► úplná topologie, tj. každý neuron je spojen s každým ► všechny neurony jsou současně vstupní i výstupní ► označme £1,..., £n vnitřní potenciály a y-i,..., yn výstupy (stavy) jednotlivých neuronů ► označme w}i celočíselnou váhu spoje od neuronu / g {1,..., n] k neuronu j e {1,..., n}. ► přepokládáme w}} = 0 pro každé j = 1,..., n. ► Nyní: ► každý neuron má bias 0/ ► stavy neuronů jsou z {0,1} Hopf ieldova síť (s biasy) Aktivní dynamika: Iniciálně jsou neurony nastaveny na vstup x = (x-i,..., xn) e {0,1 }n sítě, tedy y|0) = xy pro j = 1,..., n. V kroku t + 1 aktualizujeme neuron j, t. ž. j = (ř mod p) + 1, takto: nejprve vypočteme vnitřní potenciál n /=1 a poté (í+1) _ i = < 1 ^> 0 (0 v ď} > o ^ < o Hopf ieldova síť - aktivní dynamika Výpočet končí v kroku ŕ* pokud se síť nachází (poprvé) ve stabilním stavu, tj. >,<<'«>«•) 0.=1.....n) Energetická funkce E přiřazuje každému stavu sítě y e {0,1 }n potenciální energii danou n n n E^= ~l ÍL ÍL wiiyiyi+ÍL6iYi 2 y=1 /=1 /=1 V průběhu výpočtu se energie nezvyšuje: E(ý(ř)) > E(ý(ř+1)), stav ý(r) odpovídá lokálnímu minimu funkce E. Věta Za předpokladu symetrie vah, výpočet Hopfieldovy sítě skončí pro každý vstup. (Důkaz stejný jako předtím) 50 Hopfieldova síť a optimalizační úlohy Optimalizační úloha je zadána množinou přípustných řešení a účelovou funkcí. Cílem je nalézt přípustné řešení, které minimalizuje účelovou funkci U. Pro mnoho optimalizačních úloh lze nalézt Hopfieldovu síť takovou, že ► minima E « přípustná řešení vzhledem k U ► globální minima E « řešení minimalizující U Cílem je nalézt globální minimum funkce E (a tedy i U). Příklad: multiflop Cílem je nalézt vektor z {0,1 }n, který má všechny složky nulové kromě právě jedné. Definujeme účelovou funkci U : {0,1 }n —> IR takto: U(Ü) = in \ Z Ui VV/=1 J \ - 1 Požadované vektory jsou právě minima této funkce Ale , n n /=i a tedy L/(u) - 1 je energetickou funkcí sítě (viz. následující slajd). , n n E(Ü) = --^(-2)uiuj + YJ(-l)Ui i±j /=1 53 Příklad: n věží Cílem je rozmístit n věží na šachovnici nx n tak, aby se vzájemně neohrožovaly. Definujeme účelovou funkci : {0,1} n-n R: n ŕ n \ U Ji - 1 aU2:|0,1) n-n vV/=1 / R: 7 n ^)=E E /=i v n U 'Ji U=1 \2 - 1 7 Požadované vektory jsou právě minima funkce U = l/| + L/2. Minima 1/ odpovídají stavům s minimální energií v následující síti. 54 Příklad: n věží (síť) E(ú) = U(ú) - 2n (Tento příklad se dá zobecnit na problém obchodního cestujícího) Hopfieldova síť a lokálni minima Hledáme (globální) minima energie E .... Problém: není jasné, v jakém stavu začít, abychom dosáhli globálního minima. Síť může skončit v mělkém minimu. Řešení: V každém stavu umožníme s malou pravděpodobností přechod do stavů s vyšší energií. Tuto pravděpodobnost budeme postupně snižovat. Využijeme dynamiku Boltzmannova stroje ... ,Boltzmannovská'' aktivní dynamika Aktivní dynamika: Stavy neuronů jsou iniciálně nastaveny hodnoty z množiny {0,1}, tj. y|0) e {0,1} pro y e {1,..., n}. V kroku t + 1 aktualizujeme náhodně vybraný neuron j g {1,..., n} takto: nejprve vypočteme vnitřní potenciál a poté náhodně zvolíme hodnotu y; } e {0,1} tak, že /=1 kde fé) 1 + e-umt) Parametr T(ř) se nazývá teplota v čase ř. ► Velmi vysoká teplota T(f) znamená, že se chová téměř (uniformně) náhodně. 1 ~ i a síť ► Velmi nízká teplota T(f) znamená, že buď P[yy-ř+1^ = i] ~ 1 nebo P [yjt+^ = i] ~ 0 v závislosti na tom, jestli ^ > 0 nebo EJp < 0. Potom se sít chová téměř deterministicky (tj. jako v původní aktivní dynamice). Poznámky: ► Boltzmannovská aktivní dynamika funguje jako deterministická dynamika s náhodným šumem, ► energie E(ý) = -\£yn=1 2X1 vi^y,- + Eľ=i 0,-// se může (s pravděpodobností závislou na teplotě) zvýšit, pravděpodobnost přechodů do vyšší energetické hladiny se exponenciálně zmenšuje s velikostí energetického skoku. Simulované žíhání Následujícím postupem lze dosáhnout globálního minima funkce E: ► Na začátku výpočtu nastavíme vysokou teplotu T(r) ► Teplotu postupně snižujeme, např takto: ► T(ř) = rf • 7(0) kde r\ < 1 je blízko 1 ► nebo T(ř) = T(0)/log(1 + ř) Lze dokázat, že při vhodném postupu chlazení dosáhneme globálního minima. Pozn: ► Tento proces je analogií žíhání používané při výrobě tvrdých kovových materiálů s krystalickou strukturou: materiál se nejprve zahřeje, čímž se poruší vazby mezi atomy, v průběhu následného pomalého chlazení se materiál „usadí" do stavu s minimální vnitřní energií a s pravidelnou vnitřní strukturou. ► Jedná se také o rozšíření fyzikální motivace Hopfieldovy sítě: orientace magnetů jsou ovlivněny nejen vnitřním a vnějším magnetickým polem, ale také termálními fluktuacemi.