Entropia informațională

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 17 ianuarie 2020; verificările necesită 35 de modificări .

Entropia informației este o măsură a incertitudinii unui anumit sistem (în fizica statistică sau teoria informației ), în special, impredictibilitatea apariției oricărui caracter al alfabetului primar . În acest din urmă caz, în absența pierderii de informații, entropia este numeric egală cu cantitatea de informații pe simbol al mesajului transmis.

De exemplu, într-o succesiune de litere care alcătuiesc o propoziție în limba rusă, apar litere diferite cu frecvențe diferite , astfel încât incertitudinea apariției pentru unele litere este mai mică decât pentru altele. Dacă luăm în considerare că unele combinații de litere (în acest caz vorbesc despre entropia ordinului --lea, vezi mai jos ) sunt foarte rare, atunci incertitudinea scade și mai mult. $n$

Definiții formale

Entropia binară a informațiilor , în absența pierderii de informații, este calculată folosind formula Hartley :

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

unde este puterea alfabetului, este cantitatea de informații din fiecare simbol al mesajului. Pentru o variabilă aleatoare care ia valori aleatoare independente cu probabilități ( ), formula lui Hartley se transformă în formula lui Shannon: $N$ $i$ $X$ $n$ $x_{i}$ $p_{i}$ $i=1,...,n$

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

Această cantitate este numită și entropia medie a mesajului . Mărimea se numește entropie parțială , care caracterizează doar starea -e. $H_{i}=-\log _{2}{p_{i)}$ $i$

Astfel, entropia sistemului este suma cu semnul opus a tuturor frecvențelor relative de apariție a stării (evenimentului) cu numărul , înmulțită cu logaritmii lor binari [1] . Această definiție pentru evenimentele aleatoare discrete poate fi extinsă formal la distribuții continue date de distribuția densității de probabilitate , cu toate acestea, funcționarea rezultată va avea proprietăți ușor diferite (vezi entropia diferențială ). $X$ $i$

În general, baza logaritmului în definiția entropiei poate fi orice mai mare decât 1 (deoarece un alfabet format dintr-un singur caracter nu poate transmite informații); alegerea bazei logaritmului determină unitatea de entropie. Pentru sistemele informaționale bazate pe sistemul de numere binar, unitatea de măsură a entropiei informației (de fapt, informația) este un bit . În problemele de statistică matematică, poate fi mai convenabil să se folosească logaritmul natural , caz în care unitatea de entropie a informațiilor este nat .

Definiția lui Shannon

Claude Shannon a sugerat că câștigul de informații este egal cu incertitudinea pierdută și a stabilit cerințele pentru măsurarea acesteia:

măsura trebuie să fie continuă; adică o modificare a valorii probabilității cu o sumă mică ar trebui să provoace o mică modificare netă a funcției;
în cazul în care toate opțiunile (literele din exemplul de mai sus) sunt la fel de probabile, creșterea numărului de opțiuni (litere) ar trebui să crească întotdeauna valoarea funcției;
ar trebui să se poată face o alegere (litere în exemplul nostru) în doi pași, în care valoarea funcției rezultatului final să fie suma funcțiilor rezultatelor intermediare.[ clarifica ]

Prin urmare, funcția de entropie trebuie să îndeplinească condițiile $H$

$H(p_{1},\;\ldots ,\;p_{n})$ este definită şi continuă pentru toţi , unde pentru toţi şi . (Această funcție depinde doar de distribuția probabilității, nu de alfabet.) $p_{1},\dotsc ,p_{n)$ $p_{i}\în [0,\;1]$ $i=1,\dotsc ,n$ $p_{1}+\dotsb +p_{n}=1$
Pentru numere întregi pozitive , trebuie să fie valabilă următoarea inegalitate: $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}}.$
Pentru numere întregi pozitive , unde , egalitatea trebuie să fie valabilă $b_{i}$ $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}}}\dreapta)}_{{b_{i}}}.$

Shannon a arătat [2] că singura funcție care satisface aceste cerințe este

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

unde este o constantă pozitivă (și este într-adevăr necesară doar pentru a alege unitatea de entropie; modificarea acestei constante este echivalentă cu schimbarea bazei logaritmului). $K$

Shannon a stabilit că măsurarea entropiei ( ) aplicată unei surse de informații poate determina cerințele minime de lățime de bandă necesare pentru transmiterea fiabilă a informațiilor sub formă de numere binare codificate. Pentru a deriva formula Shannon, este necesar să se calculeze așteptarea matematică a „cantității de informații” conținută în figură din sursa de informații. Măsura entropiei Shannon exprimă incertitudinea realizării unei variabile aleatorii. Astfel, entropia este diferența dintre informațiile conținute într-un mesaj și acea parte a informației care este exact cunoscută (sau foarte previzibilă) în mesaj. Un exemplu în acest sens este redundanța limbii - există modele statistice clare în aspectul literelor, perechi de litere consecutive, triple etc. (vezi lanțuri Markov ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

Definiția entropiei lui Shannon este legată de conceptul de entropie termodinamică . Boltzmann și Gibbs au lucrat mult la termodinamica statistică, ceea ce a contribuit la acceptarea cuvântului „entropie” în teoria informației. Există o legătură între termodinamică și entropia informațională. De exemplu, demonul lui Maxwell contrastează, de asemenea, entropia termodinamică a informației, iar obținerea oricărei cantități de informații este egală cu entropia pierdută.

Definiție folosind informații proprii

De asemenea, este posibil să se determine entropia unei variabile aleatoare introducând mai întâi conceptul de distribuție a unei variabile aleatoare având un număr finit de valori: [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

si informatii proprii :

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

Atunci entropia este definită astfel:

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

Unități de entropie a informațiilor

Unitatea de măsură a cantității de informații și a entropiei depinde de baza logaritmului: bit , nat , trit sau hartley .

Proprietăți

Entropia este o cantitate definită în contextul unui model probabilistic pentru o sursă de date . De exemplu, aruncarea unei monede are entropie:

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

biți pe aruncare (presupunând că este independent), iar numărul de stări posibile este egal cu: stări posibile (valori) („capete” și „ cozi ”).

2^{1}=2

Pentru o sursă care generează un șir format doar din literele „A”, entropia este zero: , iar numărul de stări posibile este: starea posibilă (valoarea) („A”) și nu depinde de baza logaritm. Acestea sunt, de asemenea, informații care trebuie luate în considerare. Un exemplu de dispozitive de memorie care utilizează biți cu o entropie egală cu zero, dar cu o cantitate de informații egală cu o stare posibilă , adică nu egală cu zero, sunt biții de date înregistrați în ROM , în care fiecare bit are un singur bit posibil . stare . $-\sum _{{i=1}}^{\infty }\log _{2}1=0$ $2^{0}=1$

Deci, de exemplu, se poate stabili empiric că entropia unui text englezesc este de 1,5 biți pe caracter, care va varia pentru diferite texte. Gradul de entropie al sursei de date înseamnă numărul mediu de biți pe element de date necesar pentru criptarea lor (date) fără pierderi de informații, cu codificare optimă.

Este posibil ca unii biți de date să nu transporte informații. De exemplu, structurile de date stochează adesea informații redundante sau au secțiuni identice, indiferent de informațiile din structura de date.
Cantitatea de entropie nu este întotdeauna exprimată ca un număr întreg de biți.

Proprietăți matematice

Non-negativitate : . $H(X)\geqslant 0$
Marginire : , care rezultă din inegalitatea lui Jensen pentru funcția concavă și . Dacă toate elementele din sunt la fel de probabile, . $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$
Dacă este independent, atunci . $X Y$ $H(X\cdot Y)=H(X)+H(Y)$
Entropia este o funcție convexă în sus a distribuției de probabilitate a elementelor.
Dacă au aceeași distribuție de probabilitate a elementelor, atunci . $X Y$ $H(X)=H(Y)$

Eficiență

Alfabetul poate avea o distribuție de probabilitate care este departe de a fi uniformă . Dacă alfabetul original conține caractere, atunci poate fi comparat cu un „alfabet optimizat” a cărui distribuție de probabilitate este uniformă. Raportul dintre entropia alfabetului original și optimizat este eficiența alfabetului original, care poate fi exprimat ca procent. Eficiența alfabetului simbolic original poate fi definită și ca entropia sa -ariană. $n$ $n$ $n$

Entropia limitează compresia maximă posibilă fără pierderi (sau aproape fără pierderi) care poate fi realizată folosind un set teoretic tipic sau, în practică, codarea Huffman , codarea Lempel-Ziv-Welch sau codarea aritmetică .

Variații și generalizări

b -ar entropie

În general, entropia b - ară (unde b este 2, 3, …) a unei surse cu un alfabet inițial și o distribuție de probabilitate discretă unde este o probabilitate ( ) este dată de: ${\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}.

În special, când , obținem entropia binară obișnuită, măsurată în biți . Cu , obținem o entropie trinară măsurată în trits (un trit are o sursă de informații cu trei stări equiprobabile). Când obținem informații măsurate în nat . $b=2$ $b=3$ $b=e$

Entropia condiționată

Dacă ordinea caracterelor alfabetului nu este independentă (de exemplu, în franceză, litera „q” este aproape întotdeauna urmată de „u”, iar după cuvântul „peredovik” din ziarele sovietice, cuvântul „producție” sau „munca” era de obicei urmată), cantitatea de informații transportată de secvența unor astfel de simboluri (și, prin urmare, entropia) este mai mică. Entropia condiționată este folosită pentru a explica astfel de fapte.

Entropia condiționată de ordinul întâi (similar cu modelul Markov de ordinul întâi) este entropia pentru alfabet, unde sunt cunoscute probabilitățile de apariție a unei litere după alta (adică probabilitățile de combinații de două litere) :

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

unde este starea dependentă de caracterul anterior și este probabilitatea dată că a fost caracterul anterior. $i$ $p_{i}(j)$ $j$ $i$

De exemplu, pentru limba rusă fără litera „e” [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

În ceea ce privește entropiile condiționate private și generale, pierderile de informații sunt complet descrise în timpul transmisiei de date pe un canal zgomotos. Pentru aceasta, sunt folosite așa-numitele matrici de canale . Pentru a descrie pierderea pe partea sursă (adică semnalul trimis este cunoscut), luați în considerare probabilitatea condiționată de a primi un simbol de către receptor , cu condiția ca simbolul să fi fost trimis . În acest caz, matricea canalului are următoarea formă: $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})$

Probabilitățile situate de-a lungul diagonalei descriu probabilitatea recepției corecte, iar suma tuturor elementelor oricărui rând dă 1. Pierderile pe semnal transmis sunt descrise în termeni de entropie condiționată parțială: $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}).

Pentru a calcula pierderea de transmisie a tuturor semnalelor, se folosește entropia condiționată totală:

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

$H(B\mid A)$ înseamnă entropia din partea sursă, entropia din partea receptorului este considerată similar: în schimb , este indicată peste tot (însumând elementele șirului, puteți obține , iar elementele diagonalei înseamnă probabilitatea ca exact caracterul care a fost primit a fost trimis, adică probabilitatea transmiterii corecte). $H(A\mid B)$ $p(b_{j}\mid a_{i})$ $p(a_{i}\mid b_{j})$ $p(a_{i})$

Entropia reciprocă

Entropia reciprocă sau entropia uniune este concepută pentru a calcula entropia sistemelor interconectate (entropia apariției comune a mesajelor dependente statistic) și este notă cu , unde caracterizează emițătorul și - receptorul. $H(AB)$ $A$ $B$

Relația dintre semnalele transmise și recepționate este descrisă de probabilitățile comune ale evenimentelor și este necesară o singură matrice pentru a descrie pe deplin caracteristicile canalului: $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})$

Pentru un caz mai general, când nu este descris un canal, ci sisteme care interacționează în ansamblu, matricea nu trebuie să fie pătrată. Suma tuturor elementelor coloanei cu numărul dă , suma rândului cu numărul este , iar suma tuturor elementelor matricei este 1. Probabilitatea comună a evenimentelor și se calculează ca produs a probabilității inițiale și condiționate: $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}).

Probabilitățile condiționate sunt produse de formula lui Bayes . Astfel, există toate datele pentru calcularea entropiilor sursă și receptor:

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

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

Entropia reciprocă este calculată prin însumarea succesivă în rânduri (sau coloane) a tuturor probabilităților matricei înmulțite cu logaritmul lor:

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

Unitatea de măsură este biți / două caractere, asta pentru că entropia reciprocă descrie incertitudinea pentru o pereche de caractere: trimis și primit. Prin simple transformări, obținem și

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

Entropia reciprocă are proprietatea completității informației - toate cantitățile considerate pot fi obținute din ea.

Istorie

În 1948, în timp ce investiga problema transmiterii raționale a informațiilor printr-un canal de comunicare zgomotos, Claude Shannon a propus o abordare probabilistică revoluționară pentru înțelegerea comunicațiilor și a creat prima teorie cu adevărat matematică a entropiei . Ideile sale senzaționale au servit rapid drept bază pentru dezvoltarea a două domenii principale: teoria informației , care folosește conceptul de probabilitate și teoria ergodică pentru a studia caracteristicile statistice ale sistemelor de date și comunicații, și teoria codificării , care utilizează în principal instrumente algebrice și geometrice. pentru a dezvolta coduri eficiente.

Conceptul de entropie ca măsură a aleatoriei a fost introdus de Shannon în lucrarea sa „ A Mathematical Theory of Communication ” , publicată în două părți în Bell System Technical Journal în 1948.

Note

↑ Această reprezentare este convenabilă pentru a lucra cu informații prezentate în formă binară; în general, baza logaritmului poate fi diferită.
↑ Shannon, Claude E. A Mathematical Theory of Communication (nespecificata) // Bell System Technical Journal. - 1948. - iulie ( vol. 27 , nr. 3 ). - S. 419 . - doi : 10.1002/j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Prelegeri de teoria informației - MIPT , 2007. - P. 16. - 214 p. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. Despre posibilitatea creșterii vitezei de transmitere a mesajelor telegrafice. - M .: Electrosvyaz, 1958. - Nr. 1. - S. 68-69.

Vezi și

Entropie diferențială (entropie pentru distribuție continuă)
informare reciprocă
Codificarea entropiei
lanțul Markov
Distanța Kullback-Leibler

Link -uri

Shannon Claude E. A Mathematical Theory of Communication Arhivat la 31 ianuarie 1998 la Wayback Machine
Korotaev S.M. Entropia și informația sunt concepte universale de științe naturale .

Literatură

Shannon K. Lucrează pe teoria informației și cibernetică. - M .: Ed. străin lit., 2002.
Volkenshtein M. V. Entropie și informație. — M .: Nauka, 2006.
Tsymbal VP Teoria informațiilor și codării. - K .: Școala Vishcha, 2003.
Martin, Nathaniel FG & England, James W. Teoria matematică a entropiei. - Cambridge University Press, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Dezvoltarea și aplicarea conceptului de entropie. — M .: Nauka, 1967. — 280 p.
Martin N., Anglia J. Teoria matematică a entropiei. — M .: Mir, 1988. — 350 p.
Khinchin A. Ya. Conceptul de entropie în teoria probabilității // Advances in Mathematical Sciences . - Academia Rusă de Științe , 1953. - V. 8 , nr. 3(55) . - S. 3-20 . (Rusă)
Brulluen L. Știința și teoria informației. - M. , 1960.
Viner N. Cibernetica si societatea. - M. , 1958.
Wiener N. Cibernetica sau Controlul și Comunicarea în Animal și Mașină. - M. , 1968.
Petrushenko L. A. Auto-mișcarea materiei în lumina ciberneticii. - M. , 1974.
Ashby W. R. Introducere în cibernetică. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Probabilitate și informații. - M. , 1973.
Volkenshtein M. V. Entropie și informație. - M . : Nauka, 1986. - 192 p.
Vereshchagin N.K., Shchepin E.V. Informare, codificare și predicție. - M. : FMOP, MTsNMO, 2012. - 238 p. - ISBN 978-5-94057-920-5 .

Dicționare și enciclopedii

În cataloagele bibliografice
BNE : XX535116 BNF : 11985913j GND : 4743861-7 J9U : 987007550784405171 LCCN : sh85044152 NDL : 01191172 NKC : ph425914