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

Odhady pravděpodobnostních rozdělení

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


Vytěžování dat, přednáška 2: Pravděpodobnostní rozdělení Filip Železný


Fakulta elektrotechnická, ČVUT

1 / 24

Pravděpodobnostní rozdělení

Odhad rozdělení

Úloha: I

Vstup: data D = {~x1 ,~x2 , . . .~xm }, ~xi ∈ X (1 ≤ i ≤ m), m ∈ N náhodně, navz. nezávisle vybraná z rozdělení PX na X

I

Výstup: vzor h∈L reprezentující odhad PX , tj. generativní model dat

2 / 24


Odhad rozdělení: příklad úlohy

2 druhy bonbónů v balíčku

Vybíráme náhodně (poslepu), dostaneme . Jaký je poměr (pravděpodobnost) zelených bonbónů v balíčku?

3 / 24


Odhad rozdělení: příklad úlohy (pokr.)

X = { ., . } PX lze reprezentovat jedním číslem θ P( .) = θ, P( .) = 1 − θ Tedy prostor vzorů je reálný interval L = [0; 1] Pozn.: ve skutečnosti konečná podmnožina [0; 1], neboť reálná čísla se reprezentují konečným počtem číslic.

4 / 24


Odhad dle četnosti

Data D={ .

} (m = 10)

Odhad dle relativní četnosti: P( .) = θ ≈

9 10

Odůvodnění: četnost konverguje k pravděpodobnosti pro m → ∞.

5 / 24


Odhad dle maximální věrohodnosti I

Obecnější metoda odhadu. Používá podmíněnou pravděpodobnost P(D|θ) tj.: má-li parametr hodnotu θ, budeme data D pozorovat s touto pravděpodobností. Nazývá se věrohodnost (likelihood).

I

Parametr odhadneme tak, že věrohodnost maximalizujeme θ∗ = arg max P(D|θ) θ

I

Data xi ∈ D jsou vybírána navzájem nezávisle, tedy: P(D|θ) = Πm i=1 P(xi |θ)

6 / 24


Věrohodnost: příklad

D={ . I

I

} (m = 10)

Pro θ = P( .) = 0.6 P(D|θ) = P( .|0.6)9 · P( .|0.6)1 = 0.69 · 0.4 ≈ 0.004 Pro θ = P( .) = 0.8 P(D|θ) = P( .|0.8)9 · P( .|0.8)1 = 0.89 · 0.2 ≈ 0.027

I

Tedy θ = 0.8 je věrohodnější než θ = 0.6.

Obecně: jak najít θ, které věrohodnost maximalizuje?

7 / 24


Logaritmus věrohodnosti Pro snazší výpočet používáme logaritmus věrohodnosti L(D|θ) = log P(D|θ) tedy L(D|θ) = log Πm i=1 P(xi |θ) =

m ∑

log P(xi |θ)

i=1

V příkladě s bonbóny: L(D|θ) = log θz + log(1 − θ)c = c log θ + z log(1 − θ) kde c a z je počet červených resp. zelených bonbónů v datech

8 / 24


Hledání maxima věrohodnosti θ maximalizuje věrohodnost právě tehdy, když maximalizuje její logaritmus. Hledáme maximum L(D|θ), tedy položíme d L(D|θ) = 0 dθ V příkladě s bonbóny: d c z (c log θ + z log(1 − θ)) = − =0 dθ θ 1−θ Řešení:

c c = c+z m Tedy stejný výsledek jako u odhadu dle relativní četnosti. Metoda maximální věrohodnosti je ale obecnější - uvidíme dále. θ=

9 / 24


Omezená množina vzorů Tentokrát víme, že se vyrábí jen 5 typů balíčků:

1. 100% zelených 2. 75% zelených, 25% červených 3. 50% zelených, 50% červených 4. 25% zelených, 75% červených 5. 100% červených Každý typ představuje jeden vzor pro generování dat (losování bonbónů), označme je po řadě L = {h1 , h2 , h3 , h4 , h5 }. 10 / 24


Vzor s maximální věrohodnostní Odhad dle četností již není použitelný, metoda maximální věrohodnosti je. P(D|h1 ) = 1z + 0c P(D|h1 ) = 0.75z + 0.25c P(D|h3 ) = 0.5z + 0.5c P(D|h4 ) = 0.25z + 0.75c P(D|h5 ) = 0z + 1c

(z, c ... počet zelených resp. červených bonbónů v datech) Dostáváme samé zelené: D = { . nejvěrohodnější? 11 / 24


. . .}, který vzor je

Apriorní pravděpodobnosti Marginální rozdělení pravděpodobnosti PL (hi ) vzorů může být známo před obdržením dat. Např: 1. 2. 3. 4. 5.

100% zelených – 10% výroby 75% zelených, 25% červených – 20% výroby 50% zelených, 50% červených – 40% výroby 25% zelených, 75% červených – 20% výroby 100% červených – 10% výroby

Tedy PL (h1 ) = 0.1, PL (h2 ) = 0.2, PL (h3 ) = 0.4, PL (h4 ) = 0.2, PL (h5 ) = 0.1 Tyto pravděpodobnosti se nazývají apriorní. 12 / 24


Aposteriorní pravděpodobnost Známe-li rozdělení I PL I a (po obdržení dat) P(D|hi ) pro každý vzor hi můžeme podle Bayesova pravidla spočítat P(hi |D) =

P(D|hi )PL (hi ) P(D)

P(hi |D) je aposteriorní pravděpodobnost vzoru hi po obdržení dat D. Jmenovatel P(D) =

|L| ∑

P(D|hj )P(hj )

j=1

nezávisí na hi . Z tohoto důvodu arg max P(hi |D) = arg max P(D|hi )PL (hi ) hi

hi

13 / 24


Odhad dle MAP Metoda maximální aposteriorní pravděpodobnosti (MAP) vybírá vzor h h = arg max P(hi |D) = arg max P(D|hi )PL (hi ) hi

hi

Srov. s metodou maximální věrohodnosti, kde h = arg max P(D|hi ) hi

MAP tedy bere navíc úvahu informaci nesenou apriorním rozdělením PL (hi ). Ta je významná pro malé množství dat, ale s rostoucím množstvím dat její význam klesá: arg max P(D|hi )PL (hi ) →m→∞ arg max P(D|hi ) hi

hi

14 / 24


Aposteriorní pravděpodobnost jako funkce množství dat

.1

.P(h1 |d)

.P(h2 |D)

.P(h3 |D)

.P(h4 |D)

.P(h5 |D)

.D = { .PL (h3 )

.. . .}

.(dostáváme samé zelené)

.PL (h2 ) = PL (h4 ) .PL (h1 ) = PL (h5 ) . .0 15 / 24

.10 Pravděpodobnostní rozdělení

.m

Odhad parametrů normálního rozdělení Data D = {x1 , x2 , . . . xm } vybrána navz. nezávisle z rozdělení (x−µ)2 1 PX (x) = √ e− 2σ2 2πσ

Z dat odhadujeme parametry µ, σ. Aplikace metody max. věrohodnosti:

L(D|µ, σ) =

m ∑ i=1

m ∑ √ (xi − µ)2 log P(xi |µ, σ) = m(− log 2π−log σ)− 2σ 2 i=1

∑m m xi 1 ∑ d L(D|θ) = − 2 (xi − µ) = 0 ⇒ µ = i=1 dµ σ m i=1 √ ∑m m 2 ∑ d m 1 i=1 (xi − µ) L(D|θ) = − + 3 (xi − µ)2 = 0 ⇒ σ = dσ σ σ m i=1

16 / 24


Směs normálních rozdělení (pokr.) pohlaví žena žena muž žena muž muž …

výška 171 164 182 169 178 184 X = P × V = {muž, žena} × R+

D = {~x1 ,~x2 ,~x3 , . . .} = {(p1 , v1 ), (p2 , v2 ), (p3 , v3 ), . . .} = {(žena, 171), (žena, 164), (muž, 182), . . .}

17 / 24


Směs normálních rozdělení (pokr.) I

Rozdělení výšek je součtem dvou normálních rozdělení (muži, ženy)

I

Každé má svoji střední hodnotu a rozptyl

Rozdělení PX na X lze vyjádřit jako PX (~x) = PX ([p, v]) = PP (muž)PV|P (v|muž)+PP (žena)PV|P (v|žena) ) ( 1 (x − µmuž )2 PV|P (v|muž) = √ exp − 2 2σmuž 2πσmuž ( ) (x − µžena )2 1 exp − PV|P (v|žena) = √ 2 2σžena 2πσžena 18 / 24


Směs normálních rozdělení (pokr.)

Odhady dle maximální věrohodnosti, zvlášť pro každé pohlaví: pohlaví žena žena žena

výška 171 164 169

pohlaví muž muž muž

∑m

i=1 xi

504 = = 168 µžena ≈ 3 √ m 32 + 42 + 12 σžena ≈ ≈ 2.94 3

19 / 24


výška 182 173 188

∑m

σmuž

i=1 xi

543 = 181 3 √ m 12 + 8 2 + 7 2 ≈ ≈ 6.16 3

µmuž ≈

=

Skrytá proměnná Víme, že v populaci jsou muži a ženy, ale proměnná (příznak) pohlaví v datech není. pohlaví žena žena muž žena muž muž

výška 171 164 182 169 178 184

Jak nyní odhadnout PX , tedy parametry µmuž , σmuž , µžena , σžena a P(žena)?

20 / 24


Algoritmus EM 1. ‘Nastřel’ počáteční hodnoty parametrů, např. µžena = 150, σžena = 10 µmuž = 200, σmuž = 10 P(žena) = 0.5, P(muž) = 0.5

2. Krok E (expectation): Se stanovenými parametry spočti pravděpodobnosti hodnot skryté proměnné pro každou instanci, např. P(žena|171) = P(171|žena)P(žena)/P(171) = ( ) 1 (171 − µžena )2 √ exp − · 0.5/P(171) 2 2σžena 2πσžena = 0.01391 · 0.5/P(171) 21 / 24


Algoritmus EM (pokr.) 2. Krok E (pokr.) P(muž|171) = P(171|muž)P(muž)/P(171) = ( ) (171 − µmuž )2 1 √ exp − · 0.5/P(171) 2 2σmuž 2πσmuž = 0.00188 · 0.5/P(171)

P(žena|171) + P(muž|171) = 1 0.01391 · 0.5 P(žena|171) = = 0.88 0.01391 · 0.5 + 0.00188 · 0.5 P(muž|171) = 1 − 0.88 = 0.12

22 / 24


Algoritmus EM (pokr.) 3. Krok M (maximization): Se spočtenými pravděpodobnostmi pro hodnoty skrytých proměnných znovu odhadni parametry rozdělení m 1 ∑ µžena ← P(žena|vi )vi Nžena i=1 v u m u 1 ∑ σžena ← t P(žena|vi )(vi − µžena )2 Nžena i=1

1 ∑ P(žena) ← P(žena|vi ) m m

i=1

I

∑m Nžena = i=1 P(žena|vi ) . . . normalizační konstanta, zaručuje, že součet P(žena|vi ) přes všechny instance je 1.

Analogicky spočteme pro muže. 4. Opakuj krokem 2 (dokud změny nejsou dostatečně malé) 23 / 24


Algoritmus EM (pokr.)

Konvergence algoritmu EM iterace 0 1 2 (správné hodnoty)

24 / 24

µžena 150.000 167.007 167.951 168


µmuž 200.000 181.972 181.956 181

Vytěžování dat, přednáška 3: Grafické pravděpodobnostní modely Filip Železný



1 / 25

Grafické pravděpodobnostní modely

Mnoharozměrné rozdělení I

Minulá přednáška: odhad rozdělení pro data s jedním příznakem ~x = x resp. dvěma příznaky ~x = (x1 , x2 ) I

I

V této přednášce: odhadujeme rozdělení pro více příznaků (rozměrů) I

I

jednorozměrné resp. dvourozměrné rozdělení P(~x)

P(~x) = P(x1 , x2 , . . . xn )

Příklad: Věk 56 32 48 60

~x1 : ~x2 : ~x3 : ~x4 :

2 / 25

Pohlaví muž žena žena muž

Kuřák + − + +


Rakovina + − + +

Značení náhodných veličin Věk 56 32 48 60 I


Kuřák + − + +

Rakovina + − + +

Vektorové/maticové značení ~x3 = (48, žena, −, −) x3,2 = žena

I

Pomocí prvních písmen příznaků (= náhodných veličin) (V3 , P3 , K3 , R3 ) = (48, žena, −, −) P3 = žena

I

Obor hodnot X = V×P×K×R = {1, 2, . . . 100}×{muž, žena}×{+, -}×{+, -} 3 / 25


Odvozování ze sdruženého rozdělení Známe-li sdružené rozdělení všech příznaků, můžeme odvodit rozdělení (sdružené i podmíněné) přes kteroukoliv podmnožinu příznaků. Např. I

pravděpodobnost, že osoba je muž - kuřák PP,K (muž, +) =

∑∑

PV,P,K,R (v, muž, +, r)

v∈V r∈R I

pravděpodobnost, že kouřící muž má rakovinu PR,P,K (+, muž, +) PP,K (muž, +) ∑ v∈V PV,P,K,R (v, muž, +, +) ∑ ∑ = v∈V r∈R PV,P,K,R (v, muž, +, r)

PR|P,K (+|muž, +) =

4 / 25


Reprezentace sdruženého rozdělení I

Parametrická: např. mnoharozměrné normální rozdělení s parametry: vektor µ ~ středních hodnot a matice Σ tzv. kovariancí. (Mimo rozsah tohoto předmětu)

I

Neparametrická: jedno číslo ∈ [0; 1] pro každou kombinaci hodnot příznaků. V našem příkladě tedy: |V| · |P| · |K| · |R| = 100 · 2 · 2 · 2 = 800 (Odpovídá 4-rozměrné kontingenční tabulce.) Ve skutečnosti stačí 799 čísel. Proč? ∑∑∑∑ PV,P,K,R (v, p, k, r) = 1 v∈V p∈P k∈K r∈R

tedy jednu pravděpodobnost dopočítáme z ostatních. 5 / 25


Kombinatorická exploze Problémy s neparametrickým sdruženým rozdělelním: I

Paměťová náročnost. I kdyby všechny příznaky byly pouze binární, potřebujeme pro reprezentaci sdruženého rozdělení 2n − 1 čísel, kde n je počet příznaků. Exponenciální nárůst! I

I

Např. pro n = 40, jedno číslo - float - 4 bajty ⇒ potřebujeme přes 4 TB

Datová náročnost. Pro odhad každého čísla (pravděpodobnosti) z relativní četnosti, např.

PV,P,K,R (30, muž, -, -) ≈

počet 30-letých zdravých nekuřáků v datech počet dat

roste potřebný počet dat také exponenciálně. (Pro danou spolehlivost odhadu) Jak z toho ven? 6 / 25


Využití nezávislosti

I

Kdyby byly všechny příznaky navzájem nezávislé, tak PV,P,K,R = PV · PP · PK · PR a stačí tak znát jen 4 marginální rozdělení, zde tedy (100 − 1) + (2 − 1) + (2 − 1) + (2 − 1) = 102 čísel (místo původních 799).

I

Obecně pro binární příznaky: n čísel místo 2n − 1 čísel.

I

Většinou ale všechny příznaky navzájem nezávislé nejsou!

7 / 25


Využití nezávislosti (pokr.)

I

I nezávislost jedné veličiny na ostatních znamená značné ulehčení: Věk 56 32 48 60


Kuřák + − + +

Rakovina + − + +

PV,P,K,R,M | {z } 100·2·2·2·12−1=9599 čísel I

Měsíc narození 7 2 12 6

PV,P,K,R · PM | {z }

=

800−1+12−1=810 čísel

Ale ani nezávislost jediné veličiny nelze obvykle předpokládat.

8 / 25


Podmíněná nezávislost Pozorování: výskyt rakoviny R je závislý na pohlaví P, tj. PR|P 6= PR , ekvivalentně: PP|R 6= PP ale pouze proto, že muži častěji kouří. Tedy jakmile víme, zda osoba kouří, na pohlaví už nezáleží PR|P,K = PR|K , ekvivalentně: PP|R,K = PP|K R a P jsou tedy podmíněně nezávislé, přičemž podmínkou je K. Totéž jinými slovy: I V celé populaci mají častěji rakovinu muži: PR|P (+|muž) > PR (+) I U kuřáků už na pohlaví nezáleží: PR|P,K (+|muž, +) = PR|K (+|+) I Totéž u nekuřáků: PR|P,K (+|muž, −) = PR|K (+|−) 9 / 25


Grafické znázornění podmíněných nezávislostí Pro dané rodiče uzlu je uzel podmíněně nezávislý na všech uzlech, které nejsou jeho potomky. .V

.. P I

.K

.R

Orientovaný graf bez cyklů

Pro dané rodiče uzlu je uzel podmíněně nezávislý na všech uzlech, které nejsou jeho potomky. Kouření (K) závisí na všech ostatních příznacích. Výskyt rakoviny (R) závisí na kouření (K) a věku (V), ale pro dané K a V nezávisí na pohlaví P. 10 / 25


Výpočet sdruženého rozdělení .V

.

.. P

.R .K PR,K,V,P =PR|K,V,P · PK,V,P

=PR|K,V · PK,V,P =PR|K,V · PK|V,P · PV,P

=PR|K,V · PK|V,P · PV · PP (nezávislost V a P) 11 / 25


Výpočet sdruženého rozdělení (pokr.)

.V

.. P

.K

.R

Obecně pro příznaky X = X1 × X2 × . . . × Xn :

PX = Πni=1 PXi |rodiče(Xi ) rodiče(Xi ): v nezávislostním grafu, např. rodiče(R) = {K, V}

12 / 25


Příklad s binárními příznaky V: P:

vloupání do domu volá soused Pepa

Z: M:

zemětřesení volá sousedka Marie

.V

.Z

.. A

.P

13 / 25


.M

A:

ozval se alarm

Podmíněné nezávislosti .V

.Z

.A.

.P

.M

V nezávisí na Z. Z nezávisí na V. A závisí na všech ostatních. A závisí na všech ostatních. Při daném A nezávisí P na V ani Z. Při daném A nezávisí P na V, Z ani M. Při daném A nezávisí M na V, Z, ani P. 14 / 25


Výpočet sdruženého rozdělení .V

.Z

.. A

.P

.M

PX = Πni=1 PXi |rodiče(Xi ) PV,Z,A,P,M = PP|A · PM|A · PA|V,Z · PV · PZ 15 / 25


Tabulky podmíněných pravděpodobností PV,Z,A,P,M = PP|A · PM|A · PA|V,Z · PV · PZ PV,Z,A,P,M jsme dekomponovali na rozdělení PP|A , PM|A , PA|V,Z , PV , PZ . Každé z nich popíšeme tabulkou podmíněných pravděpodobností (TPP).

PP|A (+|a) 0.90 0.05

a + −

PV (+) 0.001

PM|A (+|a) 0.70 0.01

a + −

PZ (+) 0.002

PA|V,Z (+|v, z) 0.95 0.94 0.29 0.001

10 čísel (místo 25 = 32) 16 / 25


v + + − −

z + − + −

Bayesovská síť .

PV (+) 0.001

. .V

.Z

.

.

PP|A (+|a) 0.70 0.01

a + −

PA|V,Z (+|v, z) 0.95 0.94 .A. 0.29 0.001

v + + − −

z + − + −

. .P

.M

Graf + TPP = Bayesovská síť 17 / 25


PZ (+) 0.002

PM|A (+|a) 0.90 0.05

a + −

Příčinné vztahy v BS

I

Hrany v tomto grafu odpovídají příčinným (kauzálním) vzahům mezi uzly.

I

Příčinnost = vodítko pro návrh grafu BS

I

Graf BS ale obecně nemusí odpovídat příčinnosti!

18 / 25


.V

.Z .. A

.P

.M

Sestavení grafu BS

Algoritmus pro sestavení grafu BS bez znalosti příčinných vztahů 1. Zvol pořadí příznaků X1 , X2 , . . . Xn /* šťastná volba ⇒ kompaktní síť */ 2. Pro i = 1 až n: přidej Xi jako uzel do grafu vyber co nejmenší množinu rodičů z X1 , . . . Xi−1 tak, že PXi |rodiče(Xi ) = PXi |X1 ,...Xi−1 vyveď hrany z rodičů do Xi

19 / 25


Příklad sestavení grafu BS Bez znalosti příčinných vztahů volíme např. pořadí M, P, A, V, Z .M

.P

.. A

.V

.Z

žádné rodiče PP|M = PP ? Ne, M musí být rodičem. PA|P,M = PA|P nebo PA|P,M = PA|M nebo PA|P,M = PA ? Ne, M i P musí být rodiči. PV|A,P,M = PV ? Ne. PV|A,P,M = PV|A ? Ano. PZ|V,A,P,M = PZ ? Ne. PZ|V,A,P,M = PZ|A ? 20 / 25


Ekvivalentní BS Dvě BS. Různé grafy, různé TPP. Reprezentují totéž sdružené rozdělení. .V

.Z

.M

.. A .P

.P .. A

.M

.V

.Z

I

Graf sestaven na základě příčinných vztahů.

I

Graf sestaven obecným algoritmem.

I

TPP vyžadují 1 + 1 + 4 + 2 + 2 = 10 čísel.

I

TPP vyžadují 1 + 2 + 4 + 2 + 4 = 13 čísel.

21 / 25


Odvozování z BS Příklad: Volá Pepa, Marie nevolá, nevíme, zda zvonil alarm, zemětřesení není. Jaká je pravděpodobnost vloupání? PV,Z,P,M (+, −, +, −) PZ,P,M (−, +, −) ∑ = αPV,Z,P,M (+, −, +, −) = α PV,Z,A,P,M (+, −, a, +, −)

PV|Z,P,M (+|−, +, −) =

a∈{+,−}

dosadíme dle PV,Z,A,P,M = PP|A PM|A PA|V,Z PV PZ ∑ = αPV (+)PZ (−) PP|A (+|a)PM|A (−|a)PA|V,Z (a|+, −) a∈{+,−}

= α · 0.001 · 0.998 · (0.90 · 0.30 · 0.94 + 0.05 · 0.99 · 0.06) ≈ α · 0.00025

22 / 25


Odvozování z BS (pokr.) Analogicky PV|Z,P,M (−|−, +, −) ∑ = αPV (−)PZ (−)

PP|A (+|a)PM|A (−|a)PA|V,Z (a|−, −)

a∈{+,−}

= α · 0.999 · 0.998 · (0.90 · 0.30 · 0.001 + 0.05 · 0.99 · 0.999) ≈ α · 0.00520 Protože PV|Z,P,M (+|−, +, −) + PV|Z,P,M (−|−, +, −) = 1, máme: PV|Z,P,M (+|−, +, −) =

α · 0.00025 ≈ 0.046 α · 0.00025 + α · 0.00520

Apriorní pravděpodobnost vloupání je 0.001, ale volá-li soused Pepa a není zemětřesení, vzroste na 0.046. 23 / 25


Příklad využití BS: Diagnóza poruchy auta

[Russel, Norvig]

červený uzel: počáteční příznak, zelené: testovatelné příznaky, oranžové: ‘opravitelné’ příznaky, šedivé: skryté příznaky zjednodušují graf, snižují potřebný počet parametrů. battery age

battery dead battery meter

lights

24 / 25

fanbelt broken

alternator broken

no charging

battery flat

oil light

no oil

gas gauge

no gas

car won’t start


fuel line blocked

dipstick

starter broken

Příklad využití BS: Pojištění auta

[Russel, Norvig]

SocioEcon Age GoodStudent ExtraCar Mileage

RiskAversion

VehicleYear SeniorTrain MakeModel

DrivingSkill DrivingHist

Antilock DrivQuality

Airbag

Ruggedness

CarValue HomeBase

Accident Theft OwnDamage

Cushioning

MedicalCost

25 / 25

OwnCost

OtherCost

LiabilityCost

PropertyCost


AntiTheft

Vytěžování dat, cvičení 3: EM algoritmus Radomír Černoch



1 / 13

EM algoritmus

Ochutnávka EM

I

http://demonstrations.wolfram.com/ ExpectationMaximizationForGaussianMixtureDistributions

I

Bishop: Pattern Recognition and Machine Learning, str. 437

2 / 13

EM algoritmus

Gaussovské rozdělení I

Hustota pravděpodobnosti: (

1

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

x−µ √ 2 σ2

)2

Odhad parametrů: I

Střední hodnota z aritmetického průměru: 1∑ µ ˆ= xn N n=1 N

I

Variance ze střední kvadratické odchylky: 1∑ (xn − µ ˆ)2 N n=1 N

σ ˆ2 =

Vygenerujte si v Matlabu náhodné vzorky z P(x | µ = 10, σ 2 = 5) pomocí normpdf a zpětně odhadněte jejich parametry, tentokrát použití bez mean a var. 3 / 13

EM algoritmus

Směs Gaussovských rozdělení (GMM)

I

Mějme 2 normální rozdělení: P(x | µm = 180, σm = 10) a P(x | µz = 170, σz = 8) s následujícímí směsnými koeficienty: P(m) = 0.9 a P(z) = 0.1

I

Výsledná hustota pravděpodobnosti: P(x | ...) = P(m) · P(x | µm , σm ) + P(z) · P(x | µz , σz )

Zkuste si z této distribuce vygenerovat vzorky pomocí randn a zobrazit je v histogramu pomocí hist.

4 / 13

EM algoritmus

GMM: Odhady parametrů

I

Dokáži ze své výšky odhadnout, jestli jsem muž nebo žena?

I

Souhlasíte s následující úvahou: P(m | x) ∼ P(m) · P(x | µm , σm )? (pro P(z | x) obdobně)

I

Aby platil součet P(m | x) + P(z | x) = 1, používá se normalizační konstanta (jmenovatel je stejný pro P(m | x) i P(z | x)): P(m | x) =

I

P(m) · P(x | µm , σm ) P(m) · P(x | µm , σm ) + P(z) · P(x | µz , σz )

Zjistěte, zda platí P(m | x = 160) > P(z | x = 160) (pozn.: normalizační konstantu lze pro účel porovnání vynechat).

5 / 13

EM algoritmus

EM algoritmus

Inicializace Expectation Maximization

6 / 13

EM algoritmus

EM: 3 fáze 1. Inicializace náhodně nastaví parametry P(m), P(z), µm , σz , ... 2. Expectation přiřadí instance oběma normálním rozdělením. 3. Maximization odhadne parametry rodělení na základě přiřazení z E fáze:

µz ← σz2 ← P(z) ← I

Nz =

∑N

7 / 13

n=1

N 1 ∑ P(z | xn ) xn Nz

1 Nz 1 N

n=1 N ∑

P(z | xn ) (xn − µz )2

n=1 N ∑

P(z | xn )

n=1

P(z | xn ) . . . normalizační konstanta

EM algoritmus

Úloha (1/3)

1. Seznamte se s daty v souboru height.csv, který obsahuje tělesnou výšku vzorku 100 lidí, Američanů ve věku mezi 20 a 29 lety. Kromě výšky lidí (1. sloupec) obsahují data i jejich pohlaví (2. sloupec). Každý záznam tvoří jeden řádek tabulky. 2. Prohlédněte si dokumentaci k přiložené funkci dataplot(data), která načtená data vykreslí do grafu: >> data = csvread('height.csv'); dataplot(data);

8 / 13

EM algoritmus

Úloha (2/3)

4. Implementujte EM algoritmus pro maximum-likelihood optimalizaci parametrů směsi dvou normalních rozdělení. Popis algoritmu naleznete ve třetí přednášce (str. 21-24). I

I

Vstupem algorimu bude první sloupec načtených dat (druhý sloupec můžete použít pro zpětnou kontrolu). Vhodně zvolte počáteční parametry obou rozložení. Pokud Váš algoritmus vrátí matici 2 × 2 ve formátu ) ( µženy σženy params = µmuži σmuži můžete pro vykreslení obou rozdělení použít příkaz >> dataplot(data, params);

9 / 13

EM algoritmus

Úloha (3/3) 5. Vyvořte protokol o rozsahu cca. 1 strany A4, která shrne Vaši práci a analyzuje výsledky. Doporučený obsah: I

I

I

I

I

grafy obou gaussovských rozložení v několika počátečních iteracích algoritmu a stav po konvergenci počet iterací algoritmu (dochází-li k velkému rozptylu hodnot pro různá počáteční nastaveni, spustťe algoritmus několikrat a výsledek vyhodnoťte statisticky) diskuze o vlivu prvotního přiřazení parametrů na jejich výsledné hodnoty. rozbor, zda lze mezi výškou mužů a žen pozorovat statisticky významný rozdíl (využijte druhý sloupec vstupních dat a závěry z předchozích bodů) poznámky k implementaci

6. Protokol odevzdejte do upload systému do 10.10.2011. Zdrojové kódy není nutné do systému nahrávat, ale můžete být požádáni o jejich ukázku a předvedení během následujícího cvičení. 10 / 13

EM algoritmus

Úloha: Možný výsledek (1/3) Iteration 25

Frequency in population [%]

40 35 30 25 20 15 10 5 0 140

150

11 / 13

160 170 180 Height of a person [cm]

EM algoritmus

190

200



40 35 30 25 20 15 10 5 0 140

150

12 / 13


EM algoritmus

190

200



40 35 30 25 20 15 10 5 0 140

150

13 / 13


EM algoritmus

190

200

Vytěžování dat, cvičení 4: Bayesovské sítě Radomír Černoch



1 / 14

Bayesovské sítě

Modelový příklad

Consider the following situation. You have a new burglar alarm installed at home. It is fairly reliable at detecting a burglary, but also responds on occasion to minor earthquakes.1 You also have two neighbors, John and Mary, who have promised to call you at work when they hear the alarm. John always calls when he hears the alarm, but sometimes confuses the telephone ringing with the alarm and calls then, too. Mary, on the other hand, likes rather loud music and sometimes misses the alarm altogether. Given the evidence of who has or has not called, we would like to estimate the probability of a burglary. Zdroj: AIMA

1 This example is due to Judea Pearl, a resident of Los Angeles; hence the acute interest in earthquakes. 2 / 14

Bayesovské sítě

Krok 1: Vytvoření struktury Bayesovské sítě

I

Mějme 4 náhodné proměnné: Burglary, Earthquake, Alarm, JohnCalls, MaryCalls.

I

Základní princip: Šipka vede od X do Y právě tehdy když X má přímý vliv na Y.

I

Navrhněte vazby mezi proměnnými!

I

Applet: http://www.cs.cmu.edu/~javabayes/

3 / 14

Bayesovské sítě

Krok 1: Správná odpověď

4 / 14

Bayesovské sítě

Krok 3: Zadání parametrů

5 / 14

Bayesovské sítě

Krok 3: Data

I I

P(Burglary = true) = 1% P(Earthquake = true) = 0.2%

I

P(Alarm = true | Burglary = true, Earthquake = true) = 95% P(Alarm = true | Burglary = true, Earthquake = false) = 94% P(Alarm = true | Burglary = false, Earthquake = true) = 29%

I

P(Alarm = true | Burglary = false, Earthquake = false) = 0.1%

I

P(JohnCalls = true | Alarm = true) = 90%

I

P(JohnCalls = true | Alarm = false) = 5%

I

P(MaryCalls = true | Alarm = true) = 70%

I

P(MaryCalls = true | Alarm = false) = 1%

I I

6 / 14

Bayesovské sítě

Krok 4: Evidence

7 / 14

Bayesovské sítě

Krok 4: Výpočet podm. p.

8 / 14

Bayesovské sítě

Krok 5: Ruční výpočet (1/3)

P(MaryCalls | Earthquake = true) = P(M | E) =

P(M, E)

= = =

∑∑∑ A

B

J

A

B

J

∑∑∑ ∑

= ···

=

P(E)

∑

(2)

P(B) · P(E) · P(A | B, E) · P(M | A) · P(J | A)

(3)

∑∑ B

P(M | A)

A

=

P(E)

∑

∑ X

P(X) = 1;

∑ X

P(M | A)

∑

P(B) · P(A | B, E) ·

∑

Bayesovské sítě

∑

P(J | A)

(4) (5)

J

P(B) · P(A | B, E)

B

P(X, Y) = P(Y); ∑ ∑ Y f(X) · g(Y) = f(X) Y f(Y).

P(M, E) = P(E) · P(M | E);

9 / 14

P(B) · P(E) · P(A | B, E) · P(J | A)

J

B

A

Tahák:

(1)

P(B, E, A, M, J)

P(M | A)

A

P(M, E) = ... P(E)

(6)

Krok 5: Ruční výpočet (2/3) P(MaryCalls | Earthquake = true) =

= =

P(E = true) ∑

P(M | A)

A

=

∑

∑ A

∑

∑ P(M | A) B P(B) · P(A | B, E = true) P(E = true)

P(B) · P(A | B, E = true)

B

P(M | A)

A

∑( B

)

true B= false

0.01 0.99

true B= false

true 0.0095 0.2871 

 =

∑ A

=

∑

∑  P(M | A)  B

 P(M | A) 

A

10 / 14

P(M, E = true) = P(E = true)

  ×  A

A true 0.2966

false  0.7034

Bayesovské sítě

A true B= false 

false   0.0005  0.7029

true 0.95 0.29

 false   0.05  0.71

Krok 5: Ruční výpočet (2/3)

=

∑ A

=

=

=

 P(M | A) ×  

A true 0.2966

 false  0.7034 

  A false   ×  true false  true 0.01  M= 0.2966 0.7034 A false 0.99   A ∑  true false    true 0.22245 0.007034  M= A false 0.08898 0.696366 ( ) true 0.229484 M= false 0.785346 A

∑  

11 / 14

true 0.75 0.30

Bayesovské sítě

Úloha: Popis dat

Alt Yes Yes No Yes Yes No No No No Yes No Yes

Bar No No Yes No No Yes Yes No Yes Yes No Yes

Fri No No No Yes Yes No No No Yes Yes No Yes

12 / 14

Hun Yes Yes No Yes No Yes No Yes No Yes No Yes

Pat Some Full Some Full Full Some None Some Full Full None Full

Bayesovské sítě

Price 3 1 1 1 3 2 1 2 3 3 1 1

Rain No No No No No Yes Yes Yes No No No No

Res Yes No No No Yes Yes No Yes Yes Yes No No

Type French Thai Burger Thai French Italian Burger Thai Italian Italian Thai Burger

Est 0-10 >30 0-10 10-30 >30 0-10 0-10 0-10 >30 >30 0-10 >30

Wait Yes No Yes Yes No Yes No Yes No No No Yes

Úloha: Legenda 1. Alt: whether there is a suitable alternative restaurant nearby. 2. Bar: whether the restaurant has a comfortable bar area to wait in. 3. Fri: true on Fridays and Saturdays. 4. Hun: whether we are hungry. 5. Pat: how many people are in the restaurant (values are None, Some, and Full). 6. Price: the restaurant’s price range ($, $$, $$$). 7. Rain: whether it is raining outside. 8. Res: whether we made a reservation. 9. Type: the kind of restaurant (French, Italian, Thai, or Burger). 10. Est: the wait estimated by the host (0-10 minutes, 10-30, 30-60, >60). 11. Wait: whether we decided to wait 13 / 14

Bayesovské sítě

Úloha: Zadání 1. Navrhněte strukturu Bayesovské sítě. Snažte se respektovat kauzální vazby mezi náhodnými proměnnými. 2. Z dodaných dat vypočtěte podmíněné pravděpodobnosti, které odpovídají struktuře BS. 3. Pomocí počítače vypočtěte následující pravděpodobnosti z Bayesovské sítě: 3.1 3.2 3.3 3.4

P(Est) P(Est | Pat) P(Rain) P(Rain | Fri)

4. Podmíněnou pravděpodobnost 4 vypočtěte navíc ručně. 5. Porovnejte výsledky 1 s 2 a dále 3 s 4. Ovlivňuje dotazovanou proměnou informace o proměnné v podmínce? 6. Proč nelze počítat podmíněné pravděpodobnosti přímo z dat a je dobré využít „mezikrok“ podmíněných pravděpodobností BS? 14 / 14

Bayesovské sítě

Základy vytěžování dat

Recommend Documents