Che cos’è l’informazione?

Se volessimo farlo, saremmo in grado di definire l’informazione? Cos’è e come si quantifica? Sappiamo che un esperto ha più informazioni di un neofita, ma la definizione è lungi dall’essere chiara (un po’ come il tempo).

Consideriamo due persone, Alice e Bob, la loro forma di comunicazione avverrà attraverso un linguaggio che hanno in comune. Pensiamo che Alice debba descrivere a Bob come ricostruire un determinato oggetto. Bob parte da una condizione d’incertezza (o ignoranza) totale, che le informazioni di Alice tenderanno a diminuire.

Il discorso si può quindi anche capovolgere, partendo dallo stato d’incertezza iniziale e valutando il guadagno ottenuto attraverso la comunicazione. Tanto più grande è l’informazione acquisita, tanto maggiore sarà l’incertezza di cui riusciamo a liberarci.

Eppure è necessario quantificare questo guadagno. Una prima risposta qualitativa potrebbe considerare le dimensioni dell’insieme di istruzioni spedite da Alice: il grado d’informazione raggiunto sarà in rapporto diretto con la quantità d’istruzioni comunicata. O, detto in altri termini, tanto più grande è la nostra ignoranza, tanto maggiore sarà il grado di “sorpresa” che avremo alla ricezione del messaggio. Del resto, il contenuto informativo di un messaggio è tanto più alto quanto meno “è banale”.

In termini informatici, potremmo misurare l’informazione prendendo il bit come unità. Essendo una variabile che può assumere solo i valori 0 e 1, un bit quantificherà 2 messaggi, due ne descriveranno 4, e in generale ne serviranno k per gestirne $2^k$.

Facciamo comunicare Alice e Bob attraverso un alfabeto di k lettere, spedita ciascuna con una probabilità $p_i$. Semplifichiamoci la vita e non consideriamo correlazioni nell’ordine in cui compaiono, cioé dimentichiamoci un alfabeto come il nostro, dove una consonante sarà spesso seguita da una vocale. Sarebbe troppo complicato.

Proviamo a quantificare la sorpresa nel ricevere il messaggio:

  • la $p_i$ è in relazione inversa con la sorpresa nella ricezione: a probabilità più basse, corrispondono gradi di sorpresa più alti;
  • assumiamo che la sorpresa sia una funzione lentamente variabile delle $p_i$, e che sia additiva; cioé che $$S(p_i,p_j)=S(p_i)+S(p_j)$$

Con la poca fantasia che abbiamo, un logaritmo potrebbe fare al caso nostro $$\log\frac{1}{p_i}=-\log p_i$$

E’ lentamente variabile, rispetta la prima proprietà e assicura anche l’additività. Infatti $$\log\left(\frac{1}{p_i}\frac{1}{p_j}\right)=\log\frac{1}{p_i}+\log\frac{1}{p_j}$$

Associato al concetto di sorpresa, una minore probabilità di ricevere la i-sima lettera alza il contenuto informativo. Nel nostro linguaggio, l’uso delle lettere “a” o “e” non alza di molto la nostra capacità di comprensione al momento della ricezione, come potrebbero fare la “k” o la “j”. L’informazione associata alla lettera sarà allora $$h_i=p_i\log\frac{1}{p_i}=p_i\log p_i$$

In questa maniera, l’informazione del messaggio diventa $$H=\sum_ih_i=-\sum_ip_i\log p_i$$

Cioé l’entropia di Shannon ci dice che il contenuto informativo ricevuto da Bob cresce al crescere di $H$.

Partiamo da un caso semplice come una sorgente binaria, in cui i valori possono essere solo 0 o 1. L’entropia di Shannon in questo caso è $$H=-p\log p-(1-p)\log (1-p)$$

Guardando il grafico abbiamo che la funzione è simmetrica con un massimo attorno a p=0.5. Cioé abbiamo bisogno di un bit nel caso di equiprobabilità e non ce ne serve nessuno quando la sorgente è completamente prevedibile (invia sempre 0 oppure 1). $$ \begin{align} H(p=0)=0 && H(p=1)=0\\ &\text{ e }\\ \end{align}$$ $$H(p=0.5)=1$$

Prendendo un caso più complesso econsiderando un alfabeto composto da k lettere, si può vedere che l’entropia di Shannon è compresa in un preciso intervallo $$0\le H\le \log_2k$$

E come prima, tale entropia è massima se l’alfabeto è equiprobabile, cioé se la distribuzione di probabilità è costante e pari a $p=1/k$

Una sensazione intuitiva di questo potremmo averla se tentiamo di ascoltare una nuova lingua con i suoni molto diversi dalla nostra. Non abbiamo un pattern di decodifica e la nostra ignoranza è totale (quindi è potenzialmente massima l’informazione che stiamo recependo).

Pensiamo ora che Alice invii un messaggio di 7 bit, con proabilità $p_0=7/8$ e $p_1=1/8$. Così

  • la probabilità di mandare un messaggio “0000000″ sarà $p_{0000000}=(7/8)^7$
  • la probabilità di mandare un messaggio “0000001″ sarà $p_{0000001}=(7/8)^6\cdot 1/8$

Tanto maggiore è il numero di “1″ presenti, tanto minore sarà la probabilità di riceverlo. Tenendo conto di questo sbilanciamento e volendo fare economia, si potrebbero usare delle sequenze corte per lettere più probabili, e sequenza più lunghe per quelli rari. Dipendentemente dalla distribuzione di probabilità dei bit, saremmo capaci di comprimere il messaggio.

Consideriamo per esempio di avere un alfabeto composto da quattro lettere $A={a_1,a_2,a_3,a_4}$ con probabilità $p={1/2,1/4,1/8,1/8}$. Possiamo rappresentarlo sicuramente con due bit, codificando $$ \begin{align} a_1=00 && a_2=01 && a_3=10 && a_4=11 \end{align} $$

Eppure lo sbilanciamento di probabilità, ci permette di ridistribuire i bit dedicati. $$ \begin{align} c_1=0 && c_2=10 && c_3=110 && c_4=111 \end{align} $$

In questo modo stiamo riducendo mediamente la lunghezza dei bit necessari a inviare una data lettera (che per la prima codifica è sicuramente uguale a 2) $$ \sum_{i=1}^4 p_il_i=\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{8}\times 3=\frac{7}{4}\lt 2 $$

Se questa operazione di compressione è allora possibile, fino a dove possiamo spingerci perdendo una quantità arbitrariamente piccola di informazione? Con l’esempio ci siamo spostati da 2 a 1.75, è il nostro limite o possiamo andare oltre?

Teorema. Shannon Noiseless Coding
Dato un messaggio nel quale le lettere sono state scelte in maniera indipendente da un ensemble $A={a_1,\ldots,a_k}$ con probabilità ${p_1,\ldots,p_k}$, esiste asintoticamente nella lunghezza del messaggio un codice di compressione ottimale di $H(p_1,\ldots,p_k)$ bits per lettera.

Sfruttando la definizione dell’entropia di Shannon, si può allora definire un rate di compressione ottimale. Nel caso di prima, $$H=-\sum_{i=1}^4p_i\log p_i=7/4$$

Cioé la nostra seconda decodifica riusciva a fornire una compressione ottimale della lunghezza del messaggio. Grazie a questo teorema, siamo sicuri che $H$ sarà il minimo numero di bit per lettera. La richiesta di un messaggio infinitamente lungo, risiede nella possibilità di valutare la probabilità di ricezione di una data lettera con la sua frequenza. In questa maniera, le sequenze diventeranno allora “tipiche”, e la i-sima lettera comparirà un numero di volte pari a $$a_i=np_i$$

Ammettendo che le sequenze “atipiche” tendano a 0, si può dimostrare che il loro numero è dato da $$ \frac{n!}{\prod_{i=1}^k(np_i)!} $$

Con l’alfabeto binario, non ci sono variazioni se permutiamo gli 0 e gli 1. Di conseguenza, il logaritmo del rapporto delle permutazioni del messaggio rispetto alle permutazioni di ogni lettera, si può valutare come $$ \begin{align} \log\left( \frac{n!}{\prod_{i=1}^k(np_i)!} \right) &=\log n!-\sum_{i=1}^n\log(np)!\\ &=n\log n-\frac{n}{\ln 2}-\sum_{i=1}^k\left[np_i\log (np_i)-\frac{np_i}{\ln 2}\right]\\ &=n\log n-\sum_{i=1}^k np_i\log n -\sum_{i=1}^knp_i\log p_i\\ &=-n\sum_{i=1}^k p_i\log p_i \end{align} $$

Avendo usato l’approssimazione di Stirling.

Di conseguenza, i messaggi tipici saranno $$ \frac{n!}{\prod_{i=1}^k(np_i)!}= 2^{nH(p_1,\ldots,p_n)} $$

Cioé per spedire n lettere basteranno nH bit. L’entropia di Shannon ci riesce a quantificare quanti bit per lettera dobbiamo utilizzare al minimo. Tutto questo senza però considerare il rumore, che dobbiamo necessariamente includere nel ragionamento.