Entropie (teoria informației)

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În teoria informației, entropia unei surse de mesaje este media informațiilor conținute în fiecare mesaj trimis. Informațiile conținute într-un mesaj sunt cu atât mai mari cu cât erau mai puține. Un mesaj abandonat, care are o mare probabilitate de a fi emis de sursă, conține puține informații, în timp ce un mesaj neașteptat, puțin probabil, conține o cantitate mare de informații. Entropia unei surse răspunde la întrebări precum: care este numărul minim de biți necesari pentru a stoca un mesaj de la sursă în medie? Cât de previzibile sunt mesajele emise de sursă?

S-a arătat că o secvență de mesaje emise de o sursă poate fi comprimată fără pierderi de informații până la un număr minim de biți per mesaj egal cu entropia sursei.

O secvență de litere precum aaaaaaaa are mai puțină entropie decât un cuvânt precum alfabetul care, la rândul său, are și mai puțină entropie decât un șir complet aleatoriu, cum ar fi j3s0vek3 . Entropia poate fi văzută ca aleatoritatea conținută într-un șir și este strâns legată de numărul minim de biți necesari pentru a-l reprezenta fără erori.

Istorie

Îi datorăm lui Claude Shannon studiul entropiei în teoria informației, prima sa lucrare pe această temă se regăsește în articolul O teorie matematică a comunicării din 1948 . În prima teoremă a lui Shannon, sau teorema lui Shannon privind codificarea sursă, el a demonstrat că o sursă aleatorie de informații nu poate fi reprezentată cu un număr de biți mai mic decât entropia sa, adică auto-informația medie. Acest rezultat a fost implicit în definiția statistică a entropiei de către John Von Neumann , chiar dacă însuși Von Neumann, pus la îndoială de Shannon în probabil singurul schimb de opinii dintre ei, nu l-a considerat demn de atenție. După cum și-a amintit mai târziu Shannon despre rezultat, a găsit:

„Cea mai mare preocupare a mea a fost cum să-i spun. Am crezut că îl numesc informații , dar cuvântul a fost folosit prea mult, așa că am decis să-l numesc incertitudine . Când am discutat acest lucru cu John Von Neumann, el a avut o idee mai bună. El mi-a spus că ar trebui să o numesc entropie , din două motive: "În primul rând, funcția ta de incertitudine este deja cunoscută în mecanica statistică cu acest nume. În al doilea rând, și mai semnificativ, nimeni nu știe ce este entropia pentru sigur va avea întotdeauna un avantaj "

Definiție

Informații conținute într-un eveniment

Informațiile conținute într-un eveniment emis de la o sursă , numită și autoinformare, se calculează ca:

Unde este este probabilitatea ca evenimentul întâmpla. Logaritmul rezultă din faptul că prin notația pozițională este posibil să se facă distincția evenimente echipabile cu utilizarea soarelui cifre, unde este baza numerotării . Prin urmare, înseamnă că informațiile unui eveniment pot fi văzute ca cantitatea de cifre din bază pentru a fi folosit pentru a distinge evenimentul care s-a întâmplat de toate celelalte evenimente posibile. Logaritmul devine indispensabil dacă, având în vedere două evenimente independente a căror probabilitate este produsul probabilităților unice, dorim ca entropia totală să fie suma entropiilor evenimentelor unice.

Deoarece biții sunt adesea utilizați în informatică pentru codificare, este o convenție obișnuită să se utilizeze logaritmul în baza 2. Autoinformarea este deci măsurată în biți, în timp ce se utilizează logaritmul natural în loc se folosește unitatea nat de măsură introdusă de Shannon. În special

Entropia unei surse

Entropia unei surse este definită ca valoarea așteptată a autoinformării , adică informația medie conținută în fiecare mesaj emis:

Poate fi înțeles ca numărul de cifre din bază pentru a fi utilizat în medie pentru a stoca un singur eveniment produs de sursă.

Dacă sursa este o variabilă discretă aleatorie , valoarea așteptată este redusă la o medie a informațiilor fiecărui eveniment ponderat cu propria probabilitate

Dacă sursa este o variabilă continuă aleatorie , valoarea așteptată trebuie calculată printr-o integrală:

Entropia unei variabile aleatoare continue nu împărtășește toate proprietățile acesteia pentru variabilele discrete, de exemplu poate fi negativ.

Probabilitatea evenimentelor emise poate depinde de starea sursei sau de evenimentele emise anterior, caz în care se spune că sursa are memorie. Entropia surselor cu memorie este în mod rezonabil mai mică decât entropia unei surse fără memorie. De fapt, evenimentele emise depind într-o anumită măsură de cele emise anterior, ceea ce le face mai previzibile. De exemplu, gândiți-vă la o sursă care emite biți negri / albi ai unui fax. Știind că foile scanate conțin adesea scris negru pe alb, probabilitatea ca există un bit alb depinde de biții anteriori, dacă cele anterioare erau albe crește probabilitatea ca bitul următor să fie alb.

Proprietățile variabilelor aleatorii discrete

Dacă într-o primăvară există câteva valori pentru care , prezența lor nu influențează entropia sursei, de fapt contribuția lor la însumare este văzută prin limita de pentru . După cum se poate înțelege cu ușurință, dacă aceste valori nu sunt emise niciodată, nu este nevoie să le considerăm ca posibile mesaje.

Domeniu de entropie pentru variabile discrete

Este dovedit de entropia unei variabile aleatorii discrete care poate dura valorile distincte dețin întotdeauna relația:

Demonstrație

În primul rând observăm că, desigur, este adevărat . Vom folosi acest fapt de mai multe ori.

În definiția entropiei prin adăugarea și scăderea primesti:

Atâta timp cât este o constantă, o putem extrage din însumarea pentru liniaritate.

Care pentru proprietățile logaritmilor pot fi scrise ca:

Se observă că pentru fiecare Și merită asta dacă comparăm graficul logaritmului cu linia tangentă la în adică . Deci, al doilea addend al expresiei anterioare poate fi mărit:

Adică, al doilea summend este întotdeauna mai mic decât prin urmare:

În special, se arată că maximul entropiei este precis și o primești când totul valorile sunt la fel de probabile.

Eficiența unui alfabet

Dat un alfabet de simboluri, entropia sa în transmiterea informațiilor este maximă dacă toate simbolurile sunt utilizate cu aceeași frecvență și eficiența alfabetului poate fi definită ca raportul dintre entropia acestuia și maximul posibil pentru un alfabet de simboluri:

Pentru a comprima fișiere fără a pierde informații, este necesar să utilizați un alfabet mai eficient. Dacă te uiți la un fișier comprimat cu un editor de text sau hexazecimal, poți vedea marimea aleatorie a octeților conținuți în acesta. Algoritmii care permit îmbunătățirea unei codificări ineficiente sunt de exemplu codificarea Huffman și codarea aritmetică , ambele codificări trebuie să estimeze probabilitatea cu care au fost prezentate simbolurile codificării anterioare pentru a o îmbunătăți.

Exemple

Fig. 1 - Entropia unei surse binare

Entropia unei surse binare cine are probabilitate a produce , probabilitate să producă și în consecință è (a se vedea figura 1):

Prin urmare, este de 1 bit în cazul echipabilității rezultatelor și de 0 bit în cazul în care sursa este complet previzibilă (adică emite întotdeauna 0 sau întotdeauna 1). Acest rezultat este rezonabil, deoarece în primul caz se afirmă că este necesar un bit de informație pentru fiecare mesaj emis de sursă, în timp ce în al doilea caz nu este necesar niciun bit, deoarece valoarea tuturor mesajelor este cunoscută a priori și, prin urmare, sursa este complet inutil.

Pentru a ilustra corelația strânsă dintre entropia informației și entropia termodinamicii, putem folosi următorul exemplu:

Să luăm în considerare un sistem fizic în condiții date de temperatură, presiune și volum și să stabilim valoarea sa de entropie; în legătură este posibil să se stabilească gradul de ordine și, prin urmare, cantitatea de informații noastre (în sens microscopic). Acum presupunem că scădem temperatura lăsând neschimbați ceilalți parametri: observăm că entropia sa scade odată cu creșterea gradului său de ordine (ordinea statică care corespunde lipsei de mișcare, de lucru) și odată cu aceasta nivelul nostru de informații. La limită, la o temperatură apropiată de zero absolut, toate moleculele sunt „aproape” nemișcate, entropia tinde la minim și ordinea (cristalizată, nu cea a organizării negentropice care necesită un sistem deschis) este maximul posibil și odată cu aceasta aveți siguranța maximă a informațiilor; de fapt, nu mai există nicio alternativă din care să alegeți.

Utilizări

Una dintre cele mai neașteptate utilizări ale entropiei și a algoritmilor de compresie bazate pe aceasta este recunoașterea textelor, atât prin criptografie , cât și prin potrivirea tiparelor (detectarea plagiatului , comprimarea secvențelor ADN etc.).

Entropie și informații

Din definiția statistică a entropiei termodinamice se înțelege că informațiile și această mărime termodinamică sunt într-un fel corelate. Studii ample în acest domeniu sunt legate de munca de pionierat a lui Claude Shannon în domeniul teoriei informației .

De fapt, în 1948 Claude Shannon a enunțat Teorema unicității entropiei în teoria informației: De fapt, definită ca un set de caractere alfanumerice A = {A (1), A (2), A (3), ... A (n)} și definit p (i) probabilitatea de a observa simbolul A (i) este definită de fapt entropia H (p (0), p (1), ... p (n)). Trebuie să respecte trei condiții:

  • dacă A (k) are probabilitatea p (k) = 0 să apară atunci H (p (0), p (1), ... p (k-1), 0) = H (p (0), p ( 1), ... p (k-1))
  • având în vedere sistemele independente A și B avem subaditivitatea: H (A, B) <H (A) + H (B)
  • Entropia H este maximă dacă p (i) = 1 / r (unde r numărul total de stări)

atunci definiția Entropiei este bine dată și este singura posibilă.

Informația este exprimată matematic prin relație

care, folosind logaritmul de bază 2 al probabilității P că apare un eveniment dat, face posibilă obținerea unei valori măsurate în biți . 1 bit este echivalent, de exemplu, cu informațiile obținute din aruncarea unei monede (P = 0,5).

Din entropia exprimată de relația Boltzmann este ușor să derivăm egalitatea

care permite exprimarea entropiei în aceeași unitate de măsură a informației, adică bitul. Observați cum se identifică P .

În concluzie, dovedește că relația merită

ceea ce poate fi declarat ca „o creștere a entropiei corespunde unei pierderi de informații pe un sistem dat și invers”.

Bibliografie

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității LCCN (EN) sh85044152 · GND (DE) 4743861-7 · BNF (FR) cb11985913j (dată) · BNE (ES) XX535116 (dată) · NDL (EN, JA) 01.191.172