Informationsentropi

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 januari 2020; kontroller kräver 35 redigeringar .

Informationsentropi är ett mått på osäkerheten i ett visst system (i statistisk fysik eller informationsteori ), i synnerhet oförutsägbarheten av utseendet av någon karaktär i det primära alfabetet . I det senare fallet, i frånvaro av informationsförlust, är entropin numeriskt lika med mängden information per symbol för det överförda meddelandet.

Till exempel, i en sekvens av bokstäver som utgör en mening på ryska, visas olika bokstäver med olika frekvenser , så osäkerheten om förekomsten för vissa bokstäver är mindre än för andra. Om vi tar hänsyn till att vissa kombinationer av bokstäver (i det här fallet talar de om entropin av -: e ordningen, se nedan ) är mycket sällsynta, så minskar osäkerheten ännu mer. $n$

Formella definitioner

Binär informationsentropi , i frånvaro av informationsförlust, beräknas med Hartley-formeln :

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

var är kraften i alfabetet, är mängden information i varje symbol i meddelandet. För en slumpvariabel som tar oberoende slumpmässiga värden med sannolikheter ( ), förvandlas Hartleys formel till Shannons formel: $N$ $i$ $x$ $n$ $x_{i}$ $pi}$ $i=1,...,n$

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

Denna kvantitet kallas också för den genomsnittliga meddelandeentropin . Storheten kallas partiell entropi , som bara kännetecknar -e-tillståndet. $H_{i}=-\log _{2}{p_{i))$ $i$

Således är systemets entropi summan med motsatt tecken av alla relativa förekomstfrekvenser av tillståndet (händelsen) med numret multiplicerat med deras binära logaritmer [1] . Denna definition för diskreta slumpmässiga händelser kan formellt utvidgas till kontinuerliga distributioner som ges av sannolikhetstäthetsfördelningen , men den resulterande funktionalen kommer att ha något annorlunda egenskaper (se differentiell entropi ). $x$ $i$

I allmänhet kan basen för logaritmen i definitionen av entropi vara allt större än 1 (eftersom ett alfabet som består av endast ett tecken inte kan förmedla information); valet av basen för logaritmen bestämmer enheten för entropin. För informationssystem baserade på det binära talsystemet är måttenheten för informationsentropi (faktiskt information) lite . I problem med matematisk statistik kan det vara bekvämare att använda den naturliga logaritmen , i vilket fall enheten för informationsentropi är nat .

Shannons definition

Claude Shannon föreslog att informationsvinsten är lika med den förlorade osäkerheten och ställde kraven för dess mätning:

åtgärden måste vara kontinuerlig. det vill säga en förändring i värdet av sannolikhetsvärdet med ett litet belopp bör orsaka en liten nettoförändring i funktionen;
i fallet när alla alternativ (bokstäver i exemplet ovan) är lika sannolika, bör en ökning av antalet alternativ (bokstäver) alltid öka värdet på funktionen;
det ska vara möjligt att göra ett val (bokstäver i vårt exempel) i två steg, där värdet av funktionen för slutresultatet ska vara summan av funktionerna i mellanresultaten.[ klara upp ]

Därför måste entropifunktionen uppfylla villkoren $H$

$H(p_{1},\;\ldots ,\;p_{n})$ är definierad och kontinuerlig för alla , där för alla och . (Denna funktion beror bara på sannolikhetsfördelningen, inte alfabetet.) ${\displaystyle p_{1},\dotsc ,p_{n))$ $p_{i}\i [0,\;1]$ $i=1,\dotsc ,n$ $p_{1}+\dotsb +p_{n}=1$
För positiva heltal måste följande olikhet gälla: $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}}.$
För positiva heltal , där , måste likheten hålla $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)+\summa _{{i=1}}^{k} {\frac {b_{i}}{n}}H\underbrace {\left({\frac {1}{b_{i}}},\;\ldots ,\;{\frac {1}{b_{ i}}}\right)}_{{b_{i}}}.$

Shannon visade [2] att den enda funktion som uppfyller dessa krav är

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

där är en positiv konstant (och behövs egentligen bara för att välja entropienheten; att ändra denna konstant motsvarar att ändra basen för logaritmen). $K$

Shannon fastställde att mätningen av entropi ( ) som tillämpas på en informationskälla kan bestämma minimibandbreddskraven som krävs för tillförlitlig överföring av information i form av kodade binära tal. För att härleda Shannon-formeln är det nödvändigt att beräkna den matematiska förväntan av "mängden information" som finns i figuren från informationskällan. Shannon-entropimåttet uttrycker osäkerheten i realiseringen av en slumpvariabel. Entropi är alltså skillnaden mellan informationen i ett meddelande och den del av informationen som är exakt känd (eller mycket förutsägbar) i meddelandet. Ett exempel på detta är språkets redundans – det finns tydliga statistiska mönster i utseendet på bokstäver, par av på varandra följande bokstäver, trippel etc. (se Markov-kedjor ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

Definitionen av Shannons entropi är relaterad till begreppet termodynamisk entropi . Boltzmann och Gibbs arbetade mycket med statistisk termodynamik, vilket bidrog till acceptansen av ordet "entropi" i informationsteori. Det finns ett samband mellan termodynamisk och informationsentropi. Till exempel kontrasterar Maxwells demon också informationens termodynamiska entropi, och att få vilken mängd information som helst är lika med förlorad entropi.

Definition med hjälp av egen information

Det är också möjligt att bestämma entropin för en slumpvariabel genom att först introducera konceptet med fördelningen av en slumpvariabel med ett ändligt antal värden: [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

och egen information :

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

Då definieras entropin som:

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

Informationsentropienheter

Måttenheten för mängden information och entropi beror på basen för logaritmen: bit , nat , trit eller hartley .

Egenskaper

Entropi är en storhet som definieras inom ramen för en probabilistisk modell för en datakälla . Att kasta ett mynt har till exempel entropi:

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

bitar per kast (förutsatt att det är oberoende), och antalet möjliga tillstånd är lika med: möjliga tillstånd (värden) ("huvuden" och " svansar ").

2^{1}=2

För en källa som genererar en sträng som endast består av bokstäverna "A", är entropin noll: , och antalet möjliga tillstånd är: det möjliga tillståndet (värdet) ("A") och beror inte på basen av logaritm. Detta är också information som också måste beaktas. Ett exempel på minnesenheter som använder bitar med en entropi lika med noll, men med en informationsmängd lika med ett möjligt tillstånd , det vill säga inte lika med noll, är databitar inspelade i ROM , där varje bit endast har en möjlig tillstånd . $-\summa _{{i=1}}^{\infty }\log _{2}1=0$ $2^{0}=1$

Så, till exempel, kan det fastställas empiriskt att entropin för en engelsk text är 1,5 bitar per tecken, vilket kommer att variera för olika texter. Datakällans entropigrad betyder det genomsnittliga antalet bitar per dataelement som krävs för deras (data)kryptering utan förlust av information, med optimal kodning.

Vissa databitar kanske inte innehåller information. Till exempel lagrar datastrukturer ofta redundant information eller har identiska sektioner oavsett informationen i datastrukturen.
Mängden entropi uttrycks inte alltid som ett heltal av bitar.

Matematiska egenskaper

Icke-negativitet : . $H(X)\geqslant 0$
Boundedness : , som följer av Jensens olikhet för den konkava funktionen och . Om alla element från är lika sannolika, . $H(X)=-\mathop {\mathbb {E} } (\log _{2}p_{i})=\summa _{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$
Om oberoende, då . $X,\;Y$ $H(X\cdot Y)=H(X)+H(Y)$
Entropi är en uppåt konvex funktion av sannolikhetsfördelningen av element.
Om de har samma sannolikhetsfördelning av element, då . $X,\;Y$ $H(X)=H(Y)$

Effektivitet

Alfabetet kan ha en sannolikhetsfördelning som är långt ifrån enhetlig . Om originalalfabetet innehåller tecken kan det jämföras med ett "optimerat alfabet" vars sannolikhetsfördelning är enhetlig. Förhållandet mellan entropin för det ursprungliga alfabetet och det optimerade alfabetet är effektiviteten hos det ursprungliga alfabetet, vilket kan uttryckas i procent. Effektiviteten hos det ursprungliga symboliska alfabetet kan också definieras som dess -ary entropi. $n$ $n$ $n$

Entropi begränsar den maximala möjliga förlustfria (eller nästan förlustfria) komprimeringen som kan realiseras med en teoretiskt typisk uppsättning eller, i praktiken, Huffman -kodning , Lempel-Ziv-Welch- kodning eller aritmetisk kodning .

Variationer och generaliseringar

b -är entropi

I allmänhet ges b - entropin (där b är 2, 3, …) för en källa med ett initialt alfabet och en diskret sannolikhetsfördelning där är en sannolikhet ( ) av: ${\mathcal {S}}=(S,\;P)$ $S=\{a_{1},\;\ldots ,\;a_{n}\}$ $P=\{p_{1},\;\ldots ,\;p_{n}\},$ $pi}$ $a_{i}$ $p_{i}=p(a_{i})$

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

I synnerhet när , får vi den vanliga binära entropin, mätt i bitar . Med får vi en trinär entropi mätt i trits (en trit har en informationskälla med tre ekvisannolika tillstånd). När vi får information mätt i nats . $b=2$ $b=3$ $b=e$

Villkorlig entropi

Om ordningen på tecknen i alfabetet inte är oberoende (till exempel på franska följs bokstaven "q" nästan alltid av "u", och efter ordet "peredovik" i sovjetiska tidningar, ordet "produktion" eller "arbete" följdes vanligtvis), mängden information som bärs sekvensen av sådana symboler (och därmed entropin) är mindre. Villkorlig entropi används för att redogöra för sådana fakta.

Den villkorliga entropin av första ordningen (liknande Markov-modellen av första ordningen) är entropin för alfabetet, där sannolikheterna för utseendet av en bokstav efter den andra är kända (det vill säga sannolikheterna för tvåbokstavskombinationer) :

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

var är tillståndet beroende av det föregående tecknet och är sannolikheten att det var det föregående tecknet. $i$ $p_{i}(j)$ $j$ $i$

Till exempel för det ryska språket utan bokstaven "e" [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

När det gäller privata och allmänna villkorliga entropier beskrivs informationsförluster fullständigt under dataöverföring i en bullrig kanal. För detta används så kallade kanalmatriser . För att beskriva förlusten på källsidan (det vill säga den skickade signalen är känd), överväg den villkorade sannolikheten för att ta emot en symbol av mottagaren , förutsatt att symbolen skickades . I det här fallet har kanalmatrisen följande form: $p(b_{j}\mid a_{i})$ $b_{j}$ $a_{i}$

	$b_{1}$	$b_{2}$	…	$b_{j}$	…	$b_{m}$
$a_{1}$	$p(b_{1}\midt a_{1})$	$p(b_{2}\midt a_{1})$	…	$p(b_{j}\mid a_{1})$	…	$p(b_{m}\mid a_{1})$
$a_{2}$	$p(b_{1}\midt a_{2})$	$p(b_{2}\midt 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}\midt a_{m})$	$p(b_{2}\midt a_{m})$	…	$p(b_{j}\mid a_{m})$	…	$p(b_{m}\midt a_{m})$

Sannolikheterna som ligger längs diagonalen beskriver sannolikheten för korrekt mottagning, och summan av alla element i en rad ger 1. Förlusterna per sänd signal beskrivs i termer av partiell villkorlig entropi: $a_{i}$

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

För att beräkna överföringsförlusten för alla signaler används den totala villkorade entropin:

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

$H(B\mitten A)$ betyder entropin från källsidan, entropin från mottagarsidan betraktas på liknande sätt: istället indikeras den överallt (som summerar elementen i strängen kan du få , och elementen i diagonalen betyder sannolikheten att exakt tecknet som togs emot skickades, det vill säga sannolikheten för korrekt överföring). $H(A\midt B)$ $p(b_{j}\mid a_{i})$ $p(a_{i}\mid b_{j})$ $p(a_{i})$

Ömsesidig entropi

Ömsesidig entropi eller unionsentropi är utformad för att beräkna entropin för sammankopplade system (entropin för det gemensamma uppträdandet av statistiskt beroende meddelanden) och betecknas med , där kännetecknar sändaren, och - mottagaren. $H(AB)$ $A$ $B$

Förhållandet mellan sända och mottagna signaler beskrivs av gemensamma händelsesannolikheter , och endast en matris krävs för att fullständigt beskriva kanalens egenskaper: $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})$

För ett mer generellt fall, när inte en kanal beskrivs, utan interagerande system som helhet, behöver matrisen inte vara kvadratisk. Summan av alla element i kolumnen med talet ger , summan av raden med numret är , och summan av alla element i matrisen är 1. Den gemensamma sannolikheten för händelser och beräknas som produkten av den initiala och villkorade sannolikheten: $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}).

Villkorliga sannolikheter produceras av Bayes formel . Det finns alltså all data för att beräkna käll- och mottagarentropierna:

H(A)=-\summa _{i}\left(\summa _{j}p(a_{i}b_{j})\log \summa _{j}p(a_{i}b_{j} )\höger),

H(B)=-\summa _{j}\left(\summa _{i}p(a_{i}b_{j})\log \summa _{i}p(a_{i}b_{j} )\höger).

Ömsesidig entropi beräknas genom successiv rad (eller kolumn) summering av alla matrissannolikheter multiplicerat med deras logaritm:

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

Måttenheten är bit/två tecken, detta beror på att den ömsesidiga entropin beskriver osäkerheten för ett teckenpar: skickade och mottagna. Genom enkla transformationer får vi också

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

Ömsesidig entropi har egenskapen att informationen är fullständig - alla övervägda kvantiteter kan erhållas från den.

Historik

1948 , medan han undersökte problemet med rationell överföring av information genom en bullrig kommunikationskanal, föreslog Claude Shannon en revolutionerande probabilistisk metod för att förstå kommunikation och skapade den första riktigt matematiska teorin om entropi . Hans sensationella idéer fungerade snabbt som grunden för utvecklingen av två huvudområden: informationsteori , som använder begreppet sannolikhet och ergodisk teori för att studera de statistiska egenskaperna hos data- och kommunikationssystem, och kodningsteori , som huvudsakligen använder algebraiska och geometriska verktyg. att utveckla effektiva koder.

Begreppet entropi som ett mått på slumpmässighet introducerades av Shannon i hans artikel " A Mathematical Theory of Communication " , publicerad i två delar i Bell System Technical Journal 1948.

Anteckningar

↑ Denna representation är praktisk för att arbeta med information som presenteras i binär form; i allmänhet kan basen för logaritmen vara annorlunda.
↑ Shannon, Claude E. A Mathematical Theory of Communication (ospecificerad) // Bell System Technical Journal. - 1948. - Juli ( vol. 27 , nr 3 ). - S. 419 . - doi : 10.1002/j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Föreläsningar om informationsteori - MIPT , 2007. - P. 16. - 214 sid. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. Om möjligheten att öka hastigheten för överföring av telegrafmeddelanden. - M .: Electrosvyaz, 1958. - Nr 1. - S. 68-69.

Se även

Differentialentropi (entropi för kontinuerlig fördelning)
ömsesidig information
Entropikodning
Markov kedja
Avstånd Kullback-Leibler

Länkar

Shannon Claude E. A Mathematical Theory of Communication Arkiverad 31 januari 1998 på Wayback Machine
Korotaev S.M. Entropi och information är universella naturvetenskapliga begrepp .

Litteratur

Shannon K. Arbetar med informationsteori och cybernetik. - M. : Ed. utländsk lit., 2002.
Volkenshtein M. V. Entropi och information. — M .: Nauka, 2006.
Tsymbal VP Teori om information och kodning. - K . : Vishcha School, 2003.
Martin, Nathaniel FG & England, James W. Mathematical Theory of Entropy. - Cambridge University Press, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Utveckling och tillämpning av begreppet entropi. — M .: Nauka, 1967. — 280 sid.
Martin N., England J. Matematisk teori om entropi. — M .: Mir, 1988. — 350 sid.
Khinchin A. Ya. Begreppet entropi i sannolikhetsteori // Framsteg i matematiska vetenskaper . - Ryska vetenskapsakademin , 1953. - V. 8 , nr. 3(55) . - S. 3-20 . (ryska)
Brulluen L. Vetenskaps- och informationsteori. - M. , 1960.
Viner N. Cybernetik och samhälle. - M. , 1958.
Wiener N. Cybernetik eller kontroll och kommunikation inom djur och maskin. - M. , 1968.
Petrushenko L. A. Materiens självrörelse i ljuset av cybernetik. - M. , 1974.
Ashby W. R. Introduktion till cybernetik. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Sannolikhet och information. - M. , 1973.
Volkenshtein M. V. Entropi och information. - M . : Nauka, 1986. - 192 sid.
Vereshchagin N.K., Shchepin E.V. Information, kodning och förutsägelse. - M. : FMOP, MTsNMO, 2012. - 238 sid. - ISBN 978-5-94057-920-5 .

Ordböcker och uppslagsverk

I bibliografiska kataloger
BNE : XX535116 BNF : 11985913j GND : 4743861-7 J9U : 987007550784405171 LCCN : sh85044152 NDL : 01191172 NKC : ph425914