Všechno, co jste chtěli vědět z teorie pravděpodobnosti, z teorie informace a …

báli jste se zeptat(1. část)

(pro potřeby přednášky Úvod do strojového učení, PFL054)

Jedinečnou funkcí statistiky je, že umožňuje vědci číselně vyjádřit nejistotu v jeho závěrech. (G. W.

Snedecor)

Statistika se těší pochybnému vyznamenání tím,

že je nejvíce nepochopeným vědním oborem.

Neznamená to však, že je nejméně známá.

Nepochopení nějaké věci totiž předpokládá, že

se o ní něco ví, nebo přinejmenším se myslí, že

se ví. O statistice však panuje všeobecné

mínění, že z každého, kdo se naučil ve škole

trochu počítat, lze bez obtíží udělat statistika

prostě tím, že se mu tak říká. (H. Levinson)

Náhodný pokusNastal jev APravděpodobnost má modelovat relativní četnost

Výsledek není předem známPravdivost tvrzení o výsledku pokusu

ZÁKLADNÍ POJMYZÁKLADNÍ POJMY

universum (diskrétní, spojité) jevjistý , jev nemožný sjednocení jevů i=1..nAi

průnik jevů i=1..nAi

jev opačný Ac = Aelementární jev

algebra A: systém podmnožin uzavřený na sjednocení, průnik, doplněk; , Anáhodný jev A A

ZÁKLADNÍ POJMYZÁKLADNÍ POJMY (POKRAČOVÁNÍ)

pravděpodobnost P reálná fce df na A A A P(A) A A,B vzájemně disjunktní P(AB)=P(A) + P(B)

PP

Klasický pravděpodobnostní prostorKlasický pravděpodobnostní prostor

konečný prostor elementárních jevů, algebra A

A A A Ac AA, B A ABA A, B A AB A

pravděpodobnost P P(A) = A (na konečné množině zavedena pravděpodobnost)

Jaká je pravděpodobnost, že při házení třemi mincemi najednou padnou právě 2 panny? = ?, A = ?, P(A) = ?

= {OOO, OOP, OPO, OPP, POO, POP, PPO, PPP}A ={PPO, POP, OPP}P(A) = 38

přechod od konečného prostoru elementárních jevů k prostoru spočetnému

Kolgomorova definice pravděpodobnosti

pravěpodobnostní prostor prostor elementárních jevů, algebra, A

A A A Ac AAi A i=1.. Ai A (Ai A i=1.. Ai A)

Kolgomorova df psti (pokračování)Kolgomorova df psti (pokračování)

P: A P (A) APPA1, A2,... vz. disjunktní množinyA,

P(i=1.. Ai ) = i=1.. P(Ai)

P = ?

SloSloženážená pravděpodobnost,pravděpodobnost, nezávislostezávislost jevů, jevů,

Jevy A, B jsou nezávislé P(A,B)=P(A)*P(B)

Složená pravděpodobnost P(A,B)

Podmíněná pravděpodobnost P(A|B) úplně závislé jevy P(A|B) = 1 závislé P(A|B) = ? nezávislé P(A|B) = P(A)

Bayesův vzorec P(A|B) = P(A,B)/ P(B)

Bayesův inverzní vzorecBayesův inverzní vzorec

P(A|B) = P(A)*P(B|A)/P(B)

NNáhodná veličinaáhodná veličina

; XX : R P[XX = x] = P({ = x] = P({ ; X() = x} P[XX = x] = x] rozdělení náhodné rozdělení náhodné veličiny veličiny XX

diskrdiskrétní, spojitáétní, spojitá

střední hodnota náhodné veličiny střední hodnota náhodné veličiny E[E[]=]= 1/ X()= xx P[X X = x]= x]

Statistik je ten, kdo s hlavou v rozpálené troubě

a s nohama v nádobě s ledem na dotaz, jak

se cítí, odpoví: "V průměru se cítím dobře.

„ (anonym)

Teorie informaceTeorie informace

TEORIE KÓDOVÁNÍ: 0 - žádné auto, 1 - domácí, 2 - zahraniční

3 - domácí a zahraničnívysílání signálů na křižovatce podle dané situacepři binárním kódování 0(00), 1(01), 2(10), 3(11)

situace

stejně pravděpodobné např. (0.25)

nestejně pravděpodobné

např. 0 (0.5), 1 (0.125), 2 (0.125), 3 (0.25)

EFEKTIVNÍ KÓDOVÁNÍ: častější zprávy kratší kód

tedy: 0(0), 1(110), 2(111), 3(10)

jednoznačně rozpoznat začátek a konec kódu

0 - žádné auto

10 - domácí i zahraniční

110 - domácí 111 - zahraniční

„Kolik“ informace získáme, známe-li výsledek pokusu?

„Jak velkou“ nejistotu přináší neznalost výsledku pokusu?

Axiomatická definice entropieAxiomatická definice entropie

entropie - míra stupně neurčitosti pokusu X

H(X) =ozn. n(p1, p2,...,pn)

1. Hodnota fce n(p1, p2,...,pn) se nezmění při libovolné permutaci čísel p1, p2,...,pn

2. Fce 2(p1, p2) je spojitá

3. n(p1, p2,...,pn) = n-1(p1+p2,...,pn) + (p1+p2) 2(p1/p1+p2, p2/p1+p2)

4. n(1/n,1/n,...,1/n) = f(n) s rostoucím n roste

výsledky pokusu X1 X2 ... Xn

pravděpodobnosti p(X1) p(X2) ... p(Xn)

ad vlastnost č. 3ad vlastnost č. 3

• n=3, H(X) = (p1,p2,p3)

I. X1, X2

II. X3

X Y,

• n=2, p(Y1) = p1+ p2 , p(X3) = p3

H(Y) = (p1+p2,p3)

Y Y´,

• n=2, p(X1) = p1/(p1+ p2),

p(X2) = p2/(p1+ p2)

H(X) H(Y)

ad vlastnost č.3ad vlastnost č.3

H(Y´) = (p1/(p1+ p2), p2/(p1+ p2))

H(X) = H(Y) + (p1+ p2) H(Y´)

(p1,p2,p3) = (p1+p2,p3) + (p1+ p2)(p1/(p1+ p2), p2/(p1+ p2))

Axiomatická definice entropieAxiomatická definice entropie (pokračování)

Jediná funkce, která splňuje podmínky 1.- 4., má tvar:(bez důkazu)

n(p1, p2,...,pn) = c(-p1logp1-p2logp2-...-pnlogpn)

(c logap = logbp, kde bc = a)

EntropieEntropie

X - diskrétní náhodná veličina

H(X) = - xF p(x)log2 p(x) (H(X) H(p))

entropie vs kódování entropie je dolní mez průměrného počtu bitů

potřebných k zakódování zprávy entropie jako míra nejistoty obsahu zprávy (s

délkou kódu nejistota roste)

Vlastnosti entropieVlastnosti entropie

H(X) 0

Hb(X) = (logba)H(X)

p,q

- xF p(x)log2 p(x) - xF p(x)log2q(x)

(Jensenova

nerovnost)

X = 1 s pravděpodobností p,X = 0 s pravděpodobností 1-p

H(p)

0,0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

1,0

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

H(p)

H(p)H(p) vs vs pp

Shannonova hraShannonova hra

“nápodoba českého textu”

česká abeceda - 42 písmen(bez rozlišení ú a ů, plus mezera)

A. urna 1 se 42 lístečky - vybírání a vkládání zpět“ďj mrgučxýďyaýweaožá”

B. urna 2 - lístečky podle četností písmen“žia ep atndi zéuořmp”

C. urny 1-42 - 42 uren s dvojicemi písmen (ci,cj), počty dle p(ci/cj)

“lí di oneprá sguluvicechupsv”

Shannonova hra - výsledkyShannonova hra - výsledky

HA HB HC

čestina 5,39 4,67 3,87

ruština 5 4,35 3,52

angličtina 4,76 4,03 3,32

němčina 4,76 4,10

Složená a podmíněná entropieSložená a podmíněná entropie

H(X,Y) – množství informace pro předpovídání výsledků obou pokusů zároveň

H(X, Y) = - xF yG p(x,y)log p(x,y)

H(Y/X) = xF p(x)H(Y/X = x) = - xF p(x) YG p(y/x)log p(y/x)

= - xF yG p(x)p(x/y)log p(y/x) = - xF yG p(x,y) log p(y/x)

H(X) H(X/Y) , H(X) + H(Y) H(X,Y)

Chain ruleChain rule

•H(X,Y) = - xF yG p(x,y) log p(x,y)

= - xF yG p(x,y) log p(x)p(y/x)

= - xF yG p(x,y) log p(x) - xF yG p(x,y)log p(y/x)

= - xF p(x)log p(x) - xF yG p(x,y)log p(y/x)

= H(X) + H(Y/X)

•H(X,Y/Z) = H(X/Z) + H(Y/X,Z)

•H(Y/X) H(X/Y) ačkoli

H(X) - H(X/Y) = H(Y) - H(Y/X)

Křížová entropieKřížová entropie

“správný” model známe/neznáme????

aproximace - jak kvalitní? Křížová entropie

H(p,q) =def - xF p(x)log q(x)

Křížová entropie na slovo (1/n)H(X) =def - (1/n) xF p(x)log q(x)

Křížová entropie jazyka H(L, q) = lim n (1/n)xF p(x)log q(x)

Relativní entropie (Kullback-Leibler vzdálenost)

0 xF p(x) log2p(x) - xF p(x) log2q(x) = H(p,q) - H(p)

xF p(x) log(p(x)/q(x)) =def D(p||q)

Vzájemná informace I(X;Y) = xF yG p(x,y)log(p(x,y)/p(x)p(y)) = = D(p(x,y) || p(x)p(y))

Perplexita Perp(X) = 2H(X)

Relativní entropie, vzájemná informace, perplexitaRelativní entropie, vzájemná informace, perplexita

Relativní entropieRelativní entropie (pokračování)

D(p||q) ... splňuje 1., ale nesplňuje 2. a 3.

např.

p(1) = 1/4, p(2) = 3/4, r(1) = r(2) = 1/2, q(1) = 3/4, q(2) = 1/4

Proto lépe: d(p,q) = (x(p(x) - q(x))2)1/2

m(X,Y)

1. m(X,Y) 0, m(X,Y) = 0 X = Y

2. m(X,Y) = m(Y,X)

3. m(X,Y) m(X,Z) + m(Z,Y)

PerplexitaPerplexita - - příkladpříklad

Předpověď dalšího slova wt na základě t-1 předchozích slov

w1w2…wt-1

H(wti/w1w2…wt-1) =

= - i=1.NP(wti/ w1w2…wt-1)log2P(wt

i/ w1w2…wt-1)

předpoklad: P(wti/ w1w2…wt-1) = 1/N

H(wti/w1w2…wt-1) = - i=1.N1/N log21/N = log2 N

Perp(wti/w1w2…wt-1) = N

Vzájemná informaceVzájemná informace vs vs entropieentropie

• I(X;Y) = x,y p(x,y) log (p(x,y)/p(x)p(y))

= x,y p(x,y) log (p(x/y)/p(x))

= - x,y p(x,y) log p(x) + x,y p(x,y) log p(x/y)

= - x p(x) log p(x) - (- x,y p(x,y) log p(x/y))

= H(X) - H(Y/X)

• I(X;Y) = H(Y) - H(X/Y)

• I(X;Y) = H(X) + H(Y) - H(Y/X)

• I(X;X) = H(X) - H(X/X) = H(X)

Diagram vzájemná informace Diagram vzájemná informace vs vs entropieentropie

H(Y/X)H(X/Y)I(Y;X)

H(X)

H(X,Y)

H(Y)

Chain ruleChain rule (pokračování)

•H(X1, X2,…,Xn) = i=1..n H(Xi/Xi-1, …,X1)

•I(X1, X2,…,Xn;Y)= i=1..n I(Xi;Y/Xi-1, …,X1)

I(X1, X2,…,Xn;Y) = H(X1, X2,…,Xn ) - H(X1, X2,…,Xn /Y)

= i=1..n H(Xi/Xi-1, …,X1) - i=1..n H(Xi/Xi-1, …,X1,Y)

= i=1..n I(Xi;Y/Xi-1, …,X1)

•D(p(x,y) q(x,y)) = D(p(x) q(x)) + D(p(y/x) q(y/x))

Všechno, co jste chtěli vědět z teorie pravděpodobnosti, z teorie informace a …

báli jste se zeptat(2. část)

(pro potřeby přednášky Úvod do strojového učení, PFL054)

Jedinečnou funkcí statistiky je, že umožňuje vědci číselně vyjádřit nejistotu v jeho závěrech. (G. W.

Snedecor)

NNáhodná veličinaáhodná veličina

náhodný jev chceme popsat

prostřednictvím některé jeho číselné

charakteristiky X(), kterou nazveme

náhodná veličina; XX : R

diskrdiskrétníétní (nabývá konečného nebo (nabývá konečného nebo

spočetného počtu hodnot), spočetného počtu hodnot), spojitáspojitá (nabývá (nabývá

všech hodnot z daného intervalu)všech hodnot z daného intervalu)

základní charakteristiky: průměr, rozptylzákladní charakteristiky: průměr, rozptyl

Diskrétní pravděpodobnostní rozdělení

(i=1 …)P[X=xi] = 1

seznam hodnot, kterých nabývá diskrétní náhodná veličina, a seznam pravděpodobností, s nimiž těchto hodnot náhodná veličina nabývá, udává diskrétní pravděpodobnostní rozdělení

Střední hodnota (průměr) diskrétní náhodné veličiny

E[X] i=1…nxi P(X=xi) ()

E[X] i=1…xi P(X=xi)

Rozptyl (variance)

popisuje velikost kolísání náhodné veličiny kolem střední hodnoty var [X] = E (X-E[X])2 (2)

Směrodatná odchylka

= var[X]

Spojitá náhodná veličina

pravděpodobnostní rozdělení je popsáno hustotou (frekvenční fcí) f(x)

Binomické rozdělení - motivace

hod mincí: panna? orel?

Jaká je pravděpodobnost p, že padne panna?

Házejme n-krát, z toho r-krát padla panna

p = r/nopakujme n hodů mincí; r´ r, p´ p

Binomické rozdělení – motivace

(pokračování)

binomické rozdělení popisuje, pro libovolnou

hodnotu r, pravděpodobnost jevu, že při n

nezávislých hodech mincí právě r-krát padne

panna za předpokladu, že pravděpodobnost

panny v jednotlivých hodech je p

Kdy binomické rozdělení?

1. výsledky pokusu se dají popsat

náhodnou veličinou X, která má dvě

možné hodnoty {0,1}

2. P(X=1) je dáno konstantou p,

nezávislou na výsledku jakéhokoli

pokusu; většinou je p neznámé – JAK

ODHADNOUT?

Binomické rozdělení Bin(n,p)n nezávislých pokusů, zdar/nezdar - prostor elementárních jevů = {0,1}n

náhodná veličina X() = (i=1 …n)i vyjadřuje počet (0,1,…n) úspěchů v n nezávislých pokusech, kdy v každém z jednotlivých pokusů je pravděpodobnost úspěchu rovna p

, =(1,2,…,n), i je počet zdarů v i-tém pokusu, p(i) = pi (1-p)(1-i)

nezávislost pokusů: p() = (i=1..n)p(i) = p i(1-p)(n- i)

pro k=(i=1 …n)i, je počet elem. jevů = n!/k!(n-k)!

P(X=k)= n!/k!(n-k)! pk(1-p)(n-k)

Binomické rozdělení: střední hodnota, rozptyl, směrodatná odchylka

E[X] = np var[X] = np(1-p) = np(1-p)

Normální rozdělení (spojité) N(, 2)

f(x) = 1/( 22)e–1/2((x-)/)2

normální rozdělení je určeno parametry (střední hodnotou) a (sm. odchylkou) a jsou konstanty, které určují polohu křivky na ose x () a její roztažení podél osy x ()

Normální rozdělení - pokračování

Jestliže náhodná veličina X vyhovuje normálnímu rozdělení, potom: P(X (a,b)) = p(x)dx E[X] = , var(X) = 2, X =

Normální rozdělení graficky

Normální rozdělení graficky - vysvětlení

jednovrcholové, symetrické okolo střední hodnotyplocha pod křivkou hustoty je rovna jednépravděpodobnost, že náhodná veličina nabude hodnot z určitého intervalu, je rovna ploše pod hustotou nad tímto intervalemnapř. pro interval s hranicí –1,96 a 1,96 má tato plocha velikost 0,95. Náhodná veličina nabývá hodnot z tohoto intervalu s 95% pravděpodobností a pouze s 5% pravděpodobností leží její hodnoty mimo uvedený interval

Průměr náhodné veličiny určuje polohu rozdělení na na číselné ose (1<2)

Směrodatná odchylka určuje tvar hustoty (1<2)

Centrální limitní věta

Statistická metodologie

Nemusíte sníst celého vola na to, abyste

poznali, že maso je tuhé. (S. Johnson)

induktivní statistika – zobecňování závěrů s udáním stupně jejich nejistoty; schopnost učit se ze zkušenostipopulace: základní soubor (výčtem/vymezením některých společných vlastností) parametr: číselná charakteristika populace

(např. průměrná výška osmiletých dětí v ČR)výběr: požadované vlastnosti se zjišťují pouze u některých prvků populace; reprezentativnost výběru; za určitých předpokladů se dají závěry z výběrů pomocí statistické indukce zobecnit na celou populaci s vyjádřením míry nejistoty zobecňovaných závěrů

populace12 osmiletých dětí výběr 6 dětí

Zkreslení odhadu

odhad: je náhodná veličina použitá pro odhad parametru populace, z které je daný vzorek vybírán zkreslení odhadu libovolného parametru p : E[X] –p nestranný odhad: E[X] –p = 0

Jak odhadnou populační průměr z výběru pomocí tzv. intervalu spolehlivosti?

populační () vs. výběrový (x´) průměr provedeme-li opakované výběr a spočítáme průměry, pak se tyto výběry budou obvykle chovat tak, jako kdyby pocházely z normálního rozdělení(bez důkazu) výběr = populace /n, kde n je rozsah výběru, výběr je směrodatná odchylka rozdělení výběrových průměrů, populace je směrodatná odchylka původního rozdělení interval místo jednoduchého bodového odhadu

Vlastnosti rozdělení výběrového průměru

Interval spolehlivosti

N% interval spolehlivosti pokrývá parametr p s pravděpodobností N

Interval spolehlivosti - pokračování

konstanta zn určuje šířku nejmenšího intervalu kolem střední hodnoty, který pokrývá N% pravděpodobností v rámci normálního rozdělení čím vyšší je koeficient spolehlivosti, tím delší – a tedy méně přesný – je výsledný interval; je potřeba najít kompromis mezi požadovanou spolehlivostí a přesností odhadu, tj. délkou intervalu

hranice spolehlivosti N%

50 68 80 90 95 98 99

konstanta zn

0,67

1,00

1,28

1,64

1,96

2,33

2,58

Pro dané N - jak určit velikost intervalu, který obsahuje N% pstí?

pro binomické rozdělení značně obtížné ALE – máme štěstí: pro dostatečně velkou množinu instancí je možné binomické rozdělení aproximovat rozdělením normálním se stejnou střední hodnotou a se stejným rozptylem (Centrální limitní věta)

Interval spolehlivosti

jestliže náhodná veličina X vyhovuje normálnímu rozdělení se střední hodnotu a směrodatnou odchylkou , potom hodnota x veličiny X padne do intervalu ±zN v N% případů

střední hodnota padne do intervalu x±zN v N% případů