Informační entropie

Představte si dva stroje. Oba produkují zprávy v abecedě složené z písmen "A", "B", "C" nebo "D". První stroj generuje každý znak náhodně. Všechny se vyskytují s pravděpodobností 25%. Naproti tomu druhý stroj generuje symboly podle následujících pravděpodobností. Který ze strojů produkuje více informace? Claude Shannon chytře přeformuloval otázku. Jestliže máte odhadnout následující znak z každého stroje, na kolik nejméně otázek, na které je odpověď ano nebo ne, se musíme zeptat? Podívejme se na první stroj. Nejefektivnější je položit otázku, která rozdělí pravděpodobnosti na půl. Například naše první otázka - můžeme se zeptat, jestli je to jeden ze dvou znaků, například A nebo B. Je zde 50% šance, že půjde o A nebo B a 50% šance, že půjde o C nebo D. Získáním odpovědi eliminujeme polovinu možností a zbudou nám dva znaky. Oba se stejnou pravděpodobností. Jednoduše zvolíme jeden z nich. Třeba: Je to A? Po této druhé otázce budeme mít znak správně určen. Můžeme tedy říct, že neurčitost stroje je dvě otázky na znak. Nyní druhý stroj. Jako u prvního stroje se můžeme ptát na dvě otázky k určení následujícího znaku, nicméně tentokrát je pravděpodobnost každého znaku jiná, takže můžeme naše otázky položit rozdílně. Zde má A pravděpodobnost výskytu 50% a pravděpodobnost všech dalších znaků se sčítá do 50%. Můžeme tedy začít položením otázky: Jde o A? Pokud ano, máme hotovo. Pouze jedna otázka v tomto případě. Jinak zbývají dva rovnocené výsledky. "D" nebo "B" a "C". Můžeme se tedy ptát: Jde o D? Pokud ano, jsme hotovi se dvěma otázkami. Jinak se musíme ptát potřetí ke zjištění, který ze zbývajících dvou symbolů to je. Na kolik otázek se v průměru zeptáme, ke zjištění znaku druhého stroje? Můžeme to pěkně vysvětlit analogií. Předpokládejme, že chceme postavit oba stroje a můžeme generovat znaky odrazem disku od kolíků do jednoho ze dvou stejně pravděpodobných směrů. Na základě toho kam disk spadne, můžeme generovat symbol. V případě prvního stroje, musíme přidat druhou úroveň pro druhý odraz, takže nám dva odrazy vygenerují čtyři stejně pravděpodobné výsledky. Na základě toho kam disk dopadne máme výstup A, B, C nebo D. Nyní druhý stroj. V tomto případě, první odraz vede buď k A, které nastane v 50% případů, nebo vede k druhému odrazu. Výstupem druhého odrazu je D, které nastane ve 25% případů nebo vede k třetímu odrazu. Ten nám dá buď B nebo C s pravděpodobností 12,5% v obou případech. Nyní to zprůměrujme. Průměrný počet odrazů je pravděpodobnost znaku A krát jeden odraz, plus pravděpodobnost znaku B krát tři odrazy, plus pravděpodobnost znaku C krát tři odrazy, plus pravděpodobnost znaku D krát dva odrazy. Což vychází na 1,75 odrazů v průměru. Povšimněte si spojení mezi otázkami typu ano/ne a odrazy. Průměrný počet otázek je roven průměrnému počtu odrazů. První stroj vyžaduje dva odrazy na vygenerování znaku, přičemž hádání neznámého symbolu vyžaduje dvě otázky. Druhý stroj potřebuje 1,75 odrazů a musíme se zeptat v průměru na 1,75 otázek. To znamená, že zeptáme-li se na 100 znaků z obou strojů, můžeme očekávat, že se zeptáme na 200 otázek pro první stroj a na 175 otázek pro druhý stroj. To znamená, že druhý stroj produkuje méně informace, protože je méně nejistoty nebo překvapení na jeho výstupu. Claude Channon nazývá měření průměrné nejistoty ENTROPIE. A používá písmeno "H" jako označení. Jednotka entropie, kterou Shannon zvolil, je založena na nejistotě hodu mincí. Nazývá ji "bit", což je ekvivalentní odrazu disku. Dostaneme stejný výsledek, při použití analogie odražení disku. Entropie nebo H je suma pravděpodobnosti každého znaku krát počet odrazů k získání tohoto znaku. Teď se podívejme na rozdíly ve vyjádření počtu odrazů obecněji. Jak jsme viděli, počet odrazů závisí na tom, jak hluboko se nacházíme ve stromu. To můžeme zjednodušit, když řekneme, že počet odrazů je roven logaritmu o základu dva z počtu výsledků v dané úrovni stromu. Počet výsledků v dané úrovni je také založen na pravděpodobnosti, kde počet výsledků v dané úrovni je roven jedna lomeno pravděpodobnost výsledku. Počet odrazů se rovná dvojkovému logaritmu z jedna lomeno pravděpodobnost znaku. Tím dostaneme konečnou rovnici. Entropie nebo-li H, je součet pravděpodobnosti každého znaku krát dvojkový logaritmus z jedna lomeno pravděpodobnost tohoto znaku. Shannon to zapisuje lehce odlišně, převrátí zlomek v logaritmu, čímž dostaneme před sumou mínus. Nicméně oba vztahy produkují stejný výsledek. Shrňme to. Entropie je maximální, když všechny výsledky jsou stejně pravděpodobné. Kdykoli se odchýlíme od stejně pravděpodobných výsledků, nebo vznikne předvídatelnost, entropie jde dolů. Základní myšlenkou je, že jestliže entropie informačního zdroje klesá, pak to znamená, že se můžeme zeptat na méně otázek k uhodnutí výsledku. Díky Shannonovi byl bit, což je jednotka entropie, přijat jako kvantitativní míra informace nebo jako míra překvapení.