inteligenta artificiala: retele bayesiene. teoria evidentelor. teoria jocurilor

105
Inteligenţă artificială 9. Raţionament probabilistic. Teoria jocurilor Florin Leon Universitatea Tehnică „Gheorghe Asachi” din Iaşi Facultatea de Automatică şi Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Upload: enrollinfo

Post on 26-Jun-2015

440 views

Category:

Documents


15 download

DESCRIPTION

Inteligenta artificiala: Retele bayesiene. Teoria Dempster Shafer. Teoria jocurilor

TRANSCRIPT

Page 1: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Inteligenţă artificială

9. Raţionament probabilistic. Teoria jocurilor Florin Leon

Universitatea Tehnică „Gheorghe Asachi” din Iaşi Facultatea de Automatică şi Calculatoare

http://florinleon.byethost24.com/curs_ia.htm

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 2: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

2

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 3: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

3

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 4: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

4

Probabilităţi

P(A) – fracţiunea de lumi posibile în care A este adevărată

Interpretarea frecventistă (număr de experimente)

Interpretarea fizică (proprietăţi ale obiectelor)

Interpretarea subiectivistă (caracterizarea convingerilor)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 5: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

5

Paradoxuri

Problema “Monty Hall”

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 6: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

6

Paradoxuri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 7: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

7

Eroarea jucătorului de ruletă

Dacă a ieşit roşu, data următoare sunt mai multe şanse să iasă negru

1913, Monte Carlo – negrul a ieşit de 26 de ori la rând

Paradoxuri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 8: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

8

Eroarea procurorului Grupa de sânge găsită la faţa locului este o grupă rară, AB cu Rh

negativ, care are 1% frecvenţă în populaţie

S-au mai găsit urme de păr blond, persoanele blonde constituind tot 1% din populaţie

Suspectul are grupa de sânge respectivă şi este blond, prezenţa împreună a acestor trăsături având împreună probabilitatea de 0,01% ⇒ vinovat cu o probabilitate de 99,99%

Oraşul în care s-a petrecut crima are o populaţie de 100.000 de locuitori, deci alţi 10 oameni au aceleaşi trăsături ⇒ vinovat cu o probabilitate de 10%

2 camere video identifică suspectul cu o probabilitate de 70%, deci suspectul este nevinovat cu o probabilitate de 0,9 ∙ 0,3 ∙ 0,3 ⇒ vinovat cu o probabilitate de 91,9%

Paradoxuri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 9: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

9

Probabilităţi condiţionate

P(A|B) este fracţiunea de lumi posibile în care B este adevărată şi atunci şi A este adevărată

Probabilitatea lui A, dat fiind B

D = durere de cap, P(D) = 1/10

G = gripă, P(G) = 1/40

P(D|G) = 1/2

Dacă cineva are gripă, probabilitatea de a avea şi dureri de cap este de 50%

P(D|G) = P(D⋂G) / P(G)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 10: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

10

Teorema lui Bayes

P(A|B) = P(A⋂B) / P(B)

P(A⋂B) = P(A|B) · P(B)

P(A⋂B) = P(B|A) · P(A)

⇒ P(B|A) = P(A|B) · P(B) / P(A)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 11: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

11

Teorema lui Bayes

P(B|A) = P(A|B) · P(B) / P(A)

Thomas Bayes (1763). An essay towards solving a problem in the doctrine of chances. Philosophical Transactions of the Royal Society of London, vol. 53, pp. 370-418

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 12: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

12

Diagnoză

Probabilităţi cunoscute

Meningită: P(M) = 0,002%

Gât înţepenit: P(G) = 5%

Meningita cauzează gât înţepenit în jumătate din cazuri: P(G|M) = 50%

Dacă un pacient are gâtul înţepenit, care este probabilitatea să aibă meningită?

P(M|G) = P(G|M) · P(M) / P(G) = 0,02%

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 13: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

13

Diagnoză

Greşeală întâlnită uneori: P(A|B) = P(B|A)

Diagnostice pentru boli rare

Trebuie avute în vedere probabilităţile testului de a returna rezultate fals pozitive

B – boală T – test

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 14: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

14

Independenţă şi independenţă condiţionată

Exemplul 1. Ion şi Maria dau cu banul. Fiecare are un ban diferit

Evenimente independente

Rezultatul unui experiment nu influenţează rezultatul celuilalt experiment

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 15: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

15

Independenţă şi independenţă condiţionată

Exemplul 2. Ion şi Maria dau cu acelaşi ban

Dacă banul nu este corect, evenimentul A (Ion) poate aduce informaţii asupra evenimentului B (Maria)

Evenimentele nu sunt independente

Rezultatul unui experiment poate influenţa cunoştinţele despre rezultatul celuilalt

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 16: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Independenţă şi independenţă condiţionată

Exemplul 2 (cont.). Fie C variabila „banul este influenţat în favoarea pajurei”

Dacă ştim C, experimentul A nu mai aduce informaţii noi asupra lui B

P(B|A,C) = P(B|C)

A şi B sunt independente condiţional dat fiind C

Situaţia „cauză comună”

16 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 17: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Independenţă şi independenţă condiţionată

Exemplul 3. Ion şi Maria locuiesc în zone diferite ale oraşului şi vin la serviciu cu tramvaiul, respectiv maşina

„Ion a întârziat” şi „Maria a întârziat” pot fi considerate independente

Dacă vatmanii sunt în grevă, atunci şi traficul rutier creşte

Evenimentele devin condiţional independente

Sunt multe situaţii din viaţa reală în care evenimente considerate independente sunt de fapt doar condiţional independente

17 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 18: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Independenţă şi independenţă condiţionată

Exemplul 4. Atât răceala cât şi alergia îl pot determina pe Ion să strănute

Dacă nu ştim că Ion a strănutat, răceala şi alergia sunt independente

Dacă ştim că Ion a strănutat, răceala şi alergia nu mai sunt independente

Dacă mai ştim că Ion este răcit, probabil că răceala determină strănutul iar probabilitatea alergiei scade

Situaţia „revocare prin explicare” (engl. “explaining away”)

18 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 19: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

19

Reprezentarea cunoştinţelor incerte

O situaţie cu 5 variabile (exemplul următor)

Specifică o distribuţie comună de probabilitate cu 25 – 1 = 31 parametri

Fezabil

Un sistem expert cu 37 de variabile pentru monitorizarea pacienţilor de la terapie intensivă

237 – 1 ≈ 1011 parametri

Nefezabil

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 20: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

20

Reţea bayesiană

S-a instalat un nou sistem de alarmă

Sună în cazul unei spargeri dar şi în cazul unui cutremur

Vecinii John şi Mary îl sună pe proprietar la serviciu dacă aud alarma

10 parametri independenţi faţă de 31

Reţea bayesiană (J. Pearl, 1985)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 21: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

21

Comparaţie

Sistem expert pentru monitorizarea pacienţilor de la terapie intensivă

37 variabile

509 parametri în loc de 1011

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 22: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Reprezentarea distribuţiei comune de probabilitate

Este adevărată doar dacă fiecare nod este independent condiţional de predecesorii din şirul ordonat al nodurilor, daţi fiind părinţii nodului

“chain rule” (regula de înmulţire a probabilităţilor)

Dacă efectele sunt considerate independente “Naïve Bayes”

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 23: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

23

Interogări simple

Care este probabilitatea ca alarma să se declanşeze fără să fi fost nicio spargere şi niciun cutremur iar John şi Mary să sune?

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 24: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

24

Validitatea unei reţele bayesiene

O reţea bayesiană este un graf orientat aciclic

Arcele pot forma bucle, dar nu pot forma cicluri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 25: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Algoritmul Bayes-Ball

O modalitate simplă 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ţional)

25 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 26: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Reguli de trimitere a mingii

26 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 27: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Exemple

27

noduri evidenţă (gri)

noduri neobservate (albe)

o cale activă nicio cale activă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 28: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

28

Ordonarea nodurilor

Reţelele din dreapta sunt create prin introducerea succesivă a noilor noduri, de sus în jos Ambele sunt echivalente cu distribuţia comună de probabilitate Nu sunt optime din punct de vedere al compactităţii Necesită mai mulţi parametri Reţeaua (b) necesită 31 de parametri, la fel ca distribuţia comună

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 29: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

29

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 30: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

30

Inferenţa probabilităţilor marginale

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 31: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

31

Nodul LA

P(LA) =

P(LA|LF) · P(LF) + P(LA|~LF) · P(~LF) =

0.6 · 0.15 + 0.05 · (1 – 0.15) = 0.133

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 32: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

32

Nodul CL

P(CL) = P(CL|LF,PD) · P(LF) · P(PD) + P(CL|LF,~PD) · P(LF) · P(~PD) + P(CL|~LF,PD) · P(~LF) · P(PD) + P(CL|~LF,~PD) · P(~LF) · P(~PD) = 0.99 · 0.15 · 0.01 + 0.9 · 0.15 · (1 – 0.01) + 0.97 · (1 – 0.15) ·

0.01 + 0.3 · (1 – 0.15) · (1 – 0.01) = 0.395

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 33: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

33

Probabilităţile nodurilor

P(L) = P(L|CL) · P(CL) + P(L|~CL) · P(~CL) = 0.7 · 0.395 + 0.01 · (1 – 0.395) = 0.283

P(LF) = 0.15

P(PD) = 0.01

P(LA) = 0.133

P(CL) = 0.395

P(L) = 0.283

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 34: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

34

Inferenţa prin enumerare

Interogare: Care este probabilitatea spargerii, dacă atât John cât şi Mary au dat telefon?

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 35: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

35

Rezolvare

Evidenţa observată

Variabila interogată

Variabilele neobservate

Coeficient de normalizare

Sumă după toate valorile posibile ale lui y, de exemplu afirmat şi negat

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 36: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

36

Rezolvare

acelaşi tip de calcule pentru negaţie

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 37: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

37

Observaţie

Toate variabilele care nu sunt predecesori ai unei variabile de interogare sau de evidenţă sunt irelevante

Pot fi ignorate în calcule

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 38: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

38

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 39: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

39

Teoria evidenţelor Dempster-Shafer

Probabilităţile evaluează o situaţie folosind un singur număr

Teoria Dempster-Shafer acordă propoziţiilor intervale pentru

gradele de încredere [bel, pl]

bel = convingerea (engl. “belief”)

pl = plauzibilitatea: pl(A) = 1 – bel(A)

Se calculează independent A şi A

Dacă nu avem informaţii nici despre A nici despre A, intervalul

de încredere este [0, 1]

În loc de probabilitatea 0.5

Pe măsură ce se acumulează informaţii, intervalul se micşorează

bel(A) ≤ P(A) ≤ pl(A)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 40: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

40

Exemplul 1: aruncarea unui ban

Dacă nu avem nicio informaţie despre ban, dacă este corect sau nu, atunci:

bel(cap) =0 şi bel(cap) = 0

pl(cap) = 1 – bel(cap) = 1

Intervalul de încredere pentru cap este [0, 1]

Dacă un expert este 90% sigur că banul este corect, adică P(cap) = 0.5, atunci:

bel(cap) = 0.9 · 0.5 = 0.45

bel(cap) = 0.9 · 0.5 = 0.45

pl(cap) = 1 – bel(cap) = 0.55

Intervalul de încredere pentru cap este [0.45, 0.55]

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 41: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

41

Exemplul 2

Sue este de încredere cu probabilitatea 0.9

P(M) = 0.9, P(M) = 0.1

Bill este de încredere cu probabilitatea 0.8

P(B) = 0.8, P(B) = 0.2

Cazul 1. Sue şi Bill spun amândoi că lui George i-a fost furată maşina

Probabilitatea ca niciunul să nu fie de încredere este 0.02

Probabilitatea ca măcar unul din ei să fie de încredere este 1 – 0.02 = 0.98

Intervalul de încredere este [0.98, 1]

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 42: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

42

Exemplul 2

Cazul 2. Sue spune că i-a fost furată maşina, Bill spune că nu Nu pot fi simultan ambii de încredere (mărturiile se contrazic)

Doar Sue este de încredere (maşina a fost furată) 0.9 x (1 – 0.8) = 0.18

Doar Bill este de încredere (maşina nu a fost furată) 0.8 x (1 – 0.9) = 0.08

Niciunul nu este de încredere (nu ştim nimic precis) (1 – 0.8) x (1 – 0.9) = 0.02

Toate probabilităţile nenule (pentru normalizarela 1) 0.18 + 0.08 + 0.02 = 0.28

Convingerea că maşina a fost furată 0.18 / 0.28 = 0.64

Convingerea că maşina nu a fost furată 0.08 / 0.28 = 0.29

Intervalul de încredere că maşina a fost furată [0.64, 1 – 0.29] = [0.64, 0.71]

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 43: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

43

Formalizare

H – universul ipotezelor mutual exclusive (se mai notează cu Θ şi se mai numeşte cadru de discernământ)

m – o funcţie numită BBA (engl. “Basic Belief Assignement”, atribuire de convingeri de bază) sau funcţie de masă m : (H) → [0,1]

(H) = mulţimea părţilor lui H

m() = 0

∑A(H) m(A) = 1

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 44: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

44

Combinarea evidenţelor

Teoria Dempster-Shafer ne permite să combinăm convingerile m care apar din surse multiple de evidenţe

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 45: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Exemplul 1

Două site-uri de ştiri relatează despre o demonstraţie

Primul site are nivelul de încredere de 80% iar al doilea are nivelul de încredere de 60%

Ambele afirmă că demonstraţia a fost una mare, cu peste 10000 de participanţi

45 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 46: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Rezolvare

46

nu există evidenţe împotriva faptului că demonstraţia a fost mare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 47: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Exemplul 2

Primul site afirmă că demonstraţia a fost mare iar al doilea afirmă contrariul

Ar fi incorect să considerăm m2({Mare}) = 0,4, deoarece al doilea site a spus doar că demonstraţia a fost mică, nu a spus nimic despre o demonstraţie mare

Valoarea asociată mulţimii vide este 0,48 şi deci numitorul fracţiei va fi 1 – 0,48 = 0,52

47 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 48: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Rezolvare

48 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 49: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

49

Exemplul anterior

combinarea evidenţelor într-o nouă BBA

incertitudinea rămasă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 50: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

50

Exemplul anterior

Singurele perechi care se intersectează în mulţimea vidă sunt:

m1({CarMissing}) = 0.9 şi m2({CarThere}) = 0.8

produsul: 0.72

numitorul: 1 – 0.72 = 0.28

Aceleaşi valori ca înainte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 51: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

51

Alt exemplu

Un pacient poate avea răceală (Cold), gripă (Flu), Meningită sau Nimic (e sănătos)

Mulţimea de ipoteze H = {C,F,M,N}

Din studii anterioare: Febra susţine ipoteza {C,F} la nivelul 0.5 şi

{M} la nivelul 0.2

Greţurile susţin ipoteza {C,F,N} la nivelul 0.7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 52: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

52

Combinarea evidenţelor

Singura combinaţie care produce mulţimea vidă are produsul 0.14, deci numitorul va fi 1 – 0.14 = 0.86

Avem un pacient cu febră şi greţuri (m1 şi m2).

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 53: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

53

Noua BBA

Posibilitatea de răceală sau gripă: [0.581, 0.93]

Posibilitatea de meningită: [0.07, 0.175]

0.825 = 0.581 + 0.244 suma tuturor submulţimilor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 54: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

54

Altă evidenţă

Dacă se face un test de laborator şi acesta iese pozitiv, indicând ipoteza {M} la nivelul 0.8, cum se schimbă convingerile?

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 55: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

55

Discuţie

O convingere puternică atribuită mulţimii vide indică evidenţe conflictuale în mulţimea de convingeri

Când avem mulţimi mari de ipoteze şi mulţimi complexe de evidenţe, calculele devin foarte laborioase

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 56: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Evidenţe conflictuale

Exemplu de rezultat neplauzibil (L. Zadeh):

m1{(A)} = 0.99, m1({Z}) = 0.01

m2{(B)} = 0.99, m2({Z}) = 0.01

⋂ ⨉

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 57: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Aplicaţii din viaţa reală

Sisteme expert

Sisteme de diagnoză

Combinarea informaţiilor provenite de la mai mulţi senzori (engl. “sensor fusion”)

57 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 58: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

58

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 59: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

59

Teoria jocurilor

Studiază interacţiunile strategice între jucători raţionali care aleg diferite acţiuni pentru a-şi maximiza profitul

Mai formal, reprezintă studiul modelelor matematice de conflict şi cooperare între decidenţi inteligenţi şi raţionali

Jocurile din cursul 3 rezolvabile cu algoritmul minimax sunt un caz particular: jocuri secvenţiale

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 60: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

60

Aplicaţii

Oriunde există interacţiuni strategice între jucători raţionali

Economie

Strategiile nucleare ale războiului rece

Psihologie

Sociologie

Ştiinţa calculatoarelor (reţele etc.)

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 61: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

61

Caracteristicile unui joc

Jocurile studiate în teoria jocurilor au următoarele elemente:

Doi sau mai mulţi jucători

Alegerea unei acţiuni implică o strategie

Unul sau mai multe rezultate

Rezultatul depinde de strategiile alese

Jucătorii sunt raţionali

Încearcă să-şi maximizeze profitul indiferent de acţiunile celorlalţi jucători

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 62: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

62

Dilema inculpaţilor

engl. “prisoner’s dilemma” Jucători

2 inculpaţi

Acţiuni Inculpatul 1: Mărturiseşte, Neagă Inculpatul 2: Mărturiseşte, Neagă

Strategii Inculpaţii îşi aleg acţiunile simultan,

fără a cunoaşte acţiunea celuilalt

Rezultate Numărul de ani de închisoare

Profitul Mai puţini ani profit mai mare

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 63: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

63

Reprezentarea în forma normală (strategică)

O matrice care conţine jucătorii, strategiile şi profiturile

Se presupune că jucătorii acţionează simultan

Pentru dilema inculpaţilor:

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 64: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

64

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 65: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

65

Echilibrul Nash

Echilibru Nash pentru o strategie pură

),(),( ***

iiiiii ssussu

Profitul (utilitatea) jucătorului i

Strategia din echilibrul Nash

Strategia jucătorului i

Strategiile celorlalţi

jucători cu excepţia lui i

Deterministă, care nu implică

probabilităţi

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 66: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

66

Echilibrul Nash

Echilibrul Nash pentru o strategie pură

Echilibrul Nash este strict dacă:

Stările din care niciun jucător nu-şi poate mări profitul prin schimbarea unilaterală a strategiei

),(),( ***

iiiiii ssussu

),(),( ***

iiiiii ssussu

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 67: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Calculul echilibrelor Nash pure

Se evidenţiază maximele pe linii pentru primul jucător cu {

Se evidenţiază maximele pe coloane pentru al doilea jucător cu }

Stările încadrate de { } sunt echilibre Nash pure

67 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 68: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

68

Exemple

Dilema inculpaţilor

Bătălia sexelor

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 69: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

69

Tragedia păşunii comunale

engl. “the tragedy of the commons”

Păşunea este folosită în comun de 6 ţărani, fiecare cu câte o vacă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 70: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

70

Tragedia păşunii comunale

Fiecare vacă dă 20 de litri de lapte pe zi

Capacitatea păşunii este de 8 vaci

Pentru fiecare vacă peste 8, producţia de lapte scade cu 2 litri

Există mai puţină iarbă de păscut pentru fiecare vacă, deci şi mai puţin lapte

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 71: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

71

20 litri 20 litri

20 litri

20 litri 20 litri

20 litri

Producţia zilnică totală de lapte: 120 litri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 72: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

72

Ţăranii vor să-şi maximizeze producţia de lapte

20 litri

20 litri

20 litri 20 litri

20 litri

Producţia zilnică totală de lapte: 140 litri (7 vaci)

40 litri

“O să cumpăr încă o vacă”

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 73: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

73

Acum s-a atins capacitatea maximă a păşunii. Dar ţăranii nu se opresc.

20 litri

20 litri 20 litri

20 litri

Producţia zilnică totală de lapte: 160 litri (8 vaci)

40 litri 40 litri

“Atunci şi eu o să-mi cumpăr”

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 74: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

74

18 litri 18 litri

18 litri

Producţia zilnică totală de lapte: 162 litri (9 vaci)

36 litri 36 litri

“O să-mi iau încă una”

36 litri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 75: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

75

32 litri 16 litri

16 litri

Producţia zilnică totală de lapte: 160 litri (10 vaci)

32 litri 32 litri

32 litri

“Vaca produc e acum mai puţin, dar 2 vaci o să rezolve problema”

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 76: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

76

28 litri

14 litri

Producţia zilnică totală de lapte: 154 litri (11 vaci)

28 litri 28 litri

28 litri

“O să-mi cumpăr încă una” 28 litri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 77: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

77

24 litri

Producţia zilnică totală de lapte: 144 litri (12 vaci)

24 litri 24 litri

24 litri

24 litri

“Toată lumea îşi cumpără încă o vacă, deci şi eu”

24 litri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 78: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

78

20 litri

Producţia zilnică totală de lapte: 130 litri (10 vaci)

30 litri 20 litri

“Încă pot creşte producţia dacă iau şi a treia vacă”

20 litri

20 litri

20 litri

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 79: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

79

-100

-50

0

50

100

150

200

0 2 4 6 8 10 12 14 16 18 20

Total Cow s

Mil

k P

rod

uc

tio

n (

in l

ite

rs)

Producţia maximă de lapte

pentru păşune: 162 litri/zi

Ţăranii vor continua să

cumpere vaci până când sunt

15 vaci în total pe păşune

Nivelul curent

Câştigul sau pierderea

pentru un ţăran la

cumpărarea unei noi vaci

Producţia totală

pentru toate vacile

Numărul total de vaci

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 80: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

80

-100

-50

0

50

100

150

200

0 2 4 6 8 10 12 14 16 18 20

Total Cow s

Mil

k P

rod

uc

tio

n (

in l

ite

rs)

Producţia maximă de lapte

pentru păşune: 162 litri/zi

Nivelul curent

Producţia totală

pentru toate vacile

Optimul

social Rezultatul

comportamentului

individual

diferenţa

Numărul total de vaci

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 81: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

81

Soluţii?

Acord de cooperare între ţărani

Împărţirea profitului pentru cele 3 vaci în plus

Consolidare

O firmă gestionează toate vacile şi devide un singur centru de profit

Reglementări ale „statului”

Stabilirea unui număr maxim de vaci pe păşune sau impunerea redistribuirii profitului

Proiectarea mecanismelor (engl. “mechanism design”)

Stimulente şi penalizări pentru jucătorii individuali astfel încât să fie tentaţi să atingă optimul social

Problemă încă deschisă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 82: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

82

Beneficiul social şi beneficiul individual

Partajarea (sharing-ul) în reţele P2P

Poluarea

... în general, managementul resurselor din proprietatea comună

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 83: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

83

Jocul ajutorului social

Guvernul vrea să ajute un om sărac doar dacă acesta vrea să muncească

Săracul îşi caută de lucru doar dacă nu ia ajutor de la stat

engl. “the welfare game”

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 84: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

84

Jocul ajutorului social

(Aid, Try to work) nu este EN Pauper preferă Be idle

(Aid, Be Idle) nu este EN: Govt preferă No Aid

(No Aid, Be Idle) nu este EN: Pauper preferă Try to Work

(No Aid, Try to Work) nu este EN: Govt preferă Aid

Jocul nu are echilibru Nash! Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 85: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

85

Jocul ajutorului social

(Aid, Try to work) nu este EN Pauper preferă Be idle

(Aid, Be idle) nu este EN: Govt preferă No aid

(No Aid, Be Idle) nu este EN: Pauper preferă Try to Work

(No Aid, Try to Work) nu este EN: Govt preferă Aid

Jocul nu are echilibru Nash! Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 86: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

86

Jocul ajutorului social

(Aid, Try to work) nu este EN Pauper preferă Be idle

(Aid, Be idle) nu este EN: Govt preferă No aid

(No Aid, Be idle) nu este EN: Pauper preferă Try to work

(No Aid, Try to work) nu este EN: Govt preferă Aid

Jocul nu are echilibru Nash! Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 87: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

87

Jocul ajutorului social

(Aid, Try to work) nu este EN Pauper preferă Be idle

(Aid, Be idle) nu este EN: Govt preferă No Aid

(No Aid, Be idle) nu este EN: Pauper preferă Try to work

(No Aid, Try to work) nu este EN: Govt preferă Aid

Jocul nu are echilibru Nash (pur)! Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 88: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

88

Strategii pure şi mixte

Strategie pură

Jucătorul i alege strategia sij din mulţimea Si

Strategie mixtă

Jucătorul i alege strategia sij cu probabilitatea pij

pij 0, j pij = 1

Orice strategie pură este de asemenea şi o strategie mixtă

Un joc finit are întotdeauna cel puţin un echilibru Nash pur sau mixt

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 89: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

89

Strategii mixte

Profitul în strategii mixte este profitul aşteptat

Fie 1 profitul cu strategia s1 şi 4 cu strategia s2

Strategia mixtă (0,3, 0,7) dă profitul aşteptat 0,3 · 1 + 0,7 · 4 = 3,1

Un profit sigur de 3,1 este echivalent cu un profit aşteptat într-un joc cu profituri de 1 şi 4 cu probabilităţile 0,3 respectiv 0,7

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 90: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

90

Strategii mixte: interpretare

Jocuri în care se pot aplica simultan strategii multiple

Pariurile pe mai mulţi cai

Instanţe multiple ale aceluiaşi joc

Scenariu de război: qij % din piloţi urmează strategia sij

Acelaşi joc repetat la infinit

Pentru un singur joc: distribuţia de probabilitate este estimarea oponenţilor asupra deciziei unui jucător

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 91: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Metoda resturilor

engl. “oddment method”

Metodă simplă pentru calculul echilibrelor Nash mixte

Dacă jocul are un echilibru Nash pur, metoda nu se aplică

91 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 92: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Strategiile pentru Pauper

92 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 93: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Strategiile pentru Government

93 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 94: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

94

Echilibrul Nash în jocul ajutorului social cu strategie mixtă (I)

Dacă Government alege o probabilitate de 0.5 pentru Aid, Pauper nu poate profita de pe urma acestei decizii în alegerea uneia din acţiunile Work sau Be idle

Profitul Pauper (Work) = 0.5 · 2 + (1 – 0.5) · 1 = 1.5

Profitul Pauper (Be idle) = 0.5 · 3 + (1 – 0.5) · 0 = 1.5

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 95: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

95

Echilibrul Nash în jocul ajutorului social cu strategie mixtă (II)

Dacă Pauper alege Try to work cu probabilitatea 0.2, Government va fi indiferent între Aid şi No aid

Profitul Govt (Aid) = 0.2 · 3 + (1 – 0.2) · (–1) = –0.2

Profitul Govt (No aid) = 0.2 · (–1) + (1 – 0.2) · 0 = –0.2

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 96: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

96

Echilibrul Nash în jocul ajutorului social cu strategie mixtă (III)

Pentru probabilităţile 0.5 şi 0.2, atât Government cât şi Pauper au profituri egale pentru ambele acţiuni, ceea ce permite existenţa unui echilibru Nash

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 97: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Metoda 2

Determinarea strategiei pentru Pauper

3 · x + (–1) · (1 – x) = (–1) · x + 0 · (1 – x)

⇒ x = 0.2, 1 – x = 0.8

Determinarea strategiei pentru Goverment

2 · y + 1 · (1 – y) = 3 · y + 0 · (1 – y)

⇒ y = 0.5, 1 – y = 0.5

97 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 98: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

98

Stabilitatea

Dar dacă un jucător părăseşte strategia de echilibru, oponentul poate profita pentru a câştiga mai mult decât ar câştiga la echilibru

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 99: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

99

Raţionament probabilistic. Teoria jocurilor

1. Reţele bayesiene

2. Inferenţe cu reţele bayesiene

3. Teoria Dempster-Shafer

4. Teoria jocurilor

5. Echilibrul Nash

6. Optimalitatea Pareto

7. Concluzii

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 100: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

100

Optimalitatea Pareto

Un rezultat (x0,y0) este optim Pareto (sau dominant sau neinferior) dacă NU există alt rezultat (x,y) unde: Ambii jucători au un profit mai mare

x > x0 şi y > y0

Un jucător are profit mai mare iar celălalt are acelaşi profit x > x0 şi y = y0 , sau

x = x0 şi y > y0

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 101: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

Optimalitatea Pareto

Un rezultat este optim Pareto dacă este:

mai bun sau la fel decât alt rezultat din toate punctele de vedere

şi

mai bun strict din cel puţin un punct de vedere

101 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 102: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

102

Stări optime Pareto

Într-o stare optimă Pareto, jucătorii nu au motivaţia de a devia în coaliţie

De exemplu: dilema inculpaţilor

Ambii jucători au profit mai mare împreună dacă ambii neagă

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 103: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

103

Interpretare

Optimalitatea Pareto înseamnă o situaţie mai bună pentru cel puţin un jucător fără a dezavantaja niciun alt jucător

Optimalitatea Pareto nu înseamnă „egalitate” De exemplu împărţirea unui tort între 3 persoane A, B, C

A ia 70%, B ia 30%, C nu ia nimic

Această stare este un echilibru optim Pareto, deoarece pentru a-i da lui C ceva, A sau B ar trebui să renunţe la ceva

Totuşi, implică alocarea tuturor resurselor O stare în care A ia 50%, B ia 30% şi C nu ia nimic nu este

optimă Pareto

C poate lua 20% fără a-i afecta pe A sau B

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 104: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

104

Aplicaţii ale optimalităţii Pareto

Probleme de optimizare

Traficul în reţele de calculatoare

Planificarea task-urilor

Planificarea producţiei

Proiectarea componentelor

Procesele de reacţii chimice

Economie

Analiza eficienţei de piaţă

Îmbunătăţirea sistemului de impozitare

Etc.

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm

Page 105: Inteligenta artificiala: Retele bayesiene. Teoria evidentelor. Teoria jocurilor

105

Concluzii

Reţelele bayesiene asigură un mod concis de a reprezenta relaţiile de independenţă condiţională într-un domeniu şi de a face inferenţe

Teoria Dempster-Shafer combină surse de evidenţe posibil contradictorii. Se face o distincţie între probabilitatea unei propoziţii dată fiind o evidenţă incertă şi probabilitatea unei propoziţii în lipsa oricărei evidenţe

Teoria jocurilor studiază în mod abstract interacţiunile multipersonale, furnizând o metodă de modelare a comportamentului agenţilor raţionali

Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm