Haskell: Învățare instrumentală

• Responsabil: Mihnea Muraru
• Deadline soft: 21.04.2016, apoi depunctare 0.5p/ zi
• Deadline hard: 26.04.2016 ora 23.59
• Data publicării: 07.04.2016
• Data ultimei modificări: 18.04.2016
• Tema se va încărca pe vmchecker
• Data tester-ului: în curând
• Forum temă

• (08.04, 15:20) A fost adăugată în schelet funcția updateEstimation, pentru o modularizare și testabilitate mai bune.
• (09.04, 10:10) A fost adăugată o precizare despre utilitățile stărilor terminale.
• (10.04, 13:50) A fost publicat tester-ul. Fișierul readme.txt conține instrucțiunile de utilizare.
• (13.04, 22:20) A fost adăugat subtestul randomPath.neighbors, care verifică faptul că două stări adiacente într-o cale sunt într-adevăr vecine în mediu.
• (18.04, 08:40) A fost adăugată o precizare pentru acordarea bonusului indus pe absența recursivității explicite.

• Utilizarea mecanismelor funcționale, de tipuri, și de evaluare leneșă din limbajul Haskell pentru rezolvarea unei probleme de învățare instrumentală.

Secțiunea prezintă câteva noțiuni de bază despre învățarea instrumentală și relevanța acesteia pentru tema de față.

Învățarea instrumentală (reinforcement learning), cunoscută și sub numele de învățare prin consecințe, sau învățare prin recompensă și pedeapsă, este un concept introdus inițial în psihologie, și desemnează modalitatea prin care organismele cu un anumit nivel de complexitate își adaptează comportamentul în vederea sporirii recompenselor (șoricelul care apasă butonul verde pentru a primi mâncare) și a diminuării pedepselor (același șoricel care nu mai apasă butonul roșu, pentru a evita șocul electric).

Conceptul a fost ulterior împrumutat în învățarea automată (machine learning, ramură a inteligenței artificiale), cea din urmă incluzând, pe lângă învățarea instrumentală, învățarea supervizată (supervised learning) și pe cea nesupervizată (unsupervised learning).

Una dintre caracteristicile învățării instrumentale o constituie faptul că înțelegerea de către organism a consecințelor acțiunilor sale presupune explorarea diverselor opțiuni comportamentale, în situații variate, și adesea de un număr suficient de mare de ori (trial-and-error search). O altă caracteristică este reprezentată de observarea întârziată a consecințelor unei secvențe de acțiuni efectuate, iar provocarea constă în identificarea corectă a contribuției fiecărei acțiuni la obținerea recompensei sau a pedepsei.

Tema, inspirată de Anastasio (2009), vizează inserarea unui agent într-un mediu bidimensional (vezi figura de mai jos), în care diversele poziții (stări) conțin recompense (numere pozitive) sau pedepse (numere negative). Deplasându-se aleator prin mediu, agentul va dobândi capacitatea de estimare a utilității (valorii) fiecărei stări, prin prisma consecințelor prezente pe care le presupune intrarea într-o stare oarecare, precum și a consecințelor ulterioare pe care agentul le poate experimenta în medie plecând din acea stare.

Fiecărei stări i se asociază o pereche (consecință prezentă, utilitate estimată). Agentul pornește întotdeauna din starea inițială 1. Stările terminale 8 și 12 conțin câte o pedeapsă, respectiv recompensă importante. În figura de mai sus, celelalte stări nu induc consecințe proprii, iar starea 6 este inaccesibilă. În figura de mai jos, sunt prezentate utilitățile exacte ale stărilor, rotunjite la două zecimale, determinate prin mijloace analitice (care nu constituie obiectul temei), presupunând probabilități egale de tranziție dintr-o stare în orice stare vecină.

Scopul temei îl constituie implementarea unui algoritm iterativ simplu de estimare a utilităților stărilor, bazat pe principiul diferențelor temporale (temporal-difference learning). Acesta afirmă că utilitatea estimată a unei stări mai timpurii ar trebui adaptată pentru a reflecta mai bine utilitatea estimată a unei stări mai târzii, care este mai apropiată temporal de o stare terminală, și, deci, mai precisă. Principiul va fi aplicat doar pentru stări vecine, pe baza tranzițiilor realizate aleator.

1. Se generează o cale aleatoare prin mediu, demarată în starea inițială, și încheiată într-una dintre stările terminale.
2. La fiecare tranziție de la o stare curentă la una vecină, se aplică următoarea actualizare a utilității stării curente:

$$V(s) \leftarrow V(s) + \alpha \left[ R(s) + V(s') - V(s) \right],$$ unde $s$ este starea curentă, $s'$ este starea vecină, spre care se realizează tranziția, $V(s)$ este valoarea sau utilitatea stării $s$, $R(s)$ este consecința (reinforcement) imediată, aferentă intrării în starea $s$, iar $\alpha$ este rata de învățare.

1. Procesul se repetă, și se oprește în funcție de gradul de rafinare dorit pentru estimarea utilităților.

Se observă că utilitatea stării curente, $V(s)$, este actualizată cu o cantitate proporțională cu diferența dintre, pe de o parte, ceea ce obține agentul în starea curentă, $R(s)$, și ceea ce poate obține în medie în viitor, $V(s')$, realizând tranziția către noua stare, și, pe de alta, valoarea actuală a stării curente. Rata de învățare, $\alpha$, determină sensibilitatea procesului de actualizare, iar diminuarea ei în timp conduce la îmbunătățirea estimărilor.

Pentru simplitate, se poate considera că utilitățile stărilor terminale corespund direct consecințelor intrării în acestea.

Vom exemplifica pe prima figură de mai sus, unde toate utilitățile stărilor neterminale sunt inițial 0, câțiva pași de aplicare algoritmului, utilizând câteva căi generate aleator, și evidențiind actualizările de utilitate la fiecare tranziție realizată.

Conform observației de la sfârșitul secțiunii anterioare, utilitățile stărilor terminale sunt $V(8) = R(8) = -1$, și $V(12) = R(12) = 1$.

Să începem cu generarea căii 1-2-3-4-8. La fiecare dintre tranzițiile 1-2, 2-3 și 3-4, având forma $s \rightarrow s'$, expresia $R(s) + V(s') - V(s)$ are valoarea 0 și, prin urmare, utilitățile stărilor 1, 2 și 3 rămân 0. În schimb, presupunând o rată de învățare $\alpha = 0.1$, tranziția 4-8 induce actualizarea $V(4) \leftarrow V(4) + \alpha \left[ R(4) + V(8) - V(4) \right] = 0 + 0.1 (-1) = -0.1$.

Să presupunem, de dragul exemplului, că a doua cale generată este identică cu prima. Tranzițiile 1-2 și 2-3 vor avea aceeași soartă ca mai sus. Tranziția 3-4 va conduce la actualizarea $V(3) \leftarrow V(3) + \alpha \left[ R(3) + V(4) - V(3) \right] = 0 + 0.1 (-0.1) = -0.01$. De asemenea, tranziția 4-8 va conduce la o nouă actualizare $V(4) \leftarrow V(4) + \alpha \left[ R(4) + V(8) - V(4) \right] = -0.1 + 0.1 (-0.9) = -0.19$.

Rezolvarea temei este structurată pe etapele de mai jos. Începeți prin a vă familiariza cu structura arhivei de resurse. Va fi de ajutor să parcurgeți indicațiile din enunț în paralel cu comentariile din surse.

Implementați tipurile de date și funcțiile din fișierul RL.hs, conform indicațiilor de acolo. Testele aferente se găsesc în fișierul RLTest.hs. În rezolvare, exploatați testele drept cazuri de utilizare a funcțiilor pe care le implementați.

Evaluarea leneșă va permite o rezolvare modulară, bazată pe fluxuri infinite.

Prima parte a temei presupune generarea unui flux infinit de căi aleatoare infinite . Soluția propusă de Haskell pentru scrierea de cod pur, fără efecte laterale, care să opereze cu numere aleatoare, implică utilizarea explicită a unor generatoare, trimise ca parametri sau întoarse din funcții. Pentru aceasta, veți utiliza funcții din modulul System.Random (vezi și exercițiile din Laboratorul 7).

Având în vedere că funcția randomPath, implementată de voi, trebuie să întoarcă și un generator, dar că, în același timp, calea construită trebuie să fie infinită — prin urmare, neputând fi întors generatorul obținut la „sfârșitul căii” — veți utiliza funcția split, care permite extragerea a două generatoare dintr-unul singur. Astfel, un generator poate fi utilizat pentru generarea căii infinite, în timp ce celălalt poate fi întors direct.

Pe baza unui flux infinit de căi finite, încheiate în stări terminale, se va obține un flux infinit de estimări rafinate succesiv ale valorilor stărilor. Prin urmare, estimarea de un anumit rang se va obține accesând elementul corespunzător din flux. De asemenea, pe baza unei estimări, se poate obține, pentru o stare oarecare, vecinul cu utilitatea maximă, precum și o întreagă cale construită pe acest principiu.

Spre exemplu, pornind de la utilitățile evidențiate în cea de-a doua figură, calea obținută prin alegerea vecinului „optim” la fiecare tranziție este 1-5-9-10-11-12.

În acest context, este posibil să se dovedească utilă îmbinarea concomitentă a comportamentelor specifice funcționalelor map și foldl (mapping cu propagare de acumulator). Acest lucru este realizat de funcționala mapAccumL. De exemplu, lista sumelor parțiale ale unei alte liste se poate obține prin:

> mapAccumL (\acc x -> let acc1 = acc + x in (acc1, acc1)) 0 [1 .. 5]
(15, [1, 3, 6, 10, 15])

Se constată că reducerea în timp a ratei de învățare îmbunătățește estimările realizate de algoritm. Prin urmare, apariția ratei de învățare $\alpha$ din formula de actualizare a utilității unei stări se înlocuiește cu $\alpha \sigma^{N(s)}$, unde $\sigma$ este factorul de scalare a ratei de învățare, iar $N(s)$ este numărul curent de vizitări ale stării $s$, ținând cont de toate căile parcurse până în prezent. Practic, cu cât o stare este vizitată mai des, cu atât rata efectivă de învățare pentru starea respectivă scade mai mult.

Prin urmare, se va defini fluxul infinit al ratelor de învățare scalate, și se va memora, pentru fiecare stare, numărul de vizitări ale acesteia, iar funcțiile implementate mai sus se vor modifica pentru a ține cont de aceste aspecte.

Se acordă 10p dacă implementarea nu utilizează recursivitate explicită, exploatând la maxim funcționalele și alte funcții de bibliotecă. Acest bonus se va acorda proporțional cu punctajul obținut pe cerințele standard.

Se acordă 10p dacă generarea și accesarea fluxului infinit al ratelor scalate de învățare se realizează eficient, ca aici, utilizând tehnici de memoizare, ca aici.

• Este indicată utilizarea funcționalelor. Folosirea adecvată a acestora sau nefolosirea acestora aduc modificări în punctajul temei (în limita a 1 punct).
• Încercați să exploatați la maxim bibliotecile Data.List și Data.Array.
• În arhiva temei includeți un fișier README cu detalii specifice implementării voastre, unde este cazul.

• Arhiva de pornire (Schelet și tester)

• Reinforcement learning, Wikipedia.
• Temporal-difference learning. Wikipedia.
• Anastasio, T. J. (2009). Tutorial on Neural Systems Modeling. Sinauer Associates, Inc.