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 Formální neuron (s biasem) bias x0 = 1 x-i,.. .,xn jsou reálné vstupy x0 je speciální vstup, který má vždy hodnotu 1 w0, w-i,..., wn jsou reálné váhy £ je vnitřní potenciál; většinou £ = w0 + £,"=1 w,X; y je výstup daný y = a(£) kde a je aktivační funkce; např. osřrá nelinearita ( práh aktivační funkce a je roven 0; reálný práh byl nahrazen vstupem x0 = 1 a váhou w0 = -h) Základní logické funkce Aktivační funkce a je ostrá nelinearita a(£) [1 «5>0; 10 <5<0. y = AND{x:,...,xn) y=OR{xi,... 1 -A x0 = 1->Qy 1/ 1 Xi x2 y = WOT(xi) í x0 = 1 ->@ -'T 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. □ 4 Nelineární separace - ostrá nelinearita oro od 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 Nelineární separace - ostrá nelinearita - ilustrac 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. ž. 6 Nelineární separace - sigmoida Věta (Cybenko 1989 - neformální verze) Nechť o je spojitá funkce, která je sigmoidální, tedy splňuje 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íť) pro x pro x —oo 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 8 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 e > 0 lze zkonstruovat třívrstvou síť počítající funkci F : [0,1]n —> [0,1] takovou, že ► aktivační funkce v nejvyšší vrstvě je lineární, tj. £(£) = 4, ve zbylých vrstvách standardní sigmoida o *■ pro každé v e [0,1]n platí |F(v) - ř(v)| < e. 9 Aproximace spojitých funkcí - třívrstvé sítě X! X2 Zdroj obrázků: C. Bishop; Neural Networks for Pattern Recognition; ISBN 9780198538646 Aproximace spojitých funkcí - dvou vrstvě Věta (Cybenko 1989) Nechť o je spojitá funkce, která je sigmoidální, 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. 11 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. 13 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, ■■■) 14 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é (spíše historické, 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) 16 Trocha historie neuropočítačů ► 1951:SNARC(Minskiaspol.) ► první implementace neuronu ► krysa hledá cestu z ven z bludiště ► 40 umělých neuronů (300 elektronek, spousta motorů apod.) Trocha historie neuropočítačů ► 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 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ů 19 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ě) ► GPU (CUDA) implementace Ilustrativní příklad Digitální síť TOTEM (ASIC); implementace neuronů: Output Data 32-to -16 Barrel Shifter Output Address Generator Weight Memo ry (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 komerčně dostupných balíků pro analýzu dat, např. ► 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ů, ... ► NS jsou součástí mnoha známých systémů pro vědecké výpočty a analýzu dat ► např. MATLAB, Mathematica, Statistica, Weka ... ► 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í 23 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 = houseinputs; 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) Knihovn Existuje několik knihoven, které lze využít při programování strojového učení, např. FANN a OpenNN (obě open source) FANN ► vícevrstvé sítě ► čtyři učící algoritmy (zpětná propagace a další) ► multi-platformní (unix, Linux (Debian), windows) a lze ji použít z různých jazyků (C, C++, PHP, Python, Mathematica,...) ► existují grafické nástroje postavené na této knihovně (např. FANN Tool) 26 FANN - ukazka #include "fann.h" int main() I struct fann *ann = fann create(1, 0.7, 3, 26, 13, 3) ; farm train on file(ann, "frequencies . data" , 200, 10, 0.0001); 1 fann savefann, "language classify.net"); fann destroy (ann) ,- return 0; ] 27 FANN - ukäzka Max epochs 200. Desired error: 0. 0001000000 Epochs 1. Current error: 0. 7464869022 Epochs 10. Current error: 0. 7226278782 Epochs 20. Current error: 0. 6682052612 Epochs 30. Current error: 0. 6573708057 Epochs 40. Current error: 0. 5314316154 Epochs 50. Current error: 0. 0589125119 Epochs 57. Current error: 0. 0000702030 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 29