Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
Navrhování skupin klasifikátorů pomocí opakovaného výběru trenovacích dat
Jednou z často využívaných možností při návrhu klasifikátorů jsou metody opakovaného výběru trenovacích dat tak, aby byl dosažen co nejlepší odhad statistiky pro předpověď vlastností klasifikace. Výraznou roli zde hraje skutečnost, že budou klasifikována nějaká budoucí data, která samozřejmě nemohla být použita v okamžiku návrhu klasifikátorů pomocí trenovacích příkladů. Potíže při návrhu jsou také způsobeny neznámým rozložením hodnot klasifikovaných vzorů.
Výběrem vzorků dat se všeobecně zabývá statistika, zde se zmíníme o několika vybraných typických metodách používaných ve strojovém učení za situace, kdy je nutno vycházet z reálných disponibilních dat.
Existují metody opakovaného výběru vzorků, které j sou obecně zaměřeny na techniky trénování klasifikátorů.
Bagging
Metoda bagging ("rozdělování do sáčků") patří knejjednodušším postupům. Název je odvozen ze slov bootstrap aggregation, kde se využívá více trenovacích množin, z nichž každá je vytvořena výběrem n' <n příkladů ze základní trénovací množiny D. Každá z takto vzniklých podmnožin di <= D je použita k natrénování jednoho z více klasifikátorů. Výsledná klasifikace neznámého datového vzorku je pak určena "hlasováním" všech takto vytvořených klasifikátorů, tj. vzorek je zařazen do třídy určené většinou. Obvykle jsou všechny tyto klasifikátory stejného typu (např. rozhodovací stromy nebo umělé neuronové sítě)—to, že mohou rozhodovat různě, souvisí s natrénováním pomocí různých trenovacích podmnožin dt.
-l-
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
Nestabilita klasifikačního algoritmu je vlastnost, kdy vlivem malých změn trenovacích dat dochází ke vzniku podstatně různých klasifikátorů s relativně velkými rozdíly v klasifikační přesnosti (tj. podílu množství správně klasifikovaných vzorků k celkovému množství). K tomu dochází mj. i u rozhodovacích stromů. Bagging obecně zlepšuje vlastnosti nestabilních klasifikátorů vzhledem k tomu, že se bere do úvahy průměr z názorů j ednotlivých klasifikátorů, avšak teoretický důkaz tohoto zlepšení pro libovolný případ neexistuje—metoda vychází z experimentálních zkušeností a není záruka, že bude fungovat vždy, i když velmi často ke zlepšení vede.
Boosting
Cílem metody boosting je zlepšení klasifikační přesnosti libovolného algoritmu strojového učení. I zde je základem vytvoření více klasifikátorů pomocí výběru vzorků ze základní trénovací množiny D.
Boosting vychází z vytvoření prvního klasifikátorů, jehož klasifikační přesnost je lepší než 50%. Dále jsou přidávány další klasifikátory mající stejnou klasifikační vlastnost, takže je vygenerován soubor klasifikátorů, jehož celková klasifikační přesnost j e libovolně vysoká vzhledem ke vzorkům v trénovací množině—klasifikace byla zesílena (boosted).
Přiklad: nechť má skupina klasifikátorů tri členy a klasifikace je do dvou tříd. Prvně se náhodně vybere (bez vracení) nx<n trenovacích prvků z množiny D (n je počet prvků v D) a vznikne podmnožina Du na níž je natrénován první klasifikátor Cl. Stačí, když Cl je pouze tzv. slabý žák (weak learner), tj. může být pouze o málo lepší v klasifikaci než kdyby hádal náhodně—přesnost jen o málo lepší než 50% je pouze minimální požadavek; na trenovacích datech může také být přesnost samozřejmě velmi vysoká.
-2-
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
V dalším kroku se vytvoří trénovací množina D2 (n2 trenovacích prvků) vzhledem k již existujícímu C1 tak, aby C1 správně klasifikoval pouze 50% zD2 (ze zbylých prvků v D se vyhledá postupně požadované množství správně a nesprávně klasifikovaných). Nyní se natrénuje druhý klasifikátor C2 pomocí podmnožiny D2, na níž C1 selhává.
Nakonec se obdobně vytvoří D3 (n3 trenovacích prvků) vzhledem k již existujícím Cl a C2 a natrénuje se C3. Zde hraje roli to, zda Cl a C2 se shodují či neshodují v klasifikaci vzorku—podle toho se vybírají prvky do D3 tak, aby již vytvořené klasifikátory na nich při společné klasifikaci selhávaly.
Neznámý prvek x je pak při klasifikaci zařazen do třídy, na níž se shodne většina z vytvořených klasifikátorů. Např. když se Cl a C2 shodují, určují výsledek. Neshodují-li se, je výsledek dán pomocí rozhodnutí C3 (který se zde tedy shodne buď s Cl nebo C2). Skupinové rozhodování dává lepší přesnost než libovolný individuální člen.
Pro stanovení hodnot nt neexistuje jednoznačný algoritmus. Obecný požadavek je, aby se trénování účastnily všechny vzorky z Z), a dále aby počet trenovacích vzorků pro každý klasifikátor byl přibližně stejný vzhledem k tomu, že klasifikátory mají rovnocenný hlas při hlasování—měly by tedy být i rovnocenně vytvořené. Lze stanovit, aby ve výše uvedeném příkladu přibližně «, = n/3. V praxi mohou ale vzniknout potíže: snadnější klasifikační problémy mohou vést k tomu, že C1 prostě funguje na většině dat, takže n2 (i n3) pak bude značně menší než nx - n/3 (aby se vyhovělo podmínkám vytváření podmnožin) a všechny prvky z D nebudou využity. Na druhé straně může pro obtížné klasifikační problémy dojít k tomu, že C1 správně klasifikuje pouze velmi málo trenovacích vzorků, takže nx « n/3 a n2 bude velmi vysoké. Řešením je (vzhledem k náhodnosti výběru «,) opakovat celou boosting proceduru několikrát, aby se zajistila co nejlepší hodnota pro nx, přibližně rovnoměrné rozdělení počtu prvků do podmnožin a pokud možno i využití všech trenovacích vzorků. K tomu se používají různé heuristiky snažící se dodržet výše uvedené požadavky.
-3-
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
—-*i
n = 27
Obrázek ukazuje případ klasifikace dvourozměrného problému, kde jsou dvě klasifikační třídy (symbolizované znaky • pro třídu K,ao pro TZ2) a tri lineární
klasifikátory (zde—což není podstatné—typu Widrow-Hoff, tj. gradientní hledání lineární hranice oddělující třídy vzhledem k nejmenšímu čtverci chyb). Hlasující trojice má v tomto případě vždy lepší klasifikační přesnost než jednotlivé klasifikátory trénované na podmnožinách. Přesnost je také vyšší než kdyby byl vygenerován jediný klasifikátor na všech trenovacích vzorcích.
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
AdaBoost
AdaBoost {adaptive boosting) je v současnosti nejpoužívanější variantou metody boosting—umožňuj e při návrhu přidávat slabé žáky tak dlouho, dokud není dosažena určitá požadovaná nízká hodnota klasifikační chyby skupiny klasifikátorů.
Každý trénovací vzorek dostane přidělenu váhu, která určuje pravděpodobnost jeho výběru do trénovací podmnožiny pro jednotlivé klasifikátory z vytvářené skupiny.
Je-li vzorek klasifikován přesně, jeho šance na opětovný výběr pro následující klasifikátor klesá; v opačném případě roste. AdaBoost se takto soustředí na obtížné vzorky.
Na počátku dostanou vzorky stejné hodnoty vah. V každém iteračním kroku k] e výběrem tvořena trénovací množina vzhledem k těmto váhám (které ovlivňují pravděpodobnost výběru). Na této množině je natrénován klasifikátor Ck.
V následujícím kroku jsou zvýšeny váhy vzorků klasifikovaných chybně a sníženy váhy vzorků klasifikovaných správně pomocí Ck. Vzorky j sou pak na základě nového rozdělení pravděpodobnosti výběru použity při vytváření dalšího klasifikátorů pomocí Ck+1 a celý proces iterativně pokračuje.
Nechť vzorky (vektory hodnot atributů) x' v celkové trénovací množině D mají klasifikace yt.
Nechť Wk(i) je k-té diskrétní rozdělení vah přes všechny trénovací vzorky.
Dále nechť ak je vypočtená váha klasifikátorů Ck podle jeho přesnosti a Zk je normalizační konstanta.
-5-
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
Proceduru AdaBoost pak lze zapsat pomocí následujícího pseudokódu:
i     procedure AdaBoost
2       begin initialize D = {x\y„ ,„,xn,yn),kmax, Wx(i) = lln, i = 1, ..., n
3           k^O
4           do   k «— k + 1
5               trénuj slabého žáka Ck pomocí vzorků z D vzhledem k Wk(i)
6               E, <— trénovací chyba Ck měřená na D vzhledem k Wk(i)
1,
a, <- — ln
2

WJÍ)     k ay   pro   h, (x! )= v, (správná klasifikace)
8               J^-hCO"-—^X  i
Zk       \eat-    pro   hk(x')^yi (chybnáklasifikace)
9           until k = kmax return Ck a ak pro k = 1,..., kmax (vrací klasifikátory a jejich váhy)
10
n     end
Poznámky:
Řádek 5: Chyba klasifikátorů Q je stanovena vzhledem k rozdělení Wk{i) nad D, pomocí níž je trénován.
Řádek 8: Zk je normalizační konstanta stanovená tak, aby Wk{i) představovalo skutečné rozdělení, a hk(x') je označení kategorie přidělené vzorku x' klasifikátorem Ck (který je jedním z "hlasující" skupiny klasifikátorů).
Řádek 9: Ukončení cyklu do—until může být také založeno na dosažení dostatečně nízké chyby celé skupiny klasifikátorů.
-6-
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
Výsledné klasifikační rozhodnutí pro testovací vzorek x je založeno na diskriminační funkci, která je dána váhovaným součtem výsledků jednotlivých klasifikátoru:
g(x)
*inax
jt=i
I když mohou existovat případy dat, pro něž uvedený postup nemusí poskytnout očekávané výsledky, tak skupina slabých trénovaných "žáků" je schopna docílit libovolně nízké klasifikační chyby (pro trenovací data) pro dostatečně velký počet klasifikátoru kmax.
Trenovací chyba slabého žáka Q je:
pro nějakou kladnou hodnotu Gk (tj. Ek < 50%, žák dokáže správně zařadit o něco více než V2 trénovacích příkladů do příslušných kategorií). Chyba skupiny klasifikátoru pak je:
rttají
jfc—1                                                                  k=\
což ilustruje následující obrázek:
-7-
Strojové učení—boosting (průsvitky z přednášek; literatura: R.O. Duda, P.E. Hart, D.G. Stork: Pattern Classification, 2nd Edition, John Wiley & Sons, 2001)
1   2   3   4   5   6   7   8   9   10 11  12 13 14 15
AdaBoost redukuje trenovací chybu exponenciálně v závislosti na rostoucím počtu klasifikátoru kmax v "hlasující" skupině. Algoritmus AdaBoost je zaměřen na ty příklady, které způsobují klasifikační potíže, takže každý další přidaný klasifikátor má obecně větší chybu na trénovacích datech než kterýkoliv z předchozích (viz křivku chyba slabého žáka na trénovacích datech). Dokud každý z klasifikátoru ve skupině dává lepší než náhodný výsledek (tj. např. pro dvě kategorie je chyba menší než 0.5), váhované rozhodnutí celé skupiny zaručuje pokles chyby na trénovacích datech. Velmi často dochází k podobnému poklesu i na testovacích datech.
Zvyšování počtu klasifikátoru ve skupině ale může vést k tzv. přetrénování (ztrátě schopnosti generalizovat vlivem přílišného zaměření klasifikátoru na rozeznávání pouze konkrétních trénovacích dat). Simulační experimenty však ukázaly, že k tomu dochází relativně zřídka i pro extrémně vysoké hodnoty kmax. Pro praktickou aplikaci AdaBoost platí základní pravidlo:
Boosting zlep suje klasifikaci pouze tehdy, pokud klasifikátory ve skupině poskytují lepší než jenom náhodné výsledky—to však nelze zaručit předem.
Navzdory neexistenci záruky a priori, uvedená metoda poskytuj e v mnoha reálných problémech velmi dobré výsledky.
-8-