Bár az előzetes tudás felhasználása a tanulásban természetes témának tűnhet a tudományfilozófusok számára, mostanáig meglepően kevés formális eredmény született. Nelson Goodman filozófus a Fact, Fiction, and Forecast c. művében megcáfolta azt a korábbi feltételezést, miszerint az indukció nem más, mint egy univerzálisan kvantifikált kijelentés megfelelően sok példájának a megszemlélése és hipotézisként való elfogadása (Goodman, 1954).

Vegyük például azt a hipotézist, hogy „Minden smaragd zölék”, ahol a zölék azt jelenti, hogy „zöld, ha t idő előtt figyeljük meg, utána azonban kék”. A t idő előtt bármikor példák millióit láthatnánk, amelyek mind alátámasztják, hogy a smaragdok zölékek, negatív példák nélkül, mégis hezitálnánk a szabályt elfogadni. A jelenség csakis az indukciós folyamat szempontjából releváns a priori tudás szerepével magyarázható. Goodman a hasznosítható a priori tudás teljes választékát javasolja, a meghatározások túlzott hipotézisnek (overhypothesis) nevezett változatát is beleértve. Sajnos a gépi tanulással foglalkozó korai kutatásnál Goodman munkájára nem figyeltek fel.

A MAT gyökerei a tervkészítésnél használt STRIPS módszereihez nyúlnak vissza (Fikes és társai, 1972). Egy terv elkészítésével a terv egy általánosított változatát a tervek könyvtárában tárolták, és később makróoperátorként (macro-operator) a tervkészítésnél felhasználták. Hasonló ötletek Anderson ACT^* architektúrájában is megjelentek, tudáskompilálás (knowledge compilation) címen (Anderson, 1983) és SOAR architektúrájában tudásdarabolás (chunking) címen (Laird és társai, 1986). A sémabeszerzés (schema acquisition) (DeJong, 1981), az analitikus általánosítás (analytical generalization) (Mitchell, 1982) és a kényszeralapú általánosítás (constraint-based generalization) (Minton, 1984) a MAT tanulás irányában jelentkező és a (Mitchell és társai, 1986; DeJong és Mooney, 1986) publikációk stimulálta gyorsan növekvő érdeklődésnek közvetlen előfutárai voltak. A szövegben bemutatott MAT algoritmust Hirsh (Hirsh, 1987) vezette be, aki azt is megmutatta, hogy az algoritmust hogyan kell egy logikai programozási rendszerbe ágyazni. Van Harmelen és Bundy a MAT-ot a programelemző rendszerekben (Jones és társai, 1993) használt részleges kiértékelő (partial evaluation) módszer variánsaként magyarázzák (Van Harmelen és Bundy, 1988).

Az utóbbi időben a szigorú elemzés és a kísérleti kutatás a MAT jobb megértéséhez vezetett a problémamegoldás sebességében mért lehetséges költségeinek és előnyeinek terén. Minton azt mutatta meg, hogy hacsak tekintélyes munkát nem fektetünk bele, a MAT a programot lényegesen lelassíthatja (Minton, 1988). Tambe hasonló problémákkal küszködött a tudásdarabolásnál, és a szabálynyelv kifejezőerejének a mérséklését javasolta, hogy a szabályok munkamemóriához való illesztésének jelentős költségét minimálizáljuk (Tambe és társai, 1990). Erős a párhuzam ezen kutatás és az elsőrendű logika leszűkített változatának következtetési komplexitására vonatkozó jelenlegi eredményei között (lásd 9. fejezet). A MAT várható nyereségének formális valószínűségi elemzése a (Greiner, 1989; Subramanian és Feldman, 1990) munkákban található. Egy kiváló áttekintés Dietterichtől származik (Dietterich, 1990).

Ahelyett hogy a példákat mint az általánosítás fókuszpontjait tekintenénk, új problémák megoldására közvetlenül felhasználhatók az analógiás következtetés (analogical reasoning) elnevezésű megközelítésben. Az ilyen következtetésnek több változata is létezik. Idetartozik a hasonlóság mértékén alapuló plauzíbilis következtetés (Gentner, 1983) és a meghatározásokon alapuló deduktív következtetés (Davies és Russell, 1987), amely azonban megkívánja a példa jelenlétét ahhoz, hogy a belőle kialakított „lusta” MAT a régi példa általánosítását az új probléma szükségletei szerint irányítsa. Az analógiás következtetésnek ezt az utóbbi formáját általában meg lehet találni az esetalapú következtetésnél (case-based reasoning) (Kolodner, 1993) és a származtatási analógiánál (derivational analogy) (Veloso és Carbonell, 1993).

A releváns információval funkcionális függőségek formájában először az adatbázis-kutatásnál foglalkoztak, ahol ez a nagy attribútumhalmazok kezelhető részhalmazokra való strukturálásának eszköze volt. Funkcionális függőségeket analógiás következtetésre Carbonell és Collins, majd logikai színezettel Bobrow és Raphael használtak (Carbonell és Collins, 1973; Bobrow és Raphael, 1974). Davies és Russell (Davies, 1985; Davies és Russell, 1987) a függőségeket másoktól függetlenül újra felfedezték, és az analógiás következtetés szempontjából teljes körű logikai elemzésnek vetették alá. A függőségeket deklaratív elfogultság céljából Russell és Grosof használták (Russell és Grosof, 1987). A meghatározások és a leszűkített szótárral rendelkező hipotézistér közötti ekvivalenciát Russell (Russell, 1988) bizonyította be. A meghatározásokat tanuló algoritmust és az RADFT megnövelt hatékonyságát először a FOCUS algoritmusban mutatták be (Almuallim és Dietterich, 1991). Tadepalli a meghatározások tanulására egy ügyes algoritmust közölt, amely a tanulási sebességben igen lényeges javulást mutat (Tadepalli, 1993).

Az a gondolat, hogy az induktív tanulás kivitelezhető inverz dedukcióval W. S. Jevonsig vezethető vissza (Jevons, 1874), aki azt írta, hogy: „Mind a formális logika, mind a valószínűség-elmélet tanulmányozása arra az álláspontra juttatott engem, hogy egy olyan dolog, mint egy külön indukciós módszer, a dedukcióval szembeállítva nincs, és az indukció egyszerűen a dedukció egy fordított alkalmazása.” A számítástudományi elemzések Gordon Plotkin figyelemre méltó PhD-disszertációjával kezdődtek Edinburghban (Plotkin, 1971). Bár Plotkin számos, a mai ILP területén használt tételt és módszert dolgozott ki, az indukció egyes részproblémáira vonatkozó bizonyos eldönthetetlenségi eredmények elvették a kedvét. A MIS (Shapiro, 1981) újból bevezette a logikai programok tanulási problémáját, azonban ezt főleg az automatikus hibakeresés elméletéhez való hozzájárulásának tekintették. A szabályindukció kutatása, vagyis az olyan rendszerek, mint az ID3 (Quinlan, 1986) és CN2 (Clark és Niblett, 1989) a FOIL-hoz vezettek (Quinlan, 1990), amely első ízben tette lehetővé relációs szabályok gyakorlati indukcióját. A területet Muggleton és Buntine pezsdítették fel (Muggleton és Buntine, 1988). CIGOL programjuk az inverz rezolúció nem egészen teljes változatát tartalmazta, és új predikátumok generálására is alkalmas volt.^[193] A predikátum felfedezésével Wirth és O’Rorke is foglalkoztak (Wirth és O’Rorke, 1991). A következő nagyobb rendszer a GOLEM volt (Muggleton és Feng, 1990), amely a Plotkin-féle relatíve legkevésbé általános általánosítás ötletén alapuló lefedő algoritmust használja. A FOIL fentről lefelé módon, míg a CIGOL és a GOLEM lentről felfelé módon dolgoztak. E korszak más rendszerei az ITOU (Rouveirol és Puget, 1989) és a CLINT (De Raedt, 1992) rendszerek voltak. Újabban a PROGOL (Muggleton, 1995) az inverz vonzatreláció egy hibrid (fentről lefelé és lentről felfelé) megközelítését valósította meg, és a rendszert számos gyakorlati problémára alkalmazták, különösképpen a biológiában és a természetes nyelvfeldolgozásban. Muggleton a PROGOL egy kiterjesztését írja le (Muggleton, 2000), sztochasztikus logikai programok alakjában reprezentált bizonytalanság kezelésére.

Az ILP-módszerek formális elemzését (Muggleton, 1991) tartalmazza, míg a (Muggleton, 1992) egy nagy cikkgyűjtemény. A módszerek és az alkalmazások nagy gyűjteménye a (Lavrac és Dzeroski, 1994) könyv. A terület történetéről és a jövő kihívásairól újabb áttekintést ad (Page és Srinivasan, 2002). Haussler korai komplexitási eredményei azt sugallták, hogy az elsőrendű állítások tanulása reménytelenül bonyolult (Haussler, 1989). A klózokra vonatkozó különböző szintaktikai korlátozások jobb megértésével azonban pozitív eredmények is megjelentek, még a rekurziót tartalmazó klózokra is (Dzeroski és társai, 1992). Az ILP komplexitási eredményeiről Kietz és Dzeroski, valamint Cohen és Page írtak átfogó cikkeket (Kietz és Dzeroski, 1994; Cohen és Page, 1995).

Bár az ILP jelenleg a konstruktív indukció problémájának domináló megközelítése, nem csak ezzel próbálkoztak. Az ún. felfedező rendszerek (discovery systems) célja az új koncepciók tudományos felfedezésének általában a koncepció definícióterében történő közvetlen keresés útján történő modellezése. Doug Lenat AM (Automated Mathematician) programja (Davis és Lenat, 1982) szakértő szabályok formájában megfogalmazott felfedező heurisztikákat használt arra, hogy elemi számelméleti koncepciók és sejtések keresését irányítsa. Éles ellentétben a matematikai következtetésre kifejlesztett rendszerekkel, az AM nélkülözte a bizonyítás fogalmát, és csak sejtés szinten tudott működni. A program újra felfedezte a Goldbach-sejtést és az egyértelmű prímtényezőkre bontást. Az AM architektúráját később az EURISKO rendszerben (Lenat, 1983) általánosították, a rendszert a saját felfedező heurisztikákat átírni képes szabályokkal bővítve. Az EURISKO-t más, a matematikai felfedezéstől eltérő tartományokban is alkalmazták, de az AM-nél kisebb sikerrel. Az AM és az EURISKO módszertana vitatott, lásd (Ritchie és Hanna, 1984; Lenat és Brown, 1984).

A felfedező rendszerek egy másik csoportja a valós fizikai adatokkal való munkát célozza és új törvények felfedezését kísérli meg. A DALTON, a GLAUBER és a STAHL (Langley és társai, 1987) olyan szabályalapú rendszerek, amelyek fizikai rendszerekből származó adatokban kvantitatív összefüggéseket keresnek. Mindegyik rendszer képes volt egy tudomány történetéből jól ismert felfedezés újbóli meghozatalára. A probabilisztikus technikákon – különösképpen az új kategóriákat felfedező klaszterező algoritmusokon – alapuló felfedező rendszerekkel a 20. fejezetben foglalkozunk.

19.1.

Mutassa ki a konjunktív normál formába való átalakításával és a rezolúció alkalmazásával, hogy a 19.4. szakasz - Tanulás releváns információ alapján részben található és a brazilokra vonatkozó konklúzió helyes.

19.2.

Az alábbi meghatározás mindegyikére írja fel a meghatározás logikai reprezentációját, és magyarázza meg, hogy a meghatározás miért igaz (ha igaz egyáltalán).

19.3.

Hasznos lenne a meghatározásoknak egy valószínűségi verziója? Javasoljon egy definíciót.

19.4.

Pótolja a C₁ és/vagy C₂ klózok értékét az alábbi klózhalmazban, figyelembe véve, hogy C a C₁ és a C₂ rezolvense:

(a) C = Igaz ⇒ P(A, B), C₁ = P(x, y) ⇒ Q(x, y), C₂ = ??

(b) C = Igaz ⇒ P(A, B), C₁ = ??, C₂ = ??

(c) C = P(x, y) ⇒ P(x, f(y)), C₁ = ??, C₂ = ??

Ha több megoldás is lehetséges, a különböző eseteket külön példákkal illusztrálja.

19.5.

19.6.

Tegyük fel, hogy a FOIL program egy klózhoz egy literált úgy add hozzá, hogy egy bináris P predikátumot használ, és hogy az előbbi literálok (a klóz fejrészét beleértve) öt különböző változót tartalmaznak.

19.7.

A 19.11. ábrán látható családfa adatainak vagy annak részhalmazának felhasználásával alkalmazza az Őse predikátum megtanulására a FOIL algoritmust.