Reprezentarea Cunoștințelor Incerte - Artificial Intelligence PDF

Inteligent, ă Artificială Reprezentarea cunos, tint, elor incerte Slides: Alexandru Sorici Reprezentarea cunos, tint, elor incerte | 0 / 40  Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele...

Inteligent, ă Artificială Reprezentarea cunos, tint, elor incerte Slides: Alexandru Sorici Reprezentarea cunos, tint, elor incerte | 0 / 40  Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Reprezentarea cunos, tint, elor incerte | 0 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene În exemplele de probleme de căutare date până acum am presupus cunos, tint, e certe asupra stării curente s, i act, iuni cu efect determinist... dar, în practică, multe situat, ii prezintă necesitatea de a face fat, ă incertitudinii Reprezentarea cunos, tint, elor incerte | 1 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Exemplu de rat, ionament deductiv pe relat, ia simptom → problemă dacă simptom=durere dint, i atunci problemă=carie Rat, ionament gres, it (sau, cel put, in, incomplet) Reprezentarea cunos, tint, elor incerte | 2 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Exemplu de rat, ionament deductiv pe relat, ia simptom → problemă dacă simptom=durere dint, i atunci problemă=carie Rat, ionament gres, it (sau, cel put, in, incomplet) dacă simptom=durere dint, i atunci problemă=abces dacă simptom=durere dint, i atunci problemă=boală gingivală... Reprezentarea cunos, tint, elor incerte | 2 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Exemplu de rat, ionament deductiv pe relat, ia simptom → problemă dacă simptom=durere dint, i atunci problemă=carie Rat, ionament gres, it (sau, cel put, in, incomplet) dacă simptom=durere dint, i atunci problemă=abces dacă simptom=durere dint, i atunci problemă=boală gingivală... Probleme principiale: Este nefezabil (chiar imposibil) să completăm lista Simpla enumerare a posibilelor cauze nu ne dă informat, ie despre plauzibilitatea (likelihood) lor relativă O relat, ie cauzală de tip problemă=abces → simptom=durere dint, i nu este tot timpul adevărată Reprezentarea cunos, tint, elor incerte | 2 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Necesitatea surprinderii (modelării) incertitudinii apare din cauza: Imposibilităt, ii sau lipsei de fezabilitate a enumerării regulilor de inferent, ă Ignorant, ei la nivel teoretic: nu există suficiente cunos, tint, e pentru a scrie reguli de inferent, ă corecte Ignorant, ei la nivel practic: chiar dacă avem reguli de inferent, ă definite exhaustiv, ne lipses, te informat, ia necesară aplicării lor Reprezentarea cunos, tint, elor incerte | 3 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Adevăr, Falsitate, Încredere (Belief) Teoria Probabilităt, ilor permite asignarea unui grad numeric de certitudine (valoare ∈ [0, 1]) unei afirmat, ii (care poate fi adevarată sau falsă) Atent, ie: grad de certitudine ̸= grad de adevăr (not, iune utilizată, de exemplu, în Logica Fuzzy) Teoria Probabilităt, ilor permite modelarea incertitudinii cauzate de dificultatea enumerării sau de lipsa teoretică/practică de cunos, tint, e Reprezentarea cunos, tint, elor incerte | 4 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Definit, ii Ret, ele Bayesiene Probabilitatea unui eveniment incert este măsura gradului de încredere sau plauzabilitatea producerii unui eveniment. Gradul de încredere se poate modifica prin obt, inerea de probe (evidence) Probabilitate necondit, ionată (apriori) – denotă un grad de încredere înaintea obt, inerii probe pentru o ipoteză / un eveniment Probabilitate condit, ionată (aposteriori) – denotă un grad de încredere actualizat în urma obt, inerii unor probe pentru o ipoteză / un eveniment Reprezentarea cunos, tint, elor incerte | 5 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Definit, ii Ret, ele Bayesiene Pentru a defini evenimente vom lucra cu variabile aleatoare Variabilele aleatoare asignează fiecărui eveniment elementar / atomic o valoare ∈ [0, 1]. Variabilele aleatoare (s, i evenimentele atomice pe care le denotă) pot avea domenii de definit, ie care pot fi: booleene: e.g. plouă / nu plouă discrete: e.g. cele s, ase fet, e ce pot rezulta din aruncarea unui zar continue: e.g. viteza moleculelor de gaz dintr-un recipient Reprezentarea cunos, tint, elor incerte | 6 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Definit, ii Ret, ele Bayesiene Modul în care se atribuie valori de probabilitate unui eveniment poate fi privit din diferite perspective: Perspectivă frecventistă: valorile de probabilitate vin din măsuratori (e.g. incident, a unei boli într-o t, ară se obt, ine ca medie peste ani a procentului de pacient, i internat, i cu acea boală în spitale) Perspectivă obiectivistă: incertitudinea (s, i valoarea de probabilitate care o cuantifică) este o "proprietate a universului" pe care o descoperim prin măsurători (e.g. fenomene cuantice) Perspectiva subiectivistă: valorile de probabilitate vin din "gradele de încredere" acordate de un agent rat, ional (e.g. s, ansele de a lua un interview) Reprezentarea cunos, tint, elor incerte | 7 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Definit, ii Ret, ele Bayesiene Evenimente mutual exclusive: nu pot fi simultan adevărate. Exemple: Aruncarea unei monede: cade cap / pajură Aruncarea unui zar: fet, ele 1, 2, 3 sunt mutual exclusive Evenimente mutual exhaustive: enumerarea lor acoperă tot spat, iul posibilităt, ilor pentru situat, ia/procesul în cauză. Exemple: Aruncarea unei monede: cap / pajură Aruncarea unui zar: obt, inerea fet, elor 1,2,3,4,5,6 sunt evenimente mutual exhaustive Reprezentarea cunos, tint, elor incerte | 8 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Notat, ii Ret, ele Bayesiene P(X = x) – gradul de încredere (probabilitatea) ca variabila aleatoare X (scris cu majusculă) să aibă valoarea x (scris cu literă mică) Vom folosi notat, ia P(X ) pentru a denota distribut, ia de probabilitate a variabilei X (i.e. P(X = x1 ), P(X = x2 ),... , P(X = xn ) pentru toate valorile x1 , x2 ,... , xn pe care le-ar putea avea variabila X ) Pentru cazul variabilelor de tip eveniment binar (cu doar două valori: adevărat sau fals), folosim următoarea prescurtare a notat, iei: P(X = adev ) = P(x) P(X = fals) = P(¬x) Reprezentarea cunos, tint, elor incerte | 9 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Notat, ii Ret, ele Bayesiene O funct, ie P : S → R este o măsură de probabilitate (unde S este un spat, iu de probabilitate) dacă satisface axiomele: 0 ≤ P(X = x) ≤ 1 P(S) = 1 (sau P(adev ) = 1, P(fals) = 0) P(X = x ∨ Y = y ) = P(X = x) + P(Y = y ) − P(X = x ∧ Y = y ) Din axiome rezultă: P(x ∨ ¬x) = P(adev ) = P(x) + P(¬x) − P(x ∧ ¬x) = P(x) + P(¬x) − P(fals) ⇒ P(x) = 1 − P(¬x) regula probabilităt, ii complementare Reprezentarea cunos, tint, elor incerte | 10 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Notat, ii Ret, ele Bayesiene Distribut, ia comună a unor evenimente (joint probability distribution) Exemplu: Fie variabila aleatoare binară Gripa cu valori {adev , fals} s, i variabila aleatoare Tuse cu valori {absenta, usoara, grava} Distribut, ia comună (P(Gripa ∧ Tuse) = P(Gripa, Tuse)) a celor două variabile aleatoare se poate reprezenta sub forma unei tabele: absenta usoara grava adev 0.05 0.20 0.15 fals 0.4 0.12 0.08 Reprezentarea cunos, tint, elor incerte | 11 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Notat, ii Ret, ele Bayesiene Pentru evenimente e1 , e2 ,... , en mutual exclusive: P(e1 ∨ e2 ∨... ∨ en ) = P(e1 ) + P(e2 ) +... + P(en ) Formula probabilităt, ii totale (a marginalizării): fie e(A) – mult, imea de evenimente atomice mutual exclusive s, i exhaustive în care apare evenimentul A. X P(A) = P(ei ) ei ∈e(A) Exemplu: fie evenimentele din distribut, ia comună P(Gripa, Febra): {(gripa ∧ febra), (gripa ∧ ¬febra), (¬gripa ∧ febra), (¬gripa ∧ ¬febra)} X P(gripa) = P(gripa ∧ febra) + P(gripa ∧ ¬febra) = P(gripa ∧ F ) F ∈{febra,¬febra} X P(¬gripa) = P(¬gripa ∧ febra) + P(¬gripa ∧ ¬febra) = P(¬gripa ∧ F ) F ∈{febra,¬febra} Reprezentarea cunos, tint, elor incerte | 12 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Notat, ii Ret, ele Bayesiene Regula produsului Se aplică în cadrul probabilităt, ilor condit, ionate. Probabilitatea de producere a evenimentului A, în condit, iile producerii evenimentului B se notează ca P(A|B) P(A ∧ B) P(A|B) = P(B) ⇒ P(A ∧ B) = P(A|B) · P(B) = P(B|A) · P(A) Reprezentarea cunos, tint, elor incerte | 13 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Notat, ii Ret, ele Bayesiene Regula probabilităt, ii totale s, i regula produsului pot fi combinate: În exemplul de gripă s, i febră putem scrie: P(gripa) = P(gripa|febra) · P(febra) + P(gripa|¬febra) · P(¬febra) Pe caz general, dacă un eveniment Y se poate descompune în n evenimente atomice Y1 , Y2 ,... , Yn mutual exclusive s, i exhaustive, atunci pentru orice eveniment X este adevărată identitatea (regula probabilităt, ii totale): n X n X P(X) = P(X ∧ Yi ) = P(X|Yi ) · P(Yi ) i=1 i=1 O aplicare uzuală a acestei reguli este pentru descompunerea evenimentelor binare Y ({Y1 = true, Y2 = false}) în: P(X) = P(X|y) · P(y) + P(X|¬y) · P(¬y) unde am folosit notat, ia pe scurt y s, i ¬y pentru a desemna Y1 = true s, i Y2 = false, respectiv. Reprezentarea cunos, tint, elor incerte | 14 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Interogări probabilistice Ret, ele Bayesiene Folosirea distribut, iei comune pentru inferent, e Dacă se cunoas, te distribut, ia de probabilitate comună a tuturor variabilelor aleatoare ce descriu o stare a problemei, se poate răspunde oricărei interogări probabilistice Exemplu: dp ¬dp Unde DP = durere în piept, tm ¬tm tm ¬tm TM = tensiune arterială bi 0.09 0.05 0.07 0.01 mare, BI=boală de inimă ¬bi 0.02 0.08 0.03 0.65 P(bi ∨ dp) =P(bi) + P(dp) − P(bi ∧ dp) = =P(bi ∧ dp ∧ tm) + P(bi ∧ dp ∧ ¬tm) + P(bi ∧ ¬dp ∧ tm) + P(bi ∧ ¬dp ∧ ¬tm)+ P(bi ∧ dp ∧ tm) + P(¬bi ∧ dp ∧ tm) + P(bi ∧ dp ∧ ¬tm) + P(¬bi ∧ dp ∧ ¬tm)− (P(bi ∧ dp ∧ tm) + P(bi ∧ dp ∧ ¬tm)) =0.07 + 0.01 + 0.09 + 0.02 + 0.05 + 0.08 = 0.32 Reprezentarea cunos, tint, elor incerte | 15 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Interogări probabilistice Ret, ele Bayesiene De obicei vom dori calcularea unei probabilităt, i condit, ionate a unei variabile date fiind probe: P P(bi ∧ tm ∧ DP) P(bi ∧ tm) DP 0.09 + 0.07 P(bi|tm) = = P = = 0.76 P(tm) P(tm ∧ BI ∧ DP) 0.09 + 0.07 + 0.02 + 0.03 BI,DP sau P P(¬bi ∧ tm ∧ DP) DP |{z} P(¬bi ∧ tm) (U)nobserved 0.02 + 0.03 P( ¬bi | tm ) = = X = = 0.24 |{z} |{z} P(tm) P(tm ∧ BI ∧ DP) 0.09 + 0.07 + 0.02 + 0.03 (Q)uery (E)vidence BI,DP | {z } normali(Z)er Reprezentarea cunos, tint, elor incerte | 16 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Interogări probabilistice Ret, ele Bayesiene 1 În exemplul anterior putem observa că α = P(TM) este constant s, i act, ionează ca un factor de normalizare, ce face ca probabilităt, i relevante să însumeze 1. Astfel, un artificiu de calcul ne poate scuti de explicitarea factorului de normalizare: P(bi|tm) = α · P(bi ∧ tm) = α(0.09 + 0.07) P(¬bi|tm) = α · P(¬bi ∧ tm) = α(0.02 + 0.03) S, tim că P(bi|tm) + P(¬bi|tm) = 1, as, adar: 1 α= 0.09 + 0.07 + 0.02 + 0.03 Reprezentarea cunos, tint, elor incerte | 17 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Interogări probabilistice Ret, ele Bayesiene Procedura generală de inferent, ă: 1 1 X P(Q|E1 , E2 ,...) = P(Q ∧ E1 ∧ E2 ,...) = P(Q ∧ E1 ∧ E2 ∧... ∧ U1 ∧ U2 ∧...) Z Z U1 ,U2 ,... unde: Q – variabila aleatoare interogată E – mult, imea de probe (variabile aleatoare a căror valoare se cunoas, te cu certitudine) U – mult, imea de variabile aleatoare neobservate (care împreună cu Q s, i E constituie evenimente mutual exclusive s, i exhaustive) 1/Z – factor de normalizare al distribut, iei Reprezentarea cunos, tint, elor incerte | 18 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Interogări probabilistice Ret, ele Bayesiene Procedura generală de inferent, ă poate fi intractabilă computat, ional: Pentru n variabile aleatoare booleene tabela distribut, iei de probabilitate comună are 2n intrări Cost computat, ional în timp s, i spat, iu: O(2n ) Pe caz de variabile discrete cu mai mult de 2 valori, situat, ia se complică s, i mai mult Reprezentarea cunos, tint, elor incerte | 19 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Independent, ă Ret, ele Bayesiene În exemplul de analiză al bolii de inimă, presupunem că am mai considera rezultatul meciului FCSB-Dinamo cu valori posibile RM = {fcsb, dinamo, remiza}. Atunci am avea: P(BI, TM, DP, RM) = P(BI|RM, TM, DP) · P(RM, TM, DP) Dar, dacă presupunem că rezultatul unui meci nu influent, ează starea de sănătate a unui pacient, atunci P(BI|RM, TM, DP) = P(BI|TM, DP). ⇒ reducem un tabel de distribut, ie comună de probabilitate de 2 × 2 × 2 × 3 = 24 de valori la două tabele de 3 (RM) + 8 (BI, DP, TM) = 11 valori. Reprezentarea cunos, tint, elor incerte | 20 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Independent, ă Ret, ele Bayesiene Independent, ă condit, ională S, tim că P(A|B) = P(A ∧ B)/P(B) Insă, spunem că evenimentul A este independent de evenimentul B dacă: P(A|B) = P(A) În caz că A s, i B sunt independente: P(A ∧ B) = P(A) · P(B) Evenimentele A si B sunt independente condit, ional fiind dat un eveniment C dacă: S, tiind că C apare, aparit, ia lui A nu influent, ează aparit, ia lui B s, i aparit, ia lui B nu influent, ează aparit, ia lui A P(A|C) = P(A|B, C) P(A, B|C) = P(A|C) · P(B|C) Reprezentarea cunos, tint, elor incerte | 21 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene S, tim că: P(X , Y ) = P(X |Y ) · P(Y ) P(X , Y ) = P(Y |X ) · P(X ) astfel că: P(Y|X) · P(X) P(X|Y) = – Teorema lui Bayes P(Y) Interpretat cel mai des ca: P(Evidence|Hypothesis) · P(Hypothesis) P(Hypothesis|Evidence) = P(Evidence) Plauzabilitate · APriori APosteriori = Probe Reprezentarea cunos, tint, elor incerte | 22 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene Exemplu utilizare Bayes: considerăm o formă de gripă ce afectează 1% din populat, ie s, i un test care indică prezent, a bolii cu o anumită certitudine. P(gripa) = 0.01 P(Test = +|gripa) = 0.9 P(Test = +|¬gripa) = 0.2 Care este probabilitatea P(gripa|Test = +)? Reprezentarea cunos, tint, elor incerte | 23 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene Exemplu utilizare Bayes: considerăm o formă de gripă ce afectează 1% din populat, ie s, i un test care indică prezent, a bolii cu o anumită certitudine. P(gripa) = 0.01 P(Test = +|gripa) = 0.9 P(Test = +|¬gripa) = 0.2 Care este probabilitatea P(gripa|Test = +)? Folosind Bayes: P(Test = +|gripa) · P(gripa) P(gripa|Test = +) = P(Test = +) P(Test = +|gripa) · P(gripa) = P(Test = +|gripa) · P(gripa) + P(Test = +|¬gripa) · P(¬gripa) 0.9 · 0.01 = ≈ 0.043 0.9 · 0.01 + 0.2 · 0.99 Reprezentarea cunos, tint, elor incerte | 23 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene Generalizare Teoremă Bayes la mai multe ipoteze Fie h1 , h2 ,... , hk ipoteze posibile pentru probele e Dacă hi mutual exclusive s, i exhaustive, i = 1, k P(e|hi ) · P(hi ) P(hi |e) = Pk j=1 P(e|hj ) · P(hj ) Reprezentarea cunos, tint, elor incerte | 24 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene Generalizare Teoremă Bayes la mai multe ipoteze s, i mai multe probe Fie h1 , h2 ,... , hk ipoteze posibile pentru probele e1 , e2 ,... , en Dacă hi mutual exclusive s, i exhaustive, i = 1, k P(e1 , e2 ,... , en |hi ) · P(hi ) P(hi |e1 , e2 ,... , en ) = Pk j=1 P(e1 , e2 ,... , en |hj ) · P(hj ) Dacă evenimentele probă sunt independente condit, ional dat fiind hi , atunci: P(e1 , e2 ,... , en |hi ) =? Reprezentarea cunos, tint, elor incerte | 25 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene Generalizare Teoremă Bayes la mai multe ipoteze s, i mai multe probe Fie h1 , h2 ,... , hk ipoteze posibile pentru probele e1 , e2 ,... , en Dacă hi mutual exclusive s, i exhaustive, i = 1, k P(e1 , e2 ,... , en |hi ) · P(hi ) P(hi |e1 , e2 ,... , en ) = Pk j=1 P(e1 , e2 ,... , en |hj ) · P(hj ) Dacă evenimentele probă sunt independente condit, ional dat fiind hi , atunci: P(e1 , e2 ,... , en |hi ) = P(e1 |hi ) · P(e2 |hi ) ·... · P(en |hi ) Reprezentarea cunos, tint, elor incerte | 25 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor : Teorema Bayes Ret, ele Bayesiene Modelul Naive Bayes Independent, a condit, ională între evenimente probă este deseori presupusă, chiar s, i când nu t, ine de fapt. n Q P(Cauza, E1 , E2 ,... En ) = P(Cauza) · P(Ei |Cauza) i=1 n 1 Q P(Cauza|E1 , E2 ,... En ) = α · P(Cauza) · P(Ei |Cauza), unde α = P(E1 ,E2 ,...,En ) i=1 Cauza Maximum APosteriori n Y CauzaMAP = arg max P(Cauzaj ) · P(Ei |Cauzaj ) j i Reprezentarea cunos, tint, elor incerte | 26 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Definit, ii Reprezentarea cunos, tint, elor incerte | 27 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Definit, ii Ret, ele Bayesiene Reprezintă explicit relat, iile de dependent, a cauzală între variabile aleatoare sub forma unui graf orientat aciclic (DAG) Specifică distribut, iile de probabilitate apriori: pentru variabile necondit, ionate probabilităt, i condit, ionate: pentru variabilele condit, ionate de una sau mai multe variabile părinte Informat, ia despre relat, iile de dependent, ă între variabile ajută la simplificarea procedurilor de inferent, ă probabilistică Exemplul cu analiza bolii de inimă: RM BI DP TM Reprezentarea cunos, tint, elor incerte | 28 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Definit, ii Fiecare nod dintr-o ret, ea Bayesiana este o variabilă aleatoare Legăturile orientate X → Y denotă că variabila X are of influent, ă directă asupra variabilei Y. Notăm prin parinti(Y) mult, imea de variabile care influent, ează direct variabila Y. Mult, imea parinti(Y ) poate fi si vidă. Fiecare nod are asociată o distribut, ie de probabilităt, i condit, ionate ce cuantifică P(Xi |parinti(Xi )) Pentru variabile aleatoare boolene sau discrete, distribut, ia ia forma unor tabele de probabilitat, i condit, ionate (CPT) Reprezentarea cunos, tint, elor incerte | 29 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Definit, ii Structură ret, ea Bayesiană P(H) P(C) 0.001 0.002 Pentru că variabilele aleatoare din Hot Cutremur exemplu sunt binare, tabela de probabilităt, i condit, ionate pentru H C P(A | H, C) P(A|H, C) este: T T 0.95 T F 0.94 Alarma H C P(A | H, C) F T 0.29 T F F F 0.001 T T 0.95 0.05 TelMihai TelPompier T F 0.94 0.06 F T 0.29 0.71 A P(M | A) F F 0.001 0.999 A P(P | A) T 0.9 T 0.7 F 0.05 F 0.01 Reprezentarea cunos, tint, elor incerte | 30 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Structură Structura unei ret, ele bayesiene ajută la: Reprezentarea distribut, iei de probabilitate a mai multor variabile aleatoare Specificarea independent, ei condit, ionale – construct, ia ret, elei Factorizarea distribut, iei comune de probabilitate a variabilelor aleatoare n Y P(X1 , X2 ,... , Xn ) = P(Xi |parinti(Xi )) i=1 Reprezentarea cunos, tint, elor incerte | 31 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Structură Cum construim o ret, ea a.î. distribut, ia de probabilităt, i condit, ionate să fie o bună reprezentare a problemei / situat, iei modelate? Reprezentarea cunos, tint, elor incerte | 32 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Structură Cum construim o ret, ea a.î. distribut, ia de probabilităt, i condit, ionate să fie o bună reprezentare a problemei / situat, iei modelate? Din regula produsului de probabilităt, i aplicată pe n noduri dintr-o ret, ea bayesiană avem: P(X1 , X2 ,... , Xn ) = P(Xn |Xn−1 , Xn−2 ,... , X1 )P(Xn−1 , Xn−2 ,... , X1 ) = P(Xn |Xn−1 , Xn−2 ,... , X1 )P(Xn−1 |Xn−2 ,... , X1 )P(Xn−2 ,... , X1 ) n Y = P(Xn |Xn−1 , Xn−2 ,... , X1 )P(Xn−1 |Xn−2 ,... , X1 )... P(X1 ) = P(Xi |Xi−1... X1 ) i=1 Reprezentarea cunos, tint, elor incerte | 32 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Structură Cum construim o ret, ea a.î. distribut, ia de probabilităt, i condit, ionate să fie o bună reprezentare a problemei / situat, iei modelate? Din regula produsului de probabilităt, i aplicată pe n noduri dintr-o ret, ea bayesiană avem: P(X1 , X2 ,... , Xn ) = P(Xn |Xn−1 , Xn−2 ,... , X1 )P(Xn−1 , Xn−2 ,... , X1 ) = P(Xn |Xn−1 , Xn−2 ,... , X1 )P(Xn−1 |Xn−2 ,... , X1 )P(Xn−2 ,... , X1 ) n Y = P(Xn |Xn−1 , Xn−2 ,... , X1 )P(Xn−1 |Xn−2 ,... , X1 )... P(X1 ) = P(Xi |Xi−1... X1 ) i=1 Comparând ecuat, ia de mai sus cu factorizarea unei ret, ele Bayesiene, observăm că într-o RB facem presupunerea că: P(Xi |Xi−1 ,... , X1 ) = P(Xi |parinti(Xi )) pentru fiecare nod Xi , presupunând că parinti(Xi ) ⊆ {Xi−1 ,... , X1 } Reprezentarea cunos, tint, elor incerte | 32 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Structură În construirea unei RB, asigurăm o reprezentare corectă a domeniului cu condit, ia ca fiecare nod să fie independent condit, ional de nondescendent, i, fiind dat, i părint, ii săi. Condit, ia aceasta poate fi satisfăcută dacă etichetăm nodurile într-o ordine consistentă cu DAG (graf orientat aciclic). Astfel, în general, cauzele preced direct efectul: parint, ii unui nod Xi trebuie să fie toate acele noduri (Xi−1 ,... , Xi−k ) care influent, ează direct Xi Reprezentarea cunos, tint, elor incerte | 33 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Structură Pas, i construire RB: 1. Alegere mult, ime variabile aleatoare care descriu problema 2. Alegere ordonare a acestor variabile (conform influent, ei cauzale) 3. Cât timp mai sunt variabile repetă: a Alegere variabilă Xi s, i adaugare nod corespunzător în RB b Atribuire parinti(Xi ) ← set minim de noduri deja existente în ret, ea, a.î. proprietatea de independent, ă condit, ională este satisfăcută c Definire tabelă de probabilităt, i condit, ionate pentru Xi Deoarece fiecare nod este legat numai la noduri anterioare → DAG Reprezentarea cunos, tint, elor incerte | 34 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Proprietăt, i O RB are o reprezentare structurată local – fiecare componentă a structurii interact, ionează cu un număr limitat de alte componente De exemplu, din n variabile aleatoare boolene ale unei RB, putem presupune că numărul maxim de părint, i al unei variabile este k ⇒ n × 2k numere necesare pentru a specifica o distribut, ie completă de probabilităt, i, în loc de 2n Exemplu: pentru n=30 s, i k=5, diferent, a este între 25 × 30 = 960 vs. 230 valori necesare În exemplul problemei cu alarma (variabile aleatoare boolene): În lipsa structurii de dependent, ă condit, ionată: P(H, C, A, M, P) are nevoie de o tabelă cu 25 = 32 intrări În RB dată P(H, C, A, M, P) = P(H) · P(C) · P(A|H, C) · P(M|A) · P(P|A) - 5 factori necesitând 1 + 1 + 4 + 2 + 2 = 10 valori specificate în tabelele de probabilităt, i condit, ionate Reprezentarea cunos, tint, elor incerte | 35 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Proprietăt, i Într-o RB, un nod A este condit, ional independent de non-descendent, i (e.g. N1 , N2 ), dat, i fiind părint, ii săi (P1 , P2 ) Reprezentarea cunos, tint, elor incerte | 36 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Proprietăt, i Pătura Markov Într-o RB, un nod A este condit, ional independent de orice alt nod din ret, ea, dat, i fiind: părint, ii săi (M1 , M2 ) copii săi (M5 , M6 , M7 ) părint, ii copiilor săi (M3, M4) Reprezentarea cunos, tint, elor incerte | 37 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Inferent, e O ret, ea Bayesiană descrie distribut, ia comună completă. Ca atare: n Y P(Q, setE, setU) = P(Xi |parinti(Xi )) i=1 unde: Q – variabilă interogată, setE – set de variabile probă, setU – set de variabile neobservate. Astfel, inferent, a pe caz general se exprimă ca: n 1 1 XY P(Q|setE) = P(Q ∧ setE) = P(Xi |parinti(Xi )) Z Z setU i=1 Reprezentarea cunos, tint, elor incerte | 38 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Inferent, e Calculam P(h|m, ¬p), unde Q = H, setE = {m, ¬p} s, i setU = {C, A} P(h, m, ¬p) P(h|m, ¬p) = P(m, ¬p) P P(h, m, ¬p, A, C) A,C = P P(m, ¬p, H, A, C) A,C,H P P(h) · P(C) · P(a|h, C) · P(m|A) · P(¬p|A) A,C = P P(H) · P(C) · P(a|H, C) · P(m|A) · P(¬p|A) A,C,H Reprezentarea cunos, tint, elor incerte | 39 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene : Inferent, e Data viitoare: Metodă automată de inferent, ă exactă Metode de inferent, ă aproximativă prin tehnici de es, antionare Reprezentarea cunos, tint, elor incerte | 40 / 40 Cunos, tint, e Incerte Teoria Probabilităt, ilor Ret, ele Bayesiene Mult, umesc! https://forms.gle/DJUdkejstkvyNRF5A Feedbackul este binevenit! Reprezentarea cunos, tint, elor incerte | 40 / 40