18.2. Induktív tanulás
Egy determinisztikus, felügyelt tanulást végző algoritmus bemenetként megkapja az ismeretlen függvény bizonyos bemeneti értékekhez tartozó válaszait, feladata az ismeretlen függvény – vagy ahhoz nagyon közel álló leképezés – előállítása. Formálisan azt mondjuk, hogy egy minta (example) nem más, mint egy (x, f(x)) értékpár, ahol x a bemeneti érték, míg f(x) az x-re alkalmazott függvény kimeneti értéke. A tisztán induktív következtetés (pure inductive inference) (vagy indukció [induction]) feladata a következő:
Adott az f-re vonatkozó minták egy halmaza, ennek alapján határozzunk meg egy h függvényt, amely közelíti f-et.
A h függvényt hipotézisnek (hypothesis) nevezzük. A tanulás nehézsége elvi szempontból abban áll, hogy nem könnyű egy adott h függvényről megmondani, hogy jól approximálja-e f-et. Egy jó hipotézis jól általánosít (generalize) – azaz jó becslést kapunk a még nem látott mintákra is. Ez az induktív következtetés alapproblémája (problem of induction). A problémát már évszázadok óta kutatják, a 18.5. alfejezet egy részmegoldást szolgáltat.
18.1. ábra - (a) Példa (x, f(x)) értékpárok és egy velük konzisztens lineáris hipotézis. (b) Egy – ugyanazokkal az adatokkal konzisztens – hetedfokú polinom. (c) Egy másik adathalmaz egy pontosan illeszkedő hatodfokú polinommal, illetve egy közelítő lineáris illesztéssel. (d) Egy egyszerű szinuszos illesztés ugyanazokra az adatokra.
Fontos
A 18.1. ábra ismert példát mutat be: egy adathalmazra egyváltozós függvényt illesztünk. A minták (x, f(x)) értékpárok, ahol mind x, mind f(x) valós értékek. Legyen a H hipotézistér (hypothesis space H) – azon hipotézisek halmaza, amelyeket meg fogunk vizsgálni – a legfeljebb k-ad fokú polinomok tere. (Például 3x2 + 2, x17 – 4x3 stb.) A 18.1. (a) ábra valamilyen adatokat és egy az adatokra pontosan illeszkedő egyenes vonalat (elsőfokú polinom) mutat. Ez a vonal itt egy konzisztens (consistent) hipotézis, mivel valamennyi adatra illeszkedik. A 18.1. (b) ábra egy nagy fokszámú polinomot mutat, amely szintén konzisztens ugyanazokra az adatokra nézve. Ez a két példa illusztrálja az induktív tanulás első komoly megoldandó kérdését: hogyan válasszunk több konzisztens hipotézis közül? Egy lehetséges válasz az ún. Ockham borotvája[182] (Ockham’s razor) elv: részesítsük előnyben a legegyszerűbb olyan hipotézist, amely konzisztens az adatokkal. Ez józan intuíciónak tűnik, mivel azok a hipotézisek, amelyek nem egyszerűbbek, mint maguk az adatok, nem nyernek ki semmilyen mintázatot az adatokból. Az egyszerűség definíciója nem könnyű, de értelmesnek tűnik azt mondani, hogy egy elsőfokú polinom egyszerűbb, mint egy 12-ed fokú.
Fontos
A 18.1. (c) ábra egy másik adathalmazt mutat. Ezekre az adatokra nem lehet konzisztens módon egyenest illeszteni, valójában egy hatodfokú polinomra (amely 7 szabad paraméterrel rendelkezik) van szükség a pontos illesztéshez. A halmazban csak 7 adat van, így a polinomnak épp annyi paramétere van, ahány adatpont. Ennek megfelelően úgy tűnik, hogy nem sikerül valamilyen mintázatot találnunk az adathalmazban, így nem várunk jó általánosítóképességet. Jobban járhatunk, ha inkább egy egyszerű egyenest illesztünk, amely ugyan nem konzisztens, de ésszerű becsléseket adhat. Ez azt valószínűsíti, hogy a keresett függvény nem determinisztikus (vagy ami ezzel közelítőleg ekvivalens: a valódi bemeneti minták nem figyelhetők meg teljes pontossággal). Nemdeterminisztikus függvények esetén elkerülhetetlen, hogy kompromisszumot kössünk a hipotézis komplexitása és az adatokhoz való illeszkedés pontossága között. A 20. fejezetben bemutatjuk, hogy ezt a kompromisszumot hogyan lehet a valószínűség-számítás elméletének felhasználásával kialakítani.
Észben kell tartanunk, hogy egy egyszerű, konzisztens hipotézis megtalálásának esélye erősen függ a választott hipotézistértől. A 18.1. (d) ábra bemutatja, hogy a (c) alatti adatokra pontosan illeszthető egy egyszerű ax + b + c sin(x) alakú függvény. Ez a példa jól mutatja a hipotézistér jó megválasztásának fontosságát. Ha olyan hipotézisteret választunk, amely véges fokszámú polinomokat tartalmaz, akkor szinuszos függvényeket nem tudunk pontosan reprezentálni. Így egy olyan tanuló, amelyik ezt a hipotézisteret használja, nem fog tudni szinuszos adatokból tanulni. Egy tanulási problémát realizálhatónak (realizable) nevezünk, ha a hipotézistérnek eleme az igazi függvény, különben a problémát nem realizálhatónak (unrealizable) nevezzük. Sajnos nem mindig tudjuk megmondani, hogy egy tanulási probléma realizálható-e, mivel nem ismerjük a valódi függvényt. Egy lehetőség e korlát túllépésére az a priori tudás felhasználása. Ennek segítségével olyan hipotézisteret alkotunk, amelyről tudjuk, hogy tartalmazza az igazi függvényt. Ezt a témát a 19. fejezetben tárgyaljuk.
Fontos
Egy másik lehetséges megközelítés, hogy a lehető legnagyobb hipotézisteret használjuk. Például miért ne legyen a H hipotézisterünk az összes Turing-gépek osztálya? Végül is minden kiszámítható függvény reprezentálható valamilyen Turing-géppel, tehát ez a legjobb, amit tehetünk. Ennek a megközelítésnek az a problémája, hogy nem veszi figyelembe a tanulás számítási komplexitását. Kompromisszumot kell kötnünk a hipotézistér kifejezőképessége és egyszerű konzisztens hipotézisek megtalálásának komplexitása között. Például: egyenesek illesztése az adatokra könnyen megoldható, nagy fokszámú polinomok illesztése nehezebb, Turing-gépek illesztése pedig nagyon nehéz. Ugyanis annak eldöntése, hogy egy adott Turing-gép konzisztens-e az adatokkal, általánosságban még csak nem is lehetséges. Egy másik ok, ami miatt előnyben részesítjük az egyszerű hipotézistereket, hogy az eredményképp kapott hipotézisek használata is egyszerűbb lehet – könnyebb kiszámítani h(x)-et, ha h egy lineáris függvény, mint ha egy tetszőleges Turing-gép programja lenne.
Ezen okokból a legtöbb tanulással foglalkozó eddigi kutatás a viszonylag egyszerű hipotézisreprezentációkra helyezte a fő hangsúlyt. Ebben a fejezetben az ítéletlogikára és az ehhez kapcsolódó nyelvekre koncentrálunk. Az elsőrendű logikai reprezentációt használó tanulás elméletével a 19. fejezet foglalkozik. Látni fogjuk, hogy a kifejezőképesség-komplexitás kompromisszum nem is olyan egyszerű, mint először gondolnánk. Gyakran az a helyzet – mint azt a 8. fejezetben is láttuk –, hogy egy kifejezőnyelv lehetővé teszi az adatokra illesztett egyszerű elméletet, míg a nyelv kifejezőképességének korlátozása azt is jelenti, hogy bármely konzisztens elmélet szükségszerűen bonyolult lesz. A sakk szabályait például egy-két oldalon le tudjuk írni elsőrendű logika segítségével, míg az ítéletlogikával történő leírás több ezer oldalt igényelne. Ilyen esetekben kell arra lehetőségnek lennie, hogy a kifejezőbb nyelven sokkal gyorsabb legyen a tanulás.
[182] A 14. századi angol filozófus, William of Ockham után. Ockham nevét gyakran hibásan Occamnak írják, ami talán a francia „Guillaume d’Occam” fordításából ered.
