Dr. Jelasity Márk Mesterséges Intelligencia I. (I602, IB602) kurzus nyolcadik előadásának jegyzete (2008. október 20-ai)
Készítette: Bóna Bence BOBNAAT.SZE INF-MAT IV.
Bayes-Háló Ebben a részben egy szisztematikus módszert vezet be a feltételes függetlenségi kapcsolat reprezentálására, Bayes-háló fórmájában. Bayes-hálónak nevezett adatstruktúrát a változók közötti függőség leírásához, bármely együttes valószínűség – eloszlás függvény tömör megadásához. A Bayes-haló egy irányított gráf, amelyben minden csomóponthoz számszerű valószínűségi információk vannak csatolva. Részletesen: 1, A háló csomópontjait valószínűségi változók egy halmaza alkotja. A változók lehetnek diszkrétek vagy folytonosak. 2, Irányított élek (nyilak) egy halmaza összeköt bizonyos csomópontokat. Ha létezik nyíl az X csomóponttól az Y csomópontig (X → Y), azt mondjuk, hogy X szülője az Y-nak. 3, Minden Xi csomóponthoz tartozik egy P(Xi|Szülők(Xi)) feltételes valószínűségi eloszlás, ami számszerűen meghatározza a szülők hatását a csomóponti változóra. 4, A gráf nem tartalmaz irányított kört (azaz irányított, körmentes gráf – Directed Acyclic Graph, DAG). A háló topológiája – csomópontok és élek halmaza – meghatározza a feltételes függőségi kapcsolatokat. Egy jól felépített gráfban X csomópont össze van kötve Y-nal, és a nyíl intuitív jelentése az, hogy X-től függ Y -értéke. Bayes-haló topológiáját elkészítjük, már csak az egyes váltózók tartozó feltételes valószínűség-eloszlás kell meghatároznunk. Ezek segítségével egyértelműen megadja (implicit módon) az összes változó feletti együttes valószínűség-eloszlás függvényt. Most nézzünk egy példát a Bayes-hálóra.
Időjárás
Lyuk
Fogfájás
1. ábra Bayes-haló
Beakadás
Ebben a példában leírt változók a következők: Időjárás, Lyuk, Fogfájás, Beakadás. Az Időjárás független a többi változótól, továbbá a Fogfájás és a Beakadás feltételesen függetlenek a Lyuk ismeretében. Szemléletesen, a háló az a tényt fejezi ki, hogy a Lyuk közvetlen oka a Fogfájás-nak és a Beakadás-nak, továbbá közvetlen okozati kapcsolata azonban nem létezik a Fogfájás és a Beakadás között. Most egy új példát tekintünk meg. P(B) Betörés
P(F) Földrengés
0,001
Riasztás
JánosfTelef. R i h
R
F
P(R)
i i h h
i h i h
0,95 0,94 0,29 0,001
0,002
MáriaTelef.
P(J) 0,90 0,05
R i h
P(M) 0,70 0,01
2. ábra Bayes-háló A példánkban egy riasztót szemléltet. Otthonunkban egy új betörésjelzőt szereltek fel. Ez megbízhatóan észleli betörést, és időnként kisebb földrengéseket is jelzi. Két szomszédunk is van. János és Mária, akik ígérték, hogy mindig hívnak, ha meghallják a riasztó hangját. Tudnunk kell, hogy János mindig felhív, ha hallja, de előfordul az is, hogy összekeveri a telefon csörgésével a riasztó csöngését. Mária szereti hangosan hallgatni a zenét, ezért nem minden esetben hallja meg a riasztó hangját. Ezzel a Bayes-hálóval tudjuk szemléltetni, hogy mekkora a valószínűség annak, hogy betörés történt. A betörés háló esetén a topológia azt mutatja, hogy a betörés és a földrengés közvetlenül befolyásolja a riasztó megszólalásnak valószínűségét, ellenben János és Mária hívásának bekövetkezése csak magán a riasztón múlik. A valószínűségek valójában a lehetséges körülmények egy potenciálisan végtelen halmazát összegzik, amikor is a riasztó elmulaszt megszólalni, vagy János és Mária elmulaszt szólni. Az ábrán minden eloszlás, mint feltételes valószínűségi táblázat – FTV van feltüntetve. Az FTV – táblázatban minden sor az egyes csomóponti értékek feltételes valószínűségét tartalmazza az adott sorhoz tartozó szülői feltétel esetén. Az egyes sorokban szereplő számok összegének 1-et kell adnia, mivel az adott változó összes lehetséges értéke szerepel a bejegyzésben. Az igaz érték valószínűsége p, akkor a hamis érték valószínűsége 1-p. Az együttes valószínűség-eloszlás függvény leírása A Bayes-háló a tárgytartomány teljes leírását adja meg. A benne szereplő információk segítségével az együttes valószínűség-eloszlás függvény bármely bejegyzése kiszámítható. Egy együttes valószínűség-eloszlás függvény egy általános bejegyzése egy teljes hozzárendelés konjunkciójának a valószínűsége, P(X1 = x1 ∧ … ∧ Xn = xn). Amit a
továbbiakban csak P(x1,…,xn) jelöljük. Egy bejegyzés értékét a következő egyenlőtlenség adja meg: P(x1,…,xn) =
n
∏
P(xi|szülők(Xi)).
i=1
Így az együttes valószínűség-eloszlás függvényt leíró táblázat minden bejegyzése a Bayeshálóban szereplő, feltételes valószínűségi táblák megfelelő elemeinek a szorzata. Most nézzük meg mennyi annak a valószínűsége, hogy a riasztó megszólal, de nem volt sem betörés sem földrengés, azonban János és Mária is telefonál. A kezdőbetűk jelöli a változókat: P(j ∧ m ∧ a ∧ ¬ b ∧ ¬ e ) = P(j | a)P(m | a)P(a | ¬ b ∧ ¬ e)P( ¬ b)P( ¬ e) = 0,90 × 0,70 × 0,001 × 0,999 × 0,998 = 0,00062 Egy Bayes-háló konstruálása Elsőként írjuk fel az együttes valószínűség-eloszlás függvényt feltételes valószínűségek szorzataként, felhasználva a szorzatszabályt. P(x1, …, xn) = P(xn|xn-1,…, x1)P(xn-1, …, x1). Majd ismételten alkalmazzuk ezt a lépést. Végezetül egyetlen hosszú szorzatot kapunk: P(x1,…,xn) = P(xn|xn-1, … , x1)P(xn-1|xn-2, …, x1) … P(x2|x1)P(x1)
n
∏
P(xi|xi-1, …, x1)
i=1
Összehasonlítva ezt a 1. ábrával egyenlettel láthatjuk, hogy az együttes valószínűség – eloszlás függvény megadása ekvivalens azzal az állítással, hogy a háló minden Xi változójára P(Xi|Xi-1, …,X1) = P(Xi|Szülők(Xi)) feltéve, hogy Szülők(Xi) ⊆ {Xi-1, …, X1}. A Bayes-háló csak abban az esetben lehet helyes reprezentációja a tárgytartománynak, ha az adott szülők mellett, minden csomópont feltételesen független a csomópontot sorrendezésben őt megelőzőtől. Így a tárgytartomány struktúrájának megfelelő Bayes-háló Fontos megemlítünk, hogy függ a változók sorrendjétől: 1, más sorrendben lehet teljesen más topológia. 2, viszont bármely sorrendre kijön egy Bayes-háló ⇒ ok.- okozat nem tükröződik a Bayeshálóban.
Mária Telefoná
János Telefoná
Mária Telefoná
Riasztás
Földrengés
Riasztás
Betörés (a)
János Telefoná
Földrengés
Betörés (b)
Az (a) ábrában az ok-okozat megfordul, nehezen értelmezhető. A (b) ábrán ebben a sorrendben nincs tömörítés. Itt alkalmazható a teljes lánc szabály. De mindkét Bayes-háló ugyanazt a kódolja. Feltételes függetlenségi relációk a Bayes-hálókban Bayes-hálókra egy „numerikus” szemantikát adtunk meg a teljes együttes eloszlás reprezentációjának a szempontjából. Ezt a szemantikát alkalmazva a Bayes-hálók konstrukciós módszereinek a származtatásánál azt a következményt kaptunk, hogy egy csomópont feltételesen független az őt megelőzőktől, ha csomópont szőlői adottak. Más módon is eljárhatunk. Elindulhatunk egy „topológiai” szemantikától, ami a gráf által kódolt feltételes függetlenségi relációkat adja meg, és ezekből származtatjuk a „numerikus” szemantikát. 1, Egy csomópont feltételesen független a nem leszármazottaitól, feltéve, hogy a szülei adottak. Xj nem leszármazottja Xi-nek, akkor P(Xi|Szülök(Xi),Xj) = P(Xi|Szülők(Xi)). 2, Egy csomópont feltételesen független az össze többi csomóponttól a hálózatban, a szülei, gyermekei és gyermekei szüleinek az ismeretében – azaz a Markov-takarójának ismeretében. Ha Xj tetszőleges változó: P(Xi|Markov – takaró(Xi),Xj) = P(Xi|Markov – takaró(Xi)). Markov – takaró: Szülök ∪ Gyerekek ∪ Gyerekek szülei, tehát az Xi csak a Markov – takarótól függ. Feltételes eloszlások hatékony Reprezentációja A szülők maximális száma, k meglehetősen kicsi is, egy csomópont feltételes valószínűségi táblájának kitöltése akár O(2k) számú értéket és az összes lehetséges esetet figyelembe véve. Az egyik legrosszabb eset, amikor a kapcsolat a szülők és a gyermek között teljesen önkényes. Az ilyen eloszlásokat kanonikus eloszlásokkal írhatjuk le, ami valamilyen szabály mintát követ. A legnépszerűbb példa a determinisztikus csomópontok reprezentálják. Az értékeit a szüleinek az értéke teljesen meghatározza, mindenféle bizonytalanság nélkül. A reláció lehet egy logikai kapcsolat, vegyük például azt az esetet, amikor a szülőcsomópontok jelentése: Kanadai, Egyesült Államokbeli és Mexikói, a gyermekcsomópont pedig: Észak-Amerikai, akkor a kapcsolat a szülők diszjunkciója. Bizonytalan relációkat gyakran jellemezhetünk úgynevezett „zajos” logikai relációkkal. A zajos – vagy reláció a vagy reláció általánosítása. Ítéletlogikában kijelenthető, hogy a Láz akkor és csak akkor igaz, ha a Megfázás vagy az Influenza vagy a Malária igaz. Ez a modell megenged bizonytalanságot, hogy az egyes szülők okozhatják-e a gyermekek igaz értékét. A kapcsolat a szülő és a gyermek között gátolt lehet, így előfordulhat, hogy a páciens meg van fázva, de nem lázas. A modell két feltevésre épül. Elsőként feltételezhetjük, hogy az összes lehetséges ok fel van sorolva. Másodikként felteszi, hogy bármely szülő gátlása független a többi szülő gátlásától: például akármi is gátolja, hogy a Malária lázat okozzon, ez független attól, hogy mi gátolja az Influenzát, hogy lázat okozzon. Ezek a feltevésekkel a Láz akkor és csak akkor hamis, ha az összes igaz értékű szülő gátolt, aminek a valószínűsége a gátlás valószínűségek szorzata. A gátlási valószínűségek a következők: P( ¬ láz | megfázás, ¬ influenza, ¬ malária) = 0,6 P( ¬ láz | ¬ megfázás, influenza, ¬ malária) = 0,2 P( ¬ láz | ¬ megfázás, ¬ influenza, malária) = 0,1
Ennyi információból és a zajos-vagy feltevésből – a teljes FVT-t fel lehet építeni.
Megfázás
Influenza
Malária
P(Láz)
P( ¬ Láz)
H H H H I I I I
H H I I H H I I
H I H I H I H I
0,0 0,9 0,8 0,98 0,4 0,94 0,88 0,988
1,0 0,1 0,2 0,2 = 0,2 × 1,0 0,6 0,06 = 0,6 × 0,1 0,12 = 0,6 × 0,2 0,012=0,6 × 0,2 × 0,1
Általánosságban, a zajos logikai relációk, amelyekben egy változó k számú szülőtől függ. O(k) paraméterrel írhatók le, a teljes feltételes valószínűség-eloszlás táblázathoz tartozó O(2k) helyett. Ez sokkal könnyebbé teszi a becslést. Bayes-hálók folytonos változókkal. Definíció szerint, a folytonos változóknak végtelen számú értéke lehet, így lehetetlen feltételes valószínűségeket megadni minden egyes értékre. Egy lehetséges módszer a folytonos változók kezelésére, ha elkerüljük őket diszkretizálással – azaz felosztjuk a lehetséges értékeket intervallumok adott halmazára. Például, a hőmérsékletet felosztjuk (
100oC) intervallumokra. A diszkretizálás néha adekvát megoldás, de gyakran eredményezi a pontosság jelentős romlását. A másik megoldás, ha a valószínűség sűrűségfüggvény elemeiből választunk, amelyek véges számú paraméterrel megadható. Egy diszkrét és folytonos változókat is tartalmazó hálót hibrid Bayes-hálónak nevezzük. Egy hibrid háló megadásához két újfajta eloszlást kell megadnunk: feltételes eloszlást diszkrét változókhoz diszkrét és/vagy folytonos szülők esetén: továbbá feltételes eloszlás diszkrét változókhoz folytonos szülők esetén. Nézzük meg a következő példánkat: amelyben a vásárló valamilyen gyümölcsöt vásárol az ára függvényében, ami viszont a termés mennyiségétől függ és attól, hogy éppen van-e állami támogatás. Az Ár változó folytonos, a szülei pedig folytonosak és diszkrétek: a Vásárol változó diszkrét, és van egy folytonos szüleje. Az Ár változóhoz meg kell adnunk a P(Ár | Termés, Támogatás) eloszlás. A diszkrét szülők explicit felsorolással kezdjük – azaz megadjuk mind a P(Ár | Termés, támogatás), mind a P(Ár | Termés, ¬ támogatás) valószínűségeket. A termés kezeléséhez megadjuk, hogy a c ár feletti eloszlás hogyan függ a t Termés folytonos értékétől. Támogatás
Termés Ár
Vásárlás
A leggyakoribb választás a lineáris Gauss-eloszlás, amelyben a gyermek a Gauss-eloszlású, ahol a μ várható érték lineárisan változik a szülő értékével, és ahol δ szórás rögzített. Két eloszlásra van szükségünk, a támogatás és a ¬ támogatás esetére különböző paraméterekkel: P(Ár | Termés, Támogatás) = N(ait+bi, σ i2)(c) P(P | Termés, ¬ támogatás) = N (aht+bh, σ h2)(c) Ebben a példában ekkor, az Ár feltételes eloszlást a lineáris normális eloszlás kiválasztásával és a ai,bi, σ i,ah,bh és σ h paraméterekkel adhatjuk meg. A lineáris normális feltételes eloszlásnak vannak bizonyos speciális tulajdonságai. Ha diszkrét változók eloszlásával kezdünk foglakozni. Fontoljuk meg például a Vásárol csomópontot. Ésszerűnek tűnik azt feltételezni, hogy a vásárló vásárol, ha az ár alacsony, nem vásárol, ha magas, a vásárlás valószínűsége pedig folytonosan változik egy közbenső régióban. Máshogy fogalmazva, a feltételes eloszlás hasonló egy „elmosódott” küszöbfüggvényhez. Ekkor a Vásárlás valószínűsége az Ár ismeretében ez lehet: P(vásárlás|Ár = c) = φ ((-c+ μ )/ σ ) ami azt jelenti, hogy az ár küszöbszám μ körül van, és a küszöbrégió szélessége arányos δ -val, illetve, hogy a vásárlás valószínűsége csökken, ahogy az ár növekszik. Ezt a probit eloszlás azzal az érveléssel igazolható, hogy az alapul szolgáló döntési folyamatnál létezik egy pontos küszöb, de ennek pontos helyét egy véletlen normális eloszlású zaj befolyásolja. A probit modell egy alternatívája a logit eloszlás, amely a szigmoid függvényt használja egy elmosódott küszöb előállításához. 1 P(vásárlás|Ár = c) = −c + μ 1 + exp(−2 )
σ A két eloszlás hasonlóan néz ki, de valójában a logit helyzetekhez, de a logit eseteként matematikailag könnyebben kezelhető, például széles körben használatos. Következtetés felsorolással
Bármely feltételes valószínűség kiszámítható együttes eloszlás tagjainak összegzésével. Pontosabban P(X|e) lekérdezés megválaszolható, amit a jobb követhetőség kedvéért itt is megmutatjuk: P(X|e) = α P(X|e) = α
∑
P(X,e,y)
y
Továbbá, mint ismerjük a Bayes-háló a teljes együttes eloszlás egy teljes reprezentációja nyújtja. Az egyenlet azt mutatja, hogy az együttes eloszlás P(X,e,y) tagjai felírhatók a hálóból származó feltételes eloszlás szorzataként. A lekérdezés megválaszolható a Bayes-háló felhasználásával, kiszámítva a hálóból származó feltételes valószínűség szorzatainak összegeként. Vegyük a P(Betörés|JánosTelefonál = igaz, MáriaTelefonál = igaz) lekérdezést. A rejtett változók ennél a kérdésnél a Földrengés és a Riasztás. Az egyenletből ezt kapjuk P(B|j,m) = α P(Bj,m) = α ∑ ∑ P(B,e,a,j,m) e
a
A Bayes-háló szemantikája pedig FVT-bejegyzések felhasználásával egy kifejezést ad. P(b|j,m) = α ∑ ∑ P(b)P(e)P(a|b,e)P(j|a)P(m|a) e
a
Ennél a kifejezésnél a kiszámításához négy tagot kell összeadnunk, amelyek mind egyikét öt szám összeszorozásával kapjuk. Az algoritmus komplexitása egy n bináris változós háló esetén O(n2n). A következő egyszerű lépéssel javításhoz jutunk: a P(b) tag állandó és ki lehet venni az a és e feletti összegzések elé, a P(e) tag pedig kivihető az a feletti összegzés elé. P(b|j,m) = α P(b) ∑ P(e) ∑ P(a|b,e)P(j|a)P(m|a). e
a
Felhasználva a értékeket, azt kapjuk hogy P(b|m,j) = α × 0,00059224. A ¬ b-hez tartozó számítás átfutva az α × 0,0014919 eredményez. Így P(B|j,m) = α (0,00059224, 0,0014919) ≈ (0,284, 0,716). Azaz a betörés valószínűsége, ha mindkét szomszédja telefonál körülbelül 28%. Sajnos az algoritmus idő komplexitása egy n bináris változó O(n2n). A változó eliminációs algoritmus A felsoroló algoritmus lényegesen javítható ismétlődő számítások kiküszöbölésével. Az ötlet egyszerű: egyszerre végezzük el a számítást, és őrizzük meg az eredményeket későbbi számításokra. Egyfajta dinamikus programozás. Mi most a változó eliminációs algoritmust nézzük meg. A változó eliminálás az egyenlet típusú kifejezéseket jobbról balra sorrendben értékeli ki. A köztes eredményeket eltároljuk, és bármely változó feletti összegzés a kifejezésnek csak azon része felett történik meg, amely függ ettől a változótól. Értékeljük ki a következő kifejezést:P(B|j,m) = α P(B) ∑ P(e) ∑ P(a|b,e)P(j|a)P(m|a). e
a
Vegyük észre, hogy a kifejezés minden részét megjelöljük a kapcsolódó változó nevével, ezeket a tényezőket nevezzük. Egzakt következtetés komplexitása A betörés hálója a hálónak azon családjához tartozik, ahol a háló bármely két csomópontja között legfeljebb egyetlen irányítatlan út létezik. Ezeket egyszeresen összekötött hálónak vagy polifának nevezzük, amelyeknek van egy különösen kellemes tulajdonságuk, következtetés idő- és tárkomplexitása a polifánkban a háló méretében lineáris. Abban az esetben, ha minden egyes csomópontok szüleinek a száma egy konstanssal korlátozott, akkor a komplexitás a csomópontok számában is lineáris. Többszörösen összekötött hálóban a változó eliminálás legrosszabb esetben exponenciális idő- és tárkomplexitású lehet, még akkor is, ha a csomópontonként i szülők száma konstans. A Bayes-hálóban való következtetés NP-nehéz, mivel ez speciális alesetként tartalmazza az ítéletlogikai következtetést is. Csoportosító algoritmusok A változó eliminálás algoritmusa egyszerű és hatékony egyedi lekérdezések megválaszolására. A háló összes változójának az a posteriori eloszlást szeretnénk kiszámítani, akkor kevésbé hatékony. Például egy polifa hálóban O(n) egyenként O(n) költségű lekérdezést kell kiadni, összességben O(n2) időköltséggel. A csoportosítás alapötlete, hogy a háló önállóan csomópontjait egyesítjük, klasztercsomópontokat formálva úgy, hogy a kiadódó háló egy polifa legyen. Példa: egy Locsolócső+Eső-nek nevezett klasztercsomópontba való összevonása. A két bináris csomópontot egyetlen megacsomópont váltotta fel, aminek 4 értéke lehet: hh, hi, ih, ii. A megacsomópontnak csak egy szülője van. Gondos nyilvántartással ez az algoritmus képes O(n) időben – ahol n most a módosított háló mérete – kiszámolni a háló összes nem
bizonyíték csomópontjainak a posteriori eloszlását. Azonban a probléma NP-nehéz volta nem tűnt el: ha a háló exponenciális idő- és tárigényű a változó eliminálás esetén, akkor a csoportosított hálóhoz tartozó FVT-k megkonstruálása exponenciális idő- és tárigényű. P(F) = 0,5 Felhős F i h
P(l) 0,10 0,50
F i h Locsoló
L
E
P(E)
i i h h
i h i h
0,00 0,90 0,90 0,99
P(E) 0,20 0,80
Eső
Vizes Pázsit
Közelítő Következtetés Bayes-hálókban Az egzakt következtetés nagy, többszörösen összekötött hálókban való kezelhetetlensége miatt, érdemes átgondolni a módszereket. Ebben a részben a véletlen mintavételezés, Monte Carlo-módszerével ismerkedünk meg. A módszer pontossága a generált minták számától függ. A Monte Carlo algoritmus széles körben elterjedt olyan mennyiségek megbecslésére, amelyeket nehéz egzakt módon kiszámítani. Közvetlen mintavételezési módszerek Az alapelv minták generálása egy ismert valószínűség-eloszlásból. Példa: egy szabványos érme felfogható egy Érme valószínűségi változónak (fej, írás) értékekkel és P(Érme) = (0,5,0,5) a priori eloszlással. A mintavétel ebből az eloszlásból pontosan megfelel egy érme feldobásának: 0,5 valószínűséggel fej-et ad, és 0,5 valószínűsséggel írás-t. Rendelkezésre áll a [0,1] tartományba eső véletlen számoknak egy forrása, akkor bármely egyváltozós eloszlásból egyszerű dolgok mintavételezni. A véletlen mintavételezési folyamat legegyszerűbb fajtája a Bayes-hálók esetén a hálóból generál olyan eseményeket, amelyekhez nem kapcsolódik bizonyíték. Az ötlet az, hogy mintavételezzünk minden változót egymás után, topológiai sorrendben. 1. Soroljuk a P(Felhős) = (0,5, 0,5) eloszlásból; tegyük fel, hogy igaz-at kapunk. 2. Soroljuk a P(Locsoló|Felhős = igaz) = (0,1, 0,9) eloszlásból; tegyük fel, hogy hamis-at kapunk. 3. Soroljuk a P(Eső|Felhős = igaz) = (0,8, 0,2) eloszlásból; tegyük fel, hogy igaz-at kapunk. 4. Soroljuk a P(VizesPázsit|Locsoló = hamis, Felhős = igaz) = (0,9, 0,1) eloszlásból; tegyük fel, hogy igaz-at kapunk.
Ebben az esetben a PRIPR-MINTA a következő eseményt adja [igaz, hamis, igaz, igaz]. Bármilyen mintavételi algoritmusban a válasz kiszámítása a generálás során előálló minták megszámlálása alapján történik. Vegyük azt az esetet, hogy N teljes minták van, és jelölje N(x1,…,xn) az x1,…,xn esemény gyakoriságát. Azt várjuk, hogy ez a gyakoriság határértékben konvergáljon a várható értékéhez a mintavételi valószínűség szerint: Nps(x1,..,xn) = Sps(x1,…,xn) = P(x1,…,xn) lim N →∞ N Például gondoljuk meg az előbb generált eseményt: [igaz, hamis, igaz, igaz]. Ennek az eseménynek a mintavételi valószínűsége: Sps(igaz, hamis, igaz, igaz) = 0,5 × 0,9 × 0,8 × 0,9 = 0,324 Így, N nagy értékeinél azt várjuk, hogy a minták 32,4%-a ez az esemény legyen. Az ilyen becsléseket konzisztensnek nevezzük. Elutasító mintavételezés Bayes-hálóban Elutasító mintavételezés (rejection sampling) általános módszer minták előállítására egy nehezen mintavételező eloszlásból, felhasználva egy könnyen minta vételezhető eloszlást. Legegyszerűbb formájában feltételes valószínűségek kiszámítására –azaz P(X|e) meghatározására használják fel. Ebben a mintavételezésben először a háló által megadott priori eloszlásból generál mintákat, majd elutasítja azokat, amelyek nem illeszkednek a ∧
bizonyítékhoz. Végül, a P (X = x |e) becslés megkapható az X = x előfordulásinak ∧
megszámolásával a megmaradt mintában. Legyen most P (X |e) az algoritmus által kiadott becslés eloszlás. A definíciója szerint fennáll, hogy ∧ ∧ Nps(X,e) P ( X , e) P (X |e) = α Nps(X,e) = ebből kapjuk P (X |e) ≈ = P(X|e) Nps(e) P ( e) Azaz az elutasító mintavétel az igazi valószínűség konzisztens becslést adja. Az elutasító mintavételezés legnagyobb hibája, hogy nagyon sok mintát utasít el. Az e bizonyítékkal konzisztens minták aránya exponenciálisan egyre kevesebb, ahogy a bizonyítékváltozók száma nő, így az eljárás egyszerűen használhatatlan komplex problémákra. Vegyük észre, hogy az elutasító mintavétel nagyon hasonló a feltételes valószínűségek becsléséhez. Valószínűségi súlyozás A valószínűségi súlyozás elkerüli az elutasító mintavételezés gyengeségét azáltal, hogy csak e bizonyítékkal konzisztens eseményeket generál. A valószínűségi-súlyozás rögzíti az E bizonyítékváltozók értékeit, és csak a maradék X és Y változókat mintavételezi. Sajnos nem minden esemény egyenlő. Mielőtt megállapítanánk a számlálási eredményeket, minden eseményt súlyozunk azzal a valószínűséggel, amely megadja, hogy az esemény mennyire van összhangban a bizonyítékkal. Ezt, valószínűséget az egyes bizonyítékváltozók feltételes valószínűségeinek a szorzatával mérjük, a szülök ismeretében. A bizonyíték valószínűtlennek tűnik, kisebb súlyt kell adni. Alkalmazzuk az algoritmust, a háló esetén P(Eső|Locsoló = igaz, VizesPázsit = igaz) kérdésre. A folyamat a következő: először a w súly 1,0-ra állítjuk. Azután generálunk egy eseményt: 1. Soroljuk a P(Felhős) = (0,5, 0,5) eloszlásból; tegyük fel, hogy igaz-at kapunk. 2. A locsoló egy bizonyítékváltozó igaz értékkel. Ezért beállítjuk, hogy w ← w × P(Locsoló = igaz | Felhős = igaz) = 0,1 3. Soroljunk a P(Eső|Felhős = igaz) = (0,8, 0,2) eloszlásból; tegyük fel, hogy igaz-at kapunk.
4. A VizesPázsit egy bizonyítékváltozó igaz értékkel. Ezért beállítjuk, hogy w ← w × P(VizesPázsit = igaz | Locsoló = igaz, Eső = igaz) = 0,099 Itt a súlyozott-minta az [igaz,igaz,igaz,igaz] eseményt adja ki 0,099 súllyal, és ezt Eső = igaz esetnél vesszük számításba. A súly alacsony, mivel az esemény egy felhős napot ír le, amikor a valószínűtlen, hogy a locsoló be van kapcsolva. Mivel a valószínűségi súlyozás az összes generált mintát felhasználja, sokkal hatékonyabb lehet, mint az elutasító mintavétel. Azonban a teljesítmény leromlik, ha a bizonyítékváltozók száma növekszik. Ez azért történik, mert elég sok mintánál nagyon kicsi a súly. A probléma még erőt bizonyítékváltozók később fordulnak elő a változó sorrendben, mivel ekkor a minták olyan szimulációk, amelyek kevés hasonlóságot mutatnak a bizonyítékok által sugalmazott valósághoz. Következtetés a Markov-lánc szimulációval Ebben a részben a Markov-lánc Monte Carlo (MCMC, Markov Chain Monte Carlo) algoritmust ismertetjük, hogy Bayes-hálókban következtethessünk. Az MCMC algoritmus Az első két mintavételezési algoritmustól eltérően, amelyek az egyes eseményeket a semmiből generálják, az MCMC minden eseményt az azt megelőző esemény véletlen módosításával generál. Úgy lehet elképzelni ezt a hálót, mint aminek van konkrét jelenlegi állapota, ami minden változóra meghatároz egy változót. A következő állapot generálása egy Xi nem bizonyítékváltozóhoz tartozó érték véletlenszerű mintavételezésével történik, az Xi Markov-takarójába tartozó változók jelenlegi értékeinek feltétele mellett. Az MCMC így véletlen bolyongást végez az állapottérben, egyszerre csak egy változót billentve át, de rögzítetten tartva a bizonyítékváltozókat. Gondoljuk meg a P(Eső|Locsoló = igaz, VizesPázsit = igaz). A Locsoló és a VizesPázsit bizonyítékváltozók rögzítettek a megfigyelt értékeikre, míg a rejtett Felhős és Eső változók véletlenszerűen inicializáltak. Így a kezdeti állapot [igaz,igaz,hamis,igaz]. Ekkor a következő lépéseket hajtjuk végre ismétlődően: 1. A Felhős-t mintavételezzük a Markov-takarójába eső változók jelenlegi értékeinek ismeretében: ebben az esetben a P(Felhős|Locsoló = igaz, Eső = hamis) szerint mintavételezünk. Tegyük fel, hogy az eredmény Felhős = hamis. Ekkor az új állapot [hamis, igaz, hamis, igaz]. 2. Az Eső-t mintavételezzük a Markov-takarójába eső változók jelenlegi értékeinek ismeretében: ebben az esetben P(Eső|Felhős = hamis, Locsoló = igaz, VizesPázsit = igaz) szerint mintavételezünk. Tegyük fel, hogy ennek eredménye Eső = igaz. Ekkor az új állapot [hamis, igaz, igaz, igaz]. A folyamtat során meglátogatott minden egyes állapot egy olyan minta, ami hozzájárul az Eső célváltozó megbecsléséhez. Ha a folyamat 20 állapotot jár végig, ahol az Eső igaz, és 61 állapotot, ahol az Eső hamis, akkor a kérdésre a választ a NORMALIZÁL ( 〈 20,60 〉 ) = 〈 0.25, 0,75 〉 adja. Most nézzük meg, hogy a MCMC konzisztens becsléseket szolgáltat az a posteriori valószínűségekre. Az alapállapot egyszerű: a mintavételi folyamat egy olyan „dinamikus egyensúlyban” állapodik meg, amelyben az egyes állapotokban töltött idő hosszú távon számolt hányadosa pontosan az a posteriori valószínűséggel arányos. Ez a tulajdonság, a speciális átmenet valószínűség miatt áll fent, amely szerint a folyamat egyik állapotból a
másikba lép át, ahogyan ezt a feltételes eloszlást a mintavételezett változó Markov-takarója meghatározza. P(X | Markov-takaró (x)) kiszámítási módszere: Egy változó valószínűsége a Markov-takarójának ismeretében arányos a változó szüleivel vett feltételes valószínűségének és az egyes gyermekek azon szüleivel vett feltételes valószínűségeinek a szorzatával: P(X | Markov-takaró(x)): α P ( X | Szülők(x)) ×
∏
Y ∈Gyermekek ( X )
P(Y | Szülők(Y)).
Így egy változó átlépéséhez az x gyermekeinek számával megegyező számú szorzás szükséges. Legáltalánosabb formájában a MCMC hatékony módszer valószínűségi modellekkel való számolására, és számos változatát fejlesztették ki, közöttük a szimulált lehűtés algoritmust, a sztochasztikus kielégíthetőség algoritmust, és Metropolis-Hastings mintavételezőt.
