Základy vytěžování dat

Základy vytěžování dat předmět A7Bb36vyd – Vytěžování dat Filip Železný, Miroslav Čepek, Radomír Černoch, Jan Hrdlička katedra kybernetiky a katedra počítačů ČVUT v Praze, FEL

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

Klasifikace a predikce

Odkaz na výukové materiály: https://cw.felk.cvut.cz/doku.php/courses/a7b36vyd/moduly/start (oddíl 5)


Vytěžování dat, přednáška 7: Klasifikace Filip Železný


Fakulta elektrotechnická, ČVUT

1 / 24

Klasifikace

Učení s učitelem I

Pravděpodobnostní rozdělení PXY na X × Y I

I

Předpokládáme, že Y je konečná množina

Data: D je multimnožina D = {(x1 , y1 ), (x2 , y2 ), . . . (xm , y2 )} (m ∈ N) prvky vybrány náhodně a navzájem nezávisle z PXY

I

Vzor se bude používat na tomtéž X, Y a PXY

Obvykle hledáme vzory aproximující (pro zadané x ∈ X) I

podmíněnou pravděpodobnost PY|X (y|x) = PXY (x, y)/PX (x)

I

nebo nejpravděpodobnější hodnotu arg maxy∈Y PY|X (y|x)

I

tyto vzory nazýváme klasifikátory 2 / 24

Klasifikace

Klasifikace s jedním příznakem

X Vysoké příjmy ano ano ne ano ne ne ne ano ano ano ne

Y Splácí úvěr ano ne ano ano ne ne ano ano ano ano ne 3 / 24

Klasifikace

Kontingenční tabulka Y (splácí ano X (vysoké ano 5 příjmy) ne 2 ∑ 7

úvěr) ne 1 3 4

Nový žadatel o úvěr má vysoké příjmy. I

Bude splácet úvěr?

I

S jakou pravděpodobností?

∑ 6 5 11

Klasifikace dle aposteriorní pravděpodobnosti

I

Klient má vysoké příjmy. Jak bude splácet úvěr?

I

Tedy z x = vysoké urči nejpravděpodobnější hodnotu y (třídu).

I

Hledáme y0 vyhovující y0 = arg max PY|X (y|vysoké) y

I

Řešení je y0 = splácí PY|X (y0 |vysoké) ≈ 2/3

I

S pravděpodobností 1 − PY|X (y0 |vysoké) klasifikujeme chybně.

I

Klasifikací y0 = splácí tedy minimalizujeme chybu.

4 / 24

Klasifikace

Ztrátová funkce I I I

I

Každá chyba klasifikace je jinak drahá. Např. příliš optimististické hodnocení klienta stojí víc než příliš skeptické. Klasifikace dle aposteriorní pravděpodobnosti toto nerespektuje. Pro zohlednění odlišných ztrát pro různé chyby potřebujeme pojem ztrátové funkce. Ztrátová funkce L(y, y0 ) zachycuje ztrátu pro každou kombinaci I I

I

y - skutečná třída y0 - třída, do které klasifikujeme

Pro náš příklad L(y, y0 ) např.: y↓ y’→ splácí problémy nesplácí 5 / 24

Klasifikace

splácí 0 5 10

problémy 1 0 5

nesplácí 2 1 0

Klasifikátor a Riziko I

Hledáme klasifikátor, tj. funkci f : X → Y minimalizující střední hodnotu ztráty: ∑ R(f) = L(y, f(x))PXY (x, y) x,y

I

Střední hodnotu ztráty pro f se nazývá riziko klasifikátoru f.

I

Řešením f∗ = arg minf R(f) je funkce f∗ (x) = arg min r(x, y0 ) 0 y

kde

r(x, y0 ) =

∑

L(y, y0 )PY|X (y|x)

y

je riziko klasifikace y0 při příznaku x 6 / 24

Klasifikace

Klasifikace jako minimalizace rizika

I

Jak klasifikovat vysokopříjmového klienta?

PY|X x ↓y → vysoké střední nízké

splácí 2/3 2/6 0/2

problémy 1/3 2/6 1/2

nesplácí 0/3 2/6 1/2

L y ↓ y0 → splácí problémy nesplácí

splácí 0 5 10

problémy 1 0 5

7 / 24

Klasifikace

nesplácí 2 1 0

I

Klasifikace y0 = splácí skut. třída splácí problémy nesplácí

I

ztráta 0 5 10

s pravděp. 2/3 1/3 0

Riziko při této klasifikaci: 0 · 2/3 + 5 · 1/3 + 10 · 0 = 5/3


I



splácí 2/3 2/6 0/2



y ↓ y0 → splácí problémy nesplácí

splácí 0 5 10

problémy 1 0 5

nesplácí 2 1 0

8 / 24

Klasifikace

L

I

Klasifikace y0 = problémy skut. třída splácí problémy nesplácí

I

ztráta 1 0 5




I



splácí 2/3 2/6 0/2



L y ↓ y0 → splácí problémy nesplácí

splácí 0 5 10

problémy 2 1 0

9 / 24

Klasifikace

nesplácí 2 1 0

I

Klasifikace y0 = nesplácí skut. třída splácí problémy nesplácí

I

ztráta 2 1 0



Klasifikace jako minimalizace rizika I

Klasifikujeme do y0 = arg min r(vysoké, y) = problémy y

I

Pozor, jiný výsledek než dle aposteriorní pravděpodobnosti y0 = arg max PY|X (y|vysoké) = splácí y

I

Při jaké ztrátové funkci L(y, y0 ) by výsledky vyšly stejně? y↓ y’→ splácí problémy nesplácí

I

splácí 0 1 1

problémy 1 0 1

nesplácí 1 1 0

Tzv. L01 ztrátová funkce. Je-li použita, je r(x, y0 ) pravděpodobnost, že klasifikace instance s příznakem x do třídy y0 je chybná. 10 / 24

Klasifikace

Klasifikace s několika příznaky I

Zatím jsme klasifikovali pouze dle jediného příznaku (x - výše příjmů)

I

O klientech toho víme obvykle více. Příjmy (p) vysoké nízké střední nízké ...

I I

Rok narození (n) 1969 1974 1940 1985 ...

x ≡ (p, n) Třírozměrná kontingenční tabulka I

p vs. n vs. y 11 / 24

Klasifikace

Úvěr (y) splácí nesplácí problémy problémy ...

Klasifikace s několika příznaky I

Na principech klasifikace se nic nemění. Např. jak klasifikovat nízkopříjmového klienta narozeného v r. 1985? I

Maximalizací aposteriorní pravděpodobnosti f(x) = y0 = arg max PY|P,N (y|nízké, 1974) y

I

Minimalizací rizika f(x) = y0 = arg min r((nízké, 1974), y) y

I

Z kontingenční tabulky PY|P,N (y0 |nízké, 1974) ≈

12 / 24

Klasifikace

počet klientů s y0 = y, p = nízké, n = 1974 počet klientů s p = nízké, n = 1974

Prokletí rozměrnosti

PY|P,N (y0 |nízké, 1974) ≈

počet klientů s y0 = y, p = nízké, n = 1974 počet klientů s p = nízké, n = 1974

I

Čím více příznaků, tím větší nebezpečí výsledku “0/0”!

I

Kolik dat potřebujeme, aby odhady dobře konvergovaly k pravděpodobnostem?

I

Kontingenční tabulka musí být ‘dostatečně zaplněna’.

I

V předchozím příkladě (jediný příznak) p↓ y→ vysoké střední nízké ∑

splácí 2 2 0 4

problémy 1 2 1 4

nesplácí 0 2 1 3

∑ 3 6 2 11

v průměru 11/9 případů na kolonku tabulky. 13 / 24

Klasifikace

Prokletí rozměrnosti I

Předpokládejme, že 11/9 je dostatečný poměr. Kolik případů (m) potřebujeme pro jeho zachování se dvěma příznaky p a n?

I

Přepodkládejme 100 možných roků narození. Kontingenční tabulka má 100 · 3 · 3 = 900 kolonek. 11 m = 900 9 tedy nyní již potřebujeme 11 · 900/9 = 1100 dat.

I I

Po přidání dalšího příznaku, např. roku ukončení studia už potřebujeme 11 · 90000/9 = 110000 dat! Obecně pro odhady z kontingenční tabulky (tzv. neparametrické odhady) roste potřebný počet dat exponenciálně s počtem příznaků. I

“Prokletí rozměrnosti”

14 / 24

Klasifikace

Podmíněně nezávislé příznaky

I

Situace se zjednoduší, jsou-li výše příjmů a rok narození podmíněně nezávislé, tj. platí PP,N|Y (p, n|y) = PP|Y (p|y) · PN|Y (n|y) pro každou z hodnot y ∈ {splácí, problémy, nesplácí)

I

Využijeme tzv. Bayesova pravidla PY|P,N (y|p, n) =

15 / 24

Klasifikace

PP,N|Y (p, n|y)PY (y) PP,N (p, n)

Podmíněně nezávislé příznaky I

Z Bayesova pravidla platí pro klasifikaci maximalizací aposteriorní pravděpodobnosti arg max PY|P,N (y|p, n) = arg max PP,N|Y (p, n|y)PY (y) y

I

y

Podobně pro klasifikaci minimalizací rizika 0

arg min

∑

y

0

= arg min y

L(y, y0 )PY|P,N (y|p, n)

y

∑

L(y, y0 )PP,N|Y (p, n|y)PY (y)

y

I

Proč ‘zmizelo’ PP,N (p, n)? Nezávisí na y!

I

K oběma typům klasifikace tedy potřebujeme odhady dvou rozdělení: PP,N|Y a PY . 16 / 24

Klasifikace

Podmíněně nezávislé příznaky I

K oběma typům klasifikace tedy potřebujeme odhady dvou rozdělení: PP,N|Y a PY .

I

PY odhadneme z jednorozměrné kontingenční tabulky

I

Z podmíněné nezávislosti plyne PP,N|Y = PP|Y · PN|Y

I

PP|Y odhadneme z dvourozměrné tabulky 3 × 3 PN|Y odhadneme z dvourozměrné tabulky 100 × 3.

I

I

I

Obecně: při podmíněně nezávislých příznacích neroste potřebný počet dat exponenciálně s počtem příznaků. I

I

Nejnáročnější na počet dat, pro zachování poměru 11/9 vyžaduje cca 367 (<< 1100).

Je určen příznakem s největším oborem hodnot.

Příznaky obvykle nejsou podmíněně nezávislé! I

Je-li přesto použita tato metoda, mluvíme o naivní Bayesovské klasifikaci. 17 / 24

Klasifikace

Klasifikace dle nejbližšího souseda I I I

Metoda, která nevyžaduje odhad pravděpodobností. Předpoklad: umíme spočítat podobnost dvou datových instancí (jako např. u shlukování) Zde p, n ∈ N, u ∈ {splácí, problémy, nesplácí}

18 / 24

Klasifikace

Klasifikace dle nejbližšího souseda I I I

Zde podobnost např. (p1 − p2 )2 + (n1 − n2 )2 Zařazujeme do třídy nejpodobnější instance. Náchylné k šumu v datech.

19 / 24

Klasifikace

Klasifikace dle k nejbližších sousedů I I I

Zde podobnost např. (p1 − p2 )2 + (n1 − n2 )2 Zařazujeme do třídy převládající mezi k nejpodobnějšími instancemi. S rostoucím k klesá náchylnost k šumu. Nevýhody?

20 / 24

Klasifikace

Trénovací a skutečná chyba klasifikátoru

Trénovací chyba Podíl instancí v datech chybně klasifikovaných klasifikátorem f sestrojeným z těchto dat (tzv. trénovacích dat).

Skutečná chyba Pravděpodobnost chybné klasifikace f při náhodném výběru (x ∈ X, y ∈ Y) dle PXY . Při použití ztrátové funkce L01 rovna riziku R(f).

21 / 24

Klasifikace

Jaké k je nejlepší? Experiment: generovaná data

k=1 Nulová trénovací chyba, přesto klasifikace odlišná od optimální→

22 / 24

[Hastie et al.: Elements of Statistical Learning]

Dle maximální aposteriorní pravděpodobnosti (optimální)

Klasifikace

k = 15 Malá náchylnost k šumu, přesto klasifikace odlišná od ←optimální

Trénovací vs. skutečná chyba I I

Typický průběh chyb pro k = m (počet dat), m − 1, . . . 1 Trénovací chyba obecně není dobrým odhadem skutečné chyby!

23 / 24

Klasifikace

Klasifikace dle etalonů I I

Metoda nevyžadující přístup ke všem instancím při klasifikaci. Každá třída má etalon, tj. instanci s minimální průměrnou vzdáleností ke všem instancím třídy. I

I

(vybírána buďto z trénovacích dat, nebo z celého oboru hodnot (p, n))

Etalony jsou jednoduchým nepravděpodobnostním modelem dat.

24 / 24

Klasifikace

Vytěžování dat, přednáška 7: Rozhodovací stromy Filip Železný



1 / 26

Rozhodovací stromy

Reálné příznaky

I

Lineární/polynomiální modely: příznaky jsou reálná čísla

2 / 26

Rozhodovací stromy

Nominální příznaky teplota zvýšená normální horečka ... I

I

diagnóza nachlazení hypochondr chřipka ...

Lze převést na příznaky s oborem {0, 1} : reprezentace “1 z n”

normální 0 ... I

bolest svalů ne ne ano ...

teplota zvýšená 1 ...

horečka 0 ...

bolest svalů 0 ...

nachlaz. 1 ...

diagnóza chřipka hypoch. 0 0 ... ...

Umožňuje využití lineárních resp. polynomiálních klasifikátorů, ale nešikovné. Klasifikační modely přímo pro nominální příznaky? 3 / 26

Rozhodovací stromy

Rozhodovací strom

I

Klasifikační model

I

Uzly (mimo listy): testy příznaků, hrany: možné hodnoty

I

Klasifikace: cesta z kořene do listu podle hodnot příznaků

I

Jak strom zkonstruovat? 4 / 26

Rozhodovací stromy

Rekurzivní rozdělování: příklad

I I

2 binární příznaky x1 , x2 ∈ {+, −} Instance spadají do 3 tříd: I I I

10 červených instancí 8 zelených instancí 5 modrých instancí

I

Všech 10 s x1 = + má y = •

I

Všech 10 s x1 = + má y = •

I

Zbývá 13 instancí s x1 = −

I

Všech 8 s x2 = + má y = •

I

Všech 5 s x2 = − má y = •

5 / 26

Rozhodovací stromy

Algoritmus pro tvorbu rozhodovacího stromu TDIT(D,I) /* Top Down Induction of Decision Trees */ Input: D trénovací data, I indexy příznaků if všechny instance v D mají stejnou třídu y then return uzel označený y else if I = ∅ then return uzel označený většinovou třídou v D else vyber i ∈ I a vytvoř uzel označený xi for ∀vj ∈ Range(xi ) /* konečný obor hodnot xi */ do Ej = všechny instance z D u nichž xi = vj Vyveď z uzlu xi hranu označenou vj if Ej = ∅ then připoj list na hranu vj označený většinovou třídou v D else připoj výsledek TDIT(Ej , I \ {i}) na hranu vi end end end end return vytvořený strom s kořenem xi 6 / 26

Rozhodovací stromy

TDIT: rekurzivní volání

7 / 26

Rozhodovací stromy

Výběr příznaku

I

Jak implementovat příkaz “vyber i ∈ I” v algoritmu TDIT?

I

Příklad

I

Třída: barva

I

Příznaky: tvar, velikost, průhlednost

I

Začínáme konstruovat strom.

I

Jaký příznak zvolit první?

I

Měl by co ‘nejčistěji’ dělit data podle tříd

8 / 26

Rozhodovací stromy

Výběr příznaku

9 / 26

Rozhodovací stromy

Entropie

I

Entropie množiny instancí D s t třídami H(D) =

t ∑

−pi log2 pi

i=1 I

p1 , p2 . . . pt . . . poměrné velikosti tříd pi =

počet instancí třídy i v D počet všech instancí v D

I

Minimální H(D) = 0, pokud jsou všechny příklady v jedné třídě.

I

Maximální H(D) = log2 t, pokud p1 = p2 = . . . = pt .

10 / 26

Rozhodovací stromy

Entropie Pro dvě třídy

11 / 26

Rozhodovací stromy

Entropie

1 pzelená = pčervená = 2 ( ) ( ) 1 1 1 1 H(D) = − log2 − log2 =1 2 2 2 2

12 / 26

Rozhodovací stromy

Entropie po rozdělení množiny

Evelké = velké instance

Emalé = malé instance

pzelená = pčervená = 0.5

pzelená = pčervená = 0.5

H(Evelké ) = 1

H(Emalé ) = 1

Vážený průměr entropií ∑ j∈{velké,malé} 13 / 26

|Ej | 2 2 · H(Ej ) = · 1 + · 1 = 1 |D| 4 4

Rozhodovací stromy


Eprůhledné = průhledné instance

Eneprůhledné = neprůhledné instance

pzelená = 1

pzelená = 1/3

pčervená = 0

pčervená = 2/3

H(Eprůhledné ) = 0

H(Eneprůhledné ) = 0.92

Vážený průměr entropií ∑ 14 / 26

|Ej |

· H(Ej ) =

Rozhodovací stromy

1

·0+

3

· 0.92 = 0.69


Ehranaté = hranaté instance

Ekulaté = kulaté instance

pzelená = 1

pzelená = 0

pčervená = 0

pčervená = 1

H(Ehranaté ) = 0

H(Ekulaté ) = 0

Vážený průměr entropií ∑ j∈{hranaté,kulaté} 15 / 26

|Ej | 2 2 · H(Ej ) = · 0 + · 0 = 0 |D| 4 4

Rozhodovací stromy

Pokles entropie

∆H(D, xi ) = H(D) −

∑ vj ∈Range(xi )

I I

Rozdíl entropie původní množiny D a váženého průměru entropií množiny rozdělené hodnotami příznaku xi Jak implementovat příkaz “vyber i ∈ I” v algoritmu TDIT? I

I

|Ej | H(Ej ) D

Vybereme i, které maximalizuje ∆H(D, xi )

Pozn: pro výběr i není sčítanec H(D) důležitý (nezávisí na i).

16 / 26

Rozhodovací stromy

Pokles entropie

I

Jak implementovat příkaz “vyber i ∈ I” v algoritmu TDIT? I

Vybereme i, které maximalizuje ∆H(D, xi )

17 / 26

Rozhodovací stromy

Složitost rozhodovacího stromu I I

I

Algoritmus TDIT se snaží minimalizovat trénovací chybu za cenu velké složitosti (košatosti) stromu Stále platí kompromis mezi složitostí modelu a trénovací chybou!

Vymyslete úpravu algoritmu TDIT omezující složitost stromu I

Nevětvíme, pokud maxi ∆H(D, xi ) < θ, θ > 0 . . . parametr 18 / 26

Rozhodovací stromy

Ordinální příznaky

Ordinální veličina I

Veličina, jejíž obor hodnot je uspořádán

I

Např. přirozená (nebo reálná) čísla 1 < 2 < 3 < ...

I

ale i např. nízký < střední < vysoký

19 / 26

Rozhodovací stromy

Ordinální příznaky I

Pro ordinální příznaky obvykle test x>h v uzlech, kde h je zvolená hraniční hodnota

20 / 26

Rozhodovací stromy

Převod na nominální příznaky I

Před tvorbou stromu můžeme každý ordinální příznak, např. teplota převést na množinu nominálních příznaků teplota > h1 , teplota > h2 , . . . , teplota > hn z nichž každý má binární obor hodnot.

I

Co jsou h1 , h2 , . . . hn ?

I

V nejjednodušším případě celý obor hodnot původního příznaku, je-li konečný (a malý).

I

Obvykle ale jen některé z oboru hodnot. Které?

21 / 26

Rozhodovací stromy

Diskretizace I

U některých veličin se hraniční hodnoty ‘nabízejí’. xi < 36.5 36.5 ≤ xi < 37 37 ≤ xi < 38 38 ≤ xi < 42 42 ≤ xi

podchlazení normální teplota zvýšená teplota horečka smrt

I

Zde tedy uvažujeme hraniční hodnoty {36.5, 37, 38, 42}

I

Pozn.: převedení reálné veličiny (teplota) na veličinu s konečným oborem hodnot = diskretizace.

I

V obecném případě vhodné hraniční hodnoty předem neznáme.

22 / 26

Rozhodovací stromy

Diskretizace: 3 obecné způsoby I

Intervaly stejné délky

I

Intervaly stejné pravděpodobnosti

I

Intervaly obsahující instance stejné třídy (nejužívanější pro stromy)

23 / 26

Rozhodovací stromy

Separace: srovnání Separace v prostoru dvou reálných příznaků

Lineární klasifikátor (nelze rozdělit) Kvadratický klasifikátor Rozhodovací strom

24 / 26

Rozhodovací stromy

Separace rozhodovacím stromem Separace v prostoru dvou reálných příznaků

25 / 26

Rozhodovací stromy

Minimalizace nákladů na rozhodování

26 / 26

Rozhodovací stromy

I

Rozhodovací strom netestuje vždy všechny příznaky!

I

TDIT lze přizpůsobit tak, aby levné testy byly blíže ke kořeni

Vytěžování dat, přednáška 9: Lineární klasifikátor, rozšíření báze, LDA, logistická regrese Miroslav Čepek



1 / 32

Lineární klasifikátor

Klasifikátory

I

Jaké znáte klasifikační algoritmy? I I I

I

Naive Bayes Rozhodovací strom KNN

Jak fungují? I

I I

Naive Bayes počítá pravděpodobnost přiřazení do třídy za podmínky dané pozorováním. Rozhodovací strom generuje posloupnost rozhodnutí. KNN hledá nejbližsí instance z trénovací množiny.

2 / 32


Rozhodovací hranice I

Další možný pohled je z hlediska rozhodovací hranice.

I

Rozhodovací hranice je místo, kde instance přestávají patřit do třídy A a začínají patřit do třídy B.

Převzadto z http: //openclassroom.stanford.edu/MainFolder/DocumentPage. php?course=MachineLearning&doc=exercises/ex8/ex8.html 3 / 32


Rozhodovací hranice (2)

I

Co když mám následující data:

I

Jak bude vypadat nejjednodušší rozhodovací hranice, která data oklasifikuje bez chyby?

I

Stačí přece přímka!

4 / 32


Lineární klasifikátor I

Takovou přímku umíme celkem jednoduše najít a vyrobit :).

I

Jak vypadá rovnice přímky? y=

∑

wj xj = wx

j I

Jak zjistíme, do které třídy patří vzor x?

I

Prostým dosazením! Pokud y > 0 vzor patří do jedné třídy, y < 0 vzor patří do druhé třídy.

I

y = 0 je rozhodovací hranice, kde se nelze rozhodnout. Naštěstí se toto nestává často.

I

Porovnání < 0 nebo > 0 můžeme nahradit například funkcí signum(y) která vrací +1 pro kladná čísla a −1 pro záporná. 5 / 32


Lineární klasifikátor (2)

I

Vidíte v rovnici nějaký problém?

I

Zkusme dosadit do rovnice x1 = x2 = 0. Co vyjde?

I

y = 0 bez ohledu na nastavení vah w1 , w2 .

I

Rozhodovací hranice libovolného klasifikátoru tedy musí procházet nulou resp. vektorem (0, 0, . . . , 0).

I I

To je docela nepříjemné omezení – rozhodovací hranice se vlastně pouze otáčí kolem nuly. Co s tím? ∑ Můžeme přidat změnit rovnici přímky na j wj xj + Θ = 0.

I

Θ je aditivní konstanta a označuje se jako práh.

6 / 32


Lineární klasifikátor (3)

I

Rovnice pro lineární klasifikátor se tedy mírně změní: ∑ y= wj xj + Θ = wx + Θ j

I

Ale jinak vše zůstane stejné.

I

Pokud tedy vyjde, že y > 0 vzor patří do jedné třídy, y < 0 vzor patří do druhé třídy.

7 / 32


Práh I

Teď zbývá pouze najít vektor koeficientů (vah) (w1 , w2 , . . . , wn ) a prahu Θ.

I

Nejprve se zamysleme zda práh Θ představuje nějakou anomálii, která potřebuje speciální zacházení.

I

Tak napůl :). Nepotřebuje, pokud trochu upravíme vstupní data.

I

Co kdyby všechny vzory měli jeden atribut (vstupní proměnnou, řekněme x0 ) se stejnou hodnotou?

I

Když pak budu počítat w0 x0 , vyjde mi vždy stejná hodnota... to je přece náš práh!

I

Takže přidám ke každému vzoru ještě jednu dimenzi, která bude mít konstantní hodnotu – pro jednoduchost 1 (ale můžete mu přiřadit libovolnou nenulovou hodnotu).

I

Pak už se o práh nemusím speciálně starat. 8 / 32


Gradientní sestup – krok stranou

I

Gradientní sestup je iterativní optimalizační metoda.

I

Jde o to, že máme funkci f(x) a hledáme její minimum.

I

A jak minimum najít? Budu hledat takové x, kde má funkce f(x) nejnižší hodnotu.

I

Mám nějaké x0 a znám hodnotu f(x0 ). A hledám v okolí x0 , nejaké x1 , kde bude hodnota f(x1 ) nižší. A to budu opakovat stále dokola, až to dál nepůjde.

I

”Na horách se chci dostat do údolí. Podívám se, kterým směrem se kopec nejvíc snižuje a udělám krok tím směrem. A zase se podívám, kam je to nejvíc z kopce a udělám krok. A tak dále, až jednou zjistím, že to dál nejde, čili jsem v údolí.”

9 / 32


Gradientní sestup – krok stranou (2)

I

V matematice existuje možnost, jak zjistit směr největšího vzestupu hodnoty funkce - gradient. To je první parciální derivace podle všech dimenzí. Když půjdu přesně opačně, půjdu ve směru největšího poklesu.

I

Gradient je vektor parciálních derivací podle jednotlivých proměnných: grad(f(x1 , x2 , . . . , xn )) = (

10 / 32


∂f ∂f ∂f , ,..., ) ∂x1 ∂x2 ∂xn

Chybová funkce a gradientní sestup I

Stejně jako u jiných klasifikačních metod, hledáme nastavení klasifikátoru (zde vah) takové, aby klasifikoval správně co nejvíc vzorů.

I

Mějme tedy chybovou funkci J(w, χ), která vrací počet špatně klasifikovaných vzorů x z množiny vzorů χ (například z testovací množiny) při daných vahách w.

I

Ale taková se nám nehodí – neumím spočítat parciální derivace (a tudíž ani gradient). ∑ Zkusme jinou – E(w) = x∈χerr (−w(t)x), kde χerr jsou špatně klasifikované vzory z χ.

I I

To už je spojitá funkce.

I

A chybovou funkci E mohu minimalizovat změnou vah – pomocí gradientního sestupu.

11 / 32


Chybová funkce a gradientní sestup I

Parciální derivace chybové funkce E podle jedné proměnné vypadá takto: ∑ ∂ x1 ∈χerr (−w1 (t)x1 ) ∂E = ∂w1 ∂w1

I

Kde x1 je první souřadnice z x a w1 je první souřadnice z w. ∑ ∑ ∂ x1 ∈χerr (−w1 (t)x1 ) = x1 ∂w1 err x ∈χ 1

I

Z toho plyne závěr, že nejvíce chybu snížím, pokud váhu w1 změním o součet hodnot prvních vstupních proměnných x1 vzorů na kterých jsem udělal chybu.

I

Analogicky i ostatní vstupní proměnné (včetně prahu). 12 / 32


Učení lineárního klasifikátoru I

A přesně na této myšlence je založen Perceptronový algoritmus. (Proč zrovna perceptronový, necháme teď stranou).

1. Inicializuj váhy na náhodné hodnoty. 2. Vezmi náhodný ∑ vstupní vzor x. A spočítej hodnotu y(x) = sgn( j wj xj = wx). 3. Pokud se požadovaný výstup d(x) liší od skutečného y(x), oprav váhy (w) takto: I I

e(x) = d(x) − y(x) wi (t + 1) = wi (t) + ηe(x)xi

4. Pokud chceš, pokračuj bodem 2). η je koeficient učení, který s postupem času může klesat k nule. http://neuron.felk.cvut.cz/courseware/data/chapter/36nan028/s04.html 13 / 32


Jednoznačnost výsledné přímky I

Jak poznám, že se perceptronový algoritmus zastavil?

I

Je výsledná přímka jediná možná?

I

Ne, takových přímek je dokonce nekonečně mnoho.

I

Přesto jsou některé lepší něž jiné.

I

Kterou mám vybrat? A kterou nám vybere Perceptronový algoritmus? 14 / 32


Lineárně separovatelné problémy

I

Lze pomocí tohoto algoritmu klasifikovat bezchybně následující data?

I

Ne!

I

Třídám (datům), které lze oddělit přímkou říkáme lineárně separovatelná.

15 / 32


Lineárně ne–separovatelné problémy

I I

Lze pomocí lineárního klasifikátoru vyřešit lineárně ne-separovatelné problémy? Ne. K tomu potřebuji přidat další kvalitu. 1. Jednou z možností je zkombinovat lin. klasifikátory. (O tom bude příští přednáška.) 2. Rozšíření báze.

16 / 32


Rozšíření báze

I

Když data nejsou separabilní v originálním prostoru, zkusme jestli by nebyla lineárně separovatelná ve více-dimenzionálním prostoru.

17 / 32


Transformace

I

Zase existuje mnoho transformací.

I

Jedna z těch jednodušších přidává ke stávajícím dimenzím také součiny originálních dimenzí.

I

Je charakterizovaná parametrem s – maximálním stupněm součinu. Pro s = 2 z původních dimenzí (x1 , x2 ) získám 5D prostor dimenzí (x1 , x2 , χ1 , χ2 , χ3 ), kde

I

I I I

χ1 = x21 χ2 = x1 ∗ x2 χ3 = x22

18 / 32


Učení nelineárního klasifikátoru

I

Když mám teď nové dimenze, jak naučím můj klasifikátor?

I

Díky rozšíření báze teď mám více-dimenzionální prostor a (třeba) teď dokáži třídy lineárně separovat.

I

Úplně stejně jako v předchozím případě. Tj použiji například perceptronový algoritmus.

I

Pokud se mi nepodaří získat lineární separaci, mohu zkusit zvýšit maximální stupeň součinu a zkusit separaci znovu.

19 / 32


Rozhodovací hranice

I

Jak pak bude vypadat projekce rozhodovací hranice zpět do originálních dimenzí?

I

Tím se nám podařilo dosáhnout toho, že se rozhodovací hranice ”ohnula”.

I

A pokud budu zvyšovat parametr s, bude hranice stále ”poddajnější”.

20 / 32


Rozhodovací hranice (2)

I I

Můžu zvyšovat maximální stupeň součinu (parametr s) do nekonečna? Nebo někde narazím? S vyšším maximálním stupněm s vyvstávají dva problémy: 1. Jednak mám více vah, které musím nastavovat a perceptronový (nebo jakýkoliv jiný) algoritmus to nemusí zvládnout – čili váhy se nastaví špatně. 2. Zvyšuji pravděpodobnost, že se klasifikátor přeučí. Tj. naučí se šum a chyby v trénovacích datech a nedokáže vlastnosti trénovacích dat zobecnit. (Podobně jako například 1-NN klasifikátor.)

21 / 32


Klasifikace do několika tříd I

Co když mám více než dvě třídy? Mohu použít (ne-)lineární separaci?

I

Případně jak?

I

Budu rozhodovat o každé třídě samostatně.

I

Čili pro problém s N třídami budu mít N klasifikátorů. Každý bude říkat – ”Instance patří do mé třídy” / ”Instance nepatří do mé třídy”. Při rozhodování o neznámé instanci x se zeptám všech N klasifikátorů na jejich rozhodnutí.

I

1. x patří právě do jedné třídy. 2. x patří do více tříd – pak se musím rozhodnout například podle hodnoty xw (čím je větší, tím je x dále od rozhodovací hranice). 3. analogoicky, pokud x nepatří do žádné třídy. Hledám tedy trídu, kam x nepatří nejméně :). 22 / 32


Problémy lineárních klasifikátorů

I

Linearita

I

Pokud se dostatečně pohnu i jen v jedné proměnné, můžu získat obrácený výsledek.

I

Hodnota xw roste se vzdáleností od rozhodovací hranice a nemá žádnou interpretaci.

I

Lineární klasifikátory špatně snášejí chybějící hodnoty.

I

Pokud provádím rozšíření báze, může trvat učení velmi dlouho.

23 / 32


Linear Discriminant Analysis

I

LDA je statistický přístup k problému lineární separace.

I

Pamatujete si PCA? (Principal Component Analisis – mluvili jsme o něm u SOM)

I

LDA redukuje původní prostor na přímku (1 dimenzi) a to tak, co nejvíce oddělil vzory různých tříd.

I

V jistém smyslu je to opak rozšíření báze.

24 / 32


Linear Discriminant Analysis (2)

I

Obraz vzoru v nové souřadnici pak získám jako xw, kde w jsou váhy.

I

V principu počítám to samé jako u lineárního klasifikátoru, ale interpretace a postup jsou úplně jiné.

25 / 32



I

Při počítání LDA se snažím maximalizovat ”separaci” mezi třídami.

I

Nejprve pro každou třídu musím spočítat rozptyl v obraze (scatter).

µs1 =

1 ks1 k

∑

yi = xi w xi

µ˜s1 =

∀xi ∈s1

1 ∑ 1 ∑ yi = xi w ks1 k ks1 k

∑

s˜1 2 =

∀x1 ∈s1

26 / 32


∀xi ∈s1

yi − µ˜s1

∀xi ∈s1


I

A nyní můžu spočítat míru ”separace” pro projekci danou vahami w. kµ˜s1 − µ˜s2 k2 J(w) = s˜1 2 + s˜2 2

I

Hledáme tedy projekci, která co nejvíc seskupí vzory stejné třídy a co nejvíc zároveň oddělí vzory různých tříd.

27 / 32


LDA pro více tříd

I

LDA lze zobecnit tak, aby dokázalo klasifikovat do více tříd.

I

Pak se nevytváří pouze jedna nová dimenze, ale ”počet tříd”-1 nových dimenzí a mírně se upraví vzorečky :).

28 / 32


Problémy LDA

I

Stejně jako všechno, má i LDA nějaké mouchy: I

I

I

Počet dimenzí vytvořený LDA nemusí stačit ke správném zařazení do třídy. LDA předpokládá normální rozložení dat ve třídách. A selhává, pokud tomu tak není. (Například třídy mají komplexní tvary). Rozíly mezi třídami jsou spíše v rozptylu hodnot než v rozdílu středních hodnot.

29 / 32


Logistická regrese I I I I

Co kdybych chtěl, abych dokázal vzdálenosti od rozhodovací hranice nějak interpretovat. Ideálně ještě tak, že je to pravděpodobnost příslušnosti k dané třídě. Existuje logistická funkce, která je definovaná takto f(z) = 1+e1 −z Její hodnoty jsou omezené na interval 0 . . . 1. A navíc kolem z = 0 (rozhodovací hranice) je její změna největší.

30 / 32


Logistická regrese (2)

p 1−p

I

Zkusíme zavést pojem sance =

I

Abychom ji dostali do rozmezí 0 . . . 1 zkusme ji zlogaritmovat.

I

p Tím získáme funkci logit(p) = log(sance(p)) = log( 1−p )

I

Zkusme předpokládat, že logit(p) = β0 + β1 x1 + β2 x2 + . . . + βk xk

I

Kde β1 , . . . , βk jsou regresní koeficienty a β0 je posun.

I

A teď zkusme opět dopočítat pravděpodobnost vzoru x.

I

p(x) =

1 1+e−β0 +β1 x1 +β2 x2 +...+βk xk

31 / 32


Zdroje

I

LDA převzata z research.cs.tamu.edu/prism/lectures/pr/pr_l10.pdf

I

http://www.omidrouhani.com/research/ logisticregression/html/logisticregression.htm

32 / 32


Vytěžování dat, přednáška 10: Neuronové sítě s dopřednou architekturou Miroslav Čepek



1 / 30

Neuronové sítě

Umělé neuronové sítě

I

Umělá neuronová síť je matematickým přiblížením biologické neuronové sítě. A snahou je napodobovat funkci biologických neuronových sítí.

I

Umělé neuronové sítě představují jiný přístup k řešení problémů než konvenční výpočetní technika.

I

Ale mezi schopnostmi umělých neuronových sítí a mozku je přecejen ještě obrovský rozdíl.

2 / 30

Neuronové sítě

Biologická neuronová síť

I

Více si můžete přečíst například na http://www.mindcreators.com/NeuronBasics.htm nebo http://www.generation5.org/content/2000/nn00.asp.

3 / 30

Neuronové sítě

Umělá neuronová síť

I

Se skládá ze vzájemně propojených jednotek – neuronů.

I

Každý neuron transformuje své vstupy na výstup. Čili umí jen velmi málo, ale jejich síla je v jejich spolupráci.

I

Konekcionistivký přístup k umělé inteligenci – představa, že spoluprácí mnoha hloupých jednotek dosáhnu chování, které je kvalitativně ”chytřejší” než jen součet možností jednotlivých elementů.

I

Neuron při transformaci může uplantit svou lokální paměť.

I

Výstupy neuronu jsou přivedeny na vstupy dalších neuronů.

4 / 30

Neuronové sítě

Historie I

První, kdo se začal zabývat výzkumem umělých neuronových sítí byl v roce 1943 jistý profesor McCulloch a jeho žák Pitts. Oba v prvním plánu hledali matematický model biologického neuronu.

I

Tento jejich model se dodnes používá a nazývá se McCulloch-Pittsův neuron.

I

Občas se označuje také jako Perceptron.

http://wwwold.ece.utep.edu/research/webfuzzy/docs/ kk-thesis/kk-thesis-html/node12.html 5 / 30

Neuronové sítě

Princip práce McCulloch-Pittsova neuronu I

Na vstupy x1 , x2 , . . . xn (na předchozím odrázku označeny jako I1 , I2 , . . . In ) předložím pozorované hodnoty.

I

Tyto hodnoty přenásobím vahami w1 , w2 , . . . wn a spočítám tzv. aktivaci neuronu. n ∑ a= wi xi i=1

I

Aktivace odpovídá aktivaci biologického neuronu. A ten ”vypálí” výstup jen v případě, že aktivace překročí určitý práh.

I

To se v umělých neuronových sítích simuluje pomocí aktivační funkce.

I

V případě perceptronu skokovou funkcí. f(a) = 0, pro a < konst, jinak f(a) = 1.

I

Nepřipomíná vám to něco? 6 / 30

Neuronové sítě

Rozhodovací hranice a učení

I

Jak vypadá rozhodovací hranice Perceptronu (McCulloch-Pittsova neuronu)?

I

A jak nastavíme váhy?

I

Přece pomocí perceptronového algoritmu!

I

Jaké jsou limity perceptronu?

7 / 30

Neuronové sítě

Aktivační funkce I

Prvním vylepšením perceptronu jsou různé aktivační funkce, kterými se transformuje aktivaci na výstup.

8 / 30

Neuronové sítě

ADALINE

I

Drobné vylepšení perceptronu, které se týká učícího algoritmu.

I

Při učení se chyba nepočítá přímo z výstupu, ale z aktivace. Což znamená, že musím znát požadovanou aktivaci.

9 / 30

Neuronové sítě

Vícevrstvá síť perceptronů – Madaline I

MADALINE – Multiple Adaptive Linear Element – síť s jednou skrytou vrstvou a jednou výstupní vrstvou.

10 / 30

Neuronové sítě

MADALINE vybavování

I

Výpočet odpovědi sítě na předložený vstupní vzor je jednoduchý.

I

Přivedu na vstupy všech neuronů odpovídající hodnoty vstupů.

I

Pro každý neuron přenásobím vstupní hodnoty vstupnímy vahami a sečtu. Tím získám aktivaci neuronu.

I

Aktivaci transformuji aktivační funkcí na výstup.

I

Když takto vypočítám výstupy všech neuronů, aplikuji majoritu (spočítám kolik neuronů zařadilo vzor do ”třídy” 0 a kolik do ”třídy” 1). A podle toho předpovím výstupní třídu sítě.

11 / 30

Neuronové sítě

Učení MADALINE

I

Učení jen nastíním – předložím vstupní vzor a spočítám výstup sítě.

I

Pokud se výstup shoduje s požadovaným, nedělám nic.

I

Pokud se vypočítaný a skutečný výstup liší, musím změnit váhy ”nějakého” neuronu, který předpovídá špatnou třídu, aby příště ”změnil názor” a tím se majorita přiklonila na správnou stranu.

I

A nejjednodušší je ”přesvědčit” neuron, který má aktivaci nejblíž nule. Tomuto neuronu přepočítám váhy.

12 / 30

Neuronové sítě

Použití MADALINE

I

Je dnes spíše ilustrativní.

I

Učící algoritmus nezvládá komplexní úpravy a nedokáže měnit váhy neuronů dostatečně flexibilně.

I

Druhý a stejně závažný problém – MADALINE z principu fungování nemůže zvládnout lineárně neseparabilné problémy. Vymyslíte proč?

I

Problém dělá ta majorita...

13 / 30

Neuronové sítě

Back Propagation

I

Neuronová síť typu back propagation představuje elegantní cestu, jak se vypořádat s problémy sítě MADALINE a zárověň zvládnout učení několika skrytých vrstev.

I

Podle jména dochází k zpětnému šíření – kokrétně ke zpětnému šíření chyby.

I

Nejedná se v pravém slova smyslu o jednu neuronovou síť, ale označuje se tímto pojmem libovolná síť, ve které se při učení šíří chyba z výstupu zpět na vstup. Můžete narazit i na jiné back propagation síť, než o které budu vyprávět já.

I

BP jsou prakticky jediným typem sítí, který je znám mimo výzkumnou komunitu zabývající se NS.

14 / 30

Neuronové sítě

Struktura Back Propagation I

Jedná se o dopřednou síť s jednou nebo dvěma skrytými vrstvami.

I

Vrstva se skládá z neuronů – jejich počet v jednotlivých vrstvách (a počet vrstev) je jedním z parametrů, který musíte určit experimentálně – tj. zkusit.

I

Existuje celá teorie, která dokazuje, že k aproximaci libovolné funkce (libovolné rozhodovací hranice) stačí dvě skryté vrstvy.

15 / 30

Neuronové sítě

Back Propagation neuron

I

Jedná se o standardní Perceptron se spojitou (!!) aktivační funkcí. Spojitost funkce budeme používat při učení – budeme počítat derivace.

16 / 30

Neuronové sítě

Back Propagation aktivační funkce

17 / 30

Neuronové sítě

Back Propagation učení (1)

I

Učící algoritmus je trochu podobný tomu, co jsme již viděli.

I

Nejprve se spočítá odpověď (výstup) sítě na předložený vstup, pak se spočítá rozdím mezi vypočítaným a požadovaným výstupem.

I

Co je úplně jiné – je výpočet změny vah.

I

Chyba se totiž distribuuje zpět ke vstupům a postupně se upravují váhy ve skrytých vrstvách.

I

A pak se pokračuje předložením dalšího vzoru, až do té doby než dosáhneme zastavujícího kritéria.

18 / 30

Neuronové sítě


1. Inicializuj všechny váhy všech neuronů na náhodné hodnoty. 2. Vytvoř permutaci trénovací množiny. 3. Vyber další vzor xi z vytvořené permutace. 4. Vypočítej výstup sítě yi . 5. Spočítej chybu (rozdíl) mezi yi a skutečnou hodnotou di . 6. Postupně propaguj chybu zpět a modifikuj váhy. 7. Pokud jsi dosud nepředložil všechny prvky z trénovací množiny pokračuj bodem 3. 8. Pokud chyba přes všechny trénovací vzory je větší než zvolené kritétium, pokračuj bodem 2.

19 / 30

Neuronové sítě

Back Propagation učení (3) I

Výpočet výstupu sítě se provádí již známým způsobem.

I

Pro každý neuron, u nějž známe všechny vstupy spočítáme aktivaci. n ∑ wi xi + Θ a= i=1

. I

Pokud znám aktivaci můžu spočítat výstup pomocí zvolené aktivační funkce.

I

Pro, například, logistickou funkci tedy 1 y= 1 + e−γa

I

Takto postupuji pro všechny neurony, až zjistím výstup výstupního neuronu. 20 / 30

Neuronové sítě


I

Když zjistím výstup pro všechny vzory v trénovací množině, můžu zjistit globální chybu (energii) sítě. 1∑ E= (yi − di )2 2 n

i=1

I

A snažíme se chybu (energii) minimalizovat. To se dá dělat různě a jednou z variant je gradientní sestup.

I

Gradientní metoda mění váhy tak, aby energie klesla co možná nejvíc.

21 / 30

Neuronové sítě


I

”Na horách se chci dostat do údolí. Podívám se, kterým směrem se kopec nejvíc snižuje a udělám krok tím směrem. A zase se podívám, kam je to nejvíc z kopce a udělám krok. A tak dále, až jednou zjistím, že to dál nejde, čili jsem v údolí.”

I

V matematice existuje možnost, jak zjistit směr největšího vzestupu hodnoty funkce - gradient. To je první parciální derivace podle všech dimenzí. Když půjdu přesně opačně, půjdu ve směru největšího poklesu.

22 / 30

Neuronové sítě


Po chvíli derivování spočítáme (viz například skripta Miroslav Šnorek: ”Neuronové sítě a neuropočítače”), dojdeme k následujícím vzorcům. δio (t) = (yoi − di )S0 (ϕ)

I

I

Kde δio (t) je požadovaná změna neuronu i ve výstupní vrstvě o při skutečném výstupu yi oproti skutečnému výstupu di . S0 je funkce inverzní k aktivační funkci a ϕ je aktivace neuronu. Změnu váhy mezi neuronem i ve vástupní vrstvě a neuronem j v první skryté vrstvě pak spočítám takto: woij (t + 1) = woij (t) + ∆woij (t) ∆woij (t) = ηδio (t)yhj

I

Kde yhj je výstup j-tého neuronu ve druhé skryté vstvě. 23 / 30

Neuronové sítě


I

Nový práh neuronu i ve výstupní vrstvě o pak spočítám takto: Θoi (t + 1) = Θoi (t) + ∆Θoi (t) ∆Θoi (t) = ηδio (t)

24 / 30

Neuronové sítě


V druhé skryté vrstvě pak změnu vah vypočítám podle následujících vzorců: ∑ δih (t) = yhi (1 − yhi ) woik δko whij (t + 1) = whij (t) + ∆whij (t) ∆whij (t) = ηδih (t)yh−1 j Θhi (t + 1) = Θhi (t) + ∆Θhi (t) ∆Θhi (t) = ηδih (t)

I

Kde whij e váha mezi neuronem i ve druhé skryté vrstvě a j v první skryté vrstvě. yh−1 je výstup j-tého neuronu v první j skryté vrstvě. 25 / 30

Neuronové sítě

Back Propagation vylepšení trénovacího algoritmu I

Všechna vylepšení směřují k tomu, abych zvýšil pravděpodobnost toho, že (rychleji) najdu globální minimum energetické funkce.

I

Lze si jednoduše představit situaci, kdy gradientní sestup – tak jak jsem o něm teď mluvil – skončí v lokálním extrému. (Všechny body ve vzdálenosti 1 krok jsou výše, ale rozhodně nejsem v globálním minimu).

I

Setrvačnost – při hledání směru kroku v čase t + 1 zohledním nejen současný gradient, ale i směr a velikost minulého kroku.

I

Restart – nejde o vylepšení učícího algoritmu v pravém smyslu slova, ale pokud se sestup energetické funkce zastaví, zapamatuji si výsledek a začnu znova.

I

Další podrobnosti viz. například skripta Miroslav Šnorek: Neuronové sítě a neuropočítače. 26 / 30

Neuronové sítě

Další neuronové sítě

I

Prezentované sítě nejsou zdaleka jediné, které existují. I když Back propagation je nejznámější, neznamená to, že je nejlepší, nejzajímavější a nejlépe fungující.

I

Exitují například sítě, které při učení mění nejen váhy, ale i svou strukturu – sítě GMDH a GAME. Navíc mohou používat úplně jiné aktivační funkce.

I

Síť s jiným typem neuronů (a v každé vrstvě jiné) – RBF síť.

I

Sítě s velkými počty neuronů, kde váha mezi neurony i a j není určena zapamatovanou hodnotou, ale nějakou funkcí w(i, j) – HyperNEAT (umožňuje tvořit sítě s tisíci neuronů).

I

Sítě pro shlukování – SOM.

27 / 30

Neuronové sítě

Použití neuronových sítí

I

Klasifikace

I

Regrese

I

Shlukování

I

Komprese dat

I

Filtrování

I

Řízení

28 / 30

Neuronové sítě

Problémy / Nevýhody

I

Umělé neurnové sítě (stejně jako cokoliv) nejsou všemocné. A na některé problémy se nehodí nebo jsou zbytečně složité. Předtím než začnete zkoušet NS zkuste se zamyslet nad následujícími otázkami:

I

Dokáži jednoduše popsat řešení problému? Pokud ano, je mnohem jednodušší držet se tradičního programování.

I

Mám dostatečné množství ohodnocených dat v trénovací množině?

I

Musím získat absolutně přesné hodnoty na výstupu?

I

Potřebuji být schopen jednoduše vysvětlit funkci modelu?

29 / 30

Neuronové sítě

Zdroje

I

http://www.mind.ilstu.edu/curriculum/modOverview. php?modGUI=212

I

http://neuron.felk.cvut.cz/courseware/html/ chapters.html

I

skripta – Miroslav Šnorek: Neuronové sítě a neuropočítače.

I

série knih – Mařík a spol: Umělá inteligence

I

http://www.mindcreators.com/TableOfContents.htm

30 / 30

Neuronové sítě

Vytěžování dat, cvičení 9: Strojové učení Radomír Černoch



1 / 11

Strojové učení

Iris data ještě jednou

2 / 11

Strojové učení

Zmenšený dataset Iris sl = Sepal Length 4.3 5.0 5.7 5.0 5.7 6.3 4.9 6.2 6.8 7.7

3 / 11

sw = Sepal Width 3.0 3.3 4.4 2.3 2.8 3.3 2.5 2.8 3.2 3.0

Strojové učení

pl = Petal Length 1.1 1.4 1.5 3.3 4.1 4.7 4.5 4.8 5.9 6.1

pw = Petal Width 0.1 0.2 0.4 1.0 1.3 1.6 1.7 1.8 2.3 2.3

c= Species setosa setosa setosa versicolor versicolor versicolor virginica virginica virginica virginica

Naïve Bayes I

NB klasifikace počítá pravděpodobnosti třídy, pokud známe hodnoty atributů. Např. p(c = setoza | sl = 5.5, sw = 3.3, pl = 4.8, pw = 9.9).

I

Tuto pravděpodobnost neznáme přímo, pro její výpočet se používá Bayesovo pravidlo: p(c | sl, sw, pl, pw) =

I

p(c) · p(sl, sw, pl, pw | c) p(sl, sw, pl, pw)

(1)

Protože distribuce p(sl, sw, pl, pw | c) má příliš mnoho parametrů, předpokládá se jejich nezávislost („naivita“ NB klasifikátoru): p(sl, sw, pl, pw | c) = p(sl | c) · p(sw | c) · p(pl | c) · p(pw | c) . (2) 4 / 11

Strojové učení

Fáze 1: Učení

I

Učení stanovuje parametry Naïve Bayes modelu = distribuce p(sl | c), p(sw | c), p(pl | c) a p(pw | c) a p(c).

I

Distribuce p(c) říká, do kterého druhu patří libovolný květ kosatce, aniž bychom znali jakoukoli jeho vlastnost. Dá se říci, že tato distrubuce reprezentuje naše „předsudky“. Vypočtěte její parametry (předpokládejte multinomialní rozdělení ).

I

Ostatní určují rozložení jednotlivých atributů okvětních lístků pro každý druh kosatce zvlášť. Zachycuje tak vliv „měření“. Vypočtěte p(sl | c) (předpokládejte normální rozdělení ).

5 / 11

Strojové učení

Fáze 1: Učení

Správné výsledky   3/10 pro c = setosa 3/10 pro c = versicolor p(sl | c) =  4/10 pro c = virginica   N (µ = 5.0, σ = .70) pro c = setosa N (µ = 5.7, σ = .65) pro c = versicolor p(sl | c) =  N (µ = 6.4, σ = 1.2) pro c = virginica

6 / 11

Strojové učení

(3)

(4)

Fáze 1: Učení

  N (µ = 3.6, σ = .74) pro c = setosa N (µ = 2.8, σ = .50) pro c = versicolor p(sw | c) =  N (µ = 2.9, σ = .30) pro c = virginica   N (µ = 1.3, σ = .21) N (µ = 4.0, σ = .70) p(pl | c) =  N (µ = 5.3, σ = .79)   N (µ = .23, σ = .15) N (µ = 1.3, σ = .30) p(pw | c) =  N (µ = 2.0, σ = .32)

7 / 11

Strojové učení

(5)

pro c = setosa pro c = versicolor pro c = virginica

(6)

pro c = setosa pro c = versicolor pro c = virginica

(7)

Fáze 2: Klasifikace I

Mějme okvětní lístek sl = 5.5, sw = 2.4, pl = 3.7 a pw = 1.0. O jaký druh kosatců se jedná? (Pro kontrolu: versicolor.)

I

Výpočet je pouze zjednodušením vzorců z úvodu a dosazením: p(c | sl, sw, pl, pw) = = = = =

8 / 11

p(c) · p(sl | c) · p(sw | c) · p(pl | c) · p(pw | c) = (8) p(sl, sw, pl, pw) ψ(sl, sw, pl, pw, c) = (9) p(sl, sw, pl, pw) ψ(sl, sw, pl, pw, c) ∑ = (10) c p(c) · p(sl, sw, pl, pw | c) ψ(sl, sw, pl, pw, c) ∑ (11) c ψ(sl, sw, pl, pw, c)

Strojové učení

Fáze 2: Klasifikace ψ(sl = 5.5, sw = 2.4, pl = 1.4, pw = 1.1, c = setoza) =

= p(c = set.)· · p(sl = 5.5 | c = set.) · p(sw = 2.4 | c = set.)· · p(pl = 1.4 | c = set.) · p(pw = 1.1 | c = set.) = (12)

1

p(x | µ, σ) = √ exp 2 π σ2 =

(

x−µ √ 2 σ2

)2

3 · 0.44 · 0.15 · 1.8 · 2.6·10−7 = 3.1·10−8 10

9 / 11

Strojové učení

(13) (14)

Fáze 2: Klasifikace ψ(..., c = versicolor) = 5.5·10−5 ; ψ(..., c = virginica) = 1.8·10−9 p(c = setoza | ...) = =

ψ(..., c = versicolor) = ψ(..., c = set.) + ψ(..., c = ver.) + ψ(..., c = vir.) = 0.056% (15) p(c = versicolor | ...) = 99.94%

(16)

p(c = virginica | ...) = 0.004%

(17)

Bingo! Versicolor vyhrává.

10 / 11

Strojové učení

Zadání úlohy

1. V prostření Matlab implementujte k-NN klasifikátor a otestujte jej na datasetu „Breast Cancer“ 2-fold krosvalidace1 . 2. Zjistěte chybu klasifikátoru zvlášť na trénovací i testovací množině pro hodnoty k od 1 do velikosti datasetu. Oba průběhy vyneste do grafu v závislosti na k. 3. Průběh grafu interpretujte s přihlédnutím k principu fungování algoritmu k-NN. Zdrojové kódy odevzdejte do upload systému samostatně vedle PDF protokolu.

1

viz. Wikipedie 11 / 11

Strojové učení

Vytěžování dat, cvičení 10: Rozhodovací stromy Jan Hrdlička



1/8

Rozhodovací stromy

Prořezávání stromů

I

Cílem této úlohy je zjistit, jak se projevuje prořezávání stromu na úspěšnosti klasifikace na testovací množině.

I

Rozhodovací stromy už znáte z přednášky.

2/8

Rozhodovací stromy

Dataset

I

Dataset je uměle generovaný na začátku souboru cv10.m, který si stáhnete ze stránek cvičení. Úkolem bude tento soubor doplnit.

I

Dataset se skládá z ”naměřených” hodnot (proměnná obs) a z tříd do kterých se snažíme klasifikovat (proměnná class).

I

Třídy jsou 2: ”green” a ”blue”.

3/8

Rozhodovací stromy

Přehled úlohy

I

V m-file se nejprve vygeneruje soubor dat. Poté se v cyklu opakovaně pouští náhodné rozřazení na trénovací a testovací množinu. Vaším úkolem je uvnitř cyklu...

I

Vytvořit rozhodovací strom z trénovací množiny

I

Zjistit chybu na testovací množině pro různé úrovně prořezání.

I

Zarovnat chyby po prořezání podle hloubky zbylého stromu

I

Tabulku chyb vykreslit pomocí grafu boxpolot

4/8

Rozhodovací stromy

Vytvoření stromu

I

K vytvoření stromu použijte funkci classregtree.

I

DULEŽITÉ: nastavte parametry ”prune” na ”off” a ”splitmin” na 2

I

K vytvoření stromu použijte trénovací množinu

5/8

Rozhodovací stromy

Zjištění chyby (misclassification cost)

I

Ke zjištění chyby použijte funkci test (je jich v matlabu vice, tahle je metoda u třídy @classregtree)

I

Pusťte ji na testovací množině.

I

Funkce vráti vektor chyb pro různé prořezání stromu. Na prvním místě je chyba pro strom bez prořezání, na posledním místě chyba pro strom s hloubkou 1.

6/8

Rozhodovací stromy

Zarovnání chyb

I

Chyby srovnejte do tabulky costs podle hloubky stromu po prořezání, ne podle úrovně prořezání

I

Příklad: během dvou cyklů naleznete 2 různě hluboké stromy, hloubky 4 a hloubky 6. Metoda test vám vrátí vektor s délkou 4 resp. 6. Vašim cílem je, aby vždy poslední indexy byly v tabulce pod sebou. Poslední indexy totiž reprezentují chybu pro strom hloubky 1, předposlední 2 atd..

7/8

Rozhodovací stromy

Faktické náležitosti protokolu

Váš protokol by měl obsahovat: I

Boxplot daných úrovní rozhodovacích stromů

I

Vysvětlení boxplotu

8/8

Rozhodovací stromy

Vytěžování dat, cvičení 11: Lineární klasifikátor Miroslav Čepek



1/3


Zadání domácího úkolu

I

Implementujte perceptronový algoritmus podle slajdů z přednášek.

I

Pomocí implementovaného algoritmu klasifikujte OBA datasety ze stránek předmětu.

I

Proveďte rozšíření báze (pro s = 2) a opět klasifikujte oba datasety.

2/3


Obsah zprávy

I

Obsahem zprávy bude I I

I I

stručný popis algoritmu, klasifikační úspěšnost lineárního klasifikátoru a lineárního klasifikátoru s rozšířenou bází pro oba datasety, zobrazení rozhodovací hranice pro vybrané případy, váš komentář ke všem předchozím bodům.

3/3


Základy vytěžování dat

Recommend Documents