Információs entrópia

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 17-én felülvizsgált verziótól ; az ellenőrzések 35 szerkesztést igényelnek .

Az információs entrópia egy bizonyos rendszer bizonytalanságának mértéke (a statisztikai fizikában vagy az információelméletben ), különösen az elsődleges ábécé bármely karakterének megjelenésének kiszámíthatatlanságát . Ez utóbbi esetben információvesztés hiányában az entrópia számszerűen megegyezik a továbbított üzenet szimbólumonkénti információmennyiségével .

Például egy orosz nyelvű mondatot alkotó betűsorozatban különböző betűk különböző gyakorisággal jelennek meg , így egyes betűk előfordulási bizonytalansága kisebb, mint másoké. Ha figyelembe vesszük, hogy egyes betűkombinációk (jelen esetben a -edik rendű entrópiáról beszélnek, lásd alább ) nagyon ritkák, akkor a bizonytalanság még tovább csökken. $n$

Formális definíciók

Az információs bináris entrópiát információvesztés hiányában a Hartley képlet segítségével számítjuk ki :

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

ahol az ábécé ereje, az információ mennyisége az üzenet egyes szimbólumaiban. Egy olyan valószínűségi változó esetén , amely független véletlenszerű értékeket vesz fel valószínűségekkel ( ), a Hartley-képlet Shannon képletévé változik: $N$ $én$ $x$ $n$ $x_{i}$ $p_{i}$ $i=1,...,n$

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

Ezt a mennyiséget átlagos üzenetentrópiának is nevezik . A mennyiséget parciális entrópiának nevezzük , amely csak az -e állapotot jellemzi. $H_{i}=-\log _{2}{p_{i))$ $én$

Így a rendszer entrópiája a számmal rendelkező állapot (esemény) összes relatív előfordulási gyakoriságának ellentétes előjelű összege , megszorozva azok bináris logaritmusával [1] . Ez a diszkrét véletlenszerű események definíciója formálisan kiterjeszthető a valószínűségi sűrűségeloszlás által adott folytonos eloszlásokra , azonban az eredményül kapott funkcionális tulajdonságai kissé eltérőek lesznek (lásd a differenciálentrópiát ). $x$ $én$

Általában az entrópia definíciójában a logaritmus alapja 1-nél nagyobb lehet (mivel egy csak egy karakterből álló ábécé nem közvetíthet információt); a logaritmus alapjának megválasztása határozza meg az entrópia mértékegységét. A kettes számrendszeren alapuló információs rendszerek esetében az információs entrópia (valójában információ) mértékegysége egy kicsit . A matematikai statisztika problémáiban kényelmesebb lehet a természetes logaritmus használata , amely esetben az információs entrópia egysége nat .

Shannon meghatározása

Claude Shannon azt javasolta, hogy az információnyereség egyenlő az elveszett bizonytalansággal, és meghatározta a mérési követelményeket:

az intézkedésnek folyamatosnak kell lennie; azaz a valószínűségi érték értékének kis mértékű változása kis nettó változást kell, hogy okozzon a függvényben;
abban az esetben, ha minden opció (a fenti példában betűk) egyformán valószínű, az opciók (betűk) számának növelése mindig növelje a függvény értékét;
két lépésben lehessen választani (példánkban betűk), amelyben a végeredmény függvényének értéke a köztes eredmények függvényeinek összege legyen.[ tiszta ]

Ezért az entrópiafüggvénynek teljesítenie kell a feltételeket $H$

$H(p_{1},\;\ldots ,\;p_{n})$ mindenre definiált és folyamatos , ahol mindenre és . (Ez a függvény csak a valószínűségi eloszlástól függ, az ábécétől nem.) ${\displaystyle p_{1},\dotsc ,p_{n))$ $p_{i}\in [0,\;1]$ $i=1,\dotsc ,n$ $p_{1}+\dotsb +p_{n}=1$
Pozitív egész számok esetén a következő egyenlőtlenségnek teljesülnie kell: $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}}\jobbra)}_{{n+1}}.$
Pozitív egész számok esetén, ahol , az egyenlőségnek teljesülnie kell $kettős}$ $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}}}\jobbra)}_{{b_{i}}}.$

Shannon megmutatta [2] , hogy az egyetlen függvény, amely megfelel ezeknek a követelményeknek, az

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

ahol egy pozitív állandó (és valójában csak az entrópia mértékegységének kiválasztásához szükséges; ennek az állandónak a megváltoztatása egyenértékű a logaritmus alapjának megváltoztatásával). $K$

Shannon megállapította, hogy az információforrásra alkalmazott entrópia mérése ( ) meg tudja határozni azt a minimális sávszélesség-követelményt, amely az információ kódolt bináris számok formájában történő megbízható továbbításához szükséges. A Shannon-képlet levezetéséhez ki kell számítani az ábrán szereplő "információmennyiség" matematikai elvárását az információforrásból. A Shannon-entrópia mértéke egy valószínűségi változó megvalósulásának bizonytalanságát fejezi ki. Az entrópia tehát az üzenetben található információ és az információ azon része közötti különbség, amely pontosan ismert (vagy nagymértékben megjósolható) az üzenetben. Példa erre a nyelv redundanciája – egyértelmű statisztikai minták vannak a betűk, egymást követő betűpárok, hármasok stb. megjelenésében (lásd Markov-láncok ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

A Shannon-entrópia meghatározása a termodinamikai entrópia fogalmához kapcsolódik . Boltzmann és Gibbs sokat dolgozott a statisztikai termodinamikán, ami hozzájárult az „entrópia” szó elfogadásához az információelméletben. Kapcsolat van a termodinamikai és az információs entrópia között. Például Maxwell démona is szembeállítja az információ termodinamikai entrópiáját, és tetszőleges mennyiségű információ megszerzése egyenlő az entrópia elvesztésével.

Definíció saját információk felhasználásával

Egy valószínűségi változó entrópiája úgy is meghatározható, hogy először bevezetjük egy véges számú értékű valószínűségi változó eloszlásának koncepcióját: [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

és saját információ :

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

Ekkor az entrópiát a következőképpen határozzuk meg:

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

Információs entrópia mértékegységei

Az információmennyiség és az entrópia mértékegysége a logaritmus alapjától függ: bit , nat , trit vagy hartley .

Tulajdonságok

Az entrópia egy adatforrás valószínűségi modelljének kontextusában meghatározott mennyiség . Például egy érme feldobásának entrópiája van:

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

bit per dobás (feltéve, hogy ez független), és a lehetséges állapotok száma egyenlő: lehetséges állapotok (értékek) („fejek” és „ farok ”).

2^{1}=2

Egy olyan forrás esetében, amely csak "A" betűkből álló karakterláncot generál, az entrópia nulla: , és a lehetséges állapotok száma: a lehetséges állapot (érték) ("A"), és nem függ a karakterlánc alapjától. logaritmus. Ez is olyan információ, amelyet szintén figyelembe kell venni. Példa azokra a memóriaeszközökre , amelyek nullával egyenlő entrópiájú biteket használnak, de egy lehetséges állapotnak megfelelő információmennyiséggel , azaz nem egyenlő nullával, a ROM -ban rögzített adatbitek , amelyekben minden bitnek csak egy lehetséges . állapot . $-\sum _{{i=1}}^{\infty }\log _{2}1=0$ $2^{0}=1$

Így például empirikusan megállapítható, hogy egy angol szöveg entrópiája karakterenként 1,5 bit, ami a különböző szövegeknél eltérő lehet. Az adatforrás entrópiájának mértéke az adatelemenkénti bitek átlagos bitszámát jelenti, amely az (adat)titkosításukhoz szükséges információvesztés nélkül, optimális kódolással.

Előfordulhat, hogy egyes adatbitek nem hordoznak információt. Például az adatstruktúrák gyakran redundáns információkat tárolnak, vagy azonos szakaszokkal rendelkeznek, függetlenül az adatszerkezetben lévő információktól.
Az entrópia mennyiségét nem mindig egész számú bitként fejezzük ki.

Matematikai tulajdonságok

Nem negativitás : . $H(X)\geqslant 0$
Korlátozottság : , ami a Jensen-féle egyenlőtlenségből következik a konkáv függvényre és . Ha az összes elem egyformán valószínű, . $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$
Ha független, akkor . $X,\;Y$ $H(X\cdot Y)=H(X)+H(Y)$
Az entrópia az elemek valószínűségi eloszlásának felfelé konvex függvénye.
Ha az elemek valószínűségi eloszlása azonos, akkor . $X,\;Y$ $H(X)=H(Y)$

Hatékonyság

Az ábécé valószínűségi eloszlása messze nem egyenletes . Ha az eredeti ábécé karaktereket tartalmaz, akkor összehasonlítható egy „optimalizált ábécével”, amelynek a valószínűségi eloszlása egyenletes. Az eredeti és az optimalizált ábécé entrópiájának aránya az eredeti ábécé hatékonysága , amely százalékban is kifejezhető. Az eredeti szimbolikus ábécé hatékonysága annak -ári entrópiájaként is meghatározható. $n$ $n$ $n$

Az entrópia korlátozza a lehetséges legnagyobb veszteségmentes (vagy majdnem veszteségmentes) tömörítést, amely egy elméletileg tipikus halmaz vagy a gyakorlatban Huffman -kódolás , Lempel-Ziv-Welch kódolás vagy aritmetikai kódolással valósítható meg .

Változatok és általánosítások

b -ár entrópia

Általában egy kezdeti ábécével és diszkrét valószínűség- eloszlással rendelkező forrás b - ár entrópiáját ( ahol b 2, 3, …) a következőképpen adjuk meg: ${\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}.

Különösen, amikor , a szokásos bináris entrópiát kapjuk, bitben mérve . -val tritekben mért hármas entrópiát kapunk (egy tritnek van egy információforrása három kiegyenlíthető állapottal). Amikor natsban mért információt kapunk . $b=2$ $b=3$ $b=e$

Feltételes entrópia

Ha az ábécé karaktereinek sorrendje nem független (például a franciában a „q” betű után szinte mindig „u”, a „peredovik” szó után pedig a szovjet újságokban a „gyártás” ill. Általában a „munka” követését követték, az ilyen szimbólumok sorozatát hordozott információ mennyisége (és ebből következően az entrópia) kisebb. A feltételes entrópiát használják az ilyen tények figyelembevételére.

Az elsőrendű feltételes entrópia (hasonlóan az elsőrendű Markov-modellhez ) az ábécé entrópiája, ahol ismertek az egyik betű megjelenésének valószínűsége a másik után (vagyis a kétbetűs kombinációk valószínűsége). :

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

ahol az előző karaktertől függő állapot és az adott valószínűség , amely az előző karakter volt. $én$ $p_{i}(j)$ $j$ $én$

Például az orosz nyelvhez "e" betű nélkül [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

A privát és általános feltételes entrópiák tekintetében az információveszteség teljes mértékben le van írva a zajos csatornán történő adatátvitel során. Ehhez úgynevezett csatornamátrixokat használnak . A forrásoldali veszteség leírásához (azaz az elküldött jel ismert), vegye figyelembe annak feltételes valószínűségét , hogy a vevő megkapja a szimbólumot , feltéve, hogy a szimbólumot elküldték . Ebben az esetben a csatornamátrix a következő formájú: $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})$
…	…	…	…	…	…	…
$a_m$	$p(b_{1}\mid a_{m})$	$p(b_{2}\mid a_{m})$	…	$p(b_{j}\mid a_{m})$	…	$p(b_{m}\mid a_{m})$

Az átló mentén elhelyezkedő valószínűségek a helyes vétel valószínűségét írják le, és bármely sor elemeinek összege 1-et ad. Az egy átvitt jelre eső veszteségeket a részleges feltételes entrópia segítségével írjuk le: $a_{i}$

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

Az összes jel átviteli veszteségének kiszámításához a teljes feltételes entrópiát használjuk:

H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).

$H(B\közép A)$ a forrás oldali entrópiát jelenti, a vevőoldali entrópiát hasonlóan tekintjük: ehelyett , mindenhol feltüntetve (a karakterlánc elemeit összegezve megkaphatja a , az átló elemei pedig azt a valószínűséget, hogy pontosan a karakter az elküldésre került, vagyis a helyes átvitel valószínűsége). $H(A\közép B)$ $p(b_{j}\mid a_{i})$ $p(a_{i}\mid b_{j})$ $p(a_{i})$

Kölcsönös entrópia

A kölcsönös entrópia vagy egyesülési entrópia az összekapcsolt rendszerek entrópiájának kiszámítására szolgál (a statisztikailag függő üzenetek együttes megjelenésének entrópiája), és jelölése , ahol az adót és - a vevőt jellemzi. $H(AB)$ $A$ $B$

Az átvitt és vett jelek kapcsolatát közös eseményvalószínűségek írják le , és csak egy mátrix szükséges a csatorna jellemzőinek teljes leírásához: $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})$

Egy általánosabb esetben, amikor nem egy csatorna van leírva, hanem a kölcsönható rendszerek egésze, a mátrixnak nem kell négyzetesnek lennie. A számmal rendelkező oszlop összes elemének összege adja a számot , a számot tartalmazó sor összege a, a mátrix összes elemének összege pedig 1. Az események együttes valószínűsége és a szorzatként kerül kiszámításra. a kezdeti és feltételes valószínűség: $j$ $p(b_{j})$ $én$ $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}).

A feltételes valószínűségeket a Bayes-képlet állítja elő . Így minden adat rendelkezésre áll a forrás és vevő entrópiák kiszámításához:

H(A)=-\sum _{i}\left(\sum _{j}p(a_{i}b_{j})\log \sum _{j}p(a_{i}b_{j} )\jobb),

H(B)=-\sum _{j}\left(\sum _{i}p(a_{i}b_{j})\log \sum _{i}p(a_{i}b_{j} )\jobb).

A kölcsönös entrópiát az összes mátrixvalószínűség egymás utáni sor (vagy oszlop) összegzésével számítják, szorozva a logaritmusukkal:

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

A mértékegység bit / két karakter, ez azért van, mert a kölcsönös entrópia leírja a bizonytalanságot egy karakterpárra: küldött és fogadott. Egyszerű átalakításokkal azt is megkapjuk

H(AB)=H(A)+H(B\mid A)=H(B)+H(A\mid B).

A kölcsönös entrópiának megvan az információ teljességének a tulajdonsága - minden figyelembe vett mennyiség megszerezhető belőle.

Történelem

1948- ban, miközben az információ zajos kommunikációs csatornán keresztül történő racionális továbbításának problémáját vizsgálta, Claude Shannon forradalmi valószínűségi megközelítést javasolt a kommunikáció megértéséhez, és megalkotta az entrópia első valóban matematikai elméletét . Szenzációs ötletei gyorsan alapul szolgáltak két fő terület kidolgozásához: az információelmélethez , amely a valószínűség és az ergodikus elmélet fogalmát használja az adat- és kommunikációs rendszerek statisztikai jellemzőinek tanulmányozására, valamint a kódoláselméletet , amely elsősorban algebrai és geometriai eszközöket használ. hatékony kódok kidolgozására.

Az entrópia fogalmát mint a véletlenszerűség mértékét Shannon vezette be " A Mathematical Theory of Communication " című tanulmányában, amely két részben jelent meg a Bell System Technical Journal 1948-ban.

Jegyzetek

↑ Ez az ábrázolás kényelmes a bináris formában bemutatott információkkal való munkavégzéshez; általában a logaritmus alapja eltérő lehet.
↑ Shannon, Claude E. A kommunikáció matematikai elmélete (meghatározatlan) // Bell System Technical Journal. - 1948. - július ( 27. évf . 3. sz .). - S. 419 . - doi : 10.1002/j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Előadások az információelméletről - MIPT , 2007. - P. 16. - 214 p. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. A távirati üzenetek átviteli sebességének növelésének lehetőségéről. - M .: Electrosvyaz, 1958. - No. 1. - S. 68-69.

Lásd még

Differenciálentrópia (entrópia a folytonos eloszláshoz)
kölcsönös tájékoztatás
Entrópia kódolás
Markov lánc
Kullback-Leibler távolság

Linkek

Shannon Claude E. A kommunikáció matematikai elmélete archiválva 1998. január 31-én a Wayback Machine -nél
Korotaev S.M. Az entrópia és az információ egyetemes természettudományi fogalmak .

Irodalom

Shannon K. Információelmélettel és kibernetikával foglalkozik. - M . : Szerk. külföldi lit., 2002.
Volkenshtein M. V. Entrópia és információ. - M .: Nauka, 2006.
Tsymbal VP Az információ és a kódolás elmélete. - K . : Vishcha Iskola, 2003.
Martin, Nathaniel FG & England, James W. Az entrópia matematikai elmélete. - Cambridge University Press, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Az entrópia fogalmának kidolgozása és alkalmazása. — M .: Nauka, 1967. — 280 p.
Martin N., England J. Az entrópia matematikai elmélete. — M .: Mir, 1988. — 350 p.
Khinchin A. Ya. Az entrópia fogalma a valószínűségszámításban // Előrelépések a matematikai tudományokban . - Orosz Tudományos Akadémia , 1953. - V. 8. , no. 3. cikk (55) bekezdése . - S. 3-20 . (Orosz)
Bruluen L. Tudomány és információelmélet. - M. , 1960.
Viner N. Kibernetika és társadalom. - M. , 1958.
Wiener N. Kibernetika vagy Irányítás és kommunikáció az állatokban és a gépekben. - M. , 1968.
Petrusenko L. A. Az anyag önmozgása a kibernetika tükrében. - M. , 1974.
Ashby W. R. Bevezetés a kibernetikába. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Valószínűség és információ. - M. , 1973.
Volkenshtein M. V. Entrópia és információ. - M . : Nauka, 1986. - 192 p.
Verescsagin N.K., Shchepin E.V. Információ, kódolás és előrejelzés. - M. : FMOP, MTsNMO, 2012. - 238 p. - ISBN 978-5-94057-920-5 .

Szótárak és enciklopédiák

Bibliográfiai katalógusokban
BNE : XX535116 BNF : 11985913j GND : 4743861-7 J9U : 987007550784405171 LCCN : sh85044152 NDL : 01191172 NKC : ph425914