inteligenta artificiala: retele bayesiene. teoria evidentelor. teoria jocurilor

Click here to load reader

Post on 26-Jun-2015

419 views

Category:

Documents

13 download

Embed Size (px)

DESCRIPTION

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

TRANSCRIPT

Inteligen artificial 9. Raionament probabilistic. Teoria jocurilor Florin Leon Universitatea Tehnic Gheorghe Asachi din Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm2 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm3 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm4 Probabiliti P(A) fraciunea de lumi posibile n care A este adevrat Interpretarea frecventist (numr de experimente) Interpretarea fizic (proprieti ale obiectelor) Interpretarea subiectivist (caracterizarea convingerilor) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm5 Paradoxuri Problema Monty Hall Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm6 Paradoxuri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm7 Eroarea juctorului de rulet Dac a ieit rou, data urmtoare sunt mai multe anse s ias negru 1913, Monte Carlo negrul a ieit de 26 de ori la rnd Paradoxuri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm8 Eroarea procurorului Grupa de snge gsit la faa locului este o grup rar, AB cu Rh negativ, care are 1% frecven n populaie S-au mai gsit urme de pr blond, persoanele blonde constituind tot 1% din populaie Suspectul are grupa de snge respectiv i este blond, prezena mpreun a acestor trsturi avnd mpreun probabilitatea de 0,01% vinovat cu o probabilitate de 99,99% Oraul n care s-a petrecut crima are o populaie de 100.000 de locuitori, deci ali 10 oameni au aceleai trsturi 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.htm9 Probabiliti condiionate P(A|B) este fraciunea de lumi posibile n careB este adevrat i atunci i A este adevrat 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(DG) / P(G) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm10 Teorema lui Bayes P(A|B) = P(AB) / P(B) P(AB) = P(A|B) P(B) P(AB) = 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.htm11 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.htm12 Diagnoz Probabiliti cunoscute Meningit: P(M) = 0,002% Gt nepenit: P(G) = 5% Meningita cauzeaz gt nepenit n jumtate din cazuri: P(G|M) = 50% Dac un pacient are gtul nepenit, 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.htm13 Diagnoz Greeal ntlnit uneori: P(A|B) = P(B|A) Diagnostice pentru boli rare Trebuie avute n vedere probabilitile testului de a returna rezultate fals pozitive B boal T test Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm14 Independen iindependen condiionat Exemplul 1. Ion i Maria dau cu banul. Fiecare are un ban diferit Evenimente independente Rezultatul unui experiment nu influeneaz rezultatul celuilalt experiment Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm15 Independen iindependen condiionat Exemplul 2. Ion i Maria dau cu acelai ban Dac banul nu este corect, evenimentul A (Ion) poate aduce informaii asupra evenimentuluiB (Maria) Evenimentele nu sunt independente Rezultatul unui experiment poate influena cunotinele despre rezultatul celuilalt Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmIndependen iindependen condiionat Exemplul 2 (cont.). Fie C variabila banul este influenat n favoarea pajurei Dac tim C, experimentul A nu mai aduce informaii noi asupra lui B P(B|A,C) = P(B|C) A i B sunt independente condiional dat fiind C Situaia cauz comun 16 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmIndependen iindependen condiionat Exemplul 3. Ion i Maria locuiesc n zone diferite ale oraului i vin la serviciu cu tramvaiul, respectiv maina Ion a ntrziat i Maria a ntrziat pot fi considerate independente Dac vatmanii sunt n grev, atunci i traficul rutier crete Evenimentele devin condiional independente Sunt multe situaii din viaa real n care evenimente considerate independente sunt de fapt doar condiional independente 17 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmIndependen iindependen condiionat Exemplul 4. Att rceala ct i alergia l pot determina pe Ion s strnute Dac nu tim c Ion a strnutat, rceala i alergia sunt independente Dac tim c Ion a strnutat, rceala i alergia nu mai sunt independente Dac mai tim c Ion este rcit, probabil c rceala determin strnutul iar probabilitatea alergiei scade Situaia revocare prin explicare (engl. explaining away) 18 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm19 Reprezentarea cunotinelor incerte O situaie cu 5 variabile (exemplul urmtor) Specific o distribuie comun de probabilitatecu 25 1 = 31 parametri Fezabil Un sistem expert cu 37 de variabile pentru monitorizarea pacienilor de la terapie intensiv 237 1 1011 parametri Nefezabil Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm20 Reea 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 independeni fa de 31 Reea bayesian (J. Pearl, 1985) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm21 Comparaie Sistem expert pentru monitorizarea pacienilor de la terapie intensiv 37 variabile 509 parametrin loc de 1011 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmReprezentarea distribuiei comune de probabilitate Este adevrat doar dac fiecare nod este independent condiional de predecesorii din irul ordonat al nodurilor, dai fiind prinii nodului chain rule (regula de nmulirea probabilitilor) Dac efectele sunt considerate independente Nave Bayes Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm23 Interogri simple Care este probabilitatea ca alarma s se declaneze fr s fi fost nicio spargere i niciun cutremur iar John i Mary s sune? Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm24 Validitatea unei reele bayesiene O reea 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.htmAlgoritmul Bayes-Ball O modalitate simpl de a determina relaiile de independen i independen condiionat ntr-o reea bayesian Se presupune c o minge este trimis dintr-un nodn reea Mingea trece n moduri diferite, n funcie de cine o trimite (fiu sau printe) i starea nodului care o primete (observat/eviden sau neobservat) Nodurile la care mingea nu ajunge sunt independente (condiional) 25 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmReguli de trimitere a mingii 26 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemple 27 noduri eviden(gri) noduri neobservate (albe) o cale activnicio cale activ Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm28 Ordonarea nodurilor Reelele din dreapta sunt create prin introducerea succesiv a noilor noduri,de sus n jos Ambele sunt echivalente cu distribuia comun de probabilitate Nu sunt optime din punct de vedere al compactitii Necesit mai muli parametri Reeaua (b) necesit 31 de parametri, la fel ca distribuia comun Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm29 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm30 Inferena probabilitilor marginale Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm31 Nodul LA P(LA) = P(LA|LF) P(LF) + P(LA|~LF) P(~LF) = 0.6 0.15 + 0.05 (1 0.15) = 0.133Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm32 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.htm33 Probabilitile 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.htm34 Inferena prin enumerare Interogare: Care este probabilitatea spargerii, dac att John ct i Mary au dat telefon? Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm35 Rezolvare Evidena 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.htm36 Rezolvare acelai tip de calcule pentru negaie Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm37 Observaie 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.htm38 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm39 Teoria evidenelorDempster-Shafer Probabilitile evalueaz o situaie folosind un singur numr Teoria Dempster-Shafer acord propoziiilor 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 informaii nici despre A nici despre A, intervalul de ncredere este [0, 1] n loc de probabilitatea 0.5 Pe msur ce se acumuleaz informaii, intervalul se micoreaz bel(A) P(A) pl(A) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm40 Exemplul 1: aruncarea unui ban Dac nu avem nicio informaie despre ban, dac este corectsau 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.htm41 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 amndoi c lui George i-a fost furat maina Probabilitatea ca niciunul s nu fie de ncredere este 0.02 Probabilitatea ca mcar unul din ei s fie de ncredere este1 0.02 = 0.98 Intervalul de ncredere este [0.98, 1] Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm42 Exemplul 2 Cazul 2. Sue spune c i-a fost furat maina, Bill spune c nu Nu pot fi simultan ambii de ncredere (mrturiile se contrazic) Doar Sue este de ncredere (maina a fost furat) 0.9 x (1 0.8) = 0.18 Doar Bill este de ncredere (maina 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 probabilitile nenule (pentru normalizare la 1) 0.18 + 0.08 + 0.02 = 0.28 Convingerea c maina a fost furat 0.18 / 0.28 = 0.64 Convingerea c maina nu a fost furat 0.08 / 0.28 = 0.29 Intervalul de ncredere c maina a fost furat [0.64, 1 0.29] = [0.64, 0.71] Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm43 Formalizare H universul ipotezelor mutual exclusive(se mai noteaz cu i se mai numete cadru de discernmnt) m o funcie numit BBA (engl. Basic Belief Assignement, atribuire de convingeri de baz) sau funcie de mas m : (H) [0,1] (H) = mulimea prilor lui H m(|) = 0 Ae(H) m(A) = 1 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm44 Combinarea evidenelor Teoria Dempster-Shafer ne permite s combinm convingerile m care apar dinsurse multiple de evidene Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemplul 1 Dou site-uri de tiri relateaz despre o demonstraie Primul site are nivelul de ncredere de 80% iar al doilea are nivelul de ncredere de 60% Ambele afirm c demonstraia a fost una mare, cu peste 10000 de participani 45 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmRezolvare 46 nu exist evidene mpotriva faptului c demonstraia a fost mare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmExemplul 2 Primul site afirm c demonstraia a fost mare iar al doilea afirm contrariul Ar fi incorect s considerm m2({Mare}) = 0,4, deoareceal doilea site a spus doar c demonstraia a fost mic,nu a spus nimic despre o demonstraie mare Valoarea asociat mulimii vide este 0,48 i deci numitorul fraciei va fi 1 0,48 = 0,52 47 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmRezolvare 48 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm49 Exemplul anterior combinarea evidenelor ntr-o nou BBA incertitudinea rmas Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm50 Exemplul anterior Singurele perechi care se intersecteaz n mulimea vid sunt: m1({CarMissing}) = 0.9 im2({CarThere}) = 0.8 produsul: 0.72 numitorul: 1 0.72 = 0.28 Aceleai valori ca nainte Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm51 Alt exemplu Un pacient poate avea rceal (Cold), grip (Flu), Meningit sau Nimic (e sntos) Mulimea de ipoteze H = {C,F,M,N} Din studii anterioare: Febra susine ipoteza {C,F} la nivelul 0.5 i{M} la nivelul 0.2 Greurile susin ipoteza {C,F,N} la nivelul 0.7 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm52 Combinarea evidenelor Singura combinaie care produce mulimea vid are produsul 0.14,deci numitorul va fi 1 0.14 = 0.86 Avem un pacient cu febr i greuri (m1 i m2). Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm53 Noua BBA Posibilitatea de rceal sau grip: [0.581, 0.93] Posibilitatea de meningit: [0.07, 0.175] 0.825 = 0.581 + 0.244 suma tuturor submulimilor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm54 Alt eviden Dac se face un test de laborator i acesta iese pozitiv, indicnd ipoteza {M} la nivelul 0.8, cum se schimb convingerile? Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm55 Discuie O convingere puternic atribuit mulimii vide indic evidene conflictuale n mulimea de convingeri Cnd avem mulimi mari de ipoteze i mulimi complexe de evidene, calculele devin foarte laborioase Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmEvidene 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.htmAplicaii din viaa real Sisteme expert Sisteme de diagnoz Combinarea informaiilor provenite de la mai muli senzori (engl. sensor fusion) 57 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm58 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm59 Teoria jocurilor Studiaz interaciunile strategice ntre juctori raionali care aleg diferite aciuni pentru a-i maximiza profitul Mai formal, reprezint studiul modelelor matematice de conflict i cooperare ntre decideni inteligeni i raionali Jocurile din cursul 3 rezolvabile cu algoritmul minimax sunt un caz particular: jocuri secveniale Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm60 Aplicaii Oriunde exist interaciuni strategice ntre juctori raionali Economie Strategiile nucleare ale rzboiului rece Psihologie Sociologie tiina calculatoarelor (reele etc.) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm61 Caracteristicile unui joc Jocurile studiate n teoria jocurilor au urmtoarele elemente: Doi sau mai muli juctori Alegerea unei aciuni implic o strategie Unul sau mai multe rezultate Rezultatul depinde de strategiile alese Juctorii sunt raionali ncearc s-i maximizeze profitul indiferent de aciunile celorlali juctori Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm62 Dilema inculpailor engl. prisoners dilemma Juctori 2 inculpai Aciuni Inculpatul 1: Mrturisete, Neag Inculpatul 2: Mrturisete, Neag Strategii Inculpaii i aleg aciunile simultan, fr a cunoate aciunea celuilalt Rezultate Numrul de ani de nchisoare Profitul Mai puini ani profit mai mare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm63 Reprezentarea n forma normal (strategic) O matrice care conine juctorii, strategiile i profiturile Se presupune c juctorii acioneaz simultan Pentru dilema inculpailor: Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm64 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm65 Echilibrul Nash Echilibru Nash pentru o strategie pur ) , ( ) , (* * *i i i i i is s u s s u >Profitul(utilitatea) juctorului i Strategia dinechilibrul Nash Strategia juctorului i Strategiile celorlali juctori cu excepia lui i Determinist, care nu implic probabiliti Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm66 Echilibrul Nash Echilibrul Nash pentru o strategie pur Echilibrul Nash este strict dac: Strile din care niciun juctor nu-i poate mri profitul prin schimbarea unilateral a strategiei ) , ( ) , (* * *i i i i i is s u s s u >) , ( ) , (* * *i i i i i is s u s s u >Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmCalculul echilibrelor Nash pure Se evideniaz maximele pe linii pentru primul juctor cu { Se evideniaz maximele pe coloane pentru al doilea juctor cu } Strile ncadrate de { } sunt echilibre Nash pure 67 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm68 Exemple Dilema inculpailor Btlia sexelor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm69 Tragedia punii comunale engl. the tragedy of the commons Punea este folosit n comun de 6 rani,fiecare cu cte o vac Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm70 Tragedia punii comunale Fiecare vac d 20 de litri de lapte pe zi Capacitatea punii este de 8 vaci Pentru fiecare vac peste 8, producia de lapte scade cu 2 litri Exist mai puin iarb de pscut pentru fiecare vac, deci i mai puin lapte Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm71 20 litri 20 litri 20 litri 20 litri 20 litri 20 litri Producia zilnic total de lapte: 120 litri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm72 ranii vor s-i maximizeze producia de lapte 20 litri 20 litri 20 litri 20 litri 20 litri Producia zilnic total de lapte: 140 litri (7 vaci) 40 litri O s cumpr nc o vac Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm73 Acum s-a atins capacitatea maxim a punii. Dar ranii nu se opresc. 20 litri 20 litri 20 litri 20 litri Producia zilnic total de lapte: 160 litri (8 vaci) 40 litri 40 litri Atunci i eu o s-mi cumpr Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm74 18 litri 18 litri 18 litri Producia 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.htm75 32 litri 16 litri 16 litri Producia zilnic total de lapte: 160 litri (10 vaci) 32 litri 32 litri 32 litri Vaca produc e acum mai puin, dar 2 vaci o s rezolve problema Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm76 28 litri 14 litri Producia zilnic total de lapte: 154 litri (11 vaci) 28 litri 28 litri 28 litri O s-mi cumpr nc una 28 litri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm77 24 litri Producia zilnic total de lapte: 144 litri (12 vaci) 24 litri 24 litri 24 litri 24 litri Toat lumea i cumpr nc o vac, deci i eu 24 litri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm78 20 litri Producia zilnic total de lapte: 130 litri (10 vaci) 30 litri 20 litri nc pot crete produciadac iau i a treia vac 20 litri 20 litri 20 litri Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm79 -100-500501001502000 2 4 6 8 10 12 14 16 18 20Total CowsMilk Production (in liters)Producia maxim de lapte pentru pune: 162 litri/zi ranii vor continua s cumpere vaci pn cnd sunt 15 vaci n total pe pune Nivelul curent Ctigul sau pierderea pentru un ran la cumprarea unei noi vaci Producia total pentru toate vacile Numrul total de vaci Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm80 -100-500501001502000 2 4 6 8 10 12 14 16 18 20Total CowsMilk Production (in liters)Producia maxim de lapte pentru pune: 162 litri/zi Nivelul curent Producia total pentru toate vacile Optimul social Rezultatul comportamentului individual diferena Numrul total de vaci Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm81 Soluii? Acord de cooperare ntre rani mprirea profitului pentru cele 3 vaci n plus Consolidare O firm gestioneaz toate vacile i devide un singur centru de profit Reglementri ale statului Stabilirea unui numr maxim de vaci pe pune sau impunerea redistribuirii profitului Proiectarea mecanismelor (engl. mechanism design) Stimulente i penalizri pentru juctorii individuali astfel nct s fie tentai s ating optimul social Problem nc deschis Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm82 Beneficiul social i beneficiul individual Partajarea (sharing-ul) n reele P2P Poluarea ... n general, managementul resurselor din proprietatea comun Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm83 Jocul ajutorului social Guvernul vrea s ajute un om srac doar dac acesta vrea s munceasc Sracul 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.htm84 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.htm85 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.htm86 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.htm87 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.htm88 Strategii pure i mixte Strategie pur Juctorul i alege strategia sijdin mulimea Si Strategie mixt Juctorul 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 puin un echilibru Nash pur sau mixt Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm89 Strategii mixte Profitul n strategii mixte este profitul ateptat Fie 1 profitul cu strategia s1 i 4 cu strategia s2 Strategia mixt (0,3, 0,7) d profitul ateptat0,3 1 + 0,7 4 = 3,1 Un profit sigur de 3,1 este echivalent cu un profit ateptat ntr-un joc cu profituri de 1 i 4 cu probabilitile 0,3 respectiv 0,7 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm90 Strategii mixte: interpretare Jocuri n care se pot aplica simultan strategii multiple Pariurile pe mai muli cai Instane multiple ale aceluiai joc Scenariu de rzboi: qij % din piloi urmeaz strategia sij Acelai joc repetat la infinit Pentru un singur joc: distribuia de probabilitate este estimarea oponenilor asupra deciziei unui juctor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmMetoda 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.htmStrategiile pentru Pauper 92 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmStrategiile pentru Government 93 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm94 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 aciunile 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.htm95 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.htm96 Echilibrul Nash n jocul ajutorului social cu strategie mixt (III) Pentru probabilitile 0.5 i 0.2, att Government ct i Pauper au profituri egale pentru ambele aciuni, ceea ce permite existena unui echilibru Nash Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmMetoda 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.htm98 Stabilitatea Dar dac un juctor prsete strategia de echilibru, oponentul poate profita pentru a ctiga mai mult dect ar ctiga la echilibru Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm99 Raionament probabilistic.Teoria jocurilor 1. Reele bayesiene 2. Inferene cu reele 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.htm100 Optimalitatea Pareto Un rezultat (x0,y0) este optim Pareto(sau dominant sau neinferior) dacNU exist alt rezultat (x,y) unde: Ambii juctori au un profit mai mare x > x0 i y > y0

Un juctor are profit mai mare iar cellalt are acelai profit x > x0 i y = y0 , sau x = x0 i y > y0 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmOptimalitatea Pareto Un rezultat este optim Pareto dac este: mai bun sau la fel dect alt rezultat din toate punctele de vederei mai bun strict din cel puin un punct de vedere 101 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm102 Stri optime Pareto ntr-o stare optim Pareto, juctorii nu au motivaia de a devia n coaliie De exemplu: dilema inculpailor Ambii juctori au profit mai mare mpreun dac ambii neag Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm103 Interpretare Optimalitatea Pareto nseamn o situaie mai bun pentru cel puin un juctor fr a dezavantaja niciun alt juctor Optimalitatea Pareto nu nseamn egalitate De exemplu mprirea 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 renune la ceva Totui, 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% fr a-i afecta pe A sau B Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm104 Aplicaii ale optimalitii Pareto Probleme de optimizare Traficul n reele de calculatoare Planificarea task-urilor Planificarea produciei Proiectarea componentelor Procesele de reacii chimice Economie Analiza eficienei de pia mbuntirea sistemului de impozitare Etc. Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm105 Concluzii Reelele bayesiene asigur un mod concis de a reprezenta relaiile de independen condiionalntr-un domeniu i de a face inferene Teoria Dempster-Shafer combin surse de evidene posibil contradictorii. Se face o distincie ntre probabilitatea unei propoziii dat fiind o eviden incert i probabilitatea unei propoziii n lipsa oricrei evidene Teoria jocurilor studiaz n mod abstract interaciunile multipersonale, furniznd o metod de modelare a comportamentului agenilor raionali Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm