Bazele teoriei informaţiei

Source: http://www.cs.cmu.edu/~dst/Tutorials/Info-Theory/

David S. Touretzky
înfiinţarea Catedrei de Calculatoare
la Universitatea Carnegie Mellon
din Pittsburgh, PA 15213 dst@cs.cmu.edu

Versiunea de 24 noiembrie 2004

Traduceri disponibile: Belarus

Preliminarii

Deşi informaţia este, uneori, măsurată în caractere, ca atunci când descrie o lungime de un mesaj de email, sau în cifre (ca în lungime de un număr de telefon), convenţia în teoria informaţiei este de a acţiunii de informare în biţi. Un "bit" (termenul este o contractie de cifre binare) este fie un zero sau una. Deoarece există 8 configuraţii posibile de trei biţi (000, 001, 010, 011, 100, 101, 110, şi 111), putem folosi trei biţi pentru a codifica orice întreg de la 1 la 8. Aşa că atunci când ne referim la un "3-biti", ceea ce spun este un număr întreg în intervalul 1 până la 8. Toate logaritmi utilizate în această lucrare va fi la baza doi, deci log 8 este 3. În mod similar, jurnalul de 1000 este putin mai mic de 10, şi jurnalul de un milion este puţin mai mică de 20.

Codificări eficient

Să presupunem că banul un milion de ori şi scrie secvenţa de rezultate. Dacă doriţi să comunice această secvenţă la o altă persoană, câţi biţi va dura? Dacă este o moneda echitabil, cele două rezultate posibile, capetele şi cozile, apar cu egală probabilitate. Prin urmare, fiecare clapa necesită un pic de informaţii pentru a transmite.

Pentru a trimite întreaga secvenţă va necesita un milion de biţi. Dar să presupunem că moneda este partinitoare, astfel încât capetele să apară numai 1 / 4 din timp, şi cozi apar 3 / 4. Apoi, întreaga secvenţă poate fi trimis în 811300 biţi, în medie. (Formula de calcul pentru acest lucru va fi explicat mai jos.) Aceasta ar părea să sugereze că fiecare flip al monedei necesită doar 0.8113 biţi pentru a transmite. Cum se poate transmite o dă cu banul în mai puţin de un bit, în cazul în care limba este disponibilă numai că de zero-uri şi a celor? Evident, nu poţi.

Dar dacă scopul este de a transmite o secvenţă de flips întreg, şi de distribuţie este părtinitoare în vreun fel, atunci puteţi folosi cunostintele de distribuţie pentru a selecta un cod mai eficient. Un alt mod de a privi la ea este: o secvenţă de monede părtinitoare flips conţine mai puţin de "informaţii", decât o secvenţă de flips imparţiale, aşa că ar trebui să ia mai puţini biţi pentru a transmite. Să ne uităm la un exemplu. Să presupunem că moneda este foarte extrem de părtinitoare, astfel încât probabilitatea de capete obţine este de numai 1 / 1000, şi coada este 999/1000. Într-un milion de aruncări de aceasta moneda ne-ar aştepta să vedem doar aproximativ 1.000 de capete. Mai degrabă decât transmiterea rezultatelor din fiecare aruncare, am putea transmite doar numerele care aruncă venit capete; restul aruncă pot fi presupuse a fi cozi. Fiecare arunca are o poziţie în secvenţa: un număr între 1 şi 1.000.000.

Un număr din acel interval pot fi codificate folosind doar 20 de biţi. Deci, dacă ne transmit 1000 20-bit numere, vom avea transmis toate informaţiile conţinute de original, un milion amestecati secvenţă, folosind doar circa 20.000 de biţi. (Unele secvenţe va contine mai mult de 1.000 de capete, iar unele va conţine mai puţine, astfel încât să fie perfect corect ar trebui să spunem că ne aşteptăm să aibă nevoie de 20000 biţi în medie, pentru a transmite o secvenţă asa.) Putem face chiar mai bine. Encoding poziţiile absolută a şefilor în secvenţa durează 20 de biţi pe cap de locuitor, dar acest lucru ne permite să transmită capete în orice ordine. Dacă suntem de acord să transmită capete sistematic, trecând prin secvenţa de la început până la sfârşit, atunci în loc de codificare poziţiilor lor absolută, putem codifica doar distanţa până la următorul cap, care ia mai puţini biţi. De exemplu, în cazul în care primele patru capete a avut loc la poziţiile 502, 1609, 2454, 2607 şi, apoi codificarea lor ca fiind "distanţa până la următorul cap" ar fi 502, 1107, 845, 153. În medie, distanţa dintre două capete vor fi în jurul valorii de 1000 răstoarnă; numai rareori va depăşi 4.000 distanţa răstoarnă. Numerele în intervalul 1 la 4.000 pot fi codificate în 12 biţi. (Putem folosi un truc special să se ocupe de cazurile rare în care capete sunt mai mult de 4.000 de flips afară, dar nu vom intra în detalii aici.) Deci, folosind această convenţie codare mai sofisticate, o secvenţă de monede aruncă un milion care conţin aproximativ 1.000 de capete pot fi transmise în doar 12000 biţi, în medie. Astfel, o monedă unică aruncarea nevoie de doar 0.012 de biţi pentru a transmite. Din nou, această afirmaţie are sens numai pentru că suntem transmite de fapt, o secvenţă întreagă de aruncări.

Ce se întâmplă dacă am inventat o codificare mai deştept? Care este limita pe cât de eficient orice codificare poate fi? Limita fabrică stele la circa 0.0114 de biţi pe flip, asa ca suntem deja foarte aproape de codificare optimă. conţinutul de informaţii dintr-o secvenţă este definit ca numărul de biţi necesari pentru a transmite că secvenţa folosind o codificare optimă.

Suntem mereu libertatea de a folosi o codificare mai puţin eficientă, care vor necesita mai multi biti, dar că nu creşte cantitatea de informaţii transmise.

Coduri Variabila Lungime

Exemplele precedente s-au bazat pe coduri de lungime fixă, cum ar fi 12-bit numere de codificare valori cuprinse între 1 şi 4000. Putem face de multe ori mai bine, prin adoptarea unui cod de lungime variabila. Aici este un exemplu. Să presupunem că, în loc de ai arunca o moneda suntem arunca o mor opt feţe. Etichetă părţi AH. Pentru a codifica un număr între 1 şi 8 (sau între 0 şi 7, dacă eşti un om de ştiinţă de calculator) are 3 biţi, astfel încât o mie aruncă o muri echitabil va avea 3000 de biţi pentru a transmite. Acum, să presupunem muri nu este corect, dar părtinitor într-un mod specific: şansele de a arunca un A sunt 1 / 2, şansele de a arunca o B sunt 1 / 4, C este de 1 / 8, D este de 1 / 16, E este de 1 / 32, F este de 1 / 64, şi G şi H sunt fiecare 1 / 128. Permiteţi-ne să verifice că suma acestor probabilitati este de 1, cum trebuie să fie pentru orice distribuţie de probabilitate corespunzătoare:   

Acum, haideţi să ia în considerare o codificare ideal pentru această distribuţie de probabilitate. Dacă am arunca muri şi de a lua un A, vom transmite un 0 singur. Dacă am arunca o B, vom transmite un 1 urmat de un zero, pe care vom scrie 10. Dacă am arunca o C, codul va fi cu 11 urmat de 0, sau 110. În mod similar vom folosi pentru D 1110, 11110 de E, F pentru 111110, 1111110 pentru G, şi H. 1111111 pentru Observaţi că cod pentru A este foarte concis, care necesită un singur bit pentru a transmite. Codurile pentru G şi H necesita 7 biti fiecare, ceea ce este mai mult decat cele 3 biţi necesari pentru a transmite o aruncare în cazul în care mor au fost echitabile. Dar, G şi Hs apar cu probabilitate mică, aşa că va trebui foarte rar să utilizeze această multi biti pentru a transmite un singur arunca. În medie, vom avea nevoie de mai puţin de 3 biţi. Putem calcula cu uşurinţă numărul mediu de biţi necesari pentru a transmite o aruncare: este suma de numărul de biţi necesari pentru a transmite fiecare din cele opt rezultate posibile, ponderată în funcţie de probabilitatea de a rezultat că:
    

Deci, din 1000 aruncă muri poate fi transmis in doar 1984 biţi, mai degrabă decât 3.000. Acest cod simplu de lungime variabila este codificarea optima pentru distribuţie de probabilitate de mai sus. În general, însă, distribuţii de probabilitate nu sunt atât de curat structurate, şi codificări optime sunt mult mai complicate. Exerciţiu: să presupunem că vi se oferă o mor de cinci feţe părtinitoare, care are o probabilitate de 1 / 8 de a veni A, 1 / 8 pentru B, şi 1 / 4 pentru fiecare din C, D, E. şi Design un cod optim pentru transmiterea aruncări de această moară. (Raspuns la sfârşitul anului.)

Conţinut de măsurare de informare

În exemplul precedent am folosit un murim cu opt feţe. Deoarece opt este o putere a lui doi, cod optim pentru o distribuţie de probabilitate uniformă este uşor de caclulate: log 8 = 3 biţi. Pentru codul de lungime variabilă, am scris din modelul de biţi specifică care urmează să fie transmise pentru fiecare AH faţă, şi au fost astfel capabili să se bazeze în mod direct numărul de biţi necesari. Teoria informaţiei ne oferă cu o formula pentru determinarea numărului de biţi necesar într-o Codul optimă chiar şi atunci când nu ştim codul. Să considerăm mai întâi distribuţii uniforme de probabilitate în cazul în care numărul de rezultate posibile nu este o putere a lui doi. Să presupunem că am avut o murim convenţional cu şase feţe. Numărul de biţi necesari pentru a transmite o aruncare de un targ de sase fete muri este: log 6 = 2.58. Încă o dată, nu putem transmite cu adevărat o aruncare unică în mai puţin de 3 biţi, dar o serie de aruncări pot fi transmise folosind 2.58 biţi, în medie. Codul optimă în acest caz este complicat, dar aici este o abordare care este destul de simplu şi totuşi nu mai mult de 3 biţi / arunca. În loc de a trata individual aruncări, consideră că acestea trei la un moment dat. Numărul de posibile aruncare de trei secvenţe este = 216. Utilizarea 8 biţi, putem codifica un număr între 0 şi 255, asa ca o secventa de trei-aruncarea pot fi codificate în 8 biţi, cu un pic de schimb; aceasta este mai bună decât 9 biţi am fi avut nevoie dacă ne codificate fiecare dintre cele trei aruncări separat. În termeni de probabilitate, fiecare valoare posibilă a muri de şase feţe cu egală probabilitate P = 1 / 6. Teoria informaţiei ne spune că numărul minmum de biţi necesari pentru a codifica o aruncare este de -log P = 2.58. Dacă priviţi înapoi la exemplul mor opt feţe, veţi vedea că în codul optime care a fost descris, fiecare mesaj a avut o lungime exact egală cu log P- biţi. Acum să ne uităm la cum să aplice formulă pentru a părtinitoare (non-uniform) distribuţii de probabilitate. Să gama variabila x peste valorile care urmează să fie codificate, apoi permiteţi-P (x) indica probabilitatea de valoare care apar. Numărul estimat de biţi necesari pentru a codifica o valoare este media ponderată a numărului de biţi necesar pentru a codifica fiecare valoare posibilă, în cazul în care greutatea este probabilitatea ca valoare:

Acum putem revizui cazul monedei părtinitoare. Aici variază variabila pe parcursul a două rezultate: capete şi cozi. Dacă şefii apar numai 1 / 4 din timp şi cozile 3 / 4 din timp, atunci numărul de biţi necesari pentru a transmite rezultatul unuia banul este:

O monedă corect se spune pentru a produce mai mult "informaţii", deoarece este nevoie de un pic întreg pentru a transmite rezultatul tragerea la sorti:

Intuitia spatele-P log P Formula

Cheia pentru a obţine o înţelegere intuitivă a -log P P, formula de calcul conţinutul informaţiei este de a vedea dualitatea dintre numărul de mesaje care urmează să fie codificate şi probabilităţi lor. Dacă vrem să codifica oricare din cele opt mesaje posibil, avem nevoie de 3 biţi, pentru că log 8 = 3. Suntem implicit presupunând că mesajele sunt trase dintr-o distribuţie uniformă. modalitate alternativă de a exprima acest lucru este: probabilitatea ca un anumit mesaj care apare este de 1 / 8, şi -log (1 / 8) = 3, deci avem nevoie de 3 biţi de a transmite oricare dintre aceste mesaje. Algebric, log n = -log (1 / n), astfel încât cele două abordări sunt echivalente în cazul în care probabilitatea de distribuţie este uniformă. Avantajul de a folosi abordarea probabilitatea este că, atunci când distribuţia este non-uniform, şi nu putem conta pur şi simplu numărul de mesaje, conţinutul informaţiei poate fi în continuare exprimată în termeni de probabilităţi. Uneori ne scrie despre evenimente rare, ca poartă o număr mare de biţi de informaţie. De exemplu, în cazul în care o monedă vine capete numai o singură dată din 1000 aruncă, semnalul care a avut loc un heads se spune că a transporta 10 biţi de informaţie. Cum este posibil acest lucru, deoarece rezultatul de orice altă monedă special aruncarea dureaza 1 bit pentru a descrie? De transmisie atunci când are loc un eveniment rar, dacă se întâmplă doar o dată într-o mie de teste, va avea 10 biti. Prin abordarea noastră mesaj de numărare, dacă apare o valoare de numai 1 / 1000 din timp într-o distribuţie uniformă, nu va fi 999 alte valori posibile, toate la fel de probabil, astfel încât transmiterea orice valoare s-ar putea lua într-adevăr, 10 biti. Cu o monedă există doar două valori posibile. Ce spune teoria informaţiei putem face este să ia în considerare fiecare valoare separat. Dacă o anumită valoare apare cu probabilitatea P, vom presupune că aceasta este trasată de la un set uniform distribuită de valori atunci când se calculează conţinutul său informaţii. Dimensiunea acestui set va fi de 1 elemente / P. Astfel, numărul de biţi necesari pentru a codifica o valoare din acest set ipotetic este de -log P. Având în vedere că distribuţia efectivă noi incercam sa codifica nu este uniform, luăm media ponderată a conţinutului informaţiilor estimată a fiecărei valori (capete sau cozi, în cazul unei monede), ponderată în funcţie de probabilitatea P de valoare care apar. Teoria informaţiei ne spune că o codificare optimă nu poate face mai bine decât asta. Astfel, cu moneda extrem de părtinitoare avem următorul text:

    P (capete) = 1 / 1000, astfel încât şefii ia-log (1 / 1000) = 9.96578 biţi pentru a codifica

    P (cozi) = 999 / 1000, astfel încât coada ia-log (999/1000) = 0,00144 biţi pentru a codifica

    Avg.bits necesare =           = (1 / 1000) × 9.96578+ (999/1000) × = 0.00144 0.01141 biţi pe banul

Răspuns la Exercitarea

Codul optimă este:

Mesaj	Cod
A	000
B	001
C	01
D	10
E	11