Informační entropie

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. ledna 2020; kontroly vyžadují 35 úprav .

Informační entropie je mírou nejistoty určitého systému (ve statistické fyzice nebo teorii informace ), zejména nepředvídatelnosti vzhledu jakéhokoli znaku primární abecedy . V druhém případě, při absenci ztráty informace, je entropie číselně rovna množství informace na symbol přenášené zprávy.

Například v posloupnosti písmen, které tvoří větu v ruštině, se objevují různá písmena s různou frekvencí , takže nejistota výskytu u některých písmen je menší než u jiných. Pokud vezmeme v úvahu, že některé kombinace písmen (v tomto případě hovoří o entropii -tého řádu, viz níže ) jsou velmi vzácné, pak se nejistota ještě sníží. $n$

Formální definice

Informační binární entropie se při absenci ztráty informace vypočítá pomocí Hartleyho vzorce :

$i=\log _{2}N$ ,

kde je síla abecedy, je množství informací v každém symbolu zprávy. Pro náhodnou proměnnou , která nabývá nezávislých náhodných hodnot s pravděpodobnostmi ( ), se Hartleyho vzorec změní na Shannonův vzorec: $N$ $i$ $X$ $n$ $x_{i}$ $p_{i}$ $i=1,...,n$

$H(x)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}.$

Tato veličina se také nazývá průměrná entropie zprávy . Veličina se nazývá parciální entropie , která charakterizuje pouze stav -e. $H_{i}=-\log _{2}{p_{i))$ $i$

Entropie systému je tedy součet s opačným znaménkem všech relativních četností výskytu stavu (události) s číslem , vynásobený jejich binárními logaritmy [1] . Tato definice pro jednotlivé náhodné události může být formálně rozšířena na spojitá rozdělení daná rozdělením hustoty pravděpodobnosti , nicméně výsledný funkcionál bude mít mírně odlišné vlastnosti (viz diferenciální entropie ). $X$ $i$

Obecně může být základ logaritmu v definici entropie cokoli větší než 1 (protože abeceda sestávající pouze z jednoho znaku nemůže předávat informace); volba základu logaritmu určuje jednotku entropie. Pro informační systémy založené na binární číselné soustavě je měrnou jednotkou informační entropie (ve skutečnosti informace) bit . V problémech matematické statistiky může být výhodnější použít přirozený logaritmus , v takovém případě je jednotkou informační entropie nat .

Shannonova definice

Claude Shannon navrhl, že informační zisk se rovná ztracené nejistotě, a stanovil požadavky na její měření:

opatření musí být nepřetržité; to znamená, že změna hodnoty pravděpodobnosti o malou hodnotu by měla způsobit malou čistou změnu funkce;
v případě, kdy jsou všechny možnosti (písmena ve výše uvedeném příkladu) stejně pravděpodobné, zvýšení počtu možností (písmen) by mělo vždy zvýšit hodnotu funkce;
mělo by být možné provést volbu (v našem příkladu písmena) ve dvou krocích, ve kterých by hodnota funkce konečného výsledku měla být součtem funkcí mezivýsledků.[ vyčistit ]

Proto musí funkce entropie splňovat podmínky $H$

$H(p_{1},\;\ldots ,\;p_{n})$ je definován a spojitý pro všechny , kde pro všechny a . (Tato funkce závisí pouze na rozdělení pravděpodobnosti, nikoli na abecedě.) ${\displaystyle p_{1},\dotsc ,p_{n))$ $p_{i}\in [0,\;1]$ $i=1,\dotsc ,n$ $p_{1}+\dotsb +p_{n}=1$
Pro kladná celá čísla musí platit následující nerovnost: $n$ $H\underbrace {\left({\frac {1}{n)),\;\ldots ,\;{\frac {1}{n}}\right)}_{n}<H\underbrace {\left ({\frac {1}{n+1)),\;\ldots ,\;{\frac {1}{n+1}}\right)}_{{n+1}}.$
Pro kladná celá čísla , kde , musí platit rovnost $bi}$ $b_{1}+\ldots +b_{k}=n$ $H\underbrace {\left({\frac {1}{n)),\;\ldots ,\;{\frac {1}{n))\right)}_{n}=H\left({\ frac {b_{1}}{n}},\;\ldots ,\;{\frac {b_{k}}{n}}\right)+\sum _{{i=1}}^{k} {\frac {b_{i}}{n}}H\underbrace {\left({\frac {1}{b_{i}}},\;\ldots ,\;{\frac {1}{b_{ i}}}\right)}_{{b_{i}}}.$

Shannon ukázal [2] , že jediná funkce, která splňuje tyto požadavky, je

-K\součet _{{i=1}}^{n}p(i)\log _{2}p(i),

kde je kladná konstanta (a je skutečně potřeba pouze k výběru jednotky entropie; změna této konstanty je ekvivalentní změně základu logaritmu). $K$

Shannon zjistil, že měření entropie ( ) aplikované na zdroj informací může určit minimální požadavky na šířku pásma potřebné pro spolehlivý přenos informací ve formě kódovaných binárních čísel. Pro odvození Shannonova vzorce je nutné vypočítat matematické očekávání „množství informací“ obsažených na obrázku ze zdroje informací. Shannonova míra entropie vyjadřuje nejistotu realizace náhodné veličiny. Entropie je tedy rozdíl mezi informací obsaženou ve zprávě a tou částí informace, která je ve zprávě přesně známá (nebo vysoce předvídatelná). Příkladem toho je redundance jazyka – existují jasné statistické vzorce ve vzhledu písmen, dvojice po sobě jdoucích písmen, trojice atd. (viz Markovovy řetězce ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

Definice Shannonovy entropie souvisí s konceptem termodynamické entropie . Boltzmann a Gibbs udělali mnoho práce na statistické termodynamice, což přispělo k přijetí slova „entropie“ v teorii informace. Mezi termodynamickou a informační entropií existuje souvislost. Například Maxwellův démon také staví do kontrastu termodynamickou entropii informací a získání jakéhokoli množství informací se rovná ztracené entropii.

Definice pomocí vlastních informací

Je také možné určit entropii náhodné veličiny tak, že nejprve zavedeme koncept rozdělení náhodné veličiny s konečným počtem hodnot: [3] $X$

P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;n

\sum _{{i=1}}^{n}p_{i}=1

a vlastní informace :

I(X)=-\log P_{X}(X).

Potom je entropie definována jako:

H(X)=\mathbb {E} (I(X))=-\sum _{i=1}^{n}p(i)\log p(i).

Jednotky informační entropie

Jednotka měření množství informace a entropie závisí na bázi logaritmu: bit , nat , trit nebo hartley .

Vlastnosti

Entropie je veličina definovaná v kontextu pravděpodobnostního modelu pro zdroj dat . Například hod mincí má entropii:

-2\left({\frac {1}{2}}\log _{2}{\frac {1}{2}}\right)=-\log _{2}{\frac {1}{2 }}=\log _{2}2=1

bitů na hod (za předpokladu, že je nezávislý) a počet možných stavů se rovná: možným stavům (hodnotám) („hlavy“ a „ ocasy “).

2^{1}=2

Pro zdroj, který generuje řetězec sestávající pouze z písmen "A", je entropie nula: a počet možných stavů je: možný stav (hodnota) ("A") a nezávisí na bázi logaritmus. To je také informace, kterou je třeba také vzít v úvahu. Příkladem paměťových zařízení , která používají bity s entropií rovnou nule, ale s množstvím informací rovným jednomu možnému stavu , to znamená, že se nerovná nule, jsou datové bity zaznamenané v ROM , kde každý bit má pouze jeden možný stát . $-\sum _{{i=1}}^{\infty }\log _{2}1=0$ $2^{0}=1$

Například lze empiricky stanovit, že entropie anglického textu je 1,5 bitu na znak, což se bude u různých textů lišit. Stupeň entropie zdroje dat znamená průměrný počet bitů na datový prvek potřebný pro jejich (dat) šifrování bez ztráty informace, s optimálním kódováním.

Některé datové bity nemusí nést informace. Například datové struktury často ukládají redundantní informace nebo mají identické sekce bez ohledu na informace v datové struktuře.
Množství entropie není vždy vyjádřeno jako celý počet bitů.

Matematické vlastnosti

Nezápornost : . $H(X)\geqslant 0$
Omezenost : , která vyplývá z Jensenovy nerovnosti pro konkávní funkci a . Pokud jsou všechny prvky z stejně pravděpodobné, . $H(X)=-\mathop {\mathbb {E} } (\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _ {2}{\frac {1}{p_{i}}}=\sum _{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum _{ i=1}^{n}p_{i}g_{i}\right)=\log _{2}n$ $f(g_{i})=\log _{2}g_{i}$ $g_{i}={\frac {1}{p_{i}}}$ $n$ $X$ $H(X)=\log _{2}n$
Pokud nezávislá, tak . $X,\;Y$ $H(X\cdot Y)=H(X)+H(Y)$
Entropie je směrem nahoru konvexní funkce rozdělení pravděpodobnosti prvků.
Pokud mají stejné rozdělení pravděpodobnosti prvků, pak . $X,\;Y$ $H(X)=H(Y)$

Účinnost

Abeceda může mít rozdělení pravděpodobnosti, které není zdaleka jednotné . Pokud původní abeceda obsahuje znaky, pak ji lze přirovnat k „optimalizované abecedě“, jejíž rozdělení pravděpodobnosti je rovnoměrné. Poměr entropie původní a optimalizované abecedy je účinnost původní abecedy, kterou lze vyjádřit v procentech. Účinnost původní symbolické abecedy lze také definovat jako její -ary entropii. $n$ $n$ $n$

Entropie omezuje maximální možnou bezeztrátovou (nebo téměř bezeztrátovou) kompresi, kterou lze realizovat pomocí teoreticky typické sady nebo v praxi Huffmanova kódování , Lempel-Ziv-Welchova kódování nebo aritmetického kódování .

Variace a zobecnění

b -ary entropie

Obecně platí, že b - ární entropie (kde b je 2, 3, …) zdroje s počáteční abecedou a diskrétním rozdělením pravděpodobnosti , kde je pravděpodobnost ( ) je dána vztahem: ${\mathcal {S}}=(S,\;P)$ $S=\{a_{1},\;\ldots ,\;a_{n}\}$ $P=\{p_{1},\;\ldots ,\;p_{n}\},$ $p_{i}$ $a_{i}$ $p_{i}=p(a_{i})$

H_{b}({\mathcal {S)))=-\sum _{{i=1}}^{n}p_{i}\log _{b}p_{i}.

Zejména, když , dostaneme obvyklou binární entropii, měřenou v bitech . Pomocí dostaneme trinární entropii měřenou v tritech (jeden trit má informační zdroj se třemi ekvipravděpodobnými stavy). Když získáme informace měřené v natech . $b=2$ $b=3$ $b=e$

Podmíněná entropie

Není-li pořadí znaků abecedy nezávislé (např. ve francouzštině po písmenu „q“ téměř vždy následuje „u“ a za slovem „peredovik“ v sovětských novinách slovo „výroba“, resp. „práce“ byla obvykle sledována), množství informací nesoucích sled takových symbolů (a tedy i entropie) je menší. K vysvětlení takových skutečností se používá podmíněná entropie.

Podmíněná entropie prvního řádu (podobně jako Markovův model prvního řádu) je entropie pro abecedu, kde jsou známy pravděpodobnosti výskytu jednoho písmene za druhým (tj. pravděpodobnosti dvoupísmenných kombinací) :

H_{1}({\mathcal {S))=-\součet _{i}p_{i}\součet _{j}p_{i}(j)\log _{2}p_{i}(j) ,

kde je stav závislý na předchozím znaku a je daná pravděpodobnost , že byl předchozí znak. $i$ $p_{i}(j)$ $j$ $i$

Například pro ruský jazyk bez písmene „e“ [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

Pokud jde o privátní a obecné podmíněné entropie, ztráty informací jsou zcela popsány během přenosu dat v hlučném kanálu. K tomu se používají tzv. kanálové matice . Chcete-li popsat ztrátu na straně zdroje (tj. vysílaný signál je znám), zvažte podmíněnou pravděpodobnost přijetí symbolu přijímačem za předpokladu, že byl symbol odeslán . V tomto případě má kanálová matice následující tvar: $p(b_{j}\mid a_{i})$ $b_{j}$ $a_{i}$

	$b_{1}$	$b_{2}$	…	$b_{j}$	…	$b_{m}$
$a_{1}$	$p(b_{1}\mid a_{1})$	$p(b_{2}\mid a_{1})$	…	$p(b_{j}\mid a_{1})$	…	$p(b_{m}\mid a_{1})$
$a_{2}$	$p(b_{1}\mid a_{2})$	$p(b_{2}\mid a_{2})$	…	$p(b_{j}\mid a_{2})$	…	$p(b_{m}\mid a_{2})$
…	…	…	…	…	…	…
$a_{i}$	$p(b_{1}\mid a_{i})$	$p(b_{2}\mid a_{i})$	…	$p(b_{j}\mid a_{i})$	…	$p(b_{m}\mid a_{i})$
…	…	…	…	…	…	…
$dopoledne$	$p(b_{1}\mid a_{m})$	$p(b_{2}\mid a_{m})$	…	$p(b_{j}\mid a_{m})$	…	$p(b_{m}\mid a_{m})$

Pravděpodobnosti umístěné podél úhlopříčky popisují pravděpodobnost správného příjmu a součet všech prvků libovolné řady dává 1. Ztráty na přenášený signál jsou popsány pomocí částečné podmíněné entropie: $a_{i}$

H(B\mid a_{i})=-\součet _{{j=1}}^{m}p(b_{j}\mid a_{i})\log _{2}p(b_{j }\mid a_{i}).

K výpočtu ztráty přenosu všech signálů se používá celková podmíněná entropie:

H(B\mid A)=\součet _{i}p(a_{i})H(B\mid a_{i}).

$H(B\mid A)$ znamená entropii ze strany zdroje, entropie ze strany příjemce je uvažována podobně: místo toho je uvedena všude (sečtením prvků řetězce můžete získat , a prvky úhlopříčky znamenají pravděpodobnost, že přesně znak která byla přijata byla odeslána, tj. pravděpodobnost správného přenosu). $H(A\střed B)$ $p(b_{j}\mid a_{i})$ $p(a_{i}\mid b_{j})$ $p(a_{i})$

Vzájemná entropie

Vzájemná entropie nebo sjednocovací entropie je určena k výpočtu entropie propojených systémů (entropie společného výskytu statisticky závislých zpráv) a označuje se , kde charakterizuje vysílač a - přijímač. $H(AB)$ $A$ $B$

Vztah vysílaných a přijímaných signálů je popsán pravděpodobnostmi společných událostí a pro úplný popis charakteristik kanálu je zapotřebí pouze jedna matice: $p(a_{i}b_{j})$

$p(a_{1}b_{1})$	$p(a_{1}b_{2})$	…	$p(a_{1}b_{j})$	…	$p(a_{1}b_{m})$
$p(a_{2}b_{1})$	$p(a_{2}b_{2})$	…	$p(a_{2}b_{j})$	…	$p(a_{2}b_{m})$
…	…	…	…	…	…
$p(a_{i}b_{1})$	$p(a_{i}b_{2})$	…	$p(a_{i}b_{j})$	…	$p(a_{i}b_{m})$
…	…	…	…	…	…
$p(a_{m}b_{1})$	$p(a_{m}b_{2})$	…	$p(a_{m}b_{j})$	…	$p(a_{m}b_{m})$

Pro obecnější případ, kdy není popsán kanál, ale interagující systémy jako celek, matice nemusí být čtvercová. Součet všech prvků sloupce s číslem dává , součet řádku s číslem je a součet všech prvků matice je 1. Společná pravděpodobnost událostí a je vypočtena jako součin počáteční a podmíněné pravděpodobnosti: $j$ $p(b_{j})$ $i$ $p(a_{i})$ $p(a_{i}b_{j})$ $a_{i}$ $b_{j}$

p(a_{i}b_{j})=p(a_{i})p(b_{j}\mid a_{i})=p(b_{j})p(a_{i}\mid b_{ j}).

Podmíněné pravděpodobnosti jsou vytvářeny Bayesovým vzorcem . Existují tedy všechna data pro výpočet entropie zdroje a přijímače:

H(A)=-\součet _{i}\left(\součet _{j}p(a_{i}b_{j})\log \součet _{j}p(a_{i}b_{j} )\že jo),

H(B)=-\součet _{j}\left(\součet _{i}p(a_{i}b_{j})\log \součet _{i}p(a_{i}b_{j} )\že jo).

Vzájemná entropie se vypočítá postupným řádkovým (nebo sloupcovým) součtem všech pravděpodobností matic vynásobených jejich logaritmem:

H(AB)=-\součet _{i}\součet _{j}p(a_{i}b_{j})\log p(a_{i}b_{j}).

Jednotkou měření je bit / dva znaky, protože vzájemná entropie popisuje nejistotu pro dvojici znaků: odeslaný a přijatý. Jednoduchými transformacemi také získáme

H(AB)=H(A)+H(B\střed A)=H(B)+H(A\střed B).

Vzájemná entropie má vlastnost informační úplnosti – lze z ní získat všechny uvažované veličiny.

Historie

V roce 1948, když Claude Shannon zkoumal problém racionálního přenosu informací hlučným komunikačním kanálem, navrhl revoluční pravděpodobnostní přístup k pochopení komunikace a vytvořil první skutečně matematickou teorii entropie . Jeho senzační myšlenky rychle posloužily jako základ pro rozvoj dvou hlavních oblastí: teorie informace , která využívá koncept pravděpodobnosti a ergodické teorie ke studiu statistických charakteristik datových a komunikačních systémů, a teorie kódování , která využívá především algebraické a geometrické nástroje. k vývoji efektivních kódů.

Koncept entropie jako míry náhodnosti zavedl Shannon ve svém článku „ A Mathematical Theory of Communication “ , publikovaném ve dvou částech v Bell System Technical Journal v roce 1948.

Poznámky

↑ Tato reprezentace je vhodná pro práci s informacemi prezentovanými v binární formě; obecně může být základ logaritmu odlišný.
↑ Shannon, Claude E. A Mathematical Theory of Communication (nespecifikováno) // Bell System Technical Journal. - 1948. - Červenec ( roč. 27 , č. 3 ). - S. 419 . - doi : 10.1002/j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Přednášky z teorie informace - MIPT , 2007. - S. 16. - 214 s. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. O možnosti zvýšení rychlosti přenosu telegrafních zpráv. - M .: Electrosvyaz, 1958. - č. 1. - S. 68-69.

Viz také

Diferenciální entropie (entropie pro spojitou distribuci)
vzájemná informovanost
Entropické kódování
Markovský řetěz
Kullback-Leibler vzdálenost

Odkazy

Shannon Claude E. A Mathematical Theory of Communication Archived 31. ledna 1998 na Wayback Machine
Korotaev S.M. Entropie a informace jsou univerzální přírodní vědní koncepty .

Literatura

Shannon K. Pracuje na teorii informace a kybernetice. - M .: Ed. zahraniční, cizí lit., 2002.
Volkenshtein M. V. Entropie a informace. — M .: Nauka, 2006.
Tsymbal VP Teorie informace a kódování. - K .: Vishcha School, 2003.
Martin, Nathaniel FG & England, James W. Matematická teorie entropie. - Cambridge University Press, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Vývoj a aplikace konceptu entropie. — M .: Nauka, 1967. — 280 s.
Martin N., Anglie J. Matematická teorie entropie. — M .: Mir, 1988. — 350 s.
Khinchin A. Ya Koncept entropie v teorii pravděpodobnosti // Pokroky v matematických vědách . - Ruská akademie věd , 1953. - V. 8 , no. 3(55) . - S. 3-20 . (Ruština)
Brulluen L. Věda a teorie informace. - M. , 1960.
Viner N. Kybernetika a společnost. - M. , 1958.
Wiener N. Kybernetika aneb Řízení a komunikace u zvířat a strojů. - M. , 1968.
Petrušenko L. A. Samopohyb hmoty ve světle kybernetiky. - M. , 1974.
Ashby W. R. Úvod do kybernetiky. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Pravděpodobnost a informace. - M. , 1973.
Volkenshtein M. V. Entropie a informace. - M .: Nauka, 1986. - 192 s.
Vereshchagin N.K., Shchepin E.V. Informace, kódování a predikce. - M. : FMOP, MTsNMO, 2012. - 238 s. - ISBN 978-5-94057-920-5 .

Slovníky a encyklopedie

V bibliografických katalozích
BNE : XX535116 BNF : 11985913j GND : 4743861-7 J9U : 987007550784405171 LCCN : sh85044152 NDL : 01191172 NKC : ph425914