Sinteze de inteligenta artificiala 9786066874298 [PDF]

Zitiervorschau

Cuprins Inteligență artificială generală 1. Introducere în inteligența artificială .........................................................5 2. Metode de căutare a căilor ............................................................................7 3. Jocuri .................................................................................................................. 10 4. Probleme de satisfacere a constrângerilor .......................................... 13 5. Metode de optimizare .................................................................................. 14 6. Reprezentarea cunoașterii......................................................................... 24 7. Metode de inferență în logica propozițională și predicativă ........ 30 8. Logica vagă (fuzzy)........................................................................................ 36 9. Rețele bayesiene ............................................................................................ 48 10. Metode de planificare ................................................................................ 52

Învățare automată 11. Algoritmi de clasificare ............................................................................. 58 12. Clasificarea bazată pe ansambluri ........................................................ 66 13. Generalizarea................................................................................................ 71 14. Selecția trăsăturilor ................................................................................... 73 15. Regresia liniară, logistică, softmax ....................................................... 76 16. Rețele neuronale ......................................................................................... 83 17. Mașini cu vectori suport ........................................................................... 88 18. Rețele neuronale profunde ..................................................................... 95 19. Modele bazate pe energie ..................................................................... 102 20. Vectori de cuvinte (word embeddings) ............................................ 112 21. Algoritmi de grupare (clustering)...................................................... 115 22. Rețele cu auto-organizare .................................................................... 124

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

23. Învățarea cu întărire ............................................................................... 128 24. Învățarea cu întărire profundă ........................................................... 141

Sisteme multi-agent 25. Agenți și sisteme multi-agent .............................................................. 146 26. Complexitate și emergență................................................................... 148 27. Arhitecturi de agenți............................................................................... 152 28. Comunicarea inter-agent ...................................................................... 156 29. Algoritmi de căutare a căilor pentru sisteme multi-agent ....... 159 30. Teoria jocurilor ......................................................................................... 166 31. Protocoale pentru licitații ..................................................................... 179 32. Protocoale de votare............................................................................... 182 33. Protocoale de negociere ........................................................................ 186 34. Proiectarea mecanismelor ................................................................... 191 35. Protocolul rețelelor de contracte (contract net protocol) ........ 192 36. Metode de coordonare ........................................................................... 195 37. Învățarea în sisteme multi-agent ....................................................... 198 Referințe .................................................................................................................... 201

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

1. Introducere în inteligența artificială Inteligența artificială este știința de a construi mașini care să facă lucruri ce ar necesita inteligență dacă ar fi făcute de oameni. Inteligența este mai greu de definit, fiind un termen generic pentru multe capacități înrudite: capacitatea de a raționa, a planifica, a rezolva probleme, a gândi abstract, a înțelege idei complexe, a învăța repede și a învăța din experiență. Inteligența este o măsură a capacității de a atinge scopuri (de a rezolva probleme) într-un mediu complex și dinamic. Există patru direcții de abordare a inteligenței artificiale: 





A acționa omenește: De exemplu, testată cu testul Turing. Un arbitru, om, se angajează într-o conversație în limbaj natural cu alți doi participanți la experiment, unul om și altul mașină. Dacă arbitrul nu poate spune cu siguranță cine este omul și cine este mașina, aceasta se spune că a trecut testul. Contraexemplu: camera chinezească a lui Searle. Un om folosește mulțimea de reguli ale unui calculator care trece testul Turing pentru a răspunde la întrebări în limba chineză. Omul nu cunoaște această limbă. Un program care manipulează simboluri, chiar dacă se comportă inteligent, nu înțelege, nu are stări mentale și intenții; A gândi omenește: Construirea de sisteme care funcționează intern în mod similar cu mintea omenească, nu doar să rezolve probleme, ci să le rezolve în același mod ca oamenii. Se folosesc, de exemplu, rezultate din științele cognitive. O teorie este că mintea este o colecție de agenți care reprezintă procese diferite, posibil concurente; A gândi rațional: Folosirea reprezentărilor logice, cu avantajele formalizării și puterii de raționament. Dificultățile sunt reprezentarea cunoștințelor nesigure sau informale și învățarea din date afectate de zgomot; 5

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



A acționa rațional: A descoperi acțiunea optimă, care aduce utilitatea maximă, indiferent de natura prelucărilor interne. Acțiunile raționale sunt studiate de majoritatea cercetărilor actuale, deoarece comportamentul este observabil și mai ușor de testat științific decât gândirea, iar raționalitatea este clar definită.

Pentru a crea inteligența artificială generală, există o serie de direcții potențiale care ar trebui agregate într-un mecanism unitar:     

Metode conexioniste (rețele profunde); Metode simbolice (metode logice, ontologii); Metode probabilistice (rețele bayesiene); Metode evolutive (algoritmi genetici/evolutivi); Metode de analogie (învățare prin transfer).

6

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Metode de căutare a căilor 1. Metode de căutare neinformată Căutarea limitată în adâncime presupune o căutare în adâncime cu limitare la k niveluri. Sub această adâncime, nodurile nu mai sunt expandate. Căutarea iterativă în adâncime realizează succesiv căutări limitate în adâncime pentru k = 0, 1, 2, … până se găsește o soluție. Căutarea iterativă în adâncime combină avantajele căutărilor în lățime și adâncime: este completă și optimă, iar în cazul cel mai defavorabil, complexitatea de timp este O(bd), comparabilă cu a căutării în lățime, puțin mai lentă din cauza repetițiilor, iar complexitatea de spațiu este O(b ∙ d), foarte bună, comparabilă cu a căutării în adâncime. Căutarea bidirecţională în lăţime are complexitate mult mai bună decât căutarea în lățime: O(bd/2) ≪ O(bd), însă operatorii din căutarea înapoi pot fi mai dificil de identificat decât în căutarea înainte. Căutarea de cost uniform ordonează frontiera în funcție de distanța nodurilor față de starea inițială, dată de funcția g. Este utilizată pentru grafuri ponderate, în care muchiile pot avea costuri diferite.

2. Metode de căutare informată (euristice) O euristică este o metodă care furnizează rapid o soluție, nu neapărat optimă. Este o metodă aproximativă, spre deosebire de un algoritm exact optim. Deși nu garantează găsirea soluției optime, metodele euristice găsesc de obicei o soluție acceptabilă, deseori chiar soluția optimă. Metodele euristice de căutare utilizează cunoștințe specifice fiecărei probleme pentru a ordona nodurile, astfel încât cele mai „promițătoare” noduri sunt plasate la începutul frontierei.

7

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Funcții utilizate în general:   

f(n) este un cost estimat. Cu cât este mai mic f(n), cu atât este mai bun nodul n; g(n) este costul căii de la nodul inițial la n. Este cunoscută; h(n) este estimarea costului căii de la n la un nod scop. Este o estimare euristică. Tipuri de căutare:

  

Căutarea de cost uniform (neinformată): f(n) = g(n); Căutarea greedy: f(n) = h(n); Căutarea A*: f(n) = g(n) + h(n). Reunește ideile căutărilor de cost uniform și greedy.

Pentru a garanta găsirea soluției optime, funcția h trebuie să fie admisibilă: niciodată mai mare decât costul real. Pentru metodele euristice de căutare, problema principală este găsirea celei mai bune funcții h, care să dea estimări cât mai apropiate de realitate. Cu cât h este mai bună, numărul de noduri expandate este mai mic. Algoritmul A* folosește două liste: Open (frontiera) și Closed (nodurile deja vizitate). Într-o iterație, se preia primul nod din lista Open (cu cel mai mic f ). Dacă starea acestui nod este o stare scop, căutarea se termină cu succes. Altfel, nodul se expandează. Pentru fiecare succesor, se calculează f = g + h. Succesorul se ignoră dacă în listele Open și Closed există un nod cu aceeași stare, dar cu g mai mic. Altfel, se introduce succesorul în lista Open. Nodul curent (care a fost expandat) se introduce în lista Closed, iar dacă acolo există deja un nod cu aceeași stare, acesta este înlocuit. Dacă lista Open devine vidă, nu există soluție. O funcție euristică h este monotonă sau consistentă dacă respectă inegalitatea în triunghi. O euristică monotonă devine din ce în ce mai precisă cu cât înaintează în adâncimea arborelui de căutare. În multe cazuri (dar nu întotdeauna), monotonia euristicii accelerează găsirea soluției.

8

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Ecuația pathmax face ca valorile lui f să fie monoton nedescrescătoare pe căile traversate din arborele de căutare: la generarea unui nod fiu c al lui p: f(c) = max( f(p), g(c) + h(c) ). Algoritmul A* este complet și optim dacă nodurile care revizitează stările nu sunt eliminate. A* este optim eficient: niciun alt algoritm de același tip nu garantează expandarea unui număr mai mic de noduri, dar doar dacă euristica este monotonă. Căutarea iterativă în adâncime A* are un principiu similar cu acela al căutării iterative neinformate în adâncime. În loc de niveluri în arbore, folosește contururi de cost ale funcției f. Crearea de funcții euristice nu este dificilă. O euristică admisibilă poate fi văzută drept costul soluției optime a unei probleme relaxate, prin eliminarea constrângerilor.

9

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Jocuri Algoritmul minimax presupune căutarea mutării optime a calculatorului într-un arbore, în care nodurile sunt configurații ale tablei, iar ramurile sunt mutările posibile. Se presupune că jocul este de sumă nulă, deci se poate folosi o singură funcție de evaluare pentru ambii jucători. Dacă f(n) > 0, poziția n este bună pentru calculator și rea pentru om, iar dacă f(n) < 0, poziția n este rea pentru calculator și bună pentru om. Funcția de evaluare este stabilită de proiectantul aplicației. Pentru aplicarea algoritmului, se selectează o limită de adâncime și o funcție de evaluare. Se construiește arborele până la limita de adâncime. Se calculează funcția de evaluare pentru frunze şi se propagă evaluarea în sus, selectând minimele pe nivelul minimizant (decizia omului) și maximele pe nivelul maximizant (decizia calculatorului).

Retezarea alfa-beta este o optimizare a algoritmului minimax, care întrețese generarea arborelui cu propagarea valorilor. Unele valori obținute în arbore furnizează informații privind redundanța altor părți, care nu mai trebuie generate. În acest caz, se generează arborele în adâncime, de la stânga la dreapta și se propagă valorile finale ale nodurilor ca estimări inițiale pentru părinții lor. Valoarea din nodurile de pe un nivel maximizant este valoarea alfa, iar cea de pe un nivel minimizant este valoarea beta. De fiecare dată când alfa ≥ beta, se oprește generarea nodurilor descendente. 10

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

În cazul cel mai favorabil, retezarea alfa-beta are complexitatea O(b ), deci poate căuta pe o adâncime de două ori mai mare decât minimax. d/2

Pentru jocuri nedeterministe, se folosesc valori așteptate pentru nodurile-șansă, adică suma valorilor posibile înmulțite cu probabilitățile de apariție ale acestora. Căutarea pe arbori Monte Carlo (Monte Carlo Tree Search, MCTS) este o metodă stohastică de căutare a soluțiilor în jocuri cu factori mari de ramificare. Fiecare nod reține numărul de victorii și numărul de jocuri în care s-a trecut prin el. În prima fază, începând din rădăcină, se selectează în mod repetat acțiunea (nodul fiu) i care maximizează următoarea expresie:

wi 2 ln n  ni ni unde: wi este numărul de victorii în fiul i, ni este numărul de simulări în fiul i, iar n este numărul de simulări în nodul curent. Când nu se mai poate aplica selecția, urmează faza de expandare, în care este selectat în mod aleatoriu un nod fiu încă nevizitat și i se adaugă o nouă înregistrare de statistici (inițial 0/0). Începe apoi simularea Monte Carlo, în care se aleg mutări în mod aleatoriu până se ajunge într-o stare terminală (de exemplu, 11

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

victorie sau înfrângere). După terminarea simulării, pentru toate pozițiile vizitate se incrementează numărul de jocuri și, dacă e cazul, numărul de victorii. După aplicarea algoritmului (în mod repetat), se alege mutarea cu cel mai mare număr de vizite ni, deoarece valoarea sa este cel mai bine estimată.

12

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

4. Probleme de satisfacere a constrângerilor Algoritmul backtracking face o căutare în adâncime, atribuind variabilelor, în ordine, valori din domeniile corespunzătoare, până ajunge la o atribuire completă și consistentă. Ordinea de alegere a variabilelor și valorilor poate accelera găsirea unei soluții prin detectarea eșecului mai devreme. Euristici de optimizare: 

 

Cea mai constrângătoare variabilă: se alege variabila cu cele mai multe constrângeri asupra variabilelor rămase; este utilă pentru decizii în caz de egalitate, de exemplu, în starea inițială; Cea mai constrânsă variabilă (euristica celor mai puține valori rămase): se alege variabila cu cele mai puține valori permise; Cea mai puțin constrângătoare valoare: pentru o variabilă, se alege valoarea care elimină cele mai puține valori în variabilele rămase.

Algoritmul de verificare înainte (forward checking). La început, pentru fiecare variabilă se memorează mulțimea curentă de valori permise. Când se atribuie o valoare în procesul de căutare, se actualizează mulțimile de valori permise pentru toate variabilele. Dacă o mulțime devine vidă, se revine pe nivelul anterior (se face backtracking). Algoritmul Min-Conflicts este o metodă de căutare locală. Pornește cu o atribuire aleatorie completă, dar posibil inconsistentă. În fiecare iterație, alege o variabilă cu conflicte și îi atribuie valoarea care îi minimizează numărul de conflicte.

13

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

5. Metode de optimizare Optimizarea înseamnă determinarea valorii minime sau maxime a unei funcții. Considerăm aici noțiunea de funcție în accepțiunea cea mai generală: de la o funcție simplă cu valori reale, la un algoritm complex care exprimă o problemă combinatorică. Scopul este de a determina argumentele funcției care determină valoarea sa minimă sau maximă.

1. Algoritmii evolutivi Un algoritm evolutiv este o metodă de căutare prin analogie cu selecția naturală biologică. Un algoritm evolutiv are o populație de soluții potențiale care evoluează prin aplicarea iterativă a unor operatori stohastici. Evoluția soluțiilor mai bune se realizează pe baza presiunii evolutive, adică favorizarea soluțiilor mai adaptate.

Funcția de adaptare (sau de fitness) definește problema. Ea spune cât de bună este o soluție, cât de adaptat este un cromozom. 14

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Selecția alege un părinte (cromozom) pentru noua generație, pe baza funcției de adaptare. Selecția acționează la nivel de individ și este independentă de reprezentare, adică nu depinde de codare, ci doar de funcția de adaptare. Tipuri de selecție: 







Ruletă (roulette-wheel): Se atribuie fiecărui individ o parte a ruletei, proporțională cu valoarea funcției sale de adaptare. Se „învârte” ruleta de n ori pentru a se alege n părinți; Bazată pe ranguri (rank-based): Indivizii sunt numerotați în ordinea crescătoare a fitness-ului. Probabilitatea de selecție este proporțională cu rangul unui individ în populație; Eșantionare universală stohastică (stochastic universal sampling): Asemănătoare cu selecția prin ruletă, dar nu alege părinții prin eșantionări repetate, ci utilizează o singură valoare aleatorie pentru alegerea tuturor părinților, la intervale echidistante; Competiție (tournament): Se aleg aleatoriu k indivizi din populație și se determină cel mai adaptat dintre aceștia. Se repetă procedura pentru a selecta mai mulți părinți.

Elitismul presupune faptul că individul cel mai adaptat este copiat direct în noua populație. Astfel, niciodată nu se va pierde soluția cea mai bună. Încrucișarea combină 2 cromozomi părinți pentru a produce un nou cromozom fiu. Are loc cu o probabilitate mare, numită rată de încrucișare. Pentru codarea binară, cea mai des folosită metodă este încrucișarea cu un punct: se alege un punct aleatoriu în cei doi părinți, se divid părinții la punctul de încrucișare și se creează 1 sau 2 copíi prin unirea extremelor. Pentru codarea cu valori reale, se folosește de obicei încrucișarea aritmetică: se creează copíi „între” părinți: zi =  xi + (1 – ) yi , cu 0    1, unde  este o variabilă aleatorie.

15

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Mutația modifică genele unui copil cu o probabilitate mică, numită rată de mutație. Mutația binară neagă valoarea unei gene. Mutația reală resetează o genă la o valoare aleatorie în domeniul de definiție sau modifică puțin valoarea existentă. Criteriile de terminare cele mai folosite sunt: atingerea unui număr specificat de generații sau convergența populației.

2. Evoluția diferențială Evoluția diferențială (Differential Evolution, DE) este asemănătoare cu un algoritm evolutiv, are operatori de selecție, încrucișare, mutație, dar ordinea lor și procedurile propriu-zise sunt diferite. Pentru mutație, se aleg trei indivizi diferiți (xr1, xr2, xr3) și se creează un nou vector: vi ,G1  xr1,G  F ( xr 2,G  xr 3,G )

unde F  (0, 2] este factorul de amplificare. Fie alt individ xi, diferit de cei trei anteriori. Din vectorii xi și vi, se generează un vector ui numit vector de încercare, pe baza unei probabilități CR  [0, 1] numite rată de încrucișare. Există mai multe tipuri de încrucișare, de exemplu încrucișarea binomială sau exponențială (Zaharie, 2007).

16

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Selecția se realizează la nivel de cromozom:

ui ,G 1 dacă f (ui ,G 1 )  f ( xi ,G ) xi ,G 1   altfel  xi ,G

3. Optimizarea de tip roi de particule Optimizarea de tip roi de particule (Particle Swarm Optimization, PSO) este bazată pe indivizi care imită comportamentul stolurilor de păsări sau roiurilor de insecte. Fiecare particulă are: o poziție curentă xi , o viteză curentă vi , cea mai bună poziție personală yi și cea mai bună poziție a vecinătății ŷi . Pentru fiecare particulă, se inițializează aleatoriu pozițiile xi . Vitezele vi sunt inițializate tot cu valori aleatorii sau, mai rar, cu 0. Până la satisfacerea unui criteriu de convergență, de exemplu, un număr maxim de iterații, se repetă următorii pași. Se evaluează funcția obiectiv a particulei, f (xi). Se actualizează optimul personal: x (t  1) dacă f xi (t  1)   f y i (t )  y i (t  1)   i altfel  y i (t )

Se calculează optimul social (al vecinătății):

yˆ (t )  argmin ( f ( y1 (t ), f ( y 2 (t ), ..., f ( y s (t )) Pentru fiecare dimensiune, se actualizează viteza:

17

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Vitezele sunt limitate la o valoare Vmax. Se actualizează poziția curentă:

xi (t  1)  xi (t )  vi (t  1) Ponderea inerției w definește compromisul între explorare și exploatare. O valoare mai mică scade viteza particulelor și conduce la mai multă exploatare. O valoare mai mare crește viteza particulelor și conduce la mai multă explorare. Pentru a asigura convergența algoritmului, este necesară respectarea relației:

c1  c2 1  w 2

4. Optimizarea de tip colonie de furnici Optimizarea de tip colonie de furnici (Ant Colony Optimization, ACO) este o metodă probabilistică pentru rezolvarea unor probleme care pot fi reduse la găsirea unor căi în grafuri. Este inspirată din modalitatea prin care furnicile aleg drumul cel mai scurt către o sursă de hrană. Furnicile, când merg, depun urme de feromoni, iar probabilitatea de a alege o rută depinde de concentrația de feromoni. Această formă de comunicare indirectă prin modificarea mediului se numește stigmergie. Inițial, m furnici sunt plasate aleatoriu în m noduri. În fiecare iterație t, fiecare furnică k se mută din nodul i în nodul j, reprezentând o soluție intermediară mai completă. Alegerea este stohastică, pe baza nivelului de feromoni τij al arcului (i, j) și a atractivității ηij a arcului:

18

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

  (t )    (t )  p (t )    (t )   (t ) ij

k ij

lN ik

ij

il

dacă j  N ik

il

unde: ηij este în general o funcție de lungimea arcului, de obicei ηij = 1 / dij , α ≥ 0, β ≥ 1. Dacă α = 0, este o căutare greedy. Dacă β ar fi 0, doar feromonii contează și de obicei căutarea nu converge. Nik este o vecinătate fezabilă a furnicii k, adică mulțimea nodurilor nevizitate încă. Actualizarea feromonilor se face după relația: m

 ij (t  1)    ij (t )    ijk (t ) k 1

1 / Lk (t ) dacă arcul (i, j ) este traversat de furnica k în iteratia t  ijk (t )   altfel 0

unde: ρ este persistența urmei de feromoni, prin urmare (1 – ρ) este rata de evaporare, 0 ≤ ρ < 1, iar  ijk (t ) este cantitatea de feromoni depozitată de furnica k pe arcele traversate și Lk(t) este lungimea turului furnicii k.

5. Hill climbing pleacă de la o idee asemănătoare cu metoda gradientului ascendent, dacă funcția obiectiv este maximizată. Se pleacă dintr-un punct ales aleatoriu din spațiul de căutare p0. Punctul curent devine pc  p0. Se generează unul sau mai multe puncte vecine pv. Dacă funcția obiectiv într-un punct vecin este mai bună decât cea curentă, atunci pc  pv . Se poate alege primul vecin mai bun (greedy, simple hill climbing) sau vecinul cel mai bun (steepest ascent hill climbing). Rezultatul metodei hill climbing depinde de punctul de start p0. Pentru a crește probabilitatea de a găsi optimul global, există metoda hill climbing cu puncte multiple de start (multiple-point hill climbing), în care se repetă procedura de hill climbing de m ori cu puncte de start aleatorii diferite și se alege în final soluția cea mai bună. Hill climbing

19

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

6. Călirea simulată Călirea simulată (Simulated Annealing, SA) este o metodă inspirată din călirea metalurgică. Încălzirea și apoi răcirea controlată a unui material crește dimensiunea cristalelor și reduce defectele. Căldura face ca atomii să își piardă pozițiile fixe (minimul local al energiei interne) și să viziteze aleatoriu stări cu energie mai ridicată. Răcirea lentă le dă mai multe șanse să găsească o configurație cu o energie internă mai mică decât cea inițială, corespunzătoare minimului global al problemei de optimizare. Călirea simulată este o procedură asemănătoare cu hill climbing, dar se poate trece și într-o stare inferioară cu o anumită probabilitate. Presupunem o problemă de minimizare, cu funcția obiectiv E. Dacă vecinul este mai bun (Ev < Ec), atunci pc ← pv. Dacă starea curentă este mai bună decât starea următoare, a vecinului (Ev > Ec), atunci:   

Se calculează diferența funcțiilor obiectiv: ΔE = Ev – Ec ; Se consideră temperatura curentă T, mare la început și care scade în timp; Probabilitatea de a accepta tranziția în starea inferioară este: P = exp(–ΔE / T).

Temperatura inițială este mare și tinde în timp la 0. Trebuie să existe suficiente iterații la fiecare nivel de temperatură. Există mai multe metode practice de răcire:   

Scăderea liniară a temperaturii; Scăderea geometrică: T ← T ∙ α; Se începe cu o temperatură foarte mare și se răcește rapid până când 60% din soluțiile mai proaste sunt acceptate. Aceasta este temperatura reală de start și răcirea se face apoi mai lent.

La început, la temperaturi mari, există o probabilitate mai mare de acceptare a unor stări inferioare: algoritmul poate ieși din vecinătatea unui optim local. Spre final, algoritmul devine asemănător cu hill climbing: 20

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

încearcă găsirea punctului optim din vecinătate, care ar putea fi optimul global. Criteriul de terminare este când T se apropie de 0 sau când nu se mai fac tranziții, nici în stări mai rele, nici în stări mai bune.

7. Optimizarea de tip QUBO Calculul cuantic adiabatic presupune codarea problemei într-un sistem fizic astfel încât starea de energie minimă a sistemului să indice soluția problemei. Este folosit de calculatorul cuantic D-Wave. Problema este codată sub forma unor parametri pentru qubiții dispuși într-o latice de celule, în care qubiți sunt cuplați cu vecinii lor. Soluția problemei este dată de minimizarea următoarei funcții:

O(q; a, b)   ai qi   bij qi q j i

(i , j )

În acest scop trebuie realizată o formulare specifică a problemei de rezolvat. Acest tip de probleme poată numele QUBO (Quadratic Unconstrained Binary Optimization). Programatorul furnizează valori potrivite pentru ponderile qubiților ai și puterea cuploarelor bij. Acești parametri trebuie furnizați pentru fiecare problemă în parte. D-Wave găsește valorile qi pentru care funcția obiectiv O are valoarea minimă. Valorile qi observate sunt binare și reprezintă soluția problemei.

8. Optimizarea multi-obiectiv O soluție S1 domină o soluție S2 dacă și numai dacă S1 nu este inferioară lui S2 în raport cu toate obiectivele și S1 este strict superioară lui S2 în raport cu cel puțin un obiectiv. Mulțimea tuturor soluțiilor nedominate se numește front Pareto.

21

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

8.1. Algoritm scalar cu sumă ponderată a obiectivelor Pentru optimizarea multi-obiectiv, se poate folosi un algoritm scalar, pentru o problemă în care funcția de adaptare este o sumă ponderată a obiectivelor, cu ponderi stabilite de utilizator: f(x) = w1 f1(x1) + w2 f2(x2) +…+ wn fn(xn), Σ wi = 1. Utilizatorul trebuie să apeleze algoritmul scalar cu diferite combinații de ponderi. Această abordare funcționează doar când frontul Pareto este convex. 8.2. Algoritmul NSGA-II Folosește o meta-euristică: un algoritm evolutiv simplu la care se adaugă calcularea frontului Pareto. Generează noua populație folosind selecția prin competiție, încrucișări și mutații normale. Reunește populația veche cu populația nouă și selectează cei mai adaptați indivizi pentru noua generație. Selecția se bazează pe sortarea nedominată a populației pe ranguri, astfel încât membrii de rang n domină toți membrii de rang mai mare ca n. Sortarea are ca scop selectarea celor mai buni n cromozomi din populația de dimensiune 2n. Membrii de rang 1 constituie mulțimea nedominată, adică aproximarea curentă a frontului Pareto.

22

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Indivizii care aparțin aceluiași front sunt sortați pe baza distanței de aglomerare. Distanța de aglomerare este distanța Manhattan între vecinii din front ai unui individ. Pentru extreme, distanța se consideră ∞. Un individ mai bun are o distanță de aglomerare mai mare. Efectul este selecția indivizilor aflați în regiuni mai puțin aglomerate și previne omogenizarea soluțiilor, deci convergența prematură (fig. Deb, 2001).

23

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

6. Reprezentarea cunoașterii 1. Ierarhia cunoașterii În funcție de nivelul de complexitate semantică, cunoașterea poate fi structurată pe mai multe niveluri, sub forma unei piramide:

Semnalele nu au semnificație simbolică. De exemplu, o scriere necunoscută. Datele sunt secvențe de simboluri cu sens, cu valoare pur sintactică. De exemplu: „Temperatura este de 10 grade. Plouă.” Informațiile sunt date acumulate într-un context cu semnificație, având caracteristici semantice. De exemplu: „Temperatura a scăzut cu 10 grade și apoi a început să plouă.” Cunoștințele reprezintă un domeniu extins de aplicare a informațiilor. De exemplu: „Dacă umiditatea este foarte mare și temperatura scade mult, atmosfera nu mai poate reține vaporii de apă și deci începe să plouă.” Înțelepciunea presupune înțelegerea principiilor, valorilor. De exemplu: „Cel mai bun lucru pe care îl poți face când plouă este să lași 24

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

ploaia să-și urmeze cursul.” / “The best thing one can do when it rains is to let it rain.” (H. W. Longfellow) Înțelegerea se poate defini din punct de vedere comportamental ca abilitatea de a aplica un concept sau o procedură. Din punct de vedere cognitiv, se poate defini ca având mai multe perspective asupra unui concept. Mai multe perspective cresc șansele de aplicare în mai multe situații sau domenii.

2. Sisteme expert Cunoștințele unui nespecialist despre un fenomen sunt globale, amorfe, nestructurate. Pentru un expert, cunoștințele despre același fenomen sunt organizate, precise, punctuale și sistematizate. Un domeniu de expertiză poate avea între 50.000 și 100.000 de piese de cunoaștere specifice (≈ 70.000 ± 20.000). Un sistem expert este un program care utilizează cunoștințe și proceduri de inferență pentru a rezolva probleme suficient de dificile pentru a necesita în mod normal intervenția unui expert uman în vederea găsirea soluției. Pe scurt, sistemele expert sunt programe care înmagazinează cunoștințe specializate, provenite de la experți. Un sistem expert conține trei module principale, care formează așanumitul sistem esențial: baza de cunoștințe (descrierea elementelor și relațiilor), motorul de inferență (care aplică procedurile de căutare, construiește raționamentul și este independent de baza de cunoștințe) și baza de fapte (memoria auxiliară sau temporară).

3. Rețele semantice O rețea semantică este o modalitate grafică de reprezentare a cunoașterii în modele de noduri, semnificând concepte, interconectate prin arce etichetate, care precizează relațiile dintre concepte. Rețelele semantice simple folosesc etichete care descriu relațiile fundamentale dintre concepte, instanțe și atribute: 25

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Rețelele semantice permit și utilizarea de etichete mai generale pentru arce. O proprietate importantă a acestui mod de reprezentare este moștenirea trăsăturilor. În exemplul următor, Rex este un animal, este viu și are patru picioare fiindcă este câine.

Rețele semantice sortate descriu structura gramaticală a unui enunț, folosind relații de tip predicație, agent, receptor, obiect, instrument, loc, timp, durată etc.

4. Reprezentarea prin cadre Teoria cadrelor (frame theory) propune o reprezentare în care sunt cuprinse atât informații declarative cât și procedurale pentru reprezentarea situațiilor stereotipe. Un cadru este un șablon general, în care datele noi sunt interpretate în termenii sau conceptele experienței dobândite anterior.

26

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

De exemplu, pentru o cameră de hotel, reprezentarea prin cadre este următoarea (Luger, 2005):

Un cadru are atribute (slots, attributes), care au valori (values): valori primitive, referințe la alte cadre, proceduri (de exemplu, dacă nu e făcut patul, sună la recepție). Valorile implicite se bazează pe prototipuri.

5. Reprezentarea prin scenarii Un scenariu (script) este o modalitate de reprezentare a cunoașterii ce descrie o secvență stereotipă de evenimente într-un anumit context, adică situații care se repetă, păstrând aceeași structură. De exemplu, pentru un restaurant (Schank & Abelson, 1977):

27

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Elementele unui scenariu: condiții de intrare, rezultate, proprietăți (lucrurile care „sprijină” desfășurarea scenariului, de exemplu: într-un restaurant există mese, scaune, meniuri), roluri (acțiunile pe care le îndeplinesc participanții, de exemplu: chelnerul ia comanda, clientul plătește), scene (împărțirea scenariului pe aspecte temporale, de exemplu: intrarea în restaurant, comanda, luarea mesei).

28

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

6. Ontologii O ontologie reprezintă o mulțime finită de obiecte și concepte (sau clase), împreună cu relațiile dintre ele, inclusiv ierarhiile de clase. Web Ontology Language (OWL) este un limbaj de tip XML pentru definirea și instanțierea ontologiilor web. Permite descrierea claselor și reprezentarea proprietăților și instanțelor. Semantic Web este o idee de web în care cunoștințele pot fi gestionate în mod automat.

29

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

7. Metode de inferență în logica propozițională și predicativă 1. Metode de inferență în logica propozițională Teorema de completitudine a calculului propozițional spune că în calculul propozițional mulțimea teoremelor coincide cu mulțimea tautologiilor. Noțiunea de teoremă este de natură sintactică, în timp ce noțiunea de tautologie are o natură semantică. Teorema subliniază faptul că aceste noțiuni sunt echivalente: orice tautologie poate fi dedusă pe cale sintactică și orice propoziție întotdeauna adevărată este o teoremă și poate fi folosită ulterior pentru inferențe. Dintre modalitățile clasice de inferență propozițională amintim:  

Modus Ponens: premise: P → Q și P, concluzie: Q; Modus Tollens: premise: P → Q și non Q, concluzie: non P.

Rezoluția propozițională este o regulă puternică de inferență pentru logica propozițională, cu ajutorul căreia se poate construi un demonstrator de teoreme corect și complet. Ea poate fi aplicată însă doar după aducerea premiselor și concluziei într-o formă standardizată, numită formă normal conjunctivă (FNC). Transformarea în FNC are următoarele etape: 1. Se înlocuiesc relațiile de implicație și echivalență; 2. Se introduc negațiile în paranteze; 3. Se mută conjuncțiile în afara disjuncțiilor. Ideea de bază a rezoluției este deducerea din două propoziţii, în care unul din termeni apare cu valori de adevăr contrare, a unei concluzii din care este eliminat termenul respectiv. Cu alte cuvinte, din două clauze în care una conține un literal iar cealaltă negația acelui literal, putem deduce o clauză 30

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

care conține reuniunea literalilor celor două clauze-premisă, fără perechea complementară. Într-o formulare mai generală, rezoluția propozițională se bazează pe următoarea regulă de inferență: φ1 ∨ ... ∨ φi–1 ∨ χ ∨ φi+1 ∨... ∨ φn ψ1 ∨ ... ∨ ψj–1 ∨ ¬χ ∨ ψj+1 ∨... ∨ ψm --------------------------------------------------------------------------φ1 ∨ ... ∨ φi–1 ∨ φi+1 ∨... ∨ φn ∨ ψ1 ∨ ... ∨ ψj–1 ∨ ψj+1 ∨... ∨ ψm sau echivalent: C1 = {..., χ, ...} C2 = {..., ¬χ, ...} ------------------------------C1 ∖ { χ } ⋃ C2 ∖ { ¬χ } Linia punctată reprezintă o implicație. Clauza produsă se mai numește rezolvent. În exemplul de mai sus, dacă avem clauzele p ∨ q, respectiv ¬p ∨ r, putem deriva clauza q ∨ r într-un singur pas: p∨q ¬p ∨ r ---------q∨r Rezolvarea a două clauze singleton produce o clauză vidă, ca mai jos. Derivarea clauzei vide indică faptul că mulțimea de clauze, sau mulțimea de fapte, conține o contradicție: p ¬p -----{} 31

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

O propoziție φ este demonstrabilă dintr-o mulțime Δ de clauze dacă și numai dacă procesul de rezoluție propozițională generează clauza vidă din mulțimea Δ ∪ {¬φ}. Este o demonstrație de tip reducere la absurd. Se include în mulțimea de clauze concluzia negată și, prin procesul de rezoluție, se încearcă să se ajungă la o contradicție. Dacă se ajunge, concluzia se poate demonstra, dacă nu, concluzia nu se poate demonstra. De exemplu, fie următoarele premise: p  p  q (q  r )  s 

Vom încerca să demonstrăm adevărul propoziţiei s. În primul rând, cele trei premise trebuie aduse la forma normal conjunctivă: p  p  q (q  r )  s 



 p p  q    q  s  r  s

Presupunem că s este adevărat şi încercăm să ajungem la o contradicţie.

32

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Un sistem logic este decidabil dacă există o metodă eficientă care determină dacă o formulă arbitrară este o teoremă a sistemului logic considerat, adică dacă se poate stabili dacă o formulă este adevărată sau nu. Logica propozițională este decidabilă. De exemplu, cu algoritmul de rezoluție propozițională, o demonstrație se termină întotdeauna: deoarece există un număr finit de clauze care pot fi generate dintr-o mulțime inițială finită de clauze, la un moment dat algoritmul nu mai poate genera noi clauze. Dacă până în acel moment a ajuns la o contradicție, demonstrația a reușit. Dacă nu, concluzia propusă nu poate fi demonstrată.

2. Metode de inferență în logica predicativă Pentru logica predicatelor de ordin întâi, o teoremă se poate demonstra prin raționament înainte, raționament înapoi (dacă clauzele sunt implicații) sau prin rezoluție predicativă (pentru clauze generale). Pentru toate aceste metode, clauzele trebuie aduse de asemenea în forma normal conjunctivă. Transformarea în FNC are următoarele etape: 1. Se înlocuiesc relațiile de implicație și echivalență; 2. Se introduc negațiile în paranteze și peste cuantificatori; 3. Se standardizează variabilele, astfel încât fiecare cuantificator să aibă propria variabilă; 4. Se mută toţi cuantificatorii la stânga formulei, fără a le schimba ordinea relativă; 5. Se elimină cuantificatorii existenţiali, fiind înlocuiți cu funcții Skolem; 6. Se elimină prefixul rămas de cuantificatori universali; 7. Se mută conjuncțiile în afara disjuncțiilor; 8. Fiecare termen disjunctiv se consideră o propoziţie separată; 9. Se standardizează din nou variabilele între termenii disjunctivi distincţi. Deoarece aici avem în predicate atât simboluri (constante) cât și variable, se folosește procesul de unificare, bazat pe substituții (unde

33

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

anumite variabile iau valorile unor simboluri). De exemplu (Russell & Norvig, 2002):

Raționamentul înainte. Dacă procesul de căutare este modelat printr-un sistem de producție, rezolvarea problemei apare drept construirea unui arbore al operațiilor posibile. Rădăcina arborelui este starea inițială. Nivelul următor al arborelui se completează prin determinarea tuturor regulilor a căror parte stângă se potrivește nodului rădăcină. Noile noduri se creează prin intermediul părții drepte a regulilor considerate. Procedura se repetă pentru fiecare nod, până când se generează o configurație identică stării scop. Raționamentul înapoi. Căutarea pornește din starea scop către starea inițială. Rădăcina arborelui este starea scop. Nivelul următor al arborelui se completează prin determinarea tuturor regulilor a căror parte dreaptă se potrivește nodului rădăcină. Noile noduri se creează prin intermediul părții stângi a regulilor considerate. Procedura se repetă pentru fiecare nod, până când se generează o configurație identică stării inițiale. Rezoluția predicativă funcționează în același mod ca rezoluția propozițională, ținându-se cont de substituțiile necesare. De exemplu, fie premisele: xyz tata ( x, y)  parinte( y, z)  bunic( x, z) xy mama( x, y)  parinte( x, y) xy tata ( x, y)  parinte( x, y) tata (Gheorghe, Geta) mama(Geta, Tudor)

și concluzia: bunic(Gheorghe, Tudor) 34

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

În forma normal conjunctivă, premisele sunt: 1) tata ( x1 , y1 )  parinte( y1 , z1 )  bunic ( x1 , z1 ) 2) mama( x2 , y2 )  parinte( x2 , y2 ) 3) tata ( x3 , y3 )  parinte( x3 , y3 ) 4) tata (Gheorghe, Geta) 5) mama(Geta, Tudor) Presupunem adevărată concluzia negată, bunic(Gheorghe, Tudor) . Procesul de rezoluție poate fi următorul:

adică

propoziţia

Spre deosebire de logica propozițională, în logica predicativă de ordin întâi, problema demonstrării teoremelor este semidecidabilă: se poate afla dacă o propoziție se poate demonstra, dar nu se poate afla dacă o propoziție nu se poate demonstra. În acest caz, algoritmul de rezoluție predicativă poate rula la infinit.

35

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

8. Logica vagă (fuzzy) 1. Logica fuzzy. Mulțimi fuzzy Logica tradițională consideră că un obiect poate aparține sau nu unei mulțimi. Logica fuzzy permite o interpretare mai flexibilă a noțiunii de apartenență. Astfel, un obiect poate aparține mai multor mulțimi în grade diferite. Mulțimile fuzzy permit elementelor să aparțină parțial unei clase sau mulțimi. Fiecărui element i se atribuie un grad de apartenență la o mulțime. Acest grad de apartenență poate lua valori între 0 (nu aparține mulțimii) și 1 (aparține total mulțimii). În cazul în care gradul de apartenență ar fi doar 0 sau 1, mulțimea fuzzy ar fi echivalentă cu o mulțime binară. Fie X universul discursului, cu elemente notate x. O mulțime fuzzy A a universului de discurs X este caracterizată de o funcție de apartenență  A (x) care asociază fiecărui element x un grad de apartenență la mulțimea A:

 A ( x) : X  [0, 1] Pentru a reprezenta o mulțime fuzzy, trebuie să-i definim mai întâi funcția de apartenență. În acest caz, o mulțime fuzzy A este complet definită de mulțimea tuplelor:

A  {( x,  A ( x)) | x  X } Pentru o mulțime finită X = {x1, ... , xn}, se mai folosește notația: A  1 / x1  ...  n / xn

De exemplu, pentru variabila lingvistică „tânăr”, avem universul discursului X = {0, 20, 30, 50} și următoarea funcție de apartenență: A = 0/1 + 0,9/20 + 0,7/30 + 0/50, cu semnificația: o persoană de 20 de ani 36

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

aparține mulțimii oamenilor tineri în proporție de 90%, una de 30 de ani în proporție de 70% iar una de 50 de ani nu aparține mulțimii (gradul său de apartenență este 0). Aceste lucruri se reprezintă grafic ca în figura 8.1.

Figura 8.1. Funcție de apartenență pentru mulțimea oamenilor tineri

Pe un univers de discurs pot fi definite mai multe submulțimi fuzzy. De exemplu, pentru universul vârstelor unor persoane, putem defini submulțimile oamenilor tineri, bătrâni sau de vârstă mijlocie. Aceste submulțimi se pot intersecta (este chiar recomandat acest fapt). Aceeași persoană poate aparține, de exemplu, submulțimii oamenilor tineri cu un grad de 70%, submulțimii oamenilor de vârstă mijlocie cu un grad de 90% și submulțimii oamenilor bătrâni cu un grad de 30%. O altă situație cu mai multe submulțimi fuzzy este prezentată în figura 8.2. Aici, submulțimile reprezintă numere negative mari, medii, mici, negative tinzând la zero, pozitive tinzând la zero, mici, medii, și mari. Valoarea µ reprezintă gradul de apartenență.

Figura 8.2. Submulțimi fuzzy pentru universul de discurs al numerelor reale (N = negativ, P = pozitiv, L = mare, M = mediu, S = mic) (Knapp, 2004)

37

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Noțiuni fundamentale Fie A o submulțime fuzzy a universului de discurs X. Se numește suportul lui A submulțimea strictă a lui X ale cărei elemente au grade de apartenență nenule în A: supp(A) = {x  X |  A ( x)  0} . Înălțimea lui A se definește drept cea mai mare valoare a funcției de apartenență: h(A) = sup  A ( x) . xX

Se numește nucleul lui A submulțimea strictă a lui X ale cărei elemente au grade de apartenență unitare în A: n(A) = {x  X |  A ( x)  1} . Fie A și B submulțimi fuzzy ale lui X. Spunem că A este o submulțime a lui B dacă:  A ( x)  B ( x), x  X .

Figura 8.3. Submulțime fuzzy

Fie A și B submulțimi fuzzy ale lui X. Spunem că A și B sunt egale dacă A  B și B  A . Deci, A  B   A ( x)  B ( x), x  X .

38

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Numere fuzzy De multe ori, oamenii nu pot caracteriza precis informațiile numerice, folosind formulări precum „aproape 0”, „în jur de 100” etc. În teoria mulțimilor fuzzy, aceste numere pot fi reprezentate ca submulțimi fuzzy ale mulțimii numerelor reale. Un număr fuzzy este o mulțime fuzzy a mulțimii numerelor reale, cu o funcție de apartenență convexă și continuă și suport mărginit. O mulțime fuzzy A se numește număr fuzzy triunghiular cu centrul c, lățimea la stânga α > 0 și lățimea la dreapta β > 0 dacă funcția sa de apartenență are forma:  cx 1   , c    x  c  x  c  A ( x)  1  ,c  x  c   0, altfel 

Folosim notația: A = (c, α, β). Este evident că supp(A) = (c – α , c + β ). Semnificația unui număr fuzzy triunghiular cu centrul c este „x este aproximativ egal cu c”.

Figura 4. Număr fuzzy triunghiular

O mulțime fuzzy A se numește număr fuzzy trapezoidal cu intervalul de toleranță [c, d ], lățimea la stânga α > 0 și lățimea la dreapta β > 0 dacă funcția sa de apartenență are forma: 39

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

 cx 1   , c    x  c 1, c  x  d  A ( x)   x  d ,d  x d  1    0, altfel

Figura 5. Număr fuzzy trapezoidal

Aici notăm: A = (c, d, α, β ) și supp(A) = (c – α , d + β ). Semnificația unui număr fuzzy trapezoidal cu intervalul de toleranță [c, d ] este „ x este aproximativ între c și d ”.

4. Inferența Mamdani (max-min) cu o singură regulă 4.1. Modus Ponens generalizat În logica fuzzy și raționamentul aproximativ, cea mai importantă regulă de inferență este Modus Ponens generalizat. În logica clasică, această regulă de inferență este de forma ( p  ( p  q))  q , adică: regulă: premisă: concluzie:

dacă p, atunci q p q

40

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

În logica fuzzy, regula de inferență corespunzătoare este următoarea: regulă: premisă (antecedent): concluzie (consecvent):

dacă x este A, atunci y este B x este A' y este B', unde B'  A'( A  B) .

Dacă A' = A și B' = B, regula se reduce la Modus Ponens clasic. Matricea A  B deseori se notează cu R. Procesul de inferență fuzzy este văzut ca o transformare a unei mulțimi fuzzy într-o altă mulțime fuzzy. R are semnificația unei matrici de posibilități condiționate ale elementelor din A și B:

R   B| A

a1  b1  a2  b1

a1  b2 ...

...

... 4.2. Calcularea consecventului Inferența de tip Mamdani utilizează pentru implicație operatorul minimum, adică: rij  min( ai , b j ). Dacă avem mulțimile A și B, se poate astfel afla R. Prin metoda de inferență Mamdani, mulțimea rezultată B' este o variantă „retezată” a lui B, la înălțimea fixată de A'. A' poate fi o submulțime normală a lui A, nu doar cu un singur element.

Figura 8.6. Inferență de tip Mamdani

41

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Prin metoda de inferență Larsen, mulțimea rezultată B' este o variantă „scalată” a lui B, la înălțimea fixată de A'.

Figura 8.7. Inferență de tip Larsen

4.3. Defuzzificarea După ce am determinat mulțimea fuzzy indusă de o regulă de inferență, în unele aplicații trebuie obținută o valoare singulară, strictă, pe baza acestei mulțimi. Procesul se numește defuzzificare. Cea mai utilizată tehnică de defuzzificare este metoda centrului de greutate (sau a centroidului):

xCG

 x   (x )    (x ) i

i

i

A

A

i

i

Figura 8.8. Inferență de tip Mamdani și defuzzificare

42

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

În figura 8.8, în dreapta, mulțimea delimitată cu albastru este B, cea delimitată cu roz este B' iar valoarea pe axa X indicată cu roșu este centrul de greutate.

5. Inferența Mamdani cu reguli multiple Un exemplu de sistem de inferență fuzzy de tip Mamdani este prezentat în figura 8.9.

Figura 8.9. Sistem de inferență fuzzy de tip Mamdani cu două reguli și două intrări stricte (Knapp, 2004)

Pentru a calcula ieșirea acestui sistem când se dau intrările trebuie parcurși următorii 6 pași: 1. Se determină o mulțime de reguli fuzzy; 2. Se realizează fuzzificarea intrărilor utilizând funcțiile de apartenență;

43

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Se combină intrările fuzzificate urmând regulile fuzzy pentru stabilirea puterilor de activare ale regulilor; 4. Se calculează consecvenții regulilor prin combinarea puterilor de activare ale regulilor cu funcțiile de apartenență ale ieșirilor; 5. Se combină consecvenții pentru a determina mulțimea de ieșire; 6. Se defuzzifică mulțimea de ieșire, doar dacă se dorește ca ieșirea să fie strictă. În cele ce urmează se prezintă o descriere detaliată a acestui proces. 5.1. Crearea regulilor fuzzy Regulile fuzzy reprezintă o mulțime de afirmații care descriu modul în care sistemul poate lua o decizie privind estimarea ieșirii. Regulile fuzzy au următoarea formă: DACĂ (intrarea-1 este mulțime-fuzzy-1) ȘI/SAU (intrarea-2 este mulțime-fuzzy-2) ȘI/SAU ... ATUNCI (ieșirea este mulțime-fuzzy-de-ieșire). Un exemplu de regulă scrisă în acest mod este următorul: DACĂ finanțarea-proiectului este adecvată ȘI numărul de angajați este redus ATUNCI riscul-proiectului este mic. 5.2. Fuzzificarea Scopul fuzzificării este de a transforma intrările în valori cuprinse între 0 și 1 utilizând funcțiile de apartenență. În exemplul din figura 8.9 există două intrări x0 și y0 prezentate în colțul din stânga jos. Pentru aceste intrări stricte se marchează gradele de apartenență în mulțimile corespunzătoare. 44

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

5.3. Combinarea antecedenților multipli Pentru crearea regulilor fuzzy utilizăm operatorii ȘI, SAU și uneori NEGAȚIE. Operatorul fuzzy ȘI este scris ca:  AB ( x)  T (  A ( x), B ( x)) unde T este o funcție numită T-normă, µA(x) este gradul de apartenență a lui x la mulțimea A, iar µB(x) este gradul de apartenență a lui x la mulțimea B. Cu toate că există mai multe moduri pentru calculul funcției ȘI, cel mai des folosit este: min(µA(x), µB(x)). Operatorul fuzzy ȘI reprezintă o generalizare a operatorului logic boolean ȘI în sensul că valoarea de adevăr a unei propoziții nu este doar 0 sau 1, ci poate fi cuprinsă între 0 și 1. O funcție T-normă este monotonă, comutativă, asociativă și respectă condițiile T(0, 0) = 0 și T(x, 1) = x. Operatorul fuzzy SAU se scrie ca  AB  S (  A , B ) unde S este o funcție numită T-conormă. În mod similar cu operatorul ȘI, aceasta poate fi: max(µA(x), µB(x)). Operatorul fuzzy SAU reprezintă, de asemenea, o generalizare a operatorului logic boolean SAU la valori cuprinse între 0 și 1. O funcție T-conormă este monotonă, comutativă, asociativă și respectă condițiile S(x, 0) = x și S(1, 1) = 1. 5.4. Calcularea consecvenților Mai întâi, se calculează puterile de activare ale regulilor, după cum s-a prezentat în secțiunea anterioară. În figura 8.9, se poate observa că este utilizat operatorul fuzzy ȘI asupra funcțiilor de apartenență pentru a calcula puterile de activare ale regulilor. Apoi, pentru un sistem de inferență fuzzy de tip Mamdani, mulțimea de ieșire este retezată la nivelul dat de puterea de activare a regulii, așa cum s-a arătat mai sus. 5.5. Agregarea ieșirilor Ieșirile obținute după aplicarea regulilor fuzzy sunt combinate pentru a se obține mulțimea de ieșire. De obicei, acest lucru se realizează utilizând operatorul fuzzy SAU. În figura 8.9, funcțiile de apartenență din partea dreaptă sunt combinate utilizând operatorul fuzzy SAU pentru a obține mulțimea de ieșire prezentată în colțul din dreapta jos. 45

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

5.6. Defuzzificarea De multe ori, se dorește obținerea unei ieșiri stricte. De exemplu, dacă se încearcă clasificarea literelor scrise de mână pe o tabletă, sistemul de inferență fuzzy trebuie să genereze un număr strict care poate fi interpretat. Acest număr se obține în urma procesului de defuzzificare. Cea mai des utilizată metodă de defuzzificare este metoda centrului de greutate, prezentată anterior și exemplificată și în figura 8.10.

Figura 8.10. Defuzzificarea utilizând metoda centrului de greutate (Knapp, 2004)

6. Tratarea intrărilor fuzzy Figura 8.11 prezintă o modificare a sistemului de inferență din figura 8.9, unde y0 reprezintă o intrare fuzzy, nu strictă. Intrările fuzzy pot fi folosite pentru modelarea lipsei de precizie din măsurătorile care corespund intrărilor, de exemplu, când acestea sunt colectate de niște senzori. Dacă am presupune că intrarea y0 este generată de un senzor de presiune, chiar dacă aplicăm aceeași presiune, senzorul generează o tensiune ce variază între anumite limite. Funcția de apartenență a intrărilor fuzzy modelează această oscilație a semnalelor generate de senzori. Mulțimea fuzzy de intrare se intersectează cu mulțimea antecedentului corespunzător, prin utilizarea operatorului ȘI, iar înălțimea mulțimii obținute prin intersectare este utilizată apoi pentru calcularea puterii de activare a regulii.

46

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Figura 8.11. Sistem de inferență cu o intrare strictă și una fuzzy (Knapp, 2004)

47

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

9. Rețele bayesiene 1. Teorema lui Bayes P(B|A) = P(A|B) · P(B) / P(A) P(B|A) este probabilitatea a posteriori (posterior) P(A|B) este verosimilitatea (likelihood) P(B) este probabilitatea a priori (prior) P(A) este evidența (evidence) Relația este importantă deoarece putem calcula astfel probabilitățile cauzelor, date fiind efectele. Este mai simplu de cunoscut când o cauză determină un efect, dar invers, când cunoaștem un efect, probabilitățile cauzelor nu pot fi cunoscute imediat. Teorema ne ajută să diagnosticăm o anumită situație sau să testăm o ipoteză.

2. Structura unei rețele bayesiene O rețea bayesiană (Bayesian Network, BN) este un model grafic probabilistic, adică un graf cu o mulțime de noduri, care reprezintă evenimente aleatorii, conectate de arce, care reprezintă dependențe condiționate între evenimente. Ideea de bază este că un nod depinde doar de „părinții” săi, adică de o submulțime a nodurilor din rețea, nu de toate celelalte noduri, ceea ce ar implica folosirea distribuției comune de probabilitate. Altfel spus, fiecare nod este independent condiționat de predecesorii din șirul ordonat al nodurilor, dați fiind părinții nodului. O rețea bayesiană este un graf orientat aciclic. Arcele pot forma bucle, dar nu pot forma cicluri. De exemplu (Russell & Norvig, 2002):

48

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2.1. Algoritmul Bayes-Ball Reprezintă o modalitate de a determina relațiile de independență și independență condiționată într-o rețea bayesiană. Se presupune că o minge este trimisă dintr-un nod în rețea. Mingea trece în moduri diferite, în funcție de cine o trimite (fiu sau părinte) și starea nodului care o primește (observat/evidență sau neobservat). Nodurile la care mingea nu ajunge sunt independente (condiționat) de nodul de start. Regulile de trimitere a mingii sunt cele din figura de mai jos:

Rețelele bayesiene codează relații de corelație. Dacă probabilitatea unui eveniment A variază împreună cu probabilitățile altor evenimente {B, C,...}, atunci A este corelat cu {B, C,...}. A poate fi cauzat sau nu de 49

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

{B, C,...}. Toate evenimentele {A, B, C,...} ar putea fi cauzate de alte evenimente necunoscute. O relație de corelație nu implică o relație de cauzalitate. O relație de cauzalitate implică o relație de corelație. 2.2. Inferențe exacte și aproximative Sortarea topologică a unui graf este o ordonare liniară a nodurilor sale astfel încât, pentru fiecare arc A → B, A apare înaintea lui B. Pentru o rețea bayesiană, sortarea topologică asigură faptul că nodurile părinte vor apărea înaintea nodurilor fiu, ceea ce este necesar pentru unii algoritmi sau pot să simplifice calculele. Inferența probabilităților marginale calculează probabilitățile nodurilor în sine, în lipsa unor noduri evidență. Pentru un nod, se sumează probabilitățile sale condiționate de toate combinațiile de valori ale părinților, înmulțite cu probabilitățile părinților de a avea valorile respective. Inferența prin enumerare este un algoritm prin care se poate răspunde la întrebări arbitrare despre evenimentele codate de o rețea bayesiană. Unele variabile (noduri) sunt observate, iar altele nu. Se calculează probabilitățile variabile de interogare separat pentru fiecare valoare. Pentru variabilele observate, se folosește valoarea observată. Pentru variabilele neobservate, se sumează probabilitățile pentru toate valorile posibile. În final, probabilitățile determinate se normalizează, pentru a avea suma 1. Inferența prin ponderarea verosimilității este un algoritm de inferență aproximativă stohastică. Se generează aleatoriu eșantionări (instanțieri) ale rețelei și se calculează probabilitățile dorite ca frecvențe relative de apariție. Nodurile fără părinți sunt instanțiate potrivit probabilităților lor marginale. Nodurile evidență iau mereu valorile observate. Valorile variabilelor neobservate au probabilități de apariție în conformitate cu probabilitățile nodurilor. Pentru fiecare eșantionare a rețelei, se calculează o pondere. Se repetă procesul pentru un număr prestabilit de eșantioane. În final, are loc o fază de normalizare, în care se calculează suma ponderilor cazurilor în care o variabilă de interogare a avut o anumită valoare, împărțită la suma ponderilor tuturor cazurilor.

50

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Rețele bayesiane dinamice O rețea bayesiană dinamică (Dynamic Bayesian Network, DBN) este o rețea bayesiană care reprezintă un model de probabilitate temporal. Este organizată în partiții (slices) de timp. Fiecare partiție poate avea mai multe variabile de stare Xt și variabile de evidență Et. Pentru a construi o DBN, trebuie specificate: distribuția a priori a variabilelor de stare P(X0), modelul de tranziții P(Xt+1 | Xt ) și modelul de observații sau de senzori P(Et | Xt ). O DBN se poate transforma într-o rețea bayesiană simplă prin desfășurare (unrolling), după care s-ar putea aplica algoritmii de inferență de la rețelele bayesiene simple. Însă complexitatea algoritmilor de inferență exactă specifici rețelelor bayesiene simple pentru DBN-uri desfășurate este exponențială.

3.1. Filtrarea cu particule (particle filtering) Este un algoritm de inferență aproximativă pentru DBN. Filtrare înseamnă determinarea lui P(Xt | E0:t ) la momentul curent t. Mai întâi, se creează o populație de n particule cu starea eșantionată din distribuția a priori P(X0). Apoi, se repetă următoarele faze pentru fiecare moment de timp: 1. Fiecare eșantion (stare a particulei) este propagat înainte prin eșantionarea următoarei stări pe baza modelului de tranziție P(Xt+1 | Xt); 2. Fiecare particulă este ponderată de probabilitatea pe care o atribuie noilor evidențe P(Et+1 | Xt+1); 3. Populația este reeșantionată pentru a genera o nouă populație de n particule. Fiecare nouă particulă este selectată din populația curentă. Probabilitatea de a fi selectată o particulă este proporțională cu ponderea sa. Noile particule nu au ponderi.

51

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

10. Metode de planificare Planificarea reprezintă alegerea unei succesiuni de acțiuni pentru atingerea unui scop. Una din primele metode de planificare a fost metoda analizei mijloace-scopuri. Ea presupune mai întâi identificarea scopurilor și apoi identificarea mijloacelor care permit atingerea scopurilor. Se bazează pe o mulțime de reguli care pot transforma o stare a problemei în alta. Regulile se reprezintă sub forma unei părți stângi, care descrie precondițiile (condițiile de aplicare) și o parte dreaptă care descrie schimbările din starea problemei ca urmare a aplicării regulii. În acest scop se elaborează o așa-numită tabelă de diferențe, în care se precizează ce operație este aplicabilă pentru fiecare stare a problemei. Pentru rezolvarea unei probleme, se determină scopurile care trebuie atinse și, dacă nu pot fi atinse direct, se determină subscopuri până când pot fi aplicate regulile (mijloacele) în mod direct.

1. Limbaje de reprezentare: STRIPS, ADL, PDDL O stare este o conjuncție de termeni pozitivi, propoziționali sau de ordin întâi. De exemplu: Poor ∧ Unknown At(Plane1, Melbourne) ∧ At(Plane2, Sydney) Presupunerea lumii închise (closed-world assumption): orice condiție care nu este menționată într-o stare este considerată falsă. Scopurile sunt reprezentate de o conjuncție de termeni pozitivi: Rich ∧ Famous At(Plane1, Tahiti) 52

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Reprezentarea acțiunilor se face prin scheme de acțiuni, care au precondiții și postcondiții (efecte):

Problema cadrului (frame problem) apare din faptul că în mod normal ar fi necesară reprezentarea logică a unui număr mare de non-efecte obișnuite, implicite, ale unei acțiuni. Presupunerea STRIPS (STRIPS assumption) evită această problemă prin ideea că orice termen care nu este menționat în efect rămâne neschimbat. Exemplu de problemă de planificare (Russell & Norvig, 2002):

53

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Metode de planificare prin căutare în spațiul stărilor Planificarea prin progresie (căutare înainte) ia în calcul efectele tuturor acțiunilor posibile într-o stare dată (Russell & Norvig, 2002):

Planificarea prin regresie (căutare înapoi): pentru atingerea unui scop, se caută ce ar fi putut fi adevărat într-o stare anterioară (Russell & Norvig, 2002):

Căutarea este ajutată de euristici (ca la algoritmul A*, de exemplu). Abordări pentru găsirea unor euristici admisibile: soluții optime la probleme relaxate:   

No delete list:

eliminarea efectelor negative (a listei de ștergere), fără a elimina precondițiile. Este una din cele mai utilizate euristici; Eliminarea tuturor precondițiilor acțiunilor; Presupunerea independenței subscopurilor: costul rezolvării unei conjuncții de subscopuri este aproximativ egal cu suma costurilor de rezolvare independentă a subproblemelor.

54

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Euristicile presupun rezolvarea efectivă a unor probleme simplificate de planificare. În practică, aceste costuri sunt neglijabile. Tipurile de planificare prin progresie și regresie sunt forme de planificare cu ordine totală. Nu pot profita de descompunerea problemei. Trebuie luate decizii de găsire a tuturor secvențelor de acțiuni pentru toate subproblemele simultan.

3. Planificarea cu ordine parțială Planificarea cu ordine parțială (partial-order planning, POP) introduce constrângeri de ordonare a acțiunilor (ce acțiuni trebuie executate înaintea altora). În planificarea cu ordine parțială, se poate profita de descompunerea problemei: se rezolvă independent subscopurile și apoi se combină subplanurile. De exemplu (Russell & Norvig, 2002):

Planificarea cu ordine parțială poate rezolva anomalia Sussman din lumea blocurilor, care pune în evidență limitările metodelor de planificare cu ordine totală, în care, dacă există mai multe scopuri care trebuie atinse, ordinea atingerii acestor scopuri afectează optimalitatea soluției (fig. Russell & Norvig, 1998).

55

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Euristici pentru POP:  

Numărul de precondiții deschise distincte; Cea mai constrânsă variabilă: selectarea condiției deschise care poate fi satisfăcută în cele mai puține moduri.

4. Algoritmul FF Algoritmul FF (Fast-Forward) tratează planificarea ca pe o căutare înainte, folosind o serie de euristici: 

  

Folosește euristica no delete list ca estimare a apropierii de scop. Se rezolvă problema de planificare considerând că acțiunile au doar liste de adăugare. Aceasta este o problemă relaxată, mai simplă; Mai întâi folosește o strategie greedy, fără backtracking, înspre scop; Pe platouri utilizează căutarea în lățime; Dacă nu găsește o soluție, aplică o căutare A* din starea inițială. 56

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Este un algoritm rapid, dar nu garantează găsirea soluției optime (cu numărul minim de pași).

57

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

11. Algoritmi de clasificare 1. Învățarea automată Învățarea denotă schimbările dintr-un sistem, astfel încât acesta să poată realiza aceeași sarcină mai eficient sau sarcini noi, posibil similare. Un program învață dacă își îmbunătățește performanțele la îndeplinirea unei sarcini pe baza experienței. Învățarea este esențială pentru mediile necunoscute, în care nu se pot anticipa toate stările mediului, iar proiectantul nu poate să îi dea agentului toate informațiile. Învățarea este o alternativă la proiectarea explicită, deoarece expune agentul la mediul real în loc să îi descrie mediul. Învățarea automată (machine learning) își propune descoperirea unor modele interesante în date. Direcții principale: 



 

Clasificarea și regresia: presupun învățarea unei relații între intrări (vectorul x) și ieșire (y) din date. Pentru clasificare, ieșirea este discretă, iar pentru regresie, ieșirea este continuă. Pentru fiecare instanță de antrenare, valoarea dorită a ieșirii este cunoscută (învățare supervizată); Gruparea (clustering, partiționare, clusterizare): are ca scop găsirea unor grupuri astfel încât instanțele din același grup să fie mai asemănătoare între ele decât cu instanțele altor grupuri. De obicei, este nesupervizată; Determinarea regulilor de asociere: identifică relații interesante între date tranzacționale aparent neînrudite; Selecția trăsăturilor: reprezintă determinarea unei submulțimi de atribute relevante din mulțimea de antrenare.

58

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Clasificarea și regresia Aceste metode de învățare automată presupun construirea unui model pe baza unei mulțimi de antrenare, formată dintr-o mulțime de instanțe (vectori de antrenare, obiecte). Instanțele au atribute. Fiecare instanță are atribute cu anumite valori. Pentru o problemă de clasificare, de obicei, ultimul atribut este clasa. De exemplu (fig. Tan, Steinbach & Kumar, 2006):

Singura diferență între clasificare și regresie este tipul ieșirii: discret, respectiv continuu. Au însă aceeași idee de bază: învățarea unei relații între intrări (vectorul x) și ieșire (y) din date. Odată construit modelul, acesta va putea fi folosit pentru predicție, adică pentru instanțe diferite de cele conținute de mulțimea de antrenare.

3. Tipuri de atribute Atributele unei probleme de clasificare sau regresie pot fi:

59

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com





Discrete (simbolice): nominale (culoarea ochilor, nume, sex, CNP ca obiect, nu număr) sau ordinale (înălțime: mică, medie, mare, ranguri, calificative); Continue (numerice): de tip rațional (unde există un „element neutru”, de exemplu, 0: lungime, distanță, prețuri) sau de tip interval (temperatura în grade Celsius, date calendaristice).

Unii algoritmi tratează în mod natural atributele numerice (de exemplu, rețelele neuronale, cei mai apropiați k vecini), alții tratează în mod natural atributele simbolice (de exemplu, clasificatorul bayesian naiv). Dacă avem atribute simbolice pentru algoritmi cu precădere numerici, se creează câte o intrare sau ieșire pentru fiecare valoare discretă (codarea one-hot). Dacă avem atribute numerice pentru algoritmi cu precădere simbolici, acestea se discretizează. Discretizarea se poate face:   

Cu interval egal: histograma; Cu frecvență egală: mulțimi cu numere egale de instanțe; Prin grupare (clustering).

4. Arbori de decizie Algoritmul lui Hunt reprezintă o procedură generală pentru construirea unui arbore de decizie. Fie Dn mulțimea instanțelor de antrenare atribuite unui nod n. Dacă Dn conține numai instanțe din aceeași clasă yn , atunci n este o frunză etichetată yn . Dacă Dn este mulțimea vidă, atunci n este o frunză etichetată cu clasa implicită (default) yd . Dacă Dn conține instanțe care aparțin mai multor clase, se utilizează un test de atribute pentru a partiționa datele în mulțimi mai mici. Se aplică recursiv procedura pentru fiecare submulțime. Algoritmul descris mai jos este sintetizat pe baza ideilor algoritmilor ID3 și C4.5 și folosind măsura de impuritate din algoritmul CART. ID3 și C4.5 folosesc entropia, iar CART folosește indexul Gini.

60

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Atunci când este partiționat un nod, se preferă partiționarea care determină noduri-fiu cu cea mai omogenă distribuție de clase. Prin urmare, necesită o măsură a „impurității” nodurilor, precum entropia (E) sau indexul Gini (G): c

E (t )   p(i | t )  log 2 p(i | t ) i 1

c

G ( t )  1    p (i | t ) 

2

i 1

Când măsura are valoarea maximă, instanțele sunt distribuite egal între clase (cazul cel mai defavorabil). Când are valoarea minimă (0), toate instanțele aparțin unei singure clase (cazul cel mai favorabil, întrucât nodul va putea fi etichetat ca frunză și căutarea se va termina). Când un nod părinte p este partiționat în k fii, calitatea partiționării (de exemplu, indexul Gini) se calculează astfel: ni Gi i 1 n k

Gsplit  

unde ni este numărul de instanțe din nodul fiu i, iar n este numărul de instanțe din nodul p. Formula este similară pentru entropie. Calitatea unei partiționări este determinată de creșterea omogenității submulțimilor rezultate. Trebuie maximizat câștigul informațional: Δ = I(părinte) – Σi (ni / n · I(fiui)). Deoarece I(părinte) este același pentru toți fiii, se preferă valoarea minimă pentru Σi (ni / n · I(fiui)). Termenul de „câștig informațional” se utilizează când se folosește entropia ca măsură de impuritate, dar principiul este același pentru indexul Gini sau orice altă măsură de impuritate. Prin urmare, se vor încerca partiționările după toate atributele și se va selecta partiționarea cu valoarea minimă pentru formula de mai sus. După ce un atribut a fost folosit pentru partiționare, este eliminat din mulțimile rezultate (pentru nodurile-fiu). Când avem atribute continue, pentru eficientizarea calculelor se sortează valorile, acestea se parcurg liniar, actualizându-se numărarea 61

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

instanțelor și calculându-se indexul Gini și se alege poziția de partiționare cu indexul Gini minim. Pentru optimizarea acestui proces, se calculează indexul Gini doar pentru pozițiile unde se schimbă valoarea clasei. Caracteristici ale clasificării cu arbori de decizie:     

Dificultate medie de implementare; Necesită o serie de calcule; Presupune partiționarea recursivă; Arborii sunt rapizi la clasificarea instanțelor necunoscute; Ușor de interpretat, mai ales pentru arbori de dimensiuni mici.

5. Metoda Bayes naivă (Naïve Bayes) Se consideră fiecare atribut și clasa ca fiind variabile aleatorii urmând anumite distribuții. Se dă o instanță cu atributele (A1, A2, …, An), care va trebui clasificată. Trebuie determinată valoarea clasei C care maximizează P(C | A1, A2, …, An), unde P(C | A1, A2, …, An) trebuie estimată direct din date. Conform teoremei lui Bayes: P(C | A1 A2 ... An ) 

P( A1 A2 ... An | C )  P(C ) P( A1 A2 ... An )

Se alege valoarea clasei C care maximizează P(C | A1, A2, …, An). Pentru o instanță, P(A1, A2, …, An) este aceeași, deci se alege valoarea clasei C care maximizează P(A1, A2, …, An | C) · P(C). P(C) este ușor de calculat: este proporția instanțelor din clasa C în mulțimea de antrenare. Mai trebuie estimată P(A1, A2, …, An | C). Pentru aceasta, se presupune că atributele Ai sunt independente dată fiind clasa Cj : P(A1, A2, …, An | Cj) = P(A1| Cj) P(A2 | Cj) … P(An| Cj)

62

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Putem estima P(Ai | Cj) pentru toate Ai și Cj . Trebuie găsită valoarea Cj astfel încât produsul P(Cj) Πi P(Ai | Cj) să fie maxim. Dacă una din probabilitățile condiționate este 0, atunci tot produsul devine 0. Fie nc numărul de clase. Corecția Laplace evită anularea produsului de probabilităţi cauzată de un factor nul prin modificarea formulei pentru P(Ai | Cj): P( Ai | C j ) 

nij  1 n j  nc

Precizia calculelor poate fi afectată de înmulțirea probabilităților, deoarece acestea sunt valori subunitare mici. Soluția este folosirea logaritmilor. Produsul de probabilități este înlocuit cu suma logaritmilor de probabilități. Pentru atribute continue, există mai multe abordări:   

Discretizarea în atribute ordinale; Partiționarea binară: se aplică unul din testele (Ai  v) sau (Ai > v); Estimarea distribuției de probabilitate (folosită mai rar). În general, discretizarea, chiar cu intervale egale, poate da rezultate mai bune decât metoda estimării distribuției de probabilitate. Caracteristici ale clasificării cu metoda Bayes naivă:

   

Calcule simple; Robustețe la zgomot și atribute irelevante; Aplicabilitate pe mulțimi de antrenare medii sau mari; Presupunerea că atributele sunt independente condițional este deseori infirmată în realitate, dar metoda funcționează totuși bine.

63

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

6. Învățarea bazată pe instanțe (algoritmul celor mai apropiați k vecini, k-Nearest Neighbors, kNN) Se memorează efectiv instanțele de antrenare și se folosesc pentru a prezice clasele instanțelor noi. Se folosesc cele mai apropiate k instanțe pentru a realiza clasificarea. Necesită: mulțimea instanțelor de antrenare, o metrică de distanță pentru a calcula distanța dintre instanțe și valoarea lui k, numărul de vecini apropiați, k ≥ 1. Pentru a clasifica o instanță nouă, se calculează distanța față de instanțele de antrenare, se identifică cei mai apropiați k vecini și se folosesc clasele acestor vecini pentru a determina clasa noii instanțe, de exemplu, prin vot majoritar. Când k este prea mic, clasificarea poate fi afectată de zgomot. Când k este prea mare, vecinătatea poate include puncte din alte clase. Ca metrici de distanță, se folosesc în general particularizări ale distanței Minkowski: 1/ p

 n p d x, y     xi  yi   i 1 

Cele mai folosite metrici sunt: distanța euclidiană (p = 2) și distanța Manhattan (p = 1). Se recomandă scalarea atributelor pentru a preveni dominarea măsurii de distanță de către un anumit atribut. Valorile atributelor sunt normalizate: x'i 

xi  min i 

max i  min i 

 0, 1

Blestemul dimensionalității (curse of dimensionality) reprezintă faptul că datele devin mai rare în spațiile multi-dimensionale. Dacă numărul de atribute este mare, este nevoie de mai multe instanțe de antrenare pentru a forma un model corect.

64

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Ponderarea instanțelor se bazează pe faptul că vecinii mai apropiați au o influență mai mare la stabilirea clasei. Influența fiecărui vecin poate fi ponderată pe baza distanței: wi = 1 / d(xq, xi)2 Dacă d(xq, xi) = 0, atunci f(xq) = f(xi), adică se returnează clasa instanței de antrenare din acel punct. Arborii kd (kd-trees, k-dimensional trees) optimizează căutarea celui mai apropiat vecin sau a celor mai apropiați k vecini. Fiecare mulțime de noduri se partiționează după o dimensiune (atribut), de obicei în mod succesiv. Pentru o anumită dimensiune, se partiționează instanțele după valoarea mediană. Metoda este eficientă atunci când numărul de atribute al problemei este relativ mic. Clasificatorii k-NN sunt clasificatori pasivi (lazy learners): modelul nu este construit explicit, iar efortul de calcul se face la clasificarea instanțelor noi. Arborii de decizie sunt clasificatori activi (eager learners): modelul este construit explicit și aici apare efortul de calcul; în schimb, clasificarea instanțelor noi este rapidă. Caracteristici ale clasificării k-NN:  

Pentru k-NN, rata de eroare la antrenare este mică; dacă mulțimea de antrenare nu este afectată de zgomot, atunci rata de eroare este 0; Însă acest lucru nu garantează și o capacitate bună de generalizare.

65

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

12. Clasificarea bazată pe ansambluri Pentru o problemă, pentru a crește performanțele, se pot rula separat mai mulți algoritmi, de exemplu, arbori de decizie, metoda Bayes naivă, cei mai apropiați k vecini, rețele neuronale etc. Pentru o instanță de test, fiecare algoritm dă un vot privind apartenența la o clasă. Clasa cu cele mai multe voturi este răspunsul ansamblului. Pentru regresie, se face media rezultatelor individuale. Justificarea ar fi că este puțin probabil ca toți algoritmii să facă aceleași erori. Din păcate, erorile algoritmilor sunt deseori corelate și de aceea este nevoie de metode mai elaborate.

1. Bagging Bagging-ul (bootstrap aggregating) presupune următoarea procedură de antrenare. Dintr-o mulțime de date D cu n instanțe se creează m mulțimi de date bootstrapped. Fiecare mulțime este compusă tot din n instanțe, eșantionate uniform cu înlocuire din mulțimea D. Pentru fiecare element dintr-o mulțime Di care trebuie generată, se alege o instanță aleatorie din D. Procesul se repetă de n ori, până se completează toată mulțimea Di. Același algoritm de clasificare se aplică pentru fiecare mulțime. Rezultă m modele. Pentru o instanță de test, fiecare model dă un vot privind apartenența la o clasă. Clasa cu cele mai multe voturi este răspunsul ansamblului. Mulțimile rezultate sunt similare, dar nu foarte similare. Probabilitatea ca o instanță să nu fie selectată la o eșantionare este P1 = 1 – 1 / n. Probabilitatea ca o instanță să nu fie selectată deloc într-o mulțime cu n instanțe este Pn = (1 – 1 / n)n. Când n → ∞, Pn → 1 / e ≈ 0,368. Numai 63% din instanțe vor fi prezente într-o anumită mulțime bootstrapped. Fie m votanți care trebuie să ia o decizie prin vot majoritar (decizia care întrunește jumătate plus unu din voturi). Conform teoremei juriului a lui Condorcet, dacă fiecare votant are o probabilitate p > 0,5 de a lua decizia corectă, adăugarea de noi votanți crește probabilitatea ca ansamblul lor să ia 66

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

decizia corectă. Dacă p < 0,5, adăugarea de noi votanți scade calitatea deciziei. 1.1. Descompunerea subiectivitate-varianță Subiectivitatea (bias) reprezintă rata de eroare a unui model pentru o anumită problemă. Poate fi diferită de 0 chiar dacă există un număr infinit de mulțimi de antrenare sau modele independente. Apare deoarece un model nu se potrivește suficient de bine cu problema (de exemplu, un model liniar pentru date sinusoidale). Varianța este valoarea așteptată a erorii cauzată de faptul că mulțimile de antrenare sunt finite și deci nu reprezintă perfect distribuția instanțelor de antrenare. Când mulțimile sunt mai mari, varianța este mai mică. Când modelul este mai complex, varianța este mai mare. Bagging-ul reduce varianța. Eroarea totală = subiectivitate + varianță + zgomot 1.2. Random Tree Este un algoritm asemănător cu ID3/C4.5, dar într-un nod, se selectează aleatoriu d' atribute din cele d ale datelor, cu 1 ≤ d' ≤ d, și se face împărțirea după cel mai bun dintre acestea. d' poate fi log2(d). Un atribut poate fi folosit de mai multe ori. Partiționarea continuă până când eroarea de clasificare ajunge la 0. Mai rar, se poate da ca parametru de intrare adâncimea maximă a arborelui generat. 1.3. Random Forest Se bazează pe votul a m arbori aleatorii, unde m este un parametru de intrare. Se generează m mulțimi de antrenare bootstrapped și se antrenează câte un arbore aleatoriu pentru fiecare mulțime. Pentru o instanță de test, fiecare arbore dă un vot privind apartenența la o clasă. Clasa cu cele mai multe voturi este răspunsul pădurii aleatorii.

67

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

este una din cele mai bune metode de clasificare „clasice”. Subiectivitatea scade deoarece arborii componenți pot crește foarte mult, până capturează toate detaliile problemei. Varianța scade datorită mulțimilor bootstrapped și medierii rezultatelor individuale ale arborilor componenți. Random Forest

Clasificatorii cu un grad ridicat de neliniaritate, cum ar fi arborii de decizie, beneficiază cel mai mult de avantajele bagging-ului. Arborii de decizie sunt modele instabile: o modificare mică în mulțimea de antrenare poate cauza o modificare mare în arborele generat. Modelele liniare sunt mai stabile și nu beneficiază prea mult de bagging. Stabilitatea crește cu numărul de instanțe de antrenare și scade cu dimensionalitatea problemei.

2. Boosting Un clasificator puternic este o metodă de clasificare care atinge o eroare arbitrar de mică cu o mare probabilitate. Un clasificator slab este o metodă de clasificare cu o eroare mai mică decât 50%, adică este suficient ca metoda să fie puțin mai bună decât o decizie aleatorie. Aceste două tipuri de clasificatoare sunt echivalente. Boosting-ul reprezintă un meta-algoritm prin care, folosind un clasificator slab, se obține un clasificator puternic. 2.1. Adaboost Adaboost (adaptive boosting) este algoritmul care a demonstrat acest lucru, prin construcție. El construiește un clasificator puternic H ca o combinație liniară de clasificatori slabi ht :  T  H (x )  sgn   t ht (x )   t 1 

Ieșirile modelelor H, ht  {–1, 1}.

68

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Se poate folosi orice clasificator, cu condiția ca rata sa de eroare să fie mai mică decât 50%. De obicei, se folosește algoritmul Decision Stump, un arbore de decizie cu un singur nivel, în care criteriul de selecție al atributelor și pragurilor este numărul de erori rezultat: m

ht  argmin  j   Dt (i ) yi  h j ( xi ) h j H

i 1

Se poate folosi și perceptronul cu un singur strat sau algoritmi mai puternici precum Naïve Bayes sau k-Nearest Neighbor. Pseudocod (Freund & Schapire, 1997; Matas & Sochman, 2017):

În următoarea iterație, instanțele clasificate greșit vor avea o pondere mai mare, iar instanțele clasificate corect vor avea o pondere mai mică. Iterațiile pot continua și după clasificarea corectă, pentru creșterea încrederii. Acest lucru este echivalent cu mărirea marginii de separare între clase. Detectorul facial Viola-Jones a fost aplicația care i-a adus popularitate algoritmului Adaboost.

69

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Agregarea în stivă Agregarea în stivă (stacking) reprezintă ponderarea ieșirilor mai multor algoritmi numerici. Se folosește de obicei pentru probleme de regresie, în timp ce pentru clasificare se recurge la votare. De exemplu, mai multe rețele neuronale pot fi agregate în stivă. Prin sumarea ponderată a ieșirilor mai multor rețele individuale, pot crește performanțele de generalizare ale rețelei stivă agregate.

70

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

13. Generalizarea Pentru o mulțime de date de antrenare, pot exista mai multe modele, cu diferite niveluri de complexitate. De exemplu, pentru o problemă de regresie polinomială cu n puncte, se poate utiliza un polinom de gradul n – 1 sau polinoame de orice grad superior. Briciul lui Occam spune că în general trebuie preferată cea mai simplă ipoteză consistentă cu datele deoarece, la egalitate, modelele mai simple tind să generalizeze mai bine decât cele complexe. Un model învățat trebuie să aibă capacitate de generalizare, care arată cât de bun este modelul pentru date noi. De obicei există o mulțime de antrenare pentru crearea modelului și o mulțime de test pentru verificarea capacității de generalizare. Uneori, se folosește și o mulțime de validare, pentru a decide când să se oprească antrenarea sau pentru a alege arhitectura cea mai potrivită a modelului. Mulțimea de validare nu este folosită pentru determinarea parametrilor modelului, ci pentru estimarea calității sale. De exemplu, o rețea neuronală se antrenează doar cu mulțimea de antrenare, dar observăm eroarea pe mulțimea de validare și oprim antrenarea când aceasta începe să crească. Alternativ, observăm erorile pentru un număr diferit de neuroni în stratul ascuns și alegem numărul cel mai potrivit. Generarea mulțimii de test se poate face prin mai multe metode: 



Împărțirea 2/3 – 1/3: Se împart datele în 2/3 pentru antrenare și 1/3 pentru testare. Metoda este simplă și are avantajul de a crea și un model unic, dar depinde de selecția datelor incluse în cele două mulțimi; Validarea încrucișată (cross-validation): Se împart datele în n grupuri (de obicei 10), n – 1 pentru antrenare, al n-lea pentru testare și procesul se repetă de n ori. Este standardul de facto pentru compararea modelelor. Are avantajul folosirii tuturor datelor; 71

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



Leave one out: n – 1 instanțe sunt folosite pentru antrenare, iar a n-a pentru testare. Procesul se repetă de n ori. Este o formă de validare încrucișată pentru situațiile în care există puține date.

La antrenare, pot apărea două fenomene:  

Subpotrivirea (underfitting): ipoteza este prea simplă și nu poate învăța modelul din date; Suprapotrivirea (overfitting): ipoteza este prea complexă și poate fi influențată de zgomot și date irelevante. Un model suprapotrivit are performanțe foarte bune pe mulțimea de antrenare, dar performanțe slabe pe mulțimea de validare/test.

72

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

14. Selecția trăsăturilor Atributele mulțimii de antrenare pot avea grade diferite de relevanță. De exemplu, sexul unei persoane este mai puțin relevant pentru predicția diabetului decât vârsta. Unele atribute pot fi complet irelevante. Selecția trăsăturilor identifică atributele care pot contribui cel mai mult la predicția clasei.

1. Metode de filtrare (filter) O primă abordare se bazează pe un criteriu matematic (formulă) pentru a evalua calitatea fiecărui atribut sau grup de atribute, de exemplu: indexul Gini respectiv entropia, pentru atribute simbolice, unde distingem: 

importanța unei valori de atribut: k

G (vi )  1   p 2j j 1

k

E (vi )   p j  log 2 p j j 1



importanța unui atribut:

ni G (vi ) i 1 n r n E   i E (vi ) i 1 n r

G

În formulele de mai sus, vi reprezintă valorile posibile ale atributului considerat, pj este fracțiunea de instanțe care conțin valoarea vi și care aparțin clasei j, n este numărul total de instanțe și ni este numărul de instanțe care conțin valoarea vi.

73

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Pentru atribute numerice, se poate utiliza scorul Fisher, care măsoară raportul dintre separarea medie inter-clasă și separarea medie intraclasă: k

F

p j 1

j

 (  j   )2

k

p j 1

j

  2j

Aici, μj, σj, pj reprezintă media, deviația standard și fracțiunea de instanțe care aparțin clasei j, iar μ este media globală a tuturor instanțelor pentru atributul considerat. Un atribut este cu atât mai important cu cât indexul Gini sau entropia au valori mai mici. Valoarea 0 înseamnă că atributul poate rezolva singur problema de clasificare. Un atribut este cu atât mai important cu cât scorul Fisher are valori mai mari. O altă abordare este cea algoritmică, de exemplu, algoritmul Relief. În cadrul acestuia, se inițializează ponderile atributelor cu 0. Pentru fiecare instanță xq din mulțimea de antrenare sau pentru o instanță xq selectată aleatoriu, se găsește cea mai apropiată instanță din aceeași clasă (hit) și cea mai apropiată instanță dintr-o clasă diferită (miss). Se actualizează ponderile fiecărui atribut pe baza acestor distanțe. Un atribut este mai important dacă pe dimensiunea sa instanțele sunt mai depărtate de instanțele din alte clase și mai apropiate de cele din aceeași clasă (dhit mică, dmiss mare). Pseudocod (Kononenko, 1994):

74

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Metode de acoperire (wrapper) Folosesc un algoritm de clasificare pentru a determina importanța atributelor, de exemplu, căutarea în spațiul atributelor. Aici, se stabilește algoritmul de clasificare folosit și se caută în mod greedy în spațiul atributelor. Pot exista două direcții de căutare:  

Selecție înainte (prin progresie): de la niciun atribut, adăugând câte un atribut o dată; Eliminare înapoi (prin regresie): de la toate atributele, eliminând câte un atribut o dată.

La fiecare pas, este evaluat efectul adăugării sau eliminării unui atribut prin validare încrucișată, cu algoritmul de clasificare considerat. Când niciun atribut nu mai produce o îmbunătățire a rezultatelor, căutarea se oprește. Pentru a favoriza mulțimile mai mici de atribute, la selecția înainte se poate impune condiția ca procentul de erori să scadă cu o anumită valoare minimă (similar pentru eliminarea înapoi).

3. Metode încorporate (embedded) Învață calitatea atributelor în timp ce este creat modelul. În general, aici intră metodele de regularizare.

75

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

15. Regresia liniară, logistică, softmax 1. Regresia liniară. Regularizarea Multe procese din lumea reală pot fi aproximate cu modele liniare. Regresia liniară apare deseori în modulele unor sisteme mai complexe precum perceptronul, Adaboost etc. Spre deosebire de alte modele, problemele linare pot fi rezolvate analitic. Metodologia aplicată aici poate fi aplicată și pentru alte modele, de exemplu, regresie polinomială etc. Pe lângă aproximarea datelor de antrenare, ne interesează și capacitatea de generalizare. Un model liniar definește un hiperplan de separare. Dacă problema este liniar separabilă, ea poate fi învățată. Dacă nu, ne interesează un model care face cât mai puține erori:

min 1 yi  w  xi  b  0 w, b

i

Această funcție este rata de eroare sau funcția de cost 0/1. 1[∙] este funcția indicator: 1[adevărat ] = 1 și 1[fals] = 0. Aici, funcția indicator este folosită pentru a număra instanțele clasificate greșit. yi este ieșirea dorită pentru instanța i, yi  {–1, 1}. (w ∙ xi + b) este ieșirea reală a modelului, iar yi ∙ (w ∙ xi + b) este marginea. Problema de optimizare este NP dificilă atât de rezolvat exact cât și de aproximat cu o precizie arbitrară. Motivul este că o schimbare mică în parametri poate determina o schimbare mare în clasificare, între 0 și 1. Problema de optimizare anterioară se referă la minimizarea numărului de erori pe mulțimea de antrenare, nu se referă la performanțele pentru date noi. În acest scop, se introduce un termen de regularizare:

min 1 yi  w  xi  b  0  R( w, b) w, b

i

Primul termen impune minimizarea numărului de erori de antrenare. Al doilea termen impune determinarea unui model cât mai simplu, care să 76

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

generalizeze cât mai bine. De cele mai multe ori, pentru termenul de regularizare se folosește norma euclidiană: R( w, b)  w   wd2 2

d

Prin reducerea valorilor parametrilor modelului, se dorește să se prevină suprapotrivirea (overfitting). Funcțiile de cost (loss functions) definesc limite superioare ale ratei de eroare. Prin minimizarea lor, se minimizează și rata de eroare. Există multe funcții de cost: 0/1

l ( y, yˆ )  1y  yˆ  0

Hinge

l ( y, yˆ )  max( 0, 1  y  yˆ )

Logistică

l ( y, yˆ )  log 2 1  exp(  y  yˆ )

Exponențială

l ( y, yˆ )  exp(  y  yˆ )

Pătratică

l ( y, yˆ )  ( y  yˆ ) 2

unde yˆ  w  x  b . De exemplu, Decision stump folosește funcția de cost 0/1, perceptronul multistrat folosește funcția de cost pătratică, iar Adaboost folosește funcția de cost exponențială. O problemă de regresie liniară se poate rezolva cu metoda gradientului descendent. Funcția obiectiv este:

J ( w) 

1 n w1  w2  xi  yi 2   w  2 i 1 2

2

cu: 2

w  w12  w22

unde xi sunt intrările instanțelor, iar yi sunt ieșirile dorite.

77

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Gradienții celor doi parametri w1 și w2 ai modelului sunt:

g1 

g2 

n J ( w)  n      yˆ i  yi     w1   ei    w1 w1 i 1  i 1 

n J ( w)  n      yˆ i  yi   xi     w2   ei  xi    w2 w2 i 1  i 1 

unde ei reprezintă eroarea pentru instanța i. Procesul este iterativ, iar după fiecare epocă parametrii se actualizează pe baza gradienților, cu o rată de învățare α:

wi  wi    gi Iterațiile se pot termina când a fost atins un număr maxim prestabilit de iterații, când funcția obiectiv nu se mai modifică mult sau când parametrii nu se mai modifică mult. Problemele de regresie liniară se pot rezolva și matriceal:

ˆ  XW Y  yˆ1   1 x11 ... x1d   w1         ...    ... ... ... ...    ...   yˆ   1 x ... xnd   wn  n1  n  W  XT  X   XT  Y 1

Adăugând regularizarea:

W  XT  X  I D   XT  Y 1

Pentru un număr mic și mediu de dimensiuni (de exemplu, mai mic de 100), este preferabilă metoda matriceală. Pentru un număr mare, se preferă metoda diferențială. 78

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Regresia logistică Structura modelului este cea a unui perceptron cu un singur strat. Totuși, ieșirea este interpretată aici ca probabilitatea de apartenență la o clasă:

P( yi  1 | xi , w) 

1   wT  xi   pi T 1  exp(  w  xi )

P( yi  0 | xi , w)  1  P( yi  1 | xi , w)  1   wT  xi   1  pi Funcția de cost pentru antrenarea cu gradienți se bazează pe MLE (estimarea verosimilității maxime, maximum likelihood estimation). Funcția obiectiv este următoarea (cross-entropy):

J (w)    yi  log pi  1  yi   log(1  pi )  i

unde yi reprezintă ieșirile datelor de antrenare, iar pi reprezintă ieșirile modelului. Scopul este ca probabilitățile modelului să fie cât mai apropiate de datele de antrenare. Gradienții parametrilor sunt: J (w ) n   xij  pi  yi  w j i 1

3. Regresia softmax Funcția softmax generalizează expresia regresiei logistice la situația cu mai multe clase: exp( ai ) s ( ai )  k s : ℝk → ℝk  exp( a j ) j 1

79

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Funcția indică probabilitățile ca o instanță să aparțină fiecărei clase. Funcția obiectiv este:

   n k  T exp( w j x i )  1 J ( w )   1  yi  j log k  n  i 1 j 1 exp( w Tl x i )    l 1   iar gradienții: J ( w) 1 n    x i 1 yi  j   P yi  j | x i , w  w j n i 1

Pentru regularizare, la expresia lui J se adaugă termenul:



n

k

 w 2 i 0 j 1

2 ij

iar la expresia gradienților se adaugă termenul:

wj Când clasele sunt mutual exclusive, se recomandă regresia softmax (de exemplu: muzică clasică, country, rock, jazz). Pe lângă cele patru clase, se mai poate adăuga una: „alte genuri muzicale”. Altfel, se recomandă k clasificatori binari, precum regresia logistică, iar fiecare decide dacă o instanță aparține sau nu unei clase (de exemplu: cu solist vocal, coloană sonoră, dance). Chiar dacă toate cele trei metode prezentate au în denumire cuvântul „regresie”, regresia liniară este de fapt singurul algoritm de regresie propriuzisă, în care ieșirea este continuă. Regresia logistică și regresia softmax sunt de fapt algoritmi de clasificare, cu două, respectiv oricâte clase.

80

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

4. Metrici de eroare 4.1. Metrici de eroare pentru modele numerice

 p1  a1 2  ...   pn  an 2

Eroarea medie pătratică (mean squared error)

n

 p1  a1 2  ...   pn  an 2

Radicalul erorii medii pătratice (root mean squared error)

n

p1  a1  ...  pn  an

Eroarea medie absolută (mean absolute error)

n

 p1  a1 2  ...   pn  an 2 a1  a 2  ...  an  a 2

Eroarea pătratică relativă (relative squared error)

 p1  a1 2  ...   pn  an 2 a1  a 2  ...  an  a 2

Radicalul erorii pătratice relative (root relative squared error)

p1  a1  ...  pn  an

Eroarea absolută relativă (relative absolute error)

a1  a  ...  an  a

 p

Coeficientul de corelație (correlation coefficient)

i

 p

i

 p   ai  a 

 p  2

 a

i

 a

2

În formulele de mai sus, ai sunt valorile de antrenare, pi sunt valorile prezise, iar x reprezintă valoarea medie a datelor x. Cele mai des utilizate metrici sunt eroarea medie pătratică (MSE) și coeficientul de corelație (r).

81

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

4.2. Matricea de confuzii Fiecare element al matricei arată numărul de instanțe pentru care clasa dorită este dată de linie și clasa prezisă de model este dată de coloană. Rezultate bune se obțin atunci când diagonala principală are numere mari. De exemplu (fig. Witten & Frank, 2000):

Aici, rata de eroare este: 1 – (88+40+12) / 200 = 0,3.

82

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

16. Rețele neuronale 1. Perceptronul standard Este un model de neuron artificial în care semnalele de intrare sunt sumate, iar un semnal de ieșire este generat doar dacă suma depășește pragul.

 n  y  f   wi xi     i 1  Perceptronul are ponderi sinaptice ajustabile și funcție de activare semn sau treaptă:

 1 dacă a  0 f (a )   dacă a  0 1 0 dacă a  0 f (a )   1 dacă a  0 Scopul perceptronului este să clasifice o instanță într-una din două clase. Spațiul intrărilor, n-dimensional, este împărțit în două de un hiperplan definit de ecuația: 83

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

n

w x i 1

i i

  0

Pragul poate fi considerat o pondere suplimentară, cu intrarea tot timpul 1 sau –1. Acest fapt simplifică formula de calcul a ieșirii:

 n 1  y  f   wi xi   i 1  Învățarea are loc prin ajustarea succesivă a ponderilor pentru a reduce diferența dintre ieșirile reale (y) și ieșirile dorite (yd), pentru toate datele de antrenare. Regula de învățare a perceptronului este: Δw = α ∙ x ∙ e unde Δw este corecția ponderii, α este rata de învățare, x este intrarea, iar e este eroarea (yd – y). Perceptronul standard (cu un singur strat) poate învăța tot ce poate reprezenta, dar nu poate reprezenta multe funcții. Mai ales, nu poate reprezenta funcții neseparabile liniar, de exemplu, XOR.

2. Adaline Adaline este un tip de neuron asemănător perceptronului, dar are funcție de activare liniară și se antrenează diferențial. n 1

y   wi xi i 1

Eroarea folosită este eroarea pătratică:

Ei 

1  ydi  yi 2 2 84

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Antrenarea presupune minimizarea erorii în raport cu ponderile. Regula de ajustare a ponderilor este aceeași ca la perceptron. În cazul unei funcții de activare f neliniare, dar derivabile, regula delta este:

Ei   xij  y di  yi  f ' ( yi ) w j de unde se deduce:

w j    xij  ei  f ' ( yi )

3. Perceptronul multi-strat Perceptronul multi-strat este o rețea neuronală cu propagare înainte (feed-forward) cu unul sau mai multe straturi ascunse. El are:   

Un strat de intrare (care nu face procesări); Unul sau mai multe straturi ascunse (intermediare); Un strat de ieșire. De exemplu (după Negnevitsky, 2004):

85

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Proprietatea de aproximare universală. O rețea neuronală cu un singur strat ascuns, cu un număr posibil infinit de neuroni, poate aproxima orice funcție reală continuă. Din punct de vedere practic, un strat nu poate avea un număr infinit de neuroni. Un strat suplimentar poate reduce foarte mult numărul de neuroni necesari în straturile ascunse. Funcțiile de activare pentru perceptronul multi-strat trebuie să fie neliniare. Cel mai des utilizate sunt sigmoida unipolară (sau logistică), respectiv sigmoida bipolară (tangenta hiperbolică):

f ( x) 

1 1  ex

1  e 2 x f ( x)  1  e 2 x

Un perceptron cu un singur strat are aceleași limitări chiar dacă folosește o funcție de activare neliniară. Un perceptron multi-strat cu funcții de activare liniare este echivalent cu un perceptron cu un singur strat.

86

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

4. Algoritmul de retro-propagare (backpropagation) Are două faze:  

Rețeaua primește vectorul de intrare și propagă semnalul înainte, strat cu strat, până se generează ieșirea; Semnalul de eroare este propagat înapoi, de la stratul de ieșire către stratul de intrare, ajustându-se ponderile rețelei:

w jk    y j   yk 1  yk  ek wij    xi  y j 1  y j   k w jk k

Metoda momentului presupune adăugarea unui termen la regula delta, care accelerează și stabilizează căutarea:

wij ( p)    wij ( p  1)    xi  y j 1  y j   k ( p)  w jk k

Rata de învățare poate fi de asemenea modificată în mod adaptiv pe parcursul antrenării. Dacă variația sumei erorilor pătratice ΔE are același semn algebric pentru mai multe epoci consecutive, atunci rata de învățare α trebuie să crească. Dacă semnul lui ΔE alternează timp de câteva epoci consecutive, atunci rata de învățare α trebuie să scadă.

87

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

17. Mașini cu vectori suport 1. Maximizarea marginii. Probleme liniar separabile Pentru o problemă de clasificare liniar separabilă cu două clase, există multe limite de separație posibile. Teoria mașinilor cu vectori suport (Support Vector Machines, SVM) consideră că suprafața care separă clasele trebuie să fie cât mai departe de datele din ambele clase, adică marginea determinată de limita de decizie trebuie maximizată. Instanțele de antrenare care se găsesc pe linia de demarcație a marginii se numesc vectori suport.

Pentru clasificarea unei instanțe x, se folosește următoarea funcție: h(x) = g(wTx + b) unde g este funcția semn:

 1 dacă z  0 g( z)   dacă z  0 1 Prin urmare, instanțele dintr-o clasă vor avea ieșirea y = 1, iar instanțele din cealaltă clasă vor avea ieșirea y = –1. Acest efect de a împărți spațiul problemei în două este același ca la perceptron. 88

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Maximizarea marginii se poate face rezolvând o problemă de optimizare numită problemă primară:

min w ,b

astfel încât:

echivalent cu:

1 w 2

2

yi  wT x i  b  1, i  1, ..., m gi   yi  wT x i  b  1  0, i  1, ..., m

Dificultatea acestei probleme constă în faptul că dimensionalitatea ei (numărul de atribute) poate fi foarte mare și există câte o constrângere pentru fiecare instanță. De aceea, soluția poate fi determinată transformând problema primară în problema duală cu ajutorul dualității Lagrange: m

max  i  α

i 1

1 m m  yi y ji j x i , x j 2 i 1 j 1

astfel încât:

i  0, i  1, ..., m m

 y i 1

i

i

0

Aici, trebuie determinați coeficienții αi , câte unul pentru fiecare instanță de antrenare. Majoritatea αi vor fi 0, cu excepția celor corespunzători vectorilor suport. Avantajul este că numărul vectorilor suport este mult mai mic decât numărul instanțelor de antrenare. Există algoritmi speciali pentru rezolvarea problemei duale. Cel mai cunoscut este algoritmul Sequential Minimal Optimization (SMO), care este rapid și deci foarte potrivit pentru optimizarea problemelor de dimensiuni mari cu care lucrează de obicei SVM.

89

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

și b:

Rezolvând problema duală, se determină αi , iar apoi se calculează w m

w   i y i x i i 1

b

1      y s   t y t x s , x t  S sS  tS 

unde S este mulțimea vectorilor suport, iar |S| este numărul lor.

2. Probleme neseparabile liniar. Nuclee Atunci când clasele nu sunt liniar separabile, datele de antrenare se pot proiecta într-un spațiu cu mai multe dimensiuni, unde devin liniar separabile. Acest lucru se face cu o funcție ϕ(x) numită transformare în trăsături (feature mapping). Se definește un nucleu (kernel) ca fiind o funcție: K(x, z) = ϕ(x)T · ϕ(z). Un nucleu poate fi interpretat ca o măsură a similarității dintre cele două argumente.

90

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Cantitatea necesară pentru clasificare este: T

m  m  w x    i y i x i  x  b   i y i x i , x  b i 1  i 1  T

Se poate observa că toate calculele se fac doar în perechi (xi, x), unde xi este o instanță de antrenare, iar x este instanța care trebuie clasificată. În cazul liniar, se folosește produsul scalar dintre xi și x. În cazul în care folosim transformarea datelor, clasificarea va fi făcută cu un nucleu: m

f (x)   i yi K x i , x   b i 1

Deoarece calculele se fac doar în perechi, nu este nevoie să calculăm explicit trăsăturile instanțelor ϕ(x). Calcularea nucleului unei perechi de instanțe este de obicei mult mai simplă. Acesta este trucul nucleului (kernel trick). Folosind doar nucleul, nu mai este nevoie să calculăm funcția ϕ. Nucleul ar putea avea orice formă, dar trebuie să respecte condiția K(x, z) = ϕ(x)T · ϕ(z), chiar dacă nu cunoaștem sau nu ne interesează forma lui ϕ. Fie matricea nucleului K o matrice în care elementele Kij = K(xi , xj). Teorema lui Mercer. Condiția necesară și suficientă pentru ca un nucleu real să fie valid este ca matricea nucleului să fie simetrică (Kij = Kji) și pozitiv semidefinită (zT · K · z ≥ 0, z). De obicei, se folosesc următoarele nuclee: 

Nucleul liniar: K (x, z)  x T z ;



Nucleul polinomial: K (x, z)  ( xT z  r ) d ;



Nucleul gaussian: K (x, z)  exp   x  z



91

2

;

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



Nucleul sigmoid (este funcția de activare de la perceptronul multi-strat, dar uneori nu este valid conform teoremei lui Mercer): K (x, z)  tanh( xT z  r ) .

3. Margini flexibile În unele cazuri, datele nu sunt separabile liniar nici după transformările prezentate anterior sau prezintă valori extreme (outliers) care influențează marginea optimă. În acest caz, se poate permite existența unor erori ξi în clasificare. Hiperplanul are acum o margine flexibilă (soft margin). ξi se numesc variabile de decalaj (slack variables).

Problema de optimizare primară devine: m 1 2 min w  C  i w ,b 2 i 1

astfel încât:

yi  wT x i  b  1  i

i  0 unde parametrul de cost C este o măsură a erorii admise în clasificare. 92

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

C controlează compromisul dintre a permite erori pe mulțimea de antrenare și a forța margini stricte. Creșterea valorii lui C mărește costul clasificării greșite a instanțelor și determină crearea unui model mai precis, dar care poate să nu generalizeze bine. Dacă C este mare, marginea de separare va fi mai mică. Dacă C este mic, marginea de separare va fi mai mare. Problema duală este: m

max  i  α

i 1

1 m m  yi y ji j x i , x j 2 i 1 j 1

astfel încât:

0  i  C m

 y i 1

i

i

0

Termenii ξi nu apar în problema duală. Contează numai parametrul C, care limitează multiplicatorii αi. Pentru instanțele neclasificabile, multiplicatorii ar crește foarte mult și ar determina și apariția unor vectori suport (cu αi > 0) suplimentari.

4. Clasificarea cu clase multiple Modelele SVM standard permit rezolvarea problemelor binare, cu numai două clase. Pentru a trata mai multe clase există mai multe metode, dintre care cele mai des folosite sunt: 

Abordarea „una versus toate” (one-versus-all / one-against-all): Pentru k clase, se creează k modele. În modelul cu numărul i, SVM este antrenat cu instanțele din clasa i ca exemple pozitive și toate celelalte instanțe (din celelalte clase) ca exemple negative. Pentru a clasifica o nouă instanță, se apelează toate cele k modele și se alege clasa cu funcția de decizie maximă: 93

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

C  argmax f (x) i1..k



Abordarea „una versus una” (one-versus-one / one-against-one): Pentru k clase, se creează k ∙ (k – 1) / 2 modele corespunzătoare tuturor perechilor de clase. Pentru a clasifica o nouă instanță, se apelează toate modelele și fiecare model dă un vot pentru apartenența la o clasă. Se alege în final clasa care are cele mai multe voturi. Antrenarea poate fi mai rapidă pentru că mulțimile de antrenare sunt mai mici.

94

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

18. Rețele neuronale profunde 1. Comparație între rețelele neuronale clasice și profunde 



Rețele clasice: o 1-2 straturi; o Funcții de activare sigmoide; o Funcții de cost bazate pe MSE; o Algoritmi de antrenare: backpropagation, RProp, LevenbergMarquardt etc.; Rețele profunde: o Mai multe straturi; o Funcții de activare mai simple: ReLU; o Funcții de cost bazate pe MLE; o Algoritmi de antrenare: SGD, RMSProp, Adam etc.; o Alte metode de inițializare a ponderilor, regularizare, preantrenare.

Evident, diferența principală este numărul de straturi. Dincolo de acesta, diferențele nu sunt stricte. De exemplu, și neuronii unei rețele profunde pot avea funcții de activare sigmoide. Dar o rețea clasică cu mai multe straturi poate avea probleme la antrenare. Primele straturi ale unui perceptron multi-strat clasic cu un număr mai mare de straturi ascunse nu se antrenează bine. Când ponderile sunt mici sau funcțiile de activare sigmoide sunt saturate (gradienți mici), corecțiile ponderilor Δw sunt mici, iar antrenarea este foarte lentă. De asemenea, ultimele straturi, cele apropiate de ieșire, pot învăța problema „destul de bine” și deci semnalul de eroare trimis către primele straturi devine și mai mic. De aceea, sunt necesare alte metode de antrenare pentru a pune în valoare primele straturi.

95

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

1.1. Funcții de activare O funcție de activare tipică pentru arhitecturi profunde este ReLU (Rectified Linear Unit):

f ( x)  max( 0, x)

Este o funcție neliniară cu gradienți foarte ușor de calculat:

df 0 dacă x  0  dx 1 dacă x  0 Chiar dacă în partea negativă gradientul este 0, în practică funcționează bine. S-a observat că învățarea este de circa 6 ori mai rapidă față de funcțiile sigmoide. Totuși, pentru a evita problemele date de faptul că partea negativă nu contribuie la învățare, s-au propus unele variante alternative: Leaky ReLU

dacă x  0 x f ( x)   0.01x altfel

96

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Parametric ReLU

(PReLU), unde parametrul a poate fi învățat:

 x dacă x  0 f ( x)   ax altfel

1.2. Funcții de cost Pentru rețele profunde, se preferă funcții de cost bazate pe MLE (Maximum Likelihood Estimation), de exemplu, cross-entropy, softmax etc. 1.3. Algoritmi de antrenare Algoritmii sunt bazați tot pe ideea de gradient descendent, la fel ca backpropagation clasic, dar au apărut variante specializate sau îmbunătățite: 



Stochastic Gradient Descent :

Pentru problemele actuale, numărul instanțelor de antrenare poate fi foarte mare. SGD lucrează asemănător cu gradientul descendent, dar nu ia în calcul toate instanțele la calcularea gradienților, ci doar un mini-lot (minibatch). La fiecare iterație, se aleg aleatoriu alte instanțe. Gradienții sunt doar o aproximație a gradienților reali. Complexitatea de timp poate fi controlată prin dimensiunea mini-lotului. La algoritmul standard se pot adăuga variantele ratei de învățare descrescătoare și a momentului; RMSProp (Root Mean Square Propagation) : Se bazează pe ideea adaptării ratei de învățare invers proporțional cu suma pătratelor gradienților. Rata de învățare scade rapid pentru parametrii cu gradienți mari și mai încet pentru cei cu gradienți mici. Nu se folosește direct suma istorică, ci o medie glisantă (moving average), care elimină efectele trecutului îndepărtat. Altfel, prin traversarea unor zone neconvexe ale spațiului problemei, rata de învățare ar putea deveni prea mică înainte ca algoritmul să ajungă într-o zonă convexă local, unde se găsește soluția. La fel ca metoda momentului,

97

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



are ca efect atenuarea oscilațiilor și permite mărirea ratei de învățare, ceea ce accelerează învățarea; Adam (Adaptive Moment) : Poate fi văzut ca o combinație între metoda momentului și algoritmul RMSProp. 1.4. Inițializarea ponderilor

Ideea de bază pentru aceste metode de inițializare este că ponderile trebuie să aibă media 0 și o varianță specificată. La propagarea înainte într-o rețea profundă, se dorește ca varianța semnalului să rămână constantă. 1.4.1. Inițializarea Xavier (Glorot) Fie ni numărul de neuroni cu care este conectat la intrare un neuron considerat (fan-in), care are ponderile Wi , iar ni+1 numărul de neuroni cu care este conectat la ieșire (fan-out). N reprezintă distribuția normală, iar U cea uniformă. Așadar, ponderile se pot inițializa astfel:

 2   Wi ~ N  0,  n  n i i 1    6 6 Wi ~ U   , ni  ni 1 ni  ni 1 

   

1.4.2. Inițializarea Kaiming (He) Se utilizează pentru funcții de activare de tip ReLU. a este parametrul porțiunii negative din PReLU. Pentru ReLU simplu, a = 0. Ponderile se pot inițializa astfel:

 2 Wi ~ N  0, (1  a 2 ) ni 

98

   

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

1.5. Dropout este o formă de regularizare. Efectul său este asemănător cu ideea de la bagging. Simulează antrenarea unor rețele diferite prin dezactivarea aleatorie a unor neuroni în timpul antrenării. Aceste subrețele sunt parte a rețelei originare, iar ponderile sunt comune. Dropout-ul previne suprapotrivirea (overfitting). În mod ideal, fiecare neuron din rețea ar trebui să detecteze trăsături în mod independent. Dacă mai mulți neuroni detectează aceleași trăsături în mod repetat, fenomenul se numește co-adaptare. Dropout-ul previne și co-adaptarea. Eliminarea unor neuroni de intrare are efecte foarte puternice. În lipsa unor intrări, rețeaua trebuie să compenseze prin găsirea altor trăsături importante pentru clasificare. De exemplu, pentru recunoașterea unei fețe, dacă din imagine se elimină nasul, rețeaua trebuie să fie capabilă să găsească alte indicii, de exemplu, ochii sau gura. Dropout

2. Autoencodere Un autoencoder învață funcția identitate: h(x) = x (fig. Ng, 2010).

99

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

De

multe ori, se folosesc autoencodere subcomplete (undercomplete), unde |h| < |x|. Stratul ascuns este o versiune comprimată a intrării. Autoencoderele reprezintă astfel o metodă de reducere a dimensionalității problemei, ceea ce ajută învățarea întrucât majoritatea modelelor de învățare presupun reținerea trăsăturilor esențiale ale datelor. sunt antrenate cu intrări corupte, pe care încearcă să le corecteze (de-noise). Antrenarea acestora se desfășoară precum urmează. Intrările sunt corupte prin adăugarea de zgomot. Intrările corupte intră în autoencoder. Funcția de cost se calculează prin compararea ieșirii autoencoderului cu intrările necorupte. Denoising autoencoders

Autoencoderele pot fi agregate în stive (stacked autoencoders). Scopul lor este comprimarea succesivă a dimensiunii intrărilor, astfel încât se rețin trăsăturile esențiale, de ordin mai înalt, ale acestora. Antrenarea este greedy nivel cu nivel. Fiecare nivel se antrenează pe baza codurilor intermediare ale nivelului precedent. Ultimul nivel are de obicei o ieșire, de exemplu softmax, care realizează clasificarea pe baza trăsăturilor detectate. În final, se folosește algoritmul backpropagation pentru reglarea supervizată a ponderilor (fine tuning) (fig. Ng, 2010).

100

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

(VAE) este un model în care se determină o distribuție parametrică, de obicei de tip gaussian, care aproximează datele de intrare. Avantajul este că pot fi eșantionate noi exemple din această distribuție, generând astfel date noi, din distribuția datelor de intrare. De exemplu, dacă VAE se antrenează cu fețe de persoane, eșantionând distribuția ascunsă (codul), se pot genera („inventa”) fețe noi, care nu aparțin unor persoane reale din mulțimea de antrenare (fig. Shiffman, 2016). Variational Autoencoder

101

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

19. Modele bazate pe energie 1. Modelul Ising Modelul Ising este un model al feromagnetismului, cu variabile discrete care reprezintă momentele magnetice ale spinurilor atomice. Modelul se bazează pe o latice a momentelor magnetice ale atomilor. Energia unei stări este:

E s     J ij si s j  M  H i si (i, j )

i

unde (i, j) reprezintă perechile de atomi vecini, Jij este puterea interacțiunii vecinilor (i, j ), Hi este un câmp magnetic extern, M este momentul magnetic și T este temperatura. Probabilitatea unei stări este:

PT ( s ) 

e  E ( s ) /( k B T ) Z

cu Z un factor de normalizare:

Z   e E ( s ) /( k B T ) s

Acest sistem tinde către o stare cu energie minimă. Atomii vecini au tendința să își modifice orientarea spinului pentru a se alinia cu vecinii, dacă aceasta scade energia sistemului. Un atom își schimbă întotdeauna orientarea spinului când configurația rezultată are o energie mai mică (Enext < Ecrt). Dar chiar dacă energia este mai mare (Enext > Ecrt), își poate schimba orientarea cu probabilitatea P = exp(–ΔE / T), unde ΔE = Enext – Ecrt. Aceasta este chiar ideea de optimizare prin călire simulată.

102

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

O temperatură mică determină un comportament feromagnetic (sistemul este magnetizat). O temperatură mare determină un comportament paramagnetic (sistemul nu este magnetizat).

2. Rețele Hopfield 2.1. Procesul de învățare În creierele biologice, memoria lucrează prin asociere. Oamenii pot recunoaște o față cunoscută într-un mediu necunoscut în 100-200 ms sau pot rememora o întreagă experiență senzorială, vizuală și auditivă când aud primele măsuri ale unei melodii. Perceptronul multi-strat nu lucrează prin asociere. Pentru emularea acestei capacități, este nevoie de un alt tip de rețea neuronală: o rețea recurentă, care are bucle de reacție de la ieșiri către intrări (fig. Negnevitsky, 2004).

În figura de mai sus, sunt prezentate trei perspective asupra unei rețele Hopfield cu n neuroni. 103

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Rețeaua Hopfield este o memorie auto-asociativă: își poate aminti modelele stocate, își poate aminti un model dacă primește doar o parte din el și își poate aminti modelele dacă primește versiuni similare, dar nu identice, sau versiuni afectate de zgomot. Rețeaua Hopfield folosește neuroni cu funcție de activare semn:

 1 dacă X t  0  Y t 1   1 dacă X t  0 Y t dacă X t  0  Starea curentă a rețelei este determinată de ieșirile tuturor neuronilor: Y = (y1, y2, ..., yn). Y se numește vector de stare. Ponderile se reprezintă de obicei în formă matriceală și se calculează astfel: M

W   Ym YmT  M  I m 1

unde M este numărul de stări care trebuie memorate, Ym este un vector de antrenare binar n-dimensional și I este matricea identitate de dimensiune n x n. Testarea rețelei presupune determinarea ieșirii pentru o intrare anume, cu ponderile calculate prin formula anterioară:

Y  sgn W  X  Stările stabile (numite și amintiri fundamentale) sunt capabile să atragă stările apropiate. Astfel, o rețea Hopfield are capacitatea de a corecta erorile din stările prezentate. Antrenarea rețelei Hopfield este o formă de învățare hebbiană.

104

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2.2. Procesul de optimizare În descrierea anterioară a rețelei Hopfield, nu au fost luate în calcul pragurile neuronilor. Dacă se includ și pragurile θ, energia rețelei pentru un vector de stare x este:

1 E (x )   x w x T  θ x T 2

E (x)  

n 1 n n w x x   i xi  ij i j  2 i 1 j 1 i 1

Pentru a descrie capacitatea de optimizare a unei rețele Hopfield, să considerăm ca exemplu problema plasării turnurilor pe o tablă de șah, astfel încât să nu se atace reciproc. Fie xij starea neuronului corespunzător celulei de pe poziția (i, j ). xij este 1 dacă în celulă este un turn și 0 dacă nu. Avem două condiții care definesc problema de optimizare: pe fiecare coloană trebuie să fie doar un turn (C1) și pe fiecare linie trebuie să fie doar un turn (C2). Pentru condiția C1, trebuie minimizată funcția:

 n   E1      xij   1 j 1   i 1   n

2

Pentru condiția C2, trebuie minimizată funcția:

 n   E2      xij   1   i 1   j 1   n

2

Trebuie găsite ponderile și pragurile care minimizează energia E = E1 + E2. Pentru rețea, se poate folosi arhitectura de mai jos, în care nu s-au reprezentat toate conexiunile pentru a nu aglomera figura.

105

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Ponderile conexiunilor între neuronii de pe aceeași linie sau coloană sunt –2. Celelalte ponderi sunt 0. Un neuron „aprins” pe o linie sau coloană îi inhibă pe ceilalți. Toate pragurile sunt –1. Dacă niciun alt neuron nu este aprins pe linie sau coloană, se aprinde neuronul curent. Se pornește cu un vector de intrare x generat aleatoriu, cu elemente de 0 și 1 (în loc de –1 și 1; așa este definită aici problema). Se actualizează în mod repetat starea rețelei (sau până când aceasta nu se mai modifică). Pentru a asigura stabilitatea, neuronii trebuie activați secvențial și în ordine aleatorie. Problema are mai multe soluții. Rețeaua converge la o soluție, care poate fi diferită la fiecare rulare. De exemplu:

0  1 Y 0  0

0 0 1 0

106

0 0 0 1

1  0 0  0 

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Mașini Boltzmann Filosofia acestor modele se bazează pe ipoteza creierului anticipativ. Creierul realizează un model generativ probabilistic al lumii, care este folosit pentru a anticipa sau prezice stările mediului. Inversul modelului poate fi folosit pentru a recunoaște cauzele unor evenimente externe prin evocarea conceptelor interne. Conceptele interne sunt învățate prin potrivirea ipotezelor generate de creier cu intrările senzoriale din mediu. Învățarea apare prin testarea activă a ipotezelor prin acțiuni. Creierul încearcă să potrivească intrările senzoriale externe cu stările generate intern. O mașină Boltzmann este asemănătoare cu rețeaua Hopfield, dar distinge între noduri vizibile (~ intrările senzoriale) și noduri ascunse (~ stările generate de creier). Activările neuronilor sunt stohastice, nu deterministe.

Energia rețelei are aceeași expresie ca la rețeaua Hopfield. Probabilitatea unei stări este aceeași ca la modelul Ising. Antrenarea presupune minimizarea energiei, ceea ce conduce la minimizarea diferenței dintre distribuția datelor de intrare și distribuția datelor generate de model pentru acele date de intrare. Dacă T = 0, o mașină Boltzmann este echivalentă cu o rețea Hopfield.

4. Mașini Boltzmann restricționate O mașină Boltzmann restricționată (Restricted Boltzmann Machine , RBM) este un graf bipartit, adică nu există conexiuni laterale între neuronii din același strat (vizibil sau ascuns)

107

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Fie următoarele notații: stratul vizibil: vi  0, 1  , stratul ascuns: N

h j  0, 1  , pragurile neuronilor din stratul vizibil: ai ∊ ℝN, pragurile M

neuronilor din stratul ascuns: bj ∊ ℝM, ponderile conexiunilor dintre neuroni: wij ∊ ℝN XM.

Energia unei stări (v, h) este:

E ( v, h)  vT w h  aT v  bT h Probabilitatea unei stări (v, h) este:

P ( v, h ) 

1  E ( v ,h ) e Z

Z   e  E ( v,h) v

h

108

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Pornind de la aceste relații, se deduc probabilitățile de activare ale neuronilor, bazate pe funcția sigmoidă:

P( h j  1 | v ) 

1 1  exp  b j  w  j , v



   b

P(vi  1 | h)   ai  w i , h

j

 w j , v





Este interesant faptul că, pentru RBM, funcția sigmoidă σ(·) nu se dă, ci este un rezultat al calculelor de probabilități. Antrenarea RBM se bazează tot pe ideea MLE:



wij    vi h j

data

 vi h j

model



unde 〈x〉d este valoarea așteptată a lui x după distribuția d, iar ε este rata de învățare. Primul termen, cu distribuția data, este ușor de obținut:   P(h j  1 | v )    b j   vi wij  i  

  P(vi  1 | h)    ai   h j wij  j   Al doilea termen, cu distribuția model, este mai greu de obținut și necesită metode statistice precum metodele de eșantionare Monte Carlo pentru lanțuri Markov, de exemplu eșantionarea Gibbs (Gibbs sampling) pentru probabilități condiționate:

109

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Putem distinge două faze în procesul de învățare:

Faza pozitivă presupune propagarea vizibil → ascuns, ceea ce corespunde cu învățarea datelor (~ rețeaua este trează). Faza negativă presupune propagarea ascuns → vizibil, ceea ce corespunde cu reconstrucția datelor (~ rețeaua visează). Divergența contrastivă (Contrastive Divergence, CD) este algoritmul de antrenare cel mai cunoscut pentru RBM. Presupune actualizarea ponderilor și pragurilor, pentru un număr specificat de epoci. Eșantionarea Gibbs se face în k pași, dar de cele mai multe ori se consideră k = 1. CD nu urmează gradientul verosimilității maxime decât dacă k = ∞. Însă CD minimizează în mod aproximativ divergența Kullback-Leibler (KL) care măsoară distanța dintre două distribuții de probabilitate – aici, între date și model.

5. Rețele de convingeri profunde RBM-urile sunt de obicei agregate în stive, rezultând rețele de convingeri profunde (Deep Belief Networks, DBN). Antrenarea se face strat cu strat, folosind, de exemplu, algoritmul divergenței contrastive. Odată ce un RBM este antrenat, alt RBM se pune în stivă deasupra sa. Unitățile ascunse devin unități vizibile pentru stratul imediat superior. Ponderile 110

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

RBM-urilor antrenate anterior rămân fixe. Ponderile se ajustează strat cu strat prin învățare nesupervizată. Dacă scopul final este clasificarea, se antrenează un clasificator clasic pe nivelul cel mai de sus, prin învățare supervizată. În final, toate ponderile sunt rafinate (fine tuned) cu algoritmul backpropagation.

DBN-urile pot fi folosite pentru generare din model, după cum urmează. Se obține un eșantion de echilibru din RBM-ul de la nivelul cel mai de sus efectuând eșantionarea Gibbs pentru un număr mare de pași. Apoi se face traversarea top-down cu activarea unităților de pe celelalte straturi. Datele generate se regăsesc pe stratul vizibil cel mai de jos. Rezultatele generate sunt de fiecare dată altele, deși asemănătoare (din aceeași distribuție, a datelor de antrenare).

111

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

20. Vectori de cuvinte (word embeddings) În reprezentarea atomică a cuvintelor, fiecare cuvânt este reprezentat de un vector, a cărui lungime este numărul de cuvinte din vocabular. Vectorul corespunzător unui cuvânt are 1 pe poziția indexului cuvântului și 0 în rest. Relațiile semantice sunt greu de determinat, întrucât nu există o măsură de similaritate între astfel de vectori. În reprezentarea contextuală, nivelul de similaritate reiese din contextul în care sunt utilizate cuvintele. Reprezentarea unui cuvânt se bazează pe vecinii săi din text. Aceasta se folosește pentru a determina o reprezentare vectorială a cuvintelor, în care conceptele similare din punct de vedere semantic sunt apropiate ca distanță dintre vectori. Modelele recente (word2vec, GloVe) determină vectori pentru cuvinte care încorporează relații semantice, de exemplu, care permit identificarea analogiilor prin operații de tipul: king – queen = uncle – aunt sau:

queen = king + (woman – man).

1. Modelul word2vec Se definește un model care încearcă să lege un cuvânt de contextul în care apare acesta, adică să prezică un cuvânt pe baza cuvintelor vecine, a „contextului” (modelul Continuous Bag of Words, CBOW) sau să prezică un număr de cuvinte vecine pe baza unui cuvânt „central” (modelul Skip-gram). Ordinea cuvintelor din context nu contează. La intrare și la ieșire, cuvintele sunt reprezentate atomic (one-hot). De exemplu, pentru Skip-gram, modelul de găsire a vectorilor de cuvinte este de forma (fig. Singh, 2017):

112

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Stratul de intrare primește vectori one-hot, stratul ascuns are funcții liniare, iar stratul de ieșire este de tip softmax. Funcția obiectiv presupune maximizarea probabilității tuturor cuvintelor de context, dat fiind cuvântul central corespunzător. Între vectorii de cuvinte se realizează produsul scalar, care este o măsură de similaritate.

2. Descompunerea valorilor singulare Matricea de co-ocurență numără de câte ori perechile de cuvinte wij (cuvântul de pe linia i și cuvântul de pe coloana j) apar împreună în același context în corpusul de documente considerat. Descompunerea valorilor singulare (Singular Value Decomposition, SVD) este una din cele mai populare metode de reducere a dimensionalității. În domeniul prelucrării limbajului natural, se poate aplica asupra matricei de co-ocurență. Astfel se obțin trei matrice: U, S și V. Considerând un număr mai mic de dimensiuni în S, liniile lui U conțin proiecțiile vectorilor de cuvinte. 113

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Modelul GloVe GloVe încearcă să realizeze în mod explicit ceea ce word2vec face implicit: codarea informațiilor semantice sub formă de vectori de cuvinte. Folosește fracții de probabilități de co-ocurență, nu direct probabilitățile de co-ocurență. Relația dintre două cuvinte poate fi examinată comparând relațiile acestora cu diferite „cuvinte sondă” (probe words). Un mod natural de a coda fracțiile este sub forma diferențelor de logaritmi. De aici apar semnificațiile semantice ale diferențelor de vectori, ca în analogiile prezentare la început. Obiectivul antrenării este ca produsul scalar al vectorilor de cuvinte să fie egal cu logaritmul probabilității de co-ocurență a cuvintelor. Și word2vec și GloVe determină vectori de cuvinte, însă word2vec este un model „predictiv”, iar GloVe este un model „bazat pe numărare”. Modelele predictive încearcă să prezică cuvintele de context pe baza unui cuvânt țintă. Modelele bazate pe numărare încearcă să reducă dimensiunea matricei de co-ocurență cu minimizarea erorii de reconstrucție. Rezultatele word2vec și GloVe sunt destul de asemănătoare.

114

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

21. Algoritmi de grupare (clustering) 1. Algoritmul k-medii (k-means) Algoritmul partiționează o mulțime de instanțe numerice în k grupuri (clusters). k reprezintă numărul de grupuri și este un parametru de intrare ales de utilizator. Modul de funcționare:  

Se inițializează aleatoriu cele k centre inițiale; Se atribuie fiecărui centru instanțele cele mai apropiate de el:

C (i )  argmin xi  c j

2

j



Se calculează centrul de greutate (media aritmetică) a tuturor instanțelor atribuite unui centru și se actualizează poziția centrului grupului respectiv: cj 



1 nj

x

i: xi C j

i

Se repetă cei doi pași până când nu se mai modifică poziția niciunui centru.

Un exemplu de aplicare a algoritmului este prezentat în continuare (Müller & Guido, 2016):

115

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Algoritmul converge, dar găsește de obicei un minim local al funcției de eroare. În general, se recomandă mai multe rulări și alegerea rezultatului celui mai potrivit. Algoritmul dă rezultate bune dacă grupurile sunt convexe și mai ales de formă aproximativ sferică. Valoarea optimă a lui k nu se cunoaște apriori. De obicei, se încearcă mai multe valori pentru numărul de grupuri k și se alege valoarea care dă cele mai bune rezultate. O metodă automată de alegere a lui k este metoda cotului (elbow method). Se alege valoarea lui k pentru care funcția de eroare nu mai scade prea mult odată cu creșterea lui k. În funcție de alegerea centrelor inițiale, rezultatele finale pot diferi mult. O măsură a calității grupării este coeficientul de siluetă. Scopul său este maximizarea similarității intra-grup și minimizarea similarității intergrup.

116

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Pentru o instanță, se calculează: ai (distanța medie față de instanțele din același grup) și bi (distanța minimă față de orice instanță din orice alt grup). Coeficientul de siluetă al instanței i este: si = (bi – ai) / max(ai, bi)  [–1, 1] Gruparea este mai bună când si este mai mare, aproape de 1 (ai ≪ bi). Coeficientul de siluetă al unui grup este media coeficienților instanțelor. Metoda coeficientului de siluetă este potrivită pentru algoritmul k-medii, dar nu reflectă calitatea partiționării și pentru grupuri de forme arbitrare.

2. Algoritmul EM (Expectation-Maximization) Algoritmul EM (Expectation-Maximization, Așteptare-Maximizare) poate fi văzut ca o variantă flexibilă a algoritmului k-medii, în care grupurile nu mai sunt clar separate, ci o instanță aparține unui grup cu o anumită probabilitate. O instanță aparține de fapt tuturor grupurilor, dar în diverse grade. Dacă se consideră doar probabilitatea cea mai mare, EM se reduce la k-medii. În continuare, presupunem că grupurile urmează o distribuție gaussiană multidimensională, cu următoarea funcție de densitate de probabilitate:

f (x | μ, Σ) 

2 

1

n/2

Σ

1/ 2

 1  T exp   x  μ  Σ 1 x  μ   2 

unde x și μ sunt vectori, iar |Σ| este determinantul matricei de covarianță. În cazul particular 1D, funcția de densitate de probabilitate este:  1 x   2  1  f ( x |  , )  exp   2  2   2   117

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Centrele (cu mediile și matricea de covarianță / deviațiile standard) se inițializează în mod aleatoriu. Algoritmul EM are doi pași: 

Pasul E (se calculează probabilitățile ca instanțele xi să aparțină grupurilor cu centrele Cj): P (C j | x i ) 

P (C j )  P ( x i | C j )

 P (C k



k

)  P ( xi | C k )

Pasul M (se actualizează probabilitățile marginale ale grupurilor și parametrii acestora): P(C j ) 

j

1 n   PC j | xi  n i 1

 PC | x  x   PC | x  j

i

j

i

j 

 PC i

j

i

i

i



| xi  xi   j  xi   j  T

 PC i

j



| xi 

Pașii se repetă până la convergența criteriului:

  L   ln   P(C j ) P xi | C j  i  j  Din punct de vedere practic, trebuie evitată situația în care |Σ| = 0. Astfel, se pot adăuga niște numere mici la diagonala principală sau la elementele egale cu 0. De asemenea, pentru a evita un număr mare de parametri, dimensiunile se pot considera independente; în acest caz, matricea Σ va fi o matrice diagonală. 118

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Gruparea ierarhică Se poate realiza în două moduri: 



Grupare aglomerativă (strategie bottom-up): inițial fiecare punct reprezintă un grup și apoi se combină acestea în grupuri din ce în ce mai mari. De exemplu: Agglomerative Nesting, AGNES. Cele mai multe metode ierarhice sunt de acest tip; Grupare divizivă (strategie top-down): inițial toate punctele aparțin unui singur grup și acesta este partiționat treptat în grupuri mai mici. De exemplu: Divisive Analysis, DIANA. O modalitate mai simplă este aplicarea repetată a algoritmului k-medii cu k = 2.

Utilizatorul trebuie să specifice un criteriu de terminare, precum numărul de grupuri dorit, un prag impus asupra diametrelor grupurilor etc. Mai jos este prezentat un exemplu de grupare ierarhică (Han, Kamber & Pei, 2011):

Dendrograma indică succesiunea de combinări sau partiționări din gruparea ierarhică. Față de exemplul următor, axele pot fi și inversate, cu similaritatea pe axa x (Han, Kamber & Pei, 2011): 119

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Pentru gruparea aglomerativă, la un moment dat trebuie determinate două grupuri care vor fi combinate. Acest lucru se face prin minimizarea unui anumit criteriu. Există mai multe criterii, dintre care menționăm: 

Legătură simplă (single link): distanța minimă între oricare două instanțe. Produce „lanțuri” lungi de grupuri: D(C1 , C2 )  min D( x1 , x2 ) x1C1 x2 C2



Legătură completă (complete link): distanța maximă între oricare două instanțe. Produce grupuri sferice: D(C1 , C2 )  max D( x1 , x2 ) x1C1 x2 C2



Legătură medie (average link): media tuturor perechilor de distanțe. Scade sensibilitatea la valori extreme:

D(C1 , C2 ) 

1 1 n1 n2

  D( x , x )

x1 C1 x 2 C 2

1

2

Algoritmul Lance-Williams identifică o formulă unică pentru mai multe astfel de criterii. Prin setarea parametrilor formulei, se alege un criteriu specific. 120

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Deciziile de combinare sunt critice deoarece procesul este greedy – nu permite revizuirea unor decizii deja luate. Gruparea aglomerativă nu scalează bine, deoarece presupune analiza unui număr mare de instanțe sau grupuri.

4. Algoritmul DBSCAN Folosește doi parametri:  

Eps: raza maximă a vecinătății unui punct; MinPts: numărul minim de puncte din vecinătatea Eps a unui punct. Vecinătatea Eps a unui punct p este mulțimea punctelor cuprinse într-o hipersferă de rază Eps în jurul lui p:

N Eps ( p)  q  D | dist( p, q)  Eps  Un punct este esențial (core point) dacă vecinătatea Eps a sa conține cel puțin MinPts puncte. Două puncte sunt conectate prin densitate dacă există o mulțime de puncte intermediare între ele cu vecinătăți dense. Un punct este de graniță (border point) dacă nu este esențial, dar este accesibil prin densitate dintr-un punct esențial. O valoare extremă (outlier, noise) este un punct care nu este esențial și nici de graniță – acesta nu este introdus în niciun grup. Conform algoritmului DBSCAN, un grup este mulțimea cea mai mare de instanțe (puncte) conectate prin densitate. Pseudocod (Ester et al., 1996):

121

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Dbscan(d, eps, minPts): for each unvisited point p in dataset d mark p as visited neighborhood = Region(p, eps) if count(neighborhood) < minPts ignore p else c = new cluster ExpandCluster(p, neighborhood, c, eps, minPts) Region (p, eps): return all points within the n-dimensional sphere centered at p with radius eps, including p ExpandCluster(p, neighborhood, c, eps, minPts): add point p to cluster c for each point p’ in neighborhood if p’ is not visited mark p’ as visited neighborhood’ = Region(p’, eps) if count(neighborhood’) ≥ minPts neighborhood = union(neighborhood, neighborhood’) if p’ is not a member of any cluster add p’ to cluster c

Parametrul Eps controlează numărul de grupuri generate. Dacă Eps este mai mare, atunci vor fi incluse mai multe puncte într-un grup. Parametrul MinPts controlează dacă punctele din regiuni mai puțin dense vor fi incluse în grupuri sau vor fi considerate valori extreme. Dacă MinPts este mai mare, atunci vor exista mai puține puncte esențiale și mai multe valori extreme. Numărul de grupuri nu trebuie cunoscut a priori. Implicit, acesta este controlat de parametrii Eps și MinPts. Deoarece se bazează pe densitatea punctelor, în loc de distanța dintre acestea, algoritmul DBSCAN poate da rezultate bune pentru forme arbitrare (nesferice) ale grupurilor. De exemplu (Müller & Guido, 2016):

122

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

123

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

22. Rețele cu auto-organizare 1. Învățarea hebbiană Învățarea hebbiană modelează dinamica sinapselor din creierele biologice. Modelul său computațional se bazează pe legea lui Hebb: Dacă doi neuroni conectați sunt activați în același timp, ponderea conexiunii dintre ei crește. Dacă doi neuroni sunt activați în contratimp, ponderea conexiunii dintre ei scade. În engleză: “Neurons that fire together, wire together”.

wij    x j  yi

unde α este rata de învățare, iar funcțiile de activare sunt de obicei liniare. Pentru intrări multiple: D

y   wi xi i 1

y  wT x  x T w Produsul scalar poate fi interpretat ca o măsură de similaritate, prin urmare, neuronul hebbian implementează o măsură de similaritate în spațiul de intrare. O ieșire y mare înseamnă că intrarea curentă este similară cu vectorul de antrenare x care a creat ponderile. Rețeaua își amintește vectorul de antrenare, deci se comportă ca o memorie asociativă. Folosind doar regula lui Hebb, ponderile pot crește la infinit. De aceea, se poate aplica normalizarea regulii hebbiene: noua valoare a unei ponderi se împarte la norma vectorului de ponderi. Dacă o pondere crește, celelalte trebuie să scadă.

124

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Regula lui Oja este o formulă care aproximează această normalizare: w    y  (x  y  w)

Ponderile nu mai cresc nelimitat, dar rețeaua poate uita asocierile vechi. Dacă un vector de antrenare nu este prezentat frecvent, el poate fi uitat. Regula lui Sanger, care generalizează regula lui Oja pentru o rețea cu D intrări și M ieșiri (M ≤ D, dar de obicei M ≪ D) conduce la aproximarea componentelor principale ale datelor de intrare (din analiza componentelor principale, Principal Component Analysis, PCA): i   wij    yi   x j   wkj y k  k 1  

Ponderile rețelei reprezintă cei M vectori de dimensiune D. PCA este o metodă de reducere a dimensionalității sau de compresie a datelor. Prin selectarea proiecțiilor pe cele mai importante M dimensiuni, din cele D ale spațiului de intrare, cu M ≤ D, se păstrează cele mai importante caracteristici ale datelor.

2. Algoritmul Kohonen Este bazat pe ideea corespondențelor dintre intrările senzoriale și diferitele regiuni ale cortexului, în sensul că anumite intrări sunt prelucrate în anumite zone cerebrale. Modelul Kohonen presupune un spațiu de intrare cu n dimensiuni și un spațiu de ieșire cu un număr redus de dimensiuni:

125

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Neuronii (în spațiul de ieșire) sunt dispuși într-o structură regulată: matrice (2D) sau vector (1D). Ponderile fiecărui neuron sunt inițializate aleatoriu. Ponderile au aceeași dimensionalitate ca datele de intrare. Fiecare neuron poate fi reprezentat ca un punct în spațiul n-dimensional al intrărilor, în funcție de valorile ponderilor sale. Pentru fiecare vector de intrare, se determină în spațiul de intrare cel mai apropiat neuron, conform ponderilor acestuia:

i *  argmin x  w i i

unde || · || este distanța euclidiană. Se determină vecinii neuronului câștigător în spațiul de ieșire. Doar pentru neuronul câștigător și neuronii din vecinătatea lui, Λ, se actualizează ponderile:

  x  w j  w j   0

j   i* j   i*

Ponderile neuronului (neuronilor) câștigători se deplasează puțin către vectorul de intrare. Rata de învățare α are o valoare mică pozitivă (de exemplu, între 0,1 și 0,5). Mărimea vecinătății Λi poate fi statică sau dinamică (la început dimensiunea este jumătate sau o treime din dimensiunea stratului de ieșire și apoi scade treptat).

126

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Cele mai importante proprietăți ale algoritmului Kohonen sunt:  

Reducerea dimensionalității, deoarece poate transforma un spațiu n-dimensional într-un spațiu 2D sau 1D; Păstrarea topologiei, deoarece relațiile de similaritate prezente între datele inițiale sunt păstrate și între datele rezultate după transformare.

127

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

23. Învățarea cu întărire 1. Noțiuni generale 1.1. Agentul și mediul de execuție Un agent este o entitate autonomă (software sau hardware) care acționează fără intervenție umană și este parte integrantă din mediul său de execuție. Modelul de interacțiune: agentul efectuează acțiuni, iar mediul îi acordă recompense și îi prezintă agentului situații numite stări.

1.2. Învățarea cu întărire (reinforcement learning) Agentul trebuie să învețe un comportament fără a avea un instructor. El 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. El primește o recompensă (întărire pozitivă) dacă îndeplinește bine sarcina sau o pedeapsă (întărire negativă) dacă îndeplinește rău sarcina. Scopul este de a determina agentul să acționeze astfel încât să-și maximizeze recompensele totale. El trebuie să învețe ce secvență de acțiuni conduce la îndeplinirea sarcinii. Datele de antrenare sunt triplete de tipul 128

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

(S, A, R): Stare, Acțiune, Recompensă. Acțiunile afectează de obicei și recompensele ulterioare, nu numai pe cele imediate: au un efect întârziat.

2. Procese de decizie Markov Un proces de decizie Markov este definit de:   

Starea inițială s0; Modelul de tranziții T(s, a, s' ), care reprezintă probabilitatea de a ajunge din starea s în starea s' efectuând acțiunea a; Funcția de recompensă R(s). Exemplu (Russell & Norvig, 2002):

Soluția unei astfel de probleme se numește politică (policy) și se notează π. Politica este descrierea unui reflex: π(s) este acțiunea recomandată în starea s. 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 imediat, pe termen scurt. Utilitatea este câștigul total, pe termen lung. Într-un mediu stohastic, se calculează utilitatea așteptată. Politica optimă π* maximizează utilitatea așteptată.

129

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Fiecare politică generează secvențe multiple de stări, datorită incertitudinii tranzițiilor T(s, a, s' ). Utilitatea (sau valoarea) unei politici π este valoarea așteptată a sumei tuturor recompenselor actualizate observate după toate secvențele posibile de stări:

Utilitatea unei stări s este utilitatea așteptată a secvenței de stări următoare, secvență care este determinată de π(s):

Ecuația Bellman:

U ( s )  R( s)   max T ( s, a, s' )U ( s' ) a

s'

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

 * ( s)  argmax T ( s, a, s' )U ( s' ) a

s'

2.1. Iterarea valorilor (value iteration) Este un algoritm pentru calcularea politicii 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 și se alege starea cu utilitatea cea mai mare. 130

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Exemplu (Russell & Norvig, 2002):

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. De exemplu, utilitatea stării (1,1):

Sunt n stări posibile, n ecuații Bellman, una pentru fiecare stare, prin urmare trebuie rezolvat un sistem de n ecuații cu n necunoscute: U(s). Nu se poate rezolva ca sistem de ecuații liniare din cauza funcției max. Se rezolvă iterativ:

U i 1 ( s)  R( s)   max T ( s, a, s' )U i ( s' ) a

s'

Pseudocod (Russell & Norvig, 2002):

131

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2.2. Iterarea politicilor (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ă doi pași: a) Evaluarea politicii: calcularea utilităților tuturor stărilor pe baza politicii πi :

U i ( s)  R( s)   T ( s,  i ( s), s' )U i ( s' ) s'

Acesta este un sistem de n ecuații liniare cu n necunoscute. Se poate rezolva exact în O(n3) sau în mod aproximativ mai repede. b) Îmbunătățirea politicii: calcularea unei noi politici πi+1 pe baza utilităților Ui . Se cunosc toate U(s). Se calculează pentru fiecare s:

max T ( s, a, s' )U ( s' ) a

s'

132

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Aceasta este acțiunea optimă ai*(s). Dacă ai*(s) ≠ πi(s), se actualizează politica: πi+1(s) ← ai*(s). În acest mod, se pot actualiza doar părțile „promițătoare” ale spațiului de căutare. Pseudocod (Russell & Norvig, 2002):

3. Învățarea cu întărire Comparație: 



Proces de decizie Markov: o Mulțimea de stări S, mulțimea de acțiuni A; o Modelul de tranziții T(s, a, s' ) este cunoscut; o Funcția de recompensă R(s) este cunoscută; o Calculează o politică optimă; Învățare cu întărire: o Se bazează pe procese de decizie Markov, dar: o Modelul de tranziții este necunoscut; o Funcția de recompensă este necunoscută; o Învață o politică optimă. 133

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Tipuri de învățare cu întărire: 



Pasivă sau activă: o Pasivă: agentul execută o politică fixă și o evaluează; o Activă: agentul își actualizează politica pe măsură ce învață; Bazată pe model sau fără model: o Bazată pe model: învață modelul de tranziții și recompense și îl folosește pentru a descoperi politica optimă; o Fără model: descoperă politica optimă fără a învăța modelul. 3.1. Î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. Agentul execută o serie de încercări (trials). Politica este aceeași, dar mediul este nedeterminist. Exemplu (Russell & Norvig, 2002):

Scopul agentului este să învețe utilitatea așteptată Uπ(s):

134

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3.1.1. Estimarea directă a utilității În exemplul de mai sus, prima încercare produce:   

în starea (1,1) recompensa totală: –0,04 · 7 + 1 = 0,72 (cu γ = 1); î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. Însă 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. Prin urmare, căutarea se face într-un spațiu mult mai mare decât cel necesar de fapt, iar convergența este foarte lentă. 3.1.2. Programarea dinamică adaptivă Se folosesc ecuațiile Bellman:

U  ( s)  R( s)   T ( s,  ( s), s' )U  ( s' ) s'

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

135

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Trebuie estimate T(s, π(s), s' ) și R(s) din încercări, adică frecvențele tranzițiilor și mediile recompenselor. Probabilitățile și recompensele învățate se introduc în ecuațiile Bellman și se rezolvă sistemul de ecuații liniare cu necunoscutele Uπ(s). Pseudocod (Russell & Norvig, 2002):

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, deoarece presupune rezolvarea unui sistem de ecuații liniare de ordin n. 3.1.3. Învățarea diferențelor temporale (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. Pentru același exemplu din secțiunea 3.1.2:

136

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

După prima încercare: U(1,3) = 0,84, U(2,3) = 0,92. Fie tranziția (1,3) → (2,3) în a doua încercare. Între cele două stări, constrângerea dată de ecuația Bellman impune ca U(1,3) = –0,04 + U(2,3) = 0,88 (cu γ = 1). Estimarea U(1,3) = 0,84 este mai mică și trebuie mărită puțin. Ecuația diferențelor temporale propune un compromis:

U  ( s)  U  ( s)   R( s)   U  ( s' )  U  ( s) Metoda 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. Metoda diferențelor temporale nu are nevoie de model pentru a realiza actualizările. Rata de învățare α determină viteza de convergență la utilitatea reală. 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ă: 



n 1

n 1

 (n)  , 

2

(n)  

Funcția α(n) = 1 / n satisface această condiție. De multe ori, se folosește funcția: α(n) = 1 / (n + 1)  (0, 1]. Pseudocod (Russell & Norvig, 2002):

137

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3.2. Î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. 3.2.1. Explorare și exploatare Dilema exploatare-explorare a agentului:  

Să își maximizeze utilitatea pe baza cunoștințelor curente sau Să încerce să își îmbunătățească aceste cunoștințe. Este necesar un compromis.

Exploatarea: Agentul oprește învățarea și execută acțiunile date de politică. Are ca efect maximizarea recompenselor folosind estimările curente. Exploatarea pură generează de obicei politici suboptime. Explorarea: Agentul învață încercând acțiuni noi. Poate conduce la maximizarea recompenselor pe termen lung. Explorare pură: agentul învață modele din ce în ce mai bune, dar recompensele sunt mici. 138

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

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. Cea mai simplă soluție pentru dilemă este 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), dar ε nu scade niciodată sub un prag, de exemplu 0,1. Astfel, agentul are mereu o șansă de explorare, pentru a evita optimele locale 3.2.2. Algoritmul Q-Learning Algoritmul Q-Learning învață o funcție Q(s, a), astfel încât: U ( s)  max Q( s, a ) a

Ecuațiile de constrângere la echilibru:

Q( s, a )  R( s)   T ( s, a, s' ) max Q( s' , a' ) a'

s'

Q-Learning

este o metodă DT fără model:



Q( s, a )  Q( s, a )   R( s)   max Q( s' , a' )  Q( s, a ) a'

139



Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Actualizările se fac de fiecare dată când acțiunea a aplicată în s duce în s'. Rata de învățare α determină viteza de actualizare a estimărilor. De obicei, α  (0, 1). Pseudocod (Russell & Norvig, 2002):

140

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

24. Învățarea cu întărire profundă Rețelele neuronale profunde sunt utilizate pentru probleme de învățare cu întărire deoarece numărul stărilor este de obicei foarte mare, iar rețelele pot aproxima valorile acestor stări, beneficiind de o reprezentare mult mai compactă. Pentru a aproxima funcția Q din algoritmul Q-Learning, ieșirile rețelei pot fi valorile tuturor acțiunilor posibile, adică toate valorile Q pentru o stare se calculează într-un singur pas:

Algoritmul general pentru aproximarea funcției Q este următorul:    

 

Se calculează Qt(st , ai) folosind propagarea înainte prin rețeaua neuronală pentru toate acțiunile ai posibile în starea st ; Se alege o acțiune nouă at și se trece într-o nouă stare st+1 ; Se calculează Qt(st+1, ai) folosind propagarea înainte prin rețeaua neuronală pentru toate acțiunile din starea st+1 ; Se setează valoarea Qțintă ca fiind: rt+1 + γ · maxa Q(st+1, a) doar pentru acțiunea curentă at , respectiv Qt+1(st , ai) = Qt (st , ai) pentru celelalte acțiuni; Se calculează vectorul de eroare e = Qțintă – Qt = Qt+1 – Qt ; Se aplică algoritmul backpropagation asupra rețelei pentru actualizarea ponderilor. 141

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

1. Studii de caz 1.1. TD-Gammon Este un program de table (backgammon) care folosește o rețea neuronală clasică, nu profundă. Intrările rețelei reprezintă configurația tablei la un moment dat și se bazează pe informații „expert” specifice jocului de table. În total, rețeaua are 198 de intrări. Valoarea estimată a unei stări reprezintă probabilitatea de a câștiga din acea stare. Valorile sunt estimate de rețeaua neuronală (fig. Sutton & Barto, 2018).

1.2. Deep Q-Network Deep Q-Network (DQN) s-a dorit un pas către inteligența artificială generală, deoarece folosește același algoritm pentru jocuri destul de diferite: 49 de jocuri Atari 2600, precum Pong, Breakout, Space Invaders, Seaquest, Beam Rider etc. Intrările sunt reprezentate de 4 imagini consecutive ale jocului, pentru a putea estima viteza și direcția personajelor sau elementelor din joc. Scorul este standardizat, pentru a fi tratat în același fel pentru toate jocurile și este folosit pentru a calcula recompensa: +1 dacă scorul crește, –1 dacă scorul scade și 0 dacă scorul rămâne neschimbat. 142

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Ieșirile sunt valorile Q ale tuturor acțiunilor posibile. Algoritmul DQN utilizează o serie de metode pentru optimizarea antrenării: 





Experience replay. În timpul jocului, toate tranzițiile (s, a, r, s' ) sunt memorate într-o structură numită replay memory. Când se antrenează rețeaua, sunt folosite mini-loturi aleatorii din replay memory în loc de tranziția cea mai recentă. Această metodă evită problema similarității eșantioanelor de antrenare succesive, care ar conduce rețeaua într-un optim local. Este posibilă și colectarea tranzițiilor din jocul unui om și antrenarea rețelei cu acestea. Concret, se alege o acțiune în mod ε-greedy, se adaugă tranziția (st, at, rt+1, st+1 ) în replay memory, se trece în starea st+1 și se continuă jocul, dar actualizarea ponderilor rețelei se face cu un număr mic de tranziții din replay memory ; Înghețarea rețelei țintă. Parametrii curenți ai rețelei determină următoarele date de antrenare, ceea ce poate conduce la fenomenul de reacție pozitivă și deci instabilitate. După un număr anumit de actualizări, rețeaua curentă este copiată în altă rețea, iar ponderile acestei rețele sunt menținute fixe și constituie țintele de antrenare:

Limitarea erorii. Termenul de eroare (conținutul parantezei din ecuația de mai sus) este limitat la intervalul [–1, 1].

În pseudocodul următor (Mnih et al., 2013), fiecare episod este un joc complet, t reprezintă fiecare pas din joc, iar  reprezintă imaginile x procesate. Se folosește strategia ε-greedy: cu probabilitatea ε, se selectează o acțiune aleatorie, altfel se selectează în mod greedy acțiunea cea mai bună conform politicii (cu valoarea Q maximă). ε scade de la 1 la 0,1 pe parcursul primului milion de cadre, apoi rămâne constant 0,1. Optimizarea se face cu algoritmul RMSProp.

143

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

1.3. AlphaGo Programul AlphaGo a fost primul care a învins unul din cei mai buni jucători de go din lume. AlphaGo Zero este o variantă ulterioară, cu performanțe superioare. AlphaGo Zero nu se bazează pe trăsături ale jocului identificate manual sau prin învățare din jocuri umane. Se folosesc doar regulile jocului, de aici partea de “Zero” a numelui. Antrenarea se face exclusiv prin selfplay. A descoperit variante noi ale strategiilor clasice de joc. Intrările rețelei sunt reprezentate de o stivă de imagini 19 x 19 x 17. Pentru fiecare poziție de pe tabla de joc există 17 trăsături binare: primele 8 indică dacă poziția este ocupată de AlphaGo în starea curentă, respectiv 7 stări anterioare. Următoarele 8 indică același lucru pentru adversar. Ultima indică mutarea curentă: 1 pentru negru, 0 pentru alb. AlphaGo Zero combină modelele neuronale cu Monte Carlo Tree Search (MCTS), o metodă stohastică de căutare a soluțiilor în jocuri cu factori mari de ramificare. Folosește o rețea cu două capete, care aproximează politicile (probabilitățile de selecție ale acțiunilor), respectiv valorile. Rețeaua este de tip rezidual (residual neural network, ResNet). 144

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Pentru o configurație de joc dată, rețeaua neuronală calculează atât probabilitățile mutărilor P, cât și probabilitatea de a câștiga V. Se rulează MCTS pentru a rafina probabilitățile de mutare P’ și câștig V’. Se actualizează parametrii rețelei pentru a apropia P și V de P’ și V’. Procesul seamănă cu algoritmul de iterare a politicilor: self-play cu MCTS reprezintă evaluarea politicilor, iar actualizarea rețelei reprezintă îmbunătățirea politicilor. Pentru MCTS, capătul de politică ajută la scăderea lățimii de căutare dintr-un nod (preferând acțiunile mai promițătoare), iar capătul de valoare ajută la scăderea adâncimii de căutare în nodurile frunză (fig. Silver et al., 2017).

145

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

25. Agenți și sisteme multi-agent Un agent este o entitate software sau hardware situată într-un mediu de execuție și care este capabilă de acțiuni autonome pentru a-și îndeplini obiectivele proiectate. Situarea înseamnă că agentul este parte integrantă din mediul său de execuție, cu care interacționează în mod continuu: percepe mediul prin intermediul senzorilor și acționează asupra lui prin intermediul efectorilor. Autonomia înseamnă că agenții acționează independent de utilizator sau proprietar. Un sistem multi-agent este compus din agenți care interacționează. De obicei, presupunem că agenții operează într-un mediu deschis:  

 

inaccesibil: agenții nu au informații complete și actuale despre starea mediului; nedeterminist: acțiunile nu au un singur efect garantat; agenții au doar control parțial și acțiunile pot eșua, iar dacă e necesar, trebuie să-și refacă planurile; dinamic: mediul poate fi modificat și de ceilalți agenți; starea mediului se poate schimba în timpul executării unei acțiuni; continuu: mediul nu are un număr finit de stări.

Un agent inteligent este un agent cu un comportament flexibil, ceea ce presupune:   

proactivitate: comportament orientat către scop, preluarea inițiativei; reactivitate: răspunsuri prompte la schimbările din mediu; abilități sociale: posibilitatea de a interacționa cu alți agenți (sau cu oameni).

146

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Diferența principală dintre agenți și obiectele din programarea orientată pe obiecte este gradul de autonomie. În obiecte, metodele sunt apelate direct, iar fluxul de control se mută direct în metodă. Decizia de execuție este la sursă (obiectul care apelează). Agenții primesc solicitări de a îndeplini acțiuni, dar un agent poate refuza o solicitare. Decizia de execuție este la destinație (agentul care primește cererea). Mobilitatea reprezintă schimbarea perspectivei agentului asupra mediului. Poate fi schimbarea poziției fizice (agent hardware, robot) sau deplasarea pe o altă mașină (agent software). Sistemele multi-agent pot avea mobilitate slabă, în care se transferă codul și starea datelor (valorile variabilelor interne) sau mobilitate puternică, în care se transferă și contextul de execuție: stiva, registrele procesorului, adresa instrucțiunii curente etc.

147

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

26. Complexitate și emergență Viața artificială este un domeniu interdisciplinar care implică biologia, psihologia, științele cognitive și matematica. Sistemele complexe sunt sisteme care conțin un număr mare de componente care interacționează. Din cauza acestor interacțiuni, evoluția acestor sisteme este foarte dificil, sau chiar imposibil, de prezis. Emergența este fenomenul prin care unele entități de nivel superior manifestă proprietăți pe care entitățile lor componente, de nivel inferior, nu le manifestă. Aceste proprietăți sunt deseori surprinzătoare și nu pot fi prezise direct din structura și regulile de interacțiune ale componentelor de nivel inferior.

1. Automate celulare Mediul este o latice, o mulțime discretă de celule alăturate. Timpul este de asemenea discret. Celulele au stare: o serie de proprietăți care se pot modifica în timp. Starea unei celule la momentul t + 1 depinde de starea proprie și de starea celulelor vecine la momentul t. Actualizările stărilor se fac în paralel. De cele mai multe ori, automatele sunt unidimensionale sau bidimensionale. Regulile pentru un automat celular unidimensional pot fi numerotate în funcție de starea unei celule la momentul t + 1 și a sa și a vecinilor la momentul t, de exemplu 01101001 ⇒ regula 105:

Evoluția diferitelor reguli poate fi clasificată astfel:   

Clasa I: evoluează într-o stare omogenă; Clasa II: evoluează periodic; Clasa III: evoluează haotic; 148

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



Clasa IV: include toate comportamentele anterioare (sunt numite „reguli complexe”).

Regula 110 este Turing completă, adică orice calcul sau program poate fi simulat folosind acest automat. Orice secvență de biți se poate regăsi pe o linie dacă dimensiunea liniei și numărul de expandări sunt suficient de mari. Jocul vieții (game of life) este un automat celular bidimensional. Fie n numărul de vecini vii ai unei celule. Reguli:    

Dacă n < 2, celula moare de singurătate; Dacă n > 3, celula moare de supra-aglomerare; Dacă n = 3, celula renaște (se naște o nouă celulă); Altfel, celula își păstrează starea anterioară. Aplicând aceste reguli, apar o serie de modele emergente:

Acest joc are proprietatea de calcul universal, adică are capacitatea de a calcula tot ce poate fi calculat, ca Mașina Turing (prin urmare, este echivalent cu un calculator „normal” cu arhitectură von Neumann).

149

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Sisteme Lindenmeyer Au fost propuse inițial ca formalism matematic pentru modelarea creșterii plantelor. Un astfel de model se bazează pe un sistem de producție, de exemplu: Axiomă: Regula 1: Regula 2:

B B → F[–B]+B F → FF

+ rotește dreapta – rotește stânga [ salvează poziția și unghiul ] reface poziția și unghiul

Aplicând regulile de un anumit număr de ori, apar structuri foarte complexe, cu o natură fractalică:

Fractalii sunt structuri auto-similare la scări multiple, adică o porțiune mică dintr-un fractal arată la fel ca întregul.

3. Inteligența colectivă În lumea vie și în modelele computaționale inspirate din ea apar comportamente emergente, de exemplu:   

Viespi: diferențierea rolurilor, deși aceste roluri sunt ocupate de viespi identice din punct de vedere genetic; Termite: construirea mușuroiului; Furnici: sortarea obiectelor; 150

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com





Modelul Boids: simulează comportamentul unui stol de păsări, pe baza a trei reguli simple: apropierea de centrul de greutate al vecinilor, evitarea coliziunilor cu vecinii și potrivirea vitezei cu aceea a vecinilor; Modelarea traficului auto: paradoxul lui Braess. Adăugarea de noi artere de circulație nu îmbunătățește întotdeauna traficul. Invers, închiderea unor artere îl poate îmbunătăți.

4. Simulări bazate pe agenți Simulările pot pune în evidență diferențele dintre optimizarea comportamentului individual și optimizarea comportamentului social, al sistemului în ansamblul său. De exemplu: 





Modelul Sugarscape: modelează o populație de agenți care consumă zahăr. Se poate observa evoluția populației către o valoare stabilă, evoluția „averii” (puțini agenți au foarte multe resurse și multi agenți au foarte puține resurse), apariția unor schimburi economice, fenomene de migrație emergente; Modelul segregării al lui Schelling: arată că într-o societate pot exista fenomene segregaționiste evidente chiar dacă indivizii nu sunt neapărat foarte segregaționiști; Modelul lui Hammond: Este un model al corupției sociale și arată în ce condiții pedepsele aplicate pot scădea numărul de indivizi corupți dintr-o societate.

151

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

27. Arhitecturi de agenți O arhitectură definește modulele care compun un agent și modul lor de interacțiune, precum și modalitatea în care datele de la senzori și starea curentă a agentului determină acțiunile și următoarea stare internă a agentului. Un agent este într-o continuă interacțiune cu mediul: primește date de la senzori (numite percepte) privind starea mediului, își modifică starea internă și efectuează acțiuni. Acțiunile pot schimba starea mediului. În general, mediul conține și alți agenți. Există patru clase principale de arhitecturi: 

 

Deliberative: o Bazate pe raționamentul deductiv; o Bazate pe raționamentul practic; Reactive; Hibride.

1. Arhitecturi logice Arhitecturile logice folosesc reprezentări simbolice bazate pe logică ale mediului, de exemplu logică predicativă de ordin întâi sau logică temporală. Manipularea acestor cunoștințe se face prin demonstrații automate de teoreme. Pentru a efectua o acțiune, un astfel de agent încearcă mai întâi să găsească o acțiune care poate fi dedusă din baza lui de cunoștințe. Dacă nu poate, încearcă apoi să găsească o acțiune care nu este interzisă explicit. Avantaje: semantica elegantă și formalizarea matematică bună. Dezavantaje: transformarea stărilor mediului într-o reprezentare simbolică este dificilă, iar demonstrarea de teoreme este lentă.

152

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Arhitectura BDI Arhitectura BDI (Beliefs-Desires-Intentions) este probabil cea mai cunoscută arhitectură de agenți. Se bazează pe studiile psihologice asupra raționamentului practic, care presupune a decide ce scopuri trebuie atinse și cum se pot atinge aceste scopuri. Convingerile reprezintă informațiile agentului despre mediu, inclusiv despre ceilalți agenți din mediu. Dorințele reprezintă obiectivele sau stările de lucruri pe care agentul le-ar dori realizate, într-o lume ideală. Dorințele necontradictorii adoptate de agent se numesc scopuri. Intențiile sunt dorințele pe care agentul s-a angajat să le realizeze, adică pentru care a început execuția unui plan. Există mai multe strategii de angajament:   

Angajament orb: agentul își menține o intenție până când crede că aceasta a fost îndeplinită; Angajament singular: agentul își menține o intenție până când crede că a fost îndeplinită sau este imposibil de îndeplinit; Angajament deschis: agentul își menține o intenție până când crede că a fost îndeplinită sau este imposibil de îndeplinit sau scopul nu mai există.

Dacă mediul se schimbă rar, se comportă mai bine agenții care nu se opresc din execuție ca să-și reconsidere intențiile. Dacă mediul se schimbă frecvent, se comportă mai bine agenții care se opresc să-și reconsidere intențiile după fiecare acțiune. Arhitectura PRS (Procedural Reasoning System) este o implementare a arhitecturii BDI. Planurile PRS au un context (precondițiile), un scop (postcondițiile) și un corp (rețeta planului, cursul de acțiune). Deoarece algoritmii de planificare standard sunt lenți și complecși, se folosesc de obicei biblioteci de planuri deja calculate, care care descriu secvențele de acțiuni care trebuie efectuate pentru a atinge anumite scopuri. 153

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Arhitecturi reactive Arhitecturile reactive se bazează pe existența unor comportamente aranjate pe straturi. Mai multe comportamente se pot activa simultan atunci când precondițiile lor permit acest lucru, dar comportamentelor le sunt atribuite priorități diferite. Acțiunea aleasă de un agent este dată de comportamentul activ cel mai prioritar. Comportamentul global rezultat din compunerea unei mulțimi de comportamente reactive este emergent: nu poate fi descris complet doar pe baza comportamentelor individuale, ci poate fi observat doar atunci când agentul rulează efectiv. Avantaje: simplitatea, rapiditatea și robustețea. Dezavantaje: dificultatea de a învăța comportamente noi, lipsa unei metodologii clare pentru construirea unor astfel de sisteme (din cauza comportamentului global emergent), dificultatea de a construi agenți cu un număr mare de straturi de comportament.

4. Arhitecturi hibride Arhitecturile stratificate au mai multe straturi dispuse într-o ierarhie, cu diferite niveluri de abstractizare, de exemplu:   

Nivelul inferior: strat reactiv, fără un model al mediului; Nivelul mediu: strat proactiv, de planificare, bazat pe cunoștințe simbolice despre mediu; Nivelul superior: strat social, pentru reprezentarea altor agenți cu scopurile, convingerile lor etc. Tipuri de stratificare:



Stratificarea orizontală: Fiecare strat are acces la percepții și acțiuni, iar straturile concurează pentru determinarea acțiunii. Este nevoie de un mediator, care decide stratul care controlează agentul la un moment dat; 154

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



Stratificarea verticală: Percepțiile și acțiunile sunt tratate de un singur strat. Prezintă similarități cu modul în care funcționează organizațiile: informațiile se trimit spre nivelurile superioare, iar deciziile de execuție se trimit spre nivelurile inferioare. Este mai puțin tolerantă la defecte: defectele dintr-un strat pot afecta întregul comportament al agentului.

155

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

28. Comunicarea inter-agent 1. Tipuri de comunicare în sisteme multi-agent 

 

Sisteme omogene necomunicative: Comunică indirect, prin stigmergie. Stigmergie activă: un agent modifică mediul astfel încât să influențeze intrările senzoriale ale altui agent. Stigmergie pasivă: un agent modifică mediul astfel încât să schimbe efectele acțiunilor altui agent; Sisteme eterogene comunicative: Agenții pot efectua acțiuni diferite și se pot specializa pentru a îndeplini diferite roluri; Sisteme comunicative: Comunicare unu-la-unu, broadcast, memorie comună etc. Necesită un protocol privind formatul și conținutul mesajelor.

2. Teoria actelor de vorbire (speech act theory) Există o distincție între enunțuri constatative (utilizate pentru a afirma unele lucruri, pentru a transmite informații și care pot fi, de exemplu, adevărate sau false) și performative (utilizate pentru a efectua acțiuni, de exemplu, cereri, promisiuni, declarații). Tipuri de acte de vorbire:  

Acte de rostire (utterance acts): cuvintele propriu-zise. De exemplu, un barman rostește cuvintele „Barul se va închide în cinci minute”; Acte locuționare (locutionary acts): enunțuri care se referă la alte lucruri. De exemplu, actul de a spune că barul la care servește barmanul se va închide în cinci minute de la momentul în care se rostește enunțul;

156

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com





Acte ilocuționare (illocutionary acts): enunțuri care exprimă intenția de a interacționa. De exemplu, actul de a informa clienții despre închiderea barului; Acte perlocuționare (perlocutionary acts): enunțuri care exprimă intenția de a provoca un anumit răspuns comportamental la ascultător. De exemplu, actul de a determina clienții să își termine băuturile.

În teoria bazată pe planuri a actelor de vorbire, se consideră că actele de comunicare sunt părți componente din planuri și pot fi tratate la fel ca acțiunile fizice.

3. Limbaje de comunicare inter-agent Limbajele KQML (1994) și ACL (1999) sunt limbaje care definesc formatul mesajelor, independent de conținut. Se bazează pe o serie de performative predefinite, care definesc intenția de interpretare a mesajelor. Exemplu de mesaj ACL: (inform :sender agent1 :receiver agent2 :content (price good2 150) :language sl :ontology hp1-auction) ACL are 22 de performative, specificate în mod formal. Cele mai importante sunt inform, pentru transmiterea unor informații, și request, care permite unui agent să ceară altui agent să efectueze o acțiune. Conținutul unui mesaj poate fi exprimat prin orice limbaj. O încercare de standardizare în acest sens este reprezentată de limbajul KIF, bazat pe logica predicatelor de ordin întâi, destinat descrierii

157

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

proprietăților dintr-un domeniu și implicit comunicării de informații între agenți. Exemple de informații în limbajul KIF: (salary 015-46-3946 widgets 72000) (salary 026-40-9152 grommets 36000) (salary 415-32-4707 fidgets 42000) (> (* (width chip1) (length chip1)) (* (width chip2) (length chip2))) (=> (and (real-number ?x) (even-number ?n)) (> (expt ?x ?n) 0)) O ontologie este o specificare a obiectelor, conceptelor și relațiilor dintre acestea într-un anumit domeniu de interes. Ontologiile ajută agenții să „înțeleagă” vocabularul unui domeniu și facilitează comunicarea între agenți provenind din surse diferite.

158

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

29. Algoritmi de căutare a căilor pentru sisteme multi-agent Pentru aplicarea algoritmilor de căutare precum A*, se presupune că mediul este determinist și complet observabil. În cazul agenților, mediile sunt mai complexe și necesită alte variante de algoritmi de căutare. În aceste medii deschise, acțiunile pot fi nedeterministe, efectele acțiunilor nu sunt garantate și/sau agentul nu poate percepe în totalitate starea mediului. Planul rezultat, adică secvența de acțiuni, poate fi utilizat, de exemplu, în conjuncție cu arhitectura BDI.

1. Căutarea în medii nedeterministe În mediile nedeterministe, acceași acțiune poate avea rezultate diferite. Fie problema simplă din figura următoare (Russell & Norvig, 2002), cu un aspirator mobil într-un mediu cu două celule, A și B, în care acțiunile sunt de mișcare (Left, Right) și de aspirare (Suck), iar starea celulelor poate fi curată (Dirty) sau murdară (Clean).

În acest caz, planul se reprezintă ca un arbore de căutare ȘI-SAU, în care distingem între noduri în care agentul decide ce acțiune să efectueze, 159

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

numite noduri SAU, și noduri care reprezintă efectele posibile ale unei acțiuni, adică stările care pot rezulta din aplicarea unei acțiuni într-o stare, numite noduri ȘI (fig. Russell & Norvig, 2002).

Agentul trebuie să găsească un plan pentru fiecare stare posibilă. Prin urmare, o soluție este reprezentată de o succesiune de acțiuni și teste, de exemplu [Suck, if State = 5 then [Right, Suck] else []], care asigură faptul că starea scop este atinsă pe toate căile pe care le poate traversa agentul în arbore, din cauza mediului nedeterminist. Algoritmul de căutare a soluției este următorul (Russell & Norvig, 2002):

160

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Când nedeterminismul poate determina ca o acțiune câteodată să nu aibă niciun efect, există soluții ciclice, de exemplu [while State = 5 do Right].

2. Căutarea în medii parțial observabile 2.1. Căutarea fără observații Deși mediul nu este observabil, agentul are o mulțime de stări de convingeri (belief states), care indică în ce stări fizice crede agentul că s-ar putea găsi. În exemplul cu aspiratorul, starea inițială de convingeri poate fi mulțimea tuturor celor opt stări fizice. Dacă agentul face o acțiune, de exemplu Left, cardinalitatea mulțimii de stări fizice în care s-ar putea afla agentul se reduce la jumătate: dacă mediul este determinist, după Left, agentul nu mai poate fi în celula B, indiferent de celula în care era inițial. Fiecare acțiune poate reduce cardinalitatea stărilor de convingeri, până când se ajunge în starea scop. Căutarea se face în spațiul stărilor de convingeri, nu în spațiul stărilor mediului fizic (fig. Russell & Norvig, 2002).

161

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2.2. Căutarea cu observații limitate Orice percept observat reduce cardinalitatea stării de convingeri și deci ajută procesul de căutare. De exemplu, în figura următoare agentul face o acțiune, percepe starea celulei curente, iar mediul este nedeterminist în sensul că orice celulă poate deveni murdară în orice moment. Starea de convingeri curentă este reprezentată ca un cerc sau o elipsă ce conține stările fizice posibile în care s-ar putea afla agentul (fig. Russell & Norvig, 2002).

162

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Căutarea online Algoritmul A* clasic este un algoritm offline, deoarece agentul poate expanda orice stare din graful problemei la un moment dat, nu doar stări vecine. În căutarea online, agentul este fizic parte din mediu și nu poate vizita la momentul următor decât o stare vecină cu starea curentă. 3.1. Algoritmul LRTA* Se presupune că agentul este în starea i și cunoaște euristica stării curente h(i), adică estimarea distanței din starea i către starea scop. Fie k(i, j) costul cunoscut dintre stările i și j. Funcția h trebuie să fie admisibilă, adică să nu supraestimeze distanța reală: h(i) ≤ h*(i). Dacă numărul de stări este finit, costurile sunt pozitive și există o cale de la orice stare la starea scop iar euristica este admisibilă, algoritmul LRTA* este complet, adică garantează că ajunge în starea scop. În cazul cel mai defavorabil, explorează un mediu cu n stări în O(n2) pași. Algoritmul învață soluția optimă prin încercări repetate, de unde și numele său. Pseudocod (Weiss, 2000):

163

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3.2. Algoritmul RTA* Deși h trebuie să fie mai mică decât distanța reală, cu cât h este mai mare, cu atât algoritmul găsește mai repede soluția. Dacă h(i) > h*(i), algoritmul poate să nu găsească soluția optimă. RTA* încearcă să mărească artificial h prin utilizarea funcției secondmin în loc de min. Algoritmul RTA* este, de asemenea, complet. Pseudocod (Weiss, 2000):

4. Căutarea în medii dinamice Există algoritmi aplicabili atunci când mediul se poate modifica în timpul căutării. Dintre aceștia, menționăm: 



consideră că starea scop a căutării se modifică, adică agentul urmărește o țintă care poate încerca să îl evite în mod activ. Pentru ca problema să poată fi rezolvată, ținta trebuie să aibă o viteză mai mică decât agentul. MTS este asemănător cu LRTA*, dar formulele sunt mai simple deoarece se consideră că agentul și ținta se deplasează la fiecare pas într-o celulă învecinată pe grid. Exemple din viața reală sunt interceptoarele de rachete; LPA* (Life-long Planning A*): generalizează algoritmul A* pentru a trata situații în care graful se modifică, pentru a găsi calea cea mai scurtă MTS (Moving Target Search):

164

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com





de la un nod de start la un nod scop. Deoarece folosește informații de la căutarea anterioară, numărul de noduri examinate este mult mai mic decât dacă ar fi aplicat din nou, de la zero, algoritmul A*; D* lite: aplică LPA* pentru a găsi calea cea mai scurtă către un nod scop în situația în care agentul se mișcă pe o traiectorie într-un graf care se modifică. Prin urmare, diferența față de LPA* este că nodul de start se modifică și el. Acești doi algoritmi sunt eficienți când schimbările din graf au loc în vecinătarea agentului. Dacă schimbările au loc lângă nodul scop, o căutare A* de la zero poate fi mai eficientă; Field D*: este o variantă a D* lite în care mișcarea nu este constrânsă de un grid. Unghiurile de deplasare au valori reale, într-un domeniu continuu. Este util pentru a genera traiectorii netede pentru roboți mobili. Roverele NASA de pe Marte folosesc acest algoritm.

165

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

30. Teoria jocurilor Reprezentarea unui joc în formă normală, de exemplu, dilema deținutului (prisoner’s dilemma):

Deținutul 1

Deținutul 2 Neagă Mărturisește –1, –1 –5, 0 0, –5 –3, –3

Neagă Mărturisește

Fiecărei combinații de acțiuni îi corespund câștiguri (payoffs) pentru cei doi agenți. De exemplu, dacă agentul 1 mărturisește și agentul 2 neagă, agentul 1 primește 0, iar agentul 2 primește –5. Agenții decid simultan, fără să știe unul decizia celuilalt. Fiecare agent trebuie să aleagă acțiunea optimă, care îi aduce un câștig maxim, indiferent de decizia celuilalt. Combinația acestor acțiuni optime corespunde unei stări de echilibru și este soluția jocului.

1. Dominanța O strategie S domină o strategie T dacă orice rezultat al lui S este cel puțin la fel de bun ca rezultatul corespunzător al lui T. Dacă fiecare agent are o strategie dominantă și o joacă, atunci combinația acestora și câștigurile corespunzătoare constituie echilibrul strategiilor dominante ale jocului Principiul dominanței de ordin superior: se elimină în mod iterativ strategiile dominate și se rezolvă jocul care rezultă în final, de exemplu:

166

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2. Jocuri de sumă nulă cu doi agenți Pentru fiecare combinație de acțiuni, câștigul unui agent este p și câștigul celuilalt este –p, de exemplu:

2  1 1  2   Pentru jocurile de sumă nulă, vorbim de echilibru minimax. Un rezultat este un echilibru minimax pur dacă este minimul liniei și maximul coloanei sale (fig. Straffin, 1993).

Câștigul agenților la echilibru reprezintă valoarea jocului. Echilibrul se numește pur dacă este determinist. Dacă un joc nu are echilibru pur, se poate găsi un echilibru mixt, care implică probabilități de alegere a acțiunilor. O strategie mixtă reprezintă o combinație de strategii cu probabilități fixe (probabilitățile sunt fixe, nu strategiile alese la un moment dat). De exemplu, un agent alege strategia A cu probabilitatea de 25% și strategia B cu probabilitatea de 75%. Calculul echilibrului minimax mixt presupune determinarea acestor probabilități pentru un joc anume. În acest caz, vorbim de câștiguri așteptate, adică suma câștigurilor pentru fiecare strategie posibilă înmulțite cu probabilitatea de alegere a strategiei respective. La echilibru, câștigurile așteptate ale tuturor strategiilor trebuie să fie egale. Dacă o strategie ar avea un câștig mai mare, ar fi aleasă în mod determinist. Mai jos, numim Rose agentul care decide pe linii și Colin agentul care decide pe coloane.

167

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

 3  3  4 2   

R1 : 3x   3  1  x   6 x  3

R2 :  4  x  2  1  x   2  6 x Colin alege x astfel încât 6 x  3  2  6 x . Fie x0 soluția acestei ecuații. Se poate verifica ușor că x0  5 / 12 și că 6 x0  3  2  6 x0  1 / 2 . Atunci, câștigul așteptat al lui Rose este:   1 / 2 E PR    y, 1  y     1 / 2   1 / 2

La fel se determină probabilitățile strategiilor lui Rose, din egalitatea câștigurilor așteptate ale lui Colin. Jocurile (2 x n) și (m x 2) pot fi întotdeauna reduse la jocuri (2 x 2). Pentru un joc (m x 2), doar două strategii pot aduce câștiguri așteptate de valoare maximă. Ecuațiile câștigurilor așteptate determină niște drepte într-un plan. Intersecția lor reprezintă echilibrul minimax mixt. În general, trebuie găsită valoarea y minimă regiunii hașurate. Acest y este valoarea jocului. Punctul minim este intersecția a doar două drepte. Acestea corespund strategiilor cu probabilități nenule. Coordonatele x sunt aceste probabilități (fig. Straffin, 1993).

168

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Un joc (2 x n) poate fi transpus, rezultând un joc (n x 2), care se rezolvă cu metoda anterioară. Jocurile (m x n) nu pot fi reduse la jocuri (2 x 2) și se rezolvă prin metode de programare liniară. Avantajul principal al soluției minimax este garantarea unui câștig minim, independent de decizia celuilalt agent.

3. Jocuri de sumă generală cu doi agenți O combinație de strategii este un echilibru Nash dacă fiecare agent își maximizează câștigul, date fiind strategiile folosite de ceilalți agenți. Echilibrul Nash identifică acele combinații de strategii care sunt stabile, în sensul că fiecare agent este mulțumit cu acțiunea aleasă, date fiind acțiunile celorlalți. Din stările de echilibru, niciun agent nu-și poate mări câștigul prin schimbarea unilaterală a strategiei.

169

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3.1. Calculul echilibrelor Nash pure Se evidențiază maximele pe linii pentru primul agent cu „{” . Se evidențiază maximele pe coloane pentru al doilea agent cu „}”. Stările încadrate de „{ }” sunt echilibre Nash pure.

Deținutul 1

Deținutul 2 Neagă Mărturisește –1, –1 –5, 0 } { 0, –5 { –3, –3 }

Neagă Mărturisește

Unele jocuri nu au echilibru Nash pur. Folosind o strategie pură, agentul i alege determinist strategia sij din mulțimea Si. Folosind o strategie mixtă, agentul i alege strategia sij cu probabilitatea pij, astfel încât pij  0, j pij = 1. Un joc finit are întotdeauna cel puțin un echilibru Nash pur sau mixt. O strategie mixtă are întotdeauna un echilibru Nash. Câștigul în strategii mixte este câștigul așteptat. 3.2. Calculul echilibrului Nash mixt

Guvernul

Cerșetorul Muncește Nu muncește 3, 2 –1, 3 –1, 1 0, 0

Ajută Nu ajută

Determinarea strategiei pentru Cerșetor: 3 · x + (–1) · (1 – x) = (–1) · x + 0 · (1 – x) ⇒ x = 0,2, 1 – x = 0,8 Determinarea strategiei pentru Guvern: 2 · y + 1 · (1 – y) = 3 · y + 0 · (1 – y) ⇒ y = 0,5, 1 – y = 0,5

170

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Un rezultat este optim Pareto dacă este mai bun sau la fel decât orice alt rezultat din toate punctele de vedere și mai bun strict din cel puțin un punct de vedere. Optimalitatea Pareto înseamnă o situație mai bună pentru cel puțin un agent fără a dezavantaja niciun alt agent. Într-o stare optimă Pareto, agenții nu au motivația de a devia în coaliție. În cazul dilemei deținutului, ambii agenți au un câștig mai mare împreună dacă ambii neagă.

Deținutul 1

Deținutul 2 Neagă Mărturisește –1, –1 –5, 0 0, –5 –3, –3

Neagă Mărturisește

4. Jocuri cooperante cu doi agenți În jocurile necooperante, se presupune că agenții sunt raționali și egoiști. Prin cooperare, agenții pot obține un câștig mai mare. Problema este împărțirea câștigului suplimentar obținut. Soluția pentru un joc cooperant cu doi agenți: câștigul total este valoarea maximă din matricea sumă, iar diferența de câștig dintre agenți este diferențiala amenințării. Exemplu: Peugeot

Renault

F –10, –40 10, 40

F M

M 40, 10 –40, –10

Matricea sumă (sum matrix) a jocului reflectă câștigul total care poate fi obținut prin cooperare:  50 50  RP   50  50

171

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Matricea amenințărilor (threat matrix) este utilizată pentru descrierea puterii de negociere a agenților: 30   30 RP   30  30

Diferențiala amenințării (threat differential) este valoarea jocului pentru matricea amenințărilor, în acest caz 30. Nu contează strategiile jucate, atât timp cât se obține câștigul total și se respectă modul de împărțire a acestuia. Pentru strategiile (R:F / P:M), câștigurile agenților sunt cele date direct de rezultatul jocului. Pentru strategiile (R:M / P:F), P trebuie să îi plătească 30 de unități lui R.

5. Jocuri cooperante cu n agenți 5.1. Nucleul O alocare (imputation) este mulțimea de câștiguri (x1, x2, ..., xn) care satisface următoarele condiții: suma câștigurilor este maximul posibil, iar fiecare agent obține un câștig cel puțin la fel de bun ca acela obținut dacă nu ar coopera. Nucleul (core) unui joc cu n agenți este mulțimea alocărilor nedominate. Nucleul unui joc cu funcția caracteristică v este mulțimea tuturor alocărilor x = (x1, x2, ..., xn) astfel încât, pentru orice coaliție S = {Pi1, Pi2,…, Pim}, avem: xi1 + xi2 + … + xim ≥ v(S). Orice alocare din nucleu poate fi privită ca o soluție a jocului. Nucleul este stabil. Dacă o alocare nu se află în nucleu, atunci există cel puțin o coaliție ai cărei membri nu obțin câștigul maxim pe care l-ar putea obține altfel. Acești agenți preferă o altă alocare. Exemplu: 3 studenți doresc să cumpere o carte, care costă 110 unități monetare. Pentru 2 cărți sau 3 cărți cumpărate împreună, există o reducere de 10, respectiv 20 unități / exemplar. Valorile coalițiilor exprimă banii economisiți. Această reprezentare a jocului se numește formă caracteristică. 172

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

v({P1 )}  v({P2 )}  v({P3 )}  0 v({P1 , P2 )}  v({P1 , P3 )}  v({P2 , P3 )}  20 v({P1 , P2 , P3 )}  60 Fie x = (x1, x2, x3) o alocare din nucleu. Atunci:

x1  v({P1})  0, x2  v({P2 })  0, x3  v({P3})  0, x1  x2  v({P1 , P2 })  20, x1  x3  v({P1 , P3})  20, x2  x3  v({P2 , P3})  20, x1  x2  x3  v({P1 , P2 , P3})  60 Nucleul oferă o mulțime de soluții pentru un joc. Unele jocuri nu au nucleu. Nu există o modalitate de a evalua „corectitudinea” alocărilor din nucleu. 5.2. Valoarea Shapley Valoarea Shapley se bazează pe ideea că fiecare agent trebuie să primească un câștig corespunzător contribuției sale marginale la coaliție. Pentru n agenți, există n! ordonări în care un agent se poate alătura celorlalți. Valoarea Shapley reprezintă media după toate ordonările posibile:

 ( A, i ) 

1   v B( , i )  i   v B( , i )  A!   A

Exemplu: Fie un joc cu 2 agenți și următoarea formă caracteristică: v({ }) = 0, v({1}) = 1, v({2}) = 3, v({1, 2}) = 6. Există 2! permutări posibile: (1, 2) și (2, 1). Valorile Shapley sunt:

1 2

1 2

1 2

1 2

 (1)   v(1)  v()  v(2, 1)  v(2)    (1  0  6  3)  2

 (2)   v(1, 2)  v(1)  v(2)  v()    (6  1  3  0)  4 173

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Valoarea Shapley există întotdeauna, este unică și este întotdeauna fezabilă (suma câștigurilor agenților este maximă). Poate să nu aparțină nucleului, chiar dacă jocul are nucleu; în acest caz, este instabilă. Nucleul unui joc convex este întotdeauna nevid, iar valoarea Shapley aparține nucleului și este în centrul său de greutate. 5.3. Nucleolus Nucleolus este valoarea determinată prin minimizarea iterativă a exceselor coalițiilor. Pentru fiecare alocare x și coaliție S, definim excesul lui S în x astfel:

eS (x)  v( S )   xi iS

Excesul poate fi considerat o măsură a „nefericirii” coaliției S în cazul alocării x. Scopul este de a găsi alocarea care minimizează cel mai mare exces es(x), adică încercăm să facem cea mai nefericită coaliție cât mai puțin nefericită. Se calculează iterativ, rezolvând succesiv o serie de programe liniare. Pentru trei agenți, există formule directe. Nucleolus este punctul cel mai interior al nucleului. Există întotdeauna și este unic. Se află în nucleu dacă nucleul nu este vid, deci este stabil.

6. Jocuri secvențiale Într-un joc secvențial, jucătorii decid unul după altul, cu sau fără informații complete despre deciziile celorlalți. Aceste jocuri se reprezintă în formă extinsă, adică succesiunea de decizii se reprezintă ca un arbore, în care ramurile exprimă deciziile, iar frunzele exprimă câștigurile corespunzătoare combinațiilor de decizii care au condus acolo.

174

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Pentru un astfel de arbore, strategiile jucătorilor sunt combinațiile care stabilesc în mod unic o stare finală în arbore. Fie următorul exemplu, un joc secvențial de sumă nulă (Straffin, 1993).

Colin are 13 strategii pure: AJM, AKM, ALM, BNP, BOP, CQS, CQT, CQU, CQV, CRS, CRT, CRU și CRV. CRS înseamnă că agentul Colin alege mai întâi C, iar dacă Rose alege H sau I, atunci Colin alege R sau S, respectiv. Rose are 8 strategii pure: DFH, DFI, DGH, DGI, EFH, EFI, EGH și EGI. EFH înseamnă că Rose alege E, F sau H dacă agentul Colin alege A, B sau C, respectiv. O mulțime informațională (information set) este o mulțime care stabilește toate mutările posible pentru un anumit agent, având în vedere informațiile primite până atunci de acel agent. Dacă jocul are informații perfecte, orice mulțime informațională are un singur element. Dacă nu, unii agenți nu pot ști exact care este poziția lor în joc, iar unele mulțimi informaționale conțin mai multe elemente. Agenții în cauză nu pot face distincția între elementele (nodurile) unei mulțimi informaționale. În consecință, pentru toate nodurile unei mulțimi informaționale, deciziile disponibile pentru un jucător sunt aceleași.

175

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Fie următorul joc (Straffin, 1993):

Aici, Rose nu poate distinge stările rezultate după ce Rose a ales A iar Colin D sau E. Pentru Rose, aceste noduri trebuie tratate la fel, deci poate alege doar I sau J. La fel, Colin nu poate distinge stările rezultate după ce Rose a ales B sau C, prin urmare el poate alege doar între G și H în ambele noduri. Matricea jocului este următoarea (Straffin, 1993):

Algoritmul lui Zermelo poate rezolva un joc secvențial cu informații perfecte. Pleacă de la ultimul nivel din arbore și identifică deciziile optime pe care agenții le fac pe acel nivel. Presupunând că un agent face alegerile optime, nodurile de pe ultimul nivel devin frunze (mutările cele mai bune).

176

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Procesul se repetă pentru jucătorul care decide pe penultimul nivel și așa mai departe până în rădăcină. Pentru jocul din figura anterioară, pașii algoritmului sunt următorii (Straffin, 1993):

În acest exemplu, Colin alege mutările care conduc la valorile minime de pe nivelul său, deoarece este un joc de sumă nulă. Rose alege mutările care conduc la valorile maxime de pe nivelul său. În cazul în care jocul are mulțimi informaționale, algoritmul lui Zermelo se aplică doar pentru nodurile cu informații perfecte. Atunci când se ajunge la o mulțime informațională cu mai multe elemente, agentul trebuie să decidă fără să știe ce a decis celălalt agent, ceea ce este echivalent cu un joc strategic. De exemplu, în jocul următor Colin poate aplica algoritmul lui Zermelo, reținând minimele, dar Rose nu poate, deoarece nu cunoaște prima mutare a lui Colin (fig. Straffin, 1993).

177

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

După reducerea arborelui făcută de Colin, arborele devine (fig. Straffin, 1993):

Jocul se transformă într-un joc strategic, cu matricea următoare, care are un echilibru Nash mixt, cu strategiile lui Rose (l, r) = (1/2, 1/2) și ale lui Colin (H, T) = (1/2, 1/2), iar valoarea jocului este 1/2.

l r

H –1 2

178

T 2 –1

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

31. Protocoale pentru licitații Protocoalele de licitație se clasifică în două mari categorii: 



Licitații cu strigare (open outcry): o Licitația engleză (English auction): Se pornește de la un preț mic și se crește prețul, iar participanții (bidders) licitează (bid) dacă acceptă prețul curent. Când nimeni nu mai licitează, articolul este vândut participantului care a acceptat ultimul preț, cel mai mare; o Licitația olandeză (Dutch auction): Se pornește de la un preț foarte mare și se scade prețul până când un participant îl acceptă. Articolul este vândut acestui participant. Licitația olandeză este mai rapidă și se folosește în viața reală pentru produse perisabile, de exemplu, piața de flori, pește etc. Licitații cu plic închis (sealed bid): o Licitația cu primul preț (first-price): Participanții trimit oferte în plicuri închise, acestea sunt deschise și comparate și câștigă oferta cea mai mare; o Licitația Vickrey: Participanții trimit oferte în plicuri închise, acestea sunt deschise și comparate și câștigă participantul care a făcut oferta cea mai mare, dar plătește al doilea preț.

În licitația Vickrey, strategia corectă a participanților este de a oferi valoarea pe care o consideră adevărată. Nu câștigă mai mult dacă licitează mai mult (pentru că vor plăti oricum al doilea preț), iar dacă licitează mai puțin decât valoarea adevărată ar putea pierde licitația (deși licitând prețul adevărat ar fi putut câștiga). Licitațiile pot avea: 

O valoare subiectivă, sentimentală, de exemplu, un articol care a aparținut unei celebrități și care valorează mai mult pentru un fan decât pentru o altă persoană; 179

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com



O valoare obiectivă, care poate fi măsurată, dar care nu este cunoscută exact în momentul licitației.

Pentru o licitație cu valoare obiectivă, participanții fac oferte conform cu aprecierea lor asupra valorii. Se poate considera că media acestor oferte reprezintă valoarea reală. Prin urmare, câștigătorul oferă mai mult decât valoarea reală. Acest fenomen se numește blestemul câștigătorului (winner’s curse). Mai există licitații în care toți participanții plătesc, dar doar unul câștigă (all-pay): de exemplu, în competiții în care toți fac un efort, dar există doar un singur câștigător în final. Pentru licitarea unui bun cu valoarea 1, strategia de echilibru pentru n participanți este de a licita 1 / n. În funcție de atitudinea față de risc, participanții pot fi:   

Neutri față de risc (risk neutral); Cu aversiune față de risc (risk averse); Cu înclinație față de risc (risk loving).

Pentru participanții neutri față de risc, toate tipurile de licitații oferă același profit (revenue equivalence), egal cu al doilea preț. La licitația engleză, un participant câștigă când se depășește prețul celui de-al doilea participant care a mai rămas în licitație. La licitația Vickrey, câștigătorul plătește direct al doilea preț. Licitația olandeză este echivalentă cu licitația cu primul preț. În acest caz, participanții încearcă să-și mărească profitul licitând mai puțin decât valoarea adevărată. Se poate demonstra matematic că valoarea licitată este de asemenea egală cu al doilea preț. Participanții cu aversiune față de risc vor să câștige chiar plătind mai mult, pentru a nu risca să piardă licitația. Aceștia plătesc mai mult în licitația cu primul preț sau olandeză decât în licitația Vickrey. În licitația engleză, atitudinea față de risc este irelevantă, deoarece prin procesul de licitare sunt dezvăluite evaluările celorlalți participanți. Prin urmare, participanții cu aversiune față de risc preferă licitația Vickrey sau licitația engleză.

180

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Licitații combinatorice Este tipul de licitație cel mai folosit în sistemele multi-agent. Se licitează mai multe articole, iar fiecare agent trimite oferte pentru combinații de articole. Fiecare articol poate fi vândut o singură dată, iar profitul vânzătorului trebuie maximizat. Problema determinării câștigătorilor unei astfel de licitații este NP-dificilă. Este o problemă de optimizare cu constrângeri, care se poate rezolva prin transformarea într-o problemă de programare liniară.

181

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

32. Protocoale de votare Votarea este o modalitate de agregare a preferințelor. Noțiunea de „candidat” este generală și poate reprezenta orice tip de decizie pe care trebuie să o ia împreună agenții: un plan comun, o anume alocare de resurse sau task-uri etc. Agenții au interese diferite și pot minți pentru a influența rezultatul final. Când există doar două alternative, se aplică votul majoritar: câștigă alternativa care are majoritatea voturilor, adică peste jumătate. Este singura situație care poate fi tratată în mod optim. Când există mai multe alternative, există mai multe protocoale: 







Votul cu un singur tur (plurality voting): Câștigă alternativa cu cele mai multe voturi, chiar dacă nu are peste jumătate. Este cel mai simplu sistem de vot. Favorizează competiția între primele două alternative; Votul de aprobare (approval voting): Participanții dau câte un vot fiecărei alternative pe care o aprobă și deci pot vota mai multe alternative. Alternativa cu cele mai multe voturi câștigă. Favorizează alternativele moderate față de cele extremiste; Votul unic transferabil (single transferable vote): Votanții indică ordinea preferințelor pentru toate alternativele, sau o parte din acestea. Se numără voturile de pe poziția 1. Dacă nicio alternativă nu obține majoritatea, se elimină ultima alternativă, iar pentru votanții care au ales-o pe aceasta pe locul 1, acest loc este preluat de alternativa lor de pe locul 2. Procesul se repetă până când o alternativă obține majoritatea; Numărătoarea Borda (Borda count): Votanții indică ordinea preferințelor pentru toate alternativele, sau o parte din acestea. Fie n numărul de alternative. Alternativa de pe primul loc la un agent primește n puncte, următoarea n-1, iar alternativa de pe ultimul loc 1 182

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

punct. Există și varianta atribuirii de la n-1 la 0 puncte. Punctele se sumează pentru toți agenții. Alternativa cu cele mai multe puncte este câștigătoare. Poate conduce la paradoxul inversării (reversal paradox): eliminarea alternativei celei mai puțin dorite poate conduce la schimbarea câștigătorului. Un dezavantaj practic al acestor metode este că agenții trebuie să își genereze o ordonare a preferințelor, ceea ce uneori poate fi costisitor din punct de vedere computațional. Pentru mai multe alternative, se definește câștigătorul Condorcet ca fiind alternativa care ar câștiga alegerile 1 la 1 cu toate celelalte alternative (care ar bate toți ceilalți candidați într-o confruntare directă cu fiecare în parte). Un sistem de vot care dă câștigătorul Condorcet atunci când acesta există se numește metodă Condorcet. Metode Condorcet sunt: 



Metoda Copeland: Alternativele sunt ordonate după numărul de victorii în pereche minus numărul de înfrângeri. Alternativa cu scorul cel mai mare este câștigătoare; Metoda Schultze este cea mai răspândită metodă Condorcet. Are o descriere mai complexă1.

Votul cu un singur tur (plurality voting) și numărătoarea Borda nu respectă criteriul Condorcet. O euristică pentru alegerea câștigătorului este următoarea: se selectează câștigătorul Condorcet dacă acesta există, iar dacă nu, se folosește numărătoarea Borda. Teorema imposibilității a lui Arrow: niciun sistem de vot nu poate îndeplini simultan următoarele principii: 1

https://en.wikipedia.org/wiki/Schulze_method

183

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

1. Să fie complet (să ordoneze toate alternativele); 2. Să fie tranzitiv; 3. Din două alternative A și B, dacă toți votanții preferă pe A lui B, în rezultatul votului A să fie deasupra lui B; 4. Ordonarea să se bazeze exclusiv pe preferințele votanților individuali; 5. Să nu fie dictatorial (rezultatul să nu fie determinat de preferințele unui singur agent); 6. Să fie independent de alternativele irelevante (schimbările din lista de alternative, adică adăugarea sau eliminarea unor candidați să nu modifice ordonarea celorlalți candidați neafectați de schimbări). Teorema Gibbard-Satterthwaite: dacă există 3 sau mai multe alternative, pentru orice sistem de vot este îndeplinit unul din următoarele principii: 1. Sistemul de vot este dictatorial; 2. Există un candidat care nu poate niciodată câștiga; 3. Sistemul de vot poate fi manipulat. Întrucât primele două condiții sunt inacceptabile, rezultă că orice sistem de vot este manipulabil.

Manipularea strategică a voturilor  

Votul cu un singur tur (plurality voting): Dacă A este mai bine cotat decât B, B introduce un nou candidat C, care să ia voturi de la A; Votarea în perechi (procedura de amendare): Există 3 alternative: A, B, C. Se votează A vs. B, apoi câștigătorul vs. C. Gruparea alternativelor din prima rundă de vot favorizează votul strategic și poate schimba rezultatul final (paradoxul agendei).

Chiar dacă orice sistem de vot este manipulabil, se poate imagina un protocol NP-dificil de manipulat. De exemplu, următorul meta-protocol 184

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

adaugă un pas suplimentar înainte de aplicarea unui protocol standard de votare P. Candidații sunt mai întâi grupați aleatoriu în perechi. Se fac alegeri în perechi și cine pierde este eliminat. Candidații rămași intră în procesul de votare definit de protocolul P.

185

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

33. Protocoale de negociere Negocierea este o formă de interacțiune în care un grup de agenți cu obiective contradictorii dar cu dorința de a coopera, încearcă să ajungă la o înțelegere acceptabilă privind alocarea unor resurse limitate. Pentru fiecare înțelegere (deal) posibilă, un agent are o anumită utilitate, notată cu u. Funcția de utilitate reprezintă nivelul de satisfacție pe care îl are un agent pentru o anumită stare de fapt, de exemplu, consecințele unei înțelegeri. Agenți diferiți au de obicei funcții de utilitate diferite. Un agent rațional încearcă să ajungă la o înțelegere care îi maximizează utilitatea. Înțelegerea de conflict (conflict deal) reprezintă situația în care agenții nu ajung la o înțelegere. O înțelegere δ domină altă înțelegere δ' dacă: i ui ( )  ui ( ' ) și

i ui ( )  ui ( ' ) , unde i reprezintă indecșii agenților implicați. O înțelegere individual rațională este o înțelegere care domină înțelegerea de conflict. O înțelegere optimă Pareto este o înțelegere care nu este dominată de nicio altă înțelegere. Mulțimea de negociere (negotiation set) reprezintă mulțimea tuturor înțelegerilor individual raționale și optime Pareto.

1. Concepte de soluții axiomatice (axiomatic solution concepts) 

Soluția egalitaristă (egalitarian solution): toți agenții primesc aceeași utilitate și suma utilităților este maximizată:

186

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

  argmax  ui ( ' ) , E  { | i , j ui ( )  u j ( )}  'E



i

Bunăstarea socială egalitaristă (egalitarian social welfare): maximizează utilitatea primită de agentul cu cea mai mică utilitate:

  argmax min ui ( ' ) i

'



Soluția utilitaristă (utilitarian solution): maximizează suma utilităților:

  argmax  ui ( ' ) '

 

i

Soluția Kalai-Smorodinsky: înțelegerea în care utilitățile agenților sunt proporționale cu utilitățile maxime pe care le-ar putea obține; Soluția Nash: maximizează produsul utilităților:

  argmax  ui ( ' ) '

Soluția Nash este singura soluție care respectă o serie de axiome dorite: eficiență Pareto, independență de unitățile de măsură ale utilității, simetrie și independență de alternativele irelevante.

2. Concepte de soluții strategice (strategic solution concepts) 2.1. Modelul ofertelor alternative al lui Rubinstein Agenții își cunosc reciproc funcțiile de utilitate. Ei propun alternativ înțelegeri, pe care partenerul de negociere le acceptă sau le respinge. O înțelegere nu poate fi propusă de mai multe ori. Pentru a exista o soluție de echilibru, se presupune că utilitățile agenților scad în timp cu un factor de actualizare (discount factor). Fie γ1 și 187

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

γ2 factorii de actualizare ai celor doi agenți. Dacă agentul 1 propune primul, atunci soluția de echilibru pentru o unitate de utilitate (u1 + u2 = 1) este:

 1   2  1  1   2    , 1 1  2 1 1  2 

u1 , u2   

Dacă factorii de actualizare sunt egali, agenții câștigă în soluția de echilibru: 1  , 1  1 

u1 , u2   

  

Agentul care propune primul câștigă mai mult. De asemenea, un factor de actualizare mai mic conduce la un câștig mai mic. 2.2. Protocolul concesiilor monotone (monotonic concession protocol) Pseudocod (Vidal, 2007):

2.3. Strategia Zeuthen (Zeuthen Strategy) Se definește riscul unui agent ca fiind:

riski 

u1 u2

188

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

unde Δu1 este utilitatea pe care o pierde i dacă acceptă oferta lui j, iar Δu2 este utilitatea pe care o pierde i dacă nu acceptă și determină conflictul. Dacă ui(δi) = 0, se consideră riski = 1. Valori mari ale riscului, apropiate de 1, înseamnă că agentul are puțin de pierdut dacă nu se ajunge la o înțelegere și prin urmare este dispus să riște eșecul negocierii. Valori mici ale riscului, apropiate de 0, înseamnă că agentul are mai mult de pierdut dacă se ajunge la conflict. La fiecare pas, agentul cu risc mai mic face o concesie: cea mai mică concesie care schimbă totuși balanța riscurilor. Pseudocod (Vidal, 2007):

Strategia Zeuthen converge la soluția de negociere Nash. Această soluție este un echilibru Nash, prin urmare strategia de negociere a agentului poate fi făcută publică, iar ceilalți agenți nu pot exploata această informație prin alegerea altei strategii.

189

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

2.4. Protocolul cu un singur pas (one-step protocol) Pseudocod (Vidal, 2007):

3. Negocieri bazate pe argumentare Se definește un graf de argumente, care se atacă unele pe altele (fig. Wooldridge, 2002).

Negocierea se desfășoară ca un joc secvențial, în care un agent aduce un argument, celălalt încearcă să găsească un argument care atacă unul din argumentele primului agent ș.a.m.d. până când agentul care face ultima „mutare” câștigă. 190

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

34. Proiectarea mecanismelor În situații care presupun luarea unor decizii comune, de exemplu prin vot, unii agenți ar putea avea un avantaj dacă mint, adică dacă preferințele lor raportate sunt diferite de preferințele lor reale. Proiectarea mecanismelor are ca scop determinarea modalităților de proiectare a unui sistem în care agenții nu au nimic de câștigat dacă mint în legătură cu preferințele lor private. În general, se consideră că scopul sistemului este maximizarea bunăstării sociale, adică maximizarea sumei utilităților agenților. Există mai multe mecanisme propuse: 



Mecanismul Groves-Clarke: Fiecare agent primește o utilitate suplimentară, egală cu suma utilităților celorlalți agenți din sistem. Prin urmare, fiecare agent are o motivație directă de a contribui la bunăstarea celorlalți agenți; Mecanismul Vickrey-Clarke-Groves: Pleacă de la aceeași idee, de a oferi agenților o utilitate suplimentară, dar plățile sunt diferite. Utilitatea suplimentară primită de un agent i este de forma a – b, unde a este suma utilităților tuturor celorlalți agenți, iar b este suma utilităților tuturor celorlalți agenți în cazul în care i nu ar fi existat.

Se poate observa că licitația Vickrey folosește acest model: câștigătorul primește diferența dintre rezultatul licitației câștigate de el și rezultatul licitației fără el, în care ar fi câștigat a doua ofertă. Faptul că mecanismul trebuie plătească o sumă agenților nu este neapărat de dorit. Folosind regula pivotului a lui Clarke, agenții trebuie să plătească ei o taxă dacă prin votul lor se schimbă decizia care ar fi fost luată de restul agenților. Pentru un agent i, se calculează suma utilităților tuturor agenților și suma utilităților celorlalți agenți, fără i. În fiecare caz, se determină decizia care maximizează suma utilităților. Dacă prin intervenția lui i decizia sistemului se schimbă, adică i este pivotal, acesta trebuie să plătească o taxă egală cu diferența de utilitate a celorlați agenți cauzată de schimbarea rezultatului. 191

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

35. Protocolul rețelelor de contracte (contract net protocol) Este un protocol pentru alocarea task-urilor. Se presupune că pentru execuția task-urilor, agenții au o serie de costuri, iar combinații diferite de task-uri conduc la costuri diferite. Pentru creșterea utilității, agenții își pot schimba între ei task-uri. De exemplu, dacă niște poștași ar avea mai multe colete de livrat, un poștaș ar prefera să livreze cât mai multe colete în aceeași zonă. Dacă agenții își schimbă câte un task la un moment dat, procesul este echivalent cu o optimizare de tip hill climbing, care poate ajunge în optime locale. De aceea, prin introducerea unor schimburi „monetare”, se transformă un task, inițial reprezentat ca un punct în spațiul utilităților, într-o linie de pantă –1, ceea ce poate introduce noi alocări dominante (Vidal, 2007):

Astfel se poate atinge, de exemplu, soluția utilitaristă. În varianta standard, protocolul rețelelor de contracte are următorii pași:

192

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com





Managerul (inițiatorul): o Anunță că are un task care trebuie îndeplinit; o Primește și evaluează oferte de la contractanții potențiali; o Acordă contractul contractantului potrivit; o Primește și sintetizează rezultatele; Contractantul (participantul): o Primește anunțurile de task-uri; o Își evaluează capacitatea de a le îndeplini; o Răspunde, adică acceptă sau refuză task-ul; o Execută task-ul dacă oferta sa este acceptată de către manager; o Raportează rezultatele.

Un manager poate să nu primească oferte pentru un anumit task pentru o serie de motive:   

Toți contractanții potențiali sunt ocupați cu alte task-uri; Un contractant potențial este neocupat, dar ordonează task-ul propus sub alte task-uri considerate; Niciun contractant, deși neocupat, nu este capabil să lucreze la task-ul propus.

Un participant p acceptă un contract Tcontract dacă primește pentru execuția lui mai mult decât costul său marginal de executare a task-ului:

MC add T contract|T p   c p T contract  Tp   c p Tp  , unde Tp sunt task-urile pe care p le are deja, iar cp(T) reprezintă costul lui p pentru mulțimea de task-uri T. În mod similar, un manager m alocă un task Tcontract din mulțimea sa de task-uri Tm unui participant dacă îi plătește acestuia mai puțin decât suma pe care o economisește el însuși pentru că nu execută Tcontract : MC remove T contract | Tm   cm Tm   cm Tm  T contract .

193

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Prețul de contractare poate fi la jumătate între cele două costuri marginale. Există mai multe tipuri de contracte:    

contracte originare (O): schimbul unui task individual; contracte de tip grup sau cluster (C): o mulțime de task-uri este contractată de un agent altui agent; contracte de interschimbare sau swap (S): o pereche de agenți schimbă o pereche de task-uri; contracte multi-agent (M): mai mult de doi agenți schimbă task-uri atomice.

Un contract OCSM este un contract care permite orice tip de contract din cele menționate mai sus. S-a demonstrat că aceste contracte sunt necesare și suficiente pentru obținerea unei alocări optime global. Dacă un protocol de contractare permite contracte OCSM, orice secvență de contracte individual raționale găsește alocarea optimă globală de task-uri într-un număr finit de pași, fără backtracking. Există mai multe variante de extindere a protocolului rețelelor de contracte standard: 



Protocolul rețelelor de contracte concurent (concurrent contract net protocol): Pentru că mediul este foarte dinamic, cu mulți manageri și mulți participanți, iar un participant poate fi manager la rândul său, există riscul ca după acceptarea unui contract, managerul sau participantul să primească o ofertă mai bună de la un alt agent. Pentru a scădea acest risc, se introduce o fază de pre-ofertare (prebidding) și pre-atribuire (pre-assignment) înainte de fazele finale de ofertare și atribuire. În aceste faze, care pot dura mult timp, agenții propun oferte temporare, iar managerii le acceptă sau le resping tot temporar; Contracte de angajamente nivelate (leveled commitment contracts): Se introduce o penalizare dacă agenții nu își respectă angajamentele luate. După ce a acceptat un contract, dacă un agent primește o ofertă mai bună, poate renunța la primul contract, dar trebuie să plătească o penalizare celuilalt agent care este parte din contract. 194

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

36. Metode de coordonare O taxonomie a metodelor prin care agenții își pot coordona comportamentele și activitățile este prezentată în figura următoare.

Planificarea globală parțială are trei faze:   

Fiecare agent decide care îi sunt scopurile și generează planuri pe termen scurt pentru a le atinge; Agenții schimbă informații pentru a determina unde interacționează planurile și scopurile; Agenții își modifică planurile locale pentru a-și coordona mai bine activitățile.

Un model de reprezentare a mecanismelor de coordonare este Generalized Partial Global Planning (PGPG), implementat de sistemul TÆMS. Un exemplu este figura următoare, în care se poate vedea o ierarhie de scopuri care pot fi atinse prin realizarea unor subscopuri (fig. Vidal, 2007).

195

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Unele scopuri sunt necesare pentru realizarea altora, sau le pot facilita. Realizarea scopurilor presupune și maximizarea sumei utilităților agenților, prin urmare facilitarea are drept consecință creșterea acestei utilități. Realizarea fiecărui scop este cuantificată de trei parametri: calitate, cost și durată. Aceștia au valori probabilistice, de exemplu, pentru scopul G1 există o probabilitate de 20% să aibă calitatea 0 (să nu fie îndeplinit) și o probabilitate de 80% să aibă calitatea 8. Pentru scopul G31, costul va fi de 10 unități cu probabilitatea de 100%. Fiecare agent are doar o perspectivă locală asupra task-urilor care trebuie executate. Prin interacțiuni directe, succesive, cu ceilalți agenți, un agent află structura de task-uri ale acestora și își poate modifica propria planificare pentru a le facilita execuția și prin urmare, pentru a crește utilitatea întregului sistem. Coordonarea prin intenții comune se bazează pe mecanismele echipelor umane. Este descris în modelul Cooperative Distributed Problem Solving (CDPS), care are patru faze: 

Recunoașterea: Un agent are un scop și își dă seama că l-ar putea realiza doar prin cooperare cu alt agent, sau că prin cooperare l-ar realiza mai eficient; 196

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com







Formarea echipei: Agentul solicită sprijin și dacă are succes, rezultatul este că un grup de alți agenți declară că vor să participe la acțiunea comună. Echipa stabilește scopurile care trebuie atinse; Formarea planului: Se creează planul comun de urmat, de exemplu, prin negociere, în care se stabilesc mijloacele: succesiunea de acțiuni din plan pentru fiecare agent din echipă; Acțiunea echipei: Planul agreat este executat de către agenți.

Coordonarea prin convenții sociale presupune o abordare bazată pe teoria jocurilor, în care un joc în formă normală are mai multe echilibre Nash, iar agenții trebuie să se coordoneze pentru a alege unul din aceste echilibre. Se calculează toate echilibrele jocului, se ordonează aceste echilibre pe baza unei scheme unice de ordonare și se selectează primul echilibru din lista ordonată. Într-o organizație de agenți, agenții îndeplinesc roluri, iar acestea impun constrângeri asupra acțiunilor care pot fi executate de agenți, precum și specializarea agenților pe anumite tipuri de task-uri. Prespunând că agenții pot comunica, atribuirea rolurilor se poate face prin broadcast: fiecare agent își calculează potențialul pentru toate rolurile și trimite rezultatele celorlalți agenți, apoi fiecare agent identifică agentul cel mai potrivit pentru un anumit rol.

197

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

37. Învățarea în sisteme multi-agent 1. Jocuri repetate Considerând jocurile strategice simple studiate de teoria jocurilor (precum dilema deținutului), dacă jocurile sunt repetate, strategiile de echilibru se pot schimba. Pentru dilema deținutului, dacă numărul de repetări este finit, prin inducție inversă se constată că strategia de echilibru este cea egoistă, Mărturisește, ca la jocul simplu. Dacă agenții nu știu când se va termina jocul repetat (de exemplu, există la fiecare rundă o probabilitate mică ca jocul să se termine), strategia dominantă poate fi cooperarea (Neagă). Există mai multe strategii posibile, una de succes fiind Tit-for-Tat (ochi pentru ochi): un agent cooperează în prima rundă și apoi imită acțiunea anterioară a oponentului.

2. Jocul fictiv (fictitious play) Agentul care folosește această metodă presupune că oponenții folosesc strategii fixe (adică au probabilități fixe pentru alegerea acțiunilor) și încearcă să le estimeze statistic, din interacțiuni repetate. Agentul numără de câte ori fiecare oponent a ales o anumită strategie. Apoi alege ca acțiune proprie cel mai bun răspuns la o acțiune determinată de distribuția de probabilitate estimată a oponentului. Proprietăți:  



Jocul fictiv converge la echilibrul Nash: dacă jocul fictiv converge la o strategie pură, aceasta este echilibru Nash; Echilibrul Nash este un atractor al jocului fictiv: dacă un echilibru Nash strict este jucat la momentul t, el va fi jucat și la toate momentele de timp ulterioare lui t; Uneori, jocul fictiv intră in cicluri infinite și nu converge deloc.

198

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

3. Dinamica replicatorilor (replicator dynamics) Modelul prespune o populație de agenți care interacționează în mod repetat. Fiecare agent are o strategie fixă. Agenții formează perechi aleatorii și joacă jocul strategic considerat cu acțiunile date de strategia fiecăruia. Numărul agenților care aleg o anumită strategie crește proporțional cu câștigul asociat acelei strategii în întreaga populație. Utilitatea obținută contează pentru ajustarea numărului de agenți care au o anumită strategie. Dacă o strategie aduce utilități pozitive, numărul de agenți care au strategia respectivă crește în următoarea iterație. Dacă o strategie aduce utilități negative, numărul de agenți care au strategia respectivă scade. Prin urmare, dimensiunea populației fluctuează continuu. Fracțiunile de agenți care au anumite strategii pot fi considerate drept un echilibru Nash mixt al jocului. Dinamica replicatorilor este un model determinist. O stare stabilă (steady state) este o stare (proporție de agenți sau probabilități în echilibrul Nash mixt) care, după o mică perturbație, este readusă la aceeași stare de către dinamica sistemului. O stare stabilă în dinamica replicatorilor este un echilibru Nash. De asemenea, echilibrul Nash este o stare stabilă pentru dinamica replicatorilor. Există și aici cazuri (jocuri) pentru care metoda intră în cicluri infinite și nu converge la un punct fix.

4. Niveluri de modelare ale agenților Un agent de nivel 0 nu modelează alți agenți din mediu. Învață pe baza utilităților sau recompenselor primite direct pentru acțiunile sale. Dinamica replicatorilor are agenți de nivel 0. Un agent de nivel 1 este conștient de existența altor agenți în mediu, ale căror acțiuni îi influențează utilitățile. Își dă seama că utilitatea primită de el este efectul unei combinații de acțiuni (ale lui și ale unui oponent). Observă oponenții, le construiește modele (probabilistice) și apoi folosește aceste modele pentru a le prezice acțiunile și pentru a-și determina la rândul său cel mai bun răspuns. Jocul fictiv are agenți de nivel 1. 199

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Un agent de nivel 2 consideră ca toți ceilalți agenți sunt de nivel 1 și calculează modele ale modelelor acestora. Un agent de nivel n consideră că toți ceilalți agenți sunt de nivel n – 1 și îi modelează în consecință. Costul computațional pentru creșterea nivelului cu unu este exponențial. Totuși, diferența de utilitate obținută prin incrementarea nivelului scade când nivelul este deja destul de mare.

200

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

Referințe 1.

Ackley, D. H., Hinton, G. E., Sejnowski, T. J. (1985). A Learning Algorithm for Boltzmann Machines, Cognitive Science, vol. 9, no. 1, pp. 147-169.

2.

Baeck, T., Fogel, D.B., Michalewicz, Z., eds. (1997). Handbook of Evolutionary Computation, Institute of Physics Publishing Publishing and Oxford University Press.

3.

Barber, D. (2012). Bayesian Reasoning and Machine Learning, Cambridge University Press.

4.

Bellinger, G., Castro, D., Mills, A. (2004). Data, Information, Knowledge, and Wisdom, http://www.systems-thinking.org/dikw/dikw.htm.

5.

Camastra, F., Vinciarelli, A. (2015). Machine Learning for Audio, Image and Video Analysis, Theory and Applications, Second Edition, Springer.

6.

Cârstoiu, D. I. (1994). Sisteme expert, Ed. All, Bucureşti.

7.

Daumé, H. (2015). A Course in Machine Learning, http://ciml.info/dl/v0_9/cimlv0_9-all.pdf

8.

Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons.

9.

Deb, K., Agrawal, S., Pratap, A., Meyarivan, T. (2000). A Fast Elitist NonDominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II, Proceedings of the Parallel Problem Solving from Nature VI Conference, http://citeseer.ist.psu.edu/ deb00fast.html

10. Deng, L., Yu, D. (2014). Deep Learning: Methods and Applications, Now Publishers. 11. desJardins, M. (2005). Game Playing, http://www.cs.umbc.edu/courses/graduate/ 671/fall05/slides/c7-8_games.ppt 12. Drakos, N., Moore, R. (2001). Conjunctive Normal Form, http://www.mathcs. duq.edu/ simon/Fall04/notes-6-20/node2.html 13. Ester, M., Kriegel, H. P., Sander, J., Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise, Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), AAAI Press, pp. 226-231. 14. Ferber, J. (1999). Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence, Addison-Wesley Professional. 15. Finin, T., Fritzson, R., McKay, D., McEntire, R. (1994). KQML as an Agent Communication Language, Proceedings of the Third International Conference on Information and Knowledge Management, CIKM ’94, pp. 456-463. 16. Finin, T., Labrou, Y., Mayfield, J. (2003). A Brief Introduction to the Knowledge Interchange Format, http://www.cs.umbc.edu/kse/kif/ kif101.shtml.

201

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

17. FIPA, Foundation for Intelligent Physical Agents (2002). Agent Communication Language (ACL), http://www.fipa.org/repository/aclspecs.html. 18. Freund, Y., Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, vol. 55, no. 1, pp. 119-139. 19. Fullér, R. (1995). Neural Fuzzy Systems, Åbo Akademi University, http://users.abo.fi/rfuller/ln1.pdf 20. Goodfellow, I., Bengio, Y., Courville, A. (2016). Deep Learning, MIT Press. 21. Graupe, D. (2016). Deep Learning Neural Networks, Design and Case Studies, World Scientific Publishing. 22. Han, J., Kamber, M., Pei, J. (2011). Data Mining: Concepts and Techniques, 3rd Edition, Morgan Kaufmann. 23. Hanson, S. J., Remmele, W., Rivest, R. L. (1993). Machine Learning: From Theory to Applications, Springer. 24. Hoffmann, J. (2001). FF: The Fast-Forward Planning System, AI Magazine, vol. 22, no. 3, pp. 57-62, http://www.cs.toronto.edu/~sheila/2542/w06/readings/ ffplan01.pdf 25. Hsu, W. H. (2001). Decision Trees, Occam’s Razor, and Overfitting, http://www.kddresearch.org/Courses/Fall-2001/CIS732/Lectures/Lecture-0520010906.pdf 26. Jeffrey-Pennington, R., Manning, C. (2014). Glove: Global Vectors for Word Representation, Conference on Empirical Methods in Natural Language Processing. 27. Kameshwaran, S. (2002). Constraint Satisfaction Problems and Games, http://purana.csa.iisc.ernet.in/~mbk/jammin/Talk4.ppt, 2002 28. Keogh, E., Heuristic Search, http://www.cs.ucr.edu/~eamonn/teaching/ cs170materials/Heuristic%20Search.ppt 29. Klir, G. J., Yuan, B. (1995). Fuzzy Sets and Fuzzy Logic: Theory and Applications, Prentice Hall PTR. 30. Knapp, B. (2004). Fuzzy inference systems, https://www.cs.princeton.edu/courses/ archive/fall07/cos436/HIDDEN/Knapp/fuzzy004.htm. 31. Kohonen, T. (1995). Self-Organizing Maps, Springer Verlag, Berlin. 32. Kononenko, I. (1994). Estimation Attributes: Analysis and Extensions of RELIEF, European Conference on Machine Learning, Catana, Italy, Springer-Verlag. 33. Kubalik, J. (2000). Machine Learning, http://cyber.felk.cvut.cz/gerstner/ HUT2000/ml/ml1.ppt 34. Kurfess, F. J., Artificial Intelligence, http://www.csc.calpoly.edu/~fkurfess/ Courses/CSC-480/F03/Slides/Games.ppt 35. Latombe, J.-C. (2007). Blind (Uninformed) Search, http://ai.stanford.edu/ ~latombe/cs121/2007/slides/C-blind-search.ppt

202

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

36. Latombe, J.-C. (2007). Constraint Satisfaction Problems (CSP), http://ai.stanford.edu/~latombe/cs121/2007/slides/G-const-sat.ppt 37. Latombe, J. C., Getoor, L. (2005). Reinforcement Learning, http://www.cs.umbc.edu/courses/graduate/671/fall05/slides/c28_rl.ppt 38. Leon, F. (2006). Agenți inteligenți cu capacități cognitive, Tehnopress, Iași. 39. Leon, F. (2012). Inteligență artificială: raționament probabilistic, tehnici de clasificare, Tehnopress, Iași. 40. Leon, F. (2014). Inteligență artificială: mașini cu vectori suport, Tehnopress, Iași. 41. Lin, F. O., ed. (2005). Designing Distributed Learning Environments with Intelligent Software Agents, Information Science Publishing. 42. Luger, G. F. (2005). Artificial Intelligence, Structures and Strategies for Complex Problem Solving, The Benjamin/Cummings Publishing Company, Inc., Redwood City, California. 43. Marsland, S. (2015). Machine Learning, An Algorithmic Perspective, Second Edition, CRC Press. 44. Matas, J., Sochman, J. (2017). AdaBoost, http://www.robots.ox.ac.uk/~az/lectures/ cv/adaboost_matas.pdf. 45. MathWorks (2010). Fuzzy Logic Toolbox – Function Reference, http://www.mathworks.co. jp/access/helpdesk/help/toolbox/fuzzy/fp4856.html. 46. Mikolov, T., Chen, K., Corrado, G., Dean, J. (2013). Efficient Estimation of Word Representations in Vector Space, https://arxiv.org/abs/1301.3781 47. Mitchell, T. M. (1997). Machine Learning, McGraw-Hill Science/Engineering/ Math. 48. Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., Riedmiller, M. (2013). Playing Atari with Deep Reinforcement Learning, arXiv preprint arXiv:1312.5602. 49. Mohammed, M., Khan, M. B., Bashier, E. B. M. (2016). Machine Learning, Algorithms and Applications, CRC Press. 50. Morey, E. (2004). Game Theory, http://www.colorado.edu/economics/morey/ 6808/game-lect.pdf 51. Müller, A. C., Guido, S. (2016). Introduction to Machine Learning with Python: A Guide for Data Scientists, O'Reilly Media. 52. Murphy, K. P. (2012). Machine Learning, A Probabilistic Perspective, MIT Press. 53. Narayanan, S. (2007). A* Search, http://inst.eecs.berkeley.edu/~cs188/sp07/slides/ SP07%20cs188%20lecture%204%20--%20a-star%20search.ppt 54. Negnevitsky, M. (2004). Artificial Intelligence: A Guide to Intelligent Systems, 2nd Edition, Addison Wesley. 55. Ng, A. (2010). Autoencoders, http://ufldl.stanford.edu/tutorial/unsupervised/ Autoencoders/. 56. Nilsson, N. J. (2001). Introduction to Machine Learning, http://robotics.stanford. edu/people/nilsson/mlbook.html.

203

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

57. Padgham, L., Winikoff, M. (2004). Developing Intelligent Agent Systems: A Practical Guide, Wiley Series in Agent Technology, Wiley. 58. Peng, Y., Game Playing: Adversarial Search, http://www.csee.umbc.edu/~ypeng/ AI/471/lecture-notes/Ch06.ppt 59. Porter, J. (2016). Deep Learning: Fundamentals, Methods and Applications, Nova Science. 60. Portnoy, M. (2006). Intro to Game Theory, http://www.cse.yorku.ca/~lan/ seminars/intro_to_game_theory_2006.ppt 61. Priddy, K. L., Keller, P. E. (2005). Artificial Neural Networks: An Introduction, SPIE Publications. 62. Principe , J. (2010). Neural Networks for Signal Processing. Hebbian learning and PCA, http://www.cnel.ufl.edu/courses/EEL6814/chapter6.pdf 63. Rasmusen, E. (2006). The Welfare Game, http://rasmusen.org/g601/overheads/ gi03- overheads.pdf 64. Russell, S. J., Norvig, P. (1998). Planning, AIMA Slides, https://people.eecs. berkeley.edu/~russell/slides/chapter11.pdf. 65. Russell, S. J., Norvig, P. (2002). Artificial Intelligence: A Modern Approach, Prentice Hall, 2nd Edition. 66. Schank, R. C., Abelson, R. (1977). Scripts, Plans, Goals, and Understanding, Hillsdale, NJ, Earlbaum Assoc. 67. Setzer, V. W. (2001). Data, Information, Knowledge and Competency, http://www.ime.usp. br/~vwsetzer/data-info.html. 68. Shiffman, M. (2016). Under the Hood of the Variational Autoencoder, https://blog. fastforwardlabs.com/2016/08/22/under-the-hood-of-the-variationalautoencoder-in.html. 69. Shkodyrev, V. P. (2009). Perceptron – Simplest Neural Network, www.powershow.com/view/11df69-OWFlO/Lecture_6_Perceptron_Simplest_ Neural_Network. 70. Shoham, Y., Leyton-Brown, K. (2008). Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations, Cambridge University Press. 71. Silver, D., Schrittwieser, J., Simonyan, K. et al. (2017). Mastering the game of Go without human knowledge, Nature 550, 354–359, DOI: 10.1038/nature24270. 72. Singh, M. (2017). Word embedding, https://medium.com/data-science-groupiitr/word-embedding-2d05d270b285. 73. Smith, J. R. (2001). Conjunctive normal form, http://vorpal.math.drexel.edu/ course/founds/proving/node1.html 74. Stahl, S. (1999). A Gentle Introduction to Game Theory, American Mathematical Society. 75. Straffin, P. (1993). Game Theory And Strategy, American Mathematical Society. 76. Sutton, R. S., Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd Edition, MIT Press, Cambridge, MA.

204

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com

77. Tan, P.-N., Steinbach, M., Kumar, V. (2006). Introduction to Data Mining, Addison-Wesley. 78. Van Dyke Parunak, H. (1997). "Go to the ant": Engineering principles from natural multi-agent systems, Annals of Operations Research, vol. 75, pp 69-101. 79. Vidal, J. M. (2007). Fundamentals of Multiagent Systems, http://jmvidal.cse.sc. edu/papers/mas.pdf 80. Walker, E., Heuristic, http://cs.hiram.edu/~walkerel/cs386/Heuristic.ppt. 81. Wang, X. (2016). Deep Learning in Object Recognition, Detection and Segmentation, Now Publishers. 82. Weiss, G., ed. (2000). Multiagent Systems - A Modern Approach to Distributed Artificial Intelligence, The MIT Press, Cambridge, Massachusetts. 83. Williams, B.C. (2012). Planning as Heuristic Forward Search, http://www.ai.mit. edu/courses/16.412J/lectures/L6%20Planning%20as%20Heuristic%20Forward %20Search_9.30.ppt 84. Witten, I. H., Frank, E. (2000). Data Mining: Practical machine learning tools with Java implementations, Morgan Kaufmann, San Francisco. 85. Wooldridge, M. (2002). An Introduction to MultiAgent Systems, John Wiley & Sons. 86. Zaharie, D. (2007). A Comparative Analysis of Crossover Variants in Differential Evolution, Proceedings of the International Multiconference on Computer Science and Information Technology, pp. 171-181, http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.215.7335&rep=rep1&type=pdf.

205

Florin Leon (2020). Sinteze de inteligenta artificiala, Tehnopress, Iasi, ISBN 978-606-687-429-8 http://florinleon.byethost24.com