10.7. Következtetés alapértelmezett információval

Az előbbi alfejezetben láttunk egy egyszerű példát egy alapértelmezett státussal rendelkező állításra: „az embereknek két lába van”. Ezt az alapértelmezett értéket specifikusabb információval, mint például „a Kékszakállúnak egy lába van”, felülírhatjuk. Láttuk, hogy a szemantikus háló öröklődési mechanizmusa az alapértelmezett értékek felülírását egyszerű és természetes módon oldja meg. Ebben a részben az alapértelmezett értékeket mélyebben tanulmányozzuk annak érdekében, hogy az alapértelmezett értékek szemantikáját alaposabban megértsük, és ne szorítkozzunk csupán a procedurális mechanizmus megadására.

10.7.1. Nyitott és zárt világok

Tegyük fel, hogy egyetemen a számítástudományi tanszék hirdetőtábláját nézzük, és azt az üzenetet látjuk, hogy: „Az alábbi tantárgyakat fel lehet venni: SZT 101, SZT 102, SZT 106 és VIM 101.” Próbáljuk most megválaszolni, vajon hány tárgyat lehet felvenni? Ha a válasza az, hogy „négy”, ez megegyezik egy tipikus adatbázis válaszával. Ha adott egy relációs adatbázisa:

Tantárgy(SZT, 101), Tantárgy(SZT, 102), Tantárgy(SZT, 106),

Tantárgy(VIM, 101) (10.2)

négy állítás megfelelőjével, a count * from Tantárgy SQL-felkérés 4-es válasszal tér vissza. Másfelől egy elsőrendű logikai rendszer válasza az lenne, hogy „egy és végtelen között valahány”, és nem „négy”. Ennek magyarázata, hogy a Tantárgy állítás nem zárja ki, hogy más, nem említett tantárgyakat is fel lehessen venni, és azt sem, hogy az említett tantárgyak mind különbözők.

A példa mutatja, hogy az adatbázisok és az emberi kommunikáció konvenciója az elsőrendű logikától legalább két aspektusban különbözik. Először, az adatbázisok (és az emberek) feltételezik, hogy a megadott információ teljes, vagyis hogy az igazként ki nem jelentett rögzített atomi formulákról feltételezhetjük, hogy hamisak. Ez az ún. zárt világ feltételezés (closed-world assumption, CWA). Másodszor, elfogadjuk általában, hogy különböző nevek különböző objektumokat jelentenek. Ez az ún. egyedi elnevezések feltételezés (unique names assumption, UNA), amit a cselekvés-nevek kontextusában először a 10.3. alfejezetben vezettünk be.

Az elsőrendű logika e konvenciókhoz nem folyamodik, így precízebbnek kell lennie. Hogy kijelentsük, csak négy különböző tantárgyat lehet választani, azt kellene írni, hogy:

Tantárgy(d, n) ⇔ [d, n] = [SZT, 101] ∨ [d, n] = [SZT, 102]

∨ [d, n] = [SZT, 106] ∨ [d, n] = [VIM, 101] (10.3)

A (10.3) egyenletet a (10.2) lezárásának[104] (completion) nevezzük. A lezárás általában minden predikátumhoz egy definíciót, egy „akkor és csak akkor” állítást rendel hozzá. Minden definícióban mindegyik, a predikátumot a fejében tartalmazó definit klózhoz egy diszjunkció fog tartozni.[105] A lezárást általánosságban az alábbi módon szerkesztik meg:

  1. Gyűjtsük ki az ugyanolyan (P) predikátum névvel és (n) aritással rendelkező klózokat.

  2. Minden klózt az ún. Clark Normál Formára (Clark Normal Form) transzformáljuk: cseréljük a:

P(t1,…, tn) ← Törzs

kifejezést, ahol a ti-k termek, a:

P(t1,…, tn) ← ∃w1wm [v1,…, vn] = [t1,…, tn] ∧ Törzs

kifejezésre, ahol a vi-k az újonnan bevezetett változók és a wi-k az eredeti klóz változói. Használjuk minden klóz esetén a vi változók ugyanazon halmazát. Eredményként a:

P(v1,…, vn) ← B1

.

.

.

P(v1,…, vn) ← Bk

klózok halmazát kapjuk.

  1. Kombináljuk ezeket össze egy nagy diszjunktív klózzá:

P(v1,…, vn) ← B1 ∨… ∨ Bk

  1. Zárjuk le azáltal, hogy a ←-at ekvivalenciára cseréljük:

P(v1,…, vn) ⇔ B1 ∨ … ∨ Bk

A Clark-lezárás egy példáját – szabályokat és rögzített tényeket tartalmazó tudásbázis esetén – a 10.12. ábrán láthatjuk. Hogy hozzáadhassuk az egyedi elnevezések feltételezést is, egyszerűen adjuk meg az azonossági reláció Clark-lezárását, ahol csak azok az ismert tények, hogy SZT = SZT és 101 = 101 stb. Ennek megvalósítását gyakorlásképpen meghagyjuk az olvasónak.

10.12. ábra - Horn-klózok egy halmazának Clark-lezárása. Az eredeti Horn-program (balra) négy tantárgyat említ explicit módon, és azt is állítja, hogy minden egészre a 101 és a 130 között létezik egy matematikai tárgy, meg azt is, hogy minden SZT tárgyhoz a 100-as (BSc) sorozatban létezik egy megfelelő tantárgy a 200-as (MSc) sorozatban. A Clark-lezárás (jobbra) azt mondja, hogy más tantárgy nincs is. A lezárással és az egyedi elnevezések feltételezéssel (valamint az Egész predikátum nyilvánvaló definíciójával) együtt eljutunk a kívánt konklúzióig, miszerint pontosan 36 tantárgy van: 30 matematikai és 6 SZT tárgy.
Horn-klózok egy halmazának Clark-lezárása. Az eredeti Horn-program (balra) négy tantárgyat említ explicit módon, és azt is állítja, hogy minden egészre a 101 és a 130 között létezik egy matematikai tárgy, meg azt is, hogy minden SZT tárgyhoz a 100-as (BSc) sorozatban létezik egy megfelelő tantárgy a 200-as (MSc) sorozatban. A Clark-lezárás (jobbra) azt mondja, hogy más tantárgy nincs is. A lezárással és az egyedi elnevezések feltételezéssel (valamint az Egész predikátum nyilvánvaló definíciójával) együtt eljutunk a kívánt konklúzióig, miszerint pontosan 36 tantárgy van: 30 matematikai és 6 SZT tárgy.

A zárt világ feltételezés lehetővé teszi, hogy megtaláljuk egy reláció minimálmodelljét (minimal model). Ez azt jelenti, hogy a Tantárgy relációhoz a legkevesebb elemet tartalmazó modellt találhatjuk meg. A (10.2) egyenletben a Tantárgy minimálmodellje négyelemű, kevesebb már ellentmondáshoz vezet. Horn-klóz tudásbázisok esetén mindig létezik egy egyértelmű minimálmodell. Jegyezzük meg, hogy az egyedi elnevezések feltételezés mellett ez az azonossági relációra is vonatkozik: minden term csakis saját magával azonos. Paradox módon ez azt jelenti, hogy a minimál modellek egyben maximálisak abban az értelemben, hogy annyi objektumot tartalmaznak, amennyi csak lehetséges.

Lehetséges egy Horn-program Clark-lezárását képezni, majd a következtetések levonása végett egy tételbizonyítónak átadni. Hatékonyabb azonban általában egy olyan speciális rendeltetésű következtető gépet használni, mint amilyen a Prolog, amelynél a zárt világ és az egyedi elnevezések feltételezések a következtetési mechanizmusba be vannak építve.

Akik a zárt világ feltételezéshez folyamodnak, óvatosan kell megválasztaniuk az általuk használt következtetést. Egy népszámlálási adatbázisban például, ésszerű a zárt világ feltételezést használni, ha a következtetés a városok populációjáról történik, de nyilván helytelen konklúzió lenne elfogadni, hogy a jövőben nem születnek gyerekek, csakis annak alapján, hogy az adatbázis a jövőbeli születési bejegyzéseket nem tartalmazza. A zárt világ feltételezés az adatbázist teljessé (complete) teszi abban az értelemben, hogy minden atomi lekérdezésre vagy pozitív, vagy negatív választ kapunk. Ha valamely tényállásról (mint például a jövőbeli születések) tényleg tudatlanok vagyunk, a zárt világ feltételezést használni nem szabad. Egy komplikáltabb tudásreprezentációs rendszerben a felhasználónak esetleg szabad lenne specifikálni a zárt világ feltételezés használatát leíró szabályokat.

10.7.2. Negálás mint kudarc és stabil modell szemantika

A 7. és a 9. fejezetekben láttuk, hogy Horn-klóz formájú tudásbázisnak kedvező számítástechnikai tulajdonságai vannak. Sok alkalmazásban azonban nem kényelmes azt biztosítani, hogy klózok törzseiben csak pozitív literálok legyenek. Szeretnénk például azt mondani, hogy „Kimehetsz, ha nem esik”, anélkül hogy olyan predikátumokhoz kellene folyamodni, mint a NemEsik. Ebben a részben annak a lehetőségét kutatjuk, hogy a Horn-klózokhoz az explicit negálás egy formáját adjuk hozzá a negálás mint kudarc (negation as failure) ötletét felhasználva. Az ötlet az, hogy egy negatív „not P” literált igaznak „bizonyíthatunk”, hasonlóan, mint ahogy P bizonyítása kudarcba fulladhat. Ez az alapeseti következtetés egy formája, ami a zárt világ feltételezéshez szorosan kapcsolódik: tételezzük fel, hogy valami hamis, ha nem bizonyítható, hogy igaz. Hogy a negálás mint kudarc-ot a logikai „¬” operátortól megkülönböztethessük, megjelölésére a „not”-ot fogjuk használni.

A Prolog megengedi a not operátort egy klóz törzsében. Tekintsük például az alábbi Prolog programot:

IDEmeghajtó Meghajtó not SCSImeghajtó

SCSImeghajtó Meghajtó not IDEmeghajtó

SCSIvezérlő SCSImeghajtó

Meghajtó

Az első szabály azt mondja, hogy ha számítógépben merevlemez-meghajtónk van, és ez nem SCSI, akkor IDE-nek kell lennie. A másik szabály azt mondja, hogy ha ez nem IDE, akkor SCSI-nek kell lennie. A harmadik azt mondja, hogy az SCSI-meghajtó létezése egy SCSI-vezérlőt tételez fel, végül a negyedik kijelenti, hogy tényleg van egy meghajtó. Ennek a programnak két minimálmodellje van:

M1 = {Meghajtó, IDEmeghajtó}

M2 = {Meghajtó, SCSImeghajtó, SCSIvezérlő}

A minimálmodellek nem képesek a negálás mint kudarc-ot használó programok szándékolt szemantikáját kifejezni. Tekintsük a következő programot:

Pnot Q

Ennek két minimálmodellje van: {P} és {Q}. Az elsőrendű logika szemszögéből van ennek értelme, mivel a P ⇐ ¬Q a PQ-val ekvivalens. A Prolog szemszögéből azonban aggódni kellene: Q soha nem jelenik meg a nyíl bal oldalán, hogyan lehet hát egy következmény?

Egy alternatíva a stabil modell (stable model), ami egy olyan minimálmodell, ahol minden atomnak igazolása (justification) van, azaz létezik hozzá olyan szabály, amelyben a fej az atom, és ahol a törzs minden literálja kielégített. Formálisan M egy H program egy stabil modellje, ha M a H az M-re vonatkozó redukáltjának (reduct) egy egyértelmű minimálmodellje. Egy H program redukáltját úgy definiáljuk, hogy H-ból először minden olyan szabályt törlünk, amely törzsében a not A literál szerepel, ahol A a modell része, majd a maradó szabályokban a negatív literálokat töröljük. Mivel H redukáltja most már egy Horn-klóz lista, egy egyértelmű minimálmodellel kell rendelkeznie.

A Pnot Q redukáltja a {P}-re nézve maga a {P}, aminek minimálmodellje {P}. Így {P} egy stabil modell. A {Q}-ra vonatkozó redukció egy üres program, aminek minimálmodellje {}. {Q} tehát nem stabil modell, mert Q-nak a (10.5) egyenletben nincs igazolás. Egy másik példa a (10.4) redukáltjára az M1-re nézve:

IDEmeghajtó Meghajtó

SCSIvezérlő SCSImeghajtó

Meghajtó

Ennek minimálmodellje M1, így M1 egy stabil modell. A válaszhalmaz programozás (answer set programming) a logikai programozásnak a negálás mint kudarc-cal bővített fajtája, amely úgy működik, hogy a logikai programot rögzített formába transzformálja, majd stabil modelleket (amelyeket válaszhalmazoknak – answer sets – is neveznek) keres, ítéletkalkulus modell-ellenőrzési technikákat felhasználva. A válaszhalmaz-programozás leszármazottja tehát mind a Prolognak, mind az olyan gyors ítéletkalkulus-beli kielégíthetőségi tételbizonyítóknak, mint a WALKSAT. A válaszhalmaz programozást sikerrel alkalmazták tervkészítési problémákra, hasonlóan az ítéletkalkulus-beli kielégíthetőségi tételbizonyítókhoz. A válaszhalmaz-programozás előnye más tervkészítőkkel szemben a rugalmassága: a tervkészítő operátorokat és a kényszereket logikai programokkal fejezi ki, és így azok nem kötődnek a konkrét tervkészítési formalizmus korlátozott formátumához. A válaszhalmaz-programozás hátránya ugyanaz, mint minden ítéletkalkulus szintű technikáé: ha az univerzumban túl sok objektum létezik, egy exponenciális lassulással kell számolnunk.

10.7.3. Körülírás és alapeseti logika

Két példát láttunk, ahol látszólag természetes következtetési folyamatok megsértik a logika a 7. fejezetben bebizonyított monotonitás (monotonicity) tulajdonságát.[106] Az első példában egy szemantikus hálóban egy kategória összes tagja által megörökölt tulajdonságot egy alkategóriára vonatkozó specifikusabb információ felülírhatja. A másik példában a zárt világ feltételezésből származtatott negált literálokat pozitív literálok hozááadása szintén felülbírálja.

Ha egy kicsit magunkba nézünk, rájövünk, hogy a monotonitás ilyen sérülései a józan ész következtetésben igen elterjedtek. Úgy tűnik, az emberek gyakran „elhamarkodott következtetéseket” vonnak le. Ha az utcán parkoló kocsit látunk, mindenki elhiszi, hogy a kocsinak négy kereke van, holott csak három kerék látszik (ha valaki a negyedik kerék létezésében kételkedik, akkor vegye fontolóra azt a kérdést, vajon a három látható kerék valódi-e, vagy csupán a valódinak egy papírmása.) A valószínűség-elmélet nyilván igazolhatja, hogy a negyedik kerék nagy valószínűséggel létezik, az emberek többségében az a lehetőség, hogy a gépkocsinak esetleg nincs négy kereke, egyáltalán fel sem merül, hacsak valami új tényállás erre nem derít fényt. A négy kerék konklúzióját tehát alapesetként kezeljük, a kételkedésre okot adó tények hiányában. Ha új tények érkeznek – észrevesszük például, hogy a tulajdonos a kereket elviszi, és a gépkocsi egy emelőn áll – akkor a konklúziót vissza kell vonni. Az ilyen következtetésről azt mondjuk, hogy nemmonoton (nonmonoton), mert a hiedelemek halmaza idővel, ahogy az új evidenciák megjelennek, nem növekszik monoton módon. Az ilyen viselkedés leírására nemmonoton logikákat (nonmonoton logics) fejlesztettek ki, módosított igazságdefinícióval és vonzatrelációval. Két ilyen intenzíven tanulmányozott logikát fogunk megnézni: a körülírást és az alapeseti logikát.

A körülírást (circumscription) a zárt világ feltételezés erősebb és precízebb változatának lehetne tekinteni. Az ötlet, hogy konkrét predikátumokat specifikálunk, amelyekről feltételezzük, hogy „amennyire csak lehetséges hamisak” – azaz minden objektumra hamisak, kivéve azokat, amelyekre tudjuk, hogy igazak. Tegyük fel például, hogy ki akarjuk jelenteni azt az alapértelmezett szabályt, hogy a madarak tudnak repülni. Vezessük be az Abnormális1(x) predikátumot, és írjuk fel:

Madár(x) ∧ ¬Abnormális1(x) ⇒ Repül(x)

Ha azt mondjuk, hogy az Abnormális1-et körül kell írni (circumscribed), a körülíró következtető feltételezheti, hogy ¬Abnormális1(x), hacsak az Abnormális1(x)-et nem fogja igaznak találni. Ez lehetővé teszi, hogy a Repül(Tweety) konklúziót levonjuk a Madár(Tweety) premissza alapján, azonban a konklúzió csak addig igaz, amíg az Abnormál(Tweety)-t ki nem jelentjük.

A körülírást a modellpreferencia-logika (model preference logic) egy példájának is tekinthetjük. Az ilyen logikákban egy állítás vonzatrelációban van (alapeseti státuson), ha igaz a tudásbázis minden preferált modelljében, ellentétben a klasszikus logika igazságkövetelményével, hogy minden modellben legyen igaz. Körülírás esetében egy modell egy másiknál preferáltabb, ha kevesebb abnormális objektuma van.[107] Nézzük meg, hogy ez az ötlet hogyan működik szemantikus hálóban fellépő többszörös öröklődés esetén. A többszörös öröklődés standard példája az ún. „Nixon-gyémánt”.[108] Az eredete az a megfigyelés, hogy Richard Nixon egy kvéker vallási szektához tartozott (és így alapesetben pacifista) és republikánus is volt (és így alapesetben éppen nem pacifista). Ezt az alábbi módon írhatjuk fel:

Republikánus(Nixon) ∧ Kvéker(Nixon)

Republikánus(x) ∧ ¬Abnormális2(x) ⇒ ¬Pacifista(x)

Kvéker(x) ∧ ¬Abnormális3(x) ⇒ Pacifista(x)

Ha az Abnormális2-t és az Abnormális3-at körülírjuk, két preferált modellt kapunk: az egyikben igaz az Abnormális2(Nixon) és a Pacifista(Nixon), a másikban igaz az Abnormális3(Nixon) és a ¬Pacifista(Nixon). A körülíró következtető rendszer tehát megfelelően tudatlannak mutatkozik a pacifista Nixon ügyében. Ha ezentúl szeretnénk kijelenteni, hogy a vallásos meggyőződések elsőbbséget élveznek a politikai nézetekkel szemben, a prioritásos körülírás (prioritized circumscription) formalizmusát használhatjuk, hogy azoknak a modelleknek adjunk elsőbbséget, ahol az Abnormális3 minimálizálva van.

Az alapértelemzett logika (default logic) egy olyan formalizmus, ahol alapértelmezett szabályokat (default rules) lehet írni feltételes, nemmonoton következtetések generálásához. Egy alapértelmezett szabály a következőképpen néz ki:

Madár(x) : Repül(x) /Repül(x)

A szabály jelentése, hogy ha a Madár(x) igaz, és ha a Repül(x) a tudásbázissal konzisztens, akkor a Repül(x)-et alapértelmezésben lekövetkeztethetjük. Általánosságban egy alapértelmezett szabály formája a:

P : J1, …, Jn/C

ahol P-t előfeltételnek, C-t konkluziónak és a Ji-ket igazolásoknak nevezik – ha ezek közül bármelyik igazolhatóan hamis, a konklúziót levonni nem szabad. A C-ben és a Ji-ben előforduló minden változónak P-ben is meg kell jelennie. A Nixon-gyémánt példáját alapértelmezett logikában egy ténnyel és két alapértelmezett szabállyal fejezhetjük ki:

Republikánus(Nixon) ∧ Kvéker(Nixon)

Republikánus(x) : ¬Pacifista(x)/ ¬Pacifista(x)

Kvéker(x) : Pacifista(x) /Pacifista(x)

Egy alapértelmezett szabály jelentésének interpretálásához az alapértelmezett elmélet kiterjesztését (extension) kell definiálnunk, az elmélet konklúzióinak maximális halmazaként. Egy S kiterjesztés tehát az eredetileg ismert tényekből és az alapértelmezett szabályokból levont konklúzióhalmazból áll úgy, hogy S-ből semmilyen más konklúziót levonni már nem lehet, és S-beli alapértelmezett konklúzió minden igazolása S-sel konzisztens. A körülírásban tárgyalt preferált modellekhez hasonlóan a Nixon-gyémántra két lehetséges kiterjesztésünk van: egy, amelyben pacifista és egy, amelyben nem az. Léteznek prioritásos sémák, ahol egyes alapértelmezett szabályoknak precedenciát lehet biztosítani más szabályokkal szemben, és ezzel a nem egyértelmű helyzeteket valamelyest fel lehet oldani.

1980 óta, amikor is a nemmonoton logikákat első ízben javasolták, igen nagy előrehaladás történt a matematikai tulajdonságuk megértésében. A késői 1990-es évektől kezdve a logikai programozáson alapuló gyakorlati rendszerek ígéretesnek bizonyultak a tudásreprezentációs eszközök szerepében. Vannak azonban még meg nem válaszolt kérdések. Így például ha „a gépkocsiknak négy kerekük van” hamis, mit is jelent, ha egy ilyen állítás a tudásbázis része? Milyen az alapértelmezett szabályok egy jó halmaza? Ha minden szabályról külön-külön nem tudjuk eldönteni, hogy a tudásbázisunkhoz tartozik-e, akkor igen komoly problémánk van a modularitás hiányával. Végül, hogyan lehet alapértelmezett státussal rendelkező hiedelmeket a döntéshozatalban felhasználni? Ez talán az alapértelmezett következtetés legnehezebb problémája. A döntések sokszor kompromiszszumokkal járnak együtt, és így szükség van különböző cselekvések eredményeként megjelenő hiedelmek erősségét összehasonlítani. Azokban az esetekben, amikor ugyanilyen jellegű döntésket sokszor hozunk meg, lehetőség adódik, hogy az alapértelmezett szabályokat „küszöb-valószínűségi” állításokként értelmezzük. Például „a fékjeim rendben vannak” alapértelmezett szabály valójában azt jelenti, hogy „annak a valószínűsége, hogy a fékjeim rendben vannak, feltéve, hogy más információm nincs, elegendően magas ahhoz, hogy az optimális döntés számomra az, hogy induljak útnak a fékek ellenőrzése nélkül”. Amikor a döntés kontextusa megváltozik – például amikor egy súlyosan megrakott teherkocsit vezetünk egy lejtős hegyi úton –, az alapértelmezett szabály hirtelen alkalmatlanná válik, akkor is, ha semmilyen új evidenciánk nincs, ami azt sugallná, hogy a fékek hibásak. Az ilyen mérlegelések néhány kutatót arra vezettek, hogy mérlegeljék, hogyan ágyazzák be az alapértelmezett következtetést a valószínűség-elméletbe.



[104] A felfedezőjéről, Keith Clarkról néha Clark-lezárásnak is nevezik.

[105] Jegyezzük meg, hogy ez egyben a 10.3. alfejezetben megadott követő állapot axiómák alakja is.

[106] Emlékezzünk vissza, hogy a monotonitás megköveteli, hogy minden vonzatállítás igaz maradjon, amikor a tudásbázishoz új állításokat adunk hozzá. Azaz ha TB α, akkor TBβα.

[107] A zárt világ feltételezésnél egy modell egy másiknál preferáltabb, ha kevesebb igaz atomja van – azaz a preferált modellek minimálmodellek. A CWA és a definit klóz tudásbázis között létezik természetes kapcsolat, mert az ilyen tudásbázisban az előrecsatolt következtetés révén elért fix pont az egyértelmű minimálmodell (7.5.2. szakasz - Előre- és hátrafelé láncolásrészben).

[108] A „gyémánt” elnevezés a két úton futó öröklődési lánc gráfszerű alakjától származik. (A ford.)