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 je rostoucí a 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í - dvouvrstvé Věta (Cybenko 1989) Nechť o je spojitá funkce, která je sigmoidální, tedy je rostoucí a splňuje o{x) pro x —> +00 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 perceptronu (v podstatě formální neuron), který klasifikoval 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 SyNAPSE (USA) ► Velký výzkumný program financovaný agenturou DARPA ► Hlavní subjekty jsou IBM a HRL, spolupracují s významnými univerzitami, např. Boston, Stanford ► Projekt běží od roku 2008, právě se nachází ve třetí fázi z pěti, končit by měl mezi 2014 a 2017 ► Dosud investováno přes 102.6 milionů dolarů (rok 2013) Cíle ► Vyvinout hardwarovou neuronovou síť odpovídající mozku savce (myši, kočky) ► Výsledný čip by měl simulovat 10 miliard neuronů, 100 bilionů synapsí, spotřeba energie 1 kilowatt (~ malé topení), velikost 2 dm3 ► Spíše zaměřen na tvorbu počítače s odlišnou architekturou, samotný výzkum mozku není prvořadý 21 SyNAPSE (USA) - dosavadní výsledky Simulace mozku "velikosti" kočičího (2009) ► Simulace sítě s 1.6 miliardami neuronů, 8.87 biliony synapsí ► Simulace provedena na superpočítači Dawn (Blue Gene/P), 147,450 CPU, 144 terrabytů paměti ► 643 krát pomalejší než reálný běh ► Síť byla modelována dle skutečného mozku (hierarchický model vizuálního kortexu, 4 vrstvy) ► Pozorovány některé děje podobné biologickým (propagace signálu, a, y vlny) ... simulace podrobena drtivé kritice (viz. později) 22 SyNAPSE (USA) - dosavadní výsledky Další simulace (TrueNorth a Compass, 2012) 1. Synaptic crossbar a0 \—^Buffer \<— H a> [~*-(BL'rfer r— -^| Network | ► Simulace sítě s 53x1010 neuronů, 1.3714 synapsí (část mapy mozku makaka) ► 2084 milionů synaptických jader po 256 neuronech a 256x256 synaptických spojeních ► jednoduché leaky integrate-and-fire neurony ► Simulace provedena na superpočítači Sequoia (Blue Gene/P), 1,572,864 procesorů a 1.5 petabytů paměti ► 1542 krát pomalejší než reálný běh ► Aplikace (údajně) rozpoznávání obrazu, navigace robota, apod. SyNAPSE (USA) - dosavadní výsledky Hardwarové implementace ► Memristorové čipy ► poslední "fundamentální" součástka ► princip: odpor závislý na "historii" proudu, který součástkou prochází (pamatuje si historii proudu i po vypnutí!) ► dokáže spojit paměť a výpočetní prvky ► Digital neurosynaptic core (2011, 2013) ► jádro o 256 leaky integrate-and-fire neuronech, každý neuron má 1024 synapsí s ostatními ► implementováno pomocí CMOS technologie, 3.8 tranzistorů, velikost 4.2 mm2 (neuron zabírá 35 \im x 95 /im, biologický neuron má průměr 4 - 100 \im). - přes USB připojeno k PC, hodiny 1 kHz (odpovídá 1 ms) ► realizoval učení založené na spike-timing plasticity (obdoba Hebbova učení, která bere v potaz časovou souslednost impulzů) Rozpoznávalo to rukou psaná čísla a hrálo pong (tj. nic moc) V roce 2013 implementován systém 4000 jader (~ 106 neuronů) 24 Human Brain Project, HBP (Evropa) ► Financováno EU, rozpočet 109 EUR na 10 let ► Následník Blue Brain Project na EPFL Lausanne (Švýcarsko), další subjekt je ETH Zurich (spolupracují další univerzity) - v roce 2014 přesunuto do Ženevy ► Blue Brain běžel od 2005 do 2012, od 2013 běží Human Brain Project Hlavní cíl: Poznání funkce lidského mozku ► léčení onemocnění mozku ► integrace světového neurovýzkumu ► tvorba myslícího stroje Postup: ► studium mozkové tkáně pomocí mikroskopů a elektrod ► modelování biologicky věrného modelu ► simulace na superpočítači pomocí programu NEURON (open soft) 25 HBP (Evropa) - dosavadní výsledky Blue brain project ► Model části mozkové kůry krysy (cca 10,000 neuronů), podstatně složitější model neuronu než v případě SyNAPSE ► Simulováno na superpočítači typu Blue Gene/P (IBM dodala se slevou), 16,384 CPU, 56 teraflops, 16 terabytů paměti, 1 PB diskového prostoru (v plánu je použít Deep Project - 1018 FLOPS) ► Simulace 300x pomalejší než reálný běh 26 SyNAPSE vs HBP IBM Simulates 4.5 percent of the Human Brain, and All of the Cat Brain (Scientific American) "... performed the first near real-time cortical simulation of the brain that exceeds the scale of a cat cortex" (IBM) Toto prohlášení bylo podrobeno drtivé kritice v otevřeném dopise Dr. Markrama (šéf HBP) "This is a mega public relations stunt - a clear case of scientific deception of the public" "Their so called "neurons" are the tiniest of points you can imagine, a microscopic dot" "Neurons contain 10s of thousands of proteins that form a network with 10s of millions of interactions. These interactions are incredibly complex and will require solving millions of differential equations. They have none of that." 27 SyNAPSE vs HBP "Eugene Izhikevik himself already in 2005 ran a simulation with 100 billion such points interacting just for the fun of it: (over 60 times larger than Modha's simulation)" Why did they get the Gordon Bell Prize? "They seem to have been very successful in influencing the committee with their claim, which technically is not peer-reviewed by the respective community and is neuroscientifically outrageous." But is there any innovation here? "The only innovation here is that IBM has built a large supercomputer." But did Mohda not collaborate with neuroscientists? "/ would be very surprised if any neuroscientists that he may have had in his DARPA consortium realized he was going to make such an outrages claim. I can't imagine that the San Fransisco neuroscientists knew he was going to make such a stupid claim. Modha himself is a software engineer with no knowledge of the brain." 28 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í 29 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) 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) 32 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; ] 33 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 35