Informačná entropia

Entropia Bernoulliho pokusu ako funkcia pravdepodobnosti úspechu.

Entropia je pojem v termodynamike (pozri termodynamická entropia), štatistickej mechanike a teórii informácie. Pojmy informácia a entropia sú navzájom hlboko prepojené, aj keď trvalo mnoho rokov, kým to vývoj teórií štatistickej mechaniky a teórie informácie odhalil. Tento článok je o informačnej entropii, informačno-teoretickej formulácii entropie. Informačná entropia sa občas nazýva Shannonova entropia na počesť Clauda E. Shannona.

Pojem entropia v teórii informácie opisuje, s akou mierou náhodnosti (alebo prípadne „neistoty“) sa signál alebo náhodná udalosť vyskytuje. Alternatívny spôsob, ako sa na to pozerať, je hovoriť o tom, koľko informácie nesie signál.

Zoberme si napríklad anglický text, ktorý je zakódovaný ako reťazec písmen, medzier a interpunkčných znamienok (takže náš signál je reťazec znakov). Keďže frekvencia písmen pre niektoré znaky nie je veľmi vysoká (napr. „z“), zatiaľ čo iné písmená sú veľmi časté (napr. „e“), reťazec znakov nie je v skutočnosti taký náhodný, ako by mohol byť. Na druhej strane, keďže nemôžeme predpovedať, aký bude nasledujúci znak: je to do určitej miery „náhodné“. Entropia je miera tejto náhodnosti, ktorú navrhol Shannon vo svojom článku „A Mathematical Theory of Communication“ (Matematická teória komunikácie) z roku 1948.

Shannon ponúka definíciu entropie, ktorá spĺňa predpoklady, že:

(Poznámka: Shannon/Weaver sa odvolávajú na Tolmana (1938), ktorý zasa pripisuje Paulimu (1933) definíciu entropie, ktorú používa Shannon. Na iných miestach štatistickej mechaniky sa v literatúre uvádzajú odkazy na von Neumanna, ktorý v roku 1927 odvodil rovnakú formu entropie, takže von Neumann uprednostňoval používanie existujúceho termínu „entropia“. )

Claude E. Shannon definuje entropiu v zmysle diskrétnej náhodnej udalosti x s možnými stavmi (alebo výsledkami) 1..n ako:

To znamená, že entropia udalosti x je súčet všetkých možných výsledkov i x, súčin pravdepodobnosti výsledku i a logaritmu inverznej hodnoty pravdepodobnosti i (čo sa nazýva aj prekvapivosť i – entropia x je očakávaná hodnota prekvapivosti jeho výsledku). Tento postup môžeme použiť aj na všeobecné rozdelenie pravdepodobnosti, a nie na udalosť s diskrétnou hodnotou.

Doporučujeme:  Bočný roh

Shannon ukazuje, že každá definícia entropie, ktorá spĺňa jeho predpoklady, bude mať tvar:

kde K je konštanta (a v skutočnosti ide len o výber merných jednotiek).

Shannonova definícia entropie úzko súvisí s termodynamickou entropiou, ako ju definujú fyzici a mnohí chemici. Boltzmann a Gibbs vykonali značnú prácu v oblasti štatistickej termodynamiky, ktorá sa stala inšpiráciou pre prijatie slova entropia v teórii informácie. Medzi termodynamickou a informačnou entropiou existujú vzťahy. Podľa názoru Jaynesa (1957) by sa termodynamika mala v skutočnosti chápať ako aplikácia Shannonovej informačnej teórie: termodynamická entropia sa interpretuje ako odhad množstva ďalšej Shannonovej informácie (potrebnej na definovanie podrobného mikroskopického stavu systému), ktorá zostáva nekomunikovaná opisom výlučne v zmysle makroskopických premenných klasickej termodynamiky. (Pozri článok: MaxEnt termodynamika). Podobne Maxwellov démon obracia termodynamickú entropiu pomocou informácie; ak je však sám viazaný zákonmi termodynamiky, zbavenie sa tejto informácie presne vyvažuje termodynamický zisk, ktorý by inak démon dosiahol.

Z predchádzajúceho príkladu si všimnite nasledujúce body:

Entropia účinne obmedzuje výkonnosť najsilnejšej možnej bezstratovej (alebo takmer bezstratovej) kompresie, ktorú možno teoreticky realizovať použitím typickej množiny alebo v praxi použitím Huffmanovho, Lempelovho-Zivovho alebo aritmetického kódovania. Výkonnosť existujúcich algoritmov kompresie údajov sa často používa ako hrubý odhad entropie bloku údajov.

kde i je stav (určité predchádzajúce znaky) a je pravdepodobnosť, že je daný ako predchádzajúci znak (s).

Iný spôsob definovania funkcie entropie H (bez použitia Markovovho modelu) je dôkaz, že H je jednoznačne definovaná (ako už bolo spomenuté), ak H spĺňa podmienky 1) – 3):

1) H(p1, …, pn) je definovaná a spojitá pre všetky p1, …, pn, kde pi [0,1] pre všetky i = 1, …, n a p1 + … + pn = 1. (Poznamenajme, že funkcia závisí výlučne od rozdelenia pravdepodobnosti, nie od abecedy.)

Doporučujeme:  Naturalistický omyl

2) Pre všetky kladné celé čísla n platí, že H spĺňa

3) Pre kladné celé čísla bi, kde b1 + … + bk = n, H spĺňa

Odvodenie Shannonovej entropie

Keďže entropia bola daná ako definícia, nie je potrebné ju odvodzovať. Na druhej strane možno uviesť „odvodenie“, ktoré dáva zmysel motivácii definície, ako aj prepojeniu s termodynamickou entropiou.

Q. Ak je daná ruleta s n vreckami, na ktoré s rovnakou pravdepodobnosťou dopadne guľôčka, aká je pravdepodobnosť získania rozdelenia (A1, A2, …, An), kde Ai je počet prípadov, keď na vrecko i dopadla guľôčka, a

je celkový počet udalostí pristátia lopty?

A. Pravdepodobnosť je multinomické rozdelenie, t. j.

je počet možných kombinácií výsledkov (udalostí), ktoré zodpovedajú danému rozdeleniu, a

je počet všetkých možných kombinácií výsledkov pre súbor udalostí P.

Q. A čo je entropia?

A. Entropia rozdelenia sa získa z logaritmu Ω:

Súčty sa dajú tesne aproximovať nahradením integrálmi:

Integrál logaritmu je

Ak zmeníme Ax na px = Ax/P a zmeníme P na 1 (aby sme zmerali „skreslenie“ alebo „nerovnomernosť“ v rozdelení pravdepodobnosti vreciek pre jednu udalosť), potom

a člen (1 – n) možno vypustiť, pretože je konštantný a nezávisí od rozdelenia px. Výsledok je

Shannonova entropia je teda dôsledkom rovnice

čo súvisí s Boltzmannovou definíciou,

termodynamickej entropie.

Vlastnosti Shannonovej informačnej entropie

Vyplýva to z Jensenovej nerovnosti,

Ak rozdelíme mn výsledkov náhodného experimentu do m skupín, pričom každá skupina obsahuje n prvkov, môžeme experiment vykonať v dvoch krokoch: najprv určiť skupinu, do ktorej patrí skutočný výsledok, a potom nájsť výsledok v tejto skupine. Pravdepodobnosť, že budete pozorovať skupinu i, je qi. Podmienená distribučná funkcia pravdepodobnosti pre skupinu i je pi1/qi,…,pin/qi). Entropia

je entropia rozdelenia pravdepodobnosti podmienená skupinou i. Táto vlastnosť znamená, že celková informácia je súčtom informácie získanej v prvom kroku, Hm(q1,…, qn), a váženého súčtu entropií podmienených každou skupinou.

Doporučujeme:  Benígna detská epilepsia

Khinchin v roku 1957 ukázal, že jediná funkcia, ktorá spĺňa uvedené predpoklady, má tvar

kde k je kladná konštanta reprezentujúca požadovanú jednotku merania.

Odvodenie spojitej entropie z diskrétnej entropie: Boltzmannova entropia

Shannonova entropia je obmedzená na konečné množiny. Zdá sa, že vzorec

kde f označuje funkciu hustoty pravdepodobnosti na reálnej priamke, je analogická Shannonovej entropii, a preto ju možno považovať za rozšírenie Shannonovej entropie na oblasť reálnych čísel. Vzorec (*) sa zvyčajne označuje ako Boltzmannova entropia, spojitá entropia alebo diferenciálna entropia. Hoci analógia medzi oboma funkciami je sugestívna, treba si položiť nasledujúcu otázku: Je Boltzmannova entropia platným rozšírením Shannonovej entropie? Aby sme mohli odpovedať na túto otázku, musíme stanoviť súvislosť medzi oboma funkciami:

Chceme získať všeobecne konečnú mieru, keď veľkosť koša klesá k nule. V diskrétnom prípade je veľkosť koša (implicitná) šírka každého z n (konečných alebo nekonečných) košov, ktorých pravdepodobnosti sú označené pn. Pri zovšeobecnení na spojitú oblasť musíme túto šírku explicitne vyjadriť.

Začnite so spojitou funkciou f diskretizovanou podľa obrázka.
Ako je uvedené na obrázku, podľa vety o strednej hodnote existuje v každom koši taká hodnota xi, že

a teda integrál funkcie f možno aproximovať (v Riemannovom zmysle) takto

kde táto hranica a veľkosť zásobníka sa rovná nule, sú ekvivalentné.

a rozšírením logaritmu dostaneme

Všimnite si však, že ako , preto potrebujeme špeciálnu definíciu diferenciálnej alebo spojitej entropie:

ktorá sa, ako už bolo povedané, označuje ako Boltzmannova entropia. To znamená, že Boltzmannova entropia nie je limitou Shannonovej entropie pre n → ∞, a teda nie je mierou neurčitosti a informácie.

Tento článok obsahuje materiál zo Shannonovej entropie na PlanetMath, ktorý je licencovaný pod GFDL.