: Neural networks Tomáš Brázdil Course organization Course materials: ► Main: The lecture ► Neural Networks and Deep Learning by Michael Nielsen http://neuralnetworksanddeeplearning.com/ (Extremely well written modern online textbook.) ► Deep learning by Ian Goodfellow, Yoshua Bengio and Aaron Courville http://www.deeplearningbook.org/ (A very good overview of the state-of-the-art in neural networks.) Course organization Evaluation: ► Project ► teams of two students ► implementation of a selected model + analysis of real-world data ► implementation either in C++, or in Java without use of any specialized libraries for data analysis and machine learning ► real-world data means unprepared, cleaning and preparation of data is part of the project! ► Oral exam ► I may ask about anything from the lecture including some proofs that occur only on the whiteboard! ► (Optional) This year we will try to organize a simple data analysis competition (to try the concept). It is up to you whether to participate, or not. During the competition, you may use whatever tools for training neural networks you want. Q: Why English? A: Couple of reasons. First, all resources about modern neural nets are in English, it is rather cumbersome to translate everything to Czech (combination of Czech and English is ugly). Second, to attract non-Czech speaking students to the course. Q: Why are the lectures not recorded? A: Apart from my personal reasons, I want you to participate actively in the lectures, i.e. to communicate with me and other students during the lectures. Also, in my opinion, online lectures should be prepared in a completely different way. I will not discuss this issue any further. Q: Why we cannot use specialized libraries in projects? A: In order to "touch" the low level implementation details of the algorithms. You should not even use libraries for linear algebra and numerical methods, so that you will be confronted with rounding errors and numerical instabilities. Machine learning in general ► Machine learning = construction of systems that may learn their functionality from data (... and thus do not need to be programmed.) ► spam filter ► learns to recognize spam from a database of "labelled" emails ► consequently is able to distinguish spam from ham ► handwritten text reader ► learns from a database of handwritten &. Ck letters (or text) labelled by their correct M "v^ meaning ► consequently is able to recognize text ► ... ► and lots of much much more sophisticated applications ► Basic attributes of learning algorithms: ► representation: ability to capture the inner structure of training data ► generalization: ability to work properly on new data Machine learning in general Machine learning algorithms typically construct mathematical models of given data. The models may be subsequently applied to fresh data. There are many types of models: ► decision trees ► support vector machines ► hidden Markov models ► Bayes networks and other graphical models ► neural networks ► ... Neural networks, based on models of a (human) brain, form a natural basis for learning algorithms! Artificial neural networks ► Artificial neuron is a rough mathematical approximation of a biological neuron. ► (Aritificial) neural network (NN) consists of a number of interconnected artificial neurons. "Behavior" of the network is encoded in connections between neurons. y Zdroj obrázku: http://tulane.edu/sse/cmb/people/schrader/ Why artificial neural networks? Modelling of biological neural networks (computational neuroscience). ► simplified mathematical models help to identify important mechanisms ► How a brain receives information? ► How the information is stored? ► How a brain develops? ► ... ► neuroscience is strongly multidisciplinary; precise mathematical descriptions help in communication among experts and in design of new experiments. I will not spend much time on this area! Why artificial neural networks? Neural networks in machine learning. ► Typically primitive models, far from their biological counterparts (but often inspired by biology). ► Strongly oriented towards concrete application domains: ► decision making and control - autonomous vehicles, manufacturing processes, control of natural resources ► games - backgammon, poker, GO ► finance - stock prices, risk analysis ► medicine - diagnosis, signal processing (EKG, EEG,...), image processing (MRI, roentgen,...) ► text and speech processing - automatic translation, text generation, speech recognition ► other signal processing - filtering, radar tracking, noise reduction I will concentrate on this area! Important features of neural networks ► Massive parallelism ► many slow (and "dumb") computational elements work in parallel on several levels of abstraction ► Learning ► a kid learns to recognize a rabbit after seeing several rabbits ► Generalization ► a kid is able to recognize a new rabbit after seeing several (old) rabbits ► Robustness ► a blurred photo of a rabbit may still be classified as a picture of a rabbit ► Graceful degradation ► Experiments have shown that damaged neural network is still able to work quite well ► Damaged network may re-adapt, remaining neurons may take on functionality of the damaged ones The aim of the course ► We will concentrate on ► basic techniques and principles of neural networks, ► fundamental models of neural networks and their applications. ► You should learn ► basic models (multilayer perceptron, convolutional networks, recurent network (LSTM), Hopfield and Boltzmann machines and their use in pre-training of deep nets) ► Standard applications of these models (image processing, speech and text processing) ► Basic learning algorithms (gradient descent & backpropagation, Hebb's rule) ► Basic practical training techniques (data preparation, setting various parameters, control of learning) ► Basic information about current implementations (TensorFlow, CNTK) Biological neural network ► Human neural network consists of approximately 1011 (100 billion on the short scale) neurons; a single cubic centimeter of a human brain contains almost 50 million neurons. ► Each neuron is connected with approx. 104 neurons. ► Neurons themselves are very complex systems. Rough description of nervous system: ► External stimulus is received by sensory receptors (e.g. eye cells). ► Information is futher transfered via peripheral nervous system (PNS) to the central nervous systems (CNS) where it is processed (integrated), and subseqently, an output signal is produced. ► Afterwards, the output signal is transfered via PNS to effectors {e.g. muscle cells). Biological neural network Cell body of Gray Zdroj: N. Campbell and J. Reece; Biology, 7th Edition; ISBN: 080537146X Cerebral cortex Skeletal muscle movement Primary motor cortex Motor association area (premotor cortex and supplementary motor cortex) Frontal lobe Prefrontal association area Coordinates information from other association areas, controls some behaviors Reasoning skills Taste Gustat°ry Taste cortex Sme//-°,factory cortex Primary somatic sensory cortex Parietal lobe Sensory association area Sensory information from skin, musculoskeletal system, viscera, and taste buds Visual association area Occipital lobe Visual cortex Vision Auditory association area Auditory cortex Temporal lobe Hearing Copyrighl © 2007 Pearson Education, Inc., publishing as Benjamin Cummings. Fig. 9-15 14 Terminal branches of axon (form junctions with other cells) Zdroj: http://www.web-books.com/eLibrary/Medicine/Physiology/Nervous/Nervous.htm 15 Synaptic connections Resting potential Action potential Depolarization phase of the action potential / +50 Activation gate trv' f B h E 0 Threshold -100 O Inactivation ^ ^ gate ^ Repolarizing phase of the action potential Action potential A °/\ ©/ \° Threshold T 1 -potential if \ o r \ Ä O Time- ->■ Outside cell Plasma membrane Inside cell Potassium channel tMHTJJZ si nx Sodium channel Resting state Cüpyriyhi '>?■ Peüiscn E=rJu^iiti^ii. nie . p;-L.biis!iiny üs :i|í.itn in Cummmgs. Undershoot Spreading action in axon f?JAP begins "^at axon hillock r v. r p. (£) electrical current spreads,.. current spread is the electrical event that triggers V-gated channels (& thus the A?) a tiny bit down the axon electrical current spreads... j^current spread is the electrical l£ event that triggers V-gated channels (& thus the A?) a iny bit down the axon J \^ ^/^electrical current spreads,. etcetera,.. Zdroj: D. A. Tamarkin; STCC Foundation Press Chemical synapse Presy naptŕc Ca2+ membrane Synaptic terminal Postsynaptic membrane Synaptic vesicles containing neurotransmitter molecules Synaptic cleft ion channel^* (closed) O Ion channel (open} Copyrights Pearson Education. Inc.. publishing as Benjamin Cum mings. Postsynaptic cell Na" ism Neurotransmitter Receptor !; I Postsynaptic f membrane — Ion channel protein Part of degraded neurotransmitter IM 20 Summation Synaptic terminála of presynaptic neurons Dendrites of postsynaptic neuron Axon hillock A*on °* postsynaptic neuron Terminal branches of presynaptic neurons Excitatory synapse Inhibitory synapse Figure 48.11(a), page 972, Campbell's Biology, 5th Edition Biological and neurons inputs Dendrites Cell bodv Axon t rem another neun >n Mem hrane apse v^1 »3 output ľ-' "t he ľ neurons 22 Formal neuron (without bias) y ► x-i,..., xn g 1R are inputs ► ,..., wn e R are weights ► £ is an inner potential; almost always I = w,x; ► y is an output given by y = a(£) where a is an activation function e.g. a unit step function 1 0 £ < /?. where h e 1R is a threshold. Formal neuron (with bias) threshold bias y x0 = 1 wq = -h *2 ► x0 = 1, x1,..., xn e R are inputs ► w0, ,..., wn e R are weights ► £ is an inner potential; almost always £ = w0 + E/Li w,-x/ ► y is an output given by y = a(£) where a is an activation function; e.g. a unit step function 1 £>0; 0 £<0. (The threshold h has been substituted with the new input x0 = 1 and the weight w0 = -h.) 24 Neuron and linear separation £<0 inner potential n WjX; /=1 determines a separation hyperplane in the n-dimensional input space ► in 2d line ► in 3d plane 25 Neuron and linear separation 1/0 by A/B mm mm mm mm mm mm i i i i i 11 x0 = w0 1-> 0 n = 8 • 8, i.e. the number of pixels in the images. Inputs are binary vectors of dimension n (black pixel « 1, white pixel « 0). Neuron and linear separation w0 + E,=i WjXj = 0 A A wo + L/Li w/x/ = o ► Red line classifies incorrectly ► Green line classifies correctly (may be a result of a correction by a learning algorithm) 27 Neuron and linear separation (XOR) (0,1) 0,1) No line separates ones from zeros. ©—o— (0,0) (0,1) *2 28 Neural network consists of formal neurons interconnected in such a way that the output of one neuron is an input of several other neurons. In order to describe a particular type of neural networks we need to specify: ► Architecture How the neurons are connected. ► Activity How the network transforms inputs to outputs. ► Learning How the weights are changed during training. 29 Architecture Network architecture is given as a digraph whose nodes are neurons and edges are connections. We distinguish several categories of neurons: ► Output neurons ► Hidden neurons ► Input neurons (In general, a neuron may be both input and output; a neuron is hidden if it is neither input, nor output.) 30 Architecture - Cycles ► A network is cyclic (recurrent) if its architecture contains a directed cycle. ► Otherwise it is acyclic (feed-forward) Architecture - Multilayer Perceptron (MLP) Output Hidden CLOJD Input Neurons partitioned into layers; one input layer, one output layer, possibly several hidden layers layers numbered from 0; the input layer has number 0 ► E.g. three-layer network has two hidden layers and one output layer Neurons in the Mh layer are connected with all neurons in the / + 1 -st layer Architecture of a MLP is typically described by numbers of neurons in individual layers (e.g. 2-4-3-2) 32 Activity Consider a network with n neurons, k input and I output. ► State of a network is a vector of output values of all neurons. (States of a network with n neurons are vectors of Rn) ► State-space of a network is a set of all states. ► Network input is a vector of k real numbers, i.e. an element of IR^. ► Network input space is a set of all network inputs. (sometimes we restrict ourselves to a proper subset of R*) ► Initial state Input neurons set to values from the network input (each component of the network input corresponds to an input neuron) Values of the remaining neurons set to 0. Activity - computation of a network ► Computation (typically) proceeds in discrete steps. In every step the following happens: 1. A set of neurons is selected according to some rule. 2. The selected neurons change their states according to their inputs (they are simply evaluated). (If a neuron does not have any inputs, its value remains constant.) A computation is finite on a network input x if the state changes only finitely many times (i.e. there is a moment in time after which the state of the network never changes). We also say that the network stops on x. ► Network output is a vector of values of all output neurons in the network (i.e. an element of 1R6). Note that the network output keeps changing throughout the computation! MLP uses the following selection rule: In the Mh step evaluate all neurons in the Mh layer. Activity - semantics of a network Definition Consider a network with n neurons, k input, I output. Let A c Kk and B c K£. Suppose that the network stops on every input of A. Then we say that the network computes a function F : A —> B if for every network input x the vector F(x) e B is the output of the network after the computation on x stops. Example 1 This network computes a function from R2 to 1R. Activity - inner potential and activation functions In order to specify activity of the network, we need to specify how the inner potentials I are computed and what are the activation functions a. We assume (unless otherwise specified) that here x = (x1,..., xn) are inputs of the neuron and w = (w-i,..., wn) are weights. There are special types of neural network where the inner potential is computed differently, e.g. as a "distance" of an input from the weight vector: n Wi • X; /=1 = x - w here ||-|| is a vector norm, typically Euclidean. Activity - inner potential and activation functions There are many activation functions, typical examples: ► Unit step function 1 Z >0; 0 £<0. (Logistic) sigmoid 1 1 + e~A-z here A e R is a steepness parameter. Hyperbolic tangens 1 -£j 1 + e~* Activity - XOR ► Activation function is a unit step function <>{£) = 1 £>0; 0 £<0. The network computes XOR(x1/x2) X1 *2 y 1 1 0 1 0 1 0 1 1 0 0 0 38 Activity - MLP and linear separation 1 The line is given by -1 + 2x-\ + 2x2 = 0 The line P2 is given by 3-2xi- 2x2 = 0 Activity - example The activation function is the unit step function 1 1 5>0; 0 5 < 0. The input is equal to 1 40 Learning Consider a network with n neurons, k input and I output. ► Configuration of a network is a vector of all values of weights. (Configurations of a network with m connections are elements of Rm) ► Weight-space of a network is a set of all configurations. ► initial configuration weights can be initialized randomly or using some sophisticated algorithm 41 Learning algorithms Learning rule for weight adaptation. (the goal is to find a configuration in which the network computes a desired function) ► supervised learning ► The desired function is described using training examples that are pairs of the form (input, output). ► Learning algorithm searches for a configuration which "corresponds" to the training examples, typically by minimizing an error function. ► Unsupervised learning ► The training set contains only inputs. ► The goal is to determine distribution of the inputs (clustering, deep belief networks, etc.) 42 Supervised learning - illustration A A B B classification in the plane using a single neuron training examples are of the form (point, value) where the value is either 1, or 0 depending on whether the point is either A, or B the algorithm considers examples one after another whenever an incorrectly classified point is considered, the learning algorithm turns the line in the direction of the point 43 Unsupervised learning - illustration ^ ►we search for two centres of clusters A A ►red crosses correspond to potential • x < centres before application of ^ X the learnin9 algorithm, green ones after the application 44 Summary - Advantages of neural networks ► Massive parallelism ► neurons can be evaluated in parallel ► Learning ► many sophisticated learning algorithms used to "program" neural networks ► generalization and robustness ► information is encoded in a distributed manned in weights ► "close" inputs typicaly get similar values ► Graceful degradation ► damage typically causes only a decrease in precision of results 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 46 Formální neuron (s biasem) bias y x0 = 1 vv0 = -h ► ► ► ► x1,..., xn jsou reálné vstupy x0 je speciální vstup, který má vždy hodnotu 1 w0, wi,..., wn jsou reálné váhy £ je vnitřní potenciál; Většinou £ = Wo + W;X; y je výstup daný y = o(E) kde a je aktivační funkce; např. ostrá nelinearita 1 ^>0; 0 £<0. ( práh aktivační funkce o je roven 0; reálný práh byl nahrazen vstupem x0 = 1 a váhou w0 = -h) Základní logické funkce Aktivační funkce o je ostrá nelinearita o(E) = y = AND(xi,...,xn) -n T x0 = 1 ->Co} 1 £> 0 £ < y1 X! X2 y = WOT(xi) o T x0 = 1 - -1Í X1 Logické funkce - obecně Theorem Nechť a je ostrá nelinearita. Douvrstvé sítě s aktivační funkcí a mohou počítat libovolnou funkci F : {0,1 }n -> {0,1}. Proof. ► Pro každý vektor v = (^,..., vn) e {0,1 }n definujeme neuron /V-, jehož výstup je roven 1 právě když vstup je v: ► Spojíme výstupy všech neuronů /V- pro něž platí F (v) = 1 pomocí neuronu, který implementuje funkci OR. □ 49 Nelineárni separace - ostrá nelinearita y Q (XQlJD OI Q D X) 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 50 Nelineární separace - ostrá nelinearita - ilustrace y Q Q Q O Ol O iD ► 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 Ofí, spojíme výstupy všech sítí NK t. ž. KnP^0. 51 Nelineární separace - sigmoida Theorem (Cybenko 1989 - neformální verze) Nechť a je spojitá funkce, která je sigmoidální, tedy je rostoucí a splňuje Pro každou rozumnou množinu P c [0,1]n, 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ů ve [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é e (pro každé e může být nutné konstruovat jinou síť) 1 pro x —> +oo 0 pro x —> -oo Nelineárni separace - praktická ilustrace Sharp Left Straight Ahead Sharp Right 4 Hidden Units 30 Output Units 30x32 Sensor Input Retina ► 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í Zdroj obrázku: http://jmvidal.cse.sc.edu/talks/ann/alvin.html 53 Aproximace spojitých funkcí - třívrstvé sítě Nechť a je standardní sigmoida, tj. Pro každou spojitou funkci ř: [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. C(£) = £, ve zbylých vrstvách standardní sigmoida a ► pro každé v e [0,1]n platí \F(v) - f(v)\ < e. Aproximace spojitých funkcí - třívrstvé sítě Zdroj obrázků: C. Bishop; Neural Networks for Pattern Recognition; ISBN 9780198538646 Aproximace spojitých funkcí - dvouvrstvé sítě Theorem (Cybenko 1989) Nechť a je spojitá funkce, která je sigmoidální, tedy je rostoucí a splňuje Pro každou spojitou funkci f: [0,1 ]n -> [0,1 ] a e > 0 existuje funkce F : [0,1]n -> [0,1] počítaná dvouvrstvou 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 g [0,1]n. 1 pro x —> +oo 0 pro x —> -oo 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 A c R 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 £ >0; £ 0<£<1; 0 l < 0. ► Slova o; e {0,1}+ zakódujeme do racionálních čísel pomocí ku 0(01) = £ co(i) 1 pM+1 í'=1 ~~ Př.: co = 11001 dáó(w) = l + ^ + ^ + ^ (=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 -> IR {A c R) takovou, že co ^ L právě když ô(a;) e /4 a F(ó(o;)) > 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. 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, 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 60 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, IBM TrueNorth 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) Trocha historie neuropočítačů ► 1951: SNARC (Minski a spol.) ► 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ů 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 Perceptronš) ► 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) ► GPU (CUDA) implementace ► pokusy o velké hardwarové 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 ► Investováno přes 53 milionů dolarů 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ý 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 terabytů 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) ... v roce 2012 byl počet neuronů zvýšen na 530 miliard neuronů a 100 bilionů synapsí SyNAPSE (USA) - TrueNorth ► Chip s 5.4 miliardami tranzistorů ► 4096 neurosynaptických jader propojených sítí, dohromady 1 milion programovatelných "spiking" neuronů, 256 programovatelných synaptických spojů ► globální taktovací frekvence 1-kHz ► nízká spotřeba energie, cca 63mW ► Offline učení, implementováno množství známých algoritmů (konvoluční sítě, RBM apod.) ► Pokusně aplikován na rozpoznávání objektů v obraze. 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) HBP (Evropa) - některé výsledky Blue brain project (2008) ► 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 Human brain project (2015): ► Zjednodušený model nervové soustavy krysy (zhruba 200 000 neuronů) 70 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 10's of thousands of proteins that form a network with 10's of millions of interactions. These interactions are incredibly complex and will require solving millions of differential equations. They have none of that." 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." a zatím v Evropě V roce 2014 dostala Evropská komise otevřený dopis od více než 130 vedoucích významných laboratoří, v němž hrozí bojkotem projektu HBP pokud nedojde k zásadním změnám v řízení. Peter Dayan, director of the computational neuroscience unit at UCL: "The main apparent goal of building the capacity to construct a larger-scale simulation of the human brain is radically premature." "We are left with a project that can't but fail from a scientific perspective. It is a waste of money, it will suck out funds from valuable neuroscience research, and would leave the public, who fund this work, justifiably upset." 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í 74 lustrace - MatLab Zdroj: MATLAB - Neural Network Toolbox i Ne-jfal Neť>vor< F'tting Too :'"f:ooli Select Data What input; and target; define your problem? Get Data from Workspace J* Inputs: i© Targets: Samples are oriented as: houselnputs Summary Inputs 'houselnputs' is a 13x506" matrix, representing 506 samples of 13 elements. houseTargets ^ (ft) [ill] Column; [=] Row; Targets'houseTargets' is a 1x506 matrix, representing 506 samples of 1 element. Want to try outthistool with an example data set? Load Example Data Set To continue, dick [Next]. Next O Cancel lustrace - MatLab % 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 [netjtr] = train(net,inputs,targets); % Test the Network outputs = net(inputs); errors = gsubtract(outputs,targets); performance = perform(net,targets,outputs) % View the Network view(net) Knihovny 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) Další informace o knihovnách lze nalézt např. zde: http://openann.github.io/OpenANN-apidoc/OtherLibs.html FANN - ukázka #include "fann.h" int main() { struct fann *ann = fann_create(1, 0.7, 3, 2 6, 13, 3); f ann_train_on_file (ann, "frequencies . data", 200, 10, 0.00-01); & fann_save(ann, 1Tlanguage_classif y. net") ; fann_destroy(ann); return 0; } Python libraries: ► Neurolab: vícevrstvé sítě (učení pomocí variant gradientního sestupu, sdružených gradientů apod.), Hopfieldova síť ► PyBrain (Python-Based Reinforcement Learning, Artificial Intelligence and Neural Network Library): ► sdružuje algoritmy pro neuronové sítě a reinforcement learning ► většina známých druhů sítí (včetně hlubokých sítí, RBM, rekurentních sítí, Kohonenových map apod.) ► ... další učící a optimalizační algoritmy ► Theano: ► knihovna pro definici, optimalizaci a řešení matematických výrazů s multi-dimenzionálními poli (na GPU) ► vhodná pro implementaci hlubokých sítí (viz. http://deeplearning.net/tutorial/) ► Existuje několik knihoven založených na Theano: Pylearn 2, Lasagne, atd. (R is a language and environment for statistical computing and graphics.) ► neuralnet: vícevrstvé sítě (libovolný počet vrstev), varianty zpětné propagace ► nnet: vícevrstvé sítě s jednou skrytou vrstvou, zpětná propagace Hluboké sítě: ► deepnet a darch: hluboké sítě, restricted Boltzmann machines, zpětná propagace (téměř přesně to, co budeme probírat) ► H20: ► určen pro "velká data" ► H20 is a Java Virtual Machine that is optimized for doing processing of distributed, parallel machine learning algorithms on clusters ► data nejsou uložena přímo v R, které pouze komunikuje s JVM ► algoritmy: stochastický gradientní sestup & zpětná propagace 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.ibm.com/developerworks/industry/library/ind-PMMLl/index.html Perceptron a ADALINE ► Perceptron ► Perceptronové učící pravidlo ► Konvergence učení perceptronu ► ADALINE ► Učení ADALINE 82 Perceptron Organizační dynamika: y x0 = 1 —HTj \N\ / W2 O o X! X2 w= (w0,wi,...,wn) ax = (xcx^-.^Xn) kde x0 = 1. Aktivní dynamika: ► vnitřní potenciál: £ = w0 + E/Li w,-x/ = E/Lo W/X/ = w • x aktivační funkce: a(£) = 11 ^ " °' 0 £<0. funkce sítě: y[w](x) = a(E) = a(w • x) Perceptron Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {(x1/di)/(x2/d2)/.../(xp/c/p)} Zde xk = (Xko,Xfci... ,Xkn) £ lRn+1, x^o = 1, je vstup /c-tého vzoru a d/c g {0,1} je očekávaný výstup. (dk určuje, do které ze dvou kategorií dané xk = {xk0/xk^. ..,xkn) patří). ► Vektor vah w e Rn+1 je konzistentní s T pokud y[w](x/<) = o{w• Xk) = d/c pro každé k = 1,...,p. Množina T je vnitřně konzistentní pokud existuje vektor w, který je s ní konzistentní. ► Cílem je nalézt vektor w, který je konzistentní s T za předpokladu, že T je vnitřně konzistentní. Perceptron - adaptivní dynamika Online učící algoritmus: Idea: Cyklicky prochází vzory a adaptuje podle nich váhy, tj. otáčí dělící nadrovinu tak, aby se zmenšila vzdálenost špatně klasifikovaného vzoru od jeho příslušného poloprostoru. Prakticky počítá posloupnost vektorů vah w(°\ w^2\.... ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: Zde k = (ř mod p) + 1 (tj. cyklické procházení vzorů) a 0 < e < 1 je rychlost učení. Theorem (Rosenblatt) Jestliže je T vnitřně konzistentní, pak existuje ť takové, že je konzistentní s T. w Důkaz Rosenblattovy věty Pro zjednodušení budeme dále předpokládat, že e = 1. Nejprve si algoritmus přepíšeme do méně kompaktní formy ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: ► Jestliže cr(w(f) • Xk) = cfe, pak w(ř+1) = w(ř) ► Jestliže cr(wW • Xk) ^ dk, pak ► w(ř+1) = w(t) + i4 pro d/c = 1 ► w(ř+1) = w(*) - xk pro dk = 0 (Řekneme, že nastala korekce.) kde k = (t mod p) + 1. Důkaz Rosenblattovy věty (Pro daný vektor a = (ao,..., an) označme a jeho eukleidovskou normu Va • a = yLJLo af) Idea: ► Uvážíme hodná dlouhý vektor (spočítáme jak dlouhý) w\ který je konzistentní s T. ► Ukážeme, že pokud došlo v kroku ř + 1 ke korekci vah (tedy buď w(ř+1) = w(ŕ) + xk nebo w(r+1) = w(ř) - x/<), pak < ^(0 1/1/vv - max X; Všimněte si, že max / Xí > 0 nezávisí na ř. ► Z toho plyne, že algoritmus nemůže udělat nekonečně mnoho korekcí. 87 Důkaz Rosenblattovy věty Uvažme vektor w* konzistentní s T. Búno předpokládejme, že w* • xk ± 0 pro k = 1,..., p Předp., že v kroku ř + 1 došlo ke korekci, a že k = (t mod p) + 1 Ukážeme, že w < tf<ř> - ň* + - 2\w • Xk (Potom bude k důkazu věty stačit nahlédnout, že pro "dlouhý" vektor w* je \w* • xk\ "velké" kladné číslo.) Rozlišíme dva případy: dk = 1 a 4 = 0. Důkaz Rosenblattovy věty Předpokládejme dk = 1 : Došlo ke korekci, tedy iy(ř+1) = + xk a tedy w* = (wW-w*) + xk. Pak 2 W w = I l(l#ř> - tf*)+X*k| i2 = I - w*) + xk] [(# 0. 89 Důkaz Rosenblattovy věty Předpokládejme dk = 0 : Došlo ke korekci, tedy w(ř+1) = w(ř) - xk a tedy -w*) - Xk. Pak 2 = I |(«ř(o _ w ) -*k\ i2 = I - I |(vř(f) - 2 i + I |2 - 2(tf(') - • A — - 2 + 2 - 2vř(ř) • i?* + 2tf* < 2 + xfc 2-2|W*-X,(| Poslední nerovnost plyne z toho, v ze: ► došlo ke korekci při = 0, tedy muselo platit • xk>0, ► w* je konzistentní s T a tedy w* • x/< < 0. 90 Důkaz Rosenblattovy věty Máme dokázáno: w < + Xk -2\w*-xk Nechť nyní w* = a - w+ kde a > 0. Pak 5Ď(f+l) _ tf* < + 21 -»4- -» a vir • X/< Nyní stačí uvážit a min/c |w+-Xíc| a dostaneme Což dá 2i ->4- -» i ^ a|w+-X/<| < -2 max Xk min/c IVV+ • x/c < - max X/c < ^(0 wK J - max k Xk kdykoliv došlo ke korekci. Z toho plyne, že nemůže dojít k nekonečně mnoha korekcím. □ 91 Perceptron - adaptivní dynamika Dávkový učící algoritmus: Vypočte posloupnost w(°\ w^2\... váhových vektorů. ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: /c=1 Zde k = (t mod p) + 1 a 0 < e < 1 je rychlost učení. Organizační dynamika: wn xn w= (vv0,wi,...,wn) ax = (xo,xi,...,xn) kde x0 = 1. Aktivní dynamika: ► vnitřní potenciál: £ = w0 + E/Li w/'x/' = E/Lo w'x/ = w • x ► aktivační funkce: o(£) = £ ► funkce sítě: y[w](x) = o{E) = w • x 93 ADALINE Adaptivní dynamika: ► Dána množina tréninkových vzorů T = {(x1/di)/(x2/d2)/.../(xp/c/p)} Zde xk = (Xko,Xfci... ,Xkn) £ lRn+1, x^o = 1, je vstup /c-tého vzoru a d/c g IR je očekávaný výstup. Intuice: chceme, aby síť počítala afinní aproximaci funkce, jejíž (některé) hodnoty nám předepisuje tréninková množina. Chybová funkce: 1 P 2 1 P ( n \ E(w) = ?H(™'*k~dk) = J^WjXki-dk k=1 /c=1 v/=o Cílem je nalézt vv5 které minimalizuje E(w). Gradient chybové funkce Uvažme gradient chybové funkce: VE(tf) ( dWQ dE / • • / dw. dE n Intuice: VE(w) je vektor ve váhovém prostoru, který ukazuje směrem nejstrmějšího růstu funkce E(w). Vektory xk zde slouží pouze jako parametry funkce E(w) a jsou tedy fixní! Fact Pokud VE(w) = 0 = (0,..., 0), pak w je globální minimum funkce E. Námi uvažovaná chybová funkce E(w) má globální minimum, protože je konvexním paraboloidem. Pozor! Tento obrázek pouze ilustruje pojem gradientu, nezobrazuje chybovou funkci E(w) 96 Gradient chybové funkce ADALINE 1 P ÔE ( " f 2 f-í óWí , . k=l 1 V/=0 " 5Eín k=1 V/=0 p /n /c=1 ?L2 Zw/xw~dk L V/=0 V/'=o ^ WiXki V/=0 (ÔE -dk ÔE k=1 Tedy VE(w) ADALINE - adaptivní dynamika Dávkový algoritmus (gradientní sestup): ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: v^+1) = ^-£.V£(P) p /c=1 Zde k = (ř mod p) + 1 a 0 < £ < 1 je rychlost učení. (Všimněte si, že tento algoritmus je téměř stejný jako pro perceptron, protože w(ř) • xk je hodnota funkce sítě (tedy a(w^ • xk) kde cr(£) = £).) Proposition Pro dostatečně malé e > 0 posloupnost w^°\ w^2\... konverguje (po složkách) ke globálnímu minimu funkce E (tedy k vektoru w, který splňuje VE(w) = 0). ADALINE - adaptivní dynamika Online algoritmus (Delta-rule, Widrow-Hoff rule): ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 je w(ř+1) vypočteno takto: kde k = t mod p + 1 a 0 < e (t) < 1 je rychlost učení v kroku t + 1. Všimněte si, že tento algoritmus nepracuje s celým gradientem, ale jenom s jeho částí, která přísluší právě zpracovávanému vzoru! Theorem (Widrow & Hoff) Pokud t(t) = j pak w(°\ w^2\... konverguje ke globálnímu minimu chybové funkce E. 99 ADALINE - klasifikace ► Množina tréninkových vzorů je T = {(x1/di)/(x2/d2)/.../(xp/c/p)} kdex/, = {xko,xkA,...,xkn) e IRn+1 adke {1,-1}. ► Síť se natrénuje ADALINE algoritmem. ► Očekáváme, že bude platit následující: ► jestliže dk = 1, pak w • xk > 0 jestliže dk = -1, pak tv • j>4 < 0 ► To nemusí vždy platit, ale často platí. Výhoda je, že se ADALINE algoritmus postupně stabilizuje i v neseparabilním případě (na rozdíl od perceptronového algoritmu). Vícevrstvá síť Organizační dynamika Výstupní Q O CL O JJ Skryté CtQDJD Vstupní ► Neurony jsou rozděleny do vrstev (vstupní a výstupní vrstva: obecně několik skrytých vrstev) ► Vrstvy číslujeme od 0; vstupní vrstva je nultá ► Např. třívrstvá síť se skládá z jedné vstupní, dvou skrytých a jedné výstupní vrstvy ► Neurony v ^-té vrstvě jsou spojeny se všemi neurony ve vrstvě í + 1. ► Vícevrstvou síť lze zadat počty neuronů v jednotlivých vrstvách (např. 2-4-3-2) 101 Vícevrstvá síť Značení: ► Označme ► X množinu vstupních neuronů ► Y množinu výstupních neuronů ► Z množinu všech neuronů (tedy X, Y c Z) ► jednotlivé neurony budeme značit indexy apod. ► fy je vnitřní potenciál neuronu / po skončení výpočtu ► y] je stav (výstup) neuronu / po skončení výpočtu (zde definujeme y0 = 1 jako hodnotu formálního jednotkového vstupu) ► Wjj je váha spoje od neuronu / do neuronu / (zejména wj0 je váha speciálního jednotkového vstupu, tj. wj0 = -bs kde bj je bias neuronu j) ► je množina všech neuronů, z nichž vede spoj do / (zejména 0 g ;<_) ► je množina všech neuronů, do nichž vede spoj z / Vícevrstvá síť Aktivní dynamika: ► vnitřní potenciál neuronu /: ► aktivační funkce oj pro neuron/je libovolná diferencovatelná funkce [ např. logistická sigmoida oj(E) = —^ ] ► Stav nevstupního neuronu / e Z \ X po skončení výpočtu je (yj závisí na konfiguraci w a vstupu x, proto budu občas psát yj(w,x)) ► Síť počítá funkci z R|X| do R|y|. Výpočet probíhá po vrstvách. Na začátku jsou hodnoty vstupních neuronů nastaveny na vstup sítě. V kroku t jsou vyhodnoceny neurony z Mé vrstvy. Vícevrstvá síť Adaptivní dynamika: ► Dána množina T tréninkových vzorů tvaru {(xk/dk) | k = 1,...,p} kde každé xk e R|X| je vstupní vektor a každé dk e R|y| je očekávaný výstup sítě. Pro každé j eY označme dkj očekávaný výstup neuronu / pro vstup xk (vektor dk lze tedy psát jako (cfcy).ey)- ► Chybová funkce: E(w) = YjEk(w) rc=1 kde Ek(w) = \ Yj (VÍ™'**) ~ dkif jeY Vícevrstvá síť - učící algoritmus Dávkový algoritmus (gradientní sestup): Algoritmus počítá posloupnost vektorů vah w(°\ .... ► váhy v jsou inicializovány náhodně blízko 0 ► v kroku t + 1 (zde t = 0,1,2...) je w(ř+1) vypočteno takto: ji ji ji kde je změna váhy w,,- v kroku t + 1 a 0 < e(t) < 1 je rychlost učení v kroku t + 1. Všimněte si, že Jf:(w(ř)) je komponenta gradientu VE, tedy změnu vah v kroku t + 1 lze zapsat také takto: ^ř+1^ = - e(ř) • VE(w^). Vícevrstvá síť - gradient chybové funkce Pro každé wp máme dE y dEk kde pro každé k = 1,..., p platí dEk dEk a pro každé j e Z \X dostaneme —-=ys-dkj proyeY dEu v- dE, -é- ■ OriZr) ■ Wrj PrO j E Z \ ( Y U X) (Zde všechna ys jsou ve skutečnosti yj(w,xk)) 106 Vícevrstvá síť - gradient chybové funkce ► Pokud cry(£) = —pro každé y e Z pak 1 | G J o'j^j) = AjYjO - Yj) a dostaneme pro každé y e Z \ X = yy - cfc/ dys dyj ~ hi dyr pro y € V Aryr(1 - yr) • wry pro y g Z \ (y u X) Pokud (jy(í) = a • tanh(b • £y) pro každé y e Z pak °y(£y) = ^(a-yy)(a + yy) 107 Vícevrstvá síť - výpočet gradientu Algoritmicky lze ^ = £{;=1 |a spočítat takto: Polož fiy/ := 0 (na konci výpočtu bude £y,- = Pro každé k = 1,..., p udělej následující 1. spočítej yy pro každé j e Z a Ac-tý vzor, tedy yy = yy(w,Xk) (tj. vyhodnoť síť ve standardním aktivním režimu) 2. pro všechna j eZ spočítej ^ pomocí zpětného šíření (viz. následující slajd!) 3. spočítej ^ pro všechna w,, pomocí vzorce dEk dEk 4. Gji := £y/ + §j| Výsledné En se rovná .ji I U V I IU Vícevrstvá síť - zpětné šíření dEjr lze spočítat pomocí zpětného šíření: dyj spočítáme ^ pro j eY pomocí vzorce ^ = yy - dq ► rekurzivně spočítáme zbylé ^: Nechť j je v ^-té vrstvě a předpokládejme, že ^ už máme spočítáno pro všechny neurony z vyšších vrstev (tedy vrstev i+ 1,^ + 2,...)-Pak lze ^ spočítat pomocí vzorce protože všechny neurony r e patří do vrstvy £ +1. 109 Složitost dávkového algoritmu Výpočet hodnoty Jf:(w(ř 1)) probíhá v lineárním čase vzhledem k velikosti sítě a počtu tréninkových vzorů (za předpokladu jednotkové ceny operací včetně vyhodnocení ďr(^r) pro dané £r) Zdůvodnění: Algoritmus provede p krát následující 1. vyhodnocení sítě (tj. výpočet yj(w,xk)) 2. výpočet ^ zpětným šířením 3. výpočet §| 4. přičtení^ kBľl Kroky 1.-3. proběhnou v lineárním čase a krok 4. v konstantním vzhledem k velikosti sítě. Počet iterací gradientního sestupu pro přiblížení se (lokálnímu) minimu může být velký... 110 Vícevrstvá síť - ucici algoritmus Online algoritmus: Algoritmus počítá posloupnost vektorů vah w(°\ .... ► váhy v jsou inicializovány náhodně blízko 0 ► vkrokuř + 1 (zde t = 0,1,2,...) je v^(ř+1) vypočteno takto wí;+i) = v^o+aw(o kde kde k = (t mod p) +1 a 0 < e(t) < 1 je rychlost učení v kroku ř + 1. Lze použít i stochastickou verzi tohoto algoritmu, v níž je k voleno náhodně z {1,...,p}. Simulace Simulace Praktické otázky gradientního sestupu ► Otázky týkající se efektivity učení: ► Dávkový nebo online algoritmus? ► Je nutné data předzpracovat? ► Jak volit iniciální váhy? ► Je nutné vhodně volit požadované hodnoty sítě? ► Jak volit rychlost učení e (t) ? ► Dává gradient nejlepší směr změny vah? ► Otázky týkající se výsledného modelu: ► Kdy zastavit učení? ► Kolik vrstev sítě a jak velkých? ► Jak velkou tréninkovou množinu použít? ► Jak zlepšit vlastnosti (přesnost a schopnost generalizace výsledného modelu? Poznámky o konvergenci gradientního sestupu ► Chybová funkce může být velmi komplikovaná: ► může obsahovat mnoho lokálních minim, učící algoritmus v nich může skončit ► může obsahovat mnoho plochých míst s velmi malým gradientem, zejména pokud se aktivační funkce tzv. saturují (tedy jejich hodnoty jsou blízko extrémům; v případě sigmoidálních funkcí to znamená, že mají velké argumenty) ► může obsahovat velmi strmá místa, což vede k přeskočení minim gradientním sestupem pro velmi malou rychlost učení máme větší šanci dokonvergovat do lokálního minima, ale konvergence je hodně pomalá Teorie: pokud e(ř) = { pak dávkový i stochastický gradientní sestup konvergují k lokálnímu minimu (nicméně extrémně pomalu). ► pro příliš velkou rychlost učení může vektor vah střídavě přeskakovat minimum nebo dokonce divergovat Gradientní sestup - ilustrace Gradientní sestup s malou rychlostí učení: ▲ Více méně hladká křivka, každý krok je kolmý na vrstevnici. Obrázek: Neural Computation, Dr John A. Bullinaria Gradientní sestup - ilustrace Gradientní sestup s příliš velkou rychlostí učení: -► Jednotlivé kroky přeskakují minimum, učení je pomalé. Obrázek: Neural Computation, Dr John A. Bullinaria Gradientní sestup - ilustrace Online učení: A Kroky nemusí být kolmé na vrstevnice, může hodně kličkovat. Obrázek: Neural Computation, Dr John A. Bullinaria Dávkový vs online učící algoritmus Výhody dávkového: ► realizuje presne gradientní sestup pro chybovou fci (většinou konverguje k lokálnímu minimu) ► snadno paralelizovatelný (vzory je možné zpracovávat odděleně) Nevýhody dávkového: ► paměťová náročnost (musí si pamatovat chyby všech vzorů) ► redundantní data nepřidávají informaci ke gradientu. Výhody online (stochastického) ► stochastický má šanci uniknout z okolí mělkého minima (protože nerealizuje přesný grad. sestup) ► má menší paměťovou náročnost a snadno se implementuje ► je rychlejší, zejména na hodně redundantních datech Nevýhody online (stochastického) ► není vhodný pro paralelizaci ► může hodně kličkovat (více než gradientní sestup) Moment Problémy s gradientním sestupem: ► Může se stát, že gradient WE(w^) neustále mění směr, ale chyba se postupně zmenšuje. Toto často nastává, pokud jsme v mělkém údolí, které se mírně svažuje jedním směrem (něco jako U-rampa pro snowboarding, učící algoritmus potom opisuje dráhu snowboardisty) ► Online algoritmus také může zbytečně kličkovat. Tento algoritmus se vůbec nemusí pohybovat ve směru největšího spádu! Řešení: Ke změně vah dané gradientním sestupem přičteme část změny v předchozím kroku, tedy definujeme Aw{t) = Aw^ +a- Aw{t~^ ji ji kde 0 < a < 1. S momentem: Volba aktivační funkce Požadavky na vhodnou aktivační funkci o(£,)\ 1. diferencovatelnost (jinak neuděláme gradientní sestup) 2. nelinearita (jinak by vícevrstvé sítě byly ekvivalentní jednovrstvým) 3. omezenost (váhy a potenciály budou také omezené => konečnost učení) 4. monotónnost (lokální extrémy fce o zanáší nové lokální extrémy do chybové funkce) 5. linearita pro malé £ (umožní lineární model, pokud stačí k řešení úlohy) Sigmoidální funkce splňují všechny požadavky. Síť se sigmoidálními funkcemi obvykle reprezentuje data distribuované (tj. více neuronů vrací větší hodnotu pro daný vstup). Později se seznámíme se sítěmi, jejichž aktivační funkce porušují některé požadavky (Gaussovy funkce) - používá se jiný typ učení. Volba aktivační funkce ► Z hlediska rychlosti konvergence je výhodné volit lichou aktivační funkci. ► Standardní sigmoida není lichá, vhodnější je použít hyperbolický tangens: a(£) = a- tanh(b-£) ► Při optimalizaci lze předpokládat, že sigmoidální funkce jsou fixní a hýbat pouze dalšími paramtery. ► Z technických důvodů budeme dále předpokládat, že všechny aktivační funkce jsou tvaru ay(£y) = a-tanh(b-£y) kde a 1.7159 a b _ 2 3- Volba aktivační funkce 1.5H 1.0H 0.5 H 0.0 -0.5 H -1.0 H -1.5H -4-3-2-1 0 1 2 3 a(£) = 1.7159 • tanh(| • 4), platí lim^, o (Z) = 1.7159 a lim^-ooíTfé) = -1.7159 Volba aktivační funkce -1.0 -0.8 -0.6 -0.4 -0.2 0.0 0.2 0.4 0.6 0.8 1.0 a(£) = 1.7159 • tanh(| • £) je téměř lineární na [-1,1 ] první derivace funkce a(£) = 1.7159 • tanh(| • £) druhá derivace funkce a(£) = 1.7159 • tanh(| • £) Předzpracování vstupů ► Některé vstupy mohou být mnohem větší než jiné Př.: Výška člověka vs délka chodidla (oboje v cm), maximální rychlost auta (v km/h) vs cena (v Kč), apod. ► Velké komponenty vstupů ovlivňují učení více, než ty malé. Navíc příliš velké vstupy mohou zpomalit učení. ► Numerická data se obvykle normalizují tak, že mají ► průměrnou hodnotu = 0 (normalizace odečtením průměru) ► rozptyl = 1 (normalizace podělením směrodatnou odchylkou) Zde průměr a směrodatná odchylka mohou být odhadnuty z náhodného vzorku (např. z tréninkové množiny). (Ilustrace směrodatné odchylky) Předzpracování vstupů ► Jednotlivé komponenty vstupu by měly mít co nejmenší korelaci (tj. vzájemnou závislost). (Metody pro odstranění korelace dat jsou např. analýza hlavních komponent (Principal Component Analysis, PCA). Lze ji implementovat i pomocí neuronových sítí (probereme později)). I n i c i á I n í volba vah ► Iniciálně jsou váhy nastaveny náhodně z daného intervalu [-w, w] kde w závisí na počtu vstupů daného neuronu. Jaké je vhodné w? ► Uvažujeme aktivační funkci 1.7159 • tanh(| • E) pro všechny neurony. ► na intervalu [-1,1] se o chová téměř lineárně, ► extrémy o" jsou přibližně v bodech -1 a 1, ► mimo interval [-4,4] je o blízko extrémních hodnot. Tedy ► Pro velmi malé w hrozí, že obdržíme téměř lineární model (to bychom mohli dostat s použitím jednovrstvé sítě). Navíc chybová funkce je velmi plochá v blízkosti 0 (malý gradient). ► Pro w mnohem větší než 1 hrozí, že vnitřní potenciály budou vždy příliš velké a síť se nebude učit (gradient chyby £ bude velmi malý, protože hodnota sítě se téměř nezmění se změnou vah). Chceme tedy zvolit w tak, aby vnitřní potenciály byly zhruba z intervalu [-1,1]. Inicialni volba vah ► Data mají po normalizaci (zhruba) nulovou střední hodnotu, rozptyl (zhruba) 1 a předpokládejme, že jednotlivé komponenty vstupů jsou (téměř) nekorelované, ► Uvažme neuron j z první vrstvy s d vstupy, předpokládejme, že jeho váhy jsou voleny uniformně z intervalu [-w, w]. ► Pravidlo: w je dobré volit tak, že směrodatná odchylka vnitřního potenciálu £y (označme ji oy) leží na hranici intervalu, na němž je aktivační funkce o j téměř lineární tj. v našem případě chceme oy « 1. ► Z našich předpokladů plyne oy = ^ • w. tj. v našem případě položíme w = -^j. ► Totéž funguje pro vyšší vrstvy, d potom odpovídá počtu neuronů ve vrstvě o jedna nižší. (Zde je důležité, že je aktivační funkce lichá) Požadované hodnoty ► Požadované hodnoty dq by měly být voleny v oboru hodnot aktivačních funkcí, což je v našem případě [-1.716,1.716]. ► Požadované hodnoty příliš blízko extrémům +1.716 způsobí, že váhy neomezeně porostou, vnitřní neurony budou mít velké potenciály, gradient chybové funkce bude malý a učení se zpomalí. ► Proto je vhodné volit požadované hodnoty z intervalu [-1.716 + 6,1.716-0]. Optimální je, když tento interval odpovídá maximálnímu intervalu na němž jsou aktivační fce lineární. Tedy v našem případě ô « 0.716, tj. hodnoty dkj je dobré brát z intervalu [-1,1]. Rychlost učení Obecné zásady pro volbu a změny rychlosti učení e ► Je dobré začít s malou rychlostí (např. e = 0.01). (existují i metody, které pracují s velkou počáteční rychlostí a poté ji postupně snižují) ► Pokud se chyba znatelně zmenšuje (učení konverguje), můžeme rychlost nepatrně zvýšit. ► Pokud se chyba zjevně zvětšuje (učení diverguje), můžeme rychlost snížit. ► Krátkodobé zvýšení chyby nemusí nutně znamenat divergenci. E h / Obr. 2.3: Typický vývoj chyby v čase při učení pomocí back propagation. Rychlost učení Chceme, aby se neurony učily pokud možno stejně rychle. Více vstupů obvykle znamená rychlejší učení. Pro každou váhu w,, můžeme mít zvláštní rychlost učení ej\ ► 8jj lze iniciovat např. 1 /|y<_|, kde |y<_| je počet vstupů neuronu /. ► Po zahájení učení rychlost zvolna zvyšujeme (třeba er,{t) = K+ . er,{t - 1) kde K+ > 1) ► Jakmile se změní znaménko A^ř' (tedy Avví.ř~1^ • A^' < 0), rychlost snížíme (třeba takto ey/(ř) = K~ . ey/(f - 1) kde K~ < 1) Algoritmus Rprop bere v potaz pouze směr gradientu, velikost kroku se mění výše uvedeným násobením fixními konstantami K+ a K~. (Více na https://en.wikipedia.org/wiki/Rprop) Rychlost a směr - přesněji Na gradientní sestup se můžeme dívat obecněji takto: Aw^ = r(ř). S(ř) kde r(ř) je rychlost změny vah a s(ř) je směr změny vah. V našem případě: r(ř) = e(t) a s(ř) = -VE(w(ř)) (nebo s(ř) = -VE/^w^)) pro online učení). ► Ideální by bylo volit r(ř) tak, abychom minimalizovali E(vř(ř) + r(r).s(r)). Nebo se aspoň chceme přesunout (ve směru s(ř)) do místa, v němž začne gradient opět růst. ► Toho lze (přibližně) dosáhnout malými přesuny bez změny směru - nedostaneme ovšem o mnoho lepší algoritmus než standardní grad. sestup (který stále mění směr). ► Existují lepší metody, např. parabolická interpolace chybové funkce. Rychlost a směr - parabolická interpolace Označme E(r) = E(w^ + r • s(ř)); minimalizujeme E(r). Předpokládejme, že jsme schopni nalézt body A, B, C takové, že E(A) > E(S) a E(C) > E(B). Pak lze tyto body proložit parabolou a nalézt její minimum D. Toto D je dobrým odhadem minima E(r). Obrázek: Neural Computation, Dr John A. Bullinaria Rychlost a směr - parabolická interpolace Parabolickou interpolaci lze dále iterovat, čímž dosáhneme ještě lepšího odhadu: Je jasné, že E(B) > E(D) a E(C) > E(D). Pokud E(B) > E(D), lze použít stejný postup jako předtím (jinak je nutné nalézt nový bod B' t. ž. E(B') > E(D)). Optimální směr Zbývá otázka, jestli je záporný gradient správným směrem Rychlost r(ř) jsme volili tak, abychom minimalizovali e(w^) = e(w^ + r(t)-s(t)) = E(vřW + r(ř)-(-VE(vřW)) To ovšem znamená, že derivace E(w(ř+1)) podle r(ř) (zde bereme r(ř) jako nezávislou proměnnou) bude 0, tedy <5r á-j ôwjj \ ôWjj = VE(vříř+1))-(-VE(vřW)) = 0 Tj. nový a starý směr jsou vzájemně kolmé, výpočet tedy kličkuje. Gradientní sestup s optimální rychlostí Obrázek: Neural Computation, Dr John A. Bullinaria Rychlost a směr - přesněji Řešení: Do nového směru zahrneme částečně i předchozí směr a tím zmenšíme kličkování. s(f) = -VE(tfW)+j8-s(f-1) Jak určit p ? Metoda sdružených gradientů je založena na tom, že nový směr by měl co nejméně kazit minimalizaci dosaženou v předchozím směru. Chceme nalézt nový směr s(ř) takový, že gradient funkce funkce E v novém bodě vi/(ř+1) = #(0 + r(ř) • s(ř) ve starém směru s(ř - 1) je nulový: s(f-1)-VE(tf(ř+1>) = 0 Vhodné p, které to splňuje je dáno následujícím pravidlem (Polak-Ribiere): _ (VE(w(ř+1)) - VE(wW)) • VE(vř(ř+1)) ^~ VE(vř(0)-VE(vř(0) (Pokud by E byla kvadratická funkce, pak to konverguje v nejvýše n krocích) Gradientní sestup s optimální rychlostí Obrázek: Neural Computation, Dr John A. Bullinaria Další metody Existuje mnoho metod druhého řádu, které jsou přesnější, ale obvykle výpočetně mnohem náročnější (příliš se nepoužívají). Např. Newtonova metoda, Levenberg-Marquardt, atd. Většina těchto metod vyžaduje výpočet (nebo aspoň aproximaci) druhé derivace chybové funkce nebo funkce sítě (tj. Hessián). Lze nalézt v literatuře, např. Haykin, Neural Neworks and Learning Machines 142 Schopnost generalizace V klasifikačních problémech se dá generalizace popsat jako schopnost vyrovnat se s novými vzory. Pokud síť trénujeme na náhodně vybraných datech, není ideální přesně klasifikovat tréninkové vzory. Pokud aproximujeme funkční závislost vstupů a očekávaných výstupů pak obvykle nechceme aby funkce sítě vracela přesné hodnoty pro tréninkové vzory. Exaktněji: Obvykle se předpokládá, že tréninková množina byla generována takto: dkj = 9j(Xk) + Okj kde Qj je správná funkce výstupního neuronu j e Y a Q q je náhodný šum. Chceme, aby síť pokud možno realizovala funkce gľ Kdy zastavit učení? Standardní kritérium: Chyba E je dostatečně malá. Další možnost: po několik iterací je gradient chyby malý. (Výhodou tohoto kritéria je, že se nemusí počítat chyba E) Problém: Příliš dlouhé učení způsobí, že síť opisuje tréninkové vzory (je přetrénovaná). Důsledkem je špatná generalizace. Řešení: Množinu vzorů rozdělíme do následujících množin ► tréninková (např. 60%) - podle těchto vzorů se síť učí ► validační (např. 20%) - používá se k zastavení učení. ► testovací (např. 20%) - používá se po skončení učení k testování přesnosti sítě, tedy srovnání několika natrénovaných sítí. Trénink, testování, validace Obvykle se realizuje několik iterací (cca 5) tréninku na tréninkové množině. Poté se vyhodnotí chyba E na validační množině. Ideálně chceme zastavit v minimu chyby na validační množině. V praxi se sleduje, zda chyba na validační množině klesá. Jakmile začne růst (nebo roste po několik iterací za sebou), učení zastavíme. Problém: Co když máme příliš málo vzorů? Můžeme tréninkovou množinu rozdělit na K skupin S^/.../ Sk-Trénujeme v K fázích, v ^-té fázi provedeme následující: ► trénujeme na Si u ... u S^_i u S^+1 u ... u Sk ► spočteme chybu funkce E na skupině Celková chyba je potom průměr e = ^ Y$=-\ e^. Extrémní verze: K = počet vzorů (používá se při extrémně málo vzorech) Typicky se volí K = 10. Velikost sítě Podobný problém jako v případě délky učení: ► Příliš malá síť není schopna dostatečně zachytit tréninkovou množinu a bude mít stále velkou chybu ► Příliš velká síť má tendenci přesně opsat tréninkové vzory - špatná generalizace Řešení: Optimální počet neuronů :-) ► teoretické výsledky existují, ale jsou většinou nepoužitelné ► existují učící algoritmy, které postupně přidávají neurony (konstruktivní algoritmy) nebo odstraňují spoje a neurony (prořezávání) ► V praxi se počet vrstev a neuronů stanovuje experimentálně (prostě se to zkusí, uvidí, opraví) a/nebo na základě zkušeností. Velikost sítě Uvažme dvouvrstvou síť. Neurony ve vnitřní vrtvě často reprezentují "vzory" ve vstupní množině. Př.: Síť 64-2-3 pro klasifikaci písmen: sample training patterns mu mm learned input-to-hidden weights Vynechávání neuronů během učení (dropout) Přetrénování může souviset s přílišnou "závislostí" jednotlivých neuronů na chování ostatních neuronů. Pokud má síť mnoho neuronů, je schopna zachytit složité závislosti v datech mnoha různými způsoby, přičemž téměř všechny budou špatné na validační množině. Tomu lze předcházet použitím následující metody: V každém kroku gradientního sestupu měníme váhy každého jednotlivého neuronu pouze s pravděpodobností 1 /2 (v praxi lze i < 1 /2). Jinými slovy: Každý neuron je pro daný krok vyhozen ze sítě (neučí se) s pravděpodobností 1 /2. Tato metoda by měla předcházet složitým "společným" adaptacím více neuronů. Lze ji také vidět jako metodu pro trénink skupiny mnoha neuronových sítí vytvořených vyhazováním neuronů. 148 Velikost tréninkové množiny Příliš malá nebo nereprezentativní tréninková množina vede ke špatné generalizaci Příliš velká zvyšuje složitost učení. V případě dávkového algoritmu způsobuje velkou chybu (chyby na vzorech se sčítají). což může vést k přetrénování. Pravidlo pro klasifikační úlohy: počet vzorů by měl zhruba odpovídat W/o kde ► W je počet vah v síti ► 0 < ô < 1 je tolerovaná chyba na testovací množině (tj. tolerujeme ô chybně klasifikovaných vzorů z testovací množiny) 149 Regularizace - upadání vah (weight decay) Generalizaci lze zlepšit tak, že v síti necháme jen nutné neurony a spoje. Možná heuristika spočívá v odstranění malých vah. Penalizací velkých vah dostaneme silnější indikaci důležitosti vah. V každém kroku učení zmenšíme uměle všechny váhy «f'> = (1 - C)(«f + Awjp) Idea: Nedůležité váhy budou velmi rychle klesat k 0 (potom je můžeme vyhodit). Důležité váhy dokážou přetlačit klesání a zůstanou dostatečně velké. Toto je ekvivalentní gradientnímu sestupu s konstantní rychlostí učení £, pokud chybovou funkci modifikujeme takto: E'(vv) = E(vv) + y(vv- w) Zde regularizační člen ^(vv • vv) penalizuje velké váhy. Praxe - Matice zmätenosti Confusion matrix Síť má za úkol klasifikovat objekty do K tříd T\,..., TK. Confusion matrix je tabulka, jejíž pole v Mém řádku a y-tém sloupci obsahuje počet objektů z třídy T,, které byly klasifikovány jako objekty z třídy 7). Example confusion matrix Predicted Cat Dog J Rabbit Actual Cat 5 3 0 Dog 2 3 1 Rabbit 0 2 11 Zdroj: http://en.wikipedia.org/wiki/Confusion_matrix Asociativní sítě Cílem je uchovat množinu vzorů {(x^^) | Ac = 1,___,p} tak, aby platilo následující: Po předložení nového vstupu x, který je blízko některému xk bude výstup sítě roven nebo alespoň blízko dk (tato schopnost se nazývá asociace). Zejména by síť měla mít schopnost reprodukce: Pro vstup xk by měla dát výstup dk. Lineární asociativní síť (alias ADALINE s Hebbovým učením) (Pro jednoduchost a srovnání s ADALINE uvážíme pouze jeden výstup) Organizační dynamika LAS: Xq = 1 X2 X n w= (w0,wi,...,wn) ax = (xo,xi,...,xn) kde x0 = 1 Aktivní dynamika: funkce sítě: y[vv](x) = w • x = £"=0 w,x/ Hebbovo učení Adaptivní dynamika: Dána množina tréninkových vzorů T = {(x1/d1)/(x2/d2)/.../(xp/c/p)} Zde xk = (x/c0/x/c1... ,xkn)T e Rn+1, x^o = 1, je vstup /c-tého vzoru a dk e IR je očekávaný výstup. Intuice: chceme, aby síť počítala afinní aproximaci funkce, jejíž (některé) hodnoty nám předepisuje tréninková množina. Hebbovo učení Hebbův zákon: When an axon of a cell A is near enough to excite a cell B and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that A's efficiency, as one of the cells firing B, is increased. Zákon formuloval neuropsycholog Donald Hebb v knize the organization of Behavior z roku 1949. Jinými slovy: Cells that fire together, wire together Formulace používaná v umělých NS: Změna váhy spoje mezi dvěma neurony je úměrná jejich souhlasné aktivitě. Hebb se snažil vysvětlit podmíněné reflexy: Současná aktivita/pasivita presynaptického neuronu (příčina) a postsynaptického neuronu (reakce) posiluje/zeslabuje synaptickou vazbu. 155 Hebbovo učení LAS Algoritmus počítá posloupnost vektorů vah w(°\ w^\..., : ► wj0) = o pro 0 < / < n, ► v kroku k (zde k = 1,2,...) je síti předložen vzor (xk,dk) a váhy se adaptují podle Hebbova zákona: Výsledný vektor: p tí = vft>) = Y4>tkdk = XTB /c=1 kde X je matice, která má v i-tém řádku vektor xj a d = {dA,...,dp)T LAS a ortonormální vstupy Pokud jsou ,..., xp ortonormální, tedy xJxj = 0 i±j 1 i = j pak LAS má schopnost reprodukce: /c=1 /c=1 157 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 ) V/c=1 P T U k=1 U < n U /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 159 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,,- celočíselnou váhu spoje od neuronu / e {1,..., n] k neuronu / e {1,..., n] ► Zatím: žádný neuron nemá bias a přepokládáme w# = 0 pro každé / = 1,..., n 160 Hopf ieldova síť Adaptivní dynamika: Dána tréninková množina T = [xk | xk = (xM,...,xkn) e {-1,1}n,/c = 1,...,p} Adaptace probíhá podle Hebbova zákona (podobně jako u LAS). Výsledná konfigurace je p wi' = Yj XkíXki 1 ^ͱ'l^n Všimněte si, že wy, = w/,, 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 = xki neuronů / a; a počtem rozdílných stavů xk-} ± xk\. Hopf ieldova síť Aktivní dynamika: Iniciálně jsou neurony nastaveny na vstup x = (x-i,..., xn) sítě, tedy y^ = x} pro každé / = 1,..., n. Cyklicky aktualizujeme stavy neuronů, tedy v kroku t + 1 aktualizujeme neuron /, t. ž. / = (ř mod p) + 1, takto: nejprve vypočteme vnitřní potenciál n /=1 a poté Hopfieldova síť - aktivní dynamika Výpočet končí v kroku ř* pokud se síť nachází (poprvé) ve stabilním stavu, tj. ,f«> = ,<'•> (/=1.....n) Theorem 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 ý(l/l/,x) = [y\f \...,y% ^ hodnotu funkce sítě pro vstup x a matici vah W. Dále označme y7(W, x) = yíř ^ složku hodnoty funkce sítě, která odpovídá neuronu /. Pokud bude W jasné z kontextu, budu psát jen y(x) a y(x) 163 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 T T T T * orientaci každého magnetu ovlivňuje lilii jednak vnější magnetické pole * t t t 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ů 164 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/,y/y/ je stabilní a malé (záporné) w/,y/y/ 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 Obr. 3.4: Energetická plocha. 166 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 ► 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 168 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 wjh pak nové váhy wj. spočítáme pomocí Wji = Wji - XjXj (tj. podobně jako při adaptaci podle Hebbova zákona, ale s opačným znaménkem) 169 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[Xk=ý(W,Jtk)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). 170 Hopf ieldova síť - asociace Problém: ► příliš mnoho vzorů implikuje existenci lokálních minim funkce £, 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 £ ► 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 £ 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. Hopfieldova síť - příklad 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ě 172 Hopf ieldova síť - příklad obnovení vzoru ■■■■■■■ > ¥JSSSSSilíriSf^ 173 Hopfieldova síť - příklad rekonstrukce vzoru 174 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,,- celočíselnou váhu spoje od neuronu / g {1,..., n] k neuronu / e {1,..., n}. ► přepokládáme Wy = 0 pro každé / = 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) g {0,1 }n sítě, tedy y|0) = x} pro / = 1,..., n. V kroku t + 1 aktualizujeme neuron /, t. ž. / = (ř mod p) + 1, takto: nejprve vypočteme vnitřní potenciál n /=1 a poté (ř+1) _ ] = < 1 0 (0 v ď} > o If < o Hopf ieldova síť - aktivní dynamika Výpočet končí v kroku ř* pokud se síť nachází (poprvé) ve stabilním stavu, tj. yf^=yp y=i.....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+ÍL6iY 2 y=i /=1 /=1 V průběhu výpočtu se energie nezvyšuje: E(y^) > E(ý(ř+1)), stav ý(r) odpovídá lokálnímu minimu funkce E. Theorem Za předpokladu symetrie vah, výpočet Hopfieldovy sítě skončí pro každý vstup. (Důkaz stejný jako předtím) 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(Ú) = í n \ Z U, VV/=1 j \ - 1 Požadované vektory jsou právě minima této funkce Ale , n n u^ = -pL(-2)ü/^+L(-1)ü/+1 /=i a tedy U (u) - 1 je energetickou funkcí sítě (viz. následující slajd). , n n E(Ü) = --^(-2)uiUj + YJ(-^i lij /=1 180 Příklad: n věží vr v r 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 7' - 1 aU2:|0,1) v\/=1 7 R: 7 n u2(u)=e e /=i v n \ U 'Ji U=1 \2 - 1 7 7 Požadované vektory jsou právě minima funkce U = U-i + U2. Minima U odpovídají stavům s minimální energií v následující síti. 181 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ální minima Hledáme (globální) minima energie £ .... 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; 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 n /=1 kde fé) 1 + e-uím Parametr T(r) se nazývá teplota v čase ř. ► Velmi vysoká teplota 7(ř) znamená, že se chová téměř (uniformně) náhodně. 1 « \ a síť ► Velmi nízká teplota 7(ř) znamená, že buď P[yyř+1^ = i] ~ 1 nebo P [yjt+^ = i] ~ 0 v závislosti na tom, jestli ^ > 0 nebo < 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(ý) = -\EjLi _Xi v^yy + __,n=i 0/y 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. 185 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(ř) = r]ř • 7(0) kde r] < 1 je blízko 1 ► nebo T(ř) = 7(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. Boltzmannův stroj Organizační dynamika: ► Cyklická síť se symetrickými spoji (tj. libovolný neorientovaný graf) ► Množinu všech neuronů značíme N ► označme £y vnitřní potenciál a yy výstup (stav) neuronu / ► stav stroje: ý e {-1,1}|/n/|. ► označme wy; reálnou váhu spoje od neuronu / k neuronu /. ► žádný neuron nemá bias a přepokládáme wn = 0 pro / g N. 187 Botzmannův stroj Aktivní dynamika: Stavy neuronů jsou iniciálně nastaveny na hodnoty z množiny {-1,1}, tj. y|0) e {-1,1} pro / e N. V Mém kroku aktualizujeme náhodně vybraný neuron j e N takto: nejprve vypočteme vnitřní potenciál n a poté náhodně zvolíme hodnotu y)} e {-1,1} tak, že P[)f = l] = a(íf-1>)kde 1 + e-2£/T(o Parametr T(f) se nazývá teplota v čase t. Boltzmannův stroj Velmi vysoká teplota T(ŕ) znamená, že P [y|ŕ) = 1 ] « 1 a stroj se chová téměř náhodně. Velmi nízká teplota T(r) znamená, že buď P[y^ = 1 ] ~ 1 nebo P [yír^ = 1 ] « 0 v závislosti na tom, jestli ^ > 0 nebo ^ < 0. Potom se stroj chová téměř deterministicky (tj. jako Hopfieldova síť). 189 Boltzmannův stroj - reprezentace rozložení Cíl: Chceme sestrojit síť, která bude reprezentovat dané pravděpodobnostní rozložení na množině vektorů {-1,1}|/N/|. Velmi hrubá a nepřesná idea: Boltzmannův stroj mění náhodně svůj stav z množiny {-1,1}|/N/|. Když necháme B. stroj běžet dost dlouho s fixní teplotou, potom budou frekvence návštěv jednotlivých stavů nezávislé na iniciálním stavu. Tyto frekvence budeme považovat za pravděpodobnostní rozložení na {-1,1}|/N/| reprezentované B. strojem. V adaptivním režimu bude zadáno nějaké rozložení na stavech a cílem bude nalézt konfiguraci takovou, že rozložení reprezentované strojem bude odpovídat zadanému rozložení. 190 Rovnovážný stav Fixujme teplotu T (tj. T(ŕ) = T pro t = 1,2,...). Boltzmannův stroj se po jisté době dostane do tzv. termální rovnováhy. Tj. existuje čas ť takový, že pro libovolný stav stroje y* e {-1,1}|/N/| a libovolné ŕ* > ť platí, že P/v(/):=P[y(r)=ľ] splňuje p/v(y*) ~ le~E^*)/7 kde / 1/1/z. 1/. i/^ 7€{-i7i}iwi y tj. Boltzmannovo rozložení Pozn.: Teorie Markovových řetězců říká, že P [ý(r) = y*j je také dlouhodobá frekvence návštěv stavu y\ Toto platí bez ohledu na iniciální nastavení neuronů! Síť tedy reprezentuje rozložení pN. Boltzmannův stroj - učení Problém: Tak jak jsme si jej definovali má Boltzmannův stroj omezenou schopnost reprezentovat daná rozložení. Proto množinu neuronů N disjunktně rozdělíme na ► množinu viditelných neuronů V ► množinu skrytých neuronů S. Pro daný stav viditelných neuronů a e {-1,1}'V| označme Pv(a) = P/s/(a,j8) J8e{-1/I}isi pravděpodobnost stavu viditelných neuronů a v termálním ekvilibriu bez ohledu na stav skrytých neuronů. Cílem bude adaptovat síť podle daného rozložení na 192 Boltzmannův stroj - učení Adaptivní dynamika: Nechť Pd je pravděpodobnostní rozložení na množině stavů viditelných neuronů, tj. na Cílem je nalézt konfiguraci sítě W takovou, že py odpovídá Pd- Vhodnou mírou rozdílu mezi rozděleními pv a Pd je relativní entropie zvážená pravděpodobnostmi vzorů (tzv. Kullback-Leibler divergence) ae{-1,1}ivi Pd{a) In Pd{a) Pv(a) 193 Boltzmannův stroj - učení S(w) budeme minimalizovat pomocí gradientního sestupu, tj budeme počítat poslounost matic vah W(°\ ... ► váhy v jsou inicializovány náhodně blízko 0 ► v ^-tém kroku (zde l = 1,2,...) je l/l/^) vypočteno takto: ji ji ji kde A# = _,W.^(W(M)) j1 dWj, je změna váhy v ^-tém kroku a 0 < e (i) < 1 je rychlost učení v ^-tém kroku. Zbývá spočítat (odhadnout) IV). Boltzmannův stroj - učení Formálním derivováním funkce 8 lze ukázat, že dWy/ T\\w 7' /f/xed Vy 7/ Ifree, ► (yíř Mř ^ je průměrná hodnota yíř Víř ^ v termální \7i 7' /fixedJ ^ w 7/ rovnováze za předpokladu, že hodnoty viditelných neuronů jsou fixovány na počátku výpočtu dle rozložení pd. * (yf Vf ^)free Je Průměrná hodnota yj* ^ v termální rovnováze bez fixace viditelných neuronů. Celkově Aw^ = -£(0~(^-1)) ^ OWjj — í(y{ny{n) -(y(nyin) T \V) y' 'fixed VI yi /free 195 Boltzmannův stroj - učení Pro výpočet (y^ ^)fjxed proveď následující: ► Polož J/:=0a proveď následující akce q krát: 1. fixuj náhodně hodnoty viditelných neuronů dle rozložení p_ (tj. v průběhu následujících kroků je neaktualizuj) 2. simuluj stroj po ť kroků 3. přičti aktuální hodnotu yíř ^ k proměnné _/. ► J//q bude dobrým odhadem (yj* \f ^)fjxed za předpokladu že q je dostatečně velké číslo. (yf Vf ^)free se odhadne podobně, pouze se nefixují viditelné neurony (tj. v kroku 1. se zvolí libovolný startovní stav a v následném výpočtu se mohou aktualizovat všechny neurony). 196 Boltzmannuv stroj - učeni Pro upresnení analytická verze: (y{nyin) = Vi y\ /fixed ae|-1,1}M iSe{-1,1)lsl V ' kde yj je výstup neuronu j ve stavu (a,jS). ľe{-1,1}N Omezený Boltzmannův stroj (OBS) Organizační dynamika: ► Cyklická síť se symetrickými spoji, neurony jsou rozděleny do dvou skupin: ► V - viditelné ► S - skryté Množina spojů je V x S (tj. úplný bipartitní graf) ► Množinu všech neuronů značíme N ► označme £y vnitřní potenciál a yy výstup (stav) neuronu / ► stav stroje: ý e {0,1}|/n/|. ► označme wj-, váhu spoje mezi neuronem / a neuronem /. ► Uvažme bias: Wj0 je váha mezi neuronem / a "fiktivním" neuronem 0 jehož hodnota y0 je stále 1. 198 Omezený Botzmannův stroj Aktivní dynamika: Hodnoty viditelných neuronů jsou iniciálně nastaveny na hodnoty z množiny {0,1}. V Mém kroku aktualizujeme neurony takto: ► t liché: náhodně zvolíme nové hodnoty skrytých neuronů, pro j e S p[if=i]=i 1 + exp v L(ř-1) W0J V ieV \ ► ř sudé: náhodně zvolíme nové hodnoty viditelných neuronů, pro j e V p[if=i]=i 1 + exp L(ř-1) W0J V v ieS 199 Rovnovážný stav Definujeme energetickou funkci E E(ý) = - Yj wriy]yi-Y4w^yi'lLw^ ieV,jeS ieV jeS Omezený Boltzmannův stroj se po jisté době dostane do termální rovnováhy. Tj. existuje čas ŕ* takový, že pro libovolný stav stroje y* e {0,1 }|/N/| platí P [y(r) = f] - PN(f) Zde pN(y) = le~E^) kde Z= Yj e_e(7) ye{0,1 tj. Boltzmannovo rozložení Síť tedy reprezentuje rozložení p/v. 200 Omezený Boltzmannův stroj - učení Pro daný stav viditelných neuronů a e {0,1 označme pravděpodobnost stavu viditelných neuronů a v termální rovnováze bez ohledu na stav skrytých neuronů. Adaptivní dynamika: Nechť Pd je pravděpodobnostní rozložení na množině stavů viditelných neuronů, tj. na {0,1}|V|. Rozložení pd může být dáno tréninkovou posloupností tak, že kde #(a,T) je počet výskytů a v posloupnosti T Cílem je nalézt konfiguraci sítě W takovou, že py odpovídá Pd- /M0,1}is Pó{a) = #{ol,T)Ip Omezený Boltzmannův stroj - učení Vhodnou mírou rozdílu mezi rozděleními pv a Pd je relativn entropie zvážená pravděpodobnostmi vzorů (tzv. Kullback Leibler distance) Pd(a) (Odpovídá maximální věrohodnosti vůči posloupnosti T v případě, že Pd je definováno pomocí T) Omezený Boltzmannův stroj - učení G(w) budeme minimalizovat pomocí gradientního sestupu, tj budeme počítat posloupnost vektorů vah w(°\ ... ► váhy v jsou inicializovány náhodně blízko 0 ► v ř-tém kroku (zde ř = 1,2,...) je vypočteno takto: j' j' j' kde Av,(0 = _,(ř).^(^-1)) j1 dWj, je změna váhy v ř-tém kroku a 0 < e(t) < 1 je rychlost učení v ř-tém kroku. Zbývá spočítat (odhadnout) Jj|(vfr). Omezený Boltzmannův stroj - učení Lze ukázat, že dWji \\yjy,/fixed Vj y> ffree, ► (yjyi)fjxed Je průměrná hodnota y/y, po jednom kroku výpočtu za předpokladu, že hodnoty viditelných neuronů jsou fixovány dle rozložení pd. * (yf Vf ^)free Je průměrná hodnota yj* \f ^ v termální rovnováze bez fixace viditelných neuronů. Problém: výpočet (y^ ^)free trv^ dlouho (musíme opakovaně přivést stroj do termální rovnováhy). (yf Vf ^)free se Proto nahrazuje (yjyi)recon c°ž je průměrná hodnota y^yf^ za předpokladu, že iniciální hodnoty viditelných neuronů jsou voleny dle Pd. Omezený Boltzmannův stroj - učeni Tedy AWjP = £(0 • ((WftBd " M recon) se vypočte takto: Polož J/:=0a opakuj q krát: ŕ/xed (y/y/), ► fixuj náhodně hodnoty viditelných neuronů dle pd ► simuluj jeden krok výpočtu a přičti aktuální hodnotu yy, k J/ Pro vhodné q bude J//q dobrým odhadem (y/y)f/x . se vypočte takto: Polož J/:=0a opakuj q krát: recon ► nastav náhodně hodnoty viditelných neuronů dle ► simuluj tři kroky výpočtu a přičti aktuální hodnotu yy, k J/ (tj. vypočti hodnoty skrytých neuronů, potom hodnoty viditelných (tzv. rekonstrukci vstupu) a potom hodnoty skrytých neuronů) Pro vhodné q bude J//q dobrým odhadem (yyy/) recon (y]yi)fjxed Je možné počítat analyticky pro vhodně zadané Pc/. 205 Hluboké site Standardní vícevrstvá síť Organizační dynamika: Výstupní Q O CLOJO Skryté CTa DX) Vstupní Neurony jsou rozděleny do vrstev (vstupní a výstupní vrstva: obecně několik skrytých vrstev) Vrstvy číslujeme od 0; vstupní vrstva je nultá ► Např. třívrstvá síť se skládá z jedné vstupní, dvou skrytých a jedné výstupní vrstvy Neurony v ^-té vrstvě jsou spojeny se všemi neurony ve vrstvě l + 1. 206 Hluboké sítě Značení: ► Označme ► X množinu vstupních neuronů ► Y množinu výstupních neuronů ► Z množinu všech neuronů (tedy X, Y c Z) ► jednotlivé neurony budeme značit indexy apod. ► fy je vnitřní potenciál neuronu / po skončení výpočtu ► y] je stav (výstup) neuronu / po skončení výpočtu ► Wjj je váha spoje od neuronu / do neuronu / ► je množina všech neuronů, z nichž vede spoj do / (zejména 0 g ;<_) ► je množina všech neuronů, do nichž vede spoj z / Hluboké sítě Aktivní dynamika: ► vnitřní potenciál neuronu /: Zi = Tu wiiYi ► aktivační funkce 1 a = 1 + e~t pro všechny neurony stejná! ► Stav nevstupního neuronu / e Z \ X po skončení výpočtu je (y, závisí na konfiguraci w a vstupu x, proto budu občas psát y,(w,x)) ► Síť počítá funkci z R|X| do R|y|. Výpočet probíhá po vrstvách. Na začátku jsou hodnoty vstupních neuronů nastaveny na vstup sítě. V kroku t jsou vyhodnoceny neurony z Mé vrstvy. Hluboké sítě - adaptivní dynamika Tréninková posloupnost T vzorů tvaru (x^di),^,^),...,^,^) kde každé xk e {0,1 }|X| je vstupní vektor a každé dk e {0,1 }|Y| je očekávaný výstup sítě. Pro každé j e Y označme dkj očekávaný výstup neuronu ; pro vstup xk (vektor dk lze tedy psát jako (dkj)jeY)-Chybová funkce E(w) = £ Ek(w) k=1 kde jsY Používají se i jiné funkce. 209 Proč hluboké sítě ... když jedna vrstva stačí k aproximaci libovolné rozumné funkce? ► Jedna vrstva je často značně neefektivní, tj. může vyžadovat obrovský počet skrytých neuronů pro reprezentaci dané funkce Výsledky z teorie Booleovských obvodů ukazují, že nutný počet neuronů může být exponenciální vzhledem k dimenzi vstupu ... ok, proč neučit hluboké sítě pomocí obyčejné zpětné propagace? ► Rychlost učení rapidně klesá s počtem vrstev ► Hluboké sítě mají tendenci se snadno přetrénovat Vícevrstvá síť - mizející gradient Pro každé wp máme dE _ y dEk dwii ~ ^ dwii kde pro každé k = 1,..., p platí dEk dEk a pro každé j e Z \X dostaneme — =yj-dkj proyeY ^ = e^|-^)-^ proy€Zx(YuX) Pro standardní logistickou sigmoidu a váhy inicializované blízko 0 je a'r(£r) • wrj menší než 1 (pro velké váhy zase větší než 1). Hluboké sítě - adaptivní dynamika Předpokládejme k vrstvou síť. Označme ► Wj matici vah mezi vrstvami / - 1 a / ► F; funkci počítanou částí sítě s vrstvami 0,1,..., / tedy Fi je funkce počítaná jednovrstvou sítí skládající se ze vstupní a první vrstvy sítě, Fk je funkce celé sítě Všimněte si, že pro každé / lze vrstvy / - 1 a / společně s maticí W, chápat jako omezený Boltzmannův stroj B, (předpokládáme 7=1) Učení ve dvou fázích: ► předtrénování bez učitele: Postupně pro každé / = \ ,...,k trénuj OBS B, na náhodně volených vstupech z posloupnosti F/_1(x1)/...,F/_1(Xp) pomocí algoritmu pro učení OBS (zde F0(x,) = x,) (tedy B; se trénuje na tréninkových vzorech transformovaných vrstvami 0,...,/-1) ► doladění sítě s učitelem např. pomocí zpětné propagace Hluboké sítě Po první fázi dostaneme k vrstvou síť, která reprezentuje rozložení na datech. Z tohoto rozložení lze samplovat takto: ► přiveď nejvyšší OBS do termální rovnováhy (to dá hodnoty neuronů v nejvyšších dvou vrstvách) ► propaguj hodnoty do nižších vrstev (tj. proveď jeden krok aktualizace stavů mezilehlých OBS) ► stav neuronů v nejspodnější vrstvě potom bude představovat vzorek dat; pravděpodobnost s jakou se tam objeví konkrétní stav je pravděpodností onoho stavu v rozložení reprezentovaném sítí Hluboké sítě - klasifikace Předpokládejme, že každý vstup patří do jedné ze dvou tříd. Chceme vstupy klasifikovat pomocí vícevrstvé sítě. Vícevrstvou síť lze trénovat pomocí zpětné propagace. Ta je silně závislá na vhodné inicializaci, často hrozí dosažení mělkého lokálního minima apod. Dobře fungující síť si vyvine systém extraktom vlastností (tj. každý neuron reaguje na nějakou vlastnost vstupu). Jak toho dosáhnout? ► Natrénuj hlubokou síť na datech (v této fázi ignoruj příslušnost do tříd) ► Uvažuj výslednou síť jako obyčejnou vícevrstvou síť, tj. zaměň dynamiku Boltzmannova stroje za sigmoidální aktivační funkce a obvyklé vyhodnocení zdola nahoru ► přidej výstupní vrstvu s jedním neuronem ► dolaď síť pomocí zpětné propagace (malá rychlost učení pro skryté vrstvy, velká pro výstupní vrstvu): Pro vstupy z jedné třídy uvažujeme očekávaný výstup 1 pro ostatní 0. Aplikace - redukce dimenze ► Redukce dimenze dat: Tedy zobrazení R z Rn do Rm takové, že ► m < n, ► pro každý vzor x platí, že x je možné "rekonstruovat" z R(*). ► Standardní metoda PCA (exituje mnoho lineárních i nelineárních variant) • i U ! I L. t -r ■ĺ 1 • * -i ^ f 215 Original faces 1024 pixelü komprimoväno do 1 Recovered faces 00 dimenzi (tj. 100 cisel). 216 Redukce dimenze pomocí hlubokých sítí 3fl[ | 5O0 | 500 I VY 1000 1000 I 2000 2000 P ret raining Top RBM RBM RBM RBM Encoder Decoder 2O00 1000 I 500 | 30 | Code layer w Unrolling J 1 2000 1000 a 30 j T. I 500 i Wa-fi 1000 2+^2 2000 Fine-tuning Obrázky - Předtrénování ► Data: 165 600 černobílých obrázků o rozměrech 25 x 25, střední intenzita bodu 0, rozptyl 1. Obdrženo z Olivetti Faces databáze obrázků 64 x 64 standardními úpravami. ► 103 500 tréninková sada, 20 700 validační, 41 400 testovací ► Síť: Struktura sítě 2000-100-500-30, trénink pomocí postupného vrstvení RBM. Poznámky: Trénink nejnižší skryté vrsty (2000 neuronů): Hodnoty pixelů "rozmlženy" Gaussovským šumem, rychlost učení nízká: 0.001, počítáno 200 iterací Ve všech vrstvách kromě nejvyšší jsou hodnoty skrytých neuronů při tréninku binární (v nejvyšší jsou hodnoty vypočteny ze sigmoidální pravděpodobnosti přidáním šumu) Hodnoty viditelných neuronů jsou při tréninku reálné z intervalu [0,1] (zde je mírná odchylka od našeho algoritmu) Obrázky - Doladění ► Stochastické aktivace nahrazeny deterministickými Tj. hodnota skrytých neuronů není výsledkem náhodného pokusu, ale přímo výpočtu sigmoid udávajících pravděpodobnost. ► Zpětná propagace ► Chybová funkce cross-entropy kde p, je intenzita Mého pixelu ve vstupu a p, v rekonstrukci. Výsledky 1. Originál 2. Rekonstrukce hlubokou sítí (redukce na 30-dim) 3. Rekonstrukce PCA (redukce na 30-dim) Konvoluční sítě Zbytek přednášky je založen na nové online knize Neural Networks and Deep Learning, autor Michael Nielsen. http://neuralnetworksanddeeplearning.com/index.html ► Konvoluční sítě jsou v současné době nejlepší metodou pro klasifikaci obrázků z databáze ImageNet. ► Jejich počátky sahají do 90. let - síť LeNet-5 Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998 Konvoluční sítě vs MNIST (ilustrace) MNIST: ► Databáze (označkovaných) obrázků rukou psaných číslic: 60 000 tréninkových, 10 000 testovacích. ► Dimenze obrázků je 28 x 28 pixelů, jsou vycentrované do "těžiště" jednotlivých pixelů a normalizované na fixní velikost ► Více na http://yann.lecun.com/exdb/mnist/ Databáze se používá jako standardní benchmark v mnoha publikacích o rozpoznávání vzorů (nejen) pomocí neuronových sítí. Lze porovnávat přesnost klasifikace různých metod. t>00OÔ0OO0bGÔ000£D0Q>o / / I M I I I \ M / M / I / M I C 5 ř 6 5^5 f SS r? 5 ^ f S 77T77n77í7n7f? Konvoluční sítě - local receptive fields input neurons ooc ooc ooooo ooooo ooooo o ooooo hidden neuron Každý neuron je spojen s polem 5x5 neuronů v nižší vrstvě (toto pole se nazývá local receptive field) Neuron je "standardní": Počítá vážený součet vstupů, na výsledek aplikuje aktivační funkci. 223 Konvoluční sítě - stride length input neurons ooooo CO oooo first hidden laver ooooo OOOOOOOOOOO (OOOOOOOOOOO oooooooo. 00000000000 lOOCOOOOOOOOOOOOQ ÍOOOOOOOOOOOOOOOO oooooooooooooooooo< oooooooooooooooooo< oooooooooooooooooooooooooooo oooooooooooooooooooooooooooo oooo ooooooooooooa00000000000 input neurons ooooo.— oooooooo ooooo oooooooooooooooooooooooooooo oooooooooooooooooooooooooooo oooooooooooooooooooooooooooo oooooooooooooooooooooooooooo first hidden layer 000. 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 000000 00000000000000000 000 00000000000000000 □0000000000000000 00000000000000000 O O O O O u ■ OOOOOOOOOOOOí 00O' 0O0< Velikost posun vedle sebe ležících polí je stride length. Celá skupina neuronů (tj. všechny polohy) je feature map. Všechny neurony z dané feature map sdílí váhy a bias! 224 Feature maps 28 X 28 input neurons first hidden layer: li X 24 X 24 neurons 1 Každá feature map "reprezentuje" nějakou vlastnost vstupu, (v libovolné poloze ve vstupu) Typicky se uvažuje několik feature maps v jedné vrstvě. Natrénované feature maps (zde 20 feature maps, receptive fields 5x5) Pooling liiclrítm neuroníš [output from fmturc mup) max-pooling units OO_3000000000 o o------*o Vj \J \J \J \J \J \J yj \J KJ \J yj (J \} yj \J yj \J \s yj yj t^l yj \J yj yj yj yj yj \J ij yj yj y^' yj ^> oooooooooooooooooooooooo oooooooooooo oooooooooooooooooooooooo oooooooooooo j"u j"i f-^. J—H f—V J—^ f*. r~. J—, f—\ i-^ f-*i |>^T| j^-S, i""^ |T^S ."-"V ^-S j". ^-l jT^ OOOOOOOOOOOOOOOOOOOOOOOO oooooooooooo O Q ť"l O O Q O1 O O O O O O O O O O O O O O O O O O O O O O O O O O O O oooooooooooooooooooooooo oooooooooooo OOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOO OG3DOGJUJOOGOODCaGOCaCDC OOOOOOOOOOOOOOOOOOOOOOOO Neuron v pooling vrstvě počítá funkci svého pole: ► Max-pooling : maximum hodnot neuronů ► L2-pooling : odmocnina ze součtu druhých mocnin hodnot neuronů ► Average-pooling : aritmetický průměr 227 Jednoduchá konvolucni síť 28 x 2H :í x 24 x 24 28 x 28 obraz na vstupu, 3 feature maps, každá má svůj max-pooling (pole 5x5, stride = 1), 10 výstupních neuronů. Každý neuron ve výstupní vrstvě bere vstup z každého neuronu v pooling layer. Trénuje se typicky zpětnou propagací, kterou lze snadno upravit pro konvoluční síť (přepočítají se derivace). Konvolucni sit' convotution + pooling layers fully connected layers Nx binary classification Jednoduchá konvoluční síť vs MNIST dvě konvoluční-pooling vrstvy, jedna 20, druhá 40 feature maps, dvě úplně propojené vrstvy (1000-1000), výtupní vrstva (10) ► Aktivační funkce feature maps a plně propojených: ReLU ► max-pooling ► výstupní vrstva: soft-max ► Chybová fce: negative log-likelihood ► V podstatě stochastický gradientní sestup (ve skutečnosti mini-batch velikosti 10) ► rychlost učení 0.03 ► L2 regularizace s "váhou" A = 0.1 + dropout s pravd. 1 /2 ► trénink 40 epoch (tj. vše se projde 40 krát) ► Datová sada upravena posouváním o jeden pixel do libovolného směru. ► Nakonec použito hlasování pěti sítí. Konvolucni sit' - Theano »> net = Network{[ ConvPoolLayer(image_shape=(mini_batch_size, 1, 28, 28), filter_shape=(20, 1, 5, 5), poolsize=(2, 2), activationf n=Rel_U), ConvPoolLayer(image_shape=(mini_batch_sizel 20, 12, 12), filter_shape=(40, 20, 5, 5), poolsize=(2, 2), activationfn=ReLU), FullyConnectedLayer( n_in=40*4*4, n_out=1000( activation_fn=Rel_U, p_dropout=0.5), FullyConnectedLayer( n_in=1000, n_out=1000, activation fn=Rel_U, p_dropout=0.5), Softmaxl_ayer(n_in=1000, n_out=10, p_dropout=0.5)], mini_batch_size) »> net.SGD{expanded_trainingdata, 40( minibatchsize, 0.03, validation data, test data) Z 10 000 obrázků databáze MNIST, pouze těchto 33 bylo špatně klasifikováno: Složitější konvoluční síť Konvoluční sítě byly použity pro klasifikaci obrázků z databáze ImageNet (16 milionů barevných obrázků, 20 tisíc kategorií) ImageNet Large-Scale Visual Recognition Challenge (ILSVRC) Soutěž v klasifikaci nad podmnožinou obrázků z ImageNet. V roce 2012: tréninková množina 1.2 milionů obrázků z 1000 kategorií. Validační množina 50 000, testovací 150 000. Mnoho obrázků obsahuje více objektů -> za správnou odpověď se typicky považuje, když je správná kategorie mezi pěti, jimž síť přiřadí nejvyšší pravděpodobnost (top-5 kritérium). KSH síť ImageNet classification with deep convolutional neural networks, by Alex Krizhevsky, llya Sutskever, and Geoffrey E. Hinton (2012). Trénováno na dvou GPUs (NVIDIA GeForce GTX 580) Výsledky: ► úspěšnost 84.7 procenta v top-5 (druhý nejlepší alg. 73.8 procent) ► 63.3 procenta v "absolutní" klasifikaci ILSVRC 2014 Stejná sada jako v roce 2012, top-5 kritérium. Síť GoogLeNet: hluboká konvoluční síť, 22 vrstev Výsledky: ► 93.33 procent top-5 Jsou lidé stále schopni obstát proti tomuhle? Superhuman GoogLeNet?! Andrej Karpathy: ...the task of labeling images with 5 out of 1000 categories quickly turned out to be extremely challenging, even for some friends in the lab who have been working on ILSVRC and its classes for a while. First we thought we would put it up on [Amazon Mechanical Turk]. Then we thought we could recruit paid undergrads. Then I organized a labeling party of intense labeling effort only among the (expert labelers) in our lab. Then I developed a modified interface that used GoogLeNet predictions to prune the number of categories from 1000 to only about 100. It was still too hard - people kept missing categories and getting up to ranges of 13-15% error rates. In the end I realized that to get anywhere competitively close to GoogLeNet, it was most efficient if I sat down and went through the painfully long training process and the subsequent careful annotation process myself... The labeling happened at a rate of about 1 per minute, but this decreased over time... Some images are easily recognized, while some images (such as those of fine-grained breeds of dogs, birds, or monkeys) can require multiple minutes of concentrated effort. I became very good at identifying breeds of dogs... Based on the sample of images I worked on, the GoogLeNet classification error turned out to be 6.8%... My own error in the end turned out to be 5.1%, approximately 1.7% better.