5. prednáška. Učenie s odmenom a trestom a emergencia stratégie hry. Priesvitka 1 - PDF

Description
5. prednáška Učenie s odmenom a trestom a emergencia stratégie hry Priesvitka 1 Historický úvod E. L. Thorndike ( ) Americký psychológ Thorndike ( ) vo svojej knihe The Fundamentals of

Please download to get full document.

View again

of 43
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Art & Photos

Publish on:

Views: 14 | Pages: 43

Extension: PDF | Download: 0

Share
Transcript
5. prednáška Učenie s odmenom a trestom a emergencia stratégie hry Priesvitka 1 Historický úvod E. L. Thorndike ( ) Americký psychológ Thorndike ( ) vo svojej knihe The Fundamentals of Learning zaviedol dva zákony: Priesvitka 2 1. Zákon účinku: Ak odozva na opakujúci sa stimul je kladná (odmena), potom väzba medzi stimulom a odozvou sa postupne zosilňuje. V opačnom prípade, ak odozva je záporná (trest), potom väzba medzi stimulom a odozvou postupne zaniká. 2. Zákon opakovaného používania: Požadované správanie je výsledkom častého používania dvojica stimul a odozva Priesvitka 3 Metóda učenia s odmenou a trestom Učenie, ktoré je založené na týchto dvoch zákonoch sa nazýva učenie s odmenou a trestom ( reinforcement learning ). Tvorí teoretický základ behavioristického prístupu k učeniu. Priesvitka 4 Literatúra (1) R. S. Sutton and A. G. Barto: Reinforcement Learning:An Introduction, MIT Press, Cambridge, MA, (2) R. S. Sutton: Learning to Predict by the Methods of Temporal Differences. Machine Learning 3 (1988), (3) V. Kvasnička: Emergencia stratégie hry. AT&P Journal 12 (1999), Tieto citácie a mnoho iných je dostupných na internetovskej adrese ftp://math.chtf.stuba.sk/pub/vlado/ RL_textbook Priesvitka 5 Učenia s odmenou a trestom Agent, ktorý je predmetom učenia, musí mať kognitívny orgán, ktorý vykazuje určitú plasticitu. Kognitívny orgán je modelovaný jednoduchou doprednou neurónovou sieťou s jednou vrstvou skrytých neurónov. Poznámka: Plasticita neurónovej siete sa realizuje pomocou zmeny váhových koeficientov. Priesvitka 6 Teória Študujme agentov, ktorý sú určený pomocou týchto dvoch množín: (1) Množina agentových stavov S={s 1, s 2, } (2) Množina agentových akcií A={a 1, a 2, } Akcie agentov sú interpretované ako funkcie, ktoré zobrazujú stavy agentov na seba, s = a s af. Priesvitka 7 Agent má kognitívny orgán (prediktor) pomocou ktorého ohodnocuje svoje stavy reálným číslom (predikcia) af: S Pw R alebo explicitne i ( ) z = P s ;w Zobrazenie P prediktor je parametrická funkcia. Hovoríme, že vykazuje plasticitu vzhľadom k parametrom w. i Predpoklad: Výber určitej akcie a A, ktorá je aplikovaná na stav s S je riadený kognitívnym orgánom. Priesvitka 8 Postup učenia Majme sekvenciu stavov agenta a jej ohodnotenie (pochvala - trest) s, s,..., s, z 1 2 m kde z je ohodnotenie, ktoré vyjadruje skutočnosť, či sekvencia má alebo nemá požadovanú vlastnosť ( ) ( ) 1 sekvencia má danú vlastnosť z = 0 sekvencia nemá danu vlastnosť Priesvitka 9 Sekvencia stavov s 1,s 2,...,s m je zostrojená kvázináhodne, t.j. podsekvencia z = P s ;w. s,s,...,s je rozšírená o ďalší stav s i+1 na základe predikcie ( ) 1 2 i i i i+ 1 = j ( () i ) j s arg max P s ;w Priesvitka 10 Stratégia učenia Adaptovať kognitívny orgán P(w) tak, že všetky predikcie ( ) ( ) z = P = P s ;w,...,z = P = P s ;w m m m sú rovnaká, ako externé ohodnotenie celej sekvencie číslom z = P m +1 Poznámka: Používame takú stratégiu učenia, že ak je výsledná sekvencia vyhodnotená ako úspešná (neúspešná), potom všetky stavy z tejto sekvencie sú tiež úspešné (neúspešné). Priesvitka 11 Adaptácia parametrov kognitívneho orgánu Uvažujme sekvenciu stavov, ktorá je vyhodnotená ako celok číslom z, potom každý stav tejto sekvencie je tiež ohodnotený týmto číslom a fa f a f s, z, s, z,..., s, z 1 2 Kvalita tejto predikcie je určená pomocou účelovej funkcie af m b a fg2 t = 1 1 E w = z P st ; w 2 Účelová funkcia je nezáporná, rovná sa nule len vtedy, ak kognitívny orgán poskytuje také ohodnotenie všetkých stavov sekvencie, ktoré je totožné s externým ohodnotením celej sekvencie m Priesvitka 12 Adaptačná metóda učenia s odmenou a trestom má tieto základné formule w: = w+δ w Δw = m t = 1 Δ w t a f Δw = α P P λ grad P t t+ 1 t t k = 1 t k w k Poznámka. Tieto formule tvoria základ metódy učenia s odmenou a trestom vo verzii časových rozdielov RL-TD(λ) (reinforcement learning - temporal differences) Priesvitka 13 Architektúra neurónových sietí použitých ako kognitívny orgán Ohodnotenie stavov je uskutočnené pomocou parametrickej funkcie P(s)=P(x s ;w) Táto funkcia je uskutočnená pomocou doprednej neurónovej siete s jednou vrstvou skrytých neurónov Priesvitka 14 Algoritmus učenia Step 1. Váhové a prahové koeficienty kognitívneho orgánu sú náhodne vygenerované, t:=1. Step 2. Ak kázináhodne vygenerovaná sekvencia stavov spĺňa požadovanú vlastnosť, potom je ohodnotená číslom z=1, v opačnom prípade je ohodnotená číslom z=0. Step 3. Váhové a prahové koeficienty sú obnovené pomocou formúl RL-TD(λ) metódy,t:=t+1. Step 4. Ak sú splnené konvergenčné kritéria, potom prejdi na krok 5, v opačnom prípade pokračuj krokom 2. Step 5. Stop. Priesvitka 15 Prvý ilustratívny príklad Pohyb v jednoduchom bludisku Študujme jednoduché kruhové bludisko, ktoré obsahuje 7 miestností , pričom miestnosť A je vstupná a miestnosť D je výstupná. V tomto bludisku sa pohybuje agent s kognitívnym orgánom, jeho cieľom je nájsť čo najkratšiu cestu z A do D. Pri generovaní tejto cesty používa svoj kognitívny orgán ako určitého radcu, ktorým smerom sa má pohybovať. Priesvitka 16 Príklady ciest v bludisku: (1) W 1 =ABCBAGFED, W 1 =9 (2) W 2 =ABCD, W 2 =4 (najkratšia cesta) Stavy sú reprezentované siedmimi binárnymi vektormi # state binary vector x 1 A ( ) 2 B ( ) 3 C ( ) 4 D ( ) 5 E ( ) 6 F ( ) 7 G ( ) Priesvitka 17 Každá orientovaná hrana (X,Y) je ohodnotená predikciou P(X,Y), čo je realizované pomocou doprednej neurónovej siete so vstupnými aktivitami určenými vektormi x X a x Y, ktoré sú priradené stavom X a Y. Priesvitka 18 Predikcia P(X,Y) je interpretovaná ako pravdepodobnosť, že daná cesta W =A...UVX bude rozšírená na cestu W '=A...UVXY Pr Pr =, Pr = Pr Pr1+ Pr2 Pr1+ Pr2 Priesvitka 19 1. α=0.1 (rýchlosť učenia). 2. λ=0.9 (temporal-difference parameter). 3. p=5 (počet skrytých neurónov). Parametre adaptačného procesu 4. Počiatočné hodnoty váhových a prahových koeficientov sú náhodne vyberané z otvoreného intervalu (-2,2). 5. Proces učenia je zastavený po epochách. 6. Kvázináhodne generované cesty sú ohodnoco-vané podľa formule z ( ak W ) ( ak W ) 1 = 4 = 0 4 Priesvitka 20 Priesvitka 21 Priesvitka 22 Priesvitka 23 Second illustrative example Let us consider a slightly complex example than the previous one, it corresponds to a generator of bounded random walks composed of sixteen states A, B,,O, P. Our goal is to construct walks W that (1) start in the initial state A and end in the terminal state P, (2) are of shortest length, i.e. W =6. Priesvitka 24 States are represented by fifteen 15-dimensional binary unit vectors # state binary vector 1 A ( ) 2 B ( ) 3 C ( ) 4 D ( ) 5 E ( ) 6 F ( ) 7 G ( ) 8 H ( ) 9 I ( ) 10 J ( ) 11 K ( ) 12 L ( ) 13 M ( ) 14 N ( ) 15 O ( ) 16 P ( ) Priesvitka 25 Each oriented edge (X,Y) is evaluated by a predictor P(X,Y) with the following meaning: Let us have a walk W=(A UX) terminated in the state X, and let the last state X has one to three forthcoming neighbor states denoted Y, Z, and V, respectively. The walk is extended by one of them with probability proportional predictors P(X,Y), P(X,Z), and P(X,V). Priesvitka 26 W ( Y ( )) Z ( ) ( ) W = A...UXY p P X,Y = A...UX W = A...UXZ p P X,Z W = A...UXV p P X,V ( ) ( V ) This type of quasirandom selection is numerically realized by the roulette wheel (see Goldberg s implementation of GA) Priesvitka 27 pr 1 pr pr 2 3 = = = py p + p + p Y Z V pz p + p + p Y Z V p V p + p + p Y Z V Priesvitka 28 The predictor P(X,Y) is numerically realized by the feed-forward neural network with input-neuron activities specified by the vector representation of states X. Priesvitka 29 Priesvitka 30 Priesvitka 31 Tretí ilustratívny príklad Hra piškvorky (tic-tac-toe) The American Heritage Disctionary: A game played by two people, each trying to make a line of three X's or three O's in a boxlike figure with nine spaces. Hra je zahájená prvým hráčom (X), na jeho ťah odpovedá druhý hráč (O), toto striedanie hráčov sa opakuje až do konca hry. Koniec hry nastáva víťaztvom hráča, ktorý dosiahol riadkovu pozíciu troch svojich znakov, alebo remízou, ak po deviatich ťahoch ani jeden z hráčov nedosiahool víťaznú pozíciu. Priesvitka 32 Reprezentácia algoritmu pomocou stromu riešení Priesvitka 33 Vrchná časť stromu riešení Priesvitka 34 Dimenzia stavového priestoru je určená pomocou jednoduchých kombinatorických úvach takto N p 9 p = p = 1 p + = p 1 p Pomocou metódy spätného prehľadávanie je možné zostrojiť celý strom riešení, kde počty koncových pozícií sú uvedené v tabuľke No. Počet Typ víťazstvo hráča X víťazstvo hráča O remíza hráčov X a O celkový počet Z tejto tabuľky vyplýva, že prvý hráč X má väčšiu šancu hru vyhrať. Podrobnou analýzou sa dá ukázať, že aj hráč O môže hru forsírovať tak, že remizuje. Celkový počet koncových vetví v strome riešení možno jednoducho odhadnúť ako 9!= Priesvitka 35 Model hry Model obsahuje 6 pravidiel s klesajúcou prioritou: 1. Hráč vykoná ťah, ktorý vedie k jeho víťazstvu. 2. Hráč vykoná ťah, ktorý zabráni víťazstvu oponenta v nasledujúcom ťahu. 3. Hráč vykoná ťah, ktorým si pripraví možnosť dvojitého použitia 1. pravidla (tzv. vidlička). 4. Hráč vykoná ťah, ktorým zabráni oponentovi pripraviť vidličku 5. Hráč obsadí stredové pole. 6. Hráč obsadí rohové pole, ktorého proti-poloha je obsadená oponentom 7. Hráč obsadí rohové pole. 8. Hráč obsadí volné pole. Priesvitka 36 X E X O E X X E X E X O O O E E X X E O E E X O X E X E X O E O X A X X O B X O O 2 X 3 O 2 O 2 X 3 X 3 X 1 X 1 X 1 X 5 O 2 X 7 O 4 X 1 X 5 O 6 O 4 C O 4 O 6 O 4 O 2 X 3 X 1 X 5 X 7 O 2 O 2 O 2 X 1 X 1 O 6 X 1 X 5 O 6 X 1 X 5 X 3 O 4 X 3 O 4 X 3 X 7 O 4 D Diagramy A-B znázorňujú základné typy vidličkových pozícií, ktoré sú aplikovateľné použitím pravidiel 3 a 4. Tak napríklad, diagram A znázorňuje východiskovú pozíciu pre prípravu vydličky ; písmena E špecifikujú prázdne bunky. Z diagramu A môžeme vytvoriť dve vydličkové pozície. Diagram C znázorňuje hru, ktorá je prehraná pre hráča O už po druhom ťahu. Druhý hráč urobil fatálnu chybu, keď umiestnil svoju figuru O v druhom ťahu v druhom stĺpci hore, podľa pravidla mal obsadiť rohové pole. Diagram D znázorňuje hru, ktorá prebieha podľa pravidiel, končí remízou.. O 2 O 8 X 7 Priesvitka 37 Pozícia je reprezentovaná 9-rozmerným vektorom ( ) = ( ) { } 9 x P x 1,x 2,...,x 9 01,, 1 kde jednotlivé zložky určujú jednotlivé políčka v pozícii P 0 i té pole je neobsadené xi = 1 i té pole je obsadené X -1 i té pole jeobsaden O ( ) ( ) ( ) Priesvitka 38 Algoritmus modelu Prvý model - agent hrá proti modelu hry piškvorky 1. krok. Váhové koeficienty neurónovej siete sú náhodne vygenerované z intervalu [- 1,1]. 2. krok. Polož t:=1. 3. krok. S 50% pravdepodobnosťou deklaruj agenta ako prvého X-hráča a model ako druhého O-hráča (v opačnom prípade je agent deklarovaný ako druhý O-hráč a model ako prvý X-hráč). Na záver hry pomocou metódy TD(λ) opraví váhové koeficienty kognitívneho orgánu agenta. 4. krok. Polož t:=t krok. Ak t t max, potom pokračuj krokom 3, v opačnom prípade prejdi na krok krok. Koniec algoritmu. Priesvitka 39 2. α=0.1 (rýchlosť učenia). 7. λ=0.3 (temporal-difference parameter). 8. p=30 (počet skrytých neurónov). Parametre adaptačného procesu 9. Počiatočné hodnoty váhových a prahových koeficientov sú náhodne vyberané z otvoreného intervalu (-2,2). 10. Učenia je zastavené po epochách. 11. Pozície sú ohodnocované podľa formule ( ) ( ) ( ) 1 prvý hráč vyhral z = 05. hráči remizovali 0 prvý hráč prehral Priesvitka 40 100 agent remizoval frakcia hier (%) 50 0 agent prehral agent zvíťazil epocha Priebeh frakcií hier (zo 100), ktoré hral agent proti modelu hry, pričom polovicu hier (50) hral ako prvý a druhú polovicu hier hral ako druhý. Z priebehu jednotlivých prípadov jasne vyplýva, že neurónová sieť je schopná tak kvalitnej spontánnej adaptácie, že dokáže neprehrávať s modelom. Priesvitka 41 Záver Uvedený subsymbolický prístup k riešeniu úloh, pre ktoré je len veľmi obtiažne zostrojiť ich efektívny model, poskytuje povzbudzujúce výsledky. V priebehu evolúcie agentov dochádza k emergencii stratégie hry. Pre hru backgamon získal Tesauro neurónovú sieť, ktorá je schopná hrať túto hru na veľmajstrovskej úrovni. Získané výsledky sú vynikajúcou ilustráciou subsymbolického prístupu k riešeniu zložitých úloh, ktoré sú ťažko riešiteľné technikami klasickej (symbolickej) umelej inteligencie. V rámci subsymbolického prístupu, založenom na neurónových sieťach s dopredným šírením signálu a adaptačnej metóde učenia s odmenou a trestom (reinforcement learning), je možné riešiť rôzne úlohy z robotiky, riadenia zložitých systémov, komplexných strategických hier, atď. bez nutnosti poznať ich model alebo databázu ich známych realizácií. Priesvitka 42 A cognitive joke After D. J. Chalmers a 'cognitive joke' is a joke whose humour seems to rely on higher-level, more abstract cognitive processing in the brain, where offered solution is highly unexpected The End Priesvitka 43
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks