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.
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,1 ∧ s1,2 ∧ s2,1 és ismert = ¬c1,1 ∧ ¬c1,2 ∧ ¬c2,1 rövidítésekkel fogjuk jelölni. A mi számunkra a P(C1,3∣ismert, 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(s∣ismert, 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,3∣ismert, 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!
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.