19.3. Magyarázatalapú tanulás
Ahogy a fejezet bevezetőjében elmagyaráztuk, a magyarázatalapú tanulás olyan módszer, ami megfigyelésekből általános szabályokat nyer ki. Tekintsük például az algebrai kifejezések egyszerűsítését és differenciálását (lásd 9.15. feladat). X2-et X szerint differenciálva 2X-et kapunk (vegyük észre, hogy az aritmetikai ismeretlent nagy X betűvel jelöljük az x logikai változótól megkülönböztetve). Egy logikai következtető rendszerben a célt így a KÉRDEZ(Derivált(X2, X) = d, TB) kifejezéssel fejezhetjük ki, ahol a megoldás a d = 2X.
Bárki, aki a differenciálszámítást ismeri, a megoldást „ránézésre” tudja. Az ilyen problémákkal első alkalommal találkozó hallgatónak vagy netán a tapasztalatot nélkülöző programnak sokkal nehezebb lesz a dolga. A differenciálás közismert szabályai segítségével a kifejezést előbb-utóbb az 1 × (2 × (X(2–1))) alakra lehet hozni, és ez előbb-utóbb elvezet minket a 2X-hez. A szerzők logikai programjának ez 136 bizonyítási lépésbe került, amiből 99 lépés a bizonyítás zsákutca elágazásaira esett. Ezt tapasztalva azt szeretnénk, ha a program ugyanennek a problémának a megoldását a következő alkalommal lényegesen gyorsabban adná meg.
A memoizálás (memoization) módszerét a számítógép-tudományban régóta alkalmazzák, miszerint a számítások meggyorsíthatók az eredmények eltárolása révén. A memofüggvény alapgondolata, hogy bemenet/kimenet párokat gyűjtünk ki egy külön adatbázisba. Meghíváskor a függvény először megvizsgálja az adatbázist, hátha a probléma teljes újbóli megoldását így meg tudja kerülni. A magyarázatalapú tanulás ezt az ötletet továbbfejleszti úgy, hogy egy általános szabályt fogalmaz meg, amely az esetek egész osztályát képes lefedni. A differenciálás esetében a memoizálás emlékezne ugyan arra, hogy az X2-nek X szerinti deriváltja 2X, a Z2 Z szerinti deriváltjának kiszámítását azonban teljes egészében az ágensre hagyná. Célszerű lenne, ha egy olyan általános szabályt[190] tudnánk megfogalmazni, amely minden lehetséges u aritmetikai ismeretlen esetén megadná, hogy az u2-nek u szerint deriváltja 2u. A logikában ezt az alábbi szabállyal fejezhetjük ki:
AritmetikaiIsmeretlen(u) ⇒ Derivált(u2, u) = 2u
Ha a tudásbázis rendelkezik egy ilyen szabállyal, akkor minden új eset, ami a szabály egy példánya, azonnal megoldható.
Fontos
Természetesen ez csupán egy triviális példa egy igen általános jelenségre. Ha egyszer megértettünk valamit, azt általánosítva más körülmények között is felhasználhatjuk. Egy „nyilvánvaló” megoldási lépést kapunk, amely építőkockaként felhasználható bonyolultabb problémák megoldásában. Alfred North Whitehead, aki Bertrand Russell-lel együtt a Principia Mathematica társszerzője – talán a Zog felfedezése jellegű események megértéséhez saját magára alkalmazva a MAT elvét – azt írta, hogy „A civilizáció azáltal halad előre, hogy szaporítja azoknak a fontos cselekvéseknek a számát, amelyeket gondolkodás nélkül véghezvihetünk” (Whitehead, 1911). Ha ön, kedves olvasó, a deriválási példa lényegét megértette, akkor az agya már buzgón azon dolgozik, hogy megkísérelje a magyarázatalapú tanulás általános elvét kinyerni ebből a példából. Figyelje meg, hogy hacsak nem lényegesen okosabb a szerzőknél, a magyarázatalapú példa bemutatása előtt még nem ismerte fel a MAT-ot. A Zogot figyelő ősemberekhez hasonlóan önnek (és nekünk is) egy példát kellett látnunk, mielőtt az alapelvet meg tudtuk fogalmazni. Ez azért van így, mert megmagyarázni, hogy miért jó egy ötlet, sokkal könnyebb, mint magát az ötletet megfogalmazni.
A MAT alapötlete az, hogy először az előzetes tudásra alapozva megkonstruáljuk a megfigyelés magyarázatát, majd meghatározzuk annak az esetosztálynak a definícióját, amelyre a megkonstruált magyarázat alkalmazható. A definíció alapul szolgál az osztály eseteit lefedő szabály számára. A „magyarázat” lehet egy logikai bizonyítás, de általánosságban lehet akármilyen következtetési vagy problémamegoldó folyamat, feltéve, hogy a lépései jól definiáltak. Kulcsfontosságú azoknak a szükséges feltételeknek az azonosítása, amelyek révén az egyes lépések más esetre is alkalmazhatók lesznek.
Következtető rendszerként a 9. fejezetben leírt egyszerű, hátrahaladó tételbizonyító rendszert fogjuk használni. A Derivált(X2, X) = 2X bizonyítási fája túlságosan nagy ahhoz, hogy példaként szerepeljen, ezért az általánosítás módszertanát egy valamivel egyszerűbb példával fogjuk illusztrálni. Tegyük fel, hogy az 1 × (0 + X) kifejezést akarjuk egyszerűsíteni. A tudásbázis az alábbi szabályokat tartalmazza:
Átírás(u, v) ∧ Egyszerűsítés(v, w) ⇒ Egyszerűsítés(u, w)
Primitív(u) ⇒ Egyszerűsítés(u, u)
AritmetikaiIsmeretlen(u) ⇒ Primitív(u)
Szám(u) ⇒ Primitív(u)
Átírás(1 × u, u)
Átírás(0 + u, u)
.
.
.
Annak bizonyítása, hogy a válasz X, a 19.7. ábra felső részében látható. A MAT-módszer egyidőben két bizonyítási fát konstruál. A második bizonyítási fa a szabad változókkal rendelkező célt használja, ahol az eredeti cél konstansait változókkal helyettesítettük. Ahogy az eredeti bizonyítás halad előre, úgy halad a szabad változós bizonyítás is, pontosan ugyanazokat a szabályokat alkalmazva. Lehetséges, hogy néhány változót közben le kell kötni. Ahhoz, hogy az Átírás(1 × u, u) szabályt használhassuk, az Átírás(x × (y + z), v) részcél x változóját 1-re kell lekötni. Hasonlóképpen az Átírás(y + z, v') részcél y változóját 0-ra kell lekötni, ha az Átírás(0 + u, u) szabályt szeretnénk alkalmazni. Az általánosított bizonyítási fa birtokában a levelekből (a szükséges kötéseket figyelembe véve) a célpredikátum általános szabályát képezzük:
Átírás(1 × (0 + z),0 + z) ∧ Átírás(0 + z, z) ∧ AritmetikaiIsmeretlen(z)
⇒ Egyszerűsítés(1 × (0 + z), z)
Vegyük észre, hogy a bal oldal első két feltétele igaz függetlenül attól, hogy z-nek mi az értéke. Így ezeket kihagyhatjuk a szabályból, és eredményül azt kapjuk, hogy:
AritmetikaiIsmeretlen(z) ⇒ Egyszerűsítés(1 × (0 + z), z)
Általánosságban elmondható, hogy a végleges szabályból azok a feltételek hagyhatók ki, amelyek nem jelentenek kényszert a szabály jobb oldalán lévő változókra vonatkozólag. Az eredményül kapott szabály továbbra is igaz, sőt még hatékonyabb is lesz. Vegyük észre azt is, hogy az AritmetikaiIsmeretlen(z) feltétel nem hagyható ki, hiszen a z-nek nem minden lehetséges értéke aritmetikai ismeretlen. A z más jellegű értékei esetén feltehetően más egyszerűsítési szabályokat kellene alkalmazni – például ha z netán 2 × 3 lenne, akkor az 1 × (0 + (2 × 3)) helyes egyszerűsítése 6, és nem 2 × 3 lenne.
Összegezve, az alap MAT-módszer a következőképpen működik:
-
Ha adott egy példa, a rendelkezésre álló háttértudást felhasználva konstruáljunk egy bizonyítást arra, hogy a célpredikátum érvényes a példára.
-
Az előbbivel egy időben az eredeti bizonyítás következtetési lépéseivel azonos lépéseket alkalmazva konstruáljuk meg a szabad változós cél általánosított bizonyítási fáját.
-
Konstruáljuk meg az új szabályt úgy, hogy a szabály bal oldala a fa leveleiből áll, a jobb oldala viszont a szabad változós cél (az általánosított bizonyítás változókötéseit figyelembe véve).
-
Hagyjuk ki azokat a feltételeket, amelyek a célban foglalt változók értékeitől nem függnek.
19.7. ábra - Az egyszerűsítési probléma bizonyítási fái. Az első fa az eredeti problémapéldány bizonyítása, amiből az AritmetikaiIsmeretlen(z) ⇒ Egyszerűsítés(1 × (0 + z), z) vezethető le. A második fa az a bizonyítás, amikor az eredeti problémapéldányban szereplő összes konstanst változókkal helyettesítettük, amiből viszont további szabályok sokaságát vezethetjük le.
A 19.7. ábrán látható általánosított bizonyítási fából több általánosított szabályt is képesek vagyunk kinyerni. Ha a fa jobb oldali ágának növekedését leállítjuk, vagy az ágat lemetsszük (prune), amikor Primitív lépéshez jutottunk, az alábbi szabályt kapjuk:
Primitív(z) ⇒ Egyszerűsítés(1 × (0 + z), z)
Ez a szabály annyira érvényes, mint az AritmetikaiIsmeretlen-t felhasználó szabály, bár annál általánosabb, mivel olyan esetekre is vonatkozik, amikor z numerikus értékű. Még általánosabb szabályokat is kinyerhetünk, ha az Egyszerűsítés(y + z, w) után metszünk. Ekkor a szabály:
Egyszerűsítés(y + z, w) ⇒ Egyszerűsítés(1 × (y + z), w)
Általánosságban elmondható, hogy szabályokat az általánosított bizonyítási fa bármely részfájából nyerhetünk. Szembe kell néznünk azonban azzal a problémával, hogy ezek után melyik szabályt válasszuk.
Az a döntés, hogy melyik szabályt érdemes létrehozni, végső soron a hatékonyságon múlik. A MAT által biztosított hatékonyságnövekedésnek három tényezője van:
-
A tudásbázishoz nagyszámú szabály hozzáadása a következtetési folyamatot lelassíthatja, mivel a következtetési mechanizmusnak ezeket a szabályokat akkor is meg kell vizsgálnia, amikor ezek nem járulnak hozzá a megoldáshoz. Másképpen fogalmazva, a keresési tér elágazási tényezője (branching factor) ilyenkor növekszik.
-
Ahhoz, hogy ezt a jelenséget kompenzáljuk, a létrehozott szabályoknak lényeges sebességnövekedést kell garantálniuk az általuk lefedett problémapéldányok esetében. Az ilyen sebességnövekedés főleg abból származik, hogy a származtatott szabályok révén elkerülhetjük azokat a holtágakat, amelyekbe különben a bizonyítás során belemennénk, illetve abból, hogy a bizonyítások rövidebbek lesznek.
-
A származtatott szabályoknak a lehető legáltalánosabbaknak kell lenniük, hogy a lehető legnagyobb esethalmazt fedjék le.
A származtatott szabályok hatékonyságát megszokott módon úgy biztosíthatjuk, hogy megköveteljük a szabály minden részcéljától, hogy hatásos (operational) legyen. Durván fogalmazva, egy cél hatásos, ha „könnyű” megoldani. A Primitív(z) részcélt például könnyű megoldani, a megoldásához két lépés elegendő. Ezzel szemben az Egyszerűsítés(y + z, w) részcél tetszőleges számú következtetéshez vezethet az y és a z értékeinek függvényében. Ha az általánosított bizonyítás megkonstruálásakor a hatásossági tesztet minden lépésnél elvégezzük, az ágat azonnal lemetszhetjük, amint egy hatásos részcélra rátaláltunk. A hatásos részcélt ilyenkor az új szabály egy konjunktív elemeként megtartjuk.
Sajnos a hatásosság és az általánosság között általában kompromisszumot kell kötni. A konkrétabb részcélokat könnyebb megoldani, viszont azok kevesebb esetet fednek le. A hatásosság tovább fokozható; egy vagy két lépés nyilvánvalóan hatásos, de mi a helyzet 10-zel vagy 100-zal? Egy adott részcél megoldásának a költsége végül attól függ, hogy a tudásbázis milyen egyéb szabályokat tartalmaz. A költség növekedhet vagy csökkenthet, ahogy a tudásbázishoz új szabályokat adunk. Az adott kezdeti tudásbázis hatékonyságának maximalizálásánál a MAT-rendszerek valóban igen komplex optimizációs problémával kerülnek szembe. Néha megalkotható annak matematikai modellje, hogy egy adott szabály hozzáadása általában milyen hatással van a hatékonyságra, és ennek a modellnek a használatával a hozzáadandó legjobb szabály megválasztható. Az elemzés azonban igen komplikált lehet, különösképpen ha rekurzív szabályokkal van dolgunk. Ígéretes megközelítés a hatékonyság empirikus vizsgálata, amikor néhány szabály hozzáadásával meggyőződünk arról, hogy a szabályok közül melyik az, amelyik ténylegesen hasznos, és amelyik az eljárásokat felgyorsítja.
Fontos
A hatékonyság empirikus elemzésének gondolata a MAT lényegét érinti. Amit eddig informálisan „az adott tudásbázis hatékonyságának” neveztünk, az nem más, mint egy átlagos esetkomplexitás a megoldandó problémák egy eloszlásán mérve. A régi példák általánosításával a MAT növeli a tudásbázis hatékonyságát a jövőben ésszerűen várható problémák szempontjából. Az ötlet addig jó, amíg a régi példák eloszlása durván megegyezik a jövőbeli példák eloszlásával. Ez a feltételezés azonos azzal, amit a 18.5. alfejezetben a VKH-tanulás kapcsán megtettünk. Ha a MAT-rendszert gondosan kivitelezték, a későbbi problémáknál lényeges javulás érhető el. Egy nagyon nagy méretű, svéd és angol nyelv közötti beszédfordításra kifejlesztett, Prolog-alapú, természetes nyelvi rendszerben például, a valós idejű fordítási képességet csak az elemző folyamatra alkalmazott MAT révén sikerült elérni (Samuelsson és Rayner, 1991).
[190] Természetesen az un általános szabályát is meg tudnánk valósítani, a mondanivalót azonban a közölt példa is jól illusztrálja.
