Bayesian Inference Lecture PDF

Inteligent, ă Artificială Inferent, ă în Ret, ele Bayesiene Credits: Alexandru Sorici CMU AI http://ai.berkeley.edu Inferent, ă în Ret, ele Bayesiene | 0 / 54  Ret, ele Bayesiene...

Inteligent, ă Artificială Inferent, ă în Ret, ele Bayesiene Credits: Alexandru Sorici CMU AI http://ai.berkeley.edu Inferent, ă în Ret, ele Bayesiene | 0 / 54  Ret, ele Bayesiene Independent, ă Enumerare Eliminare Inferent, ă în Ret, ele Bayesiene | 0 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Independent, ă condit, ională – Recapitulare 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) Inferent, ă în Ret, ele Bayesiene | 1 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Ret, ele Bayesiene Inferent, ă în Ret, ele Bayesiene | 2 / 54 Ret, ele Bayesiene : Definit, ii Independent, ă Enumerare Eliminare Aproximare 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 Inferent, ă în Ret, ele Bayesiene | 3 / 54 Ret, ele Bayesiene : Definit, ii Independent, ă Enumerare Eliminare Aproximare 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) Inferent, ă în Ret, ele Bayesiene | 4 / 54 Ret, ele Bayesiene : Definit, ii Independent, ă Enumerare Eliminare Aproximare Structură ret, ea Bayesiană P(H) P(C) 0.001 0.002 Pentru că variabilele aleatoare din Hot, exemplu sunt binare, tabela de Cutremur 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 F F 0.001 0.999 A P(M | A) A P(P | A) T 0.9 T 0.7 F 0.05 F 0.01 Inferent, ă în Ret, ele Bayesiene | 5 / 54 Ret, ele Bayesiene : Structură Independent, ă Enumerare Eliminare Aproximare 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 Inferent, ă în Ret, ele Bayesiene | 6 / 54 Ret, ele Bayesiene : Structură Independent, ă Enumerare Eliminare Aproximare Cum construim o ret, ea a.î. distribut, ia de probabilităt, i condit, ionate să fie o bună reprezentare a problemei / situat, iei modelate? Inferent, ă în Ret, ele Bayesiene | 7 / 54 Ret, ele Bayesiene : Structură Independent, ă Enumerare Eliminare Aproximare 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 Inferent, ă în Ret, ele Bayesiene | 7 / 54 Ret, ele Bayesiene : Structură Independent, ă Enumerare Eliminare Aproximare 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 } Inferent, ă în Ret, ele Bayesiene | 7 / 54 Ret, ele Bayesiene : Structură Independent, ă Enumerare Eliminare Aproximare Î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 Inferent, ă în Ret, ele Bayesiene | 8 / 54 Ret, ele Bayesiene : Structură Independent, ă Enumerare Eliminare Aproximare 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 Inferent, ă în Ret, ele Bayesiene | 9 / 54 Ret, ele Bayesiene : Proprietăt, i Independent, ă Enumerare Eliminare Aproximare 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 P(H) P(C) 0.001 0.002 În exemplul problemei cu alarma (variabile aleatoare boolene): Hot, Cutremur H C P(A | H, C) În lipsa structurii de dependent, ă condit, ionată: T T 0.95 T F 0.94 Alarma P(H, C, A, M, P) are nevoie de o tabelă cu 25 = 32 intrări F T 0.29 F F 0.001 TelMihai TelPompier Î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 A P(M | A) A P(P | A) necesitând 1 + 1 + 4 + 2 + 2 = 10 valori specificate în T 0.9 T 0.7 F 0.05 F 0.01 tabelele de probabilităt, i condit, ionate Inferent, ă în Ret, ele Bayesiene | 10 / 54 Ret, ele Bayesiene : Proprietăt, i Independent, ă Enumerare Eliminare Aproximare Î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 ) Inferent, ă în Ret, ele Bayesiene | 11 / 54 Ret, ele Bayesiene : Proprietăt, i Independent, ă Enumerare Eliminare Aproximare 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) Inferent, ă în Ret, ele Bayesiene | 12 / 54 Ret, ele Bayesiene : Inferent, e Independent, ă Enumerare Eliminare Aproximare 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 Inferent, ă în Ret, ele Bayesiene | 13 / 54 Ret, ele Bayesiene : Inferent, e Independent, ă Enumerare Eliminare Aproximare Calculam P(h|m, ¬p), unde Q = H, setE = {m, ¬p} s, i setU = {C, A} P(H) P(C) 0.001 0.002 P(h, m, ¬p) Hot, Cutremur P(h|m, ¬p) = H T C T P(A | H, C) 0.95 P(m, ¬p) P T F F T 0.94 0.29 Alarma P(h, m, ¬p, A, C) F F 0.001 A,C TelMihai TelPompier = P P(m, ¬p, H, A, C) A,C,H A P(M | A) A P(P | A) P T 0.9 T 0.7 P(h) · P(C) · P(a|h, C) · P(m|A) · P(¬p|A) F 0.05 F 0.01 A,C = P P(H) · P(C) · P(a|H, C) · P(m|A) · P(¬p|A) A,C,H Inferent, ă în Ret, ele Bayesiene | 14 / 54 Ret, ele Bayesiene Independent, ă Condit, ională Enumerare Eliminare Aproximare Independent, ă Condit, ională Inferent, ă în Ret, ele Bayesiene | 15 / 54 Ret, ele Bayesiene Independent, ă Condit, ională Enumerare Eliminare Aproximare Pe caz general: ce relat, ii de independent, ă condit, ională devin adevărate atunci când un subset din nodurile unei RB sunt cunoscute (observate)? D-separarea: concept ce denotă procedura de observare a unui set de noduri Z dintr-o RB, ce face ca alte mult, imi (X s, i Y ) să fie independente condit, ional una de alta, cunoscute fiind valorile nodurilor din Z X⊥Y|Z O relat, ie de independent, ă condit, ională într-o RB se poate verifica folosind structura grafului aciclic orientat al ret, elei Inferent, ă în Ret, ele Bayesiene | 16 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare O relat, ie de tipul X⊥Y|Z nu t, ine atunci când: Există o conexiune directă între un nod din X s, i un nod din Y Există un lant, / o cale între un nod din X s, i un nod din Y, care nu este "blocată" de noduri din Z Inferent, ă în Ret, ele Bayesiene | 17 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Analiză a conectivităt, ii a 3 noduri în graful unei RB X Z Y Winter Snow Ski Inferent, ă în Ret, ele Bayesiene | 18 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Analiză a conectivităt, ii a 3 noduri în graful unei RB X Z Y Winter Snow Ski Lant, cauzal X→Z→Y X nu influent, ează Y dacă Z observat Lant, de probe X←Z←Y Y nu influent, ează X dacă Z observat Inferent, ă în Ret, ele Bayesiene | 18 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Analiză a conectivităt, ii a 3 noduri în graful unei RB Z BI X Y DP TM Inferent, ă în Ret, ele Bayesiene | 19 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Analiză a conectivităt, ii a 3 noduri în graful unei RB Z BI X Y Cauză comună X←Z→Y DP TM X nu influent, ează Y dacă Z observat Inferent, ă în Ret, ele Bayesiene | 19 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Analiză a conectivităt, ii a 3 noduri în graful unei RB Z BI X Y Cauză comună X←Z→Y DP TM X nu influent, ează Y dacă Z observat X Y RM Job Z Fericit Inferent, ă în Ret, ele Bayesiene | 19 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Analiză a conectivităt, ii a 3 noduri în graful unei RB Z BI X Y Cauză comună X←Z→Y DP TM X nu influent, ează Y dacă Z observat X Y RM Job Z Efect comun X→Z←Y Fericit Y influent, ează X dacă Z observat Inferent, ă în Ret, ele Bayesiene | 19 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare D-separare: analiza căilor care "permit influent, ă probabilistică" între noduri din X s, i noduri din Y O cale între un nod din X s, i un nod din Y se numes, te blocată / inactivă dacă: Cont, ine o subcale A → B → C - lant, cauzal - unde B este observat (B ∈ Z ) Cont, ine o subcale A ← B ← C - lant, de probe - unde B este observat (B ∈ Z ) Cont, ine o subcale A ← B → C - cauză comună - unde B este observat (B ∈ Z ) Cont, ine o subcale A → B ← C - efect comun - unde B s, i nici unul dintre descendent, ii săi nu este observat (B ∈ / Z s, i N ∈ / Z , ∀N ∈ desc(B)) Dacă toate căile între noduri din X s, i noduri din Y sunt inactive ⇒ X⊥Y|Z Dacă cel put, in o cale între un nod din X s, i un nod din Y este activă ⇒ X ̸⊥ Y|Z Inferent, ă în Ret, ele Bayesiene | 20 / 54 Ret, ele Bayesiene Independent, ă Condit, ională : D-separare Enumerare Eliminare Aproximare Folosind ret, ele bayesiene, putem face inferent, e: Inferent, e exacte Inferent, e aproximative (prin es, antionare – sampling) Inferent, ă în Ret, ele Bayesiene | 21 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare Inferent, e Exacte – Metoda Enumerării Inferent, ă în Ret, ele Bayesiene | 22 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare Exemplul declas, ării alarmei: P(H) P(C) 0.001 0.002 Hot, Cutremur H C P(A | H, C) P(a|h) = ? T T 0.95 T F 0.94 Alarma F T 0.29 F F 0.001 TelMihai TelPompier A P(M | A) A P(P | A) T 0.9 T 0.7 F 0.05 F 0.01 Inferent, ă în Ret, ele Bayesiene | 23 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare Exemplul declas, ării alarmei: P(H) P(C) 0.001 0.002 Hot, Cutremur H C P(A | H, C) T T 0.95 P(a|h) = P(a|h, c) · P(c|h) + P(a|h, ¬c) · P(¬c|h) T F 0.94 Alarma F T 0.29 = P(a|h, c) · P(c) + P(a|h, ¬c) · P(¬c) F F 0.001 unde am utilizat faptul că H⊥C | ∅ TelMihai TelPompier A P(M | A) A P(P | A) T 0.9 T 0.7 F 0.05 F 0.01 Inferent, ă în Ret, ele Bayesiene | 23 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare Procedura de inferent, ă prin enumerare: 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 Exemplu: 1 P(h|m, p) = P(h, m, p) Z 1 X X = P(h) · P(C) · P(A|h, C) · P(m|A) · P(p|A) Z C∈{c,¬c} A∈{a,¬a} Inferent, ă în Ret, ele Bayesiene | 24 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare Analizând exemplul anterior, grupând s, i reordonând operat, iile, observăm: 1 XX P(h|m, p) = P(h) · P(C) · P(A|h, C) · P(m|A) · P(p|A) Z C A 1 X X = · P(h) P(m|A) · P(p|A) P(C) · P(A|h, C) Z A C 1 X X = · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) Z C A Inferent, ă în Ret, ele Bayesiene | 25 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare În procedura de inferent, ă prin enu- merare unele calcule sunt redun- dante. Exemplu pentru P(h|m, p) Inferent, ă în Ret, ele Bayesiene | 26 / 54 Ret, ele Bayesiene Independent, ă Inferent, e Exacte – Metoda Enumerării Eliminare Aproximare Procedura de inferent, ă prin enumerare: Pentru n variabile aleatoare boolene, complexitatea spat, ială este O(n), iar cea de timp O(2n ) Putem îmbunătăt, i situat, ia dacă eliminăm calcule redundante ret, inând rezultatele intermediare pe parcurs (ca factori în calcul) Inferent, ă în Ret, ele Bayesiene | 27 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare Inferent, e Exacte – Eliminarea Variabilelor Inferent, ă în Ret, ele Bayesiene | 28 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare Reluând exemplul pentru P(h|m, p) avem: 1 X X · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) Z | {z } | {z } | {z } | {z } | {z } C A fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] unde fH , fC , fA , fM , fP sunt factori. Idee: executăm calculele de la dreapta la stânga (sau de jos în sus în termenii arborelui de calcul) s, i memorăm rezultatele part, iale pe parcurs, reutilizându-le la nevoie. Inferent, ă în Ret, ele Bayesiene | 29 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare Factorii sunt init, ial asociat, i câte unul fiecărei variabile aleatoare (fiecărui nod) din RB. Un factor se reprezintă ca o tabelă indexată după toate combinat, iile posibile de valori ale variabilelor incluse în factor (init, ial cele din probabilitatea condit, ionată P(X |parinti(X ))) Exemplu fA [A, H, C], fP [P, A]: A H C fA [A, H, C] T T T P(a|h, c) = 0.95 T T F P(a|h, ¬c) = 0.94 P A fP [P, A] T F T P(a|¬h, c) = 0.29 T T P(p|a) = 0.7 T F F P(a|¬h, ¬c) = 0.001 T F P(p|¬a) = 0.01 F T T P(¬a|h, c) = 0.05 F T P(¬p|a) = 0.3 F T F P(¬a|h, ¬c) = 0.06 F F P(¬p|¬a) = 0.99 F F T P(¬a|¬h, c) = 0.71 F F F P(¬a|¬h, ¬c) = 0.999 Inferent, ă în Ret, ele Bayesiene | 30 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Inferent, ă în Ret, ele Bayesiene | 31 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Avem o RB cu 5 variabile H, C, A, M, P. Interogarea P(h|m, p) (în care M s, i P sunt variabile probă / observate) necesită "eliminarea" variabilelor A s, i C 1. Reducem factorii fM [M, A] s, i fP [P, A] doar la liniile unde M = T s, i P = T , conform observat, iilor Inferent, ă în Ret, ele Bayesiene | 31 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Avem o RB cu 5 variabile H, C, A, M, P. Interogarea P(h|m, p) (în care M s, i P sunt variabile probă / observate) necesită "eliminarea" variabilelor A s, i C 1. Reducem factorii fM [M, A] s, i fP [P, A] doar la liniile unde M = T s, i P = T , conform observat, iilor 2. Înmult, im tot, i factorii care cont, in pe A – fA [A, H, C], fM [M, A], fP [P, A] Inferent, ă în Ret, ele Bayesiene | 31 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Avem o RB cu 5 variabile H, C, A, M, P. Interogarea P(h|m, p) (în care M s, i P sunt variabile probă / observate) necesită "eliminarea" variabilelor A s, i C 1. Reducem factorii fM [M, A] s, i fP [P, A] doar la liniile unde M = T s, i P = T , conform observat, iilor 2. Înmult, im tot, i factorii care cont, in pe A – fA [A, H, C], fM [M, A], fP [P, A] 3. Eliminăm prin însumare variabila A (notăm cu A faptul că factorul este însumat peste A) X fAHC [M, P, H, C] = fA [A, H, C] · fM [M, A] · fP [P, A] A Până în acest moment interogarea se poate rescrie: 1 X P(h|m, p) = · P(h) P(C) f [M, P, H, C] Z | {z } C | {z } AHC fH [h] fC [C] Inferent, ă în Ret, ele Bayesiene | 31 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Până în acest moment interogarea este reprezentată ca: 1 X P(h|m, p) = · P(h) P(C) f [M, P, H, C] Z | {z } | {z } AHC C fH [h] fC [C] 4. Eliminăm C folosind fC [C] s, i fAHC [M, P, H, C] ⇒ P fAHC [H, M, P] = fC [C] · fAHC [M, P, H, C] C Inferent, ă în Ret, ele Bayesiene | 32 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Până în acest moment interogarea este reprezentată ca: 1 X P(h|m, p) = · P(h) P(C) f [M, P, H, C] Z | {z } | {z } AHC C fH [h] fC [C] 4. Eliminăm C folosind fC [C] s, i fAHC [M, P, H, C] ⇒ P fAHC [H, M, P] = fC [C] · fAHC [M, P, H, C] C 1 5. Obt, inem factorul final peste H, M, P s, i normalizăm: P(h|m, p) = Z fH [H] · fAHC [M, P, H] Inferent, ă în Ret, ele Bayesiene | 32 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] Până în acest moment interogarea este reprezentată ca: 1 X P(h|m, p) = · P(h) P(C) f [M, P, H, C] Z | {z } | {z } AHC C fH [h] fC [C] 4. Eliminăm C folosind fC [C] s, i fAHC [M, P, H, C] ⇒ P fAHC [H, M, P] = fC [C] · fAHC [M, P, H, C] C 1 5. Obt, inem factorul final peste H, M, P s, i normalizăm: P(h|m, p) = Z fH [H] · fAHC [M, P, H] 6. Citim rezultatul P(h|m, p) pe linia H = T , M = T , P = T Inferent, ă în Ret, ele Bayesiene | 32 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare 1 P P Eliminarea variabilelor P(h|m, p) = Z · P(h) P(C) P(A|C, h) · P(m|A) · P(p|A) | {z } C | {z } A | {z } | {z } | {z } fH [h] fC [C] fA [A,h,C] fM [M,A] fP [P,A] 1 Factorul final Z fH [H] · fAHC [M, P, H] este proport, ional cu probabilitatea comună a variabilei de interogare (query) s, i a variabilelor observate. H M P ffinal (h, m, p) 1 1 1 1 ∝ p(h, m, p) = ffinal 2 0 1 1 ∝ p(¬h, m, p) = ffinal Pentru a calcula probabilitatea cerută p(h|m, p) normalizăm tabela factorului ffinal s, i preluăm rezultatul de la linia h, m, p. Factorul final normalizat H M P p(H|m, p) 1 1 2 1 1 1 ffinal /(ffinal + ffinal ) 2 1 2 0 1 1 ffinal /(ffinal + ffinal ) Inferent, ă în Ret, ele Bayesiene | 33 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare Procedura eliminării variabilelor necesită existent, a a două operat, ii pe factori Înmult, irea a doi factori Eliminarea prin însumare (eng. sum out) a unei variabile Exemplu înmult, ire: fM [M, A] · fP [P, A] M A fM [M, A] P A fP [P, A] M A P fMAP [M, A, P] T T 0.9 T T 0.7 T T T 0.9 · 0.7 = 0.63 T F 0.05 T F 0.01 T T F 0.9 · 0.3 = 0.27 F T 0.1 F T 0.3 T F T 0.05 · 0.01 = 0.0005 F F 0.95 F F 0.99 T F F 0.05 · 0.99 = 0.0495 F T T 0.1 · 0.7 = 0.07 F T F 0.1 · 0.3 = 0.03 F F T 0.95 · 0.01 = 0.0095 F F F 0.95 · 0.99 = 0.9405 Inferent, ă în Ret, ele Bayesiene | 34 / 54 Ret, ele Bayesiene Independent, ă Enumerare Inferent, e Exacte – Eliminarea Variabilelor Aproximare Exemplu: însumarea peste A în fMAP [M, A, P] X fMAP [M, P] = fMAP [M, A, P] = fMAP (M, a, P) + fMAP (M, ¬a, P) A M A P fMAP [M, A, P] M P fMP [M, P] T T T 0.63 T T 0.63 + 0.0005 = 0.6305 T T F 0.27 T F 0.27 + 0.0495 = 0.3195 T F T 0.0005 F T 0.07 + 0.0095 = 0.0795 T F F 0.0495 F F 0.03 + 0.9405 = 0.9705 F T T 0.07 F T F 0.03 F F T 0.0095 F F F 0.9405 Inferent, ă în Ret, ele Bayesiene | 35 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Inferent, e de Aproximare Inferent, ă în Ret, ele Bayesiene | 36 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Motivat, ie: Inferent, ele exacte în RB pot fi foarte costisitoare - în cazul cel mai rău complexitatea este exponent, ială în numărul de noduri (chiar s, i cu eficientizarea dată de Eliminarea Variabilelor) RB pentru asigurare auto: [AIMA, Russel & Norvig] Inferent, ă în Ret, ele Bayesiene | 37 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Inferent, ă de aproximare - Es, antionare (Sampling) De ce să es, antionăm? Învăt, are: obt, inerea de es, antioane dintr-o distribut, ie necunoscută Inferent, ă: obt, inerea de es, antioane este mai rapidă decât calculul exact Inferent, ă în Ret, ele Bayesiene | 38 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Inferent, ă de aproximare - Es, antionare (Sampling) De ce să es, antionăm? Învăt, are: obt, inerea de es, antioane dintr-o distribut, ie necunoscută Inferent, ă: obt, inerea de es, antioane este mai rapidă decât calculul exact Ideea de bază: es, antionarea este ca simularea repetată Inferent, ă în Ret, ele Bayesiene | 38 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Inferent, ă de aproximare - Es, antionare (Sampling) De ce să es, antionăm? Învăt, are: obt, inerea de es, antioane dintr-o distribut, ie necunoscută Inferent, ă: obt, inerea de es, antioane este mai rapidă decât calculul exact Ideea de bază: es, antionarea este ca simularea repetată Extragem N es, antioane dintr-o distribut, ie S Inferent, ă în Ret, ele Bayesiene | 38 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Inferent, ă de aproximare - Es, antionare (Sampling) De ce să es, antionăm? Învăt, are: obt, inerea de es, antioane dintr-o distribut, ie necunoscută Inferent, ă: obt, inerea de es, antioane este mai rapidă decât calculul exact Ideea de bază: es, antionarea este ca simularea repetată Extragem N es, antioane dintr-o distribut, ie S Calculăm pe seama lor o probabilitate aposteriori aproximativă (P(Q|e)) Inferent, ă în Ret, ele Bayesiene | 38 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Inferent, ă de aproximare - Es, antionare (Sampling) De ce să es, antionăm? Învăt, are: obt, inerea de es, antioane dintr-o distribut, ie necunoscută Inferent, ă: obt, inerea de es, antioane este mai rapidă decât calculul exact Ideea de bază: es, antionarea este ca simularea repetată Extragem N es, antioane dintr-o distribut, ie S Calculăm pe seama lor o probabilitate aposteriori aproximativă (P(Q|e)) Arătăm că probabilitatea aproximată converge (sub limită de es, antionare infinită) către probabilitatea corectă Inferent, ă în Ret, ele Bayesiene | 38 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Es, antionarea după o distribut, ie dată 1. Extragem un număr u dintr-o distribut, ie uniformă peste [0, 1) 2. Convertim u la un rezultat C P(C) din distribut, ia t, intă, făcând ros, u 0.6 0 ≤ u < 0.6 → C = ros, u o asociere între fiecare verde 0.1 0.6 ≤ u < 0.7 → C = verde rezultat posibil s, i un albastru 0.3 0.7 ≤ u < 1 → C = albastru sub-interval din [0, 1) (fiecare sub-interval fiind proport, ional cu probabilitatea de alegere a acelui rezultat) Exemplu: pentru u = 0.81 culoarea extrasă: ? Inferent, ă în Ret, ele Bayesiene | 39 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Es, antionarea după o distribut, ie dată 1. Extragem un număr u dintr-o distribut, ie uniformă peste [0, 1) 2. Convertim u la un rezultat C P(C) din distribut, ia t, intă, făcând ros, u 0.6 0 ≤ u < 0.6 → C = ros, u o asociere între fiecare verde 0.1 0.6 ≤ u < 0.7 → C = verde rezultat posibil s, i un albastru 0.3 0.7 ≤ u < 1 → C = albastru sub-interval din [0, 1) (fiecare sub-interval fiind proport, ional cu probabilitatea de alegere a acelui rezultat) Exemplu: pentru u = 0.81 culoarea extrasă: albastru Inferent, ă în Ret, ele Bayesiene | 39 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Es, antionare directă (prior sampling) Es, antionare prin eliminarea es, antioanelor nedorite (rejection sampling) Es, antionare ponderată (likelihood sampling) Es, antionare Gibbs (Gibbs sampling) Inferent, ă în Ret, ele Bayesiene | 40 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă Se generează es, antioane dintr-o distribut, ie de probabilitate cunoscuta Cel mai simplu proces de es, antionare într-o RB: utilizat pentru a genera es, antioane/evenimente din ret, ea atunci când nu avem nicio probă Idee principală: es, antionăm fiecare variabilă aleatoare pe rând, în ordine topologică Distribut, ia de probabilitate din care se obt, in valorile unei variabile din es, antion este condit, ionată de valorile care au fost deja atribuite părint, ilor Inferent, ă în Ret, ele Bayesiene | 41 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.1 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, A P I P(I|A, P) T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.5 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, A P I P(I|A, P) T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.2 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, p, A P I P(I|A, P) T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.8 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, p, i A P I P(I|A, P) T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.7 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, p, i A P I P(I|A, P) ¬n, T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.3 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, p, i A P I P(I|A, P) ¬n, a, T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.9 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, p, i A P I P(I|A, P) ¬n, a, ¬p, T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Es, antionare directă N P(N) T 0.5 F 0.5 Nori N A P(A|N) N P P(P|N) T T 0.1 T T 0.8 T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 Număr aleator: 0.4 F F 0.1 F F 0.8 Iarba uda Es, antioane: n, ¬a, p, i A P I P(I|A, P) ¬n, a, ¬p, i T T T 0.99 T T F 0.01 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 42 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă Procedură de es, antionare directă: Intrări: RB cu n noduri Ies, ire: un es, antion din RB 1. xS ← − vector gol de lungime n 2. pentru fiecare variabilă Xi din {X1 , X2... , Xn }, ordonate topologic 3. xS [i] ← − un es, antion aleator luat din distribut, ia P(Xi |parinti(Xi )) 4. întoarce xS Procedura generează es, antioane cu probabilitatea Q SPS = P(Xi |parinti(Xi )) = P(X1 , X2 ,... , Xn ) i=1,n Dacă notăm prin NPS (x1 , x2 ,... , xn ) numărul de ori în care a fost es, antionat evenimentul (x1 , x2 ,... , xn ), atunci este adevărat că: NPS (x1 , x2 ,... , xn ) lim P̂(x1 , x2 ,... , xn ) = lim n→∞ n→∞ n = SPS (x1 , x2 ,... , xn ) = P(x1 , x2 ,... , xn ) Inferent, ă în Ret, ele Bayesiene | 43 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare directă De exemplu, dacă obt, inem es, antioanele: n, ¬a, p, i n, a, p, i ¬n, a, p, ¬i n, ¬a, p, i ¬n, ¬a, ¬p, i Dacă vrem să aflăm p(i) – abordare frecventistă: Numărăm i : 4, ¬i : 1 Normalizăm s, i obt, inem P(i) = 0.8, P(¬i) = 0.2 Cu cât avem mai multe es, antioane, cu atât mai apropiată va fi estimarea Putem estima orice interogare probabilistică: e.g. P(n|i), P(n|¬a, i)...... dar, pentru probabilităt, i condit, ionate (e.g. P(n|i)) generăm s, i multe es, antioane care nu corespund probelor observate Inferent, ă în Ret, ele Bayesiene | 44 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Rejection Sampling Motivat, ie: Dacă se dores, te estimarea probabilităt, ii P(n), nu are sens să păstrăm s, i es, antioane care ar cont, ine ¬n. Ajunge să contorizăm aparit, ii ale lui N = adev în es, antioane Similar s, i pentru o probabilitate condit, ionată (e.g. P(n|a)), putem rejecta es, antioane care nu au A = adev Contorizăm aparit, ii de N = adev , dar rejectăm es, antioanele în care A = fals Inferent, ă în Ret, ele Bayesiene | 45 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Rejection Sampling Generare es, antion prin eliminarea es, antioanelor nedorite Intrări: RB cu n noduri, set variabile probă e Ies, ire: un es, antion din RB 1. xS ← vector gol de lungime n 2. pentru fiecare variabilă Xi din {X1 , X2... , Xn }, ordonate topologic 3. xS [i] ← − un es, antion aleator luat din distribut, ia P(Xi |parinti(Xi )) 4. dacă xS [i] nu e consistentă cu probele e 5. atunci întoarce ⊥ (i.e. nu se generează un es, antion) 6. întoarce xS Inferent, ă în Ret, ele Bayesiene | 46 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare ponderată Motivat, ie: Problemă în procedura de eliminare a es, antioanelor nedorite: dacă probele sunt put, in probabile rejectăm multe es, antioane Nu ne folosim suficient de valorile variabilelor probă Exemplu: dacă ne-ar interesa să calculăm P(Forma|albastru) din următoarea ret, ea: Idee: fixăm probele s, i es, antionăm doar restul Problemă: distribut, ia es, antioanelor nu mai e consecventă Solut, ie: ponderăm es, antionul după probabilitatea condit, ionată a variabilelor probă, dat, i fiind părint, ii Inferent, ă în Ret, ele Bayesiene | 47 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare ponderată Exemplu "de mână" în problema Ierbii ude N P(N) N 0.5 ¬N 0.5 Nori N A P(A | N) N P P(P | N) T T 0.1 T T 0.8 Presupunem A = adev s, i I = adev T F 0.9 Aspersor Ploaie T F 0.2 F T 0.9 F T 0.2 observate F F 0.1 F F 0.8 Iarba uda Es, antionul n, a, p, i are pondere w = 1 · P(a|n) · P(i|a, p) = 1 · 0.1 · 0.99 A T P T I T P(I | A, P) 0.99 Es, antionul ¬n, a, ¬p, i are pondere T T F 0.01 w = 1 · P(a|¬n) · P(i|a, ¬p) = 1 · 0.9 · 0.99 T F T 0.90 T F F 0.10 F T T 0.90 F T F 0.10 F F T 0.01 F F F 0.99 Inferent, ă în Ret, ele Bayesiene | 48 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare ponderată Es, antionare ponderată Intrări: RB – Ret, eaua Bayesiană; probe – mult, imea de variabile probă cunoscute; n – numărul de noduri din RB Ies, ire: Tuplu: Un es, antion din RB, pondere w 1. w← − 1.0 2. xS ← − vector gol de lungime n 3. pentru fiecare variabilă Xi din {X1 , X2... , Xn }, ordonate topologic 4. dacă Xi este variabilă cu valoare în probe 5. xS [i] ← − xi , valoarea observată pentru Xi 6. w← − w · P(xi |parinti(Xi )) 7. altfel 8. Es, antionează xi din P(Xi |parinti(Xi )) 9. xS [i] ← − xi 10. întoarce xS , w Inferent, ă în Ret, ele Bayesiene | 49 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare ponderată Es, antionarea ponderată ajută să t, inem cont de probe atunci când generăm es, antioane ⇒ eficientizarea es, antionării Problemă: Probele influent, ează (restrict, ionează) îndeosebi variabilele lor descendente. Cele părinte nu se selectează conform cu probabilitatea de a genera probele Cerint, ă: a t, ine cont de variabilele probă când es, antionăm oricare altă variabilă Inferent, ă în Ret, ele Bayesiene | 50 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs Es, antionare Gibbs – parte din familia procedurilor Markov Chain Monte Carlo (de fapt, o particularizare a procedurii Metropolis-Hastings) Idee: Es, antionăm câte o variabilă pe rând, condit, ionând în raport cu toate celelalte, iar variabilele probă rămân fixate Es, antioanele nou generate nu mai sunt independente (vor fi aproape identice), dar media es, antioanelor reprezintă o estimare consecventă Inferent, ă în Ret, ele Bayesiene | 51 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs N A P I 1. Fixare probă: P = adev Inferent, ă în Ret, ele Bayesiene | 52 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs N N A P → − A P I I 1. Fixare probă: P = adev 2. Es, antion init, ial aleator → − {¬a, n, ¬i} 3. stabiles, te secvent, ă variabile non-probă {A, N, I} Inferent, ă în Ret, ele Bayesiene | 52 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs N N N A P → − A P → − A P I I I 1. Fixare probă: P = adev 2. Es, antion init, ial aleator → − {¬a, n, ¬i} 3. stabiles, te secvent, ă variabile non-probă {A, N, I} 4. repetă: 5. alege variabilă X din secvent, ă alege A 6. Es, antionează X din P(X |restul) es, antion a după n, p, ¬i ⇒ este adevărat Inferent, ă în Ret, ele Bayesiene | 52 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs N N N N A P → − A P → − A P → − A P I I I I 1. Fixare probă: P = adev 2. Es, antion init, ial aleator → − {¬a, n, ¬i} 3. stabiles, te secvent, ă variabile non-probă {A, N, I} 4. repetă: 5. alege variabilă X din secvent, ă alege N 6. Es, antionează X din P(X |restul) es, antion n după a, p, ¬i ⇒ este adevărat Inferent, ă în Ret, ele Bayesiene | 52 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs N N N N N A P → − A P → − A P → − A P → − A P I I I I I 1. Fixare probă: P = adev 2. Es, antion init, ial aleator → − {¬a, n, ¬i} 3. stabiles, te secvent, ă variabile non-probă {A, N, I} 4. repetă: 5. alege variabilă X din secvent, ă alege I 6. Es, antionează X din P(X |restul) es, antion i după n, a, p ⇒ este fals Inferent, ă în Ret, ele Bayesiene | 52 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs N N N N N A P → − A P → − A P → − A P → − A P → −... I I I I I 1. Fixare probă: P = adev 2. Es, antion init, ial aleator → − {¬a, n, ¬i} 3. stabiles, te secvent, ă variabile non-probă {A, N, I} 4. repetă: 5. alege variabilă X din secvent, ă 6. Es, antionează X din P(X |restul) Inferent, ă în Ret, ele Bayesiene | 52 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Es, antionare Gibbs Es, antionare Gibbs: es, antionarea unei variabile P(A|N, P, ¬I) p(a, n, p, ¬i) p(a|n, p, ¬i) = p(n, p, ¬i) p(a, n, p, ¬i) = P p(A, n, p, ¬i) A p(n) · p(a|n) · p(p|n) · p(¬i|a, p) = P p(n) · p(A|n) · p(p|n) · p(¬i|A, p) A p(n) · p(a|n) · p(p|n) · p(¬i|a, p) = P p(n) · p(p|n) · p(A|n) · p(¬i|A, p) A p(a|n) · p(¬i|a, p) = P p(A|n) · p(¬i|A, p) A Observat, ie: doar tabelele de probabilitate condit, ionate ce implică A rămân Pe caz general, doar tabelele de probabilitate condit, ionate ce implică variabila re-es, antionată trebuie luate în considerare s, i reunite (ca factori) Inferent, ă în Ret, ele Bayesiene | 53 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare : Sumar Sumar tehnici de es, antionare: Es, antionare directă (prior sampling): Utilă atunci când dorim estimarea unei probabilităt, i necondit, ionate: P(Q) simplă, dar ineficientă în caz că dorim estimarea unei probabilităt, i condit, ionate (generează multe es, antioane neutilizate) Es, antionare cu eliminarea es, antioanelor nedorite: Poate fi folosită pentru estimarea de probabilităt, i condit, ionoate (unde o parte din variabile sunt probe – P(Q|e)) Mai eficientă decât es , antionarea directă Es, antionare ponderată: Poate fi folosită pentru estimarea de probabilităt, i condit, ionoate (unde o parte din variabile sunt probe – P(Q|e)) Mai eficientă decât procedurile anterioare, dar probele condit, ionează doar generarea descendent, ilor Es, antionare Gibbs: Poate fi folosită pentru estimarea de probabilităt, i condit, ionoate (unde o parte din variabile sunt probe – P(Q|e)) Mai eficientă decât procedurile anterioare: probele afectează es , antionarea atât a variabilelor descendente, cât s, i părinte Inferent, ă în Ret, ele Bayesiene | 54 / 54 Ret, ele Bayesiene Independent, ă Enumerare Eliminare Aproximare Mult, umesc! https://forms.gle/DJUdkejstkvyNRF5A Feedbackul este binevenit! Inferent, ă în Ret, ele Bayesiene | 54 / 54