OBSAH
1
}
w A| ,-./012345
Neuronov st zpracoval Martin Kuba 7. dubna 1995
Obsah 1 vod
3
2 McCullochv a Pittsv neuron 3 Perceptrony
5 5
1.1 Historie * : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1.2 Kr tk exkurze do biologie * : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1.2.1 Funkce biologick ho neuronu : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
3.1 Prahov perceptrony : : : : : : : : : : : : : : : 3.1.1 Line rn separabilita : : : : : : : : : : : 3.1.2 U en (adaptace) : : : : : : : : : : : : 3.1.3 V cevrstv s t perceptron : : : : : : : 3.2 Line rn perceptrony * : : : : : : : : : : : : : : 3.3 Neline rn perceptrony : : : : : : : : : : : : : : 3.3.1 Adaptace s u itelem : : : : : : : : : : : 3.3.2 Gradient descent learning : : : : : : : : 3.3.3 Back-Propagation : : : : : : : : : : : : 3.4 Aplikace v cevrstvch s t : : : : : : : : : : : : 3.4.1 Benz nov pumpy p klad generalizace 3.4.2 Srde n arytmie p klad klasikace : : 3.4.3 Pedpov d n budoucnosti predikce : 3.4.4 Komprese dat : : : : : : : : : : : : : : : 3.4.5 NETtalk : : : : : : : : : : : : : : : : : 3.4.6 Rozpozn v n objekt na sonaru * : : : 3.4.7 zen auta * : : : : : : : : : : : : : : : 3.5 Vhodn velikost s t : : : : : : : : : : : : : : :
4 Hopeldv model
4.1 Pojmy neline rn ch dynamickch syst m 4.2 Asociativn pam : : : : : : : : : : : : : 4.2.1 F ze u en : : : : : : : : : : : : : : 4.2.2 F ze vybavov n : : : : : : : : : : 4.2.3 Princip vybavov n : : : : : : : : : 4.2.4 Kapacita asociativn pamti * : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : : : : : : : : : : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
: : : : : :
3 3 4
7 7 8 8 9 9 10 10 11 15 15 15 16 16 16 17 17 17
17
17 18 18 19 19 21
OBSAH 4.2.5 Shrnut : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3 Optimizace pomoc s t Hopeldova typu : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
2 22 22
5 U en samoorganizac
23
6 Kohonenovy mapy
23
7 Adaptive Resonance Theory 8 Genetick algoritmy
26 27
5.1 Later ln inhibice : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.1 Funkce Kohonenovy s t : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.2 U en kohonenovy s t : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.3 Counter propagation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
23 24 24 25
1 VOD
3
1 vod Tento text vznikl na podklad pedn ky doc. Hoej e "Neuronov s t". Je doplnn poznatky, kter jsem z skal bhem vypracov v n sv diplomov pr ce. seky, kter doc. Hoej nevykl dal, tak e je nebude po adovat u zkou ky a tud jsou jen dopl!uj c , jsem ozna il hvzdi kou.
1.1 Historie *
Tuhle st jsem zaadil na za tek, proto e je to zvykem, ale doporu uji ji st a "pln nakonec, proto e a po zvl dnut teorie v s budou zaj mat drby o tom, jak vznikla. Z klady teorie polo ili p nov McCuloch a Pitts v roce 1943, kdy pedstavili prvn model neuronu, kter je po nich nazv n. N sleduj c ch patn ct let se piln pracovalo na s t ch s prahovmi neurony, kdy bylo dok z no, e jsou schopn
prov dt libovoln algoritmus. V roce 1949 pan Hebb vyslovil na z klad pozorov n biologickch neuron sv pravidlo (v anglick literatue Hebb learning rule), e synaptick spojen mezi dvma ve stejnou chv li aktivovanmi neurony se posiluje. Kolem roku 1960 vypracovala skupina pana Franka Rosenblatta nov model neuronu nazvan perceptron. Pro jednovrstevnou s perceptron dokonce dok zali stanovit u c algoritmus a dok zat jeho konvergenci. Bohu el pro teorii neuronovch s t v roce 1969 p nov Minsky a Papert dok zali, e jednovrstevn s perceptron nedok e e it XOR probl m. A proto e pan Minsky se s panem Rosenblattem njak nepohodl a pan Misky byl ve vd tou dobou velk
zv e, doporu il, aby se zastavilo nancov n vzkumu pana Rosenblatta a bylo vnov no na jin "perspektivnj " vzkumy. Na e bylo asi dvacet let ticho po p in a vzkumu neuronovch s t se vnovalo jen p r nad enc. Rosenblatt sice vdl, e v cevrstv s t jsou schopny jakchkoliv vpo t v etn XOR probl mu, ale nena el pro n u c algoritmus. (Mimochodem, v te, pro se neudluje Nobelova cena za matematiku ? Proto e panu Nobelovi utekla ena s jedn m matematikem. Cesty vvoje vdy bvaj slo it . . . ) Prudk vvoj v oblasti neuronovch s t po roce 1985 nav zal v podstat tam, kde byl ped 20 lety utnut. Algoritmus u en v cevrstvch s t , nezbytn pro dal vvoj a zn m jako back-propagation (zptn en chyby), poprv objevil pan Werbos v roce 1974 a znovu byl nez visle objeven v roce 1985 p ny Rumelhartem, Hintonem a Williamsem a tak panem Parkerem. A koliv back-propagation nen je t ide ln m obecnm algoritmem pro u en neuronovch s t , mimo jin proto e zcela jist nen t m algoritmem, kter k u en pou vaj biologick s t neuron, dok e e it mnoho probl m (nap. XOR), kter jednovrstevn perceptrony nedok ou e it. Vt ina sou asn ho vzkumu je zamena na back-propagation a jeho roz en .
1.2 Krtk exkurze do biologie *
Bhem sv ho vvoje mnohobun n ivo ichov za ali potebovat d c informa n syst m. Vyvinuli dva: pomal v esmrov chemick, kdy do krve jsou uvol!ov ny molekuly hormon, kter jsou rozn eny do cel ho tla a nkter
bu!ky pak na n reaguj svm zpsobem. Nap klad na adrenalin reaguj bu!ky c v smr tn m a t m zvy uj krevn tlak a bu!ky srdce reaguj tak, e srdce za ne rychleji b t. Druh informa n syst m je rychl pesn smrovan nervov. Prvotn re%exn oblouk vznikl u ahavc (medzy) podle tohoto schematu: po podr dn receptorov bu!ky, reaguj c nap klad na dotyk (tlak), tato bu!ka vy le dlouhm vl knem vzruch do svalov bu!ky a ta se smr t , tak e ivo ich uhne, pop pad ch!apne koist. Tato nervov soustava sest vala z osamocench nervovch bunk a nazv se rozptlen. Pozdji bylo teba reagovat slo itji, tak e vznikla ebkov nervov soustava, kterou m nap klad ala. Dal m pokrokem bylo vytvoen nervovch uzlin, kter m teba plo tnka. N sledovala nervov trubice jdouc pes cel tlo, kter se dal m vvojem diferencovala na mozek a mchu. Biologick neuron (viz obr zek 1.2) m tlo (soma) velik nkolik mikrometr, kter obsahuje organely nutn
pro ivot bu!ky. Z nj vyb haj tis ce kr tkch vb k dendrit kter tvo vstup neuronu. Z tla vyb h jedno vl kno (axon), obalen b lm tukovm ochrannm obalem (myelinem). Toto vl kno m e bt mnoho metr dlouh , u irafy vede z hlavy a do konce zadn ch nohou. Nervy jsou tvoeny svazky tchto vl ken a je v sil ch dne n chirurgie je navazovat, nap klad pi zptn m pi v n amputovan ruky. Konec axonu se vtv do mnoha vb k, kter kon synapsemi. Synapse pil haj na dendrity dal ch neuron. Mozek lovka je tvoen asi 1011 neurony, axon ka d ho neuronu pil h synapsemi na dendrity nkolika des tek tis c dal ch neuron. &ed hmota mozkov je tvoena edmi tly neuron, b l hmota mozkov je tvoena axony onch neuron. Celkov hmotnost lidsk ho mozku je 1350g u mu a 1200g u en, hustota neuron je 8:104 na 1mm3 , v ke mozkov (cortexu) je je t dov vy .
1 VOD
4
axon dendrity
synapse
soma Obr zek 1: Biologick neuron
Mozek je vzhledem ke sv v ze nejvt m spotebitelem kysl ku a koliv jeho hmota pedstavuje 2% z celkov
hmoty lovka, spotebuje a 23% z celkov ho objemu vdechovan ho kysl ku, co odpov d p konu asi 20W. Zemel neurony se neobnovuj , u lovka jich denn zahyne asi 10 000, co za 75 let ivota in asi 0.2 a 0.5% celkov ho po tu.
1.2.1 Funkce biologickho neuronu
Vl kno (axon) v klidov m stavu m rozd l elektrick ho potenci lu mezi svm vnitkem a vnj kem asi 70mV, kter je zpsoben pe erp v n m kladnch iont Na+ ven a z pornch iont K; dovnit. Po povrchu axonu je rozprostena vodiv membr na, kter je schopna se pi zv en elektrick ho potenci lu uvnit tla neuronu nad prahovou "rove! prudce depolarizovat, m se vytvo elektick impuls c se po axonu jako potenci lov vlna rychlost od nkolika a do 120 metr za sekundu. Mechanismus en vlny nen je t zcela objasnn. Pozoruhodn je, e pi nm nedoch z ke sni ov n amplitudy impulsu. Impuls b c po axonu doraz k synapsi, ze kter se v m st dotyku s dendritem n sledn ho neuronu uvoln molekuly chemick l tky (tzv. meditory nebo transmitery), kter zpsob lok ln zmnu polarizace transmisn membr ny pokrvaj c tlo a dendrity. T m vyvolaj tzv. dendriticko-somatickou potenci lovou vlnu, kter se rozvtvenm syst mem dendrit smrem k somatu neuronu. V s ti dendrit se cel skupina potenci lovch vln pi lch od rznch synaps (a od rznch neuron). Synapse samy mohou m t bu( excitan (vzru iv) nebo inhibin (tlumiv) charakter podle medi tor v nich psob c ch, kter maj depolariza n nebo hyperpolariza n " inek. Potenci lov vlny se navz jem s taj a od taj , a doraz k axonov mu hrbolku. Pokud souhrn pi lch podnt pekro ur itou prahovou rove , dojde k prudk depolarizaci tla a po axonu se za ne it potenci lov vlna (vzruch). Po vysl n impulsu se membr nov potenci l neuronu vr t na jistou zbytkovou "rove!. Po kr tk as (refraktern perioda) nen neuron citliv na podnty. Po t to dob se membr nov potenci l za ne opt pibli ovat prahov hodnot. Po jej m optovn m pekro en se cel dj opakuje. Neuron za ne generovat cel sled impuls, kter mohou m t kmito et a do 1000 impuls za sekundu, a to podle toho, o kolik peva uje "hrn psoben stimuluj c ho sign lu nad prahovou "rovn . Obvykl frekvence je nkolik jednotek a des tek impuls za sekundu. Kmito et tchto impuls je "mrn integr lu pes tu st potenci lov vlny, kter pesahuje prahovou "rove!. Aby to nebylo tak jednoduch , hodnota prahu nen v ase konstantn . U neuronovch s t ivch organism maj sign ly v nich psob c charakter sledu impuls. Informace m e bt na sign lech tohoto druhu pen ena celou adou veli in, od zmny tvaru, velikosti i polohy jednotlivch impuls a po zmnu rychlosti, se kterou jsou vys l ny. Lze soudit, e velk st informace je pen ena frekven n modulac posloupnosti impuls. Pi del m zaznamen v n prbhu impuls zjist me, e amplituda i tvar impuls se mn jen nepatrn, av ak vrazn se mn jejich frekvence. Ale informace m e bt nesena i zmnou rychlosti en vzruchu, kter se mn v rozpt 0.5 a 2 m/s.
2 MCCULLOCHV A PITTSV NEURON
5
Kdy to shrneme, tak funkce re ln ho biologick ho neuronu je velice slo it a dosud ne "pln prozkouman . P ou se o n tlust knihy a nem eme se tud divit, e form ln ch matematickch model neuronu je v ce a dn nen dokonal.
2 McCullochv a Pittsv neuron Prvn form ln model neuronu uvedli v roce 1943 McCulloch a Pitts. Byl to binrn prahov neuron (binary treshold neuron).
w1 w
2
1/0
w3 w4 w5 w6
1/0 1/0 1/0 1/0 1/0 1/0
inhibin
2
AND
excitan
1
OR
0
NOT
Obr zek 2: McCullochv a Pittsv neuron Do neuronu pich z bin rn vzruchy ( 0 nepich z vzruch, 1 pich z vzruch), ka d synapse je bu( excita n nebo inhibi n , tedy v p pad, e pich z vzruch (1), excita n spoj pisp v +1, inhibi n -1. Psoben vzruch se s t . Pokud sou et v ech vzruch pes hne prahovou hodnotu , neuron d na vstup 1, jinak 0. Form ln zaps no
ni (t + 1) = sgn( sgn(x) =
X
j 1 0
wij nj (t) ; i ) x0 x<0
kde ni (t +1) je stav i-t ho neuronu v ase t +1, wij je synaptick v ha vstupu z j -t ho do i-t ho neuronu (excita n +1, inhibi n ;1), i je prahov hodnota pro i-t neuron, sgn je funkce, kter se v nule skokem mn z nuly na jedni ku. McCulloch a Pitts dok zali, e synchronn pole takovchto neuron je v principu schopno libovoln ho vpo tu a tud m e prov dt stejn vpo ty jako digit ln po ta . Tento model neuronu m nkolik vad na kr se: Skute n neurony maj odpov( nikoliv skokovou, ale spojitou, i kdy siln neline rn (graded responce). Mnoho bunk prov d neline rn sou et vstup. Re ln neuron produkuje sled puls, ne jen jednu "rove! vstupu. I kdy reprezentujeme sled puls re lnm
slem, ignorujeme dost informace, kter mohla bt sledem pen ena. Nkte experti tvrd , e f ze puls nehraje podstatnou roli, ale jin experti s nimi nesouhlas . Skute n neurony nejsou ni m synchronizov ny.
3 Perceptrony Model perceptronu vymyslel v 60. letech pan Rosenblatt. Nejd ve je teba si ujasnit, co to znamen perceptron. Je v tom trochu nepo dek, musel jsem tuhle kapitolu nkolikr t pedl vat, ne jsem ji pivedl do vsledn ho stavu. Tak tedy: Perceptron je v cevrstv neuronov s s dopednmi vazbami (multilayered feed-forward network). Jsou v dy propojeny v echny neurony jedn vrstvy se v emi neurony n sleduj c vrstvy, neexistuj v ak dn spoje mezi vzd lenj mi vrstvami nebo mezi neurony v r mci jedn vrstvy. Do jednotliv ho neuronu p ch z impulzy jako re ln sla,
3 PERCEPTRONY
6
ka d je vyn soben jemu p slu nou synaptickou vahou, co je opt re ln slo, ud v j c "vznam" spoje. Impulzy vyn soben synaptickmi vahami jsou se teny, je ode ten prh neuronu a na vsledek je aplikov na aktivan funkce (gain function). Form ln z pis: X
Ni := g(
j
wij Nj ; i )
kde Ni je stav i-t ho neuronu, wij je synaptick v ha spoje z j -t ho do i-t ho neuronu, i je pr h neuronu i.
On O = g (h)
vstupn neurony
P
hn h = j wj Vj V = g (h) skryt vrstva P h= m k=1 wk xk vstupn neurony
V1
V2
h1 h2
Vj
neline rn transformace
hj sumace impuls
x1 x2 x3
xm
Obr zek 3: Obecn sch ma perceptronu Z form ln ch dvod se pr h i nahrad ktivn m vstupem slo nula, kter m v dy hodnotu ;1 a jemu p slu nou synaptickou vahou w0 , kter m stejnou velikost jako i . Z pis sumy se tak zjednodu a m eme ji pak zapsat jako skal rn sou in w~ :~x vektoru vah synaps w~ a vektoru vstupn ch impuls ~x. Pak m eme ps t
Ni := g(w~ :~x)
w1 w
<0,1>
2
w3 w4 w5 w6
x1 x2 x3 x4 x5 x6
-1 w0
<0,1>
w1 w
2
w3 w4 w5 w6
x1 x2 x3 x4 x5 x6
Obr zek 4: Perceptron + Perceptron s prahem form ln jako nultm vstupem+ Aktiva n funkce m e bt skokov , spojit line rn nebo spojit neline rn . Neurony pak rozli ujeme na prahov (treshold units), linern (linear units) a nelinern (non-linear units). O ka d m druhu zvl pojedn vaj n sleduj c ti podkapitoly. Pokud je s jen jednovrstevn , mluv me speci ln o jednoduchch perceptronech (simple perceptrons). U line rn ch jednotek ani nem smysl vytv et v ce vrstev, proto e vrstva line rn ch neuron prov d vlastn line rn zobrazen a skl d n m v ce line rn ch zobrazen dostaneme zase jen line rn zobrazen , tedy v ce line rn ch vrtev m e dlat jen to, co zvl dne i jedna vrstva. A nakonec, pro zmaten , budeme jednotliv neurony v perceptronech nazvat taky perceptrony.
3 PERCEPTRONY
7
1
1
0
1 0
0
Obr zek 5: Aktiva n funkce: skokov , line rn a sigmoida
3.1 Prahov perceptrony
U prahovch perceptron je aktiva n funkce skokov :
g(x) =
1 0
x0 x<0
Neuron tedy d v na vstup jen bu( 1, pokud sou et pes hl prahovou hodnotu, nebo 0, pokud nepes hl.
3.1.1 Linern separabilita
Jeden jedin prahov perceptron m e e it jen probl my, kter jsou linern separabiln.
jest b
patn separace nov separace
hospodyn
Obr zek 6: Line rn separabilita Na obr zku je n + 1-rozmrn prostor mo nch podnt pi lch do neuronu, kde n je po et rozmr podntu a jeden rozmr je pid n zaveden m prahov hodnoty jako v hy. Mohli bychom tent obr zek nakreslit tak v n rozmrn m prostoru. Pak by separuj c nadrovina nemusela proch zet po tkem souadnch os a jej posun by byl "mrn velikosti prahu. Podnty, kter jsou dle it , jsou ozna eny kole ky. Pln kole ka jsou ty podnty, na kter
neuron mus zareagovat, pr zdn naopak ty, na kter nem reagovat. V pod n pana Hoej e je tohle neuron zpsobuj c "tk kuete do bezpe . Pln kole ka jsou vjemy signalizuj c jest ba, kter chce ku tko se rat, pr zdn kole ka jsou vjemy signalizuj c hospodyni, kter kue krm a proto se ped n nem ut kat. Neuron se svmi synaptickmi vahami (a prahovou hodnotou) ur uje nadrovinu (vyzna enou peru ovanou arou), kter oddluje (separuje) poloprostory podnt, na kter se reaguje a na kter ne. Pokud nadrovina oddluje bezchybn podnty jest ba od podnt hospodyn, kue reaguje spr vn. Sta vz t vektor ~x vjem a vyn sobit ho s vektorem vah w~ . Pokud w~ :~x > 0, neuron zareaguje. (Pro ? Proto e line rn algebra a geometrie skal rn m sou inem z sk v m
3 PERCEPTRONY
8
vzd lenost bodu ~x od roviny w~ . Pokud je vsledek kladn, le bod v jednom poloprostoru, pokud nulov, le p mo v nadrovin, a pokud je z porn, le v druh m poloprostoru.) Co se v ak stane, kdy takov dl c nadrovina neexistuje ? Pak nelze spr vn podnty odli it a kue bude se r no. Jinak e eno, takov "loha je nee iteln jedn m perceptronem. P kladem line rn separabiln "lohy je funkce AND, p kladem funkce, kter nen line rn separabiln , je XOR funkce, pr v ta, kterou jako dkaz neschopnosti perceptron pedlo ili Minsky a Papert. Funkce XOR je zvl tn m p padem paritn funkce, kter d v jedna, pokud po et jedni kovch bit je lich, jinak nulu. Je to jeden z nejt ch probl m pro neuronov s t, proto e vstup mus mnit svou hodnotu po ka d zmn vstupu.
1
1
0
0 0
AND
1
0
XOR
1
Obr zek 7: AND je line rn separabiln , XOR nen .
3.1.2 U en (adaptace)
U en jednoho perceptronu spo v v nalezen takovch vah, e dl c nadrovina spr vn rozdl podnty. Postupn pro v echny podnty, na kter m neuron reagovat, se pod v me, jestli neuron d v spr vn vstup. Pokud na njak podnt ~x neuron nereaguje a ml by, pak vektor vah w~ old zmn me pi ten m vektoru podntu ~x, m dostaneme nov vektor vah w~ new ,
w~ new = w~ old + ~x
se kterm u neuron na onen podnt reaguje. Pro te( reaguje ? Proto e
w~ new :~x = (w~ old + ~x):~x = w~ old :~x + ~x:~x 0 Pokud to takhle udl me pro v echny podnty, na kter se m reagovat, nakonec dostaneme takov vektor vah, e nadrovina spr vn oddl v echny tyto podnty do jednoho poloprostoru.
3.1.3 V cevrstv s t perceptron
U v me, e samotn perceptron nem e e it probl my, kter nejsou line rn separabiln . Nem e je tedy e it ani jednovrstevn s perceptron. Ale na tst je m e vye it v cevrstv s . Intuitivn dkaz je nazna en na obr zku 8. Jeden perceptron mi rozdl prostor na dva poloprostory nadrovinou. Zareaguje pak jen na podnty nach zej c se jen v jednom poloprostoru. Jsou ozna eny plnmi kole ky. Dvouvrstevn s m e vymezit lib. konvexn "tvar. Ka d neuron prvn vrstvy vymez jeden poloprostor, neuron druh vrstvy pak vyhodnocuje prnik tchto poloprostor. Z kladn prostor podnt m bt diskr tn , aby k vymezen libovoln konvexn mno iny sta il kone n po et poloprostor. Na tst re ln svt nepotebuje matematicky pesn vymezen , sta aproximace kone nm po tem poloprostor. T vrstevn s rozezn lib. po et konvexn ch "tvar. Neurony prvn vrstvy opt vymezuj poloprostory, neurony druh vrstvy rozli uj prniky tchto poloprostor, m vymezuj konvexn mno iny, a neuron tet vrstvy prov d sjednocen tchto konvexn ch mno in.
3 PERCEPTRONY
9
-3
1 1 1
-1 -3
-3
-4
Obr zek 8: Schopnosti jedno-, dvou- a t vstevn s t.
3.2 Linern perceptrony *
Line rn perceptrony pou vaj line rn aktiva n funkci
g(x) = x Line rn s nen nutn u it, p slu n synaptick v hy se daj p mo vypo tat. Nicm n vrstva line rn ch perceptron prov d jen line rn zobrazen , co nen nic nov ho a nezn m ho, proto tento typ s t nem velk praktick pou it . Pro vpo et vah je nutn , aby vzory byly navz jem linern nezvisl , co nastane jen tehdy, pokud je vzor m ! ne neuron v s ti.
3.3 Nelinern perceptrony
Nyn se dost v me k nejpou vanj mu typu s t. Neline rn perceptrony pou vaj jako aktiva n funkci tzv. saturan funkci, kter sou et impulz transformuje do intervalu < 0 1 > a to tak, e v bl zkosti nuly funkce stoup velmi prudce, zat mco u vysokch hodnot stoup jen nepatrn, tak e p padn rozd l se tak moc neprojev . Tato vlastnost byla pevzata od biologickch neuron. Nap klad pro hladov ho studenta znamen jeden rohl k mnohem v c, ne pro pejeden ho. Jako satura n funkce se nej astji pou v sigmoida:
g(x) = 1 + 1e;x D se dok zat, e tvstevn s tchto neuron m e aproximovat libovoln re ln zobrazen mezi prostorem vstup a prostorem vstup. Jinak e eno, ke ka d funkci f : Rn ! Rm existuje 3-vstevn s , kter ji realizuje. Dkaz stoj na Kolmorogov teor mu, kter k :
3 PERCEPTRONY
10
Kolmogorovv teorm * Existuj spojit rostouc funkce ij na h0 1i tak, e ka d spojit funkce f na < 0 1 >n m e bt zaps na ve tvaru
f (x1 : : : xn ) =
2n+1
X i=1
kde i jsou vhodn zvolen spojit funkce jedn promnn .
i (
n X j =1
ij (xj ))
3.3.1 Adaptace s u itelem
V me tedy, e v cevrstv s t mohou prov st libovoln zobrazen (vpo et). Ke ka d mu probl mu m me zaji tnu existenci e c s t, ale jak ji z sk me ? P m vpo et synaptickch vah neuron je nevhodn a ve vt in p pad neuskute niteln. Nastupuje u en s t za pou it sady pklad . Mjme v cevrstvou s s m vstupn mi a n vstupn mi neurony. Tr novac mnoinou nazveme mno inu dvojic vektor
T = f ~x1 ~y1 ] : : : ~xP ~yP ]g kde ~x = (x1 x2 : : : xm ) je v dy vektor vstupn ch hodnot a ~y = (y1 y2 : : : yn) je vektor po adovanch vstupn ch hodnot. Tr novac mno ina obsahuje P p klad, kter se s mus nau it. Takov muto u en se k uen s uitelem, proto e mus existovat njak vy autorita, kter s ti pedkl d p klady dvojic vstup a vstup a pokud s odpov d patn, informuje ji o chyb a modikuje ji. Existuje i u en bez u itele, kdy s nedost v dvojice vstup-vstup, ale jen mno inu vstup a sama si je rozdluje do skupin podle podobnosti. Celkov chyba s t se po t jako
E = 21
P X n X
(Oip ; yip )2
p=1 i=1 p kde Oi je skute n vstup i-t ho neuronu ve vstupn vrstv pi pedlo en vstupu p-t ho p kladu na neurony vstupn vrstvy. Pro pehlednost se m ete pod vat zp tky na obr zek 3. Pak (Oip ; yip )2 je rozd l o ek van ho a po adovan ho
vstupu, suma pro i s t pes v ech n vstupn ch neuron a suma pro p s t pes v ech P p klad. (*) Funkce E se v anglick literatue nazv "cost function" a je ur ena pro men chyby s t s asymetrickmi spoji. Je to nco jin ho ne tzv. "energy function" zaveden v Hopeldov modelu, kter je ur ena pro men stavu s t se symetrickmi spoji.
3.3.2 Gradient descent learning
U en s t vych z z n sleduj c my lenky. Pokud s ti pedlo me pevn vektor ~x na vstup, chyba s t E je funkc v ech synaptickch vah neuron. A proto e aktiva n funkce neuron (sigmoidy) jsou derivovateln , je i E derivovateln podle jednotlivch vah. Zn zorn me si to na grafu:
E
E
@E @wi
wi Obr zek 9: Error landscape
w~
3 PERCEPTRONY
11
Vodorovn osa pedstavuje mnoharozmrn prostor vah neuron s t, svisl osa je hodnota chyby E pro dan
v hy. Vstupn vektor ~x je pevn, te( u me s jeden konkr tn p klad. Graf E je mnoharozmrn , a co je dle it , derivovateln , plocha, tzv. Error landscape, krajina chyb. Pro njak konkr tn nastaven vah jsme nkde v t to krajin. Na m "kolem je sej t co nejn , minimalizovat chybu. Ide ln by bylo sej t a na ""rove! moe", na nulovou hodnotu chyby, ale to se poda jen m lokdy. Budeme se chovat jako turista v hor ch, nebo jako voda, kter chce st ct do n in. Vyd me se po sp dnici dol. Sp dnici najdeme zderivov n m krajiny (chyby) v m st, kde stoj me. Udl me krok smrem po sp dnici, dostaneme se tak na nov m sto a postup opakujeme. Pokud bude krok p li dlouh, nap klad del ne svah kopce, na kter m stoj me, m eme se dotat a na vedlej kopec a dokonce v , ne jsme byli. V takov m p pad se vr t me a udl me krat krok. Tak se postupn dostaneme na nejni m sto, ze kter ho v echny cesty povedou nahoru. Pokud to bude glob ln minimum chyby, jsme doma, pokud to je lok ln minimum , m stn bezodtokov "dol , m me smlu a mus me se dostat nkam pry . Zvol me smr a sko me mnoho mil a budeme doufat, e z nov ho m sta se k moi dostaneme. Zkr tka a dobe, jsme v pozici turisty v mlze, ale s v komrem. Form ln zaps n vypad pedpis pro zmnu vah takto:
@E + w ; wold ] i i @wi tedy zmna konkr tn v hy je d na parci ln derivac chyby E podle t to v hy, vyn sobenou d lkou kroku . Druh len s parametrem je ve vrazu jako "setrva nost" pohybu, aby se eliminovalo mal houp n ter nu. Kdy wi = ;
jdu z dlouh ho prudk ho svahu, taky si nev m m malch kam nk, jejich strana obr cen ke mn m opa n sklon ne svah.
3.3.3 Back-Propagation
Te( teoreticky v me, jak s u it pomoc metody "svahov ho sestupu" nebo "sestupu svahem", jak se d "gradient descent" pelo it. Prakticky je ale velice dle it , jakm zpsobem budeme synaptick v hy mnit. Byl to vyn lez metody zptn ho en chyby, kter zpsobil obrovsk n rst z jmu o neuronov s t po roce 1985.
O1
vstupn neurony
W11 skryt vrstva
w11 vstupn neurony
x1
Oi
O2 W23
V1
V2
Wij Vj
V3 w35
x2
x3
x4
x5
wjk xk
Obr zek 10: Dvouvrstevn s ukazuj c ozna en neuron a vah Algoritmus back-propagation si pedvedeme na dvouvrstevn s ti, nakreslen na obr zku 10. M me ji nau it tr novac mno inu P p klad T = f ~x1 ~y1 ] : : : ~xP ~yP ]g, kde ~x = (x1 x2 : : : xm ) a ~y = (y1 y2 : : : yn). Vstupn neurony jsou ozna eny Oi , skryt neurony Vj a vstupn neurony ozna me rovnou hodnotami vstup xk . Spoje wjk vedou ze vstupn vrstvy do skryt vrstvy, spoje Wij ze skryt do vstupn . Index i v dy ozna uje vstupn neuron, j skryt a k vstupn . P smeno p je pou v no pro indexov n p klad. Pi zad n vektoru ~xp na vstup s t skryt neuron j obdr vstup
hpj =
X k
wjk xpk
3 PERCEPTRONY
12
a po transformaci aktiva n funkc (sigmoidou) d v vstup
Vjp = g(hpj ) = g( . Pak ov em vstupn neuron i obdr vstup
hpi =
X j
X k
X
Wij Vjp =
Wij g(
j
a po transformaci aktiva n funkc (sigmoidou) d v vstup
Oip = g(hpi ) = g(
X j
wjk xpk )
Wij Vjp ) = g(
X k
X j
wjk xpk )
Wij g(
X k
wjk xpk ))
Prahy neuron zad me jako zvl tn vstupn neurony nastaven na ;1, jak jsme pedvedli ji d ve. Celkov chyba s t men jako X se po dosazen mn na
E w] = 21
E w] = 21
pi
X
X
pi
j
yip ; g (
yip ; Oip ]2
Wij g(
X k
wjk xpk ))]2
To je zejm spojit diferencovateln funkce v ech vah, tak e m eme pou t gradient descent algoritmus pro nalezen spr vnch vah. A dosud byly v echny rovnice jednoduch a prhledn , proto e jsme jen dosazovali za vrazy. Ale te( se souste(te, te( to bude hor .
Zmna vah pro vstupn neurony Pro spoje mezi skrytmi a vstupn mi neurony podle gradient descent vych z zmna konkr tn v hy Wij na
Wij = ;
@E @Wij
. Z le na d lce kroku , co je n mi zvolen konstanta, a derivaci chyby E podle t to v hy. Po parci ln m zderivov n chyby E podle v hy Wij n m vyjde1
@E @Wij Zavedeme ozna en 1
=;
X p
yip ; Oip ]g 0 (hpi )Vjp
ip = g0 (hpi ) yip ; Oip ]
Pokud mi nevte, tak
E w] = 21
XX
X
yip ; g(
p
i
Wij Vjp )]2
j
suma pro i je a na jeden len tvoena konstantami P p p @E = 1 X 0 + : : : + 0 + @ yr ; g( j Wrj Vj )]2 @Wrs 2 p @Wr s a po zderivovn tohoto lenu dostanu =
z eho dostanu
X
X
p
j
yrp ; g(
X
Wrj Vjp )](0 ; g ( 0
=;
X p
Wrj Vjp )(0 + : : : + Vsp + : : : + 0))
j
@E @Wrs
+ 0 + ::: + 0
yrp ; Orp ]g0 (hpr )Vsp
3 PERCEPTRONY
13
kde ip je chyba i-t ho (tedy vstupn ho) neuronu, z vis c na sklonu sigmoidy v m st hodnoty vstupu do neuronu hpi a na rozd lu skute n a po adovan hodnoty vstupu yip ; Oip ]. Odtud slo en m dost v me @E = X p V p : Wij = ; (1) i j @W ij
p
Zmna vah pro vnitn neurony Spoje wjk mezi vstupn mi a vnitn mi neurony jsou ve vzorci pro E mnohem hloubji.
wjk = ; =
Zavedeme ozna en
X
@E @wjk
= ;
X @E @Vjp p p @Vj @wjk
i yip ; Oip ]g0 (hpi )Wij g0 (hpj )xpk p X p 0 p p = i i Wij g (hj )xk p
jp = g0 (hpj )
X
Wij ip
i p . kde j je chyba j -t ho (tedy vnitn ho) neuronu, a z vis na sklonu sigmoidy v m st hodnoty vstupu do neuronu hpj
a na chyb ch neuron, do kterch pos l svj vstup n sobench p slu nmi vahami spoj. Dost v me tedy X wjk =
p
jp xpk :
(2)
Princip back-propagation V imnme si, e pedpisy 1 a 2 jsou stejn a na denici . V eobecn, pi jak mkoliv po tu vrstev, pedpis pro zmnu vah bude m t tvar
wpq =
X p
output Vinput
kde q je neuron, ve kter m spoj za n a v p kon , V je vstup neuronu q. Vznam z vis na tom, o kterou vrstvu se jedn . Chyba vstupn ch neuron se spo t z rozd lu mezi skute nm a po adovanm vstupem a pak se zptn (back) ped v (propagation) vnitn m neuronm, pi em se n sob hodnotou v hy spoje. V hy spoj se tak pou vaj dvakr t , pi en sign l jedn m smrem a pi en chyby druhm smrem. Obr zek 11 ukazuje tuto my lenku. A koliv jsme napsali pravidla pro zmnu vah jako sumy pes v echny p klady, v praxi se nejd v pedlo jeden p klad, uprav se v echny v hy a pak se teprve pedlo dal p klad. Dokonce je vhodn nepedkl dat p klady ve st le stejn m poad , ale vyb rat je n hodn. N hodn vbr poad in cestu v hovm prostorem n hodnou a umo !uje ir prozkoum n chybov krajiny. To, e potebn hodnoty derivac chybov funkce mohou bt vypo t ny pomoc zptn ho en chyby je velmi dobr . M to dva dle it n sledky: Pravidlo pro zmnu synaptickch vah je lokln. Pro vpo et zmny konkr tn v hy potebujeme jen hodnotu en chyby na jednom jej m konci a hodnotu pen en ho sign lu V na druh m jej m konci. T m p dem se d vpo et back-propagation paralelizovat. Vpo etn slo itost je men , ne bychom mohli o ek vat. Pokud m me n spoj, vpo et chyby E stoj n operac . Vpo et n derivac p mo by pak potebovalo n2 operac , zat mco pomoc back-propagation n m posta n operac pro zmnu hodnoty v ech vah. Bohu el, back-propagation nen t m algoritmem, kter pou v pro u en s t p roda. Jeho vpo et je sice lok ln , ale lok lnost je pro biologickou implementaci podm nkou nutnou, nikoliv v ak posta uj c . Probl m spo v v obousmrnosti spoj, kdy se po nich zptn chyba. Re ln axony nejsou v dn m p pad obousmrn .
3 PERCEPTRONY
14
1
2
3
x2
x1
Obr zek 11: Back-propagation ve v cevrstv s ti. Pln ipky ukazuj smr en sign l, zat mco rkovan smr en chyby. Jako aktiva n funkce g(h) se pou vaj funkce
g1 (h) = 1 + 1e;h
a
g2 (h) = tanh( h)
proto e jejich derivace je snadn vyj dit pomoc jich samch jako g10 (h) = g1 (1 ; g1 ) a g20 (h) = (1 ; g22 ). Proto je
asto v literatue rovnice 1 vidt zaps na jako pro neurony s vstupem 0/1 a pro = 1.
ip = (yip ; Oip )Oip (1 ; Oip )
Algoritmus back-propagation Proto e je back-propagation nejdle itj m a nejpou vanj m algoritmem pro u en s t , zap eme ho zde po jednotlivch kroc ch. Mjme s s L vrstvami l = 1 : : : L a zna me Vil vstup i-t ho neuronu v l-t vrstv. Vi0 znamen xi , tedy i-t vstup. Ozna en wijl znamen spoj z Vjl;1 do Vil . Pak algoritmus zn : 1. inicializuj v hy na mal n hodn sla 2. Zadej p klad ~xp na vstup s t (vrstva l = 0), tak e
Vk0 = xpk
3. Nech it sign ly s t 4. Vypo tej delty pro vstupn vrstvu
X
Vil = g(hli ) = g(
j
wijl Vjl;1 )
p M iM = g0 (hM i ) yi ; Vi ]
5. Vypo tej delty pro pedch zej c vrstvy zptnm en m chyby
il;1 = g0(hli;1 )
X j
wjil jl
3 PERCEPTRONY
15
6. Zm! v hy podle pravidla
l = l V l;1 wij i j
wijnew = wijold + wij 7. B na bod 2 a opakuj pro dal p klad.
Vylepen back-propagation O jednom vylep en jsme se ji zm nili. Spo v v zaveden momentu setrva nosti ke zmn m vah, kdy zmna v hy z le i na velikosti pedchoz zmny. wi = ;
@E old @wi + wi
I druh vylep en spo v v ur ov n d lky kroku. Pokud jdeme po planin ch, m eme krok prodlu ovat, pokud narz me na lenitou krajinu, krok zkr t me. Dal vylep en m e bt takov , e na za tku u en s t budeme pou vat povlovnj aktiva n funkci s men m , ke konci u en pak budeme "pitvrzovat", zv me ".
3.4 Aplikace vcevrstv ch st
V t to kapitole s t rozum me s neline rn ch perceptron u enou pomoc back-propagation. Hlavn dvod, pro neuronov s t pou v me, je jejich schopnost generalizace. Spo v v tom, e s pedstavuje spojit zobrazen z prostoru vstup do prostoru vstup. Kdy nau me s spr vn odpov dat na ur itou mno inu p klad, ur ili jsme vlastn hodnotu tohoto zobrazen v nkolika diskr tn ch bodech prostoru vstup. Spojit zobrazen reprezentovan s t je vlastn hyperplocha prolo en tmito body. Proto kdy zad me s ti vstupn hodnotu, kter nebyla mezi p klady, kter um , s d njak vstup. Zaj mav je to, e tento vstup je v lidsk m smyslu rozumn. Krom tr novac mno iny se tak zav d pojem testovac mno iny, co jsou dvojice vstup a vstup, kter tak maj smysl, ale s na n nen nau ena. Pokud mezi p klady v tr novac mno in byla njak z vislost, s ji zjist . Na testovac mno in se pak zjist , nakolik je s t zji tn z vislost tou z vislost , kterou jsme chtli zjistit. Aplikace tohoto fantastick ho rysu neuronovch s t je nab ledni. Pokud m me mno inu dat, o kterch v me, e je mezi nimi njak z vislost, ale neum me ji objevit, zad me tato data s ti a ona n m tu z vislost najde. Uvedme si nkolik p klad pou it n. s t s uveden m funkce, kterou s prov d .
3.4.1 Benz nov pumpy p klad generalizace
Jedna z prvn ch aplikac neuronovch s t byla tato. V americk rm provozuj c s benz novch pump byl zamstn n
lovk, kter u dlouh l ta ur oval, jak moc se m kter pumpa pedz sobit, nap klad e ped sv tky se maj pedz sobit pumpy na vpadovk ch z msta a podobn. Tuto pr ci dlal velice dobe a nikdo jin to neuml tak dobe jako on. Tento lovk ml ale odej t do dchodu. Nebyl v ak schopen popsat, podle jakch pravidel rozdlov n benz nu ur uje, proto e to dlal na z klad dlouholet zku enosti intuitivn. Proto nebylo mo n ani setavit klasick expertn syst m, proto e ten potebuje pesn denovan pravidla. Vyrobili tedy neuronovou s , kter mla jako vstup stejn "daje, jako ml onen lovk, tzn. datum, po as a j nev m co je t. Jako vstup se s u ila d vat stejn rozdlen distribuce benzinu jako lovk. Zkr tka a dobe, asi pl roku s pozorovala, jak to ten lovk dl , a nau ila se to taky. On mohl j t klidn do dchodu a s m sto nj pracuje bez n roku na mzdu dodnes.
3.4.2 Srde n arytmie p klad klasikace
Skupina l ka vzala mnoho z znam EKG a u ka d ho z nich ur ila, jestli lovk, kter mu z znam patil, trp srde n arytmi nebo ne. Pak tyto z znamy d vali neuronov s ti na vstup a u ili ji spr vn odpov dat, jestli dan z znam vykazuje arytmii. A byla nau en na t to tr novac mno in z znam, za ali j pedkl dat z znamy, kter pedt m nevidla. A uk zalo se, e s pozn v arytmii velice dobe, dokonce l pe ne 90% norm ln ch l ka. Je to t m, e s rozhoduje stejn dobe, jako by rozhodovala skupina l ka, kte vyb rali tr novac mno inu, co jednak byli pi kov odborn ci a jednak jich bylo v c, tak e rozhodovali l pe ne jednotlivec. S tak vlastn prov dla klasikaci z znam na dv skupiny, jednu vykazuj c arytmii a druhou nevykazuj c . Klasikovat pomoc s t m eme i na v ce skupin, ne dv.
3 PERCEPTRONY
16
3.4.3 Pedpov dn budoucnosti predikce
Predikce dos hneme jednoduchm trikem. Mjme z znam prbhu njak veli iny (teba teploty), jej hodnota njak z vis na pedchoz ch hodnot ch. Pak jako tr novac mno inu pou v me jak si plovouc okno, pohybuj c se po z znamu, a s u me odpov dat na pedn st tohoto okna jeho zadn st , viz obr zek 12
posuvn okno
vstup
vstup Obr zek 12: Princip u en pi predikci
Nap klad vezmeme z znamy o teplot vzduchu za posledn ch dvst let, a s ti v dy zad me na vstup teploty v sedmi po sob n sleduj c ch dnech a u me ji odpov dat na vstupu teplotou n sleduj c ho osm ho dne. A je nau en , zad me j teploty za posledn ch sedm dn a dozv me se, jak bude z tra. (Nev m, jestli zrovna tenhle p klad doopravdy funguje, proto e teplota nez vis jen na pedchoz ch teplot ch, ale jako ilustrace se hodil).
3.4.4 Komprese dat
Komprese se prov d tak, e s u me na identitu, tedy jako p klady m stejn vstup a vstup. Vnitn vrstva neuron mus m t m n neuron ne vstupn a vstupn , proto e pak je s nucena v cerozmrn vstup transformovat do m nrozmrn ho prostoru reprentovan ho vnitn vrstvou. S se pak "rozstihne" ve stedn vrstv a jej pedn
st se pou v pro kompresi a jej zadn st pro dekompresi.
Obr zek 13: 4-2-4 enkoder a rozstihnut s
3.4.5 NETtalk
Projekt NETtalku ml za "kol vye it vyslovov n psan ho anglick ho textu. Vstupem bylo plovouc okno sedmi znak pohybuj c se po textu. Vstupem byl fon m ped van gener toru e i. S mla 7 9 vstupn ch neuron k-duj c ch sedm znak z 29 mo nch, 80 skrytch neuron a 26 vstupn ch neuron k-duj c ch fon my. S byla tr nov na na 1024 slovech, po deseti tr novac ch epoch ch produkovala srozumitelnou e a po 50ti epoch ch mla na tr novac mno in 95%n spr vnost. Nejd ve se nau ila vrazn rysy jako mezery mezi slovy a potom postupn vylep ovala rozli ov n , tak e to znlo jako d t u c se mluvit. Zjistilo se, e nkter vnitn neurony reprezentuj vznamn vci jako teba rozd l mezi samohl skami a souhl skami. Po nau en byla s zkou ena na dal ch slovech, na kterch vyk zala 78%n spr vnost a produkovala celkem srozumitelnou e .
4 HOPFIELDV MODEL
17
Je zaj mav porovnat NETtalk s komer n m DEC-talkem, kter je zalo en na ru n zadanch pravidlech. Zat mco NETtalk se nau il z p klad, DEC-talk je vsledek desetilet pr ce mnoha lingvist. DEC-talk mluv rozhodn l pe, ale "sil do nj vlo en je tak mnohem vt . Toto byl p klad toho, jak jsou pou iteln neuronov s t. Pou it neuronovch s t je druhm nejlep m e en m probl mu. Prvn m nejlep m e en m je pou t zn m optim ln algoritmus.
3.4.6 Rozpoznvn objekt na sonaru *
Gorman a Sejnovski v roce 1988 u ili dvouvrstevnou s rozpozn vat odezvy sonaru na dva druhy pedmt le c ch na dn Chesapeakesk ho z livu, na kameny a kovov v lce. Ped vstupem do s t byla na datech provedena Fourierova transformace, kterou se z skalo frekven n rozlo en sign l. Tato transformace mohla bt v principu tak provedena neuronovou s t , ale takhle se u etilo nkolik vrstev a rychlost. S mla 60 vstupn ch neuron a dva vstupn , jeden pro kameny, druh pro v lce. Po et neuron skryt vrstvy se mnil od dn ho do 24. Bez vnitn ch neuron s velice rychle dos hla 80% "sp nosti, ale d l se nedok zala zlep it. Se 12ti vnitn mi neurony v dy s dos hla skoro 100%n "sp nosti, pi pid v n dal ch u se jej vkon nezlep oval. Po natr nov n byla s testov na na novch datech, na kterch dosahovala 85%n "sp nosti. Podailo se ji zlep it a na 90% pe livj m vbrem tr novac mno iny.
3.4.7 zen auta *
Pomerlau v roce 1989 vytvoil s pro zen auta. Vstup byly 3032 pixelov obr zky z videokamery na ste e auta a 832 obr zky detektoru vzd lenost . Tyto vstupy byly vedeny do vnitn vrstvy s 29 neurony a odtud do vstupn vrstvy s 45 neurony uspo danmi do ady. Prostedn vstupn neuron znamenal j zdu p mo, zat mco m ra zat en byla reprezentov na vzd lenost vstupn ho neuronu od prostedn ho. S byla nau ena na 1200 obr zc ch. Po nau en byla s schopna dit rychlost 5 km/h na cest vedouc lesem v okol Carnegie-Mellonovy univerzity. Rychlost byla omezena malm po ta em Sun-3, kter byl pou it k propagaci sign l pes s , a mohla by bt zv ena specializovanm hardwarem. Ka dop dn to byla rychlost dvakr t vy , ne jak se podailo dos hnout jinmi (nes ovmi) algoritmy.
3.5 Vhodn velikost st
Pro e en konkr tn ho probl mu je vhodn jen s ur it velikosti. Pokud bychom pou ili s p li malou, nebyla schopna spr vn generalizace, nedok zala by prolo it plochu v emi body p klad. Naopak, pochud bychom pou ili s p li velkou, do lo by tak ke patn generalizaci. Prvn dvod je ten, e data p klad z re ln ho svta v dy obsahuj jist um, neodpov daj pesn t z vislosti, kterou chceme zjistit, nap klad v dsledku nepesnosti men hodnot. P li velk s by se nau ila z p klad i tomuto umu. Druh dvod je ten, e opravdu p li velk s by se nau ila odpov dat naprosto spr vn jen na pedlo en p klady, ale ve zbytku prostoru vstup by mla generaliza n hyperplocha nesmysln tvar. Odpov d to situaci, kdy se student nau nazpam zadan p klady, ale na ot zku, kter nebyla v p kladech, nedok e odpovdt. V ilustra n m obr zku jsou p pady s t p li mal , spr vn velk , trochu nadmrn a p li velk .
4 Hopeldv model Hopeldv model je krok smrem od biologick reality. Pou v toti symetrick spoje mezi neurony, kter v p rod neexistuj . Pat sp do teorie neline rn ch dynamickch syst m. Proto si nejd v zavedeme nkolik pojm z t to teorie.
4.1 Pojmy nelinernch dynamick ch systm
Neline rn dynamick syst m sest v z mno iny stav P a z funkce f : P ! P , kter ur uje pechody mezi stavy. Stacionrn bod je takov stav, ze kter ho se nikam jinam nedostaneme (x 2 P : f (x) = x). Atraktor je takov stacion rn bod, e existuje njak jeho okol (v njak metrice na mno in stav), z jeho v ech stav v dy skon me v atraktoru. Atraktor je od slova atraktivn , je to stav, kter ho se sna syst m dos hnout a v nm zstat. Okol atraktoru se anglicky nazv basin of attraction.
4 HOPFIELDV MODEL
18
vstup
1
2 3
4 vstup s t Obr zek 14: P klady chybnch generalizac . K ky jsou p klady, ra 1 je spr vn generalizace, ra 2 odpov d mal s ti, ra 3 trochu vt a ra 4 p li velk . Cyklus je uzaven cesta mezi stavy. Globln atraktor je cyklus, kter m njak okol , z nho v dycky skon me v cyklu.
4.2 Asociativn pam
Hopeldv model neuronov s t byl vytvoen jako asociativn pam. Je tvoena neurony, kter jsou spojeny symetrickmi spoji ka d s ka dm2 . M e bt reprezentov n symetrickou matic vah s nulovou hlavn diagon lou. Neurony maj dva stavy +1 (aktivovan) a -1 (neaktivovan) a prov dj prahovan v en sou et
X
Si := sgn( sgn(x) =
.
j
wij Sj ; i )
1 ;1
x0 x<0
Hodnota prahu bude nulov . U en spo v v tom, e vezmeme njak vzor (pattern), nap klad ernob l obr zek, provedeme piazen jeho pixel na neurony a nastav me je ern -1, b l +1. U c pravidlo je Hebbovo. Pan Hebb vyslovil na z klad pozorov n biologickch neuron pravidlo, e synaptick spojen mezi dvma neurony, kter jsou aktivov ny ve stejnou chv li, se posiluje.
4.2.1 Fze u en
Na za tku budou v echny v hy synaptickch spojen inicializov ny na nulu. Piad me neuronm hodnoty f+1 ;1g. Zmn me v echny v hy tak, e pokud spojuje neurony se stejnou hodnotou, zv me hodnotu v hy o jedni ku, pokud spojuj neurony s rozd lnmi hodnotami, hodnotu v hy o jedni ku sn me. Form ln zaps no wij = xi :xj
Tohle pravidlo u je mimo pvodn Hebbovu hypot zu, proto e v ha se mn i kdy oba neurony jsou neaktivn (-1,-1), co nem biologick opodstatnn . Pak vezmeme dal vzor, piad me hodnoty neuronm, zmn me v hy. A tak d le se v emi vzory. Po nau en hodnota v hy vyjaduje rozd l po tu vzor, ve kterch se j spojen neurony shodly svmi hodnotami, a po tu vzor, 2
U Hopflda se spoj kad s kadm grup bez rozli en pohlav mnemotechnick pom cka
4 HOPFIELDV MODEL
19
vektorov pole
stacion rn bod
atraktor
cyklus, glob ln atraktor Obr zek 15: Pojmy dynamickch neline rn ch syst m
ve kterch se neshodly. Pokud jsme nap klad mli 11 vzor a neurony slo 3 a 5 se u esti vzor shodli a u pti vzor neshodli, pak v ha w35 = w53 bude m t hodnotu +1. Kdyby se desetkr t neshodli a jednou shodli, bude v ha m t hodnotu -9.
4.2.2 Fze vybavovn
Vezmeme nkter vzor, kter jsme s nau ili a po kod me ho, nap klad invertujeme tetinu bit nebo jich n hodn
mno stv nastav me na n hodn hodnoty. Tento po kozen vzor piad me na neurony. Pak donekone na opakujeme n sleduj c postup: N hodn vybereme jeden neuron. Hodnoty ostatn ch neuron vyn sob me synaptickmi vahami, se teme a pokud vsledek bude nez porn, piad me neuronu hodnotu +1, jinak -1. Jeho starou hodnotu zapomeneme a od te( pou v me tuto novou hodnotu. Pak vezmeme dal neuron a tak d le.
4.2.3 Princip vybavovn
Tento postup vych z z n sleduj c "vahy. Mnn neuron se zept v ech ostatn ch, jakou hodnotu by ml m t. Neuron, se kterm je spojen spojem s vahou 15 mu k : "Pod vej, o patn ct v ckr t jsme mli stejnou hodnotu ne ji mli rozd lnou, tak je pravdpodobn , e ji budeme m t zase stejnou. Tak se laskav nastav na stejnou hodnotu, jako m m j . A tuhle moji radu ber v nji ne rady neuron, kte jsou s tebou spojeni slap mi vahami." Jin neuron, se kterm je spojen vahou -4 pov d : "Hele, my jsme se shodovali a neshodovali tak pl na pl, ale pece jenom po et neshod byl o tyi vy , tak e asi budeme m t rozd ln hodnoty. Ale tohohle doporu en si moc nev mej, v ha -4 nen zas tak moc." N neuron se tak zeptal v ech, podle znam nka v hy ur oval , jestli m m t stejnou nebo rozd lnou hodnotu ne neuron, kter ho se pt , a proto e byl rozen demokrat, ka d mu dal v tomhle hlasov n tolik hlas, kolik inila absolutn hodnota v hy jeho spoje. Pak vsledky se etl a podle vsledku se rozhodl bu( pro +1 nebo -1. Tento postup vybavov n se v dy po kone n m po tu krok zastav v nkter m z nau ench vzor. To, e jsme brali neurony jeden po druh m a ne nar z m velk vznam, proto e kdybychom nejd v vypo tali nov hodnoty v ech neuron a pak je teprve nastavili, nebyla by kone nost zaji tna.
4 HOPFIELDV MODEL
20 3
2
4 5
1
6
n 7
Obr zek 16: Hopelv model. wij = wji wii = 0 Kone nost postupu si dok eme zaveden m energetick funkce
E=;
X ij
wij Si SJ
Vypad sice podobn jako chybov funkce ve v cevrstvch s t ch, ale je to nco jin ho. Energetickou funkci m eme zav st jen u s t se symetrickmi v hami. Energetick funkce m energii syst mu a plat , e vdy kles nebo z stv stejn, pokud se syst m vyvj podle sv ho dynamick ho pravidla.
Dkaz kone nosti0 po tu krok vybavovn * Dok eme si, e energie klesne v dy, kdy se zmn hodnota neuronu. Nech je Sx nov hodnota stavu Sx pro njak neuron x.
X Sx0 = sgn( wxj Sj )
.
j
(3)
Pokud Sx0 = Sx (neuron se nezmnil), energie zstala stejn . V opa n m p pad Sx0 = ;Sx, tak e rozd l energi je
E0
= = =
E
=
E0 ; E
= = =
XX X X ;( wij Si Sj + wix Si Sx0 + wxj Sx0 Sj ; wxx Sx0 Sx0 ) i j i6=x j 6=x X X X ;( wij Si Sj + (wkx + wxk )Sk Sx0 ; 0) i6=x j 6=x k X X X ;( wij Si Sj + 2wkx Sk Sx0 ) i6=x j 6=x k X X X wij Si Sj + 2wkx Sk Sx ) ;( i6=x j 6=x X Xk 0 ; 2wkx Sk Sx + 2wkx Sk Sx k Xk 0 2wkx Sk (;Sx + Sx ) k X k
= 4Sx
E0 ; E
= 4Sx
(4) (5) (6) (7) (8) (9)
2wkx Sk (2Sx )
(10)
wkx Sk
(11)
wjx Sj
(12)
X k
X j
4 HOPFIELDV MODEL
21
Obr zek 17: Prostor stav s t se temi atraktory.
P
kde j wjx Sj m opa n znam nko ne Sx podle 3, tak e cel vraz je z porn. Tedy energie klesne poka d , kdy se zmn hodnota Sx njak ho neuronu. Stav bin rn Hopeldovy s t je ale vlastn bin rn slo, tedy stav je kone n po et. Kdy tedy s mn svj stav kles jej energetick funkce a proto nem e doj t k zacyklen stav, tak e po kone n m po tu krok se mus dostat do stavu, kdy u dn zmny neuron nemohou probhnout a v nm se zastav .
4.2.4 Kapacita asociativn pamti *
Energetickou funkci si opt m eme pedstavit jako plochu nad prostorem stav s t, jako "energetickou krajinu" (energy landscape). Lok ln minima "dol krajiny jsou atraktory, do kterch se s t v dy dostane. Cel prostor stav je tak rozdlen na baz ny atraktor. Schematicky to zobrazuje obr zek 17. Ot zka zn , jestli atraktory jsou zrovna ty vzory, kter jsme si chtli zapamatovat. Odpov( nen jednoduch . Voln zde opisuji z vr kapitoly pln vpo t z knihy "Introduction to the theory of neural computation,Addison-Wesley, 1992": Kapacita pmax (po et uschovatelnch vzor) je v p m "mrnosti k N (po et neuron), ale nikdy vy ne 0:138N , pokud se spokoj me s malm mno stv m chybnch bit v ka d m vzoru+ nebo je v p m "mrnosti k N=log(N ), pokud trv me na tom, aby vt ina vzor byla zapamatov na bezchybn. Krom atraktor odpov daj c ch zapamatovanm vzorm jsou je t jin atraktory.
Ke ka d mu zapamatovan mu vzoru S p je atraktorem tak inverzn stav (;S p ), kter m stejnou energii. To nen pro praktick pou it zase takov probl m, sta v echny hodnoty zinvertovat. Stabiln jsou tak tzv. mixture states (mixovan stavy) S mix, kter odpov daj line rn m kombinac m lich ho po tu vzor. Nejjednodu p pad je symetrick kombinace t zapamatovanch vzor:
Simix = sgn(Sip1 Sip2 Sip3 ) V ech osm kombinac je mo nch. Hammingova vzd lenost (po et li c ch se bit) stavu S mix od v ech t vzor Sip1 Sip2 Sip3 je N=4, le tedy na m st stejn vzd len m od v ech komponent. Podobn je to u 5,7,. . . stav. Pro p li velk po ty zapamatovanch stav existuj je t dal atraktory, kter nemaj nic spole n ho se zapamatovanmi vzory, k se jim spin glass states, co je pevzato odnkud ze statistick mechaniky. Na tst mixture states a spin glass states maj mnohem men baz ny(?) atrakce ne zapamatovan vzory, tak e je to celkem smla, kdy do nich spadneme. Nav c byly vypracov ny technick triky, kter umo !uj tato minima zmen it nebo odstranit.
4 HOPFIELDV MODEL
22
Obr zek 18: Postupn vybavov n zapamatovan slice
4.2.5 Shrnut
Na rozd l od v cevrstvch s t perceptron, kter d vaj odpov( ihned, Hopeldv model potebuje njak as, aby se ust lil v njak m stabiln m stavu. Postup vybavov n tvar zapamatovanch slic je na obr zku 18. Krom z kladn ho Hopeldova modelu existuj jeho roz en , kter umo !uj pou vat m sto bin rn ch re ln hodnoty, nebo kter si m sto jednotlivch stabiln ch stav pamatuj cel sekvence stav. Hardwarov implementace asociativn pamti jsou rzn , v sou asnosti je ve vvoji metoda, kter jako matici vah pou v hologram. To umo !uje dos hnout hustoty a 1012 spoj na cm3 , bohu el vybavov n je ste n destruktivn , tak e uschovan vzory mus bt po ase obnovov ny.
4.3 Optimizace pomoc st Hopeldova typu
Hopeldova s je vlastn dynamick syst m, u kter ho um me mit jeho energii. O t v me, e nikdy neroste. To vedlo k n padu pou t tuto s pro e en probl m, ve kterch jde o minimalizaci njak funkce. Pou itelnost si uk eme na probl mu obchodn ho cestuj c ho. Obchodn cestuj c m za "kol procestovat m mst tak, aby v ka d m byl pouze jednou a urazil co nejmen vzd lenost. Probl m vye me pomoc Hopeldovi s t s n neurony, kde n = m2 a ka d neuron reprezentuje spoj mezi dvma msty. Neurony m me uspo d ny do tvercov matice a hodnota neuronu ud v , jak moc dan spoj mezi msty pat do vsledn cesty. Ve vsledn matici mus bt v dy nanejv jeden nenulov neuron v ka d m dku a nanejv jeden nenulov neuron v ka d m sloupci, aby se matice dala interpretovat jako okru n cesta mezi msty. kolem s t je minimalizovat energetickou funkci E navr enou tak, aby byla minim ln pr v kdy jsou splnny po adavky na vslednou matici.
XX XX X XX E =A xri :xrj + B xir :xjr + C (( xij ) ; m)2 + D ( d(r s)xri (xsi+1 + xsi;1 )) {z } | r ij{z } | r ij{z } | ij {z } | rs i 1
2
4
3
1 2 3 4
Prvn len roste s po tem nenulovch neuron v jednom dku. Druh len roste s po tem nenulovch neuron v jednom sloupci. Tet len je nejmen pro pr v m spoj mezi msty. Kdybychom pou ili jen prvn ti leny, vsledkem by byla nulov matice. Proto tvrt len po t d lku cesty. A B C D jsou parametry (konstanty) ur uj c , jak velk draz d v m na jednotliv omezen . S nen bin rn , neuron m e ur ovat, e spoj mezi msty pat do hledan cesty tak napl. Jak te( z sk m s minimalizuj c pr v tuto zbsilou energetickou funkci ? Jednodu e, v imnu si, e moje energetick funkce XX XX X X
E1 = A
a energetick funkce Hopeldovi s t
xri xrj + B
E2 = ;
+C (
)2 + D
XX
wij xi xj jsou ob funkce ve stejnch promnnch x, tak e v hy wij v E2 m u rovnou vypo tat z E1 . Tak e s pro e en
probl mu obchodn ho cestuj c ho neu m, ale v hy rovnou vypo t m a m m s hotovou. Potom jenom nech m s ust lit a jedni kov neurony mi ozna uj p m cesty mezi msty, kter tvo kr tkou okru n j zdu. Tento postup d v dobr suboptim ln e en .
5 UEN SAMOORGANIZAC
23
5 U en samoorganizac
V n sleduj c ch kapitol ch opust me u en s u itelem a zam me se na s t, kter se u bez uitele. Zavedeme si zkratky LTM (long term memory) a STM (short term memory). Dlouhodob pam LTM sest v z nastaven synaptickch vah, kter se pomalu mn , kde to kr tkodob pam STM je tvoena okam itm stavem vzruch, kter se ka dm okam ikem prom!uje. Pi u en bez u itele s dost v na vstup mno inu podnt, kter si sama ut d . Nap klad rozdl podnty do skupin podle podobnosti a ur typick ho z stupce skupiny (model ART), nebo s svou kongurac za ne vystihovat topologii prostoru vstup (Kohonen). Pi u en samoorganizac jsou vektory LTM a STM stejn ho typu. U en prob h podle vzorce
LTMnew = LTMold + (STM ; LTMold) tedy dlouhodob pam se zmn "mrn rozd lu pich zej c ho podntu od zapamatovanch hodnot. Parametr se nazv koecient plasticity a jeho extr mn hodnoty jsou nula, kdy se s nen schopn u it, a jedna, kdy si s nic nezapamatuje dlouhodob, nov podnty v echno pemaz vaj .
5.1 Laterln inhibice
Later ln znamen vrstvov, inhibice je psoben , kter nco sni uje, m eme tedy later ln inhibici voln pelo it jako vzjemn tlumen v rmci vrstvy. Pi later ln inhibici jsou neurony v jedn vrstv propojeny navz jem tak, e ka d neuron psob kladnou (excita n ) vazbou s m na sebe a z pornou (inhibi n ) vazbou na ostatn neurony. Aktivovan neuron tak svoji vlastn aktivaci posiluje, zat mco aktivaci ostatn ch neuron tlum . Vazby mezi neurony jsou nazna eny na obr zku 19. Vsledek vz jemn ho psoben neuron pi later ln inhibici je, e nejsilnji aktivovan neuron utlum v echny ostatn a zstane jedinm aktivovanm neuronem. Tento princip se pou v tehdy, kdy mnoho neuron reaguje na stejn podnt a my chceme zjistit, kter z nich zareagoval nejv ce. Princip jedin ho zv tziv ho neuronu se v angli tin ozna uje jako WINNER TAKES ALL.
+ -
-
-
-
-
-
Obr zek 19: Later ln inhibice
6 Kohonenovy mapy
Kohonenova s je nakreslena na obr zku 20. Je tvoena vrstvou n vstupnch neuron , kter slou jen k na ten podnt pedstavovanch n-prvkovmi vektory ~x = (x1 : : : xn ) a druhou vrstvou kohonenovch neuron , kter jsou vz jemn spojeny vazbami later ln inhibice. Do ka d ho z kohonenovch neuron pich z spoje ze v ech vstupn ch neuron, ka d kohonenv neuron tedy te vstupn vektor ~x. Vstupy jsou n sobeny synaptickmi vahami, tak e ka d mu kohonenovu neuronu i p slu vektor synaptickch vah w~ i . Podstata Kohonenova modelu spo v v tom, e vektor vah je stejn jako vektor vstupu n-prvkov. Pro velk form ln zjednodu en budeme pou vat normalizovan vektory w~ a ~x, tedy j~xj = jw~ j = 1. Prostor vah je toto n s prostorem vstup. Proto e jsou vektory normalizovan , je tento prostor povrch n-rozmrn
hyperkoule. Vektory vah w~ jsou body na t to hyperkouli.
6 KOHONENOVY MAPY
24 Kohonenovy neurony (lat.inhibice)
w~ vstupn neurony Obr zek 20: Kohonenova s
6.1 Funkce Kohonenovy st
Pi l vstup ~x aktivuje v echny kohonenovy neurony. Hodnota excitace je d na skal rn m sou inem w~ :~x 3 Nejvt excitaci m ten neuron, kter je na hyperkouli nejbl vstupu. 4 Kohonenovy neurony se navz jem ovliv!uj later ln inhibic , tak e po kr tk dob se s ust l ve stavu, kdy bude excitovan jen jeden neuron a to ten, kter byl na po tku excitovan nejv c, tedy ten nejbli vstupu. Tomuto aktivovan mu neuronu se k grandmother cell, co poch z z diskus , jestli je v mozku neuron reaguj c v dy pr v ve chv li, kdy lovk vid svoji babi ku. w x w
w w
w
w Obr zek 21: Rozdlen prostoru vstup na oblasti p slu n jednotlivm kohonenovm neuronm Povrch hyperkoule je tak rozdlen na jak si Voron ho oblasti p slu n kohonenovm neuronm, jak je nazna eno na obr zku 21. Na vstup zareaguje v dy jen ten neuron, do jeho oblasti vstup spadl.
6.2 Uen kohonenovy st
Objasnili jsme si, e v Kohonenov s ti reaguje na vstup jen ten neuron, kter je vstupu "nejpodobnj ". Te( si pov me, jak rozm stn neuron v prostoru vstup vlastn vznik . Na po tku, pi vzniku s t, jsou neurony shrom dny bl zko sebe nkde na hyperkouli. Pi p chodu vstupu ~x nejv ce zareaguje neuron s p slu nm vektorem synaptickh vah w~ . Tento vybran neuron se zadaptuje podle pedpisu
w~ new = w~ old + (~x ; w~ old ) tedy posune se smrem k bodu pedstavuj c mu vstup. O kolik se posune z le na parametru . Pi = 1 se pesune p mo do bodu vstupu, pi = 0 se ani nehne a pi = 0:5 se posune na polovi n vzd lenost. Zde pich z takzvan konikt stability a plasticity. Pi mal m se s rychle u , ale kvli novm poznatkm zapom n star , pi velk m naopak. Pou v se tedy postupn klesaj c , v "ml d " s t vysok , ve "st " n zk .
P
Pro zapomtliv : skalrn souet je suma souin odpovdajcch si sloek vektor , tedy w~ :~x = ni=1 wi xi Vektor vstupu pedstavuje bod na hyperkouli. Vektor vah w~ njak ho neuronu si lze pedstavit bu tak jako bod na hyperkouli, nebo jako vektor vychzejc ze stedu koule do bodu na hyperkouli. Vektor vah tak vlastn uruje rovinu, kter prochz stedem hyperkoule a vektor vah je jejm normlovm vektorem. Pi vynsoben w~ :~x je vsledek vzdlenost bodu ~x od roviny uren vektorem w~ . Vzhledem k tomu, e bod ~x mus leet na hyperkouli, bude jeho vzdlenost od roviny nejvt (a rovna 1) prv tehdy, kdy bude toton s pr sekem hyperkoule s vektorem w~ , tedy kdy bude toton s bodem w~ . 3 4
6 KOHONENOVY MAPY
25
Kohonenova s se u cel ivot, nem f zi u en a f zi pou v n jako perceptrony nebo Hopeldv model, u se za provozu. Smyslem Kohonenovy s t je vystihnout charakter mno iny vstup. Pedstavme si, e mno ina vstup tvo na hyperkouli jak si shluky, tzv.klastry (clusters). Pokud je kohonenovch neuron stejn po et jako shluk, ka d neuron si najde "vlastn " shluk a us dl se v jeho stedu, stane se jeho typickm z stupcem. Nav c tam, kde bude vt hustota vstup, bude i v ce neuron. D se to pedstavit na analogii s obchody s potravinami. Tam, kde je lid m lo, na samot ch, obchody skoro vbec nebudou, naopak ve mstech, kde je vysok hustota lid , bude obchod mnoho a jejich hustota na tvere n kilometr bude zhruba odpov dat hustot lid . Kohonenova s se pou v na roztizov n vstup do skupin, pi em tyto skupiny si s sama vytvo . Nedostatkem Kohonenova modelu je to, e po et neuron mus me ur it pedem. Tento nedostatek odstra!uje ART v dal kapitole.
Vylepen u en Kohonenovy s t se d dos hnout t m, e na vstup nebude reagovat jen jeden neuron, ale v c.
Kohonenovy neurony krom logick ho um stn na hyperkouli maj tak fyzick um stn v re ln m prostoru, teba mozku. (T m se ne k , e v mozku jsou Kohonenovy neurony, ale co kdyby byly.) Pi later ln inhibici neoslabuje v echny neurony stejn, ale v z vislosti na fyzick vzd lenosti podle kivky na obr zku 22. Velikost fyzick ho okol se
asem zmen uje kvli stabilit. +++ - -
- -
Obr zek 22: Kivka "mexick ho klobouku" pi later ln inhibici Kohonen zkou el vyrobit phonetic typewriter , psac stroj ovl dan hlasem.
6.3 Counter propagation
Counter propagation je rychlej ne back-propagation, ale vytv m n pesn prototypy. Pou v Kohonenovu s nadstavenou o dal vrstvu vstupn ch neuron, kter se u Grossbergovm algoritmem. Spoje sb haj c se ze vstupn ch neuron do jednoho kohonenova neuronu se nazvaj instar (do-hvzda), spoje od kohonenova neuronu ke Grossbergovm neuronm se nazvaj outstar. y outstar instar x
Grossberg Kohonen vstupn neurony
Obr zek 23: Counter-propagation Na vstup a vstup d me tr ninkovou dvojici (~x ~y). V kohonenov vrstv na vstup zareaguje pr v jeden neuron, kter vy le jedni kov impuls pes "outstar" k horn vrstv Grossbergovch neuron, impuls je vyn soben synaptickmi vahami "outstar". Vstup se porovn s po adovanm vstupem ~y a modikuj se v hy "outstar" podle Grossbergova pedpisu
w~ 0 = w~ + (~y ; w~ ):k
Tak e s vlastn vytv prmrnou odpov( na leny njak ho klastru. Kohonenova vrstva rozdluje vstupy do klastr, na v echny vstupy z jednoho klastru zareaguje v dy ten stejn neuron. Grossbergova vrstva pak pro
7 ADAPTIVE RESONANCE THEORY
26
klastr vyr b takovou odpov(, kter vznikla postupnm spojen m vektor ~y p slu nch vstupm v klastru. S opt nem oddleny f ze u en a pr ce, u se po celou dobu. Je samozejm mo n od ur it ho okam iku zastavit u en nastaven m parametr a na nulu. Counter propagation je mo n modikovat ne"plnou later ln inhibic nebo dal transformac na Grossbergovch neuronech. Counter propagation je velice rychl, pou v se ped backem pro orientaci. Kohonenova vrstva zaji uje vysti en struktury vstupn ho prostoru, Grossbergova vrstva transformuje z stupce klastr do vstupn ho prostoru.
P klad , s byla u ena na funkci sin, jako vstupy j byly pedkl d ny hodnoty z intervalu < 0 2 >, jako
vstupy odpov daj c hodnoty sin. Neurony Kohonenovy vrstvy se rovnomrn rozprostely po intervalu, rozdlily ho na mnoho malch podinterval. Pro ka d podinterval pak Grossbergova vrstva vyrobila prmrnou odpov(. Vsledek je na obr zku 24.
Obr zek 24: Vsledek conterpropagation pi u en funkce sin
7 Adaptive Resonance Theory Tento model se pou v pro kategorizaci vstupn ch dat do kategori se sou asnm tvoen m prototyp idealizovnach z stupc kategori . Pokud pedkl d me Kohonenov s ti dal a dal data, nem me zaji tnu stabilitu ji vytvoench kategori dat. Nov data mohou kategorie zmnit. M eme samozejm sn it u c parametry na nulu a t m zmrazit stav s t. Ale pak s ztrat svoji plasticitu, schopnost reagovat na nov data. Nen jednoduch m t z rove! stabilitu ji nau en ho a plasticitu reagov n na nov podnty. Toto je Grossbergovo dilema plasticity a stability. Abychom vytvoili njak re ln syst m schopn fungovat a pitom reagovat na mn c se prosted , mus me se s t mto dilematem vyrovnat. Dal probl m spo v v tom, kolik vstupn ch bunk (ka d pro jednu kategorii) m me vlastn pou t. Pokud jich d me pevn po et, pak pokud bude kategori v ce ne bunk, bude kategorizace patn . Naopak, pokud jich d me nekone n mnoho, pro ka d vstup se vytvo vlastn kategorie, co je taky k ni emu. Dobr
e en je m t z sob rnu nekone n mnoha bunk, ale nepouvat je, dokud nejsou poteba. V ka d m okam iku bude pou ito pr v tolik bunk, kolik je dosud zn mch kategori , a pokud se objev nov kategorie, pou ijeme dal bu!ku. P nov Carpenter a Grossberg v roce 1988 vyvynuli modely ART1 a ART2, kter se chovaj t mto zpsobem. ART akceptuje vstup jen tehdy, je-li dostate n podobn nkter mu ji existuj c mu prototypu njak kategorie. Pokud nen , vytvo se nov kategorie se vstupem jako svm prototypem a je pou ita nov vstupn bu!ka. Vznam slov "dostate n podobn" z le na parametru vigilance (bdlosti) , kde 0 < 1. Pokud je vigilance velk , je podobnost posuzov na velmi p sn a vznik mnoho pesn vymezench kategori , pi mal vigilanci doch z k lep abstrakci. Hodnotu vigilance je mo no bhem u en mnit. ART1 pracuje s bin rn mi vstupy, ART2 s re lnmi. Budeme se zabvat ART1, proto e je jednodu . Popi me si ART1 jako algoritmus. Mjme vstupn vektory ~x a ulo en vektory prototyp w~ i , v echny N -prvkov
s bin rn mi hodnotami. i indexuje vstupn neurony (tedy kategorie), ka d z nich m e bt bu( enabled nebo disabled. Za neme nastaven m w~ i = ~1 na jedni kov vektory pro v echna i+ jedni kov vektor bude reprezentovat nepou it (uncommited) vstupn neuron, ne kategorii. Pak pedlo me s ti vstup ~x a prov d me algoritmus: 1. Ozna me v echny vstupn neurony jako enabled. 2. Najdme mezi enabled neurony babiku i , pi em babi ka je neuron s maxim ln m w~ i :~x, kde w~ i je normalizovan w~ i . V imnme si, e nepou it neuron nakonec zv tz (stane se babi kou), pokud se pedt m nenajde dn vhodnj .
8 GENETICK ALGORITMY
27
gain control gain control
Recognition eld
reset wave
Comparison eld
INPUT Obr zek 25: Adaptive Resonance Theory 3. Otestujme, jestli je shoda mezi vstupn m vektorem ~x a prototypovm vektorem w~ i dostate n vpo tem pomru
w~ i :~x r=P x
j j
Je to pomr jedni kovch bit z ~x kter jsou z rov! v w~ i . Pokud je r , tedy vt ne vigilance, doch z ke shod (resonanci) a pokra uj krokem 4. Jinak je prototypov vektor w~ i odm tnut. Ozna neuron i jako disabled a vra se na 2. 4. Uprav me babi ku w~ i vynulov n m v ech bit, kter nejsou z rov! v ~x. Je to operace AND, nazv se to maskovnm vstupu. Tento algoritmus m e skon it jedn m ze t zpsob. Bu( nalezneme odpov daj c prototypov vektor, uprav me ho (pokud je to nutn ) a vstupem je kategorie i. Nebo nenalezneme dn prototyp, pak je pou it jeden z je t nepou itch vektor a je nastaven na ~x+ vstupem je nov kategorie i . Nebo v kroku dva u nezbv dn voln nepou it neuron, a pak vstup ignorujeme. Smy ka z kroku 3 zpt do kroku 2 hled mezi prototypovmi vektory ten nejbli , druh nejbli , atd. dokud nenalezne ten, kter spl!uje krit rium r . Toto hled n je pomal , ale prov d se jen do doby, ne se vytvo v echny kategorie obsa en ve vstupn ch datech. Po vytvoen v ech kategori se najde p slu n kategorie na prvn pokus a skok z kroku 3 na 2 se ji nikdy neprov d . V echny kategorie budou vytvoeny po kone n m po tu krok, co plyne z binarity hodnot a toho, e v kroku 4 se bity v dy jen odstra!uj a nikdy nepid vaj . Konkr tn implementace neuronovou s t je na obr zku 25. S sest v ze dvou vrstev, comparison eld a recognition eld. Comparison eld dostane vstup. Po le ho recognition eld, kde jeden neuron (babi ka) zareaguje a po le zp tky sv o ek v n , tedy svj prototypov vektor. Comparison eld porovn vstup s o ek v n m babi ky a pokud jsou si dostate n podobn , babi ka se zadaptuje. Pokud ne, babi ka se zneaktivn (disabled) a znovu se vstup po le do recognition eld. To se opakuje tak dlouho, a se nalezne vhodn babi ka. Pokud se dn nenajde, vytvo se nov neuron, kter dostane vstup jako svj prototyp. Cel syst m je mo n realizovat ist neuron ln, v etn cykl, k tomu slou pomocn neurony ozna en gain control. Adaptace se od Kohonena li v tom, e babi ka se nemn jako vektor, ale za ne tolerovat i vci, kter se j pedt m moc nel bily. Probl m stability a plasticity je vye en jednak t m, e pibvaj vstupn neurony a tak t m, e pi u en se zvy uje m ra abstrakce.
8 Genetick algoritmy
Mjme mno inu P o r objektech, kde ka d objekt z vis na n parametrech (x1 : : : xn ), pi em o ka d m objektu m eme ci jak moc je dobr pomoc kriteri ln hodnot c funkce f (x1 : : : xn ). kol je naj t hodnoty parametr tak, aby f byla maxim ln .
8 GENETICK ALGORITMY
28
Metody jsou: systematick prohled v n prostoru parametr, n hodn vbr, gradientn metody. Nebo m eme pou t genetick algoritmus. Nejd v mus me bin rn zak-dovat parametry.
Binrn k dovn
O1=101110011010101100=4 O2=000110001010001101=3 O3=000101011010001100=4.2 Ka d rys jedince (parametr) xi je k-dov n etzcem nul a jedni ek. Rzn parametry jsou rzn vznamn (barva o , d lka dr p). Mno ina P je populace, mno ina jedinc.
Genetick algoritmus 1. N hodn zvol me nultou gewneraci P0 a stanov me s ly jedinc 2. tvo me nov jedince k en m, nap O1,O2 rodi e, O4 potomek: O2=0001/1000/1010/0011/01=3 O3=0001/0101/1010/0011/00=4.2 O4=0001/0101/1010/0011/01= 3. provedeme n hodnou mutaci z O4 na O5: O4=0001/0101/1010/0011/01= O5=0001/0101/1010/1011/01= Volby rodi , gen i mutac jsou pravdpodobnostn . 4. Odstran me jedince mal s ly z populace tak, aby velikost populace zstala zachov na, nap. z P0 = (O1 O2 O3) vznikne P1 = (O1 O3 O4), kdy s la O4 = 3:7. 5. a opakujeme Ob as mus me v populaci zachov vat i mrz ky, aby se prostor jedinc prohled val eji, jinak skon me rychle, ale v lok ln m maximu.
