ˇ zovan´ ´ ı Dat Vyteˇ ´ ska 12 – Kombinovan´ ´ ı modelu˚ Pˇrednaˇ ˇ Miroslav Cepek ˇ Pavel Kord´ık a Jan Cern´ y (FIT) ˇ ´ CVUT Fakulta Elektrotechnicka,
´ ı fond Praha & EU: Evropsk´y socialn´ Investujeme do vaˇs´ı budoucnosti
16.12.2014 ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
1 / 36
´ ı modelu) Ensembles (Kombinovan´ ˚ Aneb v´ıc hlav, v´ıc v´ı! Co kdyˇz jsme se dostali na hranice moˇznost´ı jednoho modelu? ˇ s´ı model vede jen k pˇreuˇcen´ı? Co kdyˇz uˇz dalˇs´ı uˇcen´ı nebo sloˇzitejˇ Co s t´ım?
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
2 / 36
Motivace z praxe
ˇ z – Netflix prize (predikce, ktere´ filmy by se zakazn´ ´ Souteˇ ıkovi ˇ a nejak ˇ mohly take´ l´ıbit, kdyˇz videl ohodnotil jinou skupinu filmu?) ˚ ˇ et ˇ hodnocen´ı filmu konkretn´ ´ ım Respektive – c´ılem je pˇredpoved ´ zakazn´ ıkem, kdyˇz v´ıme, jak hodnotil jine´ filmy v minulosti. ´ ze na Cenu $1,000,000 z´ıska´ nejlepˇs´ı, kdo souˇcasneˇ dokaˇ ´ ıc´ı pˇresnost alesponˇ o 5%. testovac´ı mnoˇzineˇ zlepˇsit stavaj´
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
3 / 36
Motivace z praxe (2)
A vˇsechny TOP t´ymy pouˇz´ıvaj´ı kombinace modelu. ˚ ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
4 / 36
Motivace pro kombinaci modelu˚
Cesta k vyˇssˇ ´ı pˇresnosti neˇz u nejlepˇs´ıho z d´ılˇc´ıch modelu. ˚ ˇ a´ chyby pro trochu jina´ data. A trochu jine´ chyby. Kaˇzd´y model del I
Kdyˇz se zkombinuj´ı dohromady, moˇzna´ sve´ chyby eliminuj´ı.
ˇ ızen´y experiment R´ I I I I
ˇ psingle , dveˇ tˇr´ıdy s pc1 = pc2 , modely maj´ı pevn´y chybov´y pomer ´ ´ kaˇzd´y d´ılˇc´ı klasifikator chybuje nezavisle na ostatn´ıch, ´ ´ zen´ym hlasovan´ ´ ım, v´ysledna´ klasifikace dana majoritn´ım nevaˇ jak to dopadne (pˇresnost jako funkce poˇctu modelu)? ˚
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
5 / 36
Motivace pro kombinaci modelu˚ (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
6 / 36
Motivace pro kombinaci modelu˚ (3) Analogie z idealizovane´ zkouˇsky I I I
´ kaˇzd´y student se nauˇc´ı latku (kaˇzd´y s jin´ymi chybami), ˇ ıch na otazky, ´ spoleˇcneˇ rozhoduj´ı o odpoved´ ´ ım pˇr´ıpadeˇ by meli ˇ u kaˇzde´ otazky ´ ˇ et ˇ spravn ´ eˇ :). v idealn´ odpoved
´ zeme aproximovat rozhodovac´ı Kombinac´ı ruzn´ ˚ ych modelu˚ dokaˇ ´ hranici, kterou by samostatne´ modely proloˇzit nedokazaly.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
7 / 36
Chyby modelu˚
´ modelu˚ z minule´ pˇrednaˇ ´ sky. Vraˇtme se jeˇsteˇ k chybam ˇ identicke´ chyby. Kdyˇz vytvoˇr´ım ruzn ˚ e´ modely, nebudou delat I I
´ cn´ı parametry, Napˇr´ıklad pouˇziji jine´ poˇcateˇ ´ nebo vezmu jinou podmnoˇzinu trenovac´ ı mnoˇziny.
U kombinac´ı modelu˚ I I
´ ı pˇresnost d´ılˇc´ıch = slab´ych modelu, Nebudu usilovat o maximaln´ ˚ ´ ´ ı chyb pˇri spoleˇcnem ´ rozhodovan´ ´ ı. Budu spolehat na filtrovan´
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
8 / 36
Variance modelu˚ (rozptyl chyby modelu) ˚ ´ eˇ chyby vˇsech takto vytvoˇren´ych modelu˚ by mely ˇ b´yt z Nicmen ´ ıho rozdelen´ ˇ ı se stejnou stˇredn´ı hodnotou a rozptylem. normaln´ ˇ rozptyl modelu˚ udav ´ a´ jak moc se liˇs´ı chyba jednotliv´ych Cili modelu˚ od stˇredn´ı chyby.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
9 / 36
Bias modelu˚ (Zaujet´ı modelu) ˚
Bias (zaujet´ı) vyjadˇruje systematickou chybu zpusobenou ˚ ´ (napˇr´ıklad) sˇ patneˇ zvolenou trenovac´ ı mnoˇzinou.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
10 / 36
Nedouˇcen´ı modelu (underfitting) ´ ı regrese) je pˇr´ıliˇs jednoduch´y, aby Model (napˇr´ıklad linearn´ ´ dokazal popsat data. Modely budou m´ıt n´ızkou varianci, ale vysok´y bias. ´ Co to znamena? ´ ale maj´ı (velkou) chybu uˇz na Modely si budou podobne, ´ trenovac´ ıch datech.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
11 / 36
Pˇreuˇcen´ı modelu (overfitting, uˇz zase) Model je pˇr´ıliˇs ohebn´y a nauˇcil se i sˇ um, tj. vztahy, ktere´ v datech ve skuteˇcnosti nejsou. Modely budou m´ıt n´ızk´y bias, ale vysokou varianci. ´ Co to znamena? ´ Jednotlive´ modely budou m´ıt n´ızkou chybu na trenovac´ ıch datech, ale budou hodneˇ rozd´ılne´ a budou v´yrazneˇ v´ıce chybovat na testovac´ıch datech.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
12 / 36
´ ı modelu˚ – prevence pˇreuˇcen´ı Kombinovan´ Dusledek pˇreuˇcen´ı ˚ I
model na testovac´ıch datech vykazuje velke´ chyby.
´ skupinu modelu˚ nauˇcen´ych na ruzn´ ´ Mam ˚ ych podmnoˇzinach ´ trenovac´ ıch dat. Kaˇzd´y model jsem moˇzna´ pˇreuˇcil. ˇ ceho dosahnout ´ ˇ Muˇ kombinac´ı techto modelu? ˚ zu neˇ ˚
Sn´ızˇ ili jsme rozptyl modelu. ˚ ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
13 / 36
´ ı modelu˚ – sniˇzovan´ ´ ı zaujet´ı Kombinovan´ ˇ Jednoduche´ modelovac´ı metody s malou ohebnost´ı (opet ´ dat) nedokaˇ ´ z´ı dobˇre nauˇcene´ na ruzn´ ˚ ych podmnoˇzinach aproximovat rozhodovac´ı hranici.
ˇ dosahnu ´ ˇ s´ı” hranice a tedy i menˇs´ı chyby. Kombinac´ı opet ”ohebnejˇ
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
14 / 36
Skupiny modelu˚
´ ı modelu˚ tkv´ı v diverziteˇ (ruznorodosti) S´ıla seskupovan´ modelu. ˚ ˚ ´ ˇ Diverzity muˇ dvema cestami: ˚ zu dosahnout I I
Pouˇz´ıt ruzn ˚ e´ modelovac´ı techniky. ´ Vytvoˇrit ruzn ı mnoˇziny (instance, pˇr´ıznaky). ˚ e´ podmnoˇziny trenovac´
´ ´ Zakladn´ ı schema pouˇzit´ı algoritmu˚ pro kombinaci modelu: ˚ 1 2 3
4 5
Vyber stavebn´ı jednotky ensemblu (vhodne´ modely). ´ Vytvoˇr pro kaˇzd´y trenovac´ ı mnoˇzinu. ´ Natrenuj vˇsechny modely v ensemblu (uˇcen´ı jednotliv´ych modelu˚ ´ muˇ e´ na uˇcen´ı ostatn´ıch modelu˚ v ensemblu). ˚ ze b´yt zavisl Spoˇc´ıtej v´ystup vˇsech modelu˚ v ensemblu. ´ Jejich v´ystup zkombinuj do v´ysledneho v´ystupu.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
15 / 36
´ Zakladn´ ı ensemblovac´ı algoritmy
Pro klasifikaˇcn´ı a regresn´ı ulohy se daj´ı pouˇz´ıt: ´ I I I I
bagging, boosting, stacking, cascade generalization.
Pouze pro klasifikaˇcn´ı ulohy se take´ daj´ı pouˇz´ıt: ´ I I I
cascading, delegating, arbitrating.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
16 / 36
Bagging
Jednoduˇssˇ ´ı metoda kombinace. I I
I
Homogenn´ı z hlediska algoritmu uˇcen´ı, tj. pouˇzit pouze jeden. ´ ´ Ruznorodosti dosahne odliˇsnost´ı trenovac´ ıch mnoˇzin, ˚ ´ ı s opakovan´ ´ ım do puvodn´ ´ vzorkovan´ ı velikosti trenovac´ ıch dat. ˚ ´ Slabe´ (= d´ılˇc´ı) modely uˇc´ı nezavisle.
V´ystup ensemblu se urˇc´ı: I
I
´ prum ˇ pro regresi – spoˇc´ıtam hodnotu ze vˇsech v´ystupu˚ ˚ ernou modelu˚ v ensemblu. ´ majoritu z v´ystupu˚ modelu˚ v ensemblu. pro klasifikaci – spoˇc´ıtam
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
17 / 36
Bagging (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
18 / 36
Boosting
Nauˇc´ım posloupnost modelu, ˚ kaˇzd´y dalˇs´ı model si bude vˇs´ımat te´ ´ vstupn´ıch dat, ve ktere´ pˇredchoz´ı modely chybovaly. cˇ asti To, jak moc si bude model vˇs´ımat vstupn´ıch dat, se vyjadˇruje vahami vstupn´ıho vzoru. ´ Oklasifikuji trenovac´ ı data vˇsemi doposud nauˇcen´ymi modely a ˇ chybu, pˇridam ´ do trenovac´ ´ vzory, na kter´ych jsem udelal ı mnoˇziny ´ nasleduj´ ıc´ıho modelu. ´ zˇ e se modely uˇc´ı jeden po druhem. ´ Z toho vypl´yva, ´ zen´y prum ˇ (vaˇ ´ zena´ V´ystup ensemblu se spoˇc´ıta´ jako vaˇ ˚ er majorita). ´ pro majoritu jsou um ˇ e´ pˇresnosti jednotliv´ych modelu. Vahy ´ ern ˚
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
19 / 36
Boosting (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
20 / 36
Adaboost ´ ejˇ ˇ s´ı algoritmus pro Boosting se naz´yva´ Adaboost. Nejznam ´ ´ a´ klasifikaci do dvou tˇr´ıd (+1 / -1). Zakladn´ ı algoritmus pˇredpoklad ´ ˇ ht je model Znaˇcen´ı n je poˇcet vzoru˚ v trenovac´ ı mnoˇzine. ´ (klasifikator). 1
2 3
´ u˚ vˇsech vzoru˚ v trenovac´ ´ Nastav konstantn´ı vah ı mnoˇzineˇ na D1 (i) = n1 a nastav t = 1. ´ Nauˇc klasifikator ht . ´ ı chybu na trenovac´ ´ SpoˇcP ıch datech ´ıtej globaln´ ηt = ∀i,ht (xi )6=yi Dt (i)
4
´ vˇsech vstupn´ıch vzoru, ´ ˇ Zmeˇ nˇ vahy ht udelal ˚ u kter´ych klasifikator Dt (i) ηt chybu. Dt+1 (i) = Zi 1−ηt . ∀i, kde ht (xi ) 6= yi .
5
´ ı chyba ηt klesla pod stanovenou hranici, skonˇci. Pokud globaln´ Jinak pokraˇcuj bodem 2. ˇ Prezentace venovan a´ pˇr´ımo algoritmu Adaboost http://www.robots.ox.ac.uk/˜az/lectures/cv/adaboost_matas.pdf ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
21 / 36
Stacking
´ Nezavisle nauˇc´ım skupinu modelu, ˚ pouˇziji odliˇsne´ algoritmy uˇcen´ı I
´ ruzn ruzn ˚ e´ implicitn´ı pˇredpoklady, ruzn ˚ e´ hypotezy, ˚ e´ chyby.
´ ıho v´ystupu pouˇziji m´ısto majority dalˇs´ı model Pro urˇcen´ı finaln´ I I I
ˇr´ıkame ´ mu meta-model, cˇ asto jde o logistickou regresi, v´ystupy jednotliv´ych modelu˚ slouˇz´ı jako vstupy meta-modelu, ´ ı s majoritou vetˇ ˇ s´ı moˇznosti pro kombinaci v´ystupu. ve srovnan´ ˚
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
22 / 36
Stacking (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
23 / 36
Cascade generalization
´ Modely v ensemblu tvoˇr´ım postupneˇ a zavisle I I
ˇ ym dopln´ım v´ystupy pˇredchoz´ıch modelu, ke vstupn´ım promenn´ ˚ ´ ı ke zmen ˇ eˇ v algoritmu uˇcen´ı. dochaz´
´ ˇ e´ (x1 , x2 , . . . , xn , y1 , . . . , yi−1 ) Vstupem i-teho modelu jsou promenn I I
kde x1 , . . . , xn jsou pˇr´ıznaky ze vstupn´ıch dat, kde y1 , . . . , yi−1 jsou v´ystupy pˇredchoz´ıch modelu. ˚
´ a v´ystupem ensemblu je v´ystup Modely se uˇc´ı jeden po druhem posledn´ıho modelu.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
24 / 36
Cascade generalization (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
25 / 36
Cascading
Podobneˇ jako u Boostingu se dalˇs´ı modely specializuj´ı na vzory, ktere´ pˇredchoz´ı modely klasifikovaly sˇ patneˇ – ktere´ indikovaly ˇ n´ızkou pravdepodobnost pˇriˇrazen´ı vzoru do dane´ tˇr´ıdy. ´ ı v´ystupu ensemblu se pouˇzije v´ystup modelu, kter´y Pˇri poˇc´ıtan´ ´ a´ dostateˇcneˇ vysokou ppst v´ystupn´ı tˇr´ıdy. udav
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
26 / 36
Cascading (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
27 / 36
Delegating
´ ´ Trenovac´ ı mnoˇzina prvn´ıho modelu je cela´ trenovac´ ı mnoˇzina. ´ ´ Do trenovac´ ı mnoˇziny dalˇs´ıho klasifikatoru pˇriˇrad´ım vstupn´ı vzory, ´ sˇ patneˇ nebo ppst jejich zaˇraen´ı do ktere´ byly klasifikovany ´ e´ tˇr´ıdy je menˇs´ı neˇz urˇcen´y prah. ´ spravn V´ystup ensemblu je v´ystup modelu, kter´y indikuje dostateˇcneˇ vysokou ppst pˇriˇrazen´ı do dane´ tˇr´ıdy.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
28 / 36
Delegating (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
29 / 36
Arbitrating
´ stn´ı metoda, kde jsou dva typy modelu˚ Trochu zvlaˇ I I
ˇ standardn´ı modely, predikuj´ıc´ı c´ılovou promennou, ˇ snost standardn´ıch modelu. rozhodˇc´ı modely, ktere´ predikuj´ı usp ´ eˇ ˚
Kaˇzd´y stadardn´ı model ma´ svuj ˚ rozhoˇc´ı model. ´ Kaˇzda´ dvojice stardn´ı+rozhodˇc´ı model je uˇcena nezavisle. V´ystupem ensemblu je model, jehoˇz rozhodˇc´ı predikuje nejvyˇssˇ ´ı ˇ m´ıru usp ´ echu.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
30 / 36
Arbitrating (2)
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
31 / 36
ˇ relevatn´ıch pˇr´ıznaku˚ V´yber
´ ˇ e´ Posledn´ı tema tohoto kurzu – opravdu vˇsechny vstupn´ı promenn potˇrebuji ke klasifikaci? ´ vetˇ ˇ s´ı roli Pˇri klasifikaci zdrav´ych a nemocn´ych lid´ı asi bude hrat jejich teplota a tlak, neˇz barva vlasu. ˚ ˇ e, ´ se oznaˇcuj´ı Techniky, ktere´ vyb´ıraj´ı vhodne´ vstupn´ı promenn jako feature selection (pˇr´ıpadneˇ feature ranking) metody. ˇ ı se do dvou hlavn´ıch kategori´ı: A del´ I
I
feature selection – tyto metody dodaj´ı seznam vstupn´ıch ˇ ych (atributu), ´ promenn´ ˚ ktere´ povaˇzuj´ı za duleˇ ˚ zite, ´ ´ feature ranking – tyto metody pˇriˇrad´ı kaˇzdemu atributu skore, kter´y indikuje vliv atributu na v´ystupn´ı tˇr´ıdu.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
32 / 36
Feature selection
Typicky hledaj´ı podmnoˇzinu atributu, ˚ na ktere´ model jeˇsteˇ funguje ˇ ı se do 3 hlavn´ıch kategori´ı: dobˇre. Del´ I
I
ˇ y model, Wrappers – vyberou skupinu atributu, ˚ nad n´ı nauˇc´ı nejak´ spoˇc´ıtaj´ı jeho pˇresnost a podle pˇresnosti uprav´ı skupinu atributu, ˚ atd... ˇ jen m´ısto modelu˚ se vyhodnocuj´ı Filters – funguj´ı dost podobne, tzv. filtry. F
I
´ souvislosti rozum´ı napˇr´ıklad korelace mezi vybranou Filtry se v teto ´ skupinou vstupu˚ a v´ystupem nebo vzajemn a´ informace, ...
´ do uˇc´ıc´ıho Embedded techniques – tento zpusob je zabudovan ˚ ˇ e´ model vyuˇz´ıva, ´ se algoritmu modelu a podle toho, ktere´ promenn sestavuje seznam duleˇ ˚ zit´ych atributu. ˚
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
33 / 36
Feature selection (2)
´ ı vhodne´ kombinace se cˇ asto uplatnuje ˇ Pˇri hledan´ ”hladov´y” pˇr´ıstup. ´ mnoˇzinu s jedn´ım atributem, ktera´ ma´ nejvyˇssˇ ´ı Nejprve hledam ´ (napˇr´ıklad nejvyˇssˇ ´ı pˇresnost modelu). skore ´ jednoprvkove´ mnoˇzineˇ zkouˇs´ım pˇridavat ´ K teto dalˇs´ı atribut a ´ ˇ s´ı zlepˇsen´ı modelu. hledam, kter´y pˇrinese nejvetˇ ´ tˇret´ı, a tak dale, ´ dokud se model nepˇrestane Pak hledam zlepˇsovat.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
34 / 36
Feature ranking
ˇ e´ skore, ´ Pˇriˇrazuje kaˇzde´ vstupn´ı promenn ktere´ urˇcuje jej´ı v´yznamnost. ˇ Casto se pouˇz´ıvaj´ı stejne´ metody, ktere´ se na pˇredchoz´ım slajdu oznaˇcovaly jako filters: I I I I
´ vzajemn a´ informace mezi jednotliv´ymi atributy a v´ystupem, korelace, informaˇcn´ı entropie, pˇresnost perceptronu s jedn´ım vstupem.
ˇ ˇ Je pak na cˇ loveku, jak techto informac´ı vyuˇzije.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
35 / 36
Shrnut´ı
´ ı modelu˚ je dnes standardn´ım postupem Kombinovovan´ I I
ˇ diverzita slab´ych modelu˚ spojena´ s jejich pˇresnost´ı vede k usp ´ echu, ˇ za pˇresnost plat´ıme cˇ asem a nekdy i srozumitelnost´ı.
´ a´ “no free lunch” teoremu ´ Jako kaˇzda´ jina´ metoda podleh I
´ zlepˇsen´ı pˇresnosti nedosahneme “automaticky a mechanicky”.
Literatura mj. Dietterich: Ensemble Methods in Machine Learning, Multiple classifier systems, Springer, 2000.
ˇ CVUT (FEL)
´ Sloˇzene´ klasifikatory
16.12.2014
36 / 36
