= Haskell: Învățare instrumentală =

* Responsabil: [[mmihnea@gmail.com|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 **[[https://elf.cs.pub.ro/vmchecker/ui/#PP|vmchecker]]**
* Data tester-ului: în curând
* [[http://cs.curs.pub.ro/2015/mod/forum/view.php?id=5327|Forum temă]]

== Changelog ==

* (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.

== Obiective ==

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

== Descriere ==

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

=== Învățarea instrumentală ===

**Învățarea instrumentală** (//[[https://en.wikipedia.org/wiki/Reinforcement_learning|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ă** (//[[https://en.wikipedia.org/wiki/Supervised_learning|supervised learning]]//) și pe cea **nesupervizată** (//[[https://en.wikipedia.org/wiki/Unsupervised_learning|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.

=== Scopul temei ===

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.

|  9 (0/ 0)  |  10 (0/ 0)  |  11 (0/ 0)  |  **12 (<fc #00B000>+1/ +1</fc>)**  |
|  5 (0/ 0)  |  <fc #c0c0c0>6</fc>  |  7 (0/ 0)  |  **8 (<fc #ff0000>-1/ -1</fc>)**  |
|  **1** (0/ 0)  |  2 (0/ 0)  |  3 (0/ 0)  |  4 (0/ 0)  |

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ă.

|  9 (0/ <fc #ff0000>-0.04</fc>)  |  10 (0/ <fc #00B000>+0.09</fc>)  |  11 (0/ <fc #00B000>+0.22</fc>)  |  **12 (<fc #00B000>+1/ +1</fc>)**  |
|  5 (0/ <fc #ff0000>-0.16</fc>)  |  <fc #c0c0c0>6</fc>  |  7 (0/ <fc #ff0000>-0.44</fc>)  |  **8 (<fc #ff0000>-1/ -1</fc>)**  |
|  **1** (0/ <fc #ff0000>-0.29</fc>)  |  2 (0/ <fc #ff0000>-0.42</fc>)  |  3 (0/ <fc #ff0000>-0.54</fc>)  |  4 (0/ <fc #ff0000>-0.77</fc>)  |

Scopul temei îl constituie implementarea unui algoritm iterativ simplu de estimare a utilităților stărilor, bazat pe **principiul diferențelor temporale** (//[[https://en.wikipedia.org/wiki/Temporal_difference_learning|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.

=== Algoritmul, pe scurt ===

# Se generează **o cale aleatoare** prin mediu, demarată în starea inițială, și încheiată într-una dintre stările terminale.
# **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.
# 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.

=== Exemplu de aplicare a algoritmului ===

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$.
== Cerințe ==

Rezolvarea temei este structurată pe etapele de mai jos. Începeți prin a vă familiariza cu structura **arhivei** de [[#Resurse|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**.

=== Generarea căilor (30p) ===

Prima parte a temei presupune generarea unui flux infinit de căi aleatoare infinite 8-). 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 ''[[https://hackage.haskell.org/package/random-1.1/docs/System-Random.html|System.Random]]'' (vezi și exercițiile din [[:16:laboratoare:haskell:legarea-var-functionale|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 ''[[https://hackage.haskell.org/package/random-1.1/docs/System-Random.html#v:split|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.

=== Estimarea utilităților fără diminuarea ratei de învățare (40p) ===

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 ''[[https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html#v:mapAccumL|mapAccumL]]''. De exemplu, lista sumelor parțiale ale unei alte liste se poate obține prin:
<code haskell>
> mapAccumL (\acc x -> let acc1 = acc + x in (acc1, acc1)) 0 [1 .. 5]
(15, [1, 3, 6, 10, 15])
</code>
=== Estimarea utilităților cu diminuarea ratei de învățare (30p) ===

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.
=== Bonus (20p) ===

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 [[https://en.wikipedia.org/wiki/Exponentiation_by_squaring|aici]], utilizând tehnici de **memoizare**, ca [[http://stackoverflow.com/questions/3208258/memoization-in-haskell|aici]].
== Precizări ===

* 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** ''[[https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html|Data.List]]'' și ''[[https://hackage.haskell.org/package/array-0.5.1.0/docs/Data-Array.html|Data.Array]]''.
* În arhiva temei includeți un fișier **''README''** cu detalii specifice implementării voastre, unde este cazul.

== Resurse ==

* {{:16:teme:haskell.zip|Arhiva de pornire}} (Schelet și tester)

== Referințe ==

* //[[https://en.wikipedia.org/wiki/Reinforcement_learning|Reinforcement learning]]//, Wikipedia.
* //[[https://en.wikipedia.org/wiki/Temporal_difference_learning|Temporal-difference learning]]//. Wikipedia.
* Anastasio, T. J. (2009). //[[http://www.amazon.com/Tutorial-Neural-Systems-Modeling-Anastasio/dp/0878933395|Tutorial on Neural Systems Modeling]]//. Sinauer Associates, Inc.