Inteligenta artificiala: Invatarea cu intarire
-
Upload
enrollinfo -
Category
Documents
-
view
357 -
download
4
description
Transcript of Inteligenta artificiala: Invatarea cu intarire
![Page 1: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/1.jpg)
Inteligenţă artificială
13. Învăţarea cu întărire Florin Leon
Universitatea Tehnică „Gheorghe Asachi” din Iaşi
Facultatea de Automatică şi Calculatoare
http://florinleon.byethost24.com/curs_ia.htm
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 2: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/2.jpg)
2
Învăţarea cu întărire
1. Introducere
2. Procese de decizie Markov
3. Învăţarea pasivă
4. Învăţarea activă
5. Optimizări
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 3: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/3.jpg)
3
Învăţarea cu întărire
1. Introducere
2. Procese de decizie Markov
3. Învăţarea pasivă
4. Învăţarea activă
5. Optimizări
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 4: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/4.jpg)
4
Tipuri de învăţare
Învăţarea supervizată
Date de antrenare: (A, c) – atribute, clasă
Scopul este predicţia lui c şi minimizarea erorii
Regresie, clasificare
Învăţarea nesupervizată
Date de antrenare: X – numai atributele
Scopul este determinarea unor grupuri de puncte similare în spaţiul multidimensional cu |X| dimensiuni
Partiţionare (clusterizare, grupare)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 5: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/5.jpg)
5
Învăţarea cu întărire
engl. “reinforcement learning”
Agentul trebuie să înveţe un comportament fără a avea un instructor
Agentul are o sarcină de îndeplinit
Efectuează nişte acţiuni în mediul de execuţie
Ulterior, primeşte un feedback (reacţia mediului) privind cât de bine a acţionat în vederea îndeplinirii sarcinii
Agentul urmăreşte îndeplinirea aceleiaşi sarcini în mod repetat
Un agent este o entitate autonomă (software sau hardware) care acţionează fără intervenţie umană
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 6: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/6.jpg)
6
Învăţarea cu întărire
Această modalitatea de învăţare se numeşte învăţare cu întărire
Agentul primeşte o recompensă (întărire pozitivă) dacă îndeplineşte bine sarcina
Agentul primeşte o pedeapsă (întărire negativă) dacă îndeplineşte rău sarcina
„Experienţa este un profesor dur pentru că întâi îţi dă testul şi abia apoi îţi predă lecţia” (Vernon Law)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 7: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/7.jpg)
7
Modelul de interacţiune
Agentul
Efectuează acţiuni
Mediul
Acordă recompense
Îi prezintă agentului situaţii numite stări
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 8: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/8.jpg)
8
Învăţarea cu întărire
Scopul este de a determina agentul să acţioneze astfel încât să-şi maximizeze recompensele
Agentul trebuie să-şi dea seama ce secvenţă de acţiuni conduce la îndeplinirea sarcinii
Datele de antrenare: (S, A, R) – Stare, Acţiune, Recompensă
Acţiunile pot afecta şi recompensele ulterioare, nu numai pe cele imediate (efect întârziat)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 9: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/9.jpg)
9
Gruk
Der findes en visdommens vej – det er dén, som bør være let at erindre: dum dig og dum dig og dum dig igen, men mindre og mindre og mindre.
Există un drum al înţelepciunii – este unul ce ar trebui să fie uşor de ţinut minte: greşeşte şi greşeşte şi greşeşte din nou, dar mai puţin şi mai puţin şi mai puţin.
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.htm
![Page 10: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/10.jpg)
10
Învăţarea cu întărire
1. Introducere
2. Procese de decizie Markov 2.1. Iterarea valorilor
2.2. Iterarea politicilor
3. Învăţarea pasivă
4. Învăţarea activă
5. Optimizări
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 11: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/11.jpg)
11
Decizii secvenţiale
Mediu determinist: (sus, sus, dreapta, dreapta, dreapta)
Mediu stohastic: model de tranziţii T(s, a, s’) – probabilitatea de a ajunge din
starea s în starea s’ efectuând acţiunea a
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 12: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/12.jpg)
12
Presupunerea Markov
Starea curentă Xt depinde doar de o istorie finită a stărilor anterioare
Procese Markov de ordin întâi: 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.htm
![Page 13: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/13.jpg)
13
Proces de decizie Markov
Starea iniţială S0
Modelul de tranziţii T(s, a, s’)
Funcţia recompensă R(s)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 14: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/14.jpg)
14
Definiţii
O soluţie la o astfel de problemă de căutare se numeşte politică
(engl. “policy”) şi se notează π Traduceri alternative pentru “policy”: tactică sau strategie
π(s) este acţiunea recomandată în starea s
Politica este o descriere a unui reflex
Politica este definită pentru toate stările: ce acţiune trebuie să facă agentul în orice stare s-ar afla
Se numeşte utilitate suma recompenselor pentru o secvenţă de stări Recompensa este câştigul pe termen scurt
Utilitatea este câştigul total pe termen lung
Mediu stohastic: utilitate aşteptată
Politica optimă π*: maximizează utilitatea aşteptată
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 15: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/15.jpg)
15
Exemple de politici
R(s) = recompensa în fiecare stare
neterminală
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 16: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/16.jpg)
16
Staţionaritate
Orizont finit
Uh([s0, s1, ..., sN+k]) = Uh([s0, s1, ..., sN])
După momentul N nu mai contează nimic
N = 3 trebuie să rişte (sus)
N = 100 poate alege soluţia mai sigură (stânga)
Politica optimă este nestaţionară
“history”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 17: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/17.jpg)
17
Staţionaritate
Orizont infinit
Politica optimă este staţionară
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.htm
![Page 18: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/18.jpg)
18
Evaluarea unui orizont infinit
Trebuie să ne asigurăm că utilitatea unei secvenţe posibil infinite este finită
Abordarea 1. Dacă recompensele sunt mărginite şi γ < 1 atunci:
Abordarea 2. Dacă mediul conţine stări 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.htm
![Page 19: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/19.jpg)
19
Evaluarea unei politici
Fiecare politică generează secvenţe multiple de stări, datorită incertitudinii tranziţiilor T(s, a, s’)
Valoarea unei politici π este valoarea aşteptată a
sumei tuturor recompenselor actualizate observate după toate secvenţele posibile de stări
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 20: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/20.jpg)
20
Iterarea valorilor
engl. “value iteration”
Algoritm pentru calcularea unei politici optime
Se calculează utilitatea fiecărei stări
În mod iterativ, se atribuie valorile corecte pentru utilităţi
Se folosesc utilităţile stărilor pentru selectarea unei acţiuni optime în fiecare stare
Se alege starea cu utilitatea cea mai mare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 21: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/21.jpg)
21
Utilităţile stărilor
Utilitatea unei stări s este utilitatea aşteptată a secvenţei de stări următoare
Secvenţa este determinată de π(s)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 22: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/22.jpg)
22
Exemplu
Fie g = 1 şi R(s) = –0.04
lângă scop utilităţile sunt mai mari pentru că este nevoie de mai puţini paşi cu recompensă negativă pentru atingerea stării respective
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 23: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/23.jpg)
23
Ecuaţia Bellman
Ecuaţia Bellman (1957)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 24: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/24.jpg)
24
Politica optimă
Utilitatea unei stări este recompensa imediată pentru acea stare plus utilitatea aşteptată maximă a stării următoare
Politica optimă alege acţiunea care conduce în starea cu cea mai mare utilitate aşteptată
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 25: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/25.jpg)
25
Exemplu
Se consideră rezultatele tuturor acţiunilor posibile pentru a selecta acţiunea cea mai bună şi a atribui utilitatea sa aşteptată următoarei stări din ecuaţia Bellman
Exemplu: utilitatea stării (1,1)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 26: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/26.jpg)
26
Rezolvarea unui proces de decizie Markov
n stări posibile
n ecuaţii Bellman (una pentru fiecare stare)
n ecuaţii cu n necunoscute: U(s)
Nu se poate rezolva ca sistem de ecuaţii liniare datorită funcţiei max
Trebuie rezolvat iterativ
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 27: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/27.jpg)
27
Algoritmul iterării valorilor
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 28: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/28.jpg)
28
Convergenţa c = ε / Rmax
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 29: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/29.jpg)
29
http://people.cs.ubc.ca/~poole/demos/mdp/vi.html
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 30: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/30.jpg)
30
Iterarea politicilor
engl. “policy iteration”
Dacă o acţiune este în mod evident mai bună decât toate celelalte, nu avem nevoie de valorile exacte ale utilităţilor
Algoritmul alternează 2 paşi:
Evaluarea politicii: calcularea utilităţilor tuturor stărilor
pe baza politicii πi
Îmbunătăţirea politicii: calcularea unei noi politici πi+1
pe baza utilităţilor Ui
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 31: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/31.jpg)
31
Evaluarea politicii
Sistem de n ecuaţii 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.htm
![Page 32: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/32.jpg)
32
Îmbunătăţirea politicii
Se cunosc toate U(s)
Se calculează pentru fiecare s:
Aceasta este acţiunea optimă ai*(s)
Dacă ai*(s) ≠ πi(s), se actualizează politica:
πi+1(s) = ai*(s)
Se pot actualiza doar părţile „promiţătoare” ale spaţiului de căutare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 33: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/33.jpg)
33
Algoritmul iterării politicilor
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 34: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/34.jpg)
34
Învăţarea cu întărire
1. Introducere
2. Procese de decizie Markov
3. Învăţarea pasivă 3.1. Estimarea directă a utilităţii
3.2. Programarea dinamică adaptivă
3.3. Învăţarea diferenţelor temporale
4. Învăţarea activă
5. Optimizări
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 35: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/35.jpg)
35
Învăţarea cu întărire
Proces de decizie Markov Mulţimea de stări S,
mulţimea de acţiuni A
Modelul de tranziţii T(s, a, s’) cunoscut
Funcţia recompensă R(s) cunoscută
Calculează o politică optimă
Învăţarea cu întărire Se bazează pe
procese de decizie Markov, dar:
Modelul de tranziţii este necunoscut
Funcţia recompensă este necunoscută
Învaţă o politică optimă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 36: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/36.jpg)
36
Exemple de aplicare
Medii complexe pentru care nu se pot stabili probabilităţile şi recompensele
Jocuri: spaţiu uriaş de stări
Se poate spune doar la sfârşit dacă recompensa este pozitivă (s-a câştigat) sau negativă (s-a pierdut)
Mediul fizic: roboţi, elicoptere
Recompense negative doar pentru deviere de la curs, clătinare, prăbuşire
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 37: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/37.jpg)
37
Tipuri de învăţare cu întărire
Pasivă sau activă
Pasivă: agentul execută o politică fixă şi o evaluează
Activă: agentul îşi actualizează politica pe măsură ce învaţă
Bazată pe model sau fără model
Bazată pe model: învaţă modelul de tranziţii şi recompense şi îl foloseşte pentru a descoperi politica optimă
Fără model: descoperă politica optimă fără a învăţa modelul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 38: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/38.jpg)
38
Învăţarea pasivă
Învăţarea pasivă este o modalitate de explorare a mediului De exemplu un robot cu scopul de a trece prin toate stările mediului
Evaluează cât de bună este o politică π
Învaţă utilitatea Uπ(s) a fiecărei stări
Abordare similară cu evaluarea politicii pentru PDM
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 39: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/39.jpg)
39
Învăţarea pasivă
Agentul execută o serie de încercări (engl. “trials”)
Politica este aceeaşi, dar mediul este nedeterminist
Scopul este să înveţe utilitatea aşteptată Uπ(s)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 40: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/40.jpg)
40
Estimarea directă a utilităţii
Exemplu – prima încercare produce:
în starea (1,1) recompensa totală 0.72
–0.04 · 7 + 1 = 0.72 (cu γ = 1)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 41: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/41.jpg)
41
Estimarea directă a utilităţii
Exemplu – prima încercare produce:
în starea (1,1) recompensa totală 0.72
în starea (1,2) două recompense totale 0.76 şi 0.84
în starea (1,3) două recompense totale 0.80 şi 0.88
Utilitatea unei stări este suma aşteptată a recompenselor de la acea stare înainte
Utilitatea estimată poate fi media valorilor eşantionate
U(1,1) = 0.72, U(1,2) = 0.80, U(1,3) = 0.84 etc.
Este o problemă de învăţare supervizată
Se creează un model U(S) ≈ f(S)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 42: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/42.jpg)
42
Estimarea directă a utilităţii
Utilitatea unei stări depinde de utilităţile stărilor succesoare (constrângerile date de ecuaţiile Bellman)
Estimarea directă a utilităţii ignoră această informaţie
Căutarea se face într-un spaţiu mult mai mare decât cel necesar de fapt
Convergenţa este foarte lentă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 43: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/43.jpg)
43
Programarea dinamică adaptivă
Se folosesc ecuaţiile Bellman
Trebuie estimate T(s, π(s), s’) şi R(s) din încercări Frecvenţele tranziţiilor şi mediile recompenselor
Probabilităţile şi recompensele învăţate se introduc în ecuaţiile Bellman
Se rezolvă sistemul de ecuaţii liniare cu necunoscutele Uπ(S)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 44: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/44.jpg)
44
Învăţare cu întărire pasivă cu PDA
t este o stare
având aproximările pentru
T, R şi π, se calculează
utilităţile ca la iterarea politicilor PDM, prin rezolvarea unui sistem de ecuaţii liniare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 45: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/45.jpg)
Exemplu
Acţiunea Right este executată de 3 ori în
starea (1,3) şi în 2 cazuri starea rezultantă este (2,3)
⇒ T((1,3), Right, (2,3)) = 2/3
45 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 46: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/46.jpg)
46
Convergenţa
agentul întâlneşte prima dată starea cu R = –1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 47: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/47.jpg)
47
Programarea dinamică adaptivă
PDA este un standard de comparare pentru alţi algoritmi de învăţare cu întărire
PDA este ineficient dacă spaţiul stărilor este mare
Sistem de ecuaţii liniare de ordin n
Jocul de table: 1050 ecuaţii cu 1050 necunoscute
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 48: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/48.jpg)
48
Învăţarea diferenţelor temporale
engl. “Temporal Differences”
Combină avantajele celor două abordări anterioare (estimarea directă a utilităţii şi programarea dinamică adaptivă)
Actualizează doar stările direct afectate
Satisface aproximativ ecuaţiile Bellman
Exemplu:
După prima încercare, U(1,3) = 0.84, U(2,3) = 0.92
Fie tranziţia (1,3) (2,3) în a doua încercare
Dacă ar fi deterministă, atunci U(1,3) = –0.04 + U(2,3) = 0.88
Însă tranziţiile sunt stohastice şi nu se cunoaşte modelul
Estimarea U(1,3) = 0.84 este mai mică şi trebuie mărită puţin
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 49: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/49.jpg)
49
Învăţarea diferenţelor temporale
Metoda diferenţelor temporale propune un compromis (ecuaţia DT):
DT aplică o serie de corecţii pentru a converge la ecuaţiile Bellman
Corecţia are loc proporţional cu probabilităţile
Actualizarea pentru s’ va avea loc în T(s, π(s), s’) din cazuri
Rata de învăţare α determină viteza de convergenţă la utilitatea
reală
Metoda DT nu are nevoie de model pentru a realiza actualizările
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 50: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/50.jpg)
50
Rata de învăţare
Dacă α este fix, atunci valoarea medie a lui Uπ(s) converge
la valoarea corectă
Dacă α descreşte pe măsură ce numărul de vizitări n ale
unei stări creşte, atunci chiar U(s) converge la valoarea corectă
Convergenţa este garantată dacă:
Funcţia α(n) = 1 / n satisface această condiţie
De multe ori se foloseşte funcţia α(n) = 1 / (1 + n) (0,1]
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 51: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/51.jpg)
51
Învăţare cu întărire pasivă cu DT
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 52: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/52.jpg)
52
Convergenţa
la PDA era aproximativ 100
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 53: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/53.jpg)
53
Discuţie
DT nu au nevoie de model, PDA este bazată pe model
DT actualizează succesorul observat şi nu toţi succesorii
Diferenţele scad pe măsură ce numărul de încercări creşte
DT converg mai lent, dar execută calcule mai simple
DT pot fi văzute ca o aproximare a PDA
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 54: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/54.jpg)
54
Euristici pentru PDA
Prin folosirea euristicilor, numărul de secvenţe de antrenare devine aproximativ egal pentru PDA şi PDA aproximativă, însă ultima efectuează calculele cu câteva ordine de magnitudine mai eficient
Mai ales la începutul învăţării, modelul oricum nu este cel corect, deci calculul exact al tuturor utilităţilor nu se justifică
Baleierea prioritară (engl. “prioritized sweeping”)
Se ajustează cu precădere stările ai căror succesori probabili tocmai au suferit o modificare mare a utilităţilor estimate
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 55: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/55.jpg)
55
Învăţarea cu întărire
1. Introducere
2. Procese de decizie Markov
3. Învăţarea pasivă
4. Învăţarea activă 4.1. Explorare şi exploatare
4.2. Algoritmul Q-Learning
5. Optimizări
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 56: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/56.jpg)
56
Învăţarea activă
Agentul pasiv învaţă utilităţile stărilor şi probabilităţile tranziţiilor şi alege acţiunile optime în mod greedy
Agentul activ îşi actualizează politica pe măsură ce învaţă
Scopul este să înveţe politica optimă pentru maximizarea utilităţii
Însă, la un moment dat, funcţia de utilitate nu este cunoscută decât aproximativ
Dilema agentului
Să îşi maximizeze utilitatea pe baza cunoştinţelor curente sau
Să încerce să îşi îmbunătăţească aceste cunoştinţe
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 57: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/57.jpg)
57
Exploatarea şi explorarea
Este necesar un compromis
Exploatarea
Agentul opreşte învăţarea şi execută acţiunile date de politică
Maximizarea recompenselor folosind estimările curente
Explorarea
Agentul învaţă încercând acţiuni noi
Maximizarea recompenselor pe termen lung
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 58: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/58.jpg)
58
Explorare sau exploatare?
Agentul trebuie să favorizeze:
Explorarea stărilor şi acţiunilor necunoscute sau
Exploatarea stărilor şi acţiunilor despre care ştie deja că îi aduc recompense mari
Soluţii pentru dilemă
Metoda ε-greedy
Alte metode GLIE (“greedy in the limit of infinite exploration”)
O metodă GLIE trebuie să încerce fiecare acţiune în fiecare stare de un număr nelimitat de ori
În final trebuie să devină greedy
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 59: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/59.jpg)
59
Metoda ε-greedy
Fie ε [0,1]
Acţiunea următoare selectată va fi:
O acţiune aleatorie cu probabilitatea ε
Acţiunea optimă cunoscută cu probabilitatea 1 – ε
Implementare
Iniţial ε = 1 (explorare pură)
Când se termină un episod de învăţare, ε scade, de exemplu cu 0.05 (creşte progresiv rata de exploatare)
ε nu scade niciodată sub un prag, de exemplu 0.1
Agentul are mereu o şansă de explorare, pentru a evita optimele locale
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 60: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/60.jpg)
60
Exploatarea şi explorarea
Exploatare pură
De obicei generează politici suboptime
Explorare pură
Învaţă modele din ce în ce mai bune, dar recompensele sunt mici
“n-armed bandit”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 61: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/61.jpg)
61
Metodă GLIE alternativă
Se acordă ponderi mai mari acţiunilor neîncercate frecvent Se acordă ponderi mai mici acţiunilor cu utilitate mică Se modifică ecuaţiile Bellman folosind utilităţile optimiste U+(s)
Funcţia de explorare f(u, n) Creşte cu utilitatea aşteptată u Scade cu numărul de încercări n
Exemplu:
Se încurajează acţiunile către regiuni neexplorate Oferă convergenţă mai bună şi politici aproape optime
numărul de aplicări ale acţiunii a în starea s
estimare optimistă a celei mai mari recompense care poate fi obţinută în orice stare
parametru fix
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 62: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/62.jpg)
62
Algoritmul Q-Learning
Algoritmul Q-Learning (Watkins, 1989) învaţă o funcţie acţiune-valoare Q(a,s)
Utilităţile
Ecuaţiile de constrângere la echilibru
Este o metodă DT fără model
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 63: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/63.jpg)
Algoritmul Q-Learning
63
Actualizările se fac de fiecare dată când acţiunea a aplicată în s duce în s’
Coeficientul de învăţare determină viteza
de actualizare a estimărilor
De obicei, (0,1)
Q-Learning este mai lent decât PDA
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 64: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/64.jpg)
64
Algoritmul Q-Learning
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 65: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/65.jpg)
65 http://people.cs.ubc.ca/~poole/demos/rl/q.html Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 66: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/66.jpg)
66
Învăţarea cu întărire
1. Introducere
2. Procese de decizie Markov
3. Învăţarea pasivă
4. Învăţarea activă
5. Optimizări
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 67: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/67.jpg)
67
Aproximarea funcţiilor
Problemele reale au spaţii foarte mari Jocul de table are aproximativ 1050 stări
Modelul este greu de memorat PDA memorează T(s, a, s’), N(a, s) DT, QL memorează U(s), respectiv Q(a, s)
Utilităţile se pot aproxima cu funcţii parametrice
fi sunt funcţii de bază Rezultă o compresie semnificativă (pentru table 1:1044)
Învăţarea modelului aproximativ ajută generalizarea Se pot aproxima utilităţile stărilor vizitate Se pot prezice utilităţile stărilor nevizitate
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 68: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/68.jpg)
68
Exemplu
Pentru problema prezentată cu 4 x 3 stări
utilitatea aproximată utilitatea observată eroarea
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 69: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/69.jpg)
69
Actualizarea parametrilor
parametrii se actualizează la fiecare pas / observaţie
schimbarea parametrilor la un moment dat modifică
toate utilităţile
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 70: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/70.jpg)
70
Alegerea funcţiei
Funcţia de aproximare liniară a utilităţilor trebuie să fie o funcţie liniară de parametri
Trăsăturile pot fi funcţii neliniare arbitrare de variabile de stare
Pentru exemplul anterior, se poate include un termen care să măsoare distanţa faţă de scop
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 71: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/71.jpg)
71
Învăţarea aproximărilor
Actualizările pentru DT
Actualizările pentru Q-learning
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 72: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/72.jpg)
72
Căutarea politicii
Reprezintă politica drept o funcţie parametrizată Actualizează parametrii până când politica se îmbunătăţeşte Reprezentare simplă:
Se ajustează θ pentru a se îmbunătăţi politica π este o funcţie neliniară de θ, discontinuă pentru acţiuni discrete
Actualizările pe baza gradienţilor nu sunt posibile
Reprezentarea stohastică a politicii (softmax):
Dă probabilităţi de acţiune Apropiată de varianta deterministă (max) dacă o acţiune este mult
mai bună decât alte acţiuni Politica devine o funcţie diferenţiabilă de θ
Politica diferenţiabilă poate fi optimizată cu metode bazate pe gradient sau cu metode empirice, de exemplu hill-climbing
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 73: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/73.jpg)
Funcţia softmax: exemplu
Q1 = 2, Q2 = 0, Q3 = 5, Q4 = 4
Abordarea deterministă:
max ⇒ Q3
Abordarea stohastică:
exp(Q1) = 7.4, exp(Q2) = 1, exp(Q3) = 148.4, exp(Q4) = 54.6
suma = 211.4
⇒ P(Q1) = 7.4 / 211.4 = 3.5%
Analog, P(Q2) = 0.5%, P(Q3) = 70.2%, P(Q4) = 25.8%
Dacă valoarea maximă este mult mai mare decât celelalte, probabilitatea sa se apropie de 1
73 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 74: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/74.jpg)
74
Aplicaţii
Dame – Arthur Samuel (1959, 1967)
TD-Gammon (joc de table) – Gerry Tesauro (1992)
Funcţia de evaluare: reţea neuronală cu 1 strat ascuns cu 40 de neuroni
După 300 000 de jocuri cu el însuşi, a atins performanţe de campion mondial din top 3
Alte jocuri: solitaire, şah
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 75: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/75.jpg)
75
Aplicaţii
Controlul pendulului inversat
Algoritmul Boxes – Michie & Chambers (1968)
În prezent: pendulul inversat triplu
În general probleme pentru care este dificilă determinarea apriori a unor reguli de rezolvare
Controlul roboţilor sau al altor echipamente
Stabilirea preţurilor, livrarea produselor
Listă de aplicaţii de succes
http://umichrl.pbworks.com/w/page/7597597/ Successes-of-Reinforcement-Learning
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 76: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/76.jpg)
76
Aplicaţii
Algoritmul Pegasus (Ng & Jordan, 2000): zbor autonom al unui elicopter
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 77: Inteligenta artificiala: Invatarea cu intarire](https://reader030.fdocumente.com/reader030/viewer/2022012309/5571f91e49795991698ed4f8/html5/thumbnails/77.jpg)
77
Concluzii
Învăţarea cu întărire este necesară pentru agenţii care evoluează în medii necunoscute
Învăţarea pasivă presupune evaluarea unei politici date
Învăţarea activă presupune învăţarea unei politici optime
Aproximarea funcţiilor este necesară pentru probleme cu spaţii mari de stări
În „lumea reală” există numeroase aplicaţii bazate pe învăţarea cu întărire
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm