Entropia informaţiei

Imaginează-ți două mașini. Ambele afișează mesaje dintr-un alfabet format din A, B, C sau D. Prima mașină generează fiecare simbol la întâmplare, fiecare producându-se 25% din timp, în timp ce a doua mașină generează simboluri în funcție de următoarele probabilități. Care mașină produce mai multe informații? Claude Shannon a reformulat întrebarea. Dacă ar trebui să prezici următorul simbol de la fiecare mașină, care este numărul minim de întrebări cu răspunsuri de tip da sau nu pe care ar trebui să îl pui? Să ne uităm la prima mașină. Cea mai eficientă metodă este să pui o întrebare care împarte posibilitățile în jumătate. De exemplu, prima întrebare ar putea fi dacă sunt oricare două simboluri, precum „este A sau B?”, de vreme ce sunt 50% șanse să fie A sau B și 50% șanse să fie C sau D. După primirea răspunsului, putem înlătura jumătate dintre posibilități și rămânem cu două simboluri echiprobabile. Apoi alegem unul dintre cele două și întrebăm „este A?”, iar după cea de-a doua întrebare am identificat corect simbolul. Putem spune că gradul de incertitudine al primei mașini este de două întrebări pe simbol. Cum rămâne cu a doua mașină? La fel ca în cazul primei mașini, trebuie să punem două întrebări pentru a determina următorul simbol. Oricum, în acest caz, probabilitatea fiecărui simbol este diferită, așa că vom pune întrebările diferit. Aici există o șansă de 50% să se producă A și 50% să se producă celelalte litere. Am putea începe prin a întreba: „Este A?”, Dacă este A, am terminat cu o singură întrebare în acest caz. Altfel, ne rămân două rezultate egale: D sau B și C. Am putea întreba „este D?”. Dacă răspunsul este „da”, am terminat punând doar două întrebări. Altfel, trebuie să punem o a treia întrebare pentru a determina care dintre ultimele două simboluri s-a produs. În medie, câte întrebări trebuie să pui pentru a determina simbolul celei de-a doua mașini? Acest lucru poate fi explicat ușor printr-o analogie. Să presupunem, în schimb, că vrem să construim cele două mașini, și putem genera simboluri lansând un disc spre un cui în una două direcții echiprobabile. Bazându-ne pe locul în care cade, putem genera un simbol. Pentru prima mașină trebuie să adăugăm un al doilea nivel, sau un al doilea ricoșeu, așa că vom avea două ricoșeuri ce duc la patru rezultate echiprobabile. Bazându-ne pe locul în care ajunge discul, afișăm A, B, C, sau D. Acum a doua mașină. În acest caz, primul ricoșeu duce fie la un A, ceea ce se întâmplă în 50% din cazuri, fie la un al doilea ricoșeu, care poate produce fie D, ceea ce se întâmplă în 25% din cazuri, sau poate duce la un al treilea ricoșeu ce duce fie la B, fie la C, în 12.5% din cazuri. Acum să calculăm media ponderată. Media numărului de ricoșeuri este probabilitatea simbolului A înmulțită cu un ricoșeu, plus probabilitatea lui B înmulțită cu trei ricoșeuri, plus probabilitatea lui C înmulțită cu trei ricoșeuri, plus probabilitatea lui D înmulțită cu două ricoșeuri. Asta duce la un rezultat de 1.75 ricoșeuri. Trebuie să observi legătura dintre întrebările cu răspunsuri de tip da sau nu și ricoșeurile corecte. Numărul mediu de întrebări este egal cu numărul mediu de ricoșeuri. Așadar, prima mașină necesită două ricoșeuri pentru a genera un simbol, în timp ce ghicitul unui simbol necunoscut necesită două întrebări. A doua mașină necesită 1.75 ricoșeuri. Trebuie să punem 1.75 întrebări în medie, adică dacă trebuie să ghicim o sută de simboluri de la ambele mașini, trebuie să punem 200 de întrebări pentru prima mașină și 175 de întrebări pentru a doua mașină. Asta înseamnă că a doua mașină produce mai puține informații pentru că există mai puțină incertitudine, sau surprindere, despre rezultatul afișat. Claude Shannon numește această măsurare a incertitudinii medie „entropie” și folosește litera H să o reprezinte. Unitatea de măsură a entropiei pe care Shannon o alege este bazată pe incertitudinea unei aruncări corecte a unei monede, și numește asta „bit”, care este echivalentul unui ricoșeu al discului. Putem ajunge la același rezultat folosind analogia ricoșeurilor. Entropia, sau H, este suma pentru fiecare simbol a probabilității acelui simbol înmulțită cu numărul de ricoșeuri. Cum exprimăm numărul de ricoșeuri într-un mod mai general? După cum am văzut, numărul de ricoșeuri depinde de nivelul din arbore pe care ne aflăm. Putem simplifica această idee spunand că numărul de ricoșeuri este egal cu logaritm în baza doi din numărul de rezultate de la acel nivel. Numărul de rezultate de la un nivel este, de asemenea, bazat pe probabilitate, unde numărul de rezultate la un nivel este egal cu 1 împărțit la probabilitatea acelui rezultat. Numărul de ricoșeuri este de fapt egal cu logaritm în baza doi din unu împărțit la probabilitatea acelui simbol, care ne duce la ecuația finală. Entropia, sau H, este suma pentru fiecare simbol a probabilității acelul simbol înmulțit cu logaritm în baza doi din unu împărțit la probabilitatea acelui simbol. Shannon rescrie această ecuație, inversând doar expresia din interiorul logaritmului, ceea ce ne face să adaugăm un număr negativ, deși ambele formule duc la același rezultat. Să recapitulăm. Entropia este maximă când toate rezultatele sunt echiprobabile. De fiecare dată când te îndepărtezi de rezultate echiprobabile sau introduci previzibilitatea, entropia scade. Ideea fundamentală este că, dacă entropia unei surse de informație scade, înseamnă că putem pune mai puține întrebări pentru a ghici rezultatul. Mulțumită lui Shannon, bitul, care este unitatea de masură a entropiei, este adoptat ca unitate de masură pentru cantitatea de informație, sau surpriză.