Postavení neuronových sítí v informatice ► „Vyjadřovací" schopnosti neuronových sítí ► logické funkce ► nelineární separace ► spojité funkce - algoritmická vyccíslitelnost ► Srovnání s klasickou architekturou pocítacu ► Implementace i Základní logické funkce Aktivační funkce o je ostrá nelinearita o(í) = y = AND (xi,..., xn) T j -n xo = 1 -> V1 Xi X2 0 xn 1 í > 0 ; 0 í < 0. y = NOT (xi) T xo = 1 ——> o) x1 y = OR (x1,..., xn) T -1 xo = 1 —o) x1 x2 xn 2 Logické funkce - obecne; Věta Nechť o je ostrá nelinearita. Douvrstvé sítě s aktivační funkcí o mohou počítat libovolnou funkci F : {0,1 }n — {0,1}. DUkaz. ► Pro každý vektor v = (v1,..., vn) e {0,1}n definujeme neuron Nv, jehož výstup je roven 1 práve když vstup je v: ► Spojíme výstupy všech neuronu pro než platí F(v) = 1 y 0 pomocí neuronu, který implementuje funkci OR. □ 3 Nelineární separace - ostrá nelinearita q ► Uvažujme trívrstvou sít'; každý neuron má ostrou nelinearitu jako aktivační funkci ► Síť delí vstupní prostor na dva podprostory podle hodnoty výstupu (0 nebo 1) ► První (skrytá) vrstva deií vstupní prostor na poloprostory ► Druhá muže napr. deelat průniky poloprostoru - konvexní oblasti ► Tretí (výstupní) vrstva muže např. sjednocovat konvexní oblasti X2 4 Nelineární separace - ostrá nelinearita - ilustrace q o o ► Uvažujme trívrstvou sít'; každý neuron má ostrou nelinearitu jako aktivační funkci ► Třívrstvásíť muže „aproximovat" libovolnou „rozumnou" množinu P c Rk ► Pokryjeme P hyperkrychlemi(v 2D jsou to čtverečky, v 3D krychle, ...) ► Každou hyperkrychliK lze separovat pomocí dvouvrstvé síte NK (Tj. funkce pocítaná sítí NK vrací 1 pro body z K a 0 pro ostatní) ► Pomocí neuronu, který implementuje funkci OR, spojíme výstupy všech sítí NK t. ž. K n P + 0. Xk 5 Nelineární separace - sigmoida Věta (Cybenko 1989 - neformální verze) Nechť o je spojitá sigmoidální funkce, tedy splňuje Pro každou „rozumnou" množinu P c [0,1]", existuje dvouvrstvá sít' s aktivační funkcí o, která spl"uje následující: Pro „vetšinu" vektoru V e [0,1]n platí V e P práve když výstup této síte je > 0 pro vstup v. Pro matematicky orientované: ► „rozumná" množina je Lebesgueovsky měřitelná ► „vetšina" znamená, že množina špatne klasifikovaných vektoru má Lebesgueovu míru menší než dané e (pro každé e muže být nutné konstruovat jinou sít') 1 pro x — +c» 0 pro x — -oo 6 Nelineární separace - praktická ilustrace Sharp High! ALVINN rídí automobil Sít' má 30 x 32 = 960 vstupních neuronU (vstupní prostor je R960) Vstupy berou stupne šedi jednotlivých obrazových bodu výstupní neurony „klasifikují" obrázky silnice podle zakřivení 30x32 Sensor Input Retina ► Zdroj obrázku: http://jmvidal.cse.sc.edu/talks/ann/alvin.html 7 Aproximace spojitých funkcí - třívrstvé sítě Nechť o je standardní sigmoida, tj. o(í) = Pro každou spojitou funkci f: [0,1]n — [0,1] a ô > 0 zkonstruujeme ťřívrstvou síť poCítající funkci F : [0,1]n — [0,1] takovou, že pro každé v e [0,1]n platí |F(v) - f(v)| < ô. ► Pro zjednodušení nejprve zkonstruujeme sít, která má v nejvyšší vrstve akt. funkci C(£) = £ a ve všech nižších vrstvách „strmou" sigmoidu o(£) = ť+fh kde A je obrovské ccíslo. ► Poté A přesuneme do vah a Z aproximujeme pomocí standardní sigmoidy a velmi malých vah (tj. ve skutecnosti velmi málo strmé sigmoidy). 8 Aproximace spojitých funkcí - třívrstvé sítě y vážený součet „špiček" © hodnota neuronu ■...... v. potenciál ... a další dve rotace o 90 stupnu Xi X2 Zdroj obrázkU: C. Bishop; Neural Networks for Pattern Recognition; ISBN 9780198538646 9 Aproximace spojitých funkcí - dvouvrstvé síte veta (Cybenko 1989) Nechť o je spojitá sigmoidální funkce, tedy splňuje Í1 pro x — +00 o(x) = i 10 pro x — -00 Pro každou spojitou funkci f: [0,1 ]n — [0,1 ] a e > 0 existuje funkce F : [0,1]n — [0,1] poCítaná dvouvrstvou sítí jejíž neurony mají aktivacní funkci o, která splnuje |f(V) - F(V)| < e pro každé V e [0,1 ]n. 10 Výpočetní síla neuronových sítí (vyčíslitelnost) ► Uvažujme cyklické síte ► s obecne reálnýmiváhami; ► jedním vstupním a jedním výstupním neuronem (sít' tedy poCítá funkciF : A — R kde A c R obsahuje vstupy nad kterýmisít' zastaví); ► plne paralelním pravidlem aktivní dynamiky (v každém kroku se aktualizují všechny neurony); *■ aktivaccní funkcí 1 5 > 0 ; 5 0 < 5 < 1; 0 5 < 0. Slova o e {0,1}+ zakódujeme do racionálních ccísel pomocí Ô(M) = L ~2T + 2M+T Pr.: co = 11001 dá b(cú) = 2 + 22 + 25 + 26 (= 0.110011 v dvojkové soustave). ► Výpočetní síla neuronových sítí (vyčíslitelnost) Sít akceptuje jazyk L c {0,1}+ pokud počítá funkci F : A — R (A c R) takovou, že o e L práve když b(co) e A a F(b(co)) > 0. ► Cyklické síte s racionálními váhami jsou ekvivalentní Turingovým strojum ► Pro každý rekurzivne spocetný jazyk L c {0,1}+ existuje cyklická sít' s racionálnímiváhamia s méne než 1000 neurony, která ho akceptuje. ► Problém zastavení cyklické síte s 25 neurony a racionálními váhami je nerozhodnutelný. ► Existuje „univerzální" sít' (ekvivalent univerzálního Turingova stroje) ► Cyklické síte s reálnými váhami jsou silnejší než Turingovy stroje - Pro každý jazyk L c {0,1}+ existuje cyklická sít' s méne než 1000 neurony, která ho akceptuje. 12 Shrnutí teoretických výsledku ► Neuronové síte jsou univerzální výpocetní prostředek ► dvouvrstvé síte zvládají Booleovskou logiku - dvouvrstvé síte aproximují libovolné spojité funkce ► cyklické síte jsou alespon tak silné, jako Turingovy stroje ► Tyto výsledky jsou čistě teoretické ► síte vycházející z obecných argumentu jsou extrémne velké ► je velmi obtížné je navrhovat ► Síte mají jiné výhody a úcel (ucení, generalizace, odolnost, ...) 13 Srovnaní s klasickou architekturou pocitacu Neuronové síte „Klasické" pocítace Data implicitne ve váhách explicitne Výpocet prirozene paralelní sekvencní (obvykle), lokalizovaný Odolnost odolné vuci nepresnosti vstupu a poškození zmeřna jednoho bitu muže znamenat krach výpocřtu Presnost výpoctu nepresný, síť si „vybaví" podobný tréninkový vzor presný Programování uccí se ze vzorového chování je nutné precizne programovat 14 NeuropoCítaCe ► Neuropocítac = hardwarová implementace neuronové síte ► Obvykle jsou to speciální akcelerátory („karty"), které dostávají vstupy z obycejného pocítace a vrací výstupy síte ► Podle typu reprezentace parametru síte rozlišujeme neuropocítace na ► digitální (vetšina, např. Neuricam TOTEM, Philips Lneuro a další casto pouze výzkumné projekty) ► analogové (např. Intel ETANN) ► hybridní (napr. AT&T ANNA) ► Lze pozorovat räzné stupne hardwarových implementací: ► hardware pouze provádí výpocet vnitřních potenciálu (lze provádeřt paralelneř) - hardware poccítá vnitrní potenciály i aktivacní funkce (je nutné diskrétne aproximovat spojitou akt. funkci) ► hardware implementuje ucící algoritmus (napr. zpetnou propagaci, která se podobá výpocctu síte, ale od výstupu ke vstupum) 15 Trocha historie neuropoCítaCU ► 1951: SNARC (Minski a spol.) - první implementace neuronu - nebyla použita k ničemu rozumnému ► 1957: Mark I Perceptron (Rosenblatt a spol.) - první úspěšná neuronová síť pro rozpoznávání obrazců ► jednalo se v podstate o jednovrstvou sít' ► obraz snímán 20 x 20 fotovodiči ► intenzita bodu byla vstupem síte perceptronu (jednovrstvá sít'), která klasifikovala o jaký se jedná znak ► váhy byly implementovány pomocí potenciometru (hodnota odporu nastavována motorem pro každý potenciometr zvlášt') ► umožnoval prohazovat vstupy do neuronu, címž se demonstrovala schopnost adaptace 16 Trocha historie neuropoCítaCU - 1960: ADALINE (Widrow & Hof) ► V podstate jednovrstvá sít ► Váhy uloženy v pomocí nové souccástky memistor, která si „pamatuje historii" proudu ve forme odporu. ► Widrow založil firmu Memistor Corporation, která prodávala hardwarové implementace neuronových sítí. ► 1960-66: Neekolik firem zameřeno na aplikaci neurovýpoctu 17 Trocha historie neuropočítačU ► 1967-82: Převážne mrtvo po zveřejnení práce Miského a Paperta (oficiálne vydána roku 1969 pod názvem Perceptrons) ► 1983-konec devadesátých let: Rozmach neuronových sítí ► mnoho pokusu o hardwarovou implementaci ► jednoúcelové cipy (ASIC) ► programovatelné cipy (FPGA) ► hardwarové implementace vetšinou nejsou lepší než „softwarové" implementace na univerzálních strojích (problémy s pametívah, velikostí, rychlostí, nákladností výroby apod.) ► konec devadesátých let-cca 2005: NS zatlaceny do pozadí jinými modely (support vector machines (SVM)) ► 2006-nyní: Renesance neuronových sítí ► hluboké síte (mnoho vrstev) - vetšinou lepší než SVM ► znovuobjeven memistor v HP Labs (nyní se jmenuje memristor, má odlišnou konstrukci) - spolu s analogovými neurony umožnuje miniaturizaci(obrovské síte) ► spekulace o biologickém hardware 18 Ilustrativní príklad Digitální sít TOTEM (ASIC); implementace neuronů: Address I Input Data Zdroj: http://www.neuricam.com/ 19 Ilustrativní příklad - TOTEM TOTEM (ASIC); minimální sít' s obvodem TOTEM Input Data Zdroj: http://www.neuricam.com/ ► LUT = look-up table, která počítá aktivační funkci (není prímo na čipu TOTEM) 20 Implementace neuronových sítí - software ► NS jsou soucástí nekolika komecne dostupných balíku pro analýzu dat, napřr. - NeuroSolutions (prostredí pro tvorbu, ucení a aplikaciNS, grafický interface, funguje v Excelu) ► Alyuda Neurosolutions (software pro tvorbu a aplikaciNS v mnoha oblastech, funguje v Excelu, skvelý marketing :-)) od financnictví po biotechnologie, zejména predikce a analýza dat - Knowledge Miner (NS + genetické algoritmy pro konstrukci NS, funguje v Excelu) použití: napr. předvídání zmeen klimatu, makro a mikro ekonomický vývoj, plánování zdroju, predikce spotreby zdroju, ... ► Siemens ECANSE (Environment for Computer Aided Neural Software Engineering) ► NS jsou soucástí mnoha známých systému pro vedecké výpocřty a analýzu dat ► např. MATLAB, Mathematica, Statistica, ... ► tyto systémy obvykle obsahují balíky s příkazy pro tvorbu, ucení a aplikaciNS - casto nabízejí grafické prostředí pro tvorbu sítí 21 Ilustrace - MatLab (NeuroSolutions) Zdroj: MATLAB - Neural Network Toolbox 22 Ilustrace - MatLab (NeuroSolutions) % Solve an Input-Output Fitting problem with a Neural Network % Script generated by NFTOOL % % This script assumes these variables are defined: % % houselnputs - input data. % houseTargets - target data. inputs = houselnputs; targets = houseTargets; % Create a Fitting Network hiddenLayerSize = 10; net = fitnet(hiddenLayerSize); % Set up Division of Data for Training, Validation, Testing net.divideParam.trainRatio = 70/100; net.divideParam.valRatio = 15/100; net.divideParam.testRatio = 15/100; % Train the Network [net,t r] = train(net,inputs,targets); % Test the Network outputs = net(inputs); errors = gsubtract(outputs,targets); performance = perform(net,targets,outputs) % View the Network viev.:netj 23 Implementace neuronových sítí - PMML ► znackovací jazyk založený na XML (vyvinut Data Mining Group) ► umožnuje popis modelu pro predikci a analýzu dat (mezi nimi Neuronové síte) ► podporován mnoha systmémy (Statistica, TERADATA Warehouse Miner, Pentaho Weka, atd.) Zdroj: http://www.ibm.com/developerworks/industry/library/ind-PMML1/index.html 24