3.4.2 L'entropia di Shannon e la quantità di informazione

Introduzione. Consideriamo un sistema che possa trovarsi in stati denotati dall'indice "i" con probabilità  pi . Vogliamo definire una quantità che misuri la distribuzione delle  pi . Tale funzionale, definito entropia, sarà tanto maggiore quanta meno informazione abbiamo circa il suo stato più probabile. Vale che se pj=1 per j=i e pj=0 per j diverso da i, allora S=0; inoltre se pi=1/N per ogni i (con N stati equiprobabili) allora S è massima; infine S è additiva. Da questo esce un funzionale logaritmico. Per i=1,2 e N copie di tale sistema tendenti a infinito abbiamo

S(p1,p2) = -k ( p1 ln(p1) + p2 ln(p2) )

E si può generalizzare a M possibili stati.

Shannon diceva: "il problema centrale della comunicazione è riprodurre in maniera esatta o approssimata in un punto un messaggio composto in un altro punto". Un sistema di comunicazione è composto da: una sorgente di informazione (il cui alfabeto è un insieme di simboli di cardinalità K), un trasmettitore, un canale, un ricevitore, un destinatario, possibili sorgenti di rumore. Noi analizzeremo la sorgente di informazione.

Definizioni. Una distribuzione di probabilità è una funzione non negativa  p(x)  con x appartenente a un insieme discreto e finito X=(x1,...,xk) noto come alfabeto. Vale la relazione: Somma[p(x)]=1 . Se X è aleatoria PX=pX(x) è la probabilità che la X assuma il valore x dell'alfabeto.

Chiamiamo ENTROPIA H(X) di una variabile casuale discreta X come 

H(X) = - Somma[ p(x) log(p(x)) ]

con sommatoria su tutti gli x appartenenti a X e log in base 2 (H è dunque espressa in bits). Osserviamo che H non dipende direttamente dai valori assunti da X, ma solo dalle sue probabilità.

Esempio: se X=1 con probabilità p e X=0 con probabilità 1-p allora H(X)=H(p)=1 bit per X=1/2 e H è una funzione concava con valori nulli in p=0 e 1 e massima incertezza in 1/2.

Esempio 2: possiamo scegliere i simboli a, b, c, d dell'alfabeto e assegnare loro probabilità differenti (1/2,1/4,1/8,1/8): l'entropia sarà allora  H(X)=7/4 bits .

Generalizzando possiamo scegliere una sequenza di N lettere scelte da M simboli. Tale messaggio sN generato dalla sorgente fa emergere il problema della codifica: abbiamo bisogno di trasformare ogni sequenza M-aria in una sequenza binaria nel modo più economico possibile, tale per cui la lunghezza media della sequenza sia minima. Shannon dimostrò che è possibile associare a ogni messaggio ad una sequenza  l(sN)=log2(1/p(sN))  circa. Tale valore è una misura delle risorse necessarie per inviare un messaggio. Per sorgente stazionaria e priva di memoria abbiamo l'entropia a N-blocchi (con sommatoria su tutti i messaggi):

HN = - Somma[ p(sN) ln(p(sN)) ]            HN / N = H1        h = HN+1 - HN = H1

Quando la sorgente ha memoria dobbiamo trattare con un processo Markoviano di ordine m, per cui la probabilità di avere un dato simbolo dipende solo dai precedenti m simboli e  hN = h  per ogni N maggiore o uguale a m. Nel limite di N a infinito otteniamo il numero medio di bits per codificare un simbolo emesso da una sorgente, che misura la quantità di informazione "a sorpresa" che la sorgente può emettere. Tale grandezza è definita entropia di Shannon:

h = limN [ media(l)N / N ] = limN [ Somma[ p(sN) log2(1/p(sN)) ] ]

Spieghiamo meglio supponendo che la sorpresa che riceviamo nell'apprendere che un dato evento si è verificato dipenda solo da quell'evento. Se l'evento accade con certezza la nostra sopresa sarà nulla. Dal'altra parte se la probabilità di accadere è molto piccola la nostra sopresa sarà proporzionalmente grande.

Il teorema di Shannon, Mc Millan e Breiman spiega in maniera precisa in che modo l'entropia quantifica la complessità della sorgente: se N è abbastanza grande l'insieme delle sequenze di lunghezza N, le parole, può essere diviso in due classi A1 e A2 tali che tutte le parole in A1 hanno probabilità che va come p ~ e-hN e la somma di tali probabilità tende a 1 per N tendente a infinito, mentre contemporaneamente quella relativa a A2 tende a 0. L'insieme A1 è detto delle sequenze tipiche e il numero di tali sequenze è

Neff(N) ~ ehN

Osserviamo che in casi non banali, per cui h<lnm abbiamo Neff molto minore del numero totale di possibili parole mN . Ricordiamo inoltre che il teorema precedente per processi senza memoria non è altro che la legge dei grandi numeri. L'insieme delle sequenze tipiche presenta Neff = 2Nh circa elementi e la probabilità per tali sequenze è circa 1, mentre per l'insieme rimanente è circa 0. Infine si può mostrare che l'entropia di Shannon è l'analogo dell'entropia per particella in meccanica statistica. Per lo studio della complessità algoritmica si vedano i lavori di Kolmogorov.

Tratto da Note su entropia e complessità di Vittorio Loreto (2010).