Information entropi

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. januar 2020; checks kræver 35 redigeringer .

Informationsentropi er et mål for usikkerheden i et bestemt system (i statistisk fysik eller informationsteori ), især uforudsigeligheden af udseendet af enhver karakter i det primære alfabet . I sidstnævnte tilfælde, i fravær af informationstab, er entropien numerisk lig med mængden af information pr. symbol af den transmitterede meddelelse.

For eksempel, i en sekvens af bogstaver, der udgør en sætning på russisk, vises forskellige bogstaver med forskellige frekvenser , så usikkerheden om forekomst for nogle bogstaver er mindre end for andre. Hvis vi tager i betragtning, at nogle kombinationer af bogstaver (i dette tilfælde taler de om entropien af -th orden, se nedenfor ) er meget sjældne, så falder usikkerheden endnu mere. $n$

Formelle definitioner

Binær informationsentropi , i mangel af informationstab, beregnes ved hjælp af Hartley-formlen :

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

hvor er alfabetets magt, er mængden af information i hvert symbol i beskeden. For en tilfældig variabel , der tager uafhængige tilfældige værdier med sandsynligheder ( ), bliver Hartleys formel til Shannons formel: $N$ $jeg$ $x$ $n$ $x_{i}$ $p_{i}$ $i=1,...,n$

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

Denne størrelse kaldes også den gennemsnitlige beskedentropi . Størrelsen kaldes partiel entropi , som kun karakteriserer -e-tilstanden. $H_{i}=-\log _{2}{p_{i))$ $jeg$

Således er systemets entropi summen med det modsatte fortegn af alle de relative frekvenser for forekomst af tilstanden (begivenheden) med tallet , ganget med deres binære logaritmer [1] . Denne definition for diskrete tilfældige hændelser kan formelt udvides til kontinuerlige fordelinger givet af sandsynlighedstæthedsfordelingen , men den resulterende funktionelle vil have lidt forskellige egenskaber (se differentiel entropi ). $x$ $jeg$

Generelt kan basen af logaritmen i definitionen af entropi være alt større end 1 (da et alfabet bestående af kun ét tegn ikke kan formidle information); valget af basis for logaritmen bestemmer entropienheden. For informationssystemer baseret på det binære talsystem er måleenheden for informationsentropi (faktisk information) en smule . I problemer med matematisk statistik kan det være mere bekvemt at bruge den naturlige logaritme , i hvilket tilfælde informationsentropienheden er nat .

Shannons definition

Claude Shannon foreslog, at informationsgevinsten er lig med den tabte usikkerhed, og satte kravene til dens måling:

foranstaltningen skal være kontinuerlig; det vil sige, at en ændring i værdien af sandsynlighedsværdien med et lille beløb skulle forårsage en lille nettoændring i funktionen;
i det tilfælde, hvor alle muligheder (bogstaver i ovenstående eksempel) er lige sandsynlige, bør en forøgelse af antallet af muligheder (bogstaver) altid øge værdien af funktionen;
det skulle være muligt at foretage et valg (bogstaver i vores eksempel) i to trin, hvor værdien af funktionen af det endelige resultat skal være summen af funktionerne af mellemresultaterne.[ ryd op ]

Derfor skal entropifunktionen opfylde betingelserne $H$

$H(p_{1},\;\ldots ,\;p_{n})$ er defineret og kontinuerlig for alle , hvor for alle og . (Denne funktion afhænger kun af sandsynlighedsfordelingen, ikke alfabetet.) ${\displaystyle p_{1},\dotsc ,p_{n))$ $p_{i}\i [0,\;1]$ $i=1,\dotsc ,n$ $p_{1}+\dotsb +p_{n}=1$
For positive heltal skal følgende ulighed være gældende: $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}}.$
For positive heltal , hvor skal ligheden holde $b_{i}$ $b_{1}+\ldots +b_{k}=n$ $H\underbrace {\venstre({\frac {1}{n)),\;\ldots ,\;{\frac {1}{n))\right)}_{n}=H\venstre({\ 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 viste [2] , at den eneste funktion, der opfylder disse krav, er

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

hvor er en positiv konstant (og er egentlig kun nødvendig for at vælge entropienheden; at ændre denne konstant svarer til at ændre logaritmens basis). $K$

Shannon fastslog, at målingen af entropi ( ) anvendt på en informationskilde kan bestemme minimumsbåndbreddekravene til pålidelig transmission af information i form af kodede binære tal. For at udlede Shannon-formlen er det nødvendigt at beregne den matematiske forventning til "mængden af information" indeholdt i figuren fra informationskilden. Shannon-entropimålet udtrykker usikkerheden ved realiseringen af en stokastisk variabel. Entropi er således forskellen mellem informationen indeholdt i en meddelelse og den del af informationen, der er nøjagtigt kendt (eller meget forudsigelig) i meddelelsen. Et eksempel på dette er sprogets redundans – der er tydelige statistiske mønstre i bogstavernes udseende, par af på hinanden følgende bogstaver, tripler osv. (se Markov-kæder ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

Definitionen af Shannons entropi er relateret til begrebet termodynamisk entropi . Boltzmann og Gibbs arbejdede meget med statistisk termodynamik, hvilket bidrog til accepten af ordet "entropi" i informationsteori. Der er en sammenhæng mellem termodynamisk og informationsentropi. For eksempel kontrasterer Maxwells dæmon også informationens termodynamiske entropi, og at få en hvilken som helst mængde information er lig med tabt entropi.

Definition ved hjælp af egne oplysninger

Det er også muligt at bestemme entropien af en stokastisk variabel ved først at introducere begrebet fordelingen af en stokastisk variabel med et endeligt antal værdier: [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

og egne oplysninger :

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

Så er entropien defineret som:

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

Informationsentropienheder

Måleenheden for mængden af information og entropi afhænger af basen af logaritmen: bit , nat , trit eller hartley .

Egenskaber

Entropi er en størrelse defineret i sammenhæng med en probabilistisk model for en datakilde . For eksempel har det entropi at kaste en mønt:

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

bits pr. kast (forudsat at det er uafhængigt), og antallet af mulige tilstande er lig med: mulige tilstande (værdier) ("hoveder" og " haler ").

2^{1}=2

For en kilde, der genererer en streng, der kun består af bogstaverne "A", er entropien nul: , og antallet af mulige tilstande er: den mulige tilstand (værdi) ("A") og afhænger ikke af bunden af logaritme. Dette er også oplysninger, der også skal tages i betragtning. Et eksempel på hukommelsesenheder, der bruger bits med en entropi lig med nul, men med en informationsmængde lig med én mulig tilstand , det vil sige ikke lig med nul, er databits optaget i ROM , hvor hver bit kun har én mulig stat . $-\sum _{{i=1}}^{\infty }\log _{2}1=0$ $2^{0}=1$

Så det kan for eksempel fastslås empirisk, at entropien i en engelsk tekst er 1,5 bit pr. tegn, hvilket vil variere for forskellige tekster. Graden af entropi af datakilden betyder det gennemsnitlige antal bits pr. dataelement, der kræves til deres (data)kryptering uden tab af information, med optimal kodning.

Nogle databits indeholder muligvis ikke information. For eksempel gemmer datastrukturer ofte overflødig information eller har identiske sektioner uanset informationen i datastrukturen.
Mængden af entropi er ikke altid udtrykt som et helt antal bits.

Matematiske egenskaber

Ikke-negativitet : . $H(X)\geqslant 0$
Afgrænsethed : , som følger af Jensens ulighed for den konkave funktion og . Hvis alle elementer fra er lige sandsynlige, . $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$
Hvis uafhængig, så . $X,\;Y$ $H(X\cdot Y)=H(X)+H(Y)$
Entropi er en opad konveks funktion af sandsynlighedsfordelingen af elementer.
Hvis de har den samme sandsynlighedsfordeling af elementer, så . $X,\;Y$ $H(X)=H(Y)$

Effektivitet

Alfabetet kan have en sandsynlighedsfordeling, der er langt fra ensartet . Hvis det originale alfabet indeholder tegn, så kan det sammenlignes med et "optimeret alfabet", hvis sandsynlighedsfordeling er ensartet. Forholdet mellem entropien af det originale og optimerede alfabet er effektiviteten af det originale alfabet, som kan udtrykkes som en procentdel. Effektiviteten af det originale symbolske alfabet kan også defineres som dets -ary entropi. $n$ $n$ $n$

Entropi begrænser den maksimalt mulige tabsfri (eller næsten tabsfri) komprimering, der kan realiseres ved hjælp af et teoretisk typisk sæt eller, i praksis, Huffman -kodning , Lempel-Ziv-Welch- kodning eller aritmetisk kodning .

Variationer og generaliseringer

b -ær entropi

Generelt er b - entropien (hvor b er 2, 3, …) af en kilde med et indledende alfabet og en diskret sandsynlighedsfordeling, hvor er en sandsynlighed ( ) givet ved: ${\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}.

Især når , får vi den sædvanlige binære entropi, målt i bits . Med får vi en trinær entropi målt i trits (en trit har en informationskilde med tre ligesandsynlige tilstande). Når vi får information målt i nats . $b=2$ $b=3$ $b=e$

Betinget entropi

Hvis rækkefølgen af bogstaverne i alfabetet ikke er uafhængig (for eksempel på fransk efterfølges bogstavet "q" næsten altid af "u", og efter ordet "peredovik" i sovjetiske aviser, ordet "produktion" eller "arbejdskraft" blev normalt fulgt), mængden af information, der bæres af sekvensen af sådanne symboler (og dermed entropien) er mindre. Betinget entropi bruges til at redegøre for sådanne fakta.

Den betingede entropi af første orden (svarende til Markov-modellen af første orden) er entropien for alfabetet, hvor sandsynligheden for udseendet af det ene bogstav efter det andet er kendt (det vil sige sandsynligheden for kombinationer af to bogstaver) :

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

hvor er tilstanden afhængig af det forrige tegn, og er den givne sandsynlighed , der var den forrige karakter. $jeg$ $p_{i}(j)$ $j$ $jeg$

For eksempel for det russiske sprog uden bogstavet "e" [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

Med hensyn til private og generelle betingede entropier er informationstab fuldstændig beskrevet under datatransmission i en støjende kanal. Til dette bruges såkaldte kanalmatricer . For at beskrive tabet på kildesiden (det vil sige, at det sendte signal er kendt), skal du overveje den betingede sandsynlighed for at modtage et symbol af modtageren , forudsat at symbolet blev sendt . I dette tilfælde har kanalmatrixen følgende form: $p(b_{j}\midt 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}\midt a_{1})$	…	$p(b_{m}\midt a_{1})$
$a_{2}$	$p(b_{1}\midt a_{2})$	$p(b_{2}\midt a_{2})$	…	$p(b_{j}\midt a_{2})$	…	$p(b_{m}\midt a_{2})$
…	…	…	…	…	…	…
$a_{i}$	$p(b_{1}\midt a_{i})$	$p(b_{2}\midt a_{i})$	…	$p(b_{j}\midt a_{i})$	…	$p(b_{m}\midt a_{i})$
…	…	…	…	…	…	…
$er$	$p(b_{1}\midt a_{m})$	$p(b_{2}\midt a_{m})$	…	$p(b_{j}\midt a_{m})$	…	$p(b_{m}\midt a_{m})$

Sandsynlighederne placeret langs diagonalen beskriver sandsynligheden for korrekt modtagelse, og summen af alle elementer i enhver række giver 1. Tabene pr. transmitteret signal er beskrevet i form af delvis betinget entropi: $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}).

For at beregne transmissionstabet af alle signaler bruges den samlede betingede entropi:

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

$H(B\midt A)$ betyder entropien fra kildesiden, betragtes entropien fra modtagersiden på samme måde: i stedet er den angivet overalt (som opsummerer elementerne i strengen, kan du få , og elementerne i diagonalen betyder sandsynligheden for, at nøjagtigt tegnet som blev modtaget blev sendt, det vil sige sandsynligheden for korrekt transmission). $H(A\midt B)$ $p(b_{j}\midt a_{i})$ $p(a_{i}\midt b_{j})$ $p(a_{i})$

Gensidig entropi

Gensidig entropi eller unionsentropi er designet til at beregne entropien af indbyrdes forbundne systemer (entropien af den fælles fremkomst af statistisk afhængige meddelelser) og er betegnet med , hvor karakteriserer senderen, og - modtageren. $H(AB)$ $EN$ $B$

Forholdet mellem transmitterede og modtagne signaler er beskrevet af fælles begivenhedssandsynligheder , og der kræves kun én matrix for fuldt ud at beskrive kanalens egenskaber: $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})$

For et mere generelt tilfælde, når ikke en kanal er beskrevet, men interagerende systemer som helhed, behøver matrixen ikke at være kvadratisk. Summen af alle elementer i kolonnen med tallet giver , summen af rækken med tallet er , og summen af alle elementer i matrixen er 1. Den fælles sandsynlighed for hændelser og beregnes som produktet af den indledende og betingede sandsynlighed: $j$ $p(b_{j})$ $jeg$ $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}).

Betingede sandsynligheder er produceret af Bayes' formel . Der er således alle data til beregning af kilde- og modtagerentropierne:

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

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

Gensidig entropi beregnes ved successiv række (eller kolonne) summering af alle matrix sandsynligheder ganget med deres logaritme:

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

Måleenheden er bit/to tegn, det skyldes, at den gensidige entropi beskriver usikkerheden for et tegnpar: sendt og modtaget. Ved simple transformationer opnår vi også

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

Gensidig entropi har egenskaben af informationsfuldstændighed - alle betragtede mængder kan opnås fra den.

Historie

I 1948, mens han undersøgte problemet med rationel transmission af information gennem en støjende kommunikationskanal, foreslog Claude Shannon en revolutionær probabilistisk tilgang til forståelse af kommunikation og skabte den første ægte matematiske teori om entropi . Hans opsigtsvækkende ideer tjente hurtigt som grundlag for udviklingen af to hovedområder: informationsteori , som bruger begrebet sandsynlighed og ergodisk teori til at studere de statistiske karakteristika ved data- og kommunikationssystemer, og kodningsteori , der hovedsageligt bruger algebraiske og geometriske værktøjer. at udvikle effektive koder.

Begrebet entropi som et mål for tilfældighed blev introduceret af Shannon i hans artikel " A Mathematical Theory of Communication " , offentliggjort i to dele i Bell System Technical Journal i 1948.

Noter

↑ Denne repræsentation er praktisk til at arbejde med information præsenteret i binær form; i almindelighed kan basisen for logaritmen være anderledes.
↑ Shannon, Claude E. A Mathematical Theory of Communication (uspecificeret) // Bell System Technical Journal. - 1948. - Juli ( bind 27 , nr. 3 ). - S. 419 . - doi : 10.1002/j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Forelæsninger om informationsteori - MIPT , 2007. - S. 16. - 214 s. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. Om muligheden for at øge transmissionshastigheden af telegrafmeddelelser. - M .: Electrosvyaz, 1958. - Nr. 1. - S. 68-69.

Se også

Differentiel entropi (entropi for kontinuerlig fordeling)
gensidig information
Entropi kodning
Markov kæde
Kullback-Leibler distance

Litteratur

Shannon K. Arbejder med informationsteori og kybernetik. - M. : Red. udenlandsk lit., 2002.
Volkenshtein M. V. Entropi og information. — M .: Nauka, 2006.
Tsymbal VP Teori om information og kodning. - K . : Vishcha Skole, 2003.
Martin, Nathaniel FG & England, James W. Matematisk teori om entropi. - Cambridge University Press, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Udvikling og anvendelse af begrebet entropi. — M .: Nauka, 1967. — 280 s.
Martin N., England J. Matematisk teori om entropi. — M .: Mir, 1988. — 350 s.
Khinchin A. Ya. Begrebet entropi i sandsynlighedsteori // Fremskridt i matematiske videnskaber . - Russiske Videnskabsakademi , 1953. - V. 8 , no. 3(55) . - S. 3-20 . (Russisk)
Brulluen L. Videnskab og informationsteori. - M. , 1960.
Viner N. Kybernetik og samfund. - M. , 1958.
Wiener N. Kybernetik eller kontrol og kommunikation i dyr og maskine. - M. , 1968.
Petrushenko L. A. Materiens selvbevægelse i lyset af kybernetik. - M. , 1974.
Ashby W. R. Introduktion til kybernetik. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Sandsynlighed og information. - M. , 1973.
Volkenshtein M. V. Entropi og information. - M . : Nauka, 1986. - 192 s.
Vereshchagin N.K., Shchepin E.V. Information, kodning og forudsigelse. - M. : FMOP, MTsNMO, 2012. - 238 s. - ISBN 978-5-94057-920-5 .

Ordbøger og encyklopædier

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