20.4. Példányalapú tanulás

Eddigiekben a statisztikai tanulás tárgyalásában arra koncentráltunk, hogy valószínűségi modellek egy behatárolt családjának paramétereit egy struktúrájában nem kötött adathalmazra illesszük. Például a kevert Gaussokat használó, nem ellenőrzött tanulás feltételezi, hogy az adatok megmagyarázhatók rögzített számú Gauss-eloszlás összegeként. Az ilyen módszereket paraméteres tanulásnak (parametric learning) nevezzük. A paraméteres tanuló eljárások gyakran nagyon egyszerűek és hatékonyak, de egy meghatározott behatárolt modellcsalád feltételezése sokszor túlzott egyszerűsítése annak, ami az adatokat szolgáltató valós világban történik. Nos, az természetesen igaz, hogy ha nagyon kevés adatunk van, akkor nem reménykedhetünk egy bonyolult és részletes modell megtanulásában, de butaságnak tűnik a hipotézis komplexitását akkor is rögzítve tartani, amikor az adathalmaz nagyon nagyra nő.

A paraméteres módszerekkel ellentétben a nemparaméteres tanulási (nonparametric learning) módszerek lehetővé teszik, hogy a hipotézis bonyolultsága együtt növekedjék az adatokkal. Minél több adatunk van, annál körmönfontabb lehet a hipotézis. Két, nagyon egyszerű nemparaméteres példányalapú tanulást használó módszercsaládot fogunk vizsgálni, amelyeket azért nevezünk így, mert közvetlenül a tanító példányokból hoznak létre hipotéziseket.

20.4.1. Legközelebbi-szomszéd modellek

A legközelebbi-szomszéd (nearest-neighbor) modellek alapötlete az, hogy bármely egyedi x bemeneti pont tulajdonságai valószínűleg hasonlók az x pont környezetébe eső pontok tulajdonságaihoz. Például ha sűrűségbecslést (density estimation) kívánunk végezni – azaz meg akarjuk becsülni egy ismeretlen valószínűség sűrűségfüggvény-értékét x-ben –, akkor egyszerűen mérhetjük azt, hogy x környezete milyen sűrűn van beszórva pontokkal. Ez nagyon egyszerűen hangzik, amíg rá nem jövünk, hogy meg kell határoznunk, mit is értünk „szomszédság” alatt. Ha a szomszédság túl kicsi, akkor egyáltalán nem fog pontokat tartalmazni. Ha túl nagy, akkor esetleg az összes adatpontot tartalmazni fogja, és olyan sűrűséget eredményez, ami mindenütt ugyanakkora. Egy megoldási lehetőség, ha a szomszédságot úgy definiáljuk, hogy legyen éppen elég tág ahhoz, hogy k pontot tartalmazzon, ahol k elég nagy ahhoz, hogy ésszerű becslést végezhessünk. Rögzített k esetén a szomszédság mérete változó, ahol ritkán vannak az adatok, ott a szomszédság tág térrész, ahol az adatok sűrűn helyezkednek el, ott a szomszédság szűk. A 20.12. (a) ábra egy példát mutat: két dimenzióban szétszórt adatpontokat. A 20.13. ábra mutatja az ezen adatokra elvégzett k-legközelebbi-szomszéd sűrűségbecslést k = 3, 10 és 40 esetére. k = 3 esetében a sűrűségbecslést minden egyes pontban csak 3 szomszédos pontra alapozzuk, és ezért erősen változó eredményt kapunk. k = 10 esetén a 20.12. (b) ábrán látható valódi sűrűség jó becslését kapjuk. k = 40 esetén a szomszédság túl tággá válik, és az adatok struktúráját mindenestől elvesztjük. Gyakorlatban – kis dimenziószám esetén – egy 5 és 10 közé eső k a legtöbb esetben jó eredményt ad. Keresztvalidáció alkalmazásával is jó értéket kaphatunk a k-ra.

20.12. ábra - (a) A 20.8. (a) ábra adatainak 128 pontos részhalmaza, két kiválasztott ponttal, és 10 legközelebbi szomszédjukkal. (b) Az adatok előállításánál használt kevert Gauss-eloszlás 3D ábrája.
(a) A 20.8. (a) ábra adatainak 128 pontos részhalmaza, két kiválasztott ponttal, és 10 legközelebbi szomszédjukkal. (b) Az adatok előállításánál használt kevert Gauss-eloszlás 3D ábrája.

20.13. ábra - A 20.12. (a) ábrán látható adatokra végzett sűrűségbecslés, k = 3 (a); k = 10 (b) és k = 40 (c) esetén
A 20.12. (a) ábrán látható adatokra végzett sűrűségbecslés, k = 3 (a); k = 10 (b) és k = 40 (c) esetén

Ahhoz, hogy egy kérdéses pontban a legközelebbi szomszédokat meg tudjuk határozni, egy távolságmetrikára – D(x1, x2)-re – van szükségünk. A 20.12. ábra kétdimenziós példájában euklideszi távolságot használtunk. Ez nem felel meg, ha a tér minden dimenziójában valami mást mérünk – például magasságot és súlyt –, mivel egy dimenzió skálájának megváltoztatása megváltoztatja a legközelebbi szomszédok halmazát. Az egyik lehetőség, hogy minden egyes dimenzió skáláját normalizáljuk. Ehhez először megmérjük az összes tulajdonság varianciáját a teljes adathalmazon, majd a tulajdonságértéket úgy fejezzük ki, hogy megadjuk: a tulajdonságérték az adott tulajdonság varianciájának hányszorosa. (Ez a Mahalanobis-távolság [Mahalanobis distance] – amely a tulajdonságok kovarianciamátrixát veszi figyelembe – speciális esete.) Végül diszkrét esetben alkalmazhatjuk a Hamming-távolságot (Hamming distance), amely úgy definiálja D(x1, x2)-t, mint azon tulajdonságok számát, amelyben x1 és x2 eltér.

A 20.13. ábrán láthatóhoz hasonló sűrűségbecslések a bemeneti tér feletti együttes eloszlásokat határoznak meg. A Bayes-hálóktól eltérően a példányalapú reprezentációk nem tartalmaznak rejtett változókat, ami azt jelenti, hogy nem alkalmazhatunk nem ellenőrzött osztályozást, mint ahogy a kevert Gauss-modellnél tettük. Továbbra is alkalmazhatjuk a kívánt y értéknek az x bemeneti tulajdonságok alapján történő jóslására a sűrűségbecslést, ha kiszámítjuk P(y|x) = P(y, x)/P(x)-et, feltéve, hogy a tanító adatok a kívánt értékre nézve is tartalmaznak értékeket.

A legközelebbi-szomszéd tanulási algoritmus használható közvetlen ellenőrzött tanulásra is. Ha adott egy tesztpélda x bemeneti értékekkel, akkor az y = h(x) az x k-legközelebbi-szomszédjának y értékeiből nyerhető. Diszkrét esetben többségi szavazással kaphatunk egyetlen jósolt értéket. Folytonos esetben átlagolhatjuk a k darab értéket, vagy lokális lineáris regressziót végezhetünk a k pontra illesztve, ez utóbbi esetben a jóslást a kialakuló hipersík x-beli értéke adja.

A k-legközelebbi-szomszéd tanulási algoritmus nagyon egyszerűen megvalósítható, kevés hangolást igényel, és gyakran elég jól működik. Jó dolog, ha először egy új tanulási problémán próbáljuk ki. Mindazonáltal nagy adathalmazokban hatékony mechanizmust kell találnunk arra, hogy a kérdéses x pont legközelebbi szomszédjait megtaláljuk, hiszen túl hosszú lenne minden pontra kiszámítani a távolságot. Egy sor szellemes, a tanító adatok előfeldolgozásán alapuló módszert javasoltak ennek a lépésnek a hatékonynyá tételére. Szerencsétlen módon a legtöbb ilyen módszer nem viselkedik jól a tér dimenziójának növekedésével (azaz a tulajdonságok számának növekedésével).

A sokdimenziós terek még egy további problémát jelentenek, nevezetesen azt, hogy egy ilyen térben a legközelebbi szomszédok rendszerint nagyon messze vannak. Vegyünk egy N elemű, d dimenziós egységkockában elhelyezkedő adathalmazt, és tegyük fel, hogy a szomszédságok b oldalú hiperkockák, amelyek térfogata bd. (Ugyanez a megfontolás működne hipergömbök feltételezése esetén is, de a hipergömb térfogatképlete bonyolultabb.) Ahhoz, hogy k pontot tartalmazzon, az átlagos szomszédság a teljes térfogat – amit egységnyinek tekintünk – k/N-ed részét kell elfoglalnia. Ennek megfelelően bd = k/N, vagyis b = (k/N)1/d. Eddig jó. Legyen most d = 100, k = 10 és N = 1 000 000 értékű. Akkor b 0,89 – azaz a szomszédság majdnem az egész bemeneti teret elfoglalja! Ez arra utal, hogy sokdimenziós esetben a legközelebbi-szomszéd alapú módszerek nem megbízhatók. Alacsony dimenziószám esetén nincs probléma, d = 2 esetén b = 0,003.

20.4.2. Kernelmódszerek

A kernelmodellben (kernel model) úgy tekintünk minden tanító példányra, mintha egy kis saját sűrűségfüggvényt – kernelfüggvényt (kernel function) – generálna. Az eredő sűrűségfüggvény becslés nem más, mint a kis kernelfüggvények súlyozott összege. Egy xi tanító példány egy K(x, xi) kernelfüggvényt generál, amely a tér minden x pontjához egy valószínűséget rendel. Így a sűrűségbecslés:

Normális esetben a kernelfüggvény csak az x és xi közötti D(x, xi) távolságtól függ. A legnépszerűbb kernelfüggvény (természetesen) a Gauss-függvény. Az egyszerűség kedvéért egy gömbszimmetrikus Gauss-függvényt feltételezünk, amelynek minden tengely mentén w a szórása, azaz:

ahol d az x dimenziószáma. Hátra van még a megfelelő w érték választásának problémája. Éppúgy, mint az előzőkben egy túl kis szomszédság nagyon hepehupássá teszi a becslést – mint a 20.14. (a) ábrán látható. A (b) ábrán látható, hogy egy közepes w érték nagyon jó becslést ad. A (c) ábrán bemutattuk, hogy a túl nagy szomszédság eredményeképp teljesen elveszítjük a struktúrát. Jó w értéket választhatunk keresztvalidációval.

20.14. ábra - A 20.12. (a) ábrán látható adatok sűrűségbecslése Gauss-kernelekkel, w = 0,02 (a); w = 0,07 (b) és w = 0,20 (c) esetén.
A 20.12. (a) ábrán látható adatok sűrűségbecslése Gauss-kernelekkel, w = 0,02 (a); w = 0,07 (b) és w = 0,20 (c) esetén.

Ellenőrzött tanulást kernelekkel úgy végezhetünk, hogy a tanító példányokból származtatott összes jóslás súlyozott kombinációját vesszük. (Összehasonlítva a k-legközelebbi-szomszéd módszerrel, ott a k-legközelebbi-példány súlyozatlan kombinációját használjuk.) Az i-edik példánynak a kérdéses x pontra vett súlyát a K(x, xi) kernelfüggvényérték adja. Diszkrét jóslás esetén súlyozott szavazást vehetünk, folytonos esetben súlyozott átlagot vagy súlyozott lineáris regressziót. Figyeljük meg, hogy a kernelekkel végzett jóslás azt igényli, hogy az összes tanító példányt figyelembe kell vennünk. A kernelek összekombinálhatók a legközelebbi-szomszéd indexelési sémáival azért, hogy csupán a szomszédos példányok alapján előállított súlyozott jóslást alkalmazzuk.