13.7. A wumpus világ újralátogatása

E fejezet gondolatai közül sok eredményesen kombinálható a wumpus világ valószínűségi következtetési problémáinak megoldására. (A wumpus világ teljes leírása a 7. fejezetben található.) A wumpus világban fellépő bizonytalanságot az ágens érzékelésének a világra vonatkozóan a csak helyi információt szolgáltató részlegessége okozza. Például a 13.6. ábra egy olyan szituációt ábrázol, amelyben mindhárom elérhető négyzet – [1, 3], [2, 2] és [3, 1] – tartalmazhat csapdát. Egyszerű logikai következtetéssel nem dönthető el, hogy melyik a legvalószínűbben biztonságos négyzet, így a logikai ágens kénytelen véletlenszerűen választani. Látni fogjuk ugyanakkor, hogy egy valószínűségi ágens sokkal sikeresebb, mint egy logikai ágens.

A célunk az lesz, hogy mindhárom négyzetre kiszámítsuk a csapda valószínűségét. (A példa erejéig elfelejtjük a wumpust és az aranyat.) A wumpus világ idevágó tulajdonságai a következők: (1) egy csapda szellőt okoz a szomszédos négyzetekben, és (2) az [1,1]-en kívül minden négyzet 0,2 valószínűséggel tartalmaz csapdát. Első lépésként a számításhoz szükséges véletlen változókat kell meghatároznunk:

  • Az ítéletlogikához hasonlóan, itt is minden négyzethez egy (Ci,j) logikai változóra van szükségünk, amelynek értéke akkor és csak akkor igaz, ha az [i,j] négyzet tartalmaz csapdát.

  • Vannak továbbá Si,j logikai változóink is, amelyek igaz értéke egyértelműen az [i,j] négyzetben tapasztalható szellőre utal; példánkban csak a megfigyelt – esetünkben az [1, 3], [2, 2] és [3, 1] négyzetekre – vonatkozó változókat használjuk.

A következő lépés a P(C1,1,…, C4,4, S1,1, S1,2, S2,1) teljes valószínűségi eloszlás meghatározása. A szorzatszabály alkalmazásával

P(C1,1,…, C4,4, S1,1, S1,2, S2,1) = P(S1,1, S1,2, S2,1 C1,1,…, C4,4)P(C1,1,…, C4,4)

adódik.

13.6. ábra - (a) Az ágens beragad, miután [1, 2]-ben és [2, 1]-ben is szellőt észlel – nincs feltárható biztonságos hely. (b) A négyzetek szétosztása Ismert, Perem és Egyéb csoportokba az [1, 3]-ra vonatkozó lekérdezéshez.
(a) Az ágens beragad, miután [1, 2]-ben és [2, 1]-ben is szellőt észlel – nincs feltárható biztonságos hely. (b) A négyzetek szétosztása Ismert, Perem és Egyéb csoportokba az [1, 3]-ra vonatkozó lekérdezéshez.

A dekompozíció nagyon könnyűvé teszi az együttes valószínűségi értékek meghatározását. Az első rész a szellő feltételes valószínűség konfigurációját adja adott csapda konfigurációnál; ennek értéke 1, ahol a szellő szomszédos egy csapdával, minden más esetben 0. A második tag a csapdakonfiguráció előzetes valószínűsége. A négyzetek a többi négyzettől függetlenül 0,2 valószínűséggel tartalmaznak csapdát; következésképpen

Egy n csapdát tartalmazó konfigurációnál ennek értéke 0,2n × 0,816–n.

A 13.6. (a) ábra szerinti helyzetnél a bizonyíték magában foglalja minden meglátogatott négyzetre az ott megfigyelt szellőt (vagy annak hiányát) azzal a ténnyel együtt, hogy a meglátogatott négyzetek nem tartalmaznak csapdát. Ezeket az s = ¬s1,1s1,2s2,1 és ismert = ¬c1,1 ∧ ¬c1,2 ∧ ¬c2,1 rövidítésekkel fogjuk jelölni. A mi számunkra a P(C1,3ismert, s) típusú lekérdezések megválaszolása érdekes: adott megfigyelések mellett mennyire valószínű, hogy az [1, 3] csapdát tartalmaz?

A válaszhoz követhetjük a (13.6) egyenlet szerinti szabványos megközelítést, amelyet a FELSOROL-EGYÜTTES-KÉRDEZÉS eljárás valósít meg, azaz a teljes együttes valószínűségi eloszlás bejegyzései szerinti összegzést. Jelölje Ismeretlen azt az összetett változót, amelyet a nem Ismert csoportba tartozó négyzetek és a lekérdezett [1, 3] négyzet Ci,j változói alkotnak. Ezzel a (13.6) egyenletből

A teljes együttes valószínűségeket korábban már meghatároztuk, így készen is vagyunk – kivéve, ha a számítási bonyolultság kérdésével is törődünk. 12 ismeretlen négyzetünk van; így az összegzés 212 = 4096 tagból fog állni. Általánosságban, az összegzés exponenciálisan nő a négyzetek számával.

Az intuíció azt súgja, hogy itt valamit még figyelmen kívül hagyunk. És tényleg, bárki megkérdezheti, hogy a többi négyzet nem lényegtelen-e? A [4, 4] tartalma nincs hatással arra, hogy az [1, 3] tartalmaz-e csapdát! Ez az intuíció valóban helyes. Jelölje Perem azokat a – lekérdezés változójától különböző – változókat, amelyek a meglátogatott négyzetekkel szomszédosak, esetünkben a [2, 2] és a [3, 1]. Továbbá Egyéb legyen a többi ismeretlen négyzet változója; példánkban – ahogy a 13.6. (b) ábra is mutatja – 10 ilyen négyzet van. A kulcs meglátás az, hogy megfigyelt szellők feltételesen függetlenek a többi változótól, ha adottak az ismert, a perem és a lekérdezés változók. A többi, ahogy mondják, már csak egy kis algebra.

A fenti meglátás használatához a lekérdezést olyan alakra hozzuk, amelyben a szellő az összes többi változó feltétele mellett van megadva, majd az egészet egyszerűsítjük a feltételes függetlenség alapján:

ahol az utolsó lépés használja ki a feltételes függetlenséget. E kifejezés első tagja nem függ a többi változótól, így az összegzés belülre vihető:

Függetlenség esetén a (13.15) egyenlethez hasonlóan az előző kifejezés tényezőkre bontható, majd a tényezők sorrendje átrendezhető:

ahol az utolsó lépésben C(ismert)-et belefoglaltuk a normalizáló konstansba, és kihasználtuk, hogy értéke 1.

Most már csak négy tag van a C2,2 és C3,1 peremváltozók feletti összegzésben. A függetlenség és feltételes függetlenség miatt egyáltalán nem szükséges figyelembe vennünk a többi négyzetet. Vegyük észre, hogy a P(sismert, C1,3, perem) kifejezés értéke 1, ha a határ megegyezik a szellő érzékelésekkel és minden más esetben 0. Azaz, C1,3 minden értékére azon határváltozók logikai modelljei fölött végezzük az összegzést, amelyek az megfelelnek az ismert tényeknek. (Érdemes ezt összehasonlítani a 7.5. ábra modelljei szerinti számítással.) A modelleket és a hozzájuk kapcsolódó C(perem) a priori valószínűségeket a 13.7. ábra mutatja. Ezzel

P(C1,3ismert, s) = α'⟨0,2(0,04 + 0,16 + 0,16), 0,8(0,04 + 0,16)⟩ ≈ ⟨0,31, 0, 69⟩

Azaz, az [1, 3] (és a szimmetria miatt a [3, 1]) nagyjából 31% valószínűséggel tartalmaz csapdát. Hasonló számításokból (amelyet az olvasó könnyen elvégezhet) a [2, 2]-re 86%-os valószínűséggel adódik csapda. A wumpus ágensnek határozottan el kell kerülnie a [2, 2]-t!

13.7. ábra - C2,2 és C3,1 peremváltozók, az egyes modellek C(perem) értékét mutató konzisztens modelljei: (a) három, két vagy három csapdát jelző modell C1,3 = igaz mellett, és (b) két, egy vagy két csapdát jelző modell C1,3 = hamis mellett.
C2,2 és C3,1 peremváltozók, az egyes modellek C(perem) értékét mutató konzisztens modelljei: (a) három, két vagy három csapdát jelző modell C1,3 = igaz mellett, és (b) két, egy vagy két csapdát jelző modell C1,3 = hamis mellett.

Ebben az alfejezetben azt mutattuk meg, hogy még a látszólag bonyolult problémák is pontosan megfogalmazhatók valószínűség-elméleti alapokon, és meg is oldhatók egyszerű algoritmusok segítségével. Hogy hatékony megoldásokat kapjunk, a szükséges összegzéseket a függetlenségekre és feltételes függetlenségekre alapozva egyszerűsítjük. Ezek az összefüggések gyakran egybeesnek a probléma részproblémákra való felbontására vonatkozó természetes felfogásunkkal. A következő fejezetben ilyen összefüggések formális megjelenítésére alkalmazunk módszereket, valamint olyan algoritmusokat fejlesztünk ki, amelyek hatékonyan használhatók e reprezentációk alapján elvégzett valószínűségi következtetések végrehajtására.