Informační entropie

Entropie Bernoulliho procesu jako funkce pravděpodobnosti úspěchu.

Entropie je pojem v termodynamice (viz termodynamická entropie), statistické mechanice a teorii informací. Pojmy informace a entropie mají hluboké vazby mezi sebou, i když trvalo mnoho let, než se to projevilo ve vývoji teorií statistické mechaniky a teorie informací. Tento článek je o informační entropii, informačně-teoretické formulaci entropie. Informační entropie je příležitostně nazývána Shannonovou entropií na počest Clauda E. Shannona.

Pojem entropie v teorii informace popisuje, s jak velkou náhodností (nebo alternativně 'nejistotou') je signál nebo náhodná událost. Alternativní způsob, jak se na to podívat, je mluvit o tom, kolik informací je signálem přenášeno.

Vezměme si například nějaký anglický text, kódovaný jako řetězec písmen, mezer a interpunkce (takže náš signál je řetězec znaků). Vzhledem k tomu, že četnost písmen u některých znaků není příliš vysoká (např. 'z'), zatímco jiná písmena jsou velmi častá (např. 'e'), řetězec znaků není ve skutečnosti tak náhodný, jak by mohl být. Na druhou stranu, vzhledem k tomu, že nemůžeme předpovědět, jaký bude další znak: je do určité míry 'náhodný'. Entropie je měřítkem této náhodnosti, kterou navrhl Shannon ve své práci z roku 1948 „Matematická teorie komunikace“.

Shannon nabízí definici entropie, která splňuje předpoklady, že:

(Poznámka: Shannon/Weaver odkazují na Tolmana (1938), který zase připisuje Paulimu (1933) definici entropie, kterou používá Shannon. Jinde ve statistické mechanice literatura zahrnuje odkazy na von Neumanna, který v roce 1927 odvodil stejnou formu entropie, takže to bylo tak, že von Neumann upřednostnil použití existujícího termínu 'entropie'. )

Claude E. Shannon definuje entropii z hlediska diskrétní náhodné události x, s možnými stavy (nebo výsledky) 1..n jako:

To znamená, že entropie události x je součtem všech možných výsledků i(x) součinu pravděpodobnosti výsledku i krát log inverzní pravděpodobnosti i (což se také nazývá i's surprisal – entropie x je očekávaná hodnota překvapení jeho výsledku). Můžeme to také aplikovat na obecné rozdělení pravděpodobnosti, spíše než na událost s diskrétní hodnotou.

Shannon ukazuje, že jakákoli definice entropie splňující jeho předpoklady bude mít formu:

kde K je konstanta (a je vlastně jen volbou měrných jednotek).

Shannonova definice entropie úzce souvisí s termodynamickou entropií, jak ji definovali fyzici a mnozí chemici. Boltzmann a Gibbs odvedli značnou práci na statistické termodynamice, která se stala inspirací pro přijetí slova entropie v teorii informace. Existují vztahy mezi termodynamickou a informační entropií. Ve skutečnosti by podle Jaynese (1957) měla být termodynamika chápána jako aplikace Shannonovy teorie informace: termodynamická entropie je interpretována jako odhad množství dalších Shannonových informací (potřebných k definování detailního mikroskopického stavu systému), které zůstávají nekomunikovány popisem výhradně z hlediska makroskopických proměnných klasické termodynamiky. (Viz článek: MaxEntova termodynamika). Podobně Maxwellův démon obrací termodynamickou entropii informacemi; ale pokud je sám vázán zákony termodynamiky, zbavení se této informace přesně vyvažuje termodynamický zisk, kterého by démon jinak dosáhl.

Z předchozího příkladu si povšimněte následujících bodů:

Entropie účinně omezuje výkon nejsilnější bezztrátové (nebo téměř bezztrátové) komprese, kterou lze teoreticky realizovat pomocí typické množiny nebo v praxi pomocí Huffmanova, Lempelova-Zivova nebo aritmetického kódování. Výkon stávajících algoritmů komprese dat se často používá jako hrubý odhad entropie bloku dat.

kde i je stav (určité předcházející znaky) a je pravděpodobnost dané jako předchozí znak (s).

Další způsob, jak definovat entropickou funkci H (nepoužíváme Markovův model) je dokázat, že H je jednoznačně definováno (jak již bylo zmíněno) MFF H splňuje 1) - 3):

1) H(p1, …, pn) je definováno a spojité pro všechny p1, …, pn kde pi [0,1] pro všechny i = 1, …, n a p1 + … + pn = 1. (Všimněte si, že funkce závisí výhradně na rozdělení pravděpodobnosti, nikoli na abecedě.)

2) Pro všechny pozitivní celá čísla n, H splňuje

3) Pro pozitivní celá čísla bi kde b1 + … + bk = n, H vyhovuje

Odvození Shannoniny entropie

Vzhledem k tomu, že entropie byla uvedena jako definice, není třeba ji odvodit. Na druhou stranu lze uvést „odvození“, které dává smysl motivaci pro definici i souvislosti s termodynamickou entropií.

Q. Vzhledem k tomu, ruleta s n kapsy, které jsou všechny stejně pravděpodobné, že bude přistál na míč, jaká je pravděpodobnost získání rozdělení (A1, A2, …, An) kde Ai je počet krát pocket i byl přistál na a

je celkový počet míčových přistání?

A. Pravděpodobnost je multinomiální rozdělení, viz.

je počet možných kombinací výsledků (pro události), které odpovídají danému rozdělení, a

je počet všech možných kombinací výstupů pro množinu P událostí.

Q. A jaká je entropie?

A. entropie rozdělení se získává z logaritmu Ω:

Součty mohou být přiblíženy tím, že jsou nahrazeny integrály:

Integrál z logaritmu je

Změňte Ax na px = Ax/P a změňte P na 1 (pro měření „předpětí“ nebo „nerovností“, v rozdělení pravděpodobnosti kapes pro jednu událost), pak

a výraz (1 − n) může být vypuštěn, protože je konstanta, nezávislá na px distribuci. Výsledkem je

Tedy Shannonova entropie je důsledkem rovnice

která se týká Boltzmannova definice,

termodynamické entropie.

Vlastnosti Shannonovy informační entropie

V návaznosti na Jensenovu nerovnost,

Rozdělíme-li mn výsledky náhodného experimentu do m skupin s každou skupinou obsahující n prvků, můžeme experiment provést ve dvou krocích: nejprve určit skupinu, do které náleží skutečný výsledek; poté najít výsledek v této skupině. Pravděpodobnost, že budete pozorovat skupinu i, je qi. Podmíněná funkce rozdělení pravděpodobnosti pro skupinu i je pi1/qi,...,pin/qi). entropie

je entropie pravděpodobnostního rozdělení podmíněného skupinou i. Tato vlastnost znamená, že celková informace je součtem informací získaných v prvním kroku, Hm(q1,..., qn), a váženým součtem entropií podmíněných každou skupinou.

Khinchin v roce 1957 ukázalo, že jedinou funkcí splňující výše uvedené předpoklady je na formě

kde k je kladná konstanta představující požadovanou měrnou jednotku.

Odvození kontinuální entropie z diskrétní entropie: Boltzmannova entropie

Shannonova entropie je omezena na konečné množiny. Zdá se, že vzorec

kde f označuje hustotu pravděpodobnosti funkce na reálné přímce, je analogická s Shannonovou entropií a mohla by být tedy považována za rozšíření Shannonovy entropie na doménu reálných čísel. Vzorec (*) je obvykle označován jako Boltzmannova entropie, spojitá entropie nebo diferenciální entropie. Ačkoli analogie mezi oběma funkcemi je sugestivní, je třeba položit následující otázku: je Boltzmannova entropie platným rozšířením Shannonovy entropie? Pro odpověď na tuto otázku musíme vytvořit spojení mezi oběma funkcemi:

Chceme získat obecně konečnou míru, protože velikost koše jde k nule. V diskrétním případě je velikost koše (implicitní) šířka každého z n (konečných nebo nekonečných) košů, jejichž pravděpodobnosti jsou označeny pn. Když zobecňujeme spojitou doménu, musíme tuto šířku explicitně vyjádřit.

Chcete-li to udělat, začněte s spojitou funkcí f diskrétní, jak je znázorněno na obrázku. Jak je znázorněno na obrázku, podle věty o střední hodnotě existuje hodnota xi v každém koši taková, že

a tak integrál funkce f lze aproximovat (v Riemannian smyslu) podle

kde tento limit a velikost koše jde na nulu jsou ekvivalentní.

a rozšíření logaritmu, máme

Ale na vědomí, že jako , Proto potřebujeme speciální definici diferenciální nebo spojité entropie:

který je, jak již bylo řečeno, označován jako Boltzmannova entropie. To znamená, že Boltzmannova entropie není limitem Shannonovy entropie pro n → ∞ a není tedy měřítkem nejistoty a informace.

Tento článek obsahuje materiál ze Shannonovy entropie na PlanetMath, který je licencován pod GFDL.