Inteligenţa Artificială studiază entităţile inteligente

Învăţarea pasivă într-un mediu necunoscut:

În secţiunea precedentă m-am ocupat de cazul în care modelul de mediu M este cunoscut.

Într-un mediu necunoscut agentul descoperă singur mediu prin intermediul percepţiilor provenite de la acesta şi prin observarea rezultatului acţiunilor sale asupra mediului. Modelul de mediu este acum învăţat din observarea directă a tranziţiilor dintr-o stare în alta. Într-un mediu accesibil fiecare percepţie identifică o stare şi fiecare tranziţie furnizează un exemplu de intrare / ieşire pentru funcţia de tranziţie reprezentată de M. Funcţia de tranziţie este de obicei stochastică, adică specifică o probabilitate pentru fiecare posibil succesor.

3. Învăţarea activă într-un mediu necunoscut:

Un agent care învaţă pasiv poate fi înţeles ca având o politică fixă, şi nu contează foarte mult acţiunile sale (deoarece în mare parte acestea sunt de observare a mediului). Spre deosebire de agentul pasiv, agentul activ trebuie să acorde atenţie acţiunilor sale şi mai ales trebuie să fie atent la rezultatul acestor acţiuni, deoarece de acest rezultat depinde recompensa primită.

Modelul de agent pasiv prezentat în figura 3.2.1.c) are nevoie de câteva modificări pentru a se transforma într-un agent activ:

• 
  Modelul de mediu trebuie acum să încorporeze probabilităţile de tranziţie la alte stări, dacă se face o acţiune particulară. Voi folosi M^a_{i, j} pentru a specifica probabilitatea de a ajunge din starea i în starea j efectuând acţiunea a.
  
• 
  Condiţiile asupra utilităţii fiecărei stări trebuie modificate deoarece agentul poate acum să aleagă o anumită acţiune. Un agent raţional va încerca să maximizeze utilitatea. Ecuaţia ce se va folosi este:
  

U(i) = R(i) + max_aM^a_{i, j} U(j)

• 
  agentul trebuie acum să aleagă o acţiune la fiecare pas, şi va avea nevoie de elementul de performanţă pentru aceasta. În algoritm aceasta înseamnă apelul procedurii ElementulDePerformanţă(e) şi returnarea acţiunii alese.
  

Nu ne rămâne de făcut decât să vedem ce acţiune trebuie să aleagă agentul activ, cu alte cuvinte ce acţiune trebuie să returneze funcţia ElementulDePerformanţă. S-ar putea presupune că agentul trebuie să aleagă la fiecare pas acţiunea care îi maximizează funcţia de utilitate, dar o acţiune considerată foarte bună la un moment dat s-ar putea dovedi a nu fi la fel de profitabilă ca o altă acţiune, cu o valoare a utilităţii mai mică, dar care conduce la un rezultat mai bun. Trebuie ţinut seama de faptul că acţiunile au două tipuri de rezultate:

• 
  primirea unei recompense pentru secvenţa curentă
  
• 
  afectează percepţiile primite şi, prin urmare, capacitatea agentului de a învăţa şi primi recompense în secvenţele viitoare.
  

De aceea un agent trebuie să “se gândească" şi să aleagă între o acţiune cu o recompensă pozitivă imediată sau o acţiune care nu pare atât de profitabilă în momentul de faţă, dar pe termen lung dă rezultate mai bune. Un agent care alege tot timpul acţiunea care pare cea mai bună (cea cu funcţia de utilitate cea mai mare) ar putea să se blocheze la un moment dat. Pe de altă parte dacă agentul îşi îmbunătăţeşte cunoştinţele fără a le pune în practică învăţarea nu are rost. În viaţa reală agentul trebuie să decidă dacă să continue o existenţă confortabilă, sau să pătrundă în necunoscut în speranţa descoperirii unei vieţi mai bune.

După cum am mai spus în secţiunea 3.1.1 există două posibilităţi de abordare a acestei probleme:

• 
  abordarea non – greedy - se acţionează aleator în speranţa că eventual se va explora în întregime mediul
  
• 
  abordarea greedy - se alege tot timpul acţiunea care maximizează funcţia de utilitate
  

Folosind abordarea non - greedy agentul reuşeşte să înveţe utilităţile pentru stările, dar, din păcate politica aceasta nu îl conduce la stările pentru care recompensa finală e pozitivă. Agentul care foloseşte abordarea greedy găseşte o cale spre recompensa pozitivă (+1) pe ruta de jos - prin (2,1), (3,1), (3,2) şi (3,3) din exemplu de la secţiunea 3.3.1. Din nefericire, după ce a găsit această cale nu mai explorează pentru a învăţa utilităţile celorlalte stări. Acest lucru înseamnă eşec în atingerea perfecţiunii deoarece nu găseşte drumul optim – prin (1,2), (1,3) şi (2,3). Evident avem nevoie de o abordare care să fie între abordarea non - greedy şi ce greedy . Agentul ar trebui să folosească abordarea non - greedy când ştie puţin despre mediu şi abordarea greedy când se află într-un mediu bun.

4. Diferenţa Temporală:

O idee centrală a învăţării prin întărire se numeşte Diferenţa Temporală(TD). Metodele TD sunt în general algoritmi de învăţare pentru a face predicţii pe termen lung despre sistemele dinamice. Sunt bazate pe funcţii de estimare, funcţii de stare V(s) ori perechi acţiune - stare Q(s, a) care estimează cât de bine este, pentru un sistem care învaţă, să fie într-o stare dată sau să facă o anumită acţiune într-o stare data. Asemenea valori ghidează mecanismul de selecţie al acţiunilor si permit sistemului sa-si atingă scopul. Să presupunem că observăm o tranziţie de la starea i la starea j, când U(i) = - 0.5 şi U(j) = + 0.5. Aceasta sugerează că ar trebui mărită valoarea lui U(i) pentru a se potrivi mai bine cu valoarea succesorului său. Acest lucru poate fi atins folosind următoarea regulă de reactualizare:

U(i) = U(i) + a (R(i) + U(j) – U(i)) 3.3.4.b

unde a este parametrul numit rata învăţării. Deoarece această regulă de reactualizare foloseşte diferenţele dintre utilităţile stărilor succesive se mai numeşte ecuaţia diferenţelor temporale.

Ideea de bază a tuturor metodelor de Diferenţa Temporală este în primul rând definirea condiţiilor locale când estimările sunt corecte, iar apoi să scrie o ecuaţie de reactualizare care translatează estimările către “ecuaţia de echilibru”:

U(i) = R(i) + M_{i, j}U(j) 3.2.4.a

În cazul învăţării pasive ecuaţia de echilibru este dată de ecuaţia 3.2.4.a. Acum ecuaţia 3.2.4.b constrânge agentul să atingă echilibrul dat de ecuaţia 3.2.4.a. Trebuie remarcat că actualizarea implică doar succesorul stării curente, pe când condiţiile de echilibru implică toate posibilele stări următoare. S-ar putea crede că această reactualizare cauzează o schimbare mare a valorii lui U(i) când apare o tranziţie rară, dar de fapt, deoarece tranziţiile rare sunt foarte puţin întâlnite, media valorilor lui U(i) va converge la valoarea corectă. Mai departe, dacă modificăm valoarea parametrului a dintr-un parametru fix într-o funcţie care descreşte de câte ori o stare a fost atinsă atunci U(i) va converge spre valoarea corectă.(Dayan 1992) Algoritmul Reactualizeată_TD este descris în figura 3.2.4.

function Reactualizează_TD(U, e, percepţii, M, N) returns tabelul de utilităţi U
if Terminală(e) then

U[Stare[e]] := Media_Execuţiei(U[Stare[e]], Recompensa[e], N[Stare[e]])

else if percepţii conţine mai mult de un element then

e¹ := penultimul element din percepţii

i := Stare[e¹]

j := Stare[e]

U[i] := U[i] + a(N[i])(Recompensa[e¹] + U[j] - U[i])



Fig.3.2.4 Un algoritm pentru reactualizarea utilităţilor

folosind diferenţe temporale

3. Învăţarea pe baza unei funcţii acţiune – valoare:

O funcţie acţiune - valoare atribuie o utilitate fiecărei acţiuni alese dintr-o stare dată. Asemenea valori se mai numesc Q – valori. Voi folosi notaţia Q(a, i) pentru a specifica valoarea obţinută prin alegerea acţiunii a din starea i. Q- valorile sunt direct legare de funcţiile de utilitate prin următoarea ecuaţie:

U(i) = max Q(a, i) 3.3.a

<sup>a

Q – valorile joacă un rol foarte important în învăţarea prin întărire din următoarele două motive:</sup>

• 
  ^{acţiunile sunt suficiente pentru luarea unei decizii fără a mai avea nevoie de un model}
  
• 
  ^{pot fi învăţate direct din recompensele primite}
  

<sup>Ca şi la funcţiile de utilitate putem scrie o ecuaţie care menţine echilibrul când

Q – valorile sunt corecte:


Ma_{i, j} max Q(a1, i) 3.3.b

a1

Q(a, i) = R(i) +

Voi nota cu Q*(a) valoarea reală a acţiunii a şi cu Q(a) valoarea estimată a acţiunii a la momentul t. Prin valoarea reală a acţiunii a înţeleg recompensa primită după efectuarea acţiunii a. Un mod de a calcula pe Q(a) este media recompenselor primite când acţiunea a a fost selectată. Cu alte cuvinte, dacă la momentul t al jocului a fost aleasă acţiunea a de k ori cu recompensele r</sup>₁^{, r}₂^{, …, r}_k^{, valoarea estimată este:
Q(a) = (r}₁ ^{+ r}₂ ^{+ … +r}_k^{) / k
Dacă k = 0 definesc Q(a) = 0, iar dacă k  atunci Q(a) converge la Q*(a).Această metodă se numeşte metoda eşantionul – medie. Una dintre cele mai simple metode este metoda greedy. Pentru această metodă (bazată pe alegerea acţiunii cu valoarea maximă) regula de selectare a acţiunii este:}

Q^*(a) = max Q(a)

a

4. Metodele Monte Carlo:

Este o metodă de învăţare pentru estimarea valorilor funcţiilor şi pentru descoperirea tacticilor optime. În cadrul acestor metode mediul nu este complet cunoscut. La aceste metode este necesară doar experienţa – exemple de stări, acţiuni şi recompense primite prin interacţiunile cu mediul. Învăţarea folosind experienţa este surprinzătoare deoarece nu necesită o cunoaştere prior a dinamicii mediului şi totuşi agentul are un comportament optimal. Deşi este necesar un model de mediu, modelul trebuie doar să genereze exemple de tranziţii, nu şi distribuţia probabilităţilor tuturor tranziţiilor posibile care este cerută de alte metode de învăţare (cum ar fi programarea dinamică).

Voi defini metodele Monte Carlo numai pentru cerinţe episodice. Acest lucru înseamnă că presupun că experienţa este împărţită pe episoade, iar toate episoadele se încheie indiferent de acţiunea selectată. Termenul “Monte Carlo” este des folosit pentru orice metodă de estimare a cărei operaţiuni implică componente semnificativ aleatoare.

Dacă nu avem un model, atunci este util să examinăm valorile acţiunilor în locul valorilor stărilor. Când avem un model valorile stărilor sunt suficiente pentru a determina tactica pe care trebuie să o aplice agentul; printr-o simplă privire la pasul următor şi alegerea acţiunii care conduce la cea mai bună combinaţie de recompense şi la cea mai bună stare. Fără un model de mediu numai valorile stărilor nu sunt suficiente. Trebuie estimată valoarea fiecărei acţiuni pentru ca valorile să fie utile pentru stabilirea unei tactici. De aceea unul dintre scopurile principale ale metodelor Monte Carlo este estimarea funcţiei Q^*. Pentru aceasta avem nevoie să estimăm mai întâi funcţia Q^ (s, a), recompensa aşteptată când se efectuează acţiunea a din starea s urmând tactica . Problema care apare este că multe dintre perechile acţiune stare ar putea să nu fie niciodată vizitate. Dacă  este o tactică deterministică, atunci urmând această politică vom observa ieşiri numai pentru o acţiune din fiecare stare. Astfel nu se estimează celelalte acţiuni care s-ar putea alege din stare s şi astfel experienţa nu este îmbunătăţită. Scopul învăţării funcţiilor acţiune – stare este de a ajuta alegerea unei acţiuni dintre acţiunile posibile din fiecare stare. Pentru a putea compara alternativele trebuie să putem estima valorile tuturor acţiunilor posibile din fiecare stare.

Aceasta este problema generală a menţinerii explorării. Trebuie să asigurăm explorarea continuă. Un mijloc de a face acest lucru este specificând că primul pas din fiecare episod începe cu o pereche acţiune – stare, iar fiecare astfel de pereche are o probabilitate nenulă de a fi aleasă ca start. Aceasta garantează că toate perechile acţiune – stare vor fi vizitate de un număr mare de ori. Această presupunere se numeşte explorarea startului. Această abordare este utilă, dar nu poate fi aplicată când învăţarea are loc direct din interacţiunea reală a agentului cu mediul. Cele mai întâlnite abordări pentru a ne asigura că toate perechile acţiune – stare sunt vizitate este de a considera că tacticile folosite sunt stohastice cu o probabilitate diferită de zero de a selecta toate acţiunile. Sunt două posibilităţi de realizare a acestui lucru: metodele on – line şi metodele off – line. Prima categorie de metode încearcă să evalueze sau să îmbunătăţească tactica folosită pentru luarea deciziilor. În această categorie intră tacticile soft adică cele pentru care

(s, a)  0 pentru s  S şi pentru a  A(s).

5. Mecanisme de selecţie:

1. Metodele greedy şi  - greedy:

Unul dintre cele mai simple mecanisme de acţiune –selecţie este mecanismul greedy şi extensia sa  - greedy, descris în figura 3.5.1. Acest mecanism acţionează astfel:

• 
  Alege acţiunea care are valoarea Q(s, a) maximă cu probabilitatea l-epsilon, dacă această acţiune există
  

• 
  Altfel, alege o acţiune aleatoare
  

În Figura 3.5.1. se compară o metodă greedy cu două metode  - greedy ( = 0.01 şi  = 0.1). Ambele metode folosesc estimările acţiune - valoare.

Fig. 3.5.1. Compararea metodei greedy cu  - greedy
Primul grafic arată creşterea recompensei ce se aşteaptă odată cu obţinerea experienţei. Metodele greedy îmbunătăţesc procesul de învăţare mai repede ca alte metode, dar acest lucru se produce doar la început, apoi rămân constante. Pe termen lung metoda greedy nu mai dă rezultate atât de bune datorită faptului că ia in considerare acţiuni suboptimale. Al doilea grafic arată că metoda greedy găseşte acţiunea optimală numai pentru aproximativ o treime din încercări. Metodele  - greedy acţionează mai bine deoarece continuă să exploreze şi continuă să-şi îmbunătăţească şansele de a recunoaşte acţiunile optimale. Metoda  = 0.1 găseşte acţiunea optimală destul de repede dar o selectează în mai puţin de 90% din cazuri. Metoda  = 0.01 găseşte acţiunea optimală mai

încet dar acţionează mai bine. Avantajele oferite de metodele  - greedy depind de problemă.