Az 1. fejezet felvázolta az induktív tanulás filozófiai vizsgálatának történetét. William of Ockham (1280–1349) volt korának legnagyobb hatású filozófusa és a középkori ismeretelmélet, a logika és a metafizika egyik nagy alakja. Neki tulajdonítják azt a mondást, ami „Ockham borotvája” néven rögzült a köztudatban. Latinul: Entia non sunt multiplicanda praeter necessitatem, ami azt jelenti magyarul, hogy „A dolgokat nem kell a szükségesnél jobban bonyolítani”. Sajnos ez a dicséretes mondás sehol sem található meg a műveiben pontosan így megfogalmazva.

Az EPAM (Elementary Perceiver And Memorizer, Elemi észlelő és megjegyző) volt az első rendszerek egyike, amely döntési fákat (diszkriminációs hálókat, discrimination nets) használt (Feigenbaum, 1961). Az EPAM létrehozásának célja az emberi fogalom-tanulás kognitív-szimulációs modelljének megalkotása volt. A CLS-rendszer (Hunt és társai, 1979) heurisztikus előretekintő eljárást használt a döntési fák konstrukciójára. Az ID3 (Quinlan, 1979) hozta azt a kulcsfontosságú ötletet, hogy a heurisztikus függvény használja az információtartalmat. Az információelméletet Claude Shannon fejlesztette ki a kommunikáció tanulmányozására (Shannon és Weaver, 1949). (Shannon hozzájárult a gépi tanulás területéhez is, az egyik legkorábbi példát szolgáltatva mechanikus egerével, amely egy útvesztőben navigált a kísérlet-kudarc elvet használva.) A döntési fák χ² metszését Quinlan írta le először (Quinlan, 1986). Az ipari felhasználásra alkalmas C4.5 döntési fa programcsomag is Quinlan munkáiban található meg (Quinlan, 1993). A döntési fa tanulásnak egy, az előzőktől független hagyománya alakult ki a statisztikusok körében. A Classification and Regression Trees (Breiman és társai, 1984), amelyet röviden „CART könyv”-nek neveznek, az alapvető irodalom e tekintetben.

A tanulás számos másik algoritmikus megközelítését is vizsgálták. A pillanatnyilag-legjobb-hipotézis (current-best-hypothesis) megközelítés egyetlen hipotézissel foglalkozik, specializálva, ha túl tágnak bizonyul, általánosítva, ha túl szűk. Ez a filozófiában már régóta ismert elv (Mill, 1843). A kognitív pszichológia korai munkájában szintén ezt javasolták, mint az emberi fogalom tanulás természetes formáját (Bruner és társai, 1957). Az MI-területen ez a megközelítés elsősorban Patrick Winston munkájához köthető, aki PhD-disszertációjában (Winston, 1970) a komplex objektumok leírásának tanulásával foglalkozott. A verziótér (version space) módszer (Mitchell, 1977; 1982) eltérő megközelítésen alapul, az összes konzisztens hipotézissel egyszerre foglalkozik, elhagyva azokat, amelyek az új példákkal inkonzisztenciát mutatnak. Ezt a megközelítést a META-DENDRAL kémiai szakértő rendszerben használták (Buchanan és Mitchell, 1978), majd később Mitchell LEX rendszerében (Mitchell, 1983), ami matematikai analízis problémák tanulással történő megoldását célozta. A harmadik nagyhatású irányzat kialakítása Michalski és társai munkájához köthető, akik az AQ algoritmusok sorozatával foglalkoztak, amelyek logikai szabályok halmazát tanulták (Michalski, 1969; Michalski és társai, 1986b).

Az együttes tanulás a tanuló algoritmusok teljesítménynövelésének egyre népszerűbb módszere. A zsákolás (bagging)^[187] (Breiman, 1966) az első hatékony módszer, amely többféle indító (bootstrap) adathalmaz alapján megtanult hipotézisek kombinációját hozza létre. Ezeket az adathalmazokat az eredeti alulmintavételezésével állítják elő. A fejezetben ismertetett turbózás (boosting) módszere eredetileg Schapire elméleti munkájából (Schapire, 1990) származik. Az AdaBoost algoritmust Freund és Schapire dolgozta ki (Freund és Schapire, 1996), és Schapire adta meg elméleti analízisét (Schapire, 1999). Friedman és társai statisztikai alapon tárgyalják a turbózás módszerét (Friedman és társai, 2000).

A tanulási algoritmusok elméleti vizsgálata Gold munkájával kezdődött (Gold, 1967) az identifikáció határátmenetben (identification in the limit) probléma tanulmányozásával. Ez a megközelítés ugyan részben tudományfilozófiai felfedezésből eredt (Popper, 1962), de alkalmazásának legfőbb területe nyelvtanok példamondatok alapján történő tanulása volt (Osherson és társai, 1986).

Míg az identifikáció határátmenetben megközelítés a végső konvergenciára koncentrál, addig a Kolmogorov-komplexitás (Kolmogorov complexity) vagy más néven algoritmikus komplexitás (algorithmic complexity), amelyet egymástól függetlenül Solomonoff (1964) és Kolmogorov (1965) fejlesztett ki, formális definíciót próbál adni az Ockham borotvája elvben használt egyszerűségnek. Hogy valahogy kimeneküljenek abból a csapdából, hogy az egyszerűség függ az információ reprezentációjának módjától, azt javasolták, hogy az egyszerűséget annak a legrövidebb programnak a hosszával mérjék, amely egy általános Turing-gépen helyesen adja vissza a megfigyelt adatokat. Bár sok különböző általános Turing-gépet lehet létrehozni, és így több különböző „legrövidebb” program lehetséges, ezek hossza legfeljebb csak egy konstansban tér el, amely független az adatok mennyiségétől. Ezt a gyönyörű eredményt, amely betekintést nyújt abba, hogy bármely előzetes reprezentációs eltérést végül maguk az adatok győznek le, csupán az teszi tönkre, hogy a legrövidebb program hosszának kiszámítása eldönthetetlen problémára vezet. Közelítő mértékeket lehet alkalmazni, például a legrövidebb leíró hosszt (minimum description length) vagy LLH-t (Rissanen, 1984), amivel kimagasló gyakorlati eredményeket értek el. Li és Vitányi írása a Kolmogorov komplexitás legjobb összefoglalása (Li és Vitányi, 1993).

A tanulás számítási elméletét – azaz a VKH-tanulás elméletét – Lesli Valiant vezette be (Valiant, 1984). Valiant munkája a számítási komplexitásra és a mintakomplexitásra helyezte a fő hangsúlyt. Michael Kearnsszel együtt Valiant megmutatta, hogy számos olyan fogalomosztály van, amely VKH-tanulással nem kezelhető probléma, még akkor sem, ha a példák elegendő információt nyújtanak. Bizonyos problémaosztályokban, például döntési listáknál, elértek néhány pozitív eredményt (Rivest, 1987).

A mintakomplexitás vizsgálatának ettől független tradícióját találhatjuk a statisztikusok körében, amely az egyenletes konvergencia elméletének (uniform convergence theory) vizsgálatával kezdődött (Vapnik és Cservonenkis, 1971). Az úgynevezett VC-dimenzió nagyjából a VKH tanulásból származó mértékhez hasonló – bár annál általánosabb – mértéket ad. A VC-dimenzió, ellentétben a VKH-analízissel, folytonos függvényosztályokra is alkalmazható. A VKH-analízis és a VC elmélet között először a „négy német”, Blumer, Ehrenfeucht, Haussler és Warmuth (1989) teremtett kapcsolatot (akik közül valójában egyik sem német). A VC elmélet további fejlődése vezetett a szupport vektorgép vagy SVM^[188] (support vector machine) kidolgozásához (Boser és társai, 1992; Vapnik, 1998). A szupport vektorgéppel a 20. fejezetben foglalkozunk.

Nagyon sok, a gépi tanulással foglalkozó fontos publikációt gyűjtöttek egybe a Readings in Machine Learning c. kötetben (Shavlik és Dietterich, 1990). A kétkötetes Machine Learning 1 (Michalski és társai, 1983), illetve Machine Learning 2 (Michalski és társai, 1986a) is sok fontos közlést tartalmaz, továbbá hatalmas bibliográfiát. Weiss és Kulikowski a függvény tanulás áttekinthető bevezetését adja gépi tanulási, statisztikai és neurális alapokon (Weiss és Kulikowski, 1991). A STATLOG projektben (Michie és társai, 1994) végezték a tanuló algoritmusok teljesítményének messze legkimerítőbb összehasonlítását. A jelenleg is folyó, a gépi tanulással foglalkozó fontos kutatási eredmények az International Conference on Machine Learning éves kiadványaiban, a Neural Information Processing Systems konferencián, a Machine Learning és a Journal of Machine Learning Research folyóiratokban, továbbá a fontosabb MI-újságokban jelennek meg. A tanulás számítási elméletének eredményei megjelennek az éves ACM Workshop on Computational Learning Theory (COLT) kiadványokban, valamint Kearns és Vazirani (1994), továbbá Anthony és Bartlett (1999) publikációiban.

18.1.

Vizsgálja meg a beszélni, illetve egy nyelvet megérteni tanuló gyerek problémáját! Magyarázza meg, hogy ez a folyamat hogyan illeszkedik az általános tanulási modellhez, és megfelelően azonosítsa a modell egyes komponenseit!

18.2.

Ismételje meg a 18.1. feladatot a tenisz (vagy valamilyen ön által ismert sport) tanulásának esetére! Ez felügyelt vagy megerősítéses tanulás?

18.3.

Rajzoljon fel egy döntési fát arra a problémára, hogy az útkereszteződésben elinduljunk-e előre, ha a lámpa éppen most váltott zöldre!

18.4.

Soha nem teszteljük kétszer ugyanazt az attribútumot a döntési fa egy útvonala mentén. Miért?

18.5.

Tegyük fel, hogy egy döntési fa segítségével generálunk egy tanító mintahalmazt, majd döntési fa tanulást alkalmazunk erre a halmazra. A tanulási algoritmus végül is a helyes döntési fát fogja visszaadni, ha a tanító halmaz mérete a végtelenhez tart? Miért, vagy miért nem?

18.6.

Egy jó „butácska” tanulási algoritmus a következő: készítsünk egy táblázatot az összes tanítópéldából. Vizsgáljuk meg, hogy milyen kimenet szerepel a legtöbbször a tanítópéldákban: jelöljük ezt d-vel. Ezek után, ha olyan minta jelenik meg a bemeneten, ami nincs a táblázatban, akkor adjunk vissza d-t. Olyan bemenetekre, amelyek megtalálhatók a táblában, adjuk vissza a táblázatban a bemenethez asszociált kimeneti értéket (vagy ha egynél több kimeneti érték van azonos bemenethez, akkor a leggyakrabban előfordulót). Implementálja ezt az algoritmust, és vizsgálja meg egy példának választott területen (például az étterem problémán) azt, hogy mennyire működik jól! Ennek alapján fogalmat alkothatunk a tanulás területének alapszintjéről – a minimális elvárható teljesítményről, amelyet minden tanuló algoritmusnak el kell érnie.

18.7.

Tegyük fel, hogy egy új algoritmussal tanulási kísérletet folytat. Egy adathalmazt használ, amiben 25-25 példa van az előforduló két osztályra. Azt tervezi, hogy a hagyj-ki-egyet keresztvalidációs módszert fogja használni. Összehasonlítási alapként egy egyszerű többségi szavazót használ. (A többségi szavazónak megadva egy tanító halmazt, a bemenetektől függetlenül mindig azt a kimenetet adja, amely kimeneti érték a halmazban legtöbbször előfordul.) Azt várta, hogy a többségi szavazó, a hagyj-ki-egyet keresztvalidációban nagyjából 50%-ot fog elérni, de meglepetésére 0% az eredmény. Meg tudja magyarázni, hogy miért?

18.8.

A döntési fák rekurzív előállítása során néha előfordul, hogy pozitív és negatív példák vegyes halmaza marad egy levélcsomópontban, még akkor is, ha az öszszes attribútumot használtuk már. Tegyük fel, hogy p pozitív és n negatív példánk van.

18.9.

Tegyük fel, hogy egy tanulási algoritmus konzisztens hipotézist keres, és az osztályozandó példákat véletlen módon generáljuk. A példákat egyenletes eloszlással választjuk az n Boole-attribútum alapján kialakított 2n példa lehetőségből. Számítsa ki, hány példa kell ahhoz, hogy egy ellentmondás felmerülésének a valószínűsége 0,5 legyen!

18.10.

Tegyük fel, hogy egy attribútum a példák E halmazát E_i részhalmazokra bontja, és mindegyik részhalmazban p_i pozitív és n_i negatív példa van. Mutassa meg, hogy ha a p_i/(p_i + n_i) arány nem egyforma minden i-re, akkor az attribútum információnyeresége biztosan pozitív!

18.11.

Módosítsa a DÖNTÉSI-FA-TANULÁS algoritmust úgy, hogy tartalmazza a χ² metszést! A részleteket megtalálhatja Quinlan írásában (Quinlan, 1986).

18.12.

18.13.

A 18. fejezetben megmutattuk, hogy azok az attribútumok, amelyeknek nagyon sokféle lehetséges értékük van, problémát jelenthetnek az információnyereség számításánál. Ezek az attribútumok jó eséllyel nagyon sok kis osztályra, akár egyelemű osztályokra bontják a halmazt, ezért úgy tűnik a nyereség számításánál, hogy nagyon fontosak az adott csomópontban. A nyereségarány (gain ratio) kritérium az attribútumokat az általuk hozott információnyereség és a saját belső információtartalmuk arányával méri. A belső információtartalom arra a kérdésre adott válasz, hogy „Mi az értéke ennek az attribútumnak?”. A nyereségarány kritérium ennek megfelelően azt próbálja mérni, hogy mennyire hatékony információt biztosít a példa helyes osztályozásához ez az attribútum. Alkossa meg az attribútum információtartalmának matematikai kifejezését, és módosítsa a DÖNTÉSI-FA-TANULÁS algoritmust nyereségarány-alapúra!

18.14.

Egy együttes tanulási algoritmust vizsgál, amely M megtanult hipotézis eredményének egyszerű többségi szavazását használja. Tegyük fel, hogy az összes hipotézisnek a hibája, és az egyes hipotézisek által elkövetett hibák függetlenek a többiek hibájától. Adja meg M és ε függvényében azt az összefüggést, amelylyel az együttes tanulással előállított eszköz hibája számítható, és számítsa ki M = 5, 10 és 20, illetve ε = 0,1, 0,2 és 0,4 esetén! Ha feladjuk a függetlenségre vonatkozó feltételezést, akkor előfordulhat-e, hogy az együttes hibája rosszabb lesz, mint ε?

18.15.

Ez a feladat a döntési listák kifejező erejével foglalkozik (lásd 18.5. alfejezet).