14.8. Összefoglalás

Ez a fejezet a Bayes-hálókat (Bayesian networks) mutatta be, amelyek egy jól kidolgozott reprezentációt jelentenek a bizonytalan tudás számára. A Bayes-hálók nagyjából hasonló szerepet töltenek be, mint amit az ítéletlogika a biztos tudás számára.

  • A Bayes-háló egy irányított körmentes gráf, aminek csomópontjai valószínűségi változókhoz tartoznak; minden csomóponthoz tartozik egy feltételes eloszlás, ahol a feltételt a csomópont szülei jelentik.

  • A Bayes-hálók tömör módot adnak a tárgyterület feltételes függetlenségi (conditional independence) kapcsolatainak a reprezentálására.

  • Egy Bayes-háló egy teljes együttes eloszlást specifikál; egy együttes bejegyzést a megfelelő lokális feltételes eloszlásokbeli bejegyzések szorzata határoz meg. Egy Bayes-háló gyakran exponenciálisan kisebb méretű, mint a teljes együttes eloszlás.

  • Számos feltételes eloszlást lehet tömören reprezentálni eloszlások kanonikus családjaival. A hibrid Bayes-hálók (hybrid Bayesian networks), amelyek mind diszkrét, mind folytonos változókat tartalmaznak, sokféle kanonikus eloszlást használnak.

  • A következtetés Bayes-hálókban a célváltozók egy halmaza valószínűség-eloszlásának kiszámítását jelenti, feltéve a tényváltozók egy halmazát. Az egzakt következtetési algoritmusok, mint a változó eliminálás (variable elimination) feltételes valószínűségek szorzatainak összegét értékelik, amilyen hatékonyan csak lehet.

  • Polifákban (polytrees) (egyszeresen összekötött hálókban) az egzakt következtetés számítási ideje a háló méretével lineárisan nő. Általános esetben a probléma kezelhetetlen.

  • Sztochasztikus közelítő számítási technikák, mint a valószínűségi súlyozás (likelihood weighting) és a Markov lánc Monte Carlo (Markov chain Monte Carlo) módszerek elfogadható becsléseket adnak a hálóbeli valódi a posteriori valószínűségekre, és sokkal nagyobb hálókkal is megbirkóznak, mint az egzakt algoritmusok.

  • A valószínűség-számítás kombinálható az elsőrendű logikából vett reprezentációs ötletekkel, hogy nagyon hatékony rendszereket hozzunk létre bizonytalanság esetén történő következtetéshez. A relációs valószínűségi modellek (RVM-ek) eleget tesznek olyan reprezentációs megkötéseknek, amelyek egy olyan jól definiált valószínűség eloszlást garantálnak, amely egy ekvivalens Bayes-hálóval kifejezhető.

  • Számos egyéb rendszert is javasoltak a bizonytalanság esetén történő következtetéshez. Nagy általánosságban azt lehet mondani, hogy az igazságfüggvényen (truth-functional) alapuló rendszerek az ilyen érveléshez nem a legmegfelelőbb eszközök.

14.8.1. Irodalmi és történeti megjegyzések

A hálók felhasználása valószínűségi információk reprezentálására Sewall Wright munkájával kezdődött el a 20. század elején a genetikai öröklődés analízisével és az állatok növekedési tényezőivel kapcsolatban (Wright, 1921; 1934). Az ő hálóinak egyike látszik ennek a könyvnek a borítóján. I. J. Good, Alan Turinggal együttműködve, olyan valószínűségi reprezentációkat és Bayes következtetési módszereket fejlesztett ki, amelyeket a modern Bayes-hálók előfutárának lehet tekinteni – bár a cikkre nem hivatkoznak gyakran ebben a kontextusban (Good, 1961).[155] Ugyanez a cikk az eredeti forrása a zajos-VAGY modellnek.

A döntési problémák hatásdiagram (influence diagram) reprezentációját – ami a valószínűségi változók reprezentációjához egy irányított körmentes gráfot tartalmazott – döntéselemzések során használták az 1970-es évek vége felé (lásd 16. fejezet), de a kiértékelésre csak felsorolást használtak. Judea Pearl fejlesztette ki az üzenetváltó eljárást, a fa hálókban (Pearl, 1982a) és az egyszeresen összekötött (polifa) hálókban (Kim és Pearl, 1983) történő következtetésre, és szemben az akkor népszerű bizonyossági tényezős rendszerekkel, a diagnosztikai helyett a kazuális valószínűségi modellek létrehozásának fontossága mellett érvelt. Az első szakértői rendszer, ami Bayes-hálókat használt, a CONVINCE volt (Kim, 1983; Kim és Pearl, 1987). A későbbi rendszerek között találjuk a mozgatóidegekkel kapcsolatos rendellenességek diagnosztizálására szolgáló MUNIN (Andersen és társai, 1989) és a patológiás helyzetek felderítésére szolgáló PATHFINDER rendszert (Heckerman, 1991). Messze a legtöbbet használt Bayes-hálós rendszerek a Microsoft Windows diagnóziskijavítás moduljai (például a Nyomtató varázsló) (Breese és Heckerman, 1996) és az Office segéd a Microsoft Office-ban (Horvitz és társai, 1998).

Általános Bayes-hálókban történő egzakt következtetésre Pearl fejlesztett ki egy csoportosításon alapuló algoritmust, felhasználva egy konverziót változók csoportjai feletti irányított polifába, amelyben üzenetváltások biztosítják a csoportok közös változói feletti konzisztenciát. Egy hasonló módszer, amit David Spiegelhalter és Steffen Lauritzen fejlesztett ki (Spiegelhalter, 1986; Lauritzen és Spiegelhalter, 1988), egy irányítatlan Markov-hálóba vivő konverzión alapul. Az eljárást a HUGIN rendszerben valósították meg, ami egy hatékony és széles körben használt eszköz a bizonytalansági következtetések esetén (Andersen és társai, 1989). Ross Shachter, a hatásdiagramok kutatói közösségéből, egy egzakt módszert fejlesztett ki, ami a háló célirányos csökkentésén alapul a posteriori megőrző átalakításokat felhasználva.

A fejezetben leírt változó eliminációs módszer Shachter módszeréhez áll legközelebb, amiből a szimbolikus valószínűségi következtetés (SzVK) módszere alakult ki (Shachter, 1990). Az SzVK megkísérli optimalizálni az olyan kifejezési fák kiértékelését, mint amilyen a 14.8. ábrán látható. Az általunk ismertetett algoritmus a Zhang és Poole által kifejlesztetthez áll a legközelebb (Zhang és Poole, 1994; 1996). Irreleváns változók eltávolítására szolgáló kritériumokat Geiger és társai, illetve Lauritzen és társai fejlesztettek ki (Geiger és társai, 1990; Lauritzen és társai, 1990); az általunk megadott kritérium ezeknek egy egyszerű speciális esete. Rina Dechter (Dechter, 1999) mutatta meg, hogy a változó eliminálás ötlete lényegében megegyezik a nem folytatólagos dinamikus programozással (nonserial dynamic programming) (Bertele és Brioschi, 1972). Ez egy algoritmikus megközelítés, amit Bayes-hálókban előálló következtetési problémák széles körére lehet sikerrel alkalmazni. Ilyen probléma például megfigyelések egy adott halmazához a legvalószínűbb magyarázat megkeresése. Ez összekapcsolja a Bayes-hálós algoritmusokat a kényszerkielégítési problémákat megoldó kapcsolódó módszerekkel, és közvetlen módszereket szolgáltat az egzakt következtetés komplexitására a háló hiperfájának a szélessége alapján.

Folytonos valószínűségi változók jelenlétét Bayes-hálókban Pearl, illetve Shachter és Kenley vizsgálta (Pearl, 1988; Shachter és Kenley, 1989); ezek a cikkek kizárólag folytonos változókat tartalmazó hálókat tárgyaltak, amelyek lokális függési modelljei lineáris normális eloszlásúak. Diszkrét változók bevezetését Lauritzen és Wermuth vizsgálta (Lauritzen és Wermuth, 1989), amit a cHUGIN rendszerben meg is valósítottak (Olesen, 1993). A probit eloszlást először Finney vizsgálta (Finney, 1947), szigmoid eloszlásnak nevezve. Az eloszlást széles körben használják diszkrét választási jelenségek modellezésére, és kiterjeszthető több mint két választási lehetőség kezelésére (Daganzo, 1979). A logit eloszlás használatához Bishop ad indoklást (Bishop, 1995).

Cooper mutatta meg, hogy a következtetés általános problémája tetszőleges Bayes-hálóban NP-teljes (Cooper, 1990), Paule Dagum és Mike Luby pedig azt, hogy ennek a közelítő megoldása is NP-teljes (Dagum és Luby, 1993). A tárkomplexitás szintén komoly probléma mind a csoportosító, mind a változó eliminációs módszereknél. A vágóhalmaz feltételezéseken (cutset conditioning) alapuló eljárás, amit a kényszerkielégítési problémákra az 5. fejezetben mutattunk be, elkerüli az exponenciális méretű táblák létrehozását. Egy Bayes-hálóban a vágóhalmaz a csomópontok azon halmaza, amelyek értékeinek rögzítése esetén a fennmaradó csomópontok függései egy fagráfra egyszerűsödnek, ami már lineáris időben és térben megoldható. A lekérdezést összegzéssel adhatjuk meg a vágóhalmaz minden lehetséges értékadása mellett, így az összes tárigény még mindig lineáris (Pearl, 1988). Darwiche (Darwiche, 2001) egy rekurzívan feltételező algoritmust ad meg, ami tetszőleges tár/idő egyensúlyt tesz lehetővé.

Gyors közelítő algoritmusok Bayes-hálókra való kifejlesztése nagyon aktív terület, a statisztika, a számításelmélet és a fizika határterületén. Az elutasító mintavételezés módszere egy általános, a statisztikában régóta ismert technika; Bayes-hálóknál Max Henrion alkalmazta először, aki logikai mintavételezésnek (logic sampling) nevezte (Henrion, 1988). A valószínűségi súlyozás, amit Fung és Chang (Fung és Chang, 1989), illetve Shachter és Peot fejlesztettek ki (Shachter és Peot, 1989), egy példája a fontossági mintavétel (importance sampling) jól ismert statisztikai módszerének. A valószínűségi súlyozás nagymérvű felhasználását az orvosi diagnosztikában Shwe és Cooper jelenti (Shwe és Cooper, 1991). Cheng és Druzdzel a valószínűségi súlyozás adaptív verzióját közlik (Cheng és Druzdzel, 2000), ami akkor is jól működik, ha a bizonyíték a priori valószínűsége nagyon alacsony.

A Markov lánc Monte Carlo (MCMC) módszerek a Metropolis algoritmussal kezdődtek, ami Metropolisnak köszönhető (Metropolis és társai, 1953), ami a 4. fejezetben leírt szimulált lehűtés algoritmusának szintén a forrása. A Gibbs-mintavételezőt Geman és Geman fejlesztette ki irányítatlan Markov-hálókban történő következtetésre (Geman és Geman, 1984). Az MCMC Bayes-hálókban történő alkalmazása Pearlnek köszönhető (Pearl, 1987). A Gilks és társai által összegyűjtött cikkek MCMC-alkalmazások széles skáláját ölelik fel, számos közülük a jól ismert BUGS csomaggal lett kifejlesztve (Gilks és társai, 1996).

A közelítési módszereknek két nagyon fontos családja létezik, amelyeket nem tárgyaltunk a fejezetben. Az első család a variációs közelítés (variational approximation) módszere, ami mindenfajta komplex számítás egyszerűsítésére felhasználható. Az alapötlet az, hogy az eredeti problémának előállítjuk egy olyan redukált verzióját, ami annyira egyszerű, hogy dolgozni lehessen vele, de amennyire lehet hasonló az eredeti problémához. A redukált probléma leírása tartalmazza a λ variációs paramétereket (variational parameters), amelyeket úgy állítunk be, hogy minimalizáljon egy D távolságfüggvényt az eredeti és a redukált problémák között, gyakran a ∂D/∂λ = 0 egyenletrendszer megoldásával. Számos esetben pontos felső és alsó korlátok kaphatók. Variációs módszereket régóta használnak a statisztikában (Rustagi, 1976). A statisztikus fizikában a mezőátlag (mean field) módszer egy speciális variációs módszer, amelyben a modellt alkotó egyes változókat teljesen függetlennek tételezzük fel. Ezt az ötletet felhasználva sikerült kezelni nagy irányítatlan Markov-hálókat (Peterson és Anderson, 1987; Parisi, 1988). A variációs módszerek Bayes-hálókra történő alkalmazásának matematikai megalapozását Saul és társai fejlesztették ki, és ők kaptak a szigmoid hálókra pontos alsó korlát közelítéseket a mezőátlag módszerrel (Saul és társai, 1996). Jaakkola és Jordan úgy terjesztették ki a módszert (Jaakkola és Jordan, 1996), hogy mind az alsó, mind a felső korlát kinyerhető legyen. A variációs módszereket Jordan tekintette át (Jordan, 1999).

A közelítő algoritmusok második családja Pearl fagráfon futó üzenetváltásos algoritmusán alapszik (Pearl, 1982a). Az algoritmust általános hálókra is lehet alkalmazni, ahogy Pearl javasolta (Pearl, 1988). Az eredmények lehetnek helytelenek, és lehet, hogy az algoritmus nem áll le, de számos esetben a szolgáltatott értékek közel vannak a helyes értékekhez. Ez az úgynevezett bizonyosságterjesztéses (belief propagation) vagy hurkos terjesztéses (loopy propagation) megközelítés kevés figyelmet kapott, mindaddig, amíg McEliece és társai fel nem figyeltek (McEliece és társai, 1998) arra, hogy az üzenetváltás többszörösen összekötött Bayes-hálókban pontosan megegyezik a turbó dekódolás (turbo decoding) algoritmus által végzett számítással (Berrou és társai, 1993), ami jelentős áttörést eredményezett a hibajavító kódok tervezésében. Ebből az a következtetés vonható le, hogy a bizonyosságterjesztés gyors is és pontos is a nagyon nagy méretű és nagyon sűrűn összekötött dekódolásra használt hálókban, és ezért lehet, hogy általánosabban is hasznos lehet. Murphy és társai egy kísérletről számoltak be, ahol ez valóban működött (Murphy és társai, 1999). Yedidia és társai további kapcsolatokra mutattak rá a bizonyosságterjesztés és a statisztikus fizika között (Yedidia és társai, 2001).

A valószínűség és az elsőrendű nyelvek közötti kapcsolatot Carnap tanulmányozta (Carnap, 1950). Gaifman, illetve Scott és Krauss megadott egy nyelvet, amelyben valószínűségeket elsőrendű mondatokhoz lehet kapcsolni, és amelyre a modellek valószínűségi mértékek voltak lehetséges világokon (Gaifman, 1964; Scott és Krauss, 1966). Az MI-n belül ezt az ötletet az ítéletlogikára Nilsson, a predikátumlogikára pedig Halpern fejlesztette ki (Nilsson, 1986; Halpern, 1990). A tudásreprezentációs kérdések első kiterjedt vizsgálatát ilyen nyelvek esetén Bacchus végezte (Bacchus, 1990), Wellman és társainak a tanulmánya a korai implementációkat tekinti át (Wellman és társai, 1992), amelyek egy ekvivalens (ítéletlogikai) Bayes-háló létrehozásán alapulnak. Napjainkra a kutatók elkezdték megérteni a teljes tudásbázisok fontosságát, azaz olyan tudásbázisok fontosságát, amelyek akár a Bayes-hálók, egy egyértelmű együttes eloszlást definiálnak az összes lehetséges világ felett. Az erre szolgáló eljárások a logikai programozás valószínűségi verzióin (Poole, 1993; Sato és Kameya, 1997) vagy szemantikus hálókon (Koller és Pfeffer, 1998) alapultak. A fejezetben ismertetett típusú relációs valószínűségi modelleket Pfeffer vizsgálta részletesebben (Pfeffer, 2000). Pasula és Russell mind a relációs, mind az azonossági bizonytalanságot vizsgálta az RVM-ekben és az MCMC következtetés felhasználásában (Pasula és Russell, 2001).

Amint a 13. fejezetben kifejtettük, a korai valószínűségi rendszerek kegyvesztettek lettek az 1970-es években, helyt adva az alternatív módszerek megjelenésének. A bizonyossági tényezőket a MYCIN orvosi szakértői rendszerbeli felhasználásra fejlesztették ki (Shortliffe, 1976), amit egyrészt mérnöki megoldásnak is, másrészt az emberi ítélethozatal modelljének is javasolták, bizonytalanság esetében. A Rule-Based Expert Systems gyűjtemény (Buchanan és Shortliffe, 1984) teljes áttekintést ad a MYCIN-ről és leszármazottairól (lásd még [Stefik, 1995]). David Heckerman megmutatta, hogy a bizonyossági tényezős számítások kicsit módosított verziója már helyes valószínűségeket ad bizonyos esetekben, de más esetekben a bizonyítékok hibát okozó, túlzott figyelembevételére vezet (Heckerman, 1986). A PROSPECTOR szakértői rendszer (Duda és társai, 1979) szabályalapú megközelítést használt, amiben a szabályokat (ritkán tartható) globális függetlenségi feltételezésekkel igazolták.

A Dempster–Shafer-elmélet Arthur Dempster publikációjával kezdődött, amiben a pontszerű valószínűségi értékek általánosítását javasolta intervallumértékekre, és szabályokat javasolt a kombinálásukra (Dempster, 1968). Glenn Shafer későbbi munkája vezetett el a Dempster–Shafer-elmélet és a valószínűség-számítás egymással versengő szemléletéhez (Shafer, 1976). Ruspini a Dempster–Shafer-elmélet és a valószínűség-számítás kapcsolatát elemezte (Ruspini és társai, 1992). Shenoy a Dempster–Shafer bizonyosságfüggvény alapján egy eljárást javasolt a döntéshozatalra (Shenoy, 1989).

A fuzzy halmazokat Lotfi Zadeh dolgozta ki válaszul arra a nehézségre (Zadeh, 1965), hogy egzakt bemeneti értékeket adjunk az intelligens rendszerek számára. Zimmermann leírása (Zimmermann, 2001) részletes bevezetést nyújt a fuzzy halmazok elméletébe; a (Zimmermann, 1999) pedig fuzzy alkalmazásokról szóló cikkek gyűjteménye. Amint korábban említettük, a fuzzy logikát gyakran tekintik a valószínűség-számítás versenytársának, pedig valójában eltérő kérdésekkel foglalkozik. A lehetőségelméletet (possibility theory) (Zadeh, 1978) a bizonytalanság kezelésére vezették be fuzzy rendszerekben, és sok közös vonása van a valószínűség-számítással. Dubois és Prade alapos áttekintést nyújt a lehetőségelmélet és a valószínűség-számítás kapcsolatáról (Dubois és Prade, 1994).

A valószínűség-számítás MI-n belüli feltámadása főként a Bayes-hálók felfedezésén múlt, ami módszert adott a feltételes függetlenségek reprezentálására és kihasználására. Ez az újjászületés igen küzdelmes volt; Peter Cheeseman harcias In defense of Probability (Cheeseman, 1985) és a későbbi An Inquire into Computer Understanding (Cheeseman, 1988, megjegyzésekkel) c. cikke ízelítőt ad a vitából. A logika művelőinek egyik legfőbb kifogása az volt, hogy a valószínűség-számítás miatt szükségesnek vélt számítások önelemzéssel nem érhetők el, és egy nem reális pontossági szintet tételeznek fel a bizonytalan tudásunkban. A kvalitatív Bayes-hálók (qualitative probabilistic networks) (Wellman, 1990a) lehetőséget adnak a Bayes-hálók tisztán kvalitatív absztrakciójára, csupán a változók közötti hatások pozitív és negatív jellegét kihasználva. Wellman megmutatta, hogy számos esetben ennyi információ is elegendő az optimális döntéshozatalhoz a valószínűségi értékek precíz meghatározása nélkül. Adnan Darwiche és Matt Ginsberg munkája kivonatolja a valószínűség-számítás elméletében szerepelő feltételesség és a tények kombinálásának alapvető tulajdonságait, és megmutatja, hogyan lehet ezeket alkalmazni logikai és alapértelmezési következtetésekben (Darwiche és Ginsberg, 1992).

A fejezetben leírt szívbetegség-kezelő rendszer Lucastól származik (Lucas, 1996). A Bayes-hálók más területen történő alkalmazásai között találjuk egyebek között a Microsoftnál végzett fejlesztéseket a felhasználó céljainak kikövetkeztetésére (Horvitz és társai, 1998) és a kéretlen elektronikus levelek szűrésére (Sahami és társai, 1998), az Electric Power Research Institute fejlesztését áramgenerátorok figyelésére és a NASA fejlesztését időkritikus információk megjelenítésére a Mission Controlnál Houstonban (Horvitz és Barry, 1995).

Az MI-n belüli bizonytalansági következtetéssel kapcsolatos számos fontos korai publikáció megtalálható a Readings in Uncertain Reasoning (Shafer és Pearl, 1990) és az Uncertainty in Artifical Intelligence (Kanal és Lemmer, 1986) antológiákban. A Bayes-hálók témakörének fejlődésében a legfontosabb egyedülálló publikáció vitathatatlanul a Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Pearl, 1988). Több kiváló munka tartalmazza az újabb anyagokat, mint például (Lauritzen, 1996; Jensen, 2001; Jordan, 2003). A valószínűségi következtetéssel kapcsolatos új eredmények mind az MI fő irányait meghatározó főbb lapokban, mint pl. az Artificial Intelligence-ben, mind a specializáltabb folyóiratokban, mint amilyen az International Journal of Approximate Reasoning jelennek meg. A gráfos modellekről (graphical models), amely modellosztály magában foglalja a Bayes-hálókat is, számos cikk statisztikai újságokban jelenik meg. Az Uncertainty in Artificial Intelligence (UAI), a Neural Information Processing Systems (NIPS) és az Artificial Intelligence and Statistics (AISTATS) konferenciák kiadványai kiváló forrásai a legfrissebb kutatásoknak.

14.18. ábra - Egy gépkocsi elektromos és motorikus rendszereinek részeit leíró Bayes-háló. Minden változó bináris, és az igaz érték jelzi a megfelelő funkció helyes működését.
Egy gépkocsi elektromos és motorikus rendszereinek részeit leíró Bayes-háló. Minden változó bináris, és az igaz érték jelzi a megfelelő funkció helyes működését.

14.8.2. Feladatok

14.1.

Tekintsük a 14.18. ábrán látható gépkocsi-diagnosztikai hálót.

  1. Egészítse ki a hálót a JegesIdő és az IndítóMotor bináris változókkal.

  2. Adjon meg ésszerű feltételes valószínűségi táblákat az összes csomópontra.

  3. Hány független értéket tartalmaz a teljes együttes valószínűség-eloszlás függvény 8 bináris csomópont esetén, feltételezve, hogy nincs közöttük feltételes függetlenségi reláció?

  4. Hány független valószínűségi értéket tartalmaznak az ön hálójának táblázatai?

  5. A Beindul feltételes valószínűség eloszlása megadható egy zajos-ÉS eloszlással. Írja le ezt az eloszláscsaládot általában és kapcsolatát a zajos-VAGY eloszláshoz.

14.2.

A helyi nukleáris erőműben van egy riasztó, ami érzékeli, ha a hőmérsékletmérő egy adott küszöbértéket meghalad. A mérő a reaktormag hőmérsékletét méri. Tekintse a következő bináris változókat: R (riasztó hangja), HR (hibás riasztó), HM (hibás mérő) és a következő többértékű változókat: M (mérő) és H (egy aktuális belső hőmérséklet).

  1. Rajzoljon fel egy Bayes-hálót a tárgytartományra, feltételezve, hogy valószínűbb, hogy a mérő akkor hibásodik meg, ha a hőmérséklet túl magas.

  2. A hálózata polifa lett?

  3. Tételezze fel, hogy a hőmérsékletnek csak két lehetséges értéke van: normális és magas; és hogy a mérő helytelen hőmérsékletet mér az esetek x%-ában, ha működik, és y%-ában, ha hibás. Adja meg az M feltételes valószínűség-tábláit.

  4. Tételezze fel, hogy a riasztó tökéletesen működik, hacsak nem hibás, mely utóbbi esetben egyáltalán nem riaszt. Adja meg az R-hez tartozó feltételes valószínűség-táblát.

  5. Tételezze fel, hogy a mérő és a riasztó működik, és a riasztó megszólal. Fejezze ki annak a valószínűségét, hogy a reaktormag hőmérséklete magas a háló feltételes valószínűségeinek a függvényében.

14.3.

Két csillagász – távcsöveiket használva – a világ különböző részein M1 és M2 méréseket végeznek az égbolt egy kis részén látható csillagok számáról (Sz). Általában egy kis e valószínűsége a hibának, ami egy csillagnyi eltérést jelent. Bármelyik távcsővel megtörténhet az is (egy sokkal kisebb f valószínűséggel), hogy nincs rendesen fókuszálva (F1 és F2 események), amely esetben a tudós 3 vagy több csillaggal kevesebb csillagot számlál (ha Sz kisebb mint 3, akkor egyetlen csillagot sem észlel). Tekintsük a 14.19. ábrán látható három hálót.

  1. Melyik Bayes-háló reprezentálja helyesen (de nem feltétlenül hatékonyan) a fenti ismereteket?

  2. Melyik a legjobb háló? Adjon magyarázatot.

  3. Adjon meg egy ésszerű feltételes valószínűségi táblát a P (M1∣Sz) értékeire, amikor M1 ∈ {0, 1, 2, 3, 4} és Sz ∈ {1, 2, 3}. A feltételes eloszlás minden értékét az e és az f paraméterek függvényében fejezze ki.

14.18. ábra - Három lehetséges háló a távcsőproblémára
Három lehetséges háló a távcsőproblémára

  1. Tételezze fel, hogy M1 = 1 és M2 = 3. Mik a csillagok lehetséges számai, ha a priori nem korlátozzuk Sz értékét?

  2. Mi a csillagok legvalószínűbb száma ezen megfigyelések esetén? Magyarázza el ennek kiszámítását, vagy ha nem lehetséges kiszámítani, magyarázza el, milyen további információkra van szükség, és hogy az miként befolyásolná az eredményt.

14.4.

Tekintsük a 14.19. (ii) ábrán látható hálót, és tegyük fel, hogy a két teleszkóp azonosan működik. Legyen M1, M2 ∈ {0, 1, 2, 3, 4} és Sz ∈ {1, 2, 3} a 14.3. feladatban megadott szimbolikus FVT-kkel. A felsoroló algoritmus felhasználásával számolja ki a következő valószínűség-eloszlást: P(Sz∣M1 = 2, M2 = 2).

14.5.

Tekintsük a lineáris Gauss lokális eloszlású hálók családját, amit az 14.3.1. szakasz - Bayes-hálók folytonos változókkal rész illusztrál.

  1. Egy kétváltozós hálóban legyen X1 az X2 szülője, X1-nek legyen normális a priori eloszlása, P(X2∣X1) pedig egy lineáris normális eloszlás. Mutassa meg, hogy a P(X1, X2) együttes eloszlás egy többváltozós Gauss-eloszlás, és számolja ki ennek a kovarianciamátrixát.

  2. Bizonyítsa be indukcióval, hogy egy általános lineáris Gauss-háló X1, …, Xn-en vett együttes eloszlása szintén többváltozós Gauss-eloszlás.

14.6.

Az 14.3.1. szakasz - Bayes-hálók folytonos változókkal részben definiált probit eloszlás egy bináris gyermek valószínűség-eloszlását írja le, egyetlen folytonos szülő esetén.

  1. Hogyan terjeszthető ki a definíció több folytonos szülő esetére?

  2. Hogyan terjeszthető ki, hogy többértékű gyermekváltozóra is alkalmazható legyen? Gondolja végig mind a két esetet, amikor a gyermek értékei sorrendezettek (ahogyan a vezetésnél a sebességfokozat megválasztása a sebesség, a lejtés, a kívánt gyorsulás stb. függvénye), és amikor nem állíthatók sorba (mint például a busz, a vonat vagy a kocsi választása munkába menetelnél). (Segítség: gondoljunk a lehetséges értékek két csoportra osztására, hogy bináris változót szimuláljunk.)

14.7.

Ez a feladat a 14.10. ábrán látható változó eliminációs algoritmusra irányul.

  1. A 14.4. alfejezet a változó eliminálást alkalmazza arra a lekérdezésre, hogy

P(Betörés∣JánosTelefonál = igaz, MáriaTelefonál = igaz)

Végezze el a jelzett számításokat, és ellenőrizze, hogy helyes-e a válasz.

  1. Számolja össze az elvégzett aritmetikai műveletek számát, és hasonlítsa össze a felsorolási algoritmus által elvégzettek számával.

  2. Tegyük fel, hogy a háló egy láncot alkot: bináris változók szekvenciáját, ahol Szülők(Xi) = {Xi–1} i = 2, ..., n esetén. Mi a P(X1∣Xn = igaz) kiszámításának a komplexitása a felsorolást használva? És mi, ha változó eliminálást használunk?

  3. Bizonyítsa be, hogy a változó eliminálás futásának komplexitása egyszeresen összekötött hálóban lineáris a háló méretében bármely, a háló struktúrájával konzisztens változó sorrendezés mellett.

14.8.

Vizsgáljuk meg az egzakt következtetés komplexitását általános Bayes-hálókban.

  1. Bizonyítsa be, hogy bármely 3-SAT probléma redukálható egy egzakt következtetésre egy olyan Bayes-hálóban, amely a konkrét problémát reprezentálja, és így az egzakt következtetés NP-nehéz. (Segítség: gondoljon egy olyan hálóra, amiben minden kijelentésszimbólumhoz, minden klózhoz és a klózok minden konjunkciójához rendre egy-egy csomópont tartozik.)

  2. A 3-SAT problémában a kielégítő érték-hozzárendelések számának meghatározása #P-teljes. Bizonyítsa be, hogy az egzakt következtetés legalább ennyire nehéz.

14.9.

Tekintsük egy véletlen minta egy megadott egyváltozós eloszlásból történő generálásának a problémáját. Feltételezhetjük, hogy rendelkezésre áll egy véletlenszám-generátor, ami egyenletes eloszlás szerint 0 és 1 közötti véletlen számokat ad.

  1. Legyen X egy diszkrét valószínűségi változó P(Xi = xi) = pi i ∈ {1, ..., k} tömegfüggvénnyel. Az X eloszlásfüggvénye (cumulative distribution) minden lehetséges j-re megadja annak valószínűségét, hogy X ∈ {x1, ..., xj}.

    Magyarázza el, hogyan számolható ki az eloszlásfüggvény O(k) időben, és hogyan generálhatunk vele egy X eloszlása szerinti mintát. Ez utóbbi megtehető kevesebb mint O(k) időben?

  2. Most tegyük fel, hogy N mintát szeretnénk generálni X szerint, ahol N >> k. Magyarázza el, hogyan tehető ez úgy meg, hogy a mintánkénti várható futási idő konstans (azaz független k-tól).

  3. Most tekintsünk egy folytonos értékű változót egy parametrikus eloszlással (például normálissal). Hogyan generálhatunk mintákat egy ilyen eloszlásból?

  4. Tegyük fel, hogy egy folytonos értékű változót szeretne lekérdezni, és egy olyan mintavételező algoritmust használ a következtetésre, mint a VALÓSZÍNŰSÉGISÚLYOZÁS. Hogyan kellene módosítania a lekérdezés-válaszadás folyamatát?

14.10.

Egy változó Markov-takaróját (Markov blanket) az 14.2.2. szakasz - Feltételes függetlenségi relációk Bayes-hálókban definiáltuk.

  1. Bizonyítsa be, hogy a változó független a háló összes többi változójától, ha Markov-takarója ismert.

  2. Vezesse le a (14.11) egyenletet.

14.11.

Tekintsük a P(Eső∣Locsoló = igaz, VizesPázsit = igaz) lekérdezést a 14.11. (a) ábra szerint, és annak az MCMC módszerrel való megválaszolását.

  1. Hány állapota van a Markov-láncnak?

Számítsa ki a Q állapotátmenet-mátrixot (transition matrix Q), ami tartalmazza az összes q(y⟶y′) értéket minden y-ra és y′-ra.

  1. Mit reprezentál Q2, az állapotátemeneti mátrix négyzete?

  2. Mi lesz Qn, ha n ⟶ ∞?

  3. Magyarázza el, hogy hajtsunk végre valószínűségi következtetést Bayes-hálókban, ha Qn elérhető. Hatékony módja ez a következtetésnek?

14.12.

Három focicsapat, A, B és C játszik egymás ellen. Minden meccsen két csapat vesz részt, az eredmény pedig győzelem, vereség vagy döntetlen lehet. Minden csapatnak egy rögzített, ismeretlen fokozatú játékszintje van – ami egy 0 és 3 közötti egész érték –, és egy meccs eredménye a két csapat játékszintje közötti különbségtől függ sztochasztikusan.

  1. Hozzon létre egy relációs valószínűségi modellt a tárgyterületre, és javasoljon értékeket az összes szükséges valószínűség-eloszlásra.

  2. Hozzon létre egy ekvivalens Bayes-hálót.

  3. Tegyük fel, hogy az első két meccsen A megveri B-t, C-vel pedig döntetlent játszik. Egy tetszőleges egzakt következtetést felhasználva, számítsa ki a harmadik meccs a posteriori eloszlását.

  4. Tegyük fel, hogy n csapat vesz részt a bajnokságon, és minden eredményünk megvan, kivéve az utolsót. Hogyan változik az utolsó meccs megjóslásának a komplexitása az n függvényében?

  5. Vizsgálja meg az MCMC alkalmazását ezen a problémán. Milyen gyorsan konvergál az MCMC a gyakorlatban, és hogyan skálázható fel?


[155] I. J. Good vezető statisztikus volt Turing kódfeltörő csapatában a második világháború során. A 2001: űrodüsszeia c. művében Arthur C. Clarke Goodnak és Minskynek tulajdonította azokat az áttöréseket, amelyek a HAL számítógép kifejlesztéséhez vezettek (Clarke, 1968a).

fel