inteligenta artificiala: invatarea cu intarire

Click here to load reader

Post on 27-Jun-2015

318 views

Category:

Documents

4 download

Embed Size (px)

DESCRIPTION

Inteligenta artificiala: Invatarea cu intarireArtificial Intelligence: Reinforcement Learning

TRANSCRIPT

Inteligen artificial 13. nvarea cu ntrire Florin Leon Universitatea Tehnic Gheorghe Asachi din Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm2 nvarea cu ntrire 1. Introducere 2. Procese de decizie Markov 3. nvarea pasiv 4. nvarea activ 5. Optimizri 6. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm3 nvarea cu ntrire 1. Introducere 2. Procese de decizie Markov 3. nvarea pasiv 4. nvarea activ 5. Optimizri 6. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm4 Tipuri de nvare nvarea supervizat Date de antrenare: (A, c) atribute, clas Scopul este predicia lui c i minimizarea erorii Regresie, clasificare nvarea nesupervizat Date de antrenare: X numai atributele Scopul este determinarea unor grupuri de puncte similare n spaiul multidimensional cu |X| dimensiuni Partiionare (clusterizare, grupare) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm5 nvarea cu ntrire engl. reinforcement learning Agentul trebuie s nvee un comportament fr a avea un instructor Agentul are o sarcin de ndeplinit Efectueaz nite aciuni n mediul de execuie Ulterior, primete un feedback (reacia mediului) privind ct de bine a acionat n vederea ndeplinirii sarcinii Agentul urmrete ndeplinirea aceleiai sarcini n mod repetat Un agent este o entitate autonom (software sau hardware) care acioneaz fr intervenie uman Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm6 nvarea cu ntrire Aceast modalitatea de nvare se numete nvare cu ntrire Agentul primete o recompens (ntrire pozitiv) dac ndeplinete bine sarcina Agentul primete o pedeaps (ntrire negativ) dac ndeplinete ru sarcina Experiena este un profesor dur pentru cnti i d testul i abia apoi i pred lecia (Vernon Law) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm7 Modelul de interaciune Agentul Efectueaz aciuni Mediul Acord recompense i prezint agentului situaii numite stri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm8 nvarea cu ntrire Scopul este de a determina agentul s acioneze astfel nct s-i maximizeze recompensele Agentul trebuie s-i dea seama ce secven de aciuni conduce la ndeplinirea sarcinii Datele de antrenare:(S, A, R) Stare, Aciune, Recompens Aciunile pot afecta i recompensele ulterioare, nu numai pe cele imediate (efect ntrziat) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm9 Gruk Der findes en visdommens vej det er dn, som br vre let at erindre: dum dig og dum dig og dum dig igen, men mindre og mindre og mindre. Exist un drum al nelepciunii este unul ce ar trebui s fie uor de inut minte: greete i greete i greete din nou, dar mai puin i mai puin imai puin. The road to wisdom? Well, it's plain and simple to express: err and err and err again but less and less and less. Piet Hein (1905-1996), inventator i poet danez Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm10 nvarea cu ntrire 1. Introducere 2. Procese de decizie Markov 2.1. Iterarea valorilor 2.2. Iterarea politicilor 3. nvarea pasiv 4. nvarea activ 5. Optimizri 6. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm11 Decizii secveniale Mediu determinist: (sus, sus, dreapta, dreapta, dreapta) Mediu stohastic: model de tranziii T(s, a, s) probabilitatea de a ajunge din starea s n starea s efectund aciunea a Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm12 Presupunerea Markov Starea curent Xt depinde doar de o istorie finit a strilor anterioare Procese Markov de ordin nti: starea curent Xt depinde doar de starea anterioar Xt-1 P(Xt | Xt-1 , , X0) = P(Xt | Xt-1) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm13 Proces de decizie Markov Starea iniial S0 Modelul de tranziii T(s, a, s) Funcia recompens R(s) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm14 Definiii O soluie la o astfel de problem de cutare se numete politic (engl. policy) i se noteaz Traduceri alternative pentru policy: tactic sau strategie (s) este aciunea recomandat n starea s Politica este o descriere a unui reflex Politica este definit pentru toate strile: ce aciune trebuie s fac agentul n orice stare s-ar afla Se numete utilitate suma recompenselor pentru o secvende stri Recompensa este ctigul pe termen scurt Utilitatea este ctigul total pe termen lung Mediu stohastic: utilitate ateptat Politica optim *: maximizeaz utilitatea ateptat Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm15 Exemple de politici R(s) = recompensa n fiecare stare neterminal Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm16 Staionaritate Orizont finit Uh([s0, s1, ..., sN+k]) = Uh([s0, s1, ..., sN]) Dup momentul N nu mai conteaz nimic N = 3 trebuie s rite (sus) N = 100 poate alege soluia mai sigur (stnga) Politica optim este nestaionar history Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm17 Staionaritate Orizont infinit Politica optim este staionar Recompense aditive U([s0, s1, s2, ]) = R(s0) + R(s1) + R(s2) + Recompense actualizate (engl. discounted) U([s0, s1, s2, ]) = R(s0) + R(s1) + 2R(s2) + [0,1] este factorul de actualizare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm18 Evaluarea unui orizont infinit Trebuie s ne asigurm c utilitatea unei secvene posibil infinite este finit Abordarea 1. Dac recompensele sunt mrginite i < 1 atunci: Abordarea 2. Dac mediul conine stri terminale i se garanteaz faptul c agentul va atinge una din ele (= politic adecvat, engl. proper policy), putem utiliza = 1 Abordarea 3. Compararea recompenselor medii (pentru fiecare pas) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm19 Evaluarea unei politici Fiecare politic genereaz secvene multiple de stri, datorit incertitudinii tranziiilor T(s, a, s) Valoarea unei politici este valoarea ateptat a sumei tuturor recompenselor actualizate observate dup toate secvenele posibile de stri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm20 Iterarea valorilor engl. value iteration Algoritm pentru calcularea unei politici optime Se calculeaz utilitatea fiecrei stri n mod iterativ, se atribuie valorile corecte pentru utiliti Se folosesc utilitile strilor pentru selectarea unei aciuni optime n fiecare stare Se alege starea cu utilitatea cea mai mare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm21 Utilitile strilor Utilitatea unei stri s este utilitatea ateptat a secvenei de stri urmtoare Secvena este determinat de (s) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm22 Exemplu Fie g = 1 i R(s) = 0.04 lng scop utilitile sunt mai mari pentru c este nevoie de mai puini pai cu recompens negativ pentru atingerea strii respective Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm23 Ecuaia Bellman Ecuaia Bellman (1957) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm24 Politica optim Utilitatea unei stri este recompensa imediat pentru acea stare plus utilitatea ateptat maxim a strii urmtoare Politica optim alege aciunea care conduce n starea cu cea mai mare utilitate ateptat Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm25 Exemplu Se consider rezultatele tuturor aciunilor posibile pentru a selecta aciunea cea mai bun i a atribui utilitatea sa ateptat urmtoarei stri din ecuaia Bellman Exemplu: utilitatea strii (1,1) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm26 Rezolvarea unui proces de decizie Markov n stri posibile n ecuaii Bellman (una pentru fiecare stare) n ecuaii cu n necunoscute: U(s) Nu se poate rezolva ca sistem de ecuaii liniare datorit funciei max Trebuie rezolvat iterativ Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm27 Algoritmul iterrii valorilor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm28 Convergena c = / Rmax Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm29 http://people.cs.ubc.ca/~poole/demos/mdp/vi.html Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm30 Iterarea politicilor engl. policy iteration Dac o aciune este n mod evident mai bun dect toate celelalte, nu avem nevoie de valorile exacte ale utilitilor Algoritmul alterneaz 2 pai: Evaluarea politicii: calcularea utilitilor tuturor strilorpe baza politicii i mbuntirea politicii: calcularea unei noi politici i+1pe baza utilitilor Ui Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm31 Evaluarea politicii Sistem de n ecuaii liniare cu n necunoscute Se poate rezolva exact n O(n3) sau n mod aproximativ mai repede Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm32 mbuntirea politicii Se cunosc toate U(s) Se calculeaz pentru fiecare s: Aceasta este aciunea optim ai*(s) Dac ai*(s) i(s), se actualizeaz politica:i+1(s) = ai*(s) Se pot actualiza doar prile promitoare ale spaiului de cutare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm33 Algoritmul iterrii politicilor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm34 nvarea cu ntrire 1. Introducere 2. Procese de decizie Markov 3. nvarea pasiv 3.1. Estimarea direct a utilitii 3.2. Programarea dinamic adaptiv 3.3. nvarea diferenelor temporale 4. nvarea act