ˇ zovan´ ´ ı Dat Vyteˇ ´ ska 9 – Linearn´ ´ ı klasifikator, ´ ´ Pˇrednaˇ rozˇs´ıˇren´ı baze, LDA, logisticka´ regrese ˇ Miroslav Cepek
ˇ ´ CVUT Fakulta Elektrotechnicka, ´ ı fond Praha & EU: Evropsk´y socialn´ Investujeme do vaˇs´ı budoucnosti
13.12.2011 ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
1 / 32
´ Klasifikatory
´ klasifikaˇcn´ı algoritmy? Jake´ znate
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
2 / 32
´ Klasifikatory
´ klasifikaˇcn´ı algoritmy? Jake´ znate I I I
Naive Bayes Rozhodovac´ı strom KNN
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
2 / 32
´ Klasifikatory
´ klasifikaˇcn´ı algoritmy? Jake´ znate I I I
Naive Bayes Rozhodovac´ı strom KNN
Jak funguj´ı?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
2 / 32
´ Klasifikatory
´ klasifikaˇcn´ı algoritmy? Jake´ znate I I I
Naive Bayes Rozhodovac´ı strom KNN
Jak funguj´ı? I
I I
ˇ Naive Bayes poˇc´ıta´ pravdepodobnost pˇriˇrazen´ı do tˇr´ıdy za ´ ım. podm´ınky dane´ pozorovan´ Rozhodovac´ı strom generuje posloupnost rozhodnut´ı. ´ KNN hleda´ nejbliˇzs´ı instance z trenovac´ ı mnoˇziny.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
2 / 32
Rozhodovac´ı hranice Dalˇs´ı moˇzn´y pohled je z hlediska rozhodovac´ı hranice. ´ ı patˇrit do Rozhodovac´ı hranice je m´ısto, kde instance pˇrestavaj´ tˇr´ıdy A a zaˇc´ınaj´ı patˇrit do tˇr´ıdy B.
Pˇrevzadto z http://openclassroom.stanford.edu/ MainFolder/DocumentPage.php?course= MachineLearning&doc=exercises/ex8/ex8.html ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
3 / 32
Rozhodovac´ı hranice (2)
´ nasleduj´ ´ Co kdyˇz mam ıc´ı data: Jak bude vypadat nejjednoduˇssˇ ´ı rozhodovac´ı hranice, ktera´ data oklasifikuje bez chyby?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
4 / 32
Rozhodovac´ı hranice (2)
´ nasleduj´ ´ Co kdyˇz mam ıc´ı data: Jak bude vypadat nejjednoduˇssˇ ´ı rozhodovac´ı hranice, ktera´ data oklasifikuje bez chyby? Staˇc´ı pˇrece pˇr´ımka!
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
4 / 32
´ ı klasifikator ´ Linearn´ Takovou pˇr´ımku um´ıme celkem jednoduˇse naj´ıt a vyrobit :). Jak vypada´ rovnice pˇr´ımky?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
5 / 32
´ ı klasifikator ´ Linearn´ Takovou pˇr´ımku um´ıme celkem jednoduˇse naj´ıt a vyrobit :). Jak vypada´ rovnice pˇr´ımky? y=
X
wj xj = wx
j
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
5 / 32
´ ı klasifikator ´ Linearn´ Takovou pˇr´ımku um´ıme celkem jednoduˇse naj´ıt a vyrobit :). Jak vypada´ rovnice pˇr´ımky? y=
X
wj xj = wx
j
Jak zjist´ıme, do ktere´ tˇr´ıdy patˇr´ı vzor x?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
5 / 32
´ ı klasifikator ´ Linearn´ Takovou pˇr´ımku um´ıme celkem jednoduˇse naj´ıt a vyrobit :). Jak vypada´ rovnice pˇr´ımky? y=
X
wj xj = wx
j
Jak zjist´ıme, do ktere´ tˇr´ıdy patˇr´ı vzor x? Prost´ym dosazen´ım! Pokud y > 0 vzor patˇr´ı do jedne´ tˇr´ıdy, y < 0 vzor patˇr´ı do druhe´ tˇr´ıdy. ˇ ı y = 0 je rozhodovac´ı hranice, kde se nelze rozhodnout. Naˇstest´ ´ a´ cˇ asto. se toto nestav
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
5 / 32
´ ı klasifikator ´ Linearn´ Takovou pˇr´ımku um´ıme celkem jednoduˇse naj´ıt a vyrobit :). Jak vypada´ rovnice pˇr´ımky? y=
X
wj xj = wx
j
Jak zjist´ıme, do ktere´ tˇr´ıdy patˇr´ı vzor x? Prost´ym dosazen´ım! Pokud y > 0 vzor patˇr´ı do jedne´ tˇr´ıdy, y < 0 vzor patˇr´ı do druhe´ tˇr´ıdy. ˇ ı y = 0 je rozhodovac´ı hranice, kde se nelze rozhodnout. Naˇstest´ ´ a´ cˇ asto. se toto nestav ´ ı < 0 nebo > 0 muˇ Porovnan´ ˚ zeme nahradit napˇr´ıklad funkc´ı ´ ´ signum(y) ktera´ vrac´ı +1 pro kladna´ cˇ ´ısla a −1 pro zaporn a. ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
5 / 32
´ ı klasifikator ´ Linearn´ (2)
ˇ y problem? ´ Vid´ıte v rovnici nejak´
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
6 / 32
´ ı klasifikator ´ Linearn´ (2)
ˇ y problem? ´ Vid´ıte v rovnici nejak´ Zkusme dosadit do rovnice x1 = x2 = 0. Co vyjde? y = 0 bez ohledu na nastaven´ı vah w1 , w2 . ´ ´ Rozhodovac´ı hranice libovolneho klasifikatoru tedy mus´ı ´ prochazet nulou resp. vektorem (0, 0, . . . , 0).
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
6 / 32
´ ı klasifikator ´ Linearn´ (2)
ˇ y problem? ´ Vid´ıte v rovnici nejak´ Zkusme dosadit do rovnice x1 = x2 = 0. Co vyjde? y = 0 bez ohledu na nastaven´ı vah w1 , w2 . ´ ´ Rozhodovac´ı hranice libovolneho klasifikatoru tedy mus´ı ´ prochazet nulou resp. vektorem (0, 0, . . . , 0). To je docela nepˇr´ıjemne´ omezen´ı – rozhodovac´ı hranice se ´ c´ı kolem nuly. Co s t´ım? vlastneˇ pouze otaˇ
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
6 / 32
´ ı klasifikator ´ Linearn´ (2)
ˇ y problem? ´ Vid´ıte v rovnici nejak´ Zkusme dosadit do rovnice x1 = x2 = 0. Co vyjde? y = 0 bez ohledu na nastaven´ı vah w1 , w2 . ´ ´ Rozhodovac´ı hranice libovolneho klasifikatoru tedy mus´ı ´ prochazet nulou resp. vektorem (0, 0, . . . , 0). To je docela nepˇr´ıjemne´ omezen´ı – rozhodovac´ı hranice se ´ c´ı kolem nuly. Co s t´ım? vlastneˇ pouze otaˇ P ˇ rovnici pˇr´ımky na j wj xj + Θ = 0. Muˇ ˚ zeme pˇridat zmenit ´ Θ je aditivn´ı konstanta a oznaˇcuje se jako prah.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
6 / 32
´ ı klasifikator ´ Linearn´ (3)
´ ı klasifikator ´ ˇ ı: Rovnice pro linearn´ se tedy m´ırneˇ zmen´ X wj xj + Θ = wx + Θ y= j
´ Ale jinak vˇse zustane stejne. ˚ Pokud tedy vyjde, zˇ e y > 0 vzor patˇr´ı do jedne´ tˇr´ıdy, y < 0 vzor patˇr´ı do druhe´ tˇr´ıdy.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
7 / 32
´ Prah Tedˇ zb´yva´ pouze naj´ıt vektor koeficientu˚ (vah) (w1 , w2 , . . . , wn ) a prahu Θ. ´ Θ pˇredstavuje nejakou ˇ ´ Nejprve se zamysleme zda prah anomalii, ´ ı zachazen´ ´ ktera´ potˇrebuje specialn´ ı.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
8 / 32
´ Prah Tedˇ zb´yva´ pouze naj´ıt vektor koeficientu˚ (vah) (w1 , w2 , . . . , wn ) a prahu Θ. ´ Θ pˇredstavuje nejakou ˇ ´ Nejprve se zamysleme zda prah anomalii, ´ ı zachazen´ ´ ktera´ potˇrebuje specialn´ ı. Tak napul ˚ :). Nepotˇrebuje, pokud trochu uprav´ıme vstupn´ı data. ˇ jeden atribut (vstupn´ı promennou, ˇ Co kdyby vˇsechny vzory meli ˇrekneme ˇ x0 ) se stejnou hodnotou? Kdyˇz pak budu poˇc´ıtat w0 x0 , vyjde mi vˇzdy stejna´ hodnota... to je ´ s prah! ´ pˇrece naˇ
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
8 / 32
´ Prah Tedˇ zb´yva´ pouze naj´ıt vektor koeficientu˚ (vah) (w1 , w2 , . . . , wn ) a prahu Θ. ´ Θ pˇredstavuje nejakou ˇ ´ Nejprve se zamysleme zda prah anomalii, ´ ı zachazen´ ´ ktera´ potˇrebuje specialn´ ı. Tak napul ˚ :). Nepotˇrebuje, pokud trochu uprav´ıme vstupn´ı data. ˇ jeden atribut (vstupn´ı promennou, ˇ Co kdyby vˇsechny vzory meli ˇrekneme ˇ x0 ) se stejnou hodnotou? Kdyˇz pak budu poˇc´ıtat w0 x0 , vyjde mi vˇzdy stejna´ hodnota... to je ´ s prah! ´ pˇrece naˇ ´ ke kaˇzdemu ´ Takˇze pˇridam vzoru jeˇsteˇ jednu dimenzi, ktera´ bude m´ıt konstantn´ı hodnotu – pro jednoduchost 1 (ale muˇ ˚ zete mu pˇriˇradit libovolnou nenulovou hodnotu). ´ nemus´ım specialn ´ eˇ starat. Pak uˇz se o prah ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
8 / 32
Gradientn´ı sestup – krok stranou
Gradientn´ı sestup je iterativn´ı optimalizaˇcn´ı metoda. ´ ´ Jde o to, zˇ e mame funkci f (x) a hledame jej´ı minimum. A jak minimum naj´ıt? Budu hledat takove´ x, kde ma´ funkce f (x) nejniˇzsˇ ´ı hodnotu. ´ nejak ˇ e´ x0 a znam ´ hodnotu f (x0 ). A hledam ´ v okol´ı x0 , nejake´ Mam ´ dokola, x1 , kde bude hodnota f (x1 ) niˇzsˇ ´ı. A to budu opakovat stale ´ nepujde. aˇz to dal ˚
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
9 / 32
Gradientn´ı sestup – krok stranou
Gradientn´ı sestup je iterativn´ı optimalizaˇcn´ı metoda. ´ ´ Jde o to, zˇ e mame funkci f (x) a hledame jej´ı minimum. A jak minimum naj´ıt? Budu hledat takove´ x, kde ma´ funkce f (x) nejniˇzsˇ ´ı hodnotu. ´ nejak ˇ e´ x0 a znam ´ hodnotu f (x0 ). A hledam ´ v okol´ı x0 , nejake´ Mam ´ dokola, x1 , kde bude hodnota f (x1 ) niˇzsˇ ´ı. A to budu opakovat stale ´ nepujde. aˇz to dal ˚ ´ se chci dostat do udol´ ´ se, kter´ym smerem ˇ ”Na horach ´ ı. Pod´ıvam ˇ am ´ krok t´ım smerem. ˇ se kopec nejv´ıc sniˇzuje a udel A zase se ´ ˇ am ´ krok. A tak dale, ´ aˇz pod´ıvam, kam je to nejv´ıc z kopce a udel ´ nejde, cˇ ili jsem v udol´ jednou zjist´ım, zˇ e to dal ´ ı.”
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
9 / 32
Gradientn´ı sestup – krok stranou (2)
ˇ nejvetˇ ˇ s´ıho V matematice existuje moˇznost, jak zjistit smer ´ ı derivace vzestupu hodnoty funkce - gradient. To je prvn´ı parcialn´ ˇ pujdu ˇ podle vˇsech dimenz´ı. Kdyˇz pujdu pˇresneˇ opaˇcne, ve smeru ˚ ˚ ˇ nejvetˇs´ıho poklesu. ´ ıch derivac´ı podle jednotliv´ych Gradient je vektor parcialn´ ˇ ych: promenn´ grad(f (x1 , x2 , . . . , xn )) = (
ˇ CVUT (FEL)
∂f ∂f ∂f , ,..., ) ∂x1 ∂x2 ∂xn
Self Organizing Map
13.12.2011
10 / 32
Chybova´ funkce a gradientn´ı sestup ´ Stejneˇ jako u jin´ych klasifikaˇcn´ıch metod, hledame nastaven´ı ´ ´ aby klasifikoval spravn ´ eˇ co nejv´ıc klasifikatoru (zde vah) takove, vzoru. ˚ ˇ Mejme tedy chybovou funkci J(w, χ), ktera´ vrac´ı poˇcet sˇ patneˇ klasifikovan´ych vzoru˚ x z mnoˇziny vzoru˚ χ (napˇr´ıklad z testovac´ı ´ w. mnoˇziny) pˇri dan´ych vahach
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
11 / 32
Chybova´ funkce a gradientn´ı sestup ´ Stejneˇ jako u jin´ych klasifikaˇcn´ıch metod, hledame nastaven´ı ´ ´ aby klasifikoval spravn ´ eˇ co nejv´ıc klasifikatoru (zde vah) takove, vzoru. ˚ ˇ Mejme tedy chybovou funkci J(w, χ), ktera´ vrac´ı poˇcet sˇ patneˇ klasifikovan´ych vzoru˚ x z mnoˇziny vzoru˚ χ (napˇr´ıklad z testovac´ı ´ w. mnoˇziny) pˇri dan´ych vahach ´ nehod´ı – neum´ım spoˇc´ıtat parcialn´ ´ ı derivace (a Ale takova´ se nam tud´ızˇ ani gradient).
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
11 / 32
Chybova´ funkce a gradientn´ı sestup ´ Stejneˇ jako u jin´ych klasifikaˇcn´ıch metod, hledame nastaven´ı ´ ´ aby klasifikoval spravn ´ eˇ co nejv´ıc klasifikatoru (zde vah) takove, vzoru. ˚ ˇ Mejme tedy chybovou funkci J(w, χ), ktera´ vrac´ı poˇcet sˇ patneˇ klasifikovan´ych vzoru˚ x z mnoˇziny vzoru˚ χ (napˇr´ıklad z testovac´ı ´ w. mnoˇziny) pˇri dan´ych vahach ´ nehod´ı – neum´ım spoˇc´ıtat parcialn´ ´ ı derivace (a Ale takova´ se nam tud´ızˇ ani gradient). P Zkusme jinou – E(w) = x∈χerr (−w(t)x), kde χerr jsou sˇ patneˇ klasifikovane´ vzory z χ. To uˇz je spojita´ funkce.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
11 / 32
Chybova´ funkce a gradientn´ı sestup ´ Stejneˇ jako u jin´ych klasifikaˇcn´ıch metod, hledame nastaven´ı ´ ´ aby klasifikoval spravn ´ eˇ co nejv´ıc klasifikatoru (zde vah) takove, vzoru. ˚ ˇ Mejme tedy chybovou funkci J(w, χ), ktera´ vrac´ı poˇcet sˇ patneˇ klasifikovan´ych vzoru˚ x z mnoˇziny vzoru˚ χ (napˇr´ıklad z testovac´ı ´ w. mnoˇziny) pˇri dan´ych vahach ´ nehod´ı – neum´ım spoˇc´ıtat parcialn´ ´ ı derivace (a Ale takova´ se nam tud´ızˇ ani gradient). P Zkusme jinou – E(w) = x∈χerr (−w(t)x), kde χerr jsou sˇ patneˇ klasifikovane´ vzory z χ. To uˇz je spojita´ funkce. ˇ A chybovou funkci E mohu minimalizovat zmenou vah – pomoc´ı gradientn´ıho sestupu. ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
11 / 32
Chybova´ funkce a gradientn´ı sestup ´ ı derivace chybove´ funkce E podle jedne´ promenn ˇ e´ Parcialn´ vypada´ takto: P ∂ x1 ∈χerr (−w1 (t)x1 ) ∂E = ∂w1 ∂w1 Kde x1 je prvn´ı souˇradnice z x a w1 je prvn´ı souˇradnice z w. P X ∂ x1 ∈χerr (−w1 (t)x1 ) = x1 ∂w1 x ∈χerr 1
´ er, ˇ zˇ e nejv´ıce chybu sn´ızˇ ´ım, pokud vahu ´ Z toho plyne zav w1 ˇ ım o souˇcet hodnot prvn´ıch vstupn´ıch promenn´ ˇ ych x1 vzoru˚ zmen´ ˇ chybu. na kter´ych jsem udelal ˇ e´ (vˇcetneˇ prahu). Analogicky i ostatn´ı vstupn´ı promenn ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
12 / 32
´ ıho klasifikatoru ´ Uˇcen´ı linearn´ ´ myˇslence je zaloˇzen Perceptronovy´ A pˇresneˇ na teto ´ algoritmus. (Proˇc zrovna perceptronov´y, nechame tedˇ stranou).
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
13 / 32
´ ıho klasifikatoru ´ Uˇcen´ı linearn´ ´ myˇslence je zaloˇzen Perceptronovy´ A pˇresneˇ na teto ´ algoritmus. (Proˇc zrovna perceptronov´y, nechame tedˇ stranou). 1 2
3
´ na nahodn ´ Inicializuj vahy e´ hodnoty. ´ Vezmi nahodn´ P y vstupn´ı vzor x. A spoˇc´ıtej hodnotu y(x) = sgn( j wj xj = wx). ´ Pokud se poˇzadovan´y v´ystup d(x) liˇs´ı od skuteˇcneho y(x), oprav ´ (w) takto: vahy I I
4
e(x) = d(x) − y(x) wi (t + 1) = wi (t) + ηe(x)xi
Pokud chceˇs, pokraˇcuj bodem 2).
η je koeficient uˇcen´ı, kter´y s postupem cˇ asu muˇ ˚ ze klesat k nule. http://neuron.felk.cvut.cz/courseware/data/chapter/36nan028/s04.html ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
13 / 32
Jednoznaˇcnost v´ysledne´ pˇr´ımky ´ Jak poznam, zˇ e se perceptronov´y algoritmus zastavil?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
14 / 32
Jednoznaˇcnost v´ysledne´ pˇr´ımky ´ Jak poznam, zˇ e se perceptronov´y algoritmus zastavil? ´ Je v´ysledna´ pˇr´ımka jedina´ moˇzna?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
14 / 32
Jednoznaˇcnost v´ysledne´ pˇr´ımky ´ Jak poznam, zˇ e se perceptronov´y algoritmus zastavil? ´ Je v´ysledna´ pˇr´ımka jedina´ moˇzna? Ne, takov´ych pˇr´ımek je dokonce nekoneˇcneˇ mnoho. ˇ ˇ z jine. ´ Pˇresto jsou nekter e´ lepˇs´ı neˇ
´ vybrat? A kterou nam ´ vybere Perceptronov´y Kterou mam algoritmus? ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
14 / 32
´ eˇ separovatelne´ problemy ´ Linearn
´ Lze pomoc´ı tohoto algoritmu klasifikovat bezchybneˇ nasleduj´ ıc´ı data?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
15 / 32
´ eˇ separovatelne´ problemy ´ Linearn
´ Lze pomoc´ı tohoto algoritmu klasifikovat bezchybneˇ nasleduj´ ıc´ı data?
Ne! ´ (datum), ˇ pˇr´ımkou ˇr´ıkame ´ ´ eˇ Tˇr´ıdam ktere´ lze oddelit linearn ˚ ´ separovatelna.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
15 / 32
´ eˇ ne–separovatelne´ problemy ´ Linearn
´ ıho klasifikatoru ´ ´ eˇ Lze pomoc´ı linearn´ vyˇreˇsit linearn ´ ne-separovatelne´ problemy?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
16 / 32
´ eˇ ne–separovatelne´ problemy ´ Linearn
´ ıho klasifikatoru ´ ´ eˇ Lze pomoc´ı linearn´ vyˇreˇsit linearn ´ ne-separovatelne´ problemy? Ne. K tomu potˇrebuji pˇridat dalˇs´ı kvalitu.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
16 / 32
´ eˇ ne–separovatelne´ problemy ´ Linearn
´ ıho klasifikatoru ´ ´ eˇ Lze pomoc´ı linearn´ vyˇreˇsit linearn ´ ne-separovatelne´ problemy? Ne. K tomu potˇrebuji pˇridat dalˇs´ı kvalitu. 1
´ Jednou z moˇznost´ı je zkombinovat lin. klasifikatory. (O tom bude ´ ska.) pˇr´ısˇ t´ı pˇrednaˇ
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
16 / 32
´ eˇ ne–separovatelne´ problemy ´ Linearn
´ ıho klasifikatoru ´ ´ eˇ Lze pomoc´ı linearn´ vyˇreˇsit linearn ´ ne-separovatelne´ problemy? Ne. K tomu potˇrebuji pˇridat dalˇs´ı kvalitu. 1
2
´ Jednou z moˇznost´ı je zkombinovat lin. klasifikatory. (O tom bude ´ ska.) pˇr´ısˇ t´ı pˇrednaˇ ´ Rozˇs´ıˇren´ı baze.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
16 / 32
´ Rozˇs´ıˇren´ı baze
´ ım prostoru, zkusme jestli Kdyˇz data nejsou separabiln´ı v originaln´ ´ eˇ separovatelna´ ve v´ıce-dimenzionaln´ ´ ım by nebyla linearn prostoru.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
17 / 32
Transformace
Zase existuje mnoho transformac´ı. ˇ jednoduˇssˇ ´ıch pˇridav ´ a´ ke stavaj´ ´ ıc´ım dimenz´ım take´ Jedna z tech ´ ıch dimenz´ı. souˇciny originaln´ ´ ım stupnem ˇ Je charakterizovana´ parametrem s – maximaln´ souˇcinu.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
18 / 32
Transformace
Zase existuje mnoho transformac´ı. ˇ jednoduˇssˇ ´ıch pˇridav ´ a´ ke stavaj´ ´ ıc´ım dimenz´ım take´ Jedna z tech ´ ıch dimenz´ı. souˇciny originaln´ ´ ım stupnem ˇ Je charakterizovana´ parametrem s – maximaln´ souˇcinu. ´ 5D prostor dimenz´ı Pro s = 2 z puvodn´ ıch dimenz´ı (x1 , x2 ) z´ıskam ˚ (x1 , x2 , χ1 , χ2 , χ3 ), kde I I I
χ1 = x12 χ2 = x1 ∗ x2 χ3 = x22
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
18 / 32
´ ıho klasifikatoru ´ Uˇcen´ı nelinearn´
´ tedˇ nove´ dimenze, jak nauˇc´ım muj ´ Kdyˇz mam ˚ klasifikator?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
19 / 32
´ ıho klasifikatoru ´ Uˇcen´ı nelinearn´
´ tedˇ nove´ dimenze, jak nauˇc´ım muj ´ Kdyˇz mam ˚ klasifikator? ˇ ´ ted mam ´ v´ıce-dimenzionaln´ ´ ı prostor a (tˇreba) D´ıky rozˇs´ırˇen´ı baze ´ zi tˇr´ıdy linearn ´ eˇ separovat. tedˇ dokaˇ ´ ˇ Tj pouˇziji napˇr´ıklad Upln eˇ stejneˇ jako v pˇredchoz´ım pˇr´ıpade. perceptronov´y algoritmus.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
19 / 32
´ ıho klasifikatoru ´ Uˇcen´ı nelinearn´
´ tedˇ nove´ dimenze, jak nauˇc´ım muj ´ Kdyˇz mam ˚ klasifikator? ˇ ´ ted mam ´ v´ıce-dimenzionaln´ ´ ı prostor a (tˇreba) D´ıky rozˇs´ırˇen´ı baze ´ zi tˇr´ıdy linearn ´ eˇ separovat. tedˇ dokaˇ ´ ˇ Tj pouˇziji napˇr´ıklad Upln eˇ stejneˇ jako v pˇredchoz´ım pˇr´ıpade. perceptronov´y algoritmus. ´ ı separaci, mohu zkusit zv´ysˇ it Pokud se mi nepodaˇr´ı z´ıskat linearn´ ´ ı stupenˇ souˇcinu a zkusit separaci znovu. maximaln´
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
19 / 32
Rozhodovac´ı hranice
ˇ do Jak pak bude vypadat projekce rozhodovac´ı hranice zpet ´ ıch dimenz´ı? originaln´
´ podaˇrilo dosahnout ´ T´ım se nam toho, zˇ e se rozhodovac´ı hranice ”ohnula”. ´ A pokud budu zvyˇsovat parametr s, bude hranice stale ˇ s´ı”. ”poddajnejˇ
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
20 / 32
Rozhodovac´ı hranice (2)
´ ı stupenˇ souˇcinu (parametr s) do Muˇ ˚ zu zvyˇsovat maximaln´ ˇ nekoneˇcna? Nebo nekde naraz´ım?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
21 / 32
Rozhodovac´ı hranice (2)
´ ı stupenˇ souˇcinu (parametr s) do Muˇ ˚ zu zvyˇsovat maximaln´ ˇ nekoneˇcna? Nebo nekde naraz´ım? ´ ım stupnem ˇ s vyvstavaj´ ´ ı dva problemy: ´ S vyˇssˇ ´ım maximaln´ 1
2
´ v´ıce vah, ktere´ mus´ım nastavovat a perceptronov´y Jednak mam ´ ´ se (nebo jak´ykoliv jin´y) algoritmus to nemus´ı zvladnout – cˇ ili vahy ˇ nastav´ı sˇ patne. ˇ ´ Zvyˇsuji pravdepodobnost, zˇ e se klasifikator pˇreuˇc´ı. Tj. nauˇc´ı se ´ ´ ze vlastnosti sˇ um a chyby v trenovac´ ıch datech a nedokaˇ ´ trenovac´ ıch dat zobecnit. (Podobneˇ jako napˇr´ıklad 1-NN ´ klasifikator.)
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
21 / 32
ˇ Klasifikace do nekolika tˇr´ıd ´ v´ıce neˇz dveˇ tˇr´ıdy? Mohu pouˇz´ıt (ne-)linearn´ ´ ı Co kdyˇz mam separaci? Pˇr´ıpadneˇ jak?
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
22 / 32
ˇ Klasifikace do nekolika tˇr´ıd ´ v´ıce neˇz dveˇ tˇr´ıdy? Mohu pouˇz´ıt (ne-)linearn´ ´ ı Co kdyˇz mam separaci? Pˇr´ıpadneˇ jak? ˇ Budu rozhodovat o kaˇzde´ tˇr´ıdeˇ samostatne. ˇ ´ s N tˇr´ıdami budu m´ıt N klasifikator ´ u. Cili pro problem ˚ Kaˇzd´y bude ˇr´ıkat – ”Instance patˇr´ı do me´ tˇr´ıdy” / ”Instance nepatˇr´ı do me´ tˇr´ıdy”.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
22 / 32
ˇ Klasifikace do nekolika tˇr´ıd ´ v´ıce neˇz dveˇ tˇr´ıdy? Mohu pouˇz´ıt (ne-)linearn´ ´ ı Co kdyˇz mam separaci? Pˇr´ıpadneˇ jak? ˇ Budu rozhodovat o kaˇzde´ tˇr´ıdeˇ samostatne. ˇ ´ s N tˇr´ıdami budu m´ıt N klasifikator ´ u. Cili pro problem ˚ Kaˇzd´y bude ˇr´ıkat – ”Instance patˇr´ı do me´ tˇr´ıdy” / ”Instance nepatˇr´ı do me´ tˇr´ıdy”. ´ ı o neznam ´ e´ instanci x se zeptam ´ vˇsech N Pˇri rozhodovan´ ´ u˚ na jejich rozhodnut´ı. klasifikator 1 2
3
´ eˇ do jedne´ tˇr´ıdy. x patˇr´ı prav x patˇr´ı do v´ıce tˇr´ıd – pak se mus´ım rozhodnout napˇr´ıklad podle ˇ s´ı, t´ım je x dale ´ od rozhodovac´ı hranice). hodnoty xw (ˇc´ım je vetˇ ´ e´ tˇr´ıdy. Hledam ´ tedy tr´ıdu, analogoicky, pokud x nepatˇr´ı do zˇ adn ´ eˇ :). kam x nepatˇr´ı nejmen
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
22 / 32
´ ´ ıch klasifikator ´ u˚ Problemy linearn´
Linearita ˇ e, ´ muˇ Pokud se dostateˇcneˇ pohnu i jen v jedne´ promenn ˚ zu z´ıskat ´ obracen´ y v´ysledek. ´ Hodnota xw roste se vzdalenost´ ı od rozhodovac´ı hranice a nema´ ´ zˇ adnou interpretaci. ´ ı klasifikatory ´ ´ sej´ı chybej´ ˇ ıc´ı hodnoty. Linearn´ sˇ patneˇ snaˇ ´ ım rozˇs´ıˇren´ı baze, ´ Pokud provad´ muˇ ˚ ze trvat uˇcen´ı velmi dlouho.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
23 / 32
Linear Discriminant Analysis
´ ´ ı separace. LDA je statistick´y pˇr´ıstup k problemu linearn´ Pamatujete si PCA? (Principal Component Analisis – mluvili jsme ˇ u SOM) o nem
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
24 / 32
Linear Discriminant Analysis
´ ´ ı separace. LDA je statistick´y pˇr´ıstup k problemu linearn´ Pamatujete si PCA? (Principal Component Analisis – mluvili jsme ˇ u SOM) o nem LDA redukuje puvodn´ ı prostor na pˇr´ımku (1 dimenzi) a to tak, co ˚ ˇ vzory ruzn´ nejv´ıce oddelil ˚ ych tˇr´ıd. ´ smyslu je to opak rozˇs´ırˇen´ı baze. ´ V jistem
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
24 / 32
Linear Discriminant Analysis (2)
´ jako xw, kde w jsou Obraz vzoru v nove´ souˇradnici pak z´ıskam ´ vahy. ´ to same´ jako u linearn´ ´ ıho klasifikatoru, ´ V principu poˇc´ıtam ale ˇ ´ interpretace a postup jsou upln ´ e jine.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
25 / 32
Linear Discriminant Analysis (3)
´ ı LDA se snaˇz´ım maximalizovat ”separaci” mezi tˇr´ıdami. Pˇri poˇc´ıtan´ Nejprve pro kaˇzdou tˇr´ıdu mus´ım spoˇc´ıtat rozptyl v obraze (scatter). yi = xi w µs1 =
1 ks1 k
X
xi
µ˜s1 =
∀xi ∈s1
1 X 1 X yi = xi w ks1 k ks1 k ∀xi ∈s1
s˜1 2 =
X
∀xi ∈s1
yi − µ˜s1
∀x1 ∈s1
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
26 / 32
Linear Discriminant Analysis (4)
A nyn´ı muˇ ˚ zu spoˇc´ıtat m´ıru ”separace” pro projekci danou vahami w. J(w) =
kµ˜s1 − µ˜s2 k2 s˜1 2 + s˜2 2
´ Hledame tedy projekci, ktera´ co nejv´ıc seskup´ı vzory stejne´ tˇr´ıdy a ´ ˇ ı vzory ruzn´ co nejv´ıc zarove nˇ oddel´ ˚ ych tˇr´ıd.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
27 / 32
LDA pro v´ıce tˇr´ıd
´ LDA lze zobecnit tak, aby dokazalo klasifikovat do v´ıce tˇr´ıd. ´ r´ı pouze jedna nova´ dimenze, ale ”poˇcet tˇr´ıd”-1 Pak se nevytvaˇ nov´ych dimenz´ı a m´ırneˇ se uprav´ı vzoreˇcky :).
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
28 / 32
´ Problemy LDA
ˇ e´ mouchy: Stejneˇ jako vˇsechno, ma´ i LDA nejak I
I
I
´ em ´ zaˇrazen´ı Poˇcet dimenz´ı vytvoˇren´y LDA nemus´ı staˇcit ke spravn do tˇr´ıdy. ´ a´ normaln´ ´ ı rozloˇzen´ı dat ve tˇr´ıdach. ´ ´ a, ´ LDA pˇredpoklad A selhav pokud tomu tak nen´ı. (Napˇr´ıklad tˇr´ıdy maj´ı komplexn´ı tvary). Roz´ıly mezi tˇr´ıdami jsou sp´ısˇ e v rozptylu hodnot neˇz v rozd´ılu stˇredn´ıch hodnot.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
29 / 32
Logisticka´ regrese ˇ abych dokazal ´ ´ Co kdybych chtel, vzdalenosti od rozhodovac´ı ˇ hranice nejak interpretovat. ´ eˇ jeˇsteˇ tak, zˇ e je to pravdepodobnost ˇ Idealn pˇr´ısluˇsnosti k dane´ ˇ tˇr´ıde.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
30 / 32
Logisticka´ regrese ˇ abych dokazal ´ ´ Co kdybych chtel, vzdalenosti od rozhodovac´ı ˇ hranice nejak interpretovat. ´ eˇ jeˇsteˇ tak, zˇ e je to pravdepodobnost ˇ Idealn pˇr´ısluˇsnosti k dane´ ˇ tˇr´ıde. Existuje logisticka´ funkce, ktera´ je definovana´ takto f (z) = 1+e1 −z Jej´ı hodnoty jsou omezene´ na interval 0 . . . 1. A nav´ıc kolem z = 0 ˇ ˇ s´ı. (rozhodovac´ı hranice) je jej´ı zmena nejvetˇ
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
30 / 32
Logisticka´ regrese (2)
´ pojem sance = Zkus´ıme zavest
ˇ CVUT (FEL)
p 1−p
Self Organizing Map
13.12.2011
31 / 32
Logisticka´ regrese (2)
´ pojem sance = Zkus´ıme zavest
p 1−p
Abychom ji dostali do rozmez´ı 0 . . . 1 zkusme ji zlogaritmovat. p ´ T´ım z´ıskame funkci logit(p) = log(sance(p)) = log( 1−p )
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
31 / 32
Logisticka´ regrese (2)
´ pojem sance = Zkus´ıme zavest
p 1−p
Abychom ji dostali do rozmez´ı 0 . . . 1 zkusme ji zlogaritmovat. p ´ T´ım z´ıskame funkci logit(p) = log(sance(p)) = log( 1−p ) ´ Zkusme pˇredpokladat, zˇ e logit(p) = β0 + β1 x1 + β2 x2 + . . . + βk xk Kde β1 , . . . , βk jsou regresn´ı koeficienty a β0 je posun.
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
31 / 32
Logisticka´ regrese (2)
´ pojem sance = Zkus´ıme zavest
p 1−p
Abychom ji dostali do rozmez´ı 0 . . . 1 zkusme ji zlogaritmovat. p ´ T´ım z´ıskame funkci logit(p) = log(sance(p)) = log( 1−p ) ´ Zkusme pˇredpokladat, zˇ e logit(p) = β0 + β1 x1 + β2 x2 + . . . + βk xk Kde β1 , . . . , βk jsou regresn´ı koeficienty a β0 je posun. ˇ dopoˇc´ıtat pravdepodobnost ˇ A tedˇ zkusme opet vzoru x. p(x) =
1 1+e−β0 +β1 x1 +β2 x2 +...+βk xk
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
31 / 32
Zdroje
LDA pˇrevzata z research.cs.tamu.edu/prism/lectures/ pr/pr_l10.pdf http://www.omidrouhani.com/research/ logisticregression/html/logisticregression.htm
ˇ CVUT (FEL)
Self Organizing Map
13.12.2011
32 / 32
