Postavení neuronových sítí v informatice ► „Vyjadřovací" schopnosti neuronových sítí ► logické funkce ► nelineární separace ► spojité funkce ► algoritmická vyčíslitelnost ► Srovnání s klasickou architekturou počítačů ► Implementace Základní logické funkce 1 í > 0; Aktivační funkce a je ostrá nelinearita a(EJ) y = AND{x:,...,xn) xQ = 1 -^-Q xo = 1 —-@ 10 «5 < 0. y = OR(xi,...,xn) 1/ 1 X1 x2 1/ 1 X1 x2 y = NOT(xi) x0 = 1 ^0 X1 Logické funkce - obecně 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}. Důkaz. ► Pro každý vektor v = (v^,..., vn) e {0,1 }n definujeme neuron N$, jehož výstup je roven 1 právě když vstup je v: - Spojíme výstupy všech neuronů N$ pro něž platí F(v) = 1 pomocí neuronu, který implementuje funkci OR. □ Nelineární separace - ostrá nelinearita a o o o Uvažujme třívrstvou síť; každý neuron má ostrou nelinearitu jako aktivační funkci Síť dělí vstupní prostor na dva podprostory podle hodnoty výstupu (0 nebo 1) ► První (skrytá) vrstva dělí vstupní prostor na poloprostory ► Druhá může např. dělat průniky poloprostorů - konvexní oblasti ► Třetí (výstupní) vrstva může např. sjednocovat konvexní oblasti 4 ineární separace - ostrá nelinearita - ilustrac O O Uvažujme třívrstvou síť; každý neuron má ostrou nelinearitu jako aktivační funkci Třívrstvá síť může „aproximovat" libovolnou „rozumnou" množinu PcRk Pokryjeme P hyperkrychlemi (v 2D jsou to čtverečky, v 3D krychle, ...) ► Každou hyperkrychli K lze separovat pomocí dvouvrstvé sítě NK (Tj. funkce počí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. ž. 5 Nelineární separace - sigmoida Věta (Cybenko 1989 - neformální verze) Nechť o je spojitá sigmoidální funkce, tedy splňuje Í1 prox -> +00 o(x) = I 10 pro x —> -00 Pro každou „rozumnou" množinu P c [0,1]", existuje dvouvrstvá síť s aktivační funkcí o ve vnitřních neuronech (výstupní neuron má lineární), která splňuje následující: Pro „většinu" vektorů v e [0,1]n platí v e P právě když výstup této sítě je > 0 pro vstup v. Pro matematicky orientované: *- „rozumná" množina je Lebesgueovsky měřitelná *- „většina" znamená, že množina špatně klasifikovaných vektorů má Lebesgueovu míru menší než dané £ (pro každé £ může být nutné konstruovat jinou síť) Nelineární separace - praktická ilustrac Sharp Righl ALVINN řídí automobil Síť má 30 x 32 = 960 vstupních neuronů (vstupní prostor je R960) Vstupy berou stupně šedi jednotlivých obrazových bodů výstupní neurony „klasifikují" obrázky silnice podle zakřivení 30x32 Sensor Input Retina Zdroj obrázku: http://jravidal.cse.sc.edu/talks/ann/alvin.htral 7 Aproximace spojitých funkcí - třívrstvé sítě Nechť a je standardní sigmoida, tj. 1 1 + e-« Pro každou spojitou funkci f: [0,1 ]n —> [0,1 ] a ô > 0 zkonstruujeme třívrstvou síť počí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íť, která má v nejvyšší vrstvě akt. funkci £(£) = £ a ve všech nižších vrstvách „strmou" sigmoidu a(£) = 1+g_A.ť kde A je obrovské číslo. ► Poté A přesuneme do vah a Ĺ, aproximujeme pomocí standardní sigmoidy a velmi malých vah (tj. ve skutečnosti velmi málo strmé sigmoidy). Aproximace spojitých funkcí - třívrstvé sítě X! X2 Zdroj obrázků: C. Bishop; Neural Networks for Pattern Recognition; ISBN 9780198538646 9 Aproximace spojitých funkcí - dvou vrstvě Věta (Cybenko 1989) Nechť o je spojitá sigmoidální funkce, tedy splňuje o{x) 11 pro x —> +00 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] počítaná dvou vrstvou sítí jejíž vnitřní neurony mají aktivační funkci o (výstupní neuron má lineární), která splňuje \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ítě ► s obecně reálnými váhami; ► jedním vstupním a jedním výstupním neuronem (síť tedy počítá funkci F : A -> ]R kde AcR obsahuje vstupy nad kterými síť zastaví); ► plně paralelním pravidlem aktivní dynamiky (v každém kroku se aktualizují všechny neurony); ► aktivační funkcí 1 k > 0; í 0 < <£ < 1 0 S, < 0. ► Slova co £ {0,1}+ zakódujeme do racionálních čísel pomocí i ;=1 2M+1 Pf.:a) = 11001 dáô(íu) =\+^+^+^ (=0.110011 v dvojkové soustavě). Výpočetní síla neuronových sítí (vyčíslitelnost Síť akceptuje jazyk L c {0,1}+ pokud počítá funkci F : A -» R (/\ c R) takovou, že oj e L právě když ó(a>) e A a F(ô( 0. ► Cyklické sítě s racionálními váhami jsou ekvivalentní Turingovým strojům ► Pro každý rekurzivně spočetný jazyk L c {0,1}+ existuje cyklická síť s racionálními váhami a s méně než 1000 neurony, která ho akceptuje. Problém zastavení cyklické sítě s 25 neurony a racionálními váhami je nerozhodnutelný. ► Existuje „univerzální" síť (ekvivalent univerzálního Turingova stroje) ► Cyklické sítě s reálnými váhami jsou silnější než Turingovy stroje ► Pro každý jazyk L c {0,1}+ existuje cyklická síť s méně než 1000 neurony, která ho akceptuje. 12 Shrnutí teoretických výsledků ► Neuronové sítě jsou univerzální výpočetní prostředek ► dvouvrstvé sítě zvládají Booleovskou logiku ► dvouvrstvé sítě aproximují libovolné spojité funkce ► cyklické sítě jsou alespoň tak silné, jako Turingovy stroje Tyto výsledky jsou čistě teoretické - sítě vycházející z obecných argumentů jsou extrémně velké ► je velmi obtížné je navrhovat ► Sítě mají jiné výhody a účel (učení, generalizace, odolnost, ■■■) 13 Srovnání s klasickou architekturou počítačů Neuronové sítě „Klasické" počítače Data implicitně ve váhách explicitně Výpočet přirozeně paralelní sekvenční (obvykle), lokalizovaný Odolnost odolné vůči nepřesnosti vstupu a poškození změna jednoho bitu může znamenat krach výpočtu Přesnost výpočtu nepřesný, síť si „vybaví" podobný tréninkový vzor přesný Programování učí se ze vzorového chování je nutné precizně programovat Neuropočítače ► Neuropočítač = hardwarová implementace neuronové sítě ► Obvykle jsou to speciální akcelerátory („karty"), které dostávají vstupy z obyčejného počítače a vrací výstupy sítě ► Podle typu reprezentace parametrů sítě rozlišujeme neuropočítače na ► digitální (většina, např. Neuricam TOTEM, Philips Lneuro a další často pouze výzkumné projekty) ► analogové (např. Intel ETANN) ► hybridní (např. AT&T ANNA) ► Lze pozorovat různé stupně hardwarových implementací: ► hardware pouze provádí výpočet vnitřních potenciálů (lze provádět paralelně) ► hardware počítá vnitřní potenciály i aktivační funkce (je nutné diskrétně aproximovat spojitou akt. funkci) ► hardware implementuje učící algoritmus (např. zpětnou propagaci, která se podobá výpočtu sítě, ale od výstupu ke vstupům) 15 Trocha historie neuropočítačů ► 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 podstatě o jednovrstvou síť ► obraz snímán 20 x 20 fotovodiči ► intenzita bodů byla vstupem sítě perceptronů (jednovrstvá síť), která klasifikovala o jaký se jedná znak ► váhy byly implementovány pomocí potenciometru (hodnota odporu nastavována motorem pro každý potenciometr zvlášť) ► umožňoval prohazovat vstupy do neuronů, čímž se demonstrovala schopnost adaptace 16 Trocha historie neuropočítačů ► 1960: ADALINE (Widrow & Hof) ► V podstatě jednovrstvá síť ► Váhy uloženy v pomocí nové součástky memistor, která si „pamatuje historii" proudu ve formě odporu. ► Widrow založil firmu Memistor Corporation, která prodávala hardwarové implementace neuronových sítí. 1960-66: Několik firem zaměřeno na aplikaci neurovýpočtů 17 Trocha historie neuropočítačů ► 1967-82: Převážně mrtvo po zveřejnění práce Miského a Paperta (oficiálně vydána roku 1969 pod názvem Perceptrons) ► 1983-konec devadesátých let: Rozmach neuronových sítí ► mnoho pokusů o hardwarovou implementaci ► jednoúčelové čipy (ASIC) ► programovatelné čipy (FPGA) ► hardwarové implementace většinou nejsou lepší než „softwarové" implementace na univerzálních strojích (problémy s pamětí vah, velikostí, rychlostí, nákladností výroby apod.) ► konec devadesátých let-cca 2005: NS zatlačeny do pozadí jinými modely (support vector machines (SVM)) ► 2006-nyní: Renesance neuronových sítí ► hluboké sítě (mnoho vrstev) - většinou lepší než SVM ► znovuobjeven memistor v HP Labs (nyní se jmenuje memristor, má odlišnou konstrukci) - spolu s analogovými neurony umožňuje miniaturizaci (obrovské sítě) ► spekulace o biologickém hardware 18 Ilustrativní příklad Digitální síť TOTEM (ASIC); implementace neuronů: Output Data 32-to -16 Barrel Shifter Output Address Generator Weight Memory -ß^ (DRAM) Broadcast Bus Weight Bus Weight Address Generator Weight Memory 4^+-(DRAM) Gray - Binary Decoder Address Input Data Zdroj: http://www.neuricara.cora/ Output Bus Control Weight Memory (DRAM) Ilustrativní příklad - TOTEM TOTEM (ASIC); minimální síť s obvodem TOTEM Output Data LUT = look-up table, která počítá aktivační funkci (není přímo na čipu TOTEM) Input Data Zdroj: http://www.neuricara.cora/ Implementace neuronových sítí ■ software NS jsou součástí několika komečně dostupných balíků pro analýzu dat, např. ► NeuroSolutions (prostředí pro tvorbu, učení a aplikaci NS, grafický interface, funguje v Excelu) ► Alyuda Neurosolutions (software pro tvorbu a aplikaci NS v mnoha oblastech, funguje v Excelu, skvělý marketing :-)) od finančnictví po biotechnologie, zejména predikce a analýza dat ► Knowledge Miner (NS + genetické algoritmy pro konstrukci NS, funguje v Excelu) použití: např. předvídání změn klimatu, makro a mikro ekonomický vývoj, plánování zdrojů, predikce spotřeby zdrojů, ... ► Siemens ECANSE (Environment for Computer Aided Neural Software Engineering) ► NS jsou součástí mnoha známých systémů pro vědecké výpočty a analýzu dat ► např. MATLAB, Mathematica, Statistica, ... ► tyto systémy obvykle obsahují balíky s příkazy pro tvorbu, učení a aplikaci NS často nabízejí grafické prostředí pro tvorbu sítí 21 Ilustrace - MatLab (NeuroSolutions) Zdroj: MATLAB - Neural Network Toolbox Neural Network Fitting Tool [nftool) Select Data What input; and target define your pro b lei Get Data from Workspace |» Input;: O Targets: Samples are oriented as . [HI] Columns o Kl R Want to try cut1hi:tccl .nth an example dat I Load Example ^> To continue, dick [Next]. Summary Inputs 'ha u sein puts' is a 13:j506 matrix, representing 5 06 samples of 13 ŕ ; = r"|;di' is a 1x506 matrix, representing 506 samples of 1 * Back II * Not O Cn, Ilustrace - MatLab (NeuroSolutions) % Solve an Input-Output Fitting problem with a Neural Network % Script generated by NFTOOL % % This script assumes these variables are defined: % % houseinputs - input data. % houseTargets ■ target data. inputs = hauselnputs; 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,tr] = train(net,inputs,targets); % Test the Network outputs = net(inputs); errors = gsubtract(outputs,targets); performance = perform(net,targets,outputs) % View the Network view(net) Implementace neuronových sítí - PMML ► značkovací jazyk založený na XML (vyvinut Data Mining Group) ► umožňuje popis modelů pro predikci a analýzu dat (mezi nimi Neuronové sítě) ► podporován mnoha systmémy (Statistica, TERADATA Warehouse Miner, Pentaho Weka, atd.) Zdroj: http: //www. ibra. cora/developerworks/industry/library/ind-PMLl/index.htral 24