´pi tanula ´s – III. Ge Szepesv´ari Csaba MTA SZTAKI
2005 ´apr. 11
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
1 / 37
1
¨ nte ´si fa ´k Do
2
¨gyelet ne ´lku ¨li tanula ´s Felu Klaszter-anal´ızis EM algoritmus Gauss Mixture Models F˝ okomponens anal´ızis
3
¨ ´s Osszefoglal a
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
2 / 37
¨ nte ´si fa ´k Do ¨ Otlet: input t´er part´ıcion´al´asa
Oszd meg ´es uralkodj (divide and conquer)! Top-down” part´ıcion´al´as; lehet˝os´egek: ”
Egyszerre egy attib´ utum (ID3, C4.5) vs. ´altal´anos helyzet˝ u egyenesek ment´en (CART) Melyik attrib´ utum? Hol v´agjunk? H´any r´eszre?
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
3 / 37
¨ nte ´si fa ´k Do
Fogalmak Cs´ ucspontok, ´agak, levelek Nem lev´el cs´ ucspontok: egy-egy attrib´ utumra vonatkoz´o teszt ´ Ag: a teszt egy kimenetele (pl. Sz´ın=piros) Lev´el: C´ımke, vagy eloszl´as a c´ımk´eken Klasszifik´aci´o: A fa gy¨oker´et˝ol egy lev´elig egy u ´t bej´ar´asa
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
4 / 37
´lda: Teniszezzu ¨nk? Pe
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
5 / 37
¨ nte ´si fa ´k e ´p´ıte ´se (Quinlan, ’93) Do
Top-down ´ep´ıtkez´es Indul´askor minden p´elda a gy¨ ok´erhez tartozik L´ep´esenk´ent egy attrib´ utumot v´alasztva rekurz´ıvan part´ıcion´aljuk a p´eld´akat
Bottom-up ny´ır´as (pruning) R´eszf´akat/´agakat tesztelj¨ unk ´es dobjuk ki ˝ oket, ha a CV-vel becs¨ ult hibaar´anyon ez jav´ıt
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
6 / 37
´lasszam..? Melyiket va
Melyik a legalkalmasabb attrib´ utum? Amelyik a legkisebb f´ahoz vezet Heurisztika: V´alasszunk olyan attrib´ utumot, amelyik a legegyszer˝ ubb” ” alfeladathoz (n´odushoz) vezet
J´ os´ag: amelyik attrib´ utumn´al a legnagyobb, azt v´alasztjuk ki Legismertebb m´ert´ekek: Information gain (ID3/C4.5) Information gain ratio Gini index
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
7 / 37
´cio ´ nyerese ´g I. Informa X , Y val.v´altoz´ok Y entr´ opi´aja: V´arhat´o k´odhossz, optim´alis k´odol´as mellett: ! H(Y ) = −E[log2 p(Y )] = −
X
P(Y = yi ) log2 P(Y = yi ) .
i
Individu´alis felt´eteles entr´opia: Y entr´opi´aja azokban az esetekben, amikor X = x: X H(Y |X = x) = P(Y = yi |X = x) log2 P(Y = yi |X = x) i
azaz Y k´odhossza, felt´eve, hogy X = x. (Megj.: H(Y |X = x) 6= −E[log2 P(Y )|X = x]!) Felt´eteles entr´opia: P H(Y |X ) = E[H(Y |X )] = x P(X = x)H(Y |X = x); Y v´arhat´o k´ odhossza, felt´eve, hogy X ´ert´eke felhaszn´alhat´o a k´odol´askor. (Megj.: H(Y , X ) = H(X ) + H(Y |X ) = (H(Y ) + H(X |Y ))) Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
8 / 37
´cio ´ nyerese ´g II. Informa
X miatti inform´aci´o nyeres´eg Y -ra n´ezve: v´arhat´olag mennyivel cs¨ okken Y entr´opi´aja, az´altal, hogy X -et felhaszn´alhatjuk a k´ odol´askor: I (Y , X ) = H(Y ) − H(Y |X ). (Megj. I (Y , X ) = I (X , Y ), ez´ert nem I (Y |X )-et haszn´alunk a jel¨ ol´esben) K¨ ov: Ha X hasznos inform´aci´ot hordoz Y -ra n´ezve, akkor I (Y , X ) nagy!
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
9 / 37
´lda biztos´ıta ´smatematika ´ bo ´l Pe Feladat Adott u ¨gyf´el meg´eri-e a 80-at? Y = 1 – hossz´ u ´elet˝ u, Y = 0 – nem hossz´ u ´elet˝ u. M´ ultbeli adatok alapj´an a k¨ovetkez˝ot tal´aljuk: I (Y |Hajsz´ın) = 0.01 I (Y |Doh´anyos) = 0.2 I (Y |Nem) = 0.25 I (Y |SzSzUtols´oSzJegye) = 0.0001 Melyik attrib´ utumokat ´erdemes figyelembe venni? IG: mennyire ´erdekes egy 2D-s kontingencia t´abla.
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
10 / 37
´rte ´ku ˝ attribu ´tumok Sok-e
Probl´ema: Ha az attrib´ utum extr´em sok ´ert´eket vesz fel.. (pl. sz.sz.) Y |X = x nagyobb es´ellyel egyszer˝ u”, ´ıgy: ” IG j´o es´ellyel sok ´ert´eket felvev˝ o attrib´ utumot v´alaszt .. ez t´ ultan´ıt´ashoz vezethet
Megold´as?
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
11 / 37
´ltan´ıta ´s elkeru ¨ le ´se Tu .. pl. relativiz´aljuk az inform´aci´o nyeres´eget: def
IR(Y |X ) = I (Y , X )/H(Y |X ) =⇒Ar´anyos´ıtott inform´aci´o nyeres´eg P M´as j´ os´ag m´ert´ekek;P pl. Gini index: G (Y ) = 1 − i P(Y = yi )2 ; G (Y |X = x) = 1 − i P(Y = yi |X = x)2 ; G(Y |X ) = E [G (Y |X )] ´ Early stopping: Alljunk le a fa n¨oveszt´es´evel (pl. ha a tan´ıt´asi mint´ak sz´ama egy adott ´agban m´ar kicsi) Tan´ıtsunk t´ ul, majd vagdossuk le a r´eszf´akat/´agakat f¨ uggetlen valid´aci´os adatokon m´ert teljes´ıtm´eny seg´ıts´eg´evel (+++) A levelekn´el haszn´aljunk Laplace korrekci´ot ..
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
12 / 37
´b praktikus ke ´rde ´sek Egye
Hi´anyz´o attrib´ utum ´ert´ekek Klasszifik´aci´os k¨olts´egek Sz´am´ıt´asig´eny =⇒ Quinlan’s C4.5 (1993), majd C5.0
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
13 / 37
¨gyelet ne ´lku ¨li (unsupervised) tanula ´s Felu
Adatok: X1 , . . . , Xn ; Xi ∼ p(·), p nem ismert K´erd´esek: p =? – s˝ ur˝ us´egf¨ uggv´eny becsl´es Milyen term´eszetes csoportok k¨ ul¨ on´ıthet˝oek el a adatban? – klaszterez´es
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
14 / 37
Klaszter-anal´ızis
Klaszterez˝o f¨ uggv´eny: C : Rd → {1, 2, . . . , k}, C =?, k =? Kvant´al´o f¨ uggv´eny: Q : Rd → {x1 , x2 , . . . , xk }, Q =?, x1 , . . . , xk =?, k =? Objektumok csoportos´ıt´asa u ´gy, hogy .. a hasonl´obbak ker¨ uljenek azonos csoportba .. kvant´al´asi hiba minim´alis legyen
Alapprobl´ema: Hogy defini´aljuk a hasonl´os´agot/kvant´al´asi hib´at?
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
15 / 37
˝ algoritmusok – alapt´ıpusok Klaszterezo
Kombinatorikus m´odszerek K¨ozvetlen¨ ul az adatokkal dolgoznak
Kever´ek-eloszl´asok modellez´ese (Mixture Modeling) Valamilyen kever´ek-eloszl´ast felt´etelez
M´ odusz-keres´es S˝ ur˝ us´egf¨ uggv´enyek m´ odusz´anak keres´ese
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
16 / 37
´ dszerek Kombinatorikus mo Klaszteren bel¨ uli k¨ ul¨onb¨oz˝os´eg (dissimilarity) minimaliz´al´asa ekvivalens: klaszterek k¨oz¨otti k¨ ul¨onb¨oz˝os´eg maximaliz´al´asa Mi´ert? Klaszteren bel¨ uli k¨ ul¨onb¨oz˝os´eg: XX W (C ) = I(C (Xp ) = C (Xq )) d(Xp , Xq ) p
q
Klaszterek k¨oz¨otti k¨ ul¨onb¨oz˝os´eg: XX B(C ) = I(C (Xp ) 6= C (Xq )) d(Xp , Xq ) p
q
Teljes k¨ ul¨onb¨oz˝os´eg: T (C ) = W (C ) + B(C ) ≡ const.
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
17 / 37
k-Means
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
18 / 37
k-Medoids
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
19 / 37
´rte ´ke? Mennyi legyen k e
N´eha a probl´em´aval j¨on k ´ert´eke is!:) Ha k nem adott, akkor Wk (Ck∗ )-ot megvizsg´aljuk.. Ha k n˝o, Wk (Ck∗ ) cs¨okken.. B¨ untess¨ uk a nagyobb k ´ert´eket (MDL, MAP/BIC,..) Valid´aci´os adat: cross-validation
pl. X-means” (D. Pelleg, A. Moore, 2000) ”
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
20 / 37
˝ ru ˝ se ´gfu ¨ggve ´ny becsle ´s EM algoritmus – su Dn = (X1 , X2 , . . . , Xn ); Xi ∼ p p =? Maximum likelihood: p = p(·; θ); P L(θ) = log p(Dn ; θ) = i log p(Xi ; θ) – f¨ uggetlens´eg X θML = argmaxθ log p(Xi ; θ) i
Rejtett v´altoz´ok: (Xi , Zi ) ∼ p Mi´ert? Kever´ek eloszl´asok Hidden-Markov Models (rejtett Markov modellek)
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
21 / 37
´s kevere ´k eloszla ´sokkal Modelleze ´lda: Gaussok kevere ´ke Pe Kever´ek: p(x) =
r X
wj N (x; µj , Σj );
wj ≥ 0,
r X
j=1
N (x; µ, Σ) =
wj = 1
j=1
1 T −1 p exp − (x − µ) Σ (x − µ) 2 (2π)d/2 |Σ| 1
Generat´ıv szeml´elet: Zi
∼ (w1 , . . . , wr ),
Xi
∼ N (x; µZi , ΣZi )
i = 1, . . . , n
Param´eterek: θ = (w1 , µ1 , Σ1 , . . . , wr , µr , Σr ) =? Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
22 / 37
´kek - II. Kevere
Dn = (X1 , X2 , . . . , Xn ); Xi ∼ p p = p(x, z; θ) =? Marginaliz´al´as: p(x; θ) = E[p(x, Z ; θ)] Maximum likelihood: θML = argmaxθ
X
log p(Xi ; θ) =?
i
Rejtett v´altoz´ok ´ert´ek´enek dek´odol´asa: argmaxz p(z|x; θ) =? (pl. HMM)
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
23 / 37
˝ tlense ´ge Jensen egyenlo
´tel Te Ha f : D → R konvex, ´es X D-´ert´ek˝ u val.v´altoz´o, akkor E[f (X )] ≥ f (EX ) (f konk´av, akkor E[f (X )] ≤ f (EX ))
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
24 / 37
˝ le ´pe ´sek EM algoritmus: elso Ha Zi -t megfigyelt¨ uk volna θML sz´amolhat´o lenne De Zi -t nem figyelt¨ uk meg.. Log-likelihood-ra als´ o becsl´es: X X X L(θ) = log p(Xi ; θ) = log p(Xi , z; θ) i
z
=
X
X
≥
XX
i
log
z
i
i
Qi (z)
Qi (z) log
z
p(Xi , z; θ) (Jensen :) Qi (z) p(Xi , z; θ) Qi (z)
– aholis Qi (·) egy tetsz˝oleges eloszl´as. Jensen: Yi (x) =
p(x,Zi ;θ) Qi (Zi ) -re,
Zi ∼ Qi (·), f (w ) = log(w ) mellett.
Hogy v´alasszuk Qi -t? Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
25 / 37
´laszta ´sa EM algoritmus: Qi va L(θ) =
X
log p(Xi ; θ) =
i
X
log
X
=
X
≥
XX
log
Qi (z)
p(Xi , z; θ) Qi (z)
Qi (z) log
p(Xi , z; θ) Qi (z)
X z
i
i
p(Xi , z; θ)
z
i
z
Hogy v´alasszuk Qi -t? ¨ ´ Otlet: Ugy, hogy fent egyenl˝os´eg legyen. Jensen: Yi ≡ const =⇒ egyenl˝os´eg P Qi (z) ∝ p(Xi , z; θ), spec. z Qi (z) = 1 miatt p(Xi , z; θ) Qi (z) = P ≡ p(z|x; θ) z p(Xi , z; θ) Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
26 / 37
EM algoritmus
Algoritmus Input: (X1 , . . . , Xn ) – adatok; p(x, z; θ) modell t=0 Konvergenci´aig ism´etelni: E-step: Minden i-re, Qi (z) := p(z|Xi ; θt ) P P i ,z;θ) M-step: θt+1 := argmaxθ i z Qi (z) log p(X Qi (z) t := t + 1
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
27 / 37
EM algoritmus: konvergencia ´ ´ıta ´s All Az EM algoritmus konverg´al L(θ) egy lok´alis maximumhely´ehez Most csak: L(θ) sohasem cs¨okken Def.: A(θ; θ0 ) =
XX i
Qi (z; θ) log
z
p(Xi , z; θ0 ) Qi (z; θ)
Volt: L(θt ) = A(θt ; θt ) A(θt ; θt+1 ) = maxθ0 A(θt ; θ0 ) ≥ A(θt ; θt ) = L(θt ) L(θt+1 ) ≥ A(θt ; θt+1 )? – igen; volt: L(θ) ≥
XX i
Qi (z) log
z
p(Xi , z; θ) Qi (z)
spec. θ = θt+1 ,Qi (z) = Qi (z; θt )-ra is ´all. Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
28 / 37
´sik interpreta ´cio ´ .. EM algoritmus: egy ma
EM L(θ)-t nem cs¨okkenti Le´all´asi felt´etel: L(θ) nem sokat v´altozik Koordin´at´ank´enti optimaliz´al´as: Q = (Q1 , . . . , Qn ); P P J(Q, θ) = i z Qi (z) log Volt: L(θ) ≥ J(Q, θ) Interpret´aci´o:
p(Xi ,z;θ) Qi (z)
E-step: Q-ban maximaliz´ al´ as M-step: θ-ban maximaliz´ al´ as
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
29 / 37
´ la ´s Inicializa
EM iterat´ıv; nagyon ´erz´ekeny a kezdeti ´ert´ekekre Rossz pontb´ol ind´ıtva =⇒ rossz pontba konverg´al Gyors ´es min˝os´egi inicializ´al´asra van sz¨ uks´eg Gyakran: k-means (GMM-hez) Alternat´ıv´ak: Gaussian splitting, hierarchikus k-means
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
30 / 37
Gauss Mixture Models Modell: p(x; θ) =
r X
wj N (x; µj , Σj );
wj ≥ 0,
j=1
N (x; µ, Σ) =
r X
wj = 1
j=1
1 T −1 p exp − (x − µ) Σ (x − µ) 2 (2π)d/2 |Σ| 1
p(x, z; θ) = wz N (x; µz , Σz ) P p(x) = z p(x, z; θ) Behelyettes´ıt´es.. Qi (z; θ) = p(Z = z|Xi ; θ) = ..
Szepesv´ ari Csaba (SZTAKI)
p(Xi |Z =z;θ)p(Z =z;θ) p(Xi ;θ)
G´ epi tanul´ as – III.
´pr. 11 2005 a
31 / 37
´rt e ´rdekesek a GMM-ek Mie
Univerz´alis approxim´atorok
Diagon´alis GMM-ek is univerz´alis approxim´atorok
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
32 / 37
˝ komponens anal´ızis Fo
F˝okomponens anal´ızis = Principal Component Analysis (PCA) P´elda Helikopter-vezet´es t´avir´any´ıt´assal K´epess´eg ´ Elvezet karma” - rejtett v´altoz´ o ”
Feladat: keress¨ uk azt az ir´anyt (alteret), amelyikben az adat legjobban v´altozik
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
33 / 37
˝ komponens anal´ızis - Modellek Fo
Modell-1 (nem-parametrikus): Projekci´o ut´an az adatoknak a lehet˝ o legnagyobb legyen a varienci´aja
Modell-2 (nem-parametrikus) P : RdP → Rd projekci´ o egy m dimenzi´ os alt´erre m Px = j=1 vj (vjT x), viT vj = δij . argminP proj. E[kPX − X k22 ] =?
Modell-3 (parametrikus) X = AU + W U ∈ Rm , W ∈ Rd v.v. A ∈ Rd×m m´atrix (X1 , . . . , Xn )-t figyelj¨ uk meg, A =? Felt´etel: U, W Gauss ( ellipszisek”) ”
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
34 / 37
Algoritmus
Algoritmus Input: (X1 , . . . , Xn ) Centr´alunk: Xi0 := Xi − m, m = (1/n)
P
Xi . P 0 0 T Empirikus kovariencia m´atrix: C = (1/n) i Xi (Xi ) P C saj´at´ert´ekfelbont´asa: C = di=1 λi vi viT , λ1 > λ2 > . . . λd P T Output: P = m j=1 vj vj
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
i
´pr. 11 2005 a
35 / 37
˝ go ¨ rbe ´k e ´s felu ¨letek Fo
Principal curves and surfaces
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
36 / 37
¨ ´s Osszefoglal a
D¨ ont´esi f´ak: top-down, moh´o (information gain); ID3/C4.5 Fel¨ ugyelet n´elk¨ uli tanul´as Klaszterez´es (k-means, k-medoid) EM-algoritmus Gauss-kever´ekek F˝okomponens anal´ızis
Legk¨ ozelebb: F¨ uggetlen komponens anal´ızis Line´aris diszkrimin´ansok NMF Feature-selection Feature weighting; boosting
Szepesv´ ari Csaba (SZTAKI)
G´ epi tanul´ as – III.
´pr. 11 2005 a
37 / 37
