AdaBoost tanuló algoritmus
Kapcsolódó könyvfejezetek:
18.5. Miért működik a tanulás: a tanulás számítási elmélete
Kapcsolódó könyvfejezetek:
20. fejezet - Statisztikai tanulási módszerek A tartalom szövege (HTML):
AdaBoost tanuló algoritmus
Kerettörténet
Egy lóversenyen fogadó szerencsejátékos nyereményének maximalizálása érdekében elhatározta, hogy készít egy olyan számítógépes programot, amely a futamokat leíró általános információk alapján képes megjósolni a győztes befutót [1]. A program elkészítéséhez segítséget is kért egy profi szerencsejátékostól. A profi fogadót arra kérte meg a program készítője, hogy magyarázza el a fogadási stratégiáját. Nem meglepő módon a profi képtelen volt megadni egy olyan általános szabályhalmazt, ami segíthet a megfelelő ló kiválasztásában. Másrészről, amikor a megadott versenyeket leíró adatok is rendelkezésre álltak a profinak nem okozott gondot a fogadási szabályok megalkotása, stratégiájának elmagyarázása (például: Fogadj arra a lóra, amely mostanában a legtöbb versenyt nyeri! Fogadj arra a lóra, amely mostanában a legnépszerűbb a fogadók körében!). Érezhető azonban, hogy az ilyen általános szabályok önmagukban elég pontatlanok, de az ilyen szabályok alkalmazása nem tűnik ésszerűtlennek, ha olyan becsléseket adnak meg, amelyek kicsivel jobbak, mintha véletlenszerűen fogadnánk. Ráadásul, ha más-más versenyekről ismételve megkérdezzük a profi véleményét, akkor a profi szerencsejátékos képes további kevésbé általános fogadási szabályokat megalkotni. Ahhoz, hogy az egyes versenyekből kivonatolt szabályokat versenyfogadásra fel tudjuk használni, ahhoz két problémával is szembe kell néznünk. Egyrészt, hogyan kellene kiválasztani a futamokat leíró adatokat úgy, hogy a profi képes legyen megfelelő fogadási szabályokat alkotni. Másrészt, a versenyekből kivonatolt szabályok miként kombinálhatóak össze egy sokkal pontosabb fogadási szabállyá.
A boosting tanuló algoritmus egy általános és bizonyítottan hatékony [1], pontos jóslási szabályokat megalkotó eljárás. A becslési szabályt durva becslésű és pontatlan szabályok kombinációjából hozza létre, ahogyan az előbb leírt kerettörténetben szereplő profi fogadó is teszi. A véletlen tippelésnél kicsivel jobb szabályok kombinációjából létrehoz egy megbízhatóbb fogadási szabályt.
Boosting és az AdaBoost algoritmus
Kearns és Valiant vetették fel először, hogy ha a gyenge tanuló algoritmusok, amelyeknek becslése csak egy kicsivel jobb, mint a véletlen tippelés a PAC (Probaby Approxiamtly Correct) modellben, akkor a gyenge tanuló algoritmusokból tetszőleges pontosságú tanuló algoritmust nyerhetünk [2], [3]. Schapire 1989-ben bizonyította be az első polinom idejű boosting algoritmust [1]. Egy évvel később Freund kifejlesztett egy hatékonyabb boosting tanuló algoritmust, amelyet a gyakorlatban jobban lehetett alkalmazni [1]. Az AdaBoost tanuló algoritmus megalkotása Freund és Schapire munkásságának köszönhető. A publikált AdaBoost tanuló algoritmus megoldotta a korábbi boosting algoritmusok alkalmazhatóságának nehézségeit. (Az AdaBoost algoritmus az osztályozás során súlyokat is használ, hogy a vágások mentén felosztott adatminták rosszul történő osztályozását csökkentse.)
A boosting tanuló algoritmus gyorsan népszerűvé vált a gépi tanulással foglalkozó kutatók körében. Ez a téma lassan a statisztikai kutatások főirányává vált [4]. A gépi tanulás elméletével foglalkozó kutatók létre kívántak hozni egy „gyengébb” osztályozó eljárások becslési eredményeit egybevonó „erősebb” osztályozó eljárást (Schapire 1990, Freund 1995). A munkájuk 1997-ben teljesedett ki, amikor Freund és Schapire publikálta az AdaBoost algoritmust. Ezt az algoritmust az irodalomban gyakran nevezik még diszkrét AdaBoost tanuló algoritmusnak is [4]. (A diszkrét elnevezés abban gyökerezik, hogy az algoritmus első változata bináris célváltozó (nyer, nem nyer) értékét tudta becsülni.)
A tanuló algoritmus belsejében lévő gyenge tanuló algoritmus az adathalmazban szereplő adatmintákat egymást követően különböző súlyozás mellett veszi figyelembe. A gyenge osztályozó eljárás a rosszul osztályozott egyedeket felsúlyozza. A következő iterációban az előbbi lépésben kiszámolt súlyok mellett újra osztályozza gyenge tanuló algoritmus az adatmintákat. A tanuló eljárás ezt a lépést több iteráción keresztül megismétli. Így a nehezen osztályozható mintákat felsúlyozza a tanuló algoritmus. Végül az AdaBoost tanuló eljárás a gyenge osztályozók becsléseinek súlyozott szavazatát veszi figyelembe [4]. (A gyenge osztályozó eljárások becsléseit különböző súlyokkal veszi figyelembe.)
A kutatási eredmények alapján úgy tűnik, hogy lehetséges a tanuló algoritmus becslési teljesítményének javítása a becslések torzításának és várható értékének tükrében [4]. (Ha a becslés várható értéke és a becsülni kívánt célváltozó várható értéke megegyezik, akkor a becslés torzítása, tanulás esetében a becslés elfogultsága (bias) nulla.) Továbbá, az eljárás úgy tűnik nem érzékeny a túltanulás jelenségére [4]. (Tanuló algoritmus túltanulása azt jelenti, hogy olyan szabályokat alkot az osztályozó eljárás, amelyek csak a tanuló adathalmazra érvényesek. Például csak barna és zöld szemű zsokék lovai nyertek a tanuló mintán, és az eljárás azt a szabályt határozza meg, hogy más szemszínű zsoké lova nem lehet győztes befutó.)
Az AdaBoost tanuló algoritmus
Az algoritmus bemenete egy tanító adathalmaz. Ezek legyenek (x1, y1),…,(xm, ym), ahol minden xi eleme a doménnek (Lóversenyes példa esetében, ezek a változók írják le a futamokat. Például az i-edik ló hányszor volt győztes befutó, vagy az i-edik ló a futamok során átlagosan hanyadik helyen végzett.), és minden yi a célváltozó (label) eleme az Y halmaznak. Tegyük fel, hogy Y = {-1, +1} (bináris osztályozó). Az AdaBoost algoritmus minden egyes lépésben meghív egy gyenge osztályozó eljárást. Az algoritmus lépéseit jelölje t, ahol t = 1 … T. Az algoritmus egyik alapötlete, hogy a tanuló mintákat egy súlymértékkel látja el. Később látni fogjuk, hogy ezek a súlyok egy valószínűségi eloszlást képeznek. A tanuló minta súlyát jelölje az i-edik tanulómintán és az algoritmus t-edik lépésében Dt(i). Kezdetben minden tanuló minta súlya egyenlő, de az algoritmus minden egyes iterációban újra felosztja a tanítási minták súlyát úgy, hogy a rosszul osztályozott minták súlyát megnöveli. Ezáltal a következő iterációban a gyenge tanuló algoritmus nagyobb figyelmet fog fordítani a rosszul osztályozott mintákra. (A belső gyenge algoritmus addig nagyobb súlyt ad a tanuló mintának, amíg nem sikerül jól osztályoznia.) A gyenge tanuló algoritmus feladata, hogy gyenge hipotéziseket állítson fel. A t-edik lépésben a hipotézist jelölje 
, és ez a hipotézis összhangban van a Dt értékeivel. A gyenge hipotézis jóságát a hibája nagyságával mérhetjük. A hipotézis hibáját az (1) képlet írja le formálisan [1].
, és ez a hipotézis összhangban van a Dt értékeivel. A gyenge hipotézis jóságát a hibája nagyságával mérhetjük. A hipotézis hibáját az (1) képlet írja le formálisan [1].
A ht hipotézis hibáját leíró (1) képlet a rosszul osztályozott Dt súlyok összege adja meg. A gyakorlatban a gyenge osztályozó, egy olyan tanuló algoritmus, amely a tanító minta Dt súlyait használja fel. Az AdaBoost tanuló algoritmus pszeudó kód leírása a következő:
Adott:
ahol 
Kezdetben: 
Ciklus t = 1…T:
Gyenge osztályozó tanítása Dt eloszlással
Állítsuk elő a gyenge hipotézist és számítsuk ki a hibaértékét: 
és számítsuk ki a hibaértékét: Válasszuk 
Frissítés: 
ahol Zt a normalizációs tényező (úgy kell megválasztani, hogy Dt+1 egy valószínűségi eloszlás legyen).
Kimenet a végső hipotézis:
Az algoritmus minden t-edik iterációban az előző iterációban kiszámolt Dt súlyokkal „betanítja” a belső gyenge tanuló eljárást. A tanítás után megkapjuk a gyenge hipotézist és kiszámíthatjuk annak hibáját. Ezek után az algoritmusban vázolt képlet segítségével kiszámítjuk
αt paraméter értékét. Az
αt paraméter értéke kifejezi a ht hipotézis fontosságát (információ tartalmát). A Dt értékek frissítését az algoritmus következő lépése írja le. Az említett lépés hatására megnövekszik mindazon minták súlya, amelyeket a ht hipotézis rosszul osztályozott, és csökkenti azon minták súlyát, amelyeket jól osztályozott. Így a súly a „nehezen” osztályozható minták mentén fog koncentrálódni. A végső H hipotézis lényegében a T darab gyenge hipotézis súlyozott többségi szavazásából áll elő, ahol az
αt –k értéke a ht hipotézisre vonatkozik.
Az AdaBoost algoritmus belső „gyenge” tanuló algoritmusaként úgynevezett döntési csonk (Decision Stump) eljárást szoktak alkalmazni. Ez az algoritmus egyetlen attribútum érték mentén osztja fel a tanítási mintákat, továbbá ezt a vágást
θ küszöbérték mellett végzi el. Az eljárás megfelel egyszintű döntési fa modellnek (Egyetlen attribútum érték szerint vág. A fa egyik levelében lesznek a
θ -nálkisebb attribútum értékű minták, míg a másik levélben a
θ -nál nagyobbak.). A döntési csonk algoritmus működési elvét a (2) képlet szemlélteti.
Speciális esetben az AdaBoost „gyenge” tanuló algoritmusaként döntési fát szoktak alkalmazni [5]. Ilyenkor a gyenge hipotézis a tanítóhalmaz mintáinak partícionálását végzi el. A döntési fán alapuló gyenge hipotézis működését a (3), (4), (5) képletek írják le [5] és az 1. ábra szemlélteti. A Wjb az j-edik partícióban szereplő, b célváltozó értékkel megegyező minták súlyát fejezi ki. A cj értéke a j-edik partíció „jóságát” fejezi ki. A képletben szereplő Z értékea súlyok kiszámításához felhasznált normalizáló tényező.A példában a döntési fa Pi partíciókra osztotta fel a tanító adathalmazt (Ebben a példában a döntési fa két attribútum szerint vágott.).
3#1. ábra. Döntési fa alkalmazása az AdaBoost algoritmusban.
Az AdaBoost tanuló algoritmusnak számos változatát publikálták. Említésképpen ilyen például a LogitBoost tanuló algoritmus, amely képes folytonos értékkészletű célváltozók értékét is becsülni. Ebben az algoritmusban szereplő „gyenge” tanuló algoritmusként regressziós eljárást alkalmaznak [6].
Az AdaBoost tanuló algoritmus alkalmazása
Az AdaBoost tanuló algoritmus ismertetése után vizsgáljuk meg, hogyan változik az egyes iterációkban a tanítási minták súlya. Kezdetben minden minta súlya azonos, majd a gyenge hipotézis alkalmazása után felosztott adathalmazban szereplő minták súlyát újra számoljuk úgy, hogy a rosszul osztályozott minták súlyát növeljük és a jól osztályozott minták súlyát csökkentjük. A leírtakkal összhangban, egy adathalmaz valamilyen gyenge hipotézis szerinti felosztását és a tanítópontok súlyának változását a 2. ábra szemlélteti. A „körbezárt” minták osztályozására az AdaBoost algoritmus gyenge osztályozó eljárásként lineáris regressziót alkalmaz. Ennek az eljárásnak a lényege, hogy megtalálja a mintákra leginkább illeszkedő egyenest, ami azt jelenti, hogy minden más egyenes esetében a mintapontoktól mért függőleges távolságának négyzetösszege nagyobb, mint a leginkább illeszkedő egyenesnél kapott összeg. A 2. ábra a,) részén látható, hogy kezdetben minden minta súlya azonos. A 2. ábra b,) részén megfigyelhetjük a súlyok eloszlását az algoritmus 1. iterációja után. Végül a 2. ábra c,) részén láthatjuk a súlyok alakulását, valamint a vágási felszínt az algoritmus 120. lépése után. Az ábrán színárnyalatok jelölik a gyenge osztályozók becslésének összegét (Minél fehérebb egy terület annál többször vágták úgy az adathalmazt a regressziós egyenesek, hogy ott a kék mintákra „tippeltek” ).
2. ábra. Tanítóminták súlyainak változása az AdaBoost algoritmus működése során.
Látható, hogy az AdaBoost algoritmus futása során képes volt a „körbezárt” kék egyedeket jó közelítéssel megkülönböztetni a pirosaktól. Vegyük észre, hogy az algoritmus működése során a súlyok a nehezen osztályozható minták körül csoportosultak, azaz a felsúlyozott minták a döntési felszín körül alakultak ki. Érezhető, hogy az algoritmus a döntési felszín közelében elhelyezkedő tesztminták esetében pontatlanabb becslést fog adni. A 2. ábra alapján észrevehető, hogy az AdaBoost algoritmus hatékony megoldást tud nyújtani a példában felvázolt osztályozási problémára.
Az algoritmus működésének bemutatásához képzeljük el a következő osztályozási feladatot: Az AdaBoost algoritmus segítségével szeretnénk megkülönböztetni az eredeti virágokat a művirágoktól. A virágokat jellemezze a tömegük és a színük. A feladatra alkalmazott algoritmus lépéseit a 3. ábra szemlélteti. A 3. ábrán „gyenge” tanuló algoritmusok „egyszerű” koordináta tengelyek szerinti vágásokat végeztek. Az ábrán a gyenge tanuló algoritmusok által meghatározott hipotéziseit és a tanítóminták súlyának változását figyelhetjük meg. A tanítási minták súlyát a virágok mérete jelöli. Látható, hogy az első hipotézis a vörösség mértéke szerint osztotta fel a tanítómintát. A második lépésben az előzőek során „felsúlyozott” mintákra koncentrálva határozza meg a vágási hipotézist. A 2. hipotézis alkalmazása után kiszámított súlyok alapján láthatjuk, hogy az előző lépésben „felsúlyozott” minták súlya lecsökkent.
Az AdaBoost tanuló algoritmus egyetlen hipotézissé kombinálja össze az iterációk során meghatározott „gyenge” hipotézisek becslését. A „gyenge” hipotézisek összekombinálását az 4. ábra szemlélteti. Vegyük észre, hogy egyszerű koordináta tengelyek szerinti vágások összekombinálása esetében az algoritmus teljesen el tudta különíteni a példában szereplő egyedeket, tehát az AdaBoost algoritmus alacsony komplexitású „gyenge” osztályozók (Decision Stump) hipotéziseit összekombinálva megbízható eredményt adhat. Az ábrán vastag vonal jelöli a vágási felszínt, és a színárnyalatok jelölik a „gyenge” hipotézisek metszetének „jóságát” (becslési összegét). Látható, hogy a meghatározott vágási felszín mellett jól elkülönültek a valódi virágok a műanyagból készültektől.
3. ábra. Az AdaBoost algoritmus lépései során meghatározott hipotézisek.
4. ábra. A gyenge tanuló algoritmusok összekombinálása.
Példaalkalmazások
Az algoritmus működésének demonstrálására Freund egy alkalmazást is készített [7]. A felhasználó a mintapontokat egér bal és jobb gombjának segítségével helyezheti el. Ezután a felvett adathalmazt tanítóhalmazra és teszthalmazra oszthatjuk fel. Az alkalmazás az algoritmus lépései során grafikonon ábrázolja a tanító és a tesztadathalmazon az AdaBoost hibáját és annak elméleti határát, valamint az adott lépésben meghatározott „gyenge” hipotézis hibáját. Az AdaBoost működését egy MATLAB programkód [8] segítségével is megvizsgálhatjuk, valamint lehetőséget biztosít különböző gyenge osztályozó eljárások kipróbálására is.
Irodalom
[1] Y. Freund , R. Schapire, A short introduction to boosting, Japonese Society for Artificial Intelligence, vol. 14, no. 5, pp. 771-780, 1999.
[2] M. Kearns , L. G. Valiant, Learning Boolean formulae or finite automata is as hard as factoring, Technical Report TR-14-88, Harvard University Aiken Computation Laboratory, 1988.
[3] M.l Kearns ,L. G. Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the Association for Computing Machinery, vol. 41, no. 1, pp. 67–95, 1994.
[4] G. Ridgeway, The state of boosting, Computing Science and Statistics 31. Interface Foundation of North America, pp. 172-181, 1999.
[5] R. Schapire , Y. Singer, Improved Boosting Algorithms Using Confidence-rated Predictions,
Machine Learning vol. 37, no. 3, pp. 297-336, 1999.
[6] J. Friedman, T. Hastie, R. Tibshirani, Additive logistic regression: a statistical view of boosting, Annals of Statistics vol. 28, no. 2, pp. 337-407, 2000.
[7] http://cseweb.ucsd.edu/~yfreund/adaboost/ , Y. Freund, An applet demonstrating adaboost.
[8] http://www.downloadplex.com/Scripts/Matlab/Development-Tools/Download-bo..., R. Stapenhurst, boosting_demo.
Szerző: Varga Róbert, BME