KLASIFIKAČNÍ A REGRESNÍ LESY

ROBUST’2004

c JČMF 2004

KLASIFIKAČNÍ A REGRESNÍ LESY Jan Klaschka, Emil Kotrč Klíčová slova: Klasifikační stromy, klasifikační lesy, bagging, boosting, arcing, Random Forests. Abstrakt: Klasifikační les je klasifikační model vytvořený kombinací určitého počtu klasifikačních stromů. Každý strom přiřazuje hodnotě vektoru prediktorů nějakou třídu a výsledná klasifikační funkce je dána hlasováním. Obdobně regresní les sestává z několika regresních stromů a výsledná regresní funkce je obvykle definována jako vážený průměr regresních funkcí jednotlivých stromů. V práci jsou stručně vysvětleny některé metody vytváření lesů, jmenovitě tzv. bagging, boosting, arcing a Random Forests.

1

Úvod

Klasifikační a regresní stromy se pěstují od 60. let. Silným metodologickým impulsem byla v 80. letech kniha [3], popisující tehdy novou metodu CART (Classification And Regression Trees). Věrozvěstem metody CART a stromů obecně na ROBUSTu se v r. 1988 stal Jaromír Antoch příspěvkem [1]. Mezitím, co od druhé poloviny 90. let přibývaly na ROBUSTu další práce o stromech [8], [11], [12], odstartovala ve světě – nejvíce ale asi v pracovně Leo Breimana, jednoho z „otcůÿ CARTu – nová etapa rozvoje metod analýzy dat založených na stromech. Zdá se, že je na čase probrat ji také na ROBUSTu. Tématem tohoto článku jsou klasifikační a regresní lesy. Klasifikační les je klasifikační model, jehož klasifikační funkce je dána kombinací (podle vhodně zvoleného pravidla) klasifikačních funkcí určitého počtu (typicky několika desítek) klasifikačních stromů. Obdobně lze charakterizovat regresní les – stačí v předcházející větě všude nahradit slovo „klasifikačníÿ slovem „regresníÿ. Dlužno poznamenat, že článek nebude v rámci české literatury takovým pionýrským počinem jako již citovaná práce [1]: Přinejmenším se o některých technikách konstrukce lesů zmiňuje (byť v obecnější poloze) Berka v knize [2].

2

Klasifikační a regresní stromy

Les, jak každé malé dítě ví, se skládá ze stromů. Zopakujme některá základní fakta o stromech (podrobněji viz [3],[1]): • Klasifikační strom představuje model pro data, kde každé pozorování patří do některé z tříd C1 , . . . , Ck , k ≥ 2. Současně je pozorování charakterizováno vektorem x = (x1 , . . . , xm ) hodnot vysvětlujících proměnných (prediktorů) X1 , . . . , Xm . V jedné a téže úloze se mohou vyskytovat prediktory kvantitativní i kvalitativní. • Model lze popsat stromovým grafem sestávajícím z uzlů a orientovaných hran (orientace se nevyznačuje, hrana vede shora dolů).

178

Jan Klaschka, Emil Kotrč

• V každém neterminálním uzlu se strom větví – z uzlu vedou hrany do dvou nebo (v některých metodách) více dceřinných uzlů. Větvení je založeno na hodnotě jediného prediktoru. Nejběžnější je binární větvení podle odpovědi na otázku tvaru „xi < c?ÿ pro kvantitativní prediktory Xi a „xi ∈ B?ÿ (kde B je neprázdná vlastní podmnožina množiny všech hodnot veličiny Xi ) pro prediktory Xi kvalitativní. Jedna hrana je pak přiřazena kladné a druhá záporné odpovědi. (Některé metody umožňují i větvení založená na lineární kombinaci kvantitativních prediktorů.) • Pozorování podle hodnot prediktorů „postupujeÿ od kořenového uzlu přes větvení v neterminálních uzlech k některému terminálnímu uzlu (listu). Množina všech listů určuje disjunktní rozklad prostoru hodnot prediktorů X . Terminálnímu uzlu a zároveň pozorováním, která do něj patří, je přiřazena některá z tříd C1 , . . . , Ck . Strom T tak určuje klasifikační funkci dT definovanou na X s hodnotami v množině {C1 , . . . , Ck }. Regresní strom se od klasifikačního stromu liší tím, že každému terminálnímu uzlu je přiřazena reálná konstanta – odhad kvantitativní závisle proměnné Y. Regresní strom T definuje reálnou regresní funkci dT , která je uvnitř množin odpovídajících terminálním uzlům konstantní. K vytváření (pěstování) stromů prakticky všechny běžné metody využívají tzv. rekurzivní dělení (recursive partitioning). Konstrukce začíná stromem o jediném uzlu, do kterého patří všechna trénovací data (kořen je zároveň listem). Probere se množina všech možných větvení a pro každé z nich se vypočte kriteriální statistika (splitting criterion), která – budiž řečeno bez podrobností – hodnotí, nakolik jsou potenciální dceřinné uzly co do hodnot závisle proměnné vnitřně homogenní a navzájem odlišné. Větvení s maximální hodnotou kritéria se vybere jako nejlepší a použije se v modelu, k němuž tak přibude dvojice (popř. v některých metodách větší počet) uzlů, jež jsou prozatím terminální. Data, která patří do kořenového uzlu, se rozdělí podle hodnot prediktorů mezi nové dceřinné uzly. Pro každý z těchto provizorních listů se procedura opakuje, jako by se jednalo o kořen – hledá se nejlepší větvení, atd. Při konstrukci klasifikačního stromu je žádoucí dosáhnout co nejmenší
skutečné (generalizační) klasifikační chyby RP (T ) = P dT (X) 6= Y , kde P je sdružené rozdělení vektoru prediktorů X a závisle proměnné Y s hodnotami v {C1 , . . . , Ck }. V regresních úlohách obdobnou roli nejčastěji hraje
2 (skutečná) střední kvadratická chyba RP (T ) = EP Y − dT (X) . S rostoucí velikostí stromu sice stále klesá (nebo alespoň neroste) chyba na trénovacích datech, ale skutečná chyba v mnoha typických situacích klesá jen do určité velikosti, pak s dalším zvětšováním stromu opět roste. Podle přístupu k problému stanovení „správné velikostiÿ se metody pěstování stromů dělí do dvou skupin. Metody z prvé skupiny přidávají nová větvení, jen dokud to přináší dostatečně velký okamžitý efekt. Když se takové větvení nenajde, proces končí a strom je hotov. Metody druhého typu (např. CART [3]) nejdříve vypěstují tzv. velký strom Tmax , který se následně proře-

Klasifikační a regresní lesy

179

zává – některé uzly se opět odstraňují. Při kostrukci Tmax se uzel stane terminálním, až když obsahuje méně pozorování než zvolená mez nebo všechna pozorování v uzlu patří do téže třídy, popř. mají stejné hodnoty všech prediktorů. O tom, jak velká část stromu Tmax se má odstranit, rozhodují empirické odhady skutečné chyby. Ty se získávají různými způsoby, například pomocí testovacích (validačních) dat, která byla k tomu účelu při konstrukci stromu „ponechána stranouÿ, nebo složitějším „trikemÿ, křížovou validací (cross-validation), při níž se v opakovaných analýzách všechna pozorování střídají v rolích prvků trénovací a testovací množiny. (Detaily viz [3], [1]). Mezi metodami pěstování stromů požívají asi největší prestiže Breimanův, Friedmanův, Olshenův a Stoneův CART (Classification And Regression Trees) ([3]) a Quinlanova metoda C4.5 ([9]). Jediná současná implementace CARTu „posvěcenáÿ autory metody je šířena komerčně firmou Salford Systems1 (San Diego, CA, USA). Volné programy tree a rpart v rámci projektu R2 však představují také dosti věrné implementace metodologie CART. Program C4.5 je k dispozici bezplatně3 . Vylepšenou verzi pod názvy C5.0 (Unix) a See5 (Windows) komerčně šíří Quinlanova firma Rulequest Research4. Informace o řadě dalších programů konstruujících stromy lze nalézt např. na webových stránkách Yu-Shan Shiha z Tchai-wanu5 (spoluautora metod QUEST a CRUISE). Výhodou klasifikačních a regresních stromů je, že pružně postihují vztahy mezi různými typy veličin, nelineární závislosti, interakce proměnných a závislosti, které mají rozdílnou podobu v různých částech prostoru X . Ve srovnání s klasickými parametrickými metodami dosahují často srovnatelné přesnosti, ale poskytují přitom daleko přehlednější a názornější modely. Nevýhodou stromů je, že jsou obvykle značně nestabilní: Zhusta pro jedna a tatáž data existuje mnoho různých stromů s přibližně stejnou chybou a při malé změně dat nebo vstupních parametrů se může výsledný strom (a příslušná klasifikační nebo regresní funkce) výrazně změnit.

3

Lesy

Myšlenka klasifikačních a regresních lesů je vcelku prostá: Co místo jednoho stromu T vypěstovat L stromů T1 , . . . , TL a vytvořit z nich „komisiÿ, která se bude o zařazení pozorování do tříd, (popř., půjde-li o regresní úlohu, o predikované hodnotě závisle proměnné) „usnášetÿ6? Jinými slovy, „agregovanáÿ 1 http://www.salford-systems.com 2 http://cran.r-project.org 3 http://www.rulequest.com/Personal 4 http://www.rulequest.com 5 Užší výběr http://www.math.ccu.edu.tw/~yshih/trees.html, širší, ale ne zcela aktuální přehled http://www.math.ccu.edu.tw/~yshih/tree.html. 6 Již jednou jsme se odvolávali na znalosti malých dětí, a i toto si dnes kdekteré dítě dokáže představit, pokud vidělo ve filmu Dvě věže, druhém dílu trilogie Pán prstenů, jak sněm Entů (chodících stromů) rozhoduje o tom, zda jít do války, tj. jak řeší klasifikační úlohu, zda vstupní informace, které jsou k dispozici, patří do třídy „válkaÿ, nebo „mírÿ.

180

Jan Klaschka, Emil Kotrč

klasifikační (popř. regresní) funkce dA (x) vznikne vhodným zkombinováním klasifikačních (popř. regresních) funkcí d1 (x), . . . , dL (x) jednotlivých stromů. Přirozeným a jednoduchým způsobem kombinace je u regrese aritmetický průměr a u klasifikace většinové hlasování, tj. dA (x) = Ci∗ , pokud #{j; dj (x) = Ci∗ } = max #{j; dj (x) = Ci }, i=1,...,k kde symbol # značí počet prvků. (Nejednoznačnost vyplývající ze shody počtu hlasů se řeší např. znáhodněním.) Kombinování klasifikačních funkcí (v regresi to je analogické, rozdíly si lze domyslet) může být také o něco složitější. Při hlasování může váha hlasu každé z L klasifikačních funkcí záviset na chybě stromu na trénovacích datech (pochopitelně přesnější strom má vyšší váhu). Váha hlasu jednotlivého stromu případně nemusí být stejná pro všechny hodnoty vektoru prediktorů x – může záviset např. také na tom, jak je list příslušného stromu, do kterého x patří, velký (kolik pozorování z trénovacího souboru do něj patří) a „čistýÿ (jak výrazná je převaha nejfrekventovanější třídy). Složitější vážení hlasů je dílem už standardní součástí některých metod konstrukce lesů, ale dílem také ještě předmětem výzkumu (viz např. [15], [13]).

3.1

Čtvero způsobů, jak na to

Dobrá, vypěstovat více stromů, ale kde je vzít? Použijeme-li na jedna a tatáž data opakovaně např. program CART se stejnými vstupními parametry, dostaneme pokaždé tentýž strom. Kombinováním totožných stromů pak nic nového nezískáme. Rozdělit data na L disjunktních částí a každou použít ke konstrukci jednoho stromu se také nezdá být dobrý nápad. Problém přesto má řešení, resp. více řešení. Podívejme se na některá z nich. 3.1.1 Bagging je akronym, zkratka „bootstrap aggregatingÿ. Základní citace je Breimanův článek [4]. Z trénovacího datového souboru L = {(x1 , y1 ), . . . , (xn , yn )} se vytvoří náhodným výběrem s vracením L souborů L1 , . . . , LL velikosti n (bootstrapových výběrů), každý z nich se použije k sestrojení jednoho klasifikačního (popř. regresního) stromu a výsledný klasifikační (nebo regresní) les je pak dán většinovým hlasováním se stejnými vahami (resp. aritmetickým průměrem dílčích regresních funkcí). Do bootstrapového výběru jsou některá pozorování z L vybrána opakovaně a některá naopak vůbec. Počet opakování má pro jednotlivé pozorování z L asymptoticky (pro n → ∞) Poissonovo rozdělení se střední hodnotou 1. Pravděpodobnost, že pozorování nebude vůbec vybráno, je tedy přibližně e−1 ≈ 0.37. Bootstrapový výběr je tudíž tvořen asi 63% pozorování z L, 37% zůstává mimo. Breiman v [4] uvádí u lesů velikosti L = 50 (tvořených stromy vypěstovanými metodou CART) v několika reálných i umělých klasifikačních úlohách snížení generalizační chyby oproti jednomu stromu o 20-47% a velmi podobná čísla – 22-46% – udává také pro úlohy regresní.

Klasifikační a regresní lesy

181

3.1.2 Boosting a arcing. Boosting (to boost – zesilovat) je původně pojem z teorie strojového učení ([14], [5]) a v analýze dat se tak obvykle označuje algoritmus AdaBoost (adaptive boosting), navržený v článku [7]. Mějme klasifikační metodu (nemusí se jednat jen o stromy), která vytváří klasifikační model T na základě trénovacích dat (x1 , y1 ), . . . , (xn , yn ) a vektoru w = (w1 , . . . , wn ) vah přiřazených jednotlivým pozorováním. Algoritmus AdaBoost konstruuje posloupnost rozdílných modelů T1 , . . . , TL s klasifikačními funkcemi d1 (x), . . . , dL (x) tak, že se podle předcházejících výsledků postupně upravují váhy případů. V prvním kroku se použije váhový vektor w1 zadaný uživatelem (např. rovnoměrné váhy) a vytvoří se model T1 . V dalších krocích se pak vždy ke konstrukci modelu Ti (i = 2, . . . , L) použije váhový vektor wi získaný takovou úpravou vektoru wi−1 , že se váhy pozorování chybně klasifikovaných modelem Ti−1 zvýší a správně klasifikovaných sníží. Klasifikační metoda tak stále více „soustředí pozornostÿ na „obtížnáÿ pozorování, která vzdorují zařazení do správné třídy. Váha modelu při hlasování závisí na chybě modelu na trénovacích datech. (Konkrétněji viz [7], [5], [2].) Algoritmus nazvaný v článku [7] AdaBoost je vlastně určen jen pro klasifikační úlohu se dvěma třídami, ale v článku jsou popsány také modifikace AdaBoost.M1 a AdaBoost.M2 pro úlohy s více třídami a AdaBoost.R pro regresní úlohy s hodnotami závisle proměnné v intervalu [0, 1]. Arcing je další Breimanův akronym (adaptive resampling and combining). Základní prací je článek [5]. Arcing představuje spojení myšlenky baggingu a boostingu. Váhy případů se postupně upravují stejným způsobem jako v AdaBoostu, ale používají se jinak: Místo toho, aby s těmito vahami vstupovala všechna pozorování do analýzy, jsou jako v baggingu vytvářeny výběry s vracením, přičemž váhy (náležitě normované) slouží jako pravděpodobnosti „vytaženíÿ. Ukazuje se (viz např. [10], [5]), že boosting i arcing u klasifikačních stromů většinou snižují generalizační chybu ještě více než bagging. V některých případech však mohou výsledky být naopak katastrofální – zejména tehdy, když data jsou „zašuměnáÿ a u části trénovacích dat je hodnota závisle proměnné yi jiná, než „by správně měla býtÿ. Boosting nebo arcing pak vede k tomu, že se učíme opakovat chyby v datech. 3.1.3 Metoda Random Forests je opět „dítkemÿ Leo Breimana, jehož článek [6] představuje základní citaci. Je založena na několika „tricíchÿ: • Trénovací soubory pro jednotlivé stromy jsou (jako v baggingu) bootstrapové výběry z datového souboru L.

• Při volbě větvení pro daný uzel se z m prediktorů X1 , . . . , Xm , které jsou k dispozici, nejdříve náhodně vybere některých m0 , načež se nejlepší větvení hledá již klasicky, ale jen mezi těmi větveními, která jsou založena na vybraných m0 veličinách.

• Pěstují se velké stromy (viz sekci 2), které se neprořezávají.

182

Jan Klaschka, Emil Kotrč

Nejen že náhodný výběr prediktorů výrazně urychluje výpočty, ale experimenty v [6] také dávají zejména v klasifikačních úlohách velmi dobré výsledky – mj. srovnání s metodou AdaBoost vyznívá pro Random Forests příznivě. (V regresi je efekt méně výrazný a zdá se, že jsou o něco výhodnější některé modifikace uvedeného postupu.) Zvláště přínosná se metoda ukazuje u problémů, kde existuje velký počet prediktorů, z nichž každý sám o sobě obsahuje jen málo informace o závisle proměnné. Jak volit parametr m0 ? Nejvhodnější hodnota závisí na úloze a uživatel může experimentovat. Jednoduché rozumné doporučení je použít m0 blízké log2 m. U některých problémů se jako dobré, nebo dokonce nejlepší ukazuje m0 =1. To znamená, že se prediktor, který se má v uzlu použít pro větvení, vybírá zcela náhodně! Jinými slovy, na tom, jaké větvení se vybere, v podstatě nezáleží, hlavně že se prostor hodnot prediktorů vůbec nějak rozparceluje – hlasování (nebo v případě regrese průměrování) to dá do pořádku. To je mimochodem zcela protichůdné optimalizaci stromů, o níž byly v minulých letech na ROBUSTu dva příspěvky ([11], [12]) – připomeňme, že větvení se optimalizuje za cenu drastických výpočetních nákladů a s výsledky (co do generalizační chyby) mnohdy ne právě uspokojivými. Vidíme zde jeden podstatný rozdíl mezi baggingem, boostingem a arcingem na jedné straně a metodou Random Forests na straně druhé. Bagging, boosting a arcing jsou nadstavbou nad klasickými metodami (jako CART nebo C4.5) zaměřenými na pěstování co nejpřesnějších stromů. U metody Random Forests na kvalitě jednotlivých stromů tolik nezáleží; cílem není minimalizovat chybu stromů, ale jen celého lesa.

3.2

Proč to funguje

Zatím jsme se omezili na popisný přístup – říkáme, jak která metoda postupuje, ale ne proč. Stejně tak informujeme, jaké jsou empirické výsledky, ale nevysvětlujeme, jak je možné, že to tak je. Může se tak zdát, že nové způsoby konstrukce lesů se navrhují podle vzoru „Myslím, myslím, nevím dál, co bych ještě udělal.ÿ Ve skutečnosti se při studiu vlastností lesů neuplatňují jen numerické experimenty, ale také teoretické úvahy, byť částečně heuristického charakteru. Čtenáře v tomto ohledu odkazujeme na dříve citovanou literaturu, ale alespoň něco málo naznačíme. Z metod uvedených v paragrafu 3.1 se jen Random Forests týká specificky stromů a lesů. Bagging, boosting a arcing lze aplikovat nejen na stromy, ale na vcelku libovolnou klasifikační či regresní metodu. (Všimněme si, že v názvech článků [4] a [5] se mluví obecně o prediktorech a klasifikátorech, nikoli o stromech.) Platí, vágně řečeno, že agregovaný klasifikační model, jehož klasifikační funkce dA je dána kombinací dílčích klasifikačních funkcí d1 , . . . , dL pomocí hlasování, je tím přesnější (tj. má tím menší skutečnou chybu), čím přes-

Klasifikační a regresní lesy

183

nější jsou dílčí klasifikátory a čím jsou si funkce d1 , . . . , dL vzájemně méně podobné. U regrese s agregací průměrováním je to obdobné. „Alchymieÿ přidávání náhody do konstrukce modelu sleduje cíl najít co nejlepší kompromis: co možná zvýšit vzájemnou nepodobnost funkcí di , ale tak, aby přesnost dílčích modelů neutrpěla přespříliš. Skrze lesy se ve výhodu obrací nevýhoda stromů – jejich nestabilita, tj. fakt, že malá změna dat zpravidla vede k velké změně stromu T a jeho klasifikační (nebo regresní) funkce dT . K dalším nestabilním metodám patří třeba neuronové sítě nebo kroková lineární regrese. Příklady stabilních metod jsou lineární diskriminační analýza nebo metoda k nejbližších sousedů. Nestabilní metody lze pomocí baggingu a obdobných technik výrazně zpřesnit, zatímco u stabilních metod je efekt minimální, popřípadě dokonce záporný.

3.3

Software

Repertoár softwaru pro pěstování lesů je zatím skromnější než nabídka programů pro konstrukci stromů. Uveďme několik současných možností. • Komerční verze programu CART zahrnuje bagging a arcing. • Quinlanovy programy C5.0 a See5 (viz sekci 2) obsahují boosting. • Softwarový systém Weka7 zaměřený na strojové učení, vyvinutý na University of Waikato na Novém Zélandu, obsahuje pod názvem j48 implementaci metody C4.5, a dále procedury Bagging a AdaBoostM1, které se dají v kombinaci s j48 použít k pěstování lesů. Weka je freeware. • Breimanův vlastní software Random Forests je volně k dispozici8 a zároveň existuje komerční verze šířená firmou Salford Systems. Implementace randomForest v projektu R je freeware. Pokud nějaký program pro konstrukci stromů umožňuje snadné zadávání vstupních údajů a dává výstupy ve vhodném tvaru, „dotvořitÿ jej na software pro pěstování lesů je programátorsky nenáročné. Do původního programu není třeba zasahovat, takže nevadí, není-li dostupný ve zdrojovém tvaru.

4

Závěr

Klasifikační a regresní lesy představují významné zdokonalení metodologií založených na stromech. Za cenu únosného zvýšení výpočetní náročnosti se dosahuje výrazného zpřesnění modelů. Patrně jedinou nevýhodou lesů oproti stromům je to, že se ztrácí pro stromy tak charakteristická přehlednost. Na les tvořený desítkami nebo stovkami stromů nejsme schopni, stejně jako je tomu např. u neuronových sítí, se dívat jinak než jako na „černou skříňkuÿ. Jinými slovy, do lesa není vidět. 7 http://www.cs.waikato.ac.nz/~ml/index.html 8 http://www.stat.berkeley.edu/users/breiman/RandomForests

184

Jan Klaschka, Emil Kotrč

Reference [1] Antoch J. (1988). Klasifikace a regresní stromy. In: ROBUST’1988. Sborník prací 5. letní školy JČSMF, J. Antoch, T. Havránek & J. Jurečková (eds.), Praha, JČSMF, 0 – 6. [2] Berka P. (2003). Dobývání znalostí z databází. Praha: Academia. [3] Breiman L., Friedman J.H., Olshen R.A., Stone C.J. (1984). Classification and regression trees. Belmont CA: Wadsworth. [4] Breiman L. (1996). Bagging predictors. Machine Learning 24, 123 – 140. [5] Breiman L. (1998). Arcing classifiers. Annals of Statistics 26, 801 – 849. [6] Breiman L. (2001). Random forests. Machine Learning 45, 5 – 32. [7] Freund Y., Schapire R.E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences 55, 119 – 139. [8] Klaschka J., Antoch J. (1997). Jak rychle pěstovat stromy. In: ROBUST’1996. Sborník prací 9. letní školy JČMF, J. Antoch & G. Dohnal (eds.), Praha, JČMF, 91 – 106. [9] Quinlan J.R. (1992). C4.5: Programs for machine learning. New York: Morgan Kaufmann. [10] Quinlan J.R. (1996). Bagging, boosting, and C4.5. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence, 725 – 730. [11] Savický P., Klaschka J., Antoch J. (2000). Optimální klasifikační stromy. In: ROBUST’2000. Sborník prací 11. letní školy JČMF, J. Antoch & G. Dohnal (eds.), Praha, JČMF, 267 – 283. [12] Savický P., Klaschka J. (2002). Lesk a bída optimálních stromů. In: ROBUST’2002. Sborník prací 12. zimní školy JČMF, J. Antoch, G. Dohnal & J. Klaschka (eds.), Praha, JČMF, 256 – 267. [13] Savický P., Kotrč E. (2004). Experimental study of leaf confidences for random forest. In: COMPSTAT 2004. Proceedings in Computational Statistics, J. Antoch (ed.), Heidelberg, Physica Verlag, 1767 – 1774. [14] Schapire R.E. (1990). The strength of weak learnability. Machine Learning 5, 197 – 227. [15] Schapire R.E., Singer Y. (1999). Improved boosting algorithms using confidence-rated predictions. Machine Learning 37, 297 – 336. Poděkování: Práce byla podporována granty ME 701 MŠMT ČR a GA ČR 201/02/1456. Adresa: J. Klaschka, E. Kotrč, Ústav informatiky AV ČR, Pod Vodárenskou věží 2, 182 07 Praha 8 E-mail : {klaschka,kotrc}@cs.cas.cz