Tekintsük a 4.3. és a 4.4. táblázatokban látható tanuló- és teszthalmazokat az emlős osztályozási feladatra. A tíz tanulórekord közül kettő kapott téves címkét: a denevéreket és a bálnákat osztályoztuk nem-emlősöknek emlősök helyett.

Egy a tanulóadatokra tökéletesen illeszkedő döntési fa látható 17. (a) ábrán. Bár a fa tanítási hibája nulla, a tesztelési hibaaránya 30% . Az emberek és a delfinek egyaránt hibásan osztályozódnak mint nem-emlősök, mert a Testhőmérséklet , Elevenszülő és Négylábú attribútumok értékei azonosak a tanulóhalmaz tévesen címkézett rekordjaiéval. A hangyászsünök másrészt egy kivételes esetet jelentenek, amikor egy tesztrekord osztálycímkéje ellentmond más hasonló rekordok osztálycímkéjének a tanulóhalmazban. A kivételes esetek miatti hibák gyakran elkerülhetetlenek, és meghatározzák a bármilyen osztályozó által elérhető minimális hibaarányt.

Ezzel szemben a 4.25. (b) ábrán látható M2 döntési fa tesztelési hibaaránya kisebb ( 10% ) annak ellenére, hogy a tanítási hibaarány valamivel magasabb ( 20% ). Nyilvánvaló, hogy az M1 első döntési fa túlillesztett a tanulóadatokon, mert létezik egy egyszerűbb modell, amelynek kisebb a hibaaránya a teszthalmazon. A Négylábú attribútumon alapuló tesztfeltétel az M1 modellben hamis, mert illeszkedik a tévesen címkézett tanító rekordokra, ami a rekordok téves osztályozására vezet a teszthalmazon.

Azok a modellek, amelyeknek az osztályozási döntései kevés számú tanulórekordon alapulnak, szintén érzékenyek a túlillesztésre. Ezek a modellek akkor jöhetnek létre, ha a tanulóadatokból jellegzetes minták hiányoznak, és a tanuló algoritmusok akkor is tovább finomítják a modelljeiket, ha már csak néhány tanulórekord áll rendelkezésre. Ezeket a hatásokat szemléltetjük az alábbi példában.

Tekintsük a 4.5. táblázatban látható öt tanulórekordot. Mindegyik tanulórekord helyesen címkézett, és a megfelelő döntési fát a 4.26. ábrán ábrázoltuk. Bár a tanítási hiba nulla, a hibaarány 30% a teszthalmazon.

Az emberek, elefántok és delfinek tévesen osztályozódnak, mert a döntési fa az összes téli álmot nem alvó melegvérű gerincest nem-emlősnek osztályozza. A fa azért jut erre az osztályozási döntésre, mert csak egy tanulórekord van ilyen jellemzőkkel, a sas. Ez a példa világosan demonstrálja a rossz előrejelzés veszélyét, amikor nincs elég reprezentatív eset egy döntési fa levélcsúcsaiban.

A modell túlillesztés olyan tanuló algoritmusoknál is felmerülhet, amelyek a többszörös összehasonlítási eljárásként ismert módszertant alkalmazzák. Ahhoz, hogy megértsük a többszörös összehasonlítási eljárást, tekintsük annak előrejelzésének a feladatát, hogy a tőzsde növekedni vagy csökkenni fog-e a következő tíz kereskedési napon. Ha egy tőzsdei elemző egyszerű véletlen találgatásokat tesz, akkor 0,5 annak a valószínűsége, hogy az előrejelzése helyes bármelyik kereskedési napon. Ugyanakkor annak a valószínűsége, hogy tízből legalább nyolcszor helyesen jósol

( 10 8 )+( 10 9 )+( 10 10 ) 2 10 =0,0547,

amely igen valószínűtlennek tűnik.

Tegyük fel, hogy ötven tőzsdei elemző közül egy befektetési tanácsadó kiválasztása iránt érdeklődünk. Stratégiánk az, hogy azt az elemzőt választjuk ki, aki a legtöbb helyes előrejelzést hozza az elkövetkező tíz kereskedési napon. A hiba ebben a stratégiában az, hogy még ha minden elemző véletlenszerű módon jelez előre,

1− (1−0,0547) 50 =0,9399

annak a valószínűsége, hogy legalább az egyik közülük legalább nyolc pontos előrejelzést tesz, ami nagyon magas. Bár mindegyik elemző kis valószínűséggel jelez helyesen előre legalább nyolc alkalommal, összekötve őket már nagy valószínűséggel találunk egy olyan elemzőt, aki ezt képes megtenni. Nincs garancia továbbá a jövőben arra, hogy egy ilyen elemző továbbra is pontos előrejelzéseket fog adni véletlenszerű találgatással.

Hogyan kapcsolódik a többszörös összehasonlítási eljárás a modell túlillesztéshez? Sok tanuló algoritmus független alternatívák egy { γ i } halmazát tárja fel, majd azt a γ max alternatívát választja, amely egy adott kritérium függvényt maximalizál. Az algoritmus hozzáadja γ max -ot az aktuális modellhez azért, hogy javítsa annak összteljesítményét. Ezt az eljárást addig ismételjük, amíg további javulás nem figyelhető meg. A döntési fa építése során például több vizsgálatot végzünk, hogy melyik attribútum tudja legjobban vágni a tanulóadatokat. A legjobb vágáshoz vezető attribútumot választjuk a fa növelésére addig, amíg a megfigyelt javulás statisztikailag szignifikáns.

Legyen T 0 a kezdeti döntési fa és T x az új fa az x attribútumhoz tartozó belső csúcs beszúrása után. Elvileg x -et akkor lehet hozzáadni a fához, ha a Δ( T 0 , T x ) megfigyelt nyereség nagyobb, mint egy előre meghatározott α küszöbérték. Ha csak egy attribútum tesztfeltételt kell kiértékelni, akkor el tudjuk elkerülni hamis csúcsok beszúrását úgy, hogy egy elég nagy α értéket választunk. A gyakorlatban azonban egynél több tesztfeltétel áll rendelkezésre, és a döntési fa algoritmusnak kell kiválasztani a legjobb x max attribútumot jelöltek egy { x 1 , x 2 ,…, x k } halmazából, hogy az adatokat particionáljuk. Ebben az esetben az algoritmus valójában egy többszörös összehasonlítási eljárást használ annak eldöntésére, hogy megnöveljen-e egy döntési fát. Pontosabban, Δ( T 0 , T x )≥α helyett a Δ( T 0 , T x max )≥α egyenlőtlenséget vizsgálja. Mivel az alternatívák k száma nő, így vele együtt nő annak az esélye, hogy egy olyan x max -ot találunk, melyre Δ( T 0 , T x max )≥α . Kivéve ha a Δ nyereségfüggvényt, vagy az α küszöbértéket a k nagyságához nem igazítjuk, az algoritmus akaratlanul is hamis csúcsokat ad hozzá a modellhez, ami modell túlillesztéshez vezet.

Ez a hatás egyre kifejezettebb lesz, ha a tanulórekordok, ahonnan x max -ot választjuk, száma kicsi, mert Δ( T 0 , T x max ) varianciája nagy, ha kevesebb eset áll a tanítás rendelkezésére. Ennek eredményeként ha nagyon kevés tanulórekord van, akkor nő annak a valószínűsége, hogy egy olyan x max -ot találunk, melyre Δ( T 0 , T x max )≥α . Ez gyakran előfordul, amikor a döntési fa mély lesz, ami viszont csökkenti a csúcsok által lefedett rekordok számát, és növeli annak valószínűségét, hogy felesleges csúcsot adunk a fához. A nagy számú alternatíva vagy a kis számú tanulórekord hibájának kompenzálása ezért modell túlillesztéshez vezet.

Bár a túlillesztés elsődleges oka még mindig vita tárgya, általában egyetértenek abban, hogy a modell bonyolultsága (összetettsége) hatással van a modell túlillesztésre, mint ahogy azt a 4.23. ábra mutatja. A kérdés az, hogyan határozzuk meg a megfelelő modell bonyolultságot? Ideális bonyolultságról akkor beszélünk, ha egy modell a legkisebb általánosítási hibát adja. A probléma az, hogy a tanuló algoritmus csak a tanulórekordokhoz fér hozzá a modell építése során (lásd a 4.3. ábrát). Nem ismeri a teszthalmazt, és így nem tudja, milyen jól fog majd működni a fa olyan rekordokon, amelyeket még sohasem látott. A legjobb, amit tehetünk, hogy megbecsüljük a felépített fa általánosítási hibáját. Ez a szakasz több módszert is ismertet a becslés végrehajtására.

Visszahelyettesítéses becslés használata

A visszahelyettesítéses becslés megközelítés feltételezi, hogy a tanulóhalmaz jól reprezentálja az összes adatot. Következésképpen a tanítási hiba, vagy más néven visszahelyettesítéses hiba használható arra, hogy az általánosítási hiba egy optimista becslését adja. E feltételezés szerint egy döntési fa következtetési algoritmus egyszerűen azt a modellt választja ki, mint végleges modellt, amelyik a legkisebb tanítási hibaarányt adja. A tanítási hiba ugyanakkor általában az általánosítási hiba rossz becslése.

A modell bonyolultságának beépítése

Mint már említettük, a modell túlillesztés esélye nő, amint a modell egyre bonyolultabbá válik. Emiatt inkább az egyszerűbb modelleket részesítjük előnyben. Ez a stratégia a jól ismert Occam borotvája (Occam’s razor) elv vagy a takarékosság elve:

(Occam borotvája) Két azonos általánosítási hibájú modell közül az egyszerűbb modellt részesítjük előnyben az összetettebb modellel szemben. Az Occam borotvája egy intuitív elv, mert egy bonyolult modellben a további összetevők a puszta véletlen miatt nagyobb eséllyel fognak illeszkedni. Einstein szavaival: ,,Tegyünk mindent a lehető legegyszerűbbé, de nem egyszerűbbé, mint ami valójában’’. Ezután két módszert mutatunk be a modell bonyolultság beépítésére osztályozási modellek kiértékelésénél.

Pesszimista hibabecslés

Az első megközelítés úgy számolja ki explicit módon az általánosítási hibát, mint a tanítási hiba és egy, a modell bonyolultságát leíró büntető tag összege. Az így kapott általánosítási hiba annak pesszimista hibabecslésének tekinthető. Legyen például n(t) a t csúcs által osztályozott tanulórekordok száma, e(t) pedig a tévesen osztályozott rekordok száma. Egy T döntési fa e g (T) pesszimista becslési hibáját az alábbiak szerint lehet kiszámítani:

e g (T)= ∑ i=1 k [e( t i )+Ω( t i )] ∑ i=1 k n( t i ) = e(T)+Ω(T) N t ,

ahol k a levélcsúcsok száma, e(T) a döntési fa teljes tanítási hibája, N t a tanulórekordok száma, Ω( t i ) pedig az egyes t i csúcsokhoz tartozó büntető tag.

Tekintsük a 4.27. ábrán látható bináris döntési fákat. Ha a büntető tag 0,5 -del egyenlő, akkor a baloldali fa pesszimista hibabecslése

e g ( T L )= 4+7×0,5 24 = 7,5 24 =0,3125

és a jobboldali fa pesszimista hibabecslése

e g ( T R )= 6+4×0,5 24 = 8 24 =0,3333.

Így a baloldali fa pesszimista hibaaránya jobb, mint a jobboldali fáé. A bináris fáknál a 0,5 -es büntető tag azt jelenti, hogy egy csúcsot mindaddig ki kell terjeszteni a két gyerek csúcsára, amíg legalább egy tanulórekordon javul az osztályozás, mert egy csúcs kiterjesztése, amely 0,5 -nek a teljes hibához való hozzáadásával egyenértékű, kevésbé költséges, mint egy tanítási hiba elkövetése.

Ha Ω(t)=1 minden t csúcs esetén, akkor a baloldali fa pesszimista hibabecslése e g ( T L )=11/24=0,458 , míg a jobboldali fa pesszimista hibabecslése e g ( T R )=10/24=0,417 . A jobboldali fa ezért jobb pesszimista hibaaránnyal bír, mint a baloldali fa. Így egy csúcsot nem kell kiterjeszteni a gyerek csúcsaira, kivéve, ha egynél több tanulórekordnál csökken a téves osztályozás hibája.

Legrövidebb leíró hossz elve

Egy másik mód a modell bonyolultságának figyelembe vételére a legrövidebb leíró hosszon vagy MDL (Minimum Description Length) elven alapuló információelméleti megközelítés. Ezen elv szemléltetésére tekintsük a 4.28. ábrán látható példát. Ebben a példában A és B számára egyaránt rekordok egy halmaza adott, ismert x attribútumértékekkel. Ezen kívül az A személy ismeri minden egyes rekord pontos osztálycímkéjét, míg a B személy nem tudja ezt az információt. B megkaphatja az összes rekord osztályozását úgy, hogy kérésére A szekvenciálisan továbbítja neki az osztálycímkéket. Egy ilyen üzenet Θ(n) bit információt igényel, ahol n a rekordok száma.

Alternatívaként A dönthet úgy, hogy egy olyan osztályozási modellt épít, amely az x és y közötti kapcsolatot összegzi. A modell a B számára történő továbbítás előtt tömör formában kódolható. Ha a modell 100% -osan pontos, akkor az átvitel költsége egyenértékű a modell kódolásának költségével. Egyébként A azt az információt is át kell hogy küldje, hogy mely rekordot sorolta be helytelenül a modell. Így az átvitel teljes költsége

Költség(modell,adat)=Költség(model)+Költség(adat|modell), (4.9)

ahol a jobb oldalon az első tag a modell kódolásának költsége, míg a második tag a tévesen címkézett rekordok kódolásának költségét reprezetálja. Az MDL elv szerint egy olyan modellt kellene keresnünk, amely minimalizálja a teljes költségfüggvényt. A 207. oldalon a 9. feladatban található példa bemutatja, hogyan kell kiszámítani egy döntési fa teljes leíró hosszát.

Becslő statisztikai korlátok

Az általánosítási hiba a tanítási hiba statisztikai korrekciójaként is becsülhető. Mivel az általánosítási hiba hajlamos arra, hogy nagyobb legyen, mint a tanítási hiba, a statisztikai korrekciót általában a tanítási hiba felső korlátjaként számoljuk ki azon tanulórekordok számát figyelembe véve, amelyek egy adott levélcsúcsba kerülnek. A C4.5 döntési fa algoritmus például az egyes levélcsúcsok által elkövetett hibák számáról feltételezi, hogy binomiális eloszlást követ. Az általánosítási hiba kiszámításához a megfigyelt tanítási hiba felső korlátját kell meghatározni, amint azt a következő példa szemlélteti.

4.3. Példa.

Tekintsük a 4.27. ábrán látható bináris döntési fák bal szélső ágát. Figyeljük meg, hogy T R bal szélső levélcsúcsa két gyerek csúccsal bővült T L -ben. Vágás előtt a csúcs hibaaránya 2/7=0,286 . A binomiális eloszlást normális eloszlással közelítve az e hibaarányra a következő felső korlátot lehet levezetni:

e felső (N,e,α)= e+ Z α/2 2 2N + Z α/2 e(1−e) N + Z α/2 2 4 N 2 1+ Z α/2 2 N , (4.10)

ahol α a megbízhatósági szint, Z α/2 a standard normális eloszlás α/2 kvantilise, N pedig az e kiszámításához használt összes tanulórekord száma. Az α=25% , N=7 és e=2/7 helyettesítéssel a hibaarány felső korlátja e felső (7;2/7;0,25)=0,503 , ami 7×0,503=3,521 hibának felel meg. Ha kiterjesztjük a csúcsot a gyerek csúcsaira ahogy T L mutatja, akkor a gyerek csúcsok tanítási hibaaránya egyenként 1/4=0,250 és 1/3=0,333 . (4.10) egyenletet használva ezeknek hibaarányoknak a felső határai egyenként e felső (4;1/4;0,25)=0,537 és e felső (3;1/3;0,25)=0,650 . A gyerek csúcsok teljes tanítási hibája így 4×0,537+3×0,650=4,098 , ami nagyobb, mint a T R -beli megfelelő csúcs becsült hibája.

Validációs halmaz használata

Ennél a megközelítésnél ahelyett, hogy az általánosítási hiba becslésére a tanulóhalmazt használnánk, az eredeti tanulóadatokat két kisebb részhalmazra bontjuk. Az egyik részhalmazt a tanításra használjuk, míg a másikat, az úgynevezett validációs (érvényesítő) halmazt (validation set), használjuk az általánosítási hiba becslésre. Általában a tanulóhalmaz kétharmadát a modellépítésére tartják fenn, míg a fennmaradó egyharmadot használják hibabecslésre.

Ezt a megközelítést általában olyan osztályozási módszereknél használják, amelyek úgy paraméterezhetőek, hogy különböző bonyolultsági szintű modellek adódnak. A legjobb modell bonyolultsága a tanuló algoritmus paraméterének a módosításával becsülhető (például egy döntési fa metszési szintje), míg a tanuló algoritmus által kapott empirikus modell a legalacsonyabb hibaarányt el nem éri a validációs halmazon. Bár ez a megközelítés jobb módot ad annak becslésére, hogy mennyire jól teljesít a modell a korábban nem látott rekordokon, kevesebb adat áll rendelkezésre a tanításra.

Az előző szakaszban számos módszert írtunk le egy osztályozási modell általánosítási hibájának becslésére. Az általánosítási hiba egy megbízható becslése lehetővé teszi, hogy a tanuló algoritmus egy olyan pontos modellt találjon, amely nincs túlillesztve a tanulóadatokon. Ez a szakasz két stratégiát mutat be a modell túlillesztés elkerülésére döntési fa következtetési környezetben.

Előmetszés (prepruning, korai megállási szabály)

Ebben a megközelítésben a faépítő algoritmus megszakad, mielőtt előállítaná azt a teljesen kifejlett fát, amely tökéletesen illeszkedik a teljes tanulóhalmazra. Ehhez szigorúbb megállási feltételt kell alkalmazni, például meg kell állni egy levélcsúcs bővítésével, ha a szennyezettségi mértékben megfigyelt nyereség (vagy a becsült általánosítási hibában való javulás) nem ér el egy bizonyos küszöbértéket. Az az előnye ennek a megközelítésnek, hogy elkerüli olyan túlságosan bonyolult részfák előállítását, amelyek túlillesztődnek a tanulóhalmazon. Mindazonáltal nehéz kiválasztani a megfelelő küszöbértéket a korai leállásra. Túl magas küszöbérték alulillesztett modellt eredményez, míg a túl alacsony küszöbérték nem elegendő ahhoz, hogy úrrá legyünk a modell túlillesztési problémán. Továbbá, még ha nem is kaptunk szignifikáns nyereséget a létező attribútum tesztfeltételek egyikét használva, egy újabb vágás jobb részfát eredményezhet.

Utómetszés (postpruning)

Ebben a megközelítésben a döntési fát először a maximális méretére növeljük. Ezt egy fametszési lépés követi, amely során a teljesen kifejlett fát alulról felfelé haladóan lenyessük. A nyesést megtehetjük úgy, hogy a részfát helyettesítjük (1) egy olyan új levélcsúccsal, amelynek osztálycímkéjét a részfához tartozó rekordok többségi osztálya határozza meg, vagy (2) a részfa leggyakoribb ágával. A fa-metszést akkor fejezzük be, amikor további javulás már nem figyelhető meg. Az utómetszés általában jobb eredményt ad, mint az előmetszés, mert a nyesésről hozott döntés a teljesen kifejlett fán alapszik, ellentétben az előmetszéssel, amely a faépítési folyamat túl korai megszakításától szenved. Ugyanakkor utómetszésnél a teljes fa felépítéséhez szükséges további számítások hiábavalóak lehetnek, amikor a részfát lemetszük.

A 4.29. ábra az egyszerűsített döntési fa modellt szemlélteti 4.3.6. szakaszbeli web-robot észlelő példához. Figyeljük meg, hogy a depth=1 gyökerű részfa helyébe az ImagePages attribútumot bevonó ágak egyike kerül. Ez a megközelítés részfa növelés (subtree raising) néven is ismert. A depth≥1 és MultiAgent=0 részfát pedig egy a 0 osztályhoz rendelt levélcsúcs váltotta fel. Ez a megközelítés az úgynevezett részfa csere (subtree replacement). A depth≥1 és MultiAgent=1 részfa érintetlen marad.