Nejistota Vlastnosti Podmíněná entropie Informace Závěr Teorie kódování - Kapitola 1 - Entropie Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 14. února 2023 • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky Q Entropie a její vlastnosti • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií Q Podmíněná entropie • Definice podmíněné entropie • Vlastnosti podmíněné entropie Q Informace • Motivace • Charakterizace • Vzájemná informace § Závěr • Shrnutí Nejistota Vlastnosti Podmíněná entropie Informace Závěr O Nejistota • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky ) Entropie a její vlastnosti • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace Shrnutí Fl Uvažme následující tvrzení. A Výsledek běhu mezi dvěma rovnocennými závodníky je méně nejistý než výsledek běhu mezi šesti rovnocennými závodníky. Fl Uvažme následující tvrzení. A Výsledek běhu mezi dvěma rovnocennými závodníky je méně nejistý než výsledek běhu mezi šesti rovnocennými závodníky. B Výsledek rulety je více nejistý než vrh kostkou. Fl Uvažme následující tvrzení. A Výsledek běhu mezi dvěma rovnocennými závodníky je méně nejistý než výsledek běhu mezi šesti rovnocennými závodníky. B Výsledek rulety je více nejistý než vrh kostkou. C Výsledek vrhu ideální kostkou je více nejistý než výsledek vrhu falešnou kostkou. Fl Uvažme následující tvrzení. A Výsledek běhu mezi dvěma rovnocennými závodníky je méně nejistý než výsledek běhu mezi šesti rovnocennými závodníky. B Výsledek rulety je více nejistý než vrh kostkou. C Výsledek vrhu ideální kostkou je více nejistý než výsledek vrhu falešnou kostkou. Fl Uvažme následující tvrzení. A Výsledek běhu mezi dvěma rovnocennými závodníky je méně nejistý než výsledek běhu mezi šesti rovnocennými závodníky. B Výsledek rulety je více nejistý než vrh kostkou. C Výsledek vrhu ideální kostkou je více nejistý než výsledek vrhu falešnou kostkou. Zřejmě s výše uvedenými tvrzeními lze okamžitě souhlasit. Obtížné však bude definovat, co je to vlastně nejistota. Fl Uvažme následující tvrzení. A Výsledek běhu mezi dvěma rovnocennými závodníky je méně nejistý než výsledek běhu mezi šesti rovnocennými závodníky. B Výsledek rulety je více nejistý než vrh kostkou. C Výsledek vrhu ideální kostkou je více nejistý než výsledek vrhu falešnou kostkou. Zřejmě s výše uvedenými tvrzeními lze okamžitě souhlasit. Obtížné však bude definovat, co je to vlastně nejistota. Podívejme se na dvě různé náhodné veličiny X aY. Nechť P(X = 0) P P(X 1) = 1 - A a P{Y = 100) pricmz 0 < p < 1. P P(Y 200) = 1 - p, □ - = Nejistota Vlastnosti Podmíněná entropie Informace Závěr Zřejmě by nám definice nejistoty měla zajistit, že X a Y jsou stejně nejisté. Tedy nejistota X a tedy i Y by měla být funkcí pouze pravděpodobnosti p. Tato vlastnost nejistoty musí být rozšiřitelná i na náhodné proměnné, které nabývají více než dvou hodnot. Tedy: Nejistota náhodné proměnné Z, která nabývá hodnoty a, s pravděpodobností p/5 (1 < / < n), je funkcí pouze pravděpodobností p1,..., pn. Nejistota Vlastnosti Podmíněná entropie Informace Závěr O Nejistota • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie 9 Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace Shrnutí Nejistota Vlastnosti Podmíněná entropie Informace Závěr Defi Proto značíme takovouto funkci jako H(p1,..., pn), přičemž předpokládáme splnění následujících přirozených podmínek: (A1) H(p-|,..., pn) je maximální, když p-| = p2 = ... = pn = 1 /n. (A2) Pro každou permutaci tt na {1,..., n} platí W(Pi, . . . ,pn) = H{Ptt^)i • • • iPirin))- Tedy H je symetrická funkce svých argumentů, tj. její výsledek nezávisí na pořadí. (A3) H(p1,..., pn) > 0 a rovnost nastává právě tehdy, když p,- = 1 pro nějaké /. Nejistota má tedy vždy nezápornou hodnotu a je nulová právě tehdy, když je jakákoliv náhoda vyloučena. (A4) H(pu...,pn,0) = H(p!,...,Pn). Nejistota vrhu šestibokou ideální kostkou je tatáž jako nejistota vrhu sedmibokou kostkou, u které je nemožné aby padla 7, ale ostatní případy jsou si rovnocenné. (A5) Výsledek běhu mezi dvěma závodníky je méně nejistý než výsledek běhu mezi více závodníky. (A6) H(p-|,..., pn) je spojitá funkce svých parametrů. Malé změny na vstupu dají malé změny na výstupu. Nejistota Vlastnosti Podmíněná entropie Informace Závěr (A7) Jsou-li rn, n e N, pak H' 1 1 = H 1 1 + H ( n n m • n m • nj \m m Tato podmínka říká, že nejistota vrhu m • n-stranné kostky je obsažena ve vrhu m-stranné kostky následovaná vrhem n-stranné kostky, a je rovna součtu individuálních nejistot. (A8) Nechť p = & + • • • + pm a q = qÁ + • • • + qn, ph q} jsou nezáporné. Jsou-li p a q kladná čísla, p + q = 1, pak platí H(p!,.., p.77, Qi,..., qn) = H(p, Q)+p • H(p! /p,..., pm/p) +q- H(qi/q,...,qn/q). Představme si, že máme n + m uchazečů na místo v konkurzu - z toho je m mužů a n žen, s pravděpodobnostmi p,, Qy vítězství v konkurzu. Pak nejistota výsledku konkurzu je nejistota, že vyhraje muž nebo žena plus vážený součet, nejistot výhry mezi muži a ženami. Nejistota Vlastnosti Podmíněná entropie Informace Závěr sa O Nejistota • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky O I f> • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace Shrnutí Nejistota Vlastnosti Podmíněná entropie Informace Závěr Věta 1.1 Buď H(p-|,..., pn) funkce definovaná pro každé přirozené číslo n a pro všechny hodnoty p-i,..., pn tak, že p, > 0 a n /=1 Pokud H splňuje axiómy (A1)-(A8), pak platí H(Pi,p2,...,Pn) = -A^P/c • logp/c k (1.1) kde X je libovolná kladná konstanta a sumuje se přes všechna k taková,že pk > 0. Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve MA Nechť H splňuje axiómy (A1)-(A8). Definujme (1) g(n) = H(1 /n,..., 1 /rí) pro n e N. Z (A7) pak g(nK) = g(n) + g(nk-1) Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve MA Nechť H splňuje axiómy (A1)-(A8). Definujme (1) g(n) = H(1 /n,..., 1 /rí) pro n e N. Z (A7) pak g(nk) = g{ri) + g{nk~^) a tedy (2) g{nk) = k ■ g(n). Buď dále r,seN-{1},neNam= m(n, r, s) e N tak, že Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve MA Nechť H splňuje axiómy (A1)-(A8). Definujme (1) g(n) = H(1 /n,..., 1 /rí) pro n e N. Z (A7) pak g(nk) = g{ri) + g{nk~^) a tedy (2) g{nk) = k ■ g(n). Buď dále r,seN-{1},neNam= m(n, r, s) e N tak, že (3) rm 0 a pí H-----h P/v = 1, a to indukcí podle N. Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve Z (6) víme, že (7) platí pro N = 2 a triviálně platí pro N = 1 z (A3). Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve Z (6) víme, že (7) platí pro N = 2 a triviálně platí pro N = 1 z (A3). Předpokládejme, že (7) platí pro N a uvažujme H(p!,..., p/v+1). Položme p = ^ + • • • + pN, q = p/v+i. Případ p = 0 je jasný, předpokládejme tedy, že p > 0 a použijme (A8). Z (6) víme, že (7) platí pro N = 2 a triviálně platí pro A/ = 1 z (A3). Předpokládejme, že (7) platí pro N a uvažujme H(p!,..., p/v+1). Položme p = p1 + • • • + pN, q = p/v+i. Případ p = 0 je jasný, předpokládejme tedy, že p > 0 a použijme (A8). Máme pak =o Hta,..., Pa,+1 ) = H(AQ)+p.H(^...,^)+S^Í(T) A/ = -A • p • Inp - A • Q • In g + p • (-A) • ^ — In /=1 P z indukčního předpokladu. Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve Upravíme-li poslední rovnost na tvar n H(pA,..., p/v+1) = -A-(p-ln p+P/v+1 -In pA/+1 + pr(ln p/-ln p)) /=1 a vzpomeneme-li si, že J^-, p, = p, obdržíme hledanou rovnost A/+1 H(p1,..., p/v+1) = -A • p/ • In p,-. /=1 Nejistota Vlastnosti Podmíněná entropie Informace Závěr oty Fl Na základě výše uvedené věty pak definujeme Definice 1 Buď X náhodná proměnná s konečným oborem hodnot s odpovídajícími pravděpodobnostmi p1, p2,..., pn. Pak definujeme nejistotu neboli entropii náhodné veličiny X jako H{X) = -Y,Pk'\°š2Pk, (1- k kde suma se bere pouze přes ta k, pro která je pk > 0. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Definice Charakterizace nejistoty Ekvivalentní definice nejistoty Poznámka 1.2 Nadále budeme vždy (bez újmy na obecnosti) předpokládat, že pro všechny členy pravé strany (1.2) jsou pravděpodobnosti pk nenulové. Poznámka 1.3 Podmínky (A1)-(A8) odpovídají axiomům pro entropii navrženým Shannonem. Poznámka 1.4 ■ Entropii náhodné veličiny X můžeme rovněž interpretovat jakožto střední hodnotu náhodné proměnné log2 ^kq. Tedy H{X) = E(log2 = - Pk • log2 Pk- (1.3) u 1 i|j Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Definice Charakterizace nejistoty Ekvivalentní definice nejistoty Příklad 1.5 Nechť Pak X = 1 s pravděpodobností p 0 s pravděpodobností ~\ - p. H(X) = -p\og2p- (1 - p) log2(1 - p) (1.4) (1.5) Cvičení 1.6 o Který dostih má větší entropii: ten, ve kterém je sedm žokejů, tři z nich vyhrají s pravděpodobností ^ a čtyři z nich s pravděpodobností g nebo dostih, ve kterém je 8 žokejů s dvěma koni s pravděpodobností výhry \ a šest koní s pravděpodobností výhry ^ ? Cvičení 1.6 o Který dostih má větší entropii: ten, ve kterém je sedm žokejů, tři z nich vyhrají s pravděpodobností ^ a čtyři z nich s pravděpodobností g nebo dostih, ve kterém je 8 žokejů s dvěma koni s pravděpodobností výhry \ a šest koní s pravděpodobností výhry ^ ? O Ověřte, že výše definovaná funkce entropie splňuje podmínky (A1)-(A8). Příklad 1.7 • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky Q Entropie a její vlastnosti • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace Zaver • Shrnutí Nejistota Vlastnosti Podmíněná entropie Informace Závěr oru nice Sčítání en Fl Řekli jsme, že pro náhodnou proměnnou X s konečným oborem hodnot a s pravděpodobnostmi p1,..., pn tak, že X)P/ = 1 ap/>0(1 0 a D(p||q) = 0, pokud p = q. 9 Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky Q Entropie a její vlastnosti • Entropie náhodného vektoru 9 Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace Shrnutí □ t3 Věta 2.3 Jsou-li XaY náhodné proměnné s konečným oborem hodnot, platí pak H{X, Y)Hog2(r/-sy) ij £fH°S2 = Y) > - dle předchozího lemmatu Nejistota Vlastnosti Podmíněná entropie Informace Závěr nice Sčítání en uKaz ve Odtud pak H(X) + H(Y) = -^tij-log^n-Sj) > - £fH°S2 = Y) dle předchozího lemmatu. Rovnost nastane právě tehdy, když r, • Sj — tjj. Ale to je právě podmínka nezávislosti X aY. Jednoduchým rozšířením této metody lze dokázat: H(Xi,...,Xn)4) = - p(x = ak\A)logP(X = ak\A). /c=1 Úplně stejně, je-li Y jiná náhodná proměnná nabývající hodnot bk (1 < k < m), definujeme podmíněnou entropii náhodné proměnné X určenou náhodnou proměnnou Y jako H{X\Y) = Y^H{X\Y = bj)P{Y = bj). i Úplně stejně, je-li Y jiná náhodná proměnná nabývající hodnot bk (1 < k < m), definujeme podmíněnou entropii náhodné proměnné X určenou náhodnou proměnnou Y jako H{X\Y) = Y^H{X\Y = bj)P{Y = bj). i Považujeme H{X\Y) za entropii náhodné proměnné X určenou jistou hodnotou Y zprůměrovanou přes všechny hodnoty, jichž může / nabývat. Zcela triviální důsledky definic jsou: H{X\X) = 0, (3.1) H(X\ Y) = H(X) jsou-li X a V nezávislé. (3.2) Příklad 3.1 Buď X náhodná proměnná získaná vrháním ideální kostky. Buď dále Y jiná náhodná proměnná určená tímtéž experimentem, přičemž Y se rovná 1, je-li vržená hodnota lichá a O v ostatních případech. Protože kostka je ideální, platí H(X) = log 6, H{ Y) = log 2 a H(X\ Y) = log 3. Příklad 3.1 Buď X náhodná proměnná získaná vrháním ideální kostky. Buď dále Y jiná náhodná proměnná určená tímtéž experimentem, přičemž Y se rovná 1, je-li vržená hodnota lichá a O v ostatních případech. Protože kostka je ideální, platí H(X) = log 6, H{ Y) = log 2 a H(X\ Y) = log 3. Jsou-li U a V náhodné vektory, přirozeně rozšíříme definici podmíněné entropie následovně W(U|V) = E H(UIV = vv)p(v = vv)> <3-3) i přičemž se sčítá, jako obvykle, přes (konečný) obor hodnot vy tak, že odpovídající pravděpodobnost je kladná. • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky • Entropie náhodného vektoru 9 Horní hranice entropie • Sčítání entropií Q Podmíněná entropie • Definice podmíněné entropie • Vlastnosti podmíněné entropie 9 Motivace • Charakterizace • Vzájemná informace □ <3 ► < -1 Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Jako první příklad, jakým způsobem entropie H(U|V) měří nejistotu o U obsaženou ve V, dokážeme: H(U|V) = 0 právě tehdy, když U = gr(V) pro nějakou funkci g. (3-4) Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Jako první příklad, jakým způsobem entropie H(U|V) měří nejistotu o U obsaženou ve V, dokážeme: H(U|V) = 0 právě tehdy, když U = gr(V) pro nějakou funkci g. (3-4) Důkaz. Pravá strana z definice podmíněné entropie je součet konečného počtu nezáporných veličin. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Jako první příklad, jakým způsobem entropie H(U|V) měří nejistotu o U obsaženou ve V, dokážeme: H(U|V) = 0 právě tehdy, když U = gr(V) pro nějakou funkci g. (3-4) Důkaz. Pravá strana z definice podmíněné entropie je součet konečného počtu nezáporných veličin. Tudíž, aby byla nulová, potřebujeme H(U|V = vy) = 0 pro všechna j. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmí Vlastnosti podmíněné entropie Jako první příklad, jakým způsobem entropie H(U|V) měří nejistotu o U obsaženou ve V, dokážeme: H(U|V) = 0 právě tehdy, když U = gr(V) pro nějakou funkci g. (3-4) Důkaz. Pravá strana z definice podmíněné entropie je součet konečného počtu nezáporných veličin. Tudíž, aby byla nulová, potřebujeme H(U|V = vy) = 0 pro všechna j. Ale opět každá z těchto nezáporných veličin je nulová právě tehdy, když U je jednoznačně určená V. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entropie Vlastnosti podmíněné entropie - řetězcové pravidlo Poněkud více nám dává následující výsledek, který matematicky vyjadřuje ideu, že naše definice podmíněné entropie X při daném Y korektně měří zbývající nejistotu. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entropie Vlastnosti podmíněné entropie - řetězcové pravidlo Poněkud více nám dává následující výsledek, který matematicky vyjadřuje ideu, že naše definice podmíněné entropie X při daném Y korektně měří zbývající nejistotu. Pro každou dvojici náhodných proměnných X aY, které nabývají pouze konečné množiny hodnot, platí H(X, Y) = H(Y) + H(X\Y). Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entropie Vlastnosti podmíněné entropie - řetězcové pravidlo Poněkud více nám dává následující výsledek, který matematicky vyjadřuje ideu, že naše definice podmíněné entropie X při daném Y korektně měří zbývající nejistotu. Věta 3.2 Pro každou dvojici náhodných proměnných X aY, které nabývají pouze konečné množiny hodnot, platí H(X, Y) = H(Y) + H(X\Y). H(X) H(Y) H(X:Y) Bez ztráty na obecnosti lze předpokládat, že X a Y nabývají pouze celočíselných hodnot a, kde to bude nutné, že Pij = P(X = i,Y = j). Nejistota Vlastnosti Podmíněná entropie Informace Závěr ti podmíněné entr uKaz ve Bez ztráty na obecnosti lze předpokládat, že X a Y nabývají pouze celočíselných hodnot a, kde to bude nutné, že PiJ = P{X = i,Y = j). Nyní H{X,Y) = -^^P{X = i,Y = j)\ogP{X = i,Y = j) i j ] P(X = i,Y = y)logP(X = /| V = y)P(V = y) / j ^ Pij\ogP(X = i\Y = j)-YYl Pff'°9p(y = D i j i j Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve ;ti podmíněné entn Tedy H(X,Y) = -J2iJ2jPij\OQP(X = i\Y=j)-j:ij:jpij\ogP(Y=j) = ~ E/ Ey P{X = i\Y = j)P{ Y = y)logP(X = i\Y = j) + H( Y) = -EjP(Y= j) E/ P{X = i\Y = j)\ogP(X = i\Y = j) + H( Y) = Y,jP(Y = j)H(X\Y = j) + H(Y) = H{X\ Y) + H{Y), což bylo třeba dokázat. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie - řetězcové pravidlo Věta 3.3 Jsou-li U a V náhodné vektory, které nabývají pouze konečné množiny hodnot, platí H(U,V) = H(V) + H(U|V). Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie - řetězcové pravidlo Jsou-li U a V náhodné vektory, které nabývají pouze konečné množiny hodnot, platí H(U,V) = H(V) + H(U|V). Důkaz Věty 3.3: Procházíme důkazem předchozí věty, ale namísto XaY nabývajích pouze celočíselných hodnot / a j máme U a V nabývajích hodnot u, a vy-, kde u, a vy jsou zadané vektory. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Důsledek 3.4 Pro každou dvojici X a Y náhodných vektorů je H(X|Y) < H(X) a rovnost nastává právě tehdy, když X a Y jsou nezávislé. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Důsledek 3.4 Pro každou dvojici X a Y náhodných vektorů je H(X|Y) < H(X) a rovnost nastává právě tehdy, když X a Y jsou nezávislé. Důkaz Důsledku 3.4: Z Věty 3.3 máme H(X|Y) = H(X,Y)-H(Y). Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entropie Vlastnosti podmíněné entropie Pro každou dvojici X a Y náhodných vektorů je H(X|Y) < H(X) a rovnost nastává právě tehdy, když X a Y jsou nezávislé. Důkaz Důsledku 3.4: Z Věty 3.3 máme H(X|Y) = H(X,Y)-H(Y). Ale H(X|Y) + H(Y) = H(X, Y) < H(X) + H(Y), s rovností právě tehdy, když X a Y jsou nezávislé. □ s Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Pro každou dvojici X a Y náhodných vektorů je H(X|Y) < H(X) a rovnost nastává právě tehdy, když X a Y jsou nezávislé. ^^^^^^^^^^^^^^^^^^^^^^^^^^^ Důkaz Důsledku 3.4: Z Věty 3.3 máme H(X|Y) = H(X,Y) - W(Y). Ale H(X|Y) + H(Y) = H(X, Y) < H(X) + H(Y), s rovností právě tehdy, když X a Y jsou nezávislé. Tedy H(X|Y) < H(X) a rovnost nastává právě tehdy, když X a Y jsou nezávislé. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entr< Vlastnosti podmíněné entropie Cvičení 3.5 O Ukažte, že pro každou náhodnou proměnnou X platí H(X2|X) = 0, ale uveďte příklad, že H(X|X2) není vždy nulová. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Definice podmíněné entropie Vlastnosti podmíněné entropie Vlastnosti podmíněné entropie Cvičení 3.5 O Ukažte, že pro každou náhodnou proměnnou X platí H(X2|X) = 0, ale uveďte příklad, že H(X|X2) není vždy nulová. O Náhodná proměnná X nabývá celočíselných hodnot 1,..., 2N se stejnou pravděpodobností. Náhodná proměnná Y je definovaná Y = 0, je-li X sudá, ale Y je-li X lichá. Ukažte, že l = 1, H(X\ Y) = H(X) - 1, ale že H{Y\X) = 0. Nejistota Vlastnosti Podmíněná entropie Informace Závěr 11 informace 9 Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky • Entropie náhodného vektoru 9 Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie « Vlastnosti podmíněné entropie Q Informace • Motivace • Charakterizace • Vzájemná informace Fl Zdá se, že R.V.L. Hartley byl v r. 1928 první, kdo se pokusil přiřadit kvantitativní míru k pojmu informace. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Fl Zdá se, že R.V.L. Hartley byl v r. 1928 první, kdo se pokusil přiřadit kvantitativní míru k pojmu informace. Jeho myšlenky byly pak pomocí matematické statistiky a teorie pravděpodobnosti zevšeobecněny Shannonem, Wienerem a Fischerem koncem 40. let téhož století a daly základ kvantitativní teorii informace, která se zaměřovala na problémy související s množstvím informace, ale ne na problém, co to vlastně informace je. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Fl Zdá se, že R.V.L. Hartley byl v r. 1928 první, kdo se pokusil přiřadit kvantitativní míru k pojmu informace. Jeho myšlenky byly pak pomocí matematické statistiky a teorie pravděpodobnosti zevšeobecněny Shannonem, Wienerem a Fischerem koncem 40. let téhož století a daly základ kvantitativní teorii informace, která se zaměřovala na problémy související s množstvím informace, ale ne na problém, co to vlastně informace je. Naznačily však, že je třeba hledat odpověď v obsahových a kvalitativních projevech informace. Racionální příčinu tohoto pokusu můžeme částečně popsat následovně. Racionální příčinu tohoto pokusu můžeme částečně popsat následovně. Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru Q spojené jistým experimentem a předpokládejme, že funkce / je naše míra informace. Racionální příčinu tohoto pokusu můžeme částečně popsat následovně. Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru Q spojené jistým experimentem a předpokládejme, že funkce / je naše míra informace. Mají-li E1 a E2 pravděpodobnosti p^ a p2, pak můžeme argumentovat tím, že každá přirozená míra obsahu informace by měla splňovat /(PiP2) = /(Pi) + /(Pz) Racionální příčinu tohoto pokusu můžeme částečně popsat následovně. Předpokládejme, že E1 a E2 jsou dvě události v pravděpodobnostním prostoru Q spojené jistým experimentem a předpokládejme, že funkce / je naše míra informace. Mají-li E1 a E2 pravděpodobnosti p^ a p2, pak můžeme argumentovat tím, že každá přirozená míra obsahu informace by měla splňovat /(PiP2) = /(Pi) + /(P2) na základě toho, že, pro dvě nezávislé realizace experimentu, informace, pro kterou výsledky těchto experimentů dopadnou jako E1 následováno E2, by měla být součtem informací získaných provedením těchto experimentů zvlášť. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Připustíme-li, že výše uvedená rovnost má jistou platnost, a přejeme-li si mít naši míru nezápornou a spojitou v p, což jsou oba přirozené předpoklady, zbývá nám s malou alternativou definovat informaci I události E kladné pravděpodobnosti jako /(£) = -log2P(£), přičemž jsme vybrali 2 jako základ našich logaritmů, abychom zachovali soulad s moderní konvencí. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Připustíme-li, že výše uvedená rovnost má jistou platnost, a přejeme-li si mít naši míru nezápornou a spojitou v p, což jsou oba přirozené předpoklady, zbývá nám s malou alternativou definovat informaci I události E kladné pravděpodobnosti jako /(£) = -log2P(£), přičemž jsme vybrali 2 jako základ našich logaritmů, abychom zachovali soulad s moderní konvencí. Hartley původně použil logaritmy o základu 10. Někdy též mluvíme o Hartleyově míře informace. • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky j j • Entropie náhodného vektoru 9 Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie « Vlastnosti podmíněné entropie Q Informace • Motivace • Charakterizace • Vzájemná informace • Shrnutí < □ Platí totiž následující tvrzení ■ Funkce /(p), definovaná pro všechna 0 < p < 1, splňuje podmínky • /(p) > 0, pro všechna 0 < p < 1, 9 /(p • q) = /(p) + /(q) pro všechny 0 < p, g < 1 takové, že p a q jsou pravděpodobnosti navzájem nezávislých jevů, a • podmínku spojitosti vzhledem k p právě tehdy, když je tvaru Xlog2p, kde X je kladná konstanta. Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve imiii Ponecháme za cvičení ukázat, že každá funkce výše uvedeného tvaru splňuje všechny tři podmínky. Ponecháme za cvičení ukázat, že každá funkce výše uvedeného tvaru splňuje všechny tři podmínky. Abychom dokázali obrácené tvrzení, pripomeňme, že z vlastnosti /(p • q) = /(p) + l(q) máme l(pn) = nl(p) pro všechna kladná přirozená čísla n. Speciálně tedy platí /(p^) = l/(p). Ponecháme za cvičení ukázat, že každá funkce výše uvedeného tvaru splňuje všechny tři podmínky. Abychom dokázali obrácené tvrzení, pripomeňme, že z vlastnosti /(p • q) = /(p) + l(q) máme l(pn) = nl(p) pro všechna kladná přirozená čísla n. Speciálně tedy platí /(p^) = l/(p). Odtud pak máme n 1 n l(pm) = nl(pm) = -I(P) tj. platí l(pq) = ql(p) pro všechna kladná racionální čísla q. Nejistota Vlastnosti Podmíněná entropie Informace Závěr ■ á informace Ze spojitosti umocňování a funkce / máme, že pro všechna kladná reálná čísla r musí platit l(jf) = rl(p). Ze spojitosti umocňování a funkce / máme, že pro všechna kladná reálná čísla r musí platit l(jf) = r/(p). Buď nyní p libovolné, pevně zvolené číslo, 0 < p < 1. Protože každé číslo g, 0 < q < 1 lze psát ve tvaru q = plogpQ, máme pak /(?) = /(pl0^) = /(p)logpQ = /(P){^ = -Alog2Q, _ l(P) pro vhodnou kladnou konstantu A = - g2P Ze spojitosti umocňování a funkce / máme, že pro všechna kladná reálná čísla r musí platit l(jf) = r/(p). Buď nyní p libovolné, pevně zvolené číslo, 0 < p < 1. Protože každé číslo g, 0 < q < 1 lze psát ve tvaru q = plogpQ, máme pak /(?) = /(pl0^) = /(p)logpQ = /(P){^ = -Alog2Q, pro vhodnou kladnou konstantu A = -J^-. Ze spojitosti funkce / plyne /(1) = 0. Příklad 4.2 Předpokládejme, že máme zdroj, který emituje řetězec binárních číslic O a 1, každou se stejnou pravděpodobností a nezávisle pro po sobě jdoucích číslicích. Buď E událost, že prvních n číslic jsou střídavě nuly a jedničky. Pak evidentně 1 /(E) = -log2— = n a totéž platí pro každou předepsanou posloupnost číslic délky n. Příklad 4.2 Předpokládejme, že máme zdroj, který emituje řetězec binárních číslic O aJ\, každou se stejnou pravděpodobností a nezávisle pro po sobě jdoucích číslicích. Buď E událost, že prvních n číslic jsou střídavě nuly a jedničky. Pak evidentně /(E) = -log2^ = n a totéž platí pro každou předepsanou posloupnost číslic délky n. Tedy "informačně-teoretická"jednotka informace, totiž bit, odpovídá přirozeně využití slova "bit", které znamená binární číslo v současné počítačové terminologii. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Charakterizace Vzájemná informace Informace pro náhodné vektory Rozšíříme pojem informace na to, abychom pokryli náhodné proměnné a vektory následovně. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Charakterizace Vzájemná informace Informace pro náhodné vektory Rozšíříme pojem informace na to, abychom pokryli náhodné proměnné a vektory následovně. Předpokládejme, že X je náhodný vektor, který nabývá hodnoty x-i,..., xm, s pravděpodobnostmi p^...,pm. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Charakterizace Vzájemná informace Informace pro náhodné vektory Rozšíříme pojem informace na to, abychom pokryli náhodné proměnné a vektory následovně. Předpokládejme, že X je náhodný vektor, který nabývá hodnoty x-i,..., xm, s pravděpodobnostmi p^...,pm. Pak každá z elementárních událostí X = (1 < k < m) obsahuje sdruženou informaci rovnou -\og2Pk a poznamenejme, že entropie vektoru X je určena vztahem W(X) = - J2pk\og2pk = ^P/c/(X = x*), Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Charakterizace Vzájemná informace Informace pro náhodné vektory Rozšíříme pojem informace na to, abychom pokryli náhodné proměnné a vektory následovně. Předpokládejme, že X je náhodný vektor, který nabývá hodnoty x-i,..., xm, s pravděpodobnostmi p^...,pm. Pak každá z elementárních událostí X = (1 < k < m) obsahuje sdruženou informaci rovnou -\og2Pk a poznamenejme, že entropie vektoru X je určena vztahem W(X) = - J2pk\og2pk = ^P/c/(X = x*), tedy H(X) má přirozenou interpretaci jako střední hodnota informace sdružené s elementárními událostmi určenými X. • Motivace 9 Definice nejistoty • Charakterizace nejistoty a její důsledky • Entropie náhodného vektoru 9 Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie Q Informace • Motivace • Charakterizace • Vzájemná informace 9 Shrnutí < □ Nejistota Vlastnosti Podmíněná entropie Informace Závěr náhodné vektory á informace Obecněji, jsou-li X a Y dva náhodné vektory, definujeme vzájemnou informaci o X poskytnutou Y jako číslo /(X|Y) = H(X) - H(X|Y). □ <3 Nejistota Vlastnosti Podmíněná entropie Informace Závěr áhodné vektory Obecněji, jsou-li X a Y dva náhodné vektory, definujeme vzájemnou informaci o X poskytnutou Y jako číslo /(X|Y) = H(X) - H(X|Y). Jinak řečeno, /(X|Y) vyjadřuje množství nejistoty o X odstraněné Y. Nejistota Vlastnosti Podmíněná entropie Informace Závěr áhodné vektory Obecněji, jsou-li X a Y dva náhodné vektory, definujeme vzájemnou informaci o X poskytnutou Y jako číslo /(X|Y) = H(X) - H(X|Y). Jinak řečeno, /(X|Y) vyjadřuje množství nejistoty o X odstraněné Y. Zřejmě platí, že /(X|X) = H(X), /(X| Y) = 0 právě tehdy, když X a Y jsou nezávislé. Nejistota Vlastnosti Podmíněná entropie Informace Závěr áhodné vektory Obecněji, jsou-li X a Y dva náhodné vektory, definujeme vzájemnou informaci o X poskytnutou Y jako číslo /(X|Y) = H(X) - H(X|Y). Jinak řečeno, /(X|Y) vyjadřuje množství nejistoty o X odstraněné Y. Zřejmě platí, že /(X|X) = H(X), /(X| Y) = 0 právě tehdy, když X a Y jsou nezávislé. Důkaz. Výsledek plyne bezprostředně z dřívější poznámky, že H(X) = H(X|Y) právě tehdy, když X a Y jsou nezávislé. Nejistota Vlastnosti Podmíněná entropie Informace Závěr Motivace Charakterizace Vzájemná informace Vzájemná informace pro náhodné vektory H(X,Y) Poněkud udivující symetrie v / je následující výsledek, který zřejmě nemá intuitivní vysvětlení. /(X|Y) = H(X)-H(X|Y) = H(X) - [H(X, Y) - H(Y)] = H(X) + H(Y) - W(X, Y) = /(Y|X). H(X) H(Y) Nejistota Vlastnosti Podmíněná entropie Informace Závěr áhodné vektory Cvičení 4.3 O Co má větší informační obsah: posloupnost deseti písmen nad abecedou o 26 písmenech nebo posloupnost 26 číslic z množiny {0,1,. ..,9}?/"Předpokládejte, že všechny posloupnosti mají stejnou pravděpodobnost] Q Ideální kostka je vržena. Ukažte, že informace o hodnotě kostky daná znalostí, že se jedná o nesložené číslo, má velikost log21. Nejistota Vlastnosti Podmíněná entropie Informace Závěr a relativní entropie Věta 4.4 Jsou-li X a Y dva náhodné vektory s pravděpodobnostními rozděleními p = (p,-: 1 < / < m) a q = (c/y: 1 kde pq ye součinové rozdělení marginálů náhodného vektoru (X,Y)._ /(X|Y) měří odlišnost sdruženého rozdělení náhodného vektoru (X, Y) od součinového rozdělení, kterým by se vektor (X, Y) řídil, pokud by X a Y byly nezávislé. Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve Uvědomme si nejprve, že P(x,y) — PxiyQ kde px|y je pravděpodobnostní rozdělení náhodného vektoru XIY. Nejistota Vlastnosti Podmíněná entropie Informace Závěr uKaz ve Uvědomme si nejprve, že P(X,Y) — PXIY^ kde pX|Y je pravděpodobnostní rozdělení náhodného vektoru X|Y. Platí pak /(X|Y) = W(X) - H(X|Y) -Ľ/P/log2P/-Ľy^W(X|Y = yy) - E/,y (njlog2Pi - <7yP(X = x,|Y = Vy)log2P(X E/,y''/,ylog2^ = D(p(x,y)llpq) = X; Y = • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky bntropie ajeji vlastnosti • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace O Závěr • Shrnutí Shrneme-li předchozí odstavce, ukázali jsme, že nejistota a informace jsou tytéž veličiny a odstranění nejistoty je rovno podání informace. Obě veličiny jsou měřitelné matematickým pojmem entropie, který je jednoznačně definován (až na multiplikativní konstantu) veličinou H = -A^p/-logp/. Konvence si žádá, aby logaritmy byly brány o základu 2, v kterémžto případě je jednotka entropie bit. • Motivace • Definice nejistoty • Charakterizace nejistoty a její důsledky bntropie ajeji vlastnosti • Entropie náhodného vektoru • Horní hranice entropie • Sčítání entropií • Definice podmíněné entropie • Vlastnosti podmíněné entropie • Motivace • Charakterizace • Vzájemná informace O Závěr ^ Shrnutí □ ^ - = i >oq,o Nejistota Vlastnosti Podmíněná entropie Informace Závěr Shrnutí Problémy k řešení Problémy k řešení Diskžokej má slovník o kapacite 10 000 slov a pronáší 1000 slov náhodně (opakování je dovoleno). Ukažte, že informační obsah jeho 1000 slov je mnohonásobně menší než obrazovky televizního přijímače o 500 řádcích a 600 sloupcích, přičemž každý pixel nabývá jednu z 16 úrovní jasu. Problémy 1 Diskžokej má slovník o kapacite 10 000 slov a pronáší 1000 slov náhodně (opakování je dovoleno). Ukažte, že informační obsah jeho 1000 slov je mnohonásobně menší než obrazovky televizního přijímače o 500 řádcích a 600 sloupcích, přičemž každý pixel nabývá jednu z 16 úrovní jasu. O Jsou-li XaY diskrétní náhodné proměnné, které nabývají pouze konečného počtu hodnot, ukažte, že H(X+ Y\X) = H{Y\X). Ukažte, že H{g{X, Y)\X) = H{Y\X) neplatí obecně pro g : R2 R. Problémy 1 Q Je-li (X, : 1 < / < oo) posloupnost náhodných proměnných a Y je nějaká jiná náhodná proměnná, dokažte, že H(X|,..., Xn\Y) < H(X1,..., Xn+11 Y) pro každé přirozené číslo n. O Statistický přehled ženatých dvojic ukazuje, že 70% mužů mělo tmavé vlasy, 25% žen bylo blondýnek a že 80% blondýnek si bere tmavovlasé muže. Kolik informace o barvě mužových vlasů je sděleno barvou vlasů jeho ženy? O Jsou-li X, Y, Z náhodné vektory, přičemž každý z nich nabývá pouze konečně mnoha hodnot, dokažte, že H(Y|X) + H(Z|X) > H(Y,Z|X). Problémy 1 O Dokažte, že pro každý náhodný vektor Y a pro každou množinu náhodných proměnných X1,..., Xn+1 platí W(Y|X|,..., Xn) > H(Y|Xj,..., Xn+i). O Jsou-li X a Y dvě náhodné proměnné afag jsou libovolné dvě funkce, dokažte, že H{f(X),g{Y))d{X,Z). Nejistota Vlastnosti Podmíněná entropie Informace Závěr Shrnutí Problémy k řešení Problémy k řešení ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Problémy 1 © Předpokládejte, že X je náhodná proměnná nabývající hodnot v^,..., vn. Ukažte, že je-li E(X) = /i a X je náhodná proměnná s maximální entropií vzhledem k těmto omezením, pak Pj = p(x = v/} = At —av. J kde A a a jsou konstanty určené vztahy E(X) = y a Poznámka: hořejší příklad je ilustrací principu maximální entropie: jedná se o rozšíření Laplaceova principu nedostatečné příčiny; tento je často užíván ve statistické mechanice, vytváření obrazů a podobně jako je princip pro vybrání a priori distribuce vzhledem k různým omezením. Viz např. Guiasu a Shenitzer (1985).