Informazione, entropia e informazione mutua

La teoria dell'informazione (C. Shannon, A mathematical theory of communication, 1948) vuole misurare l'informazione prodotta da una sorgente, con un numero che dica quanti bit servono per descriverla. È la base della codifica di sorgente (Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →) e, più avanti, del concetto di capacità del canale (Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →). Servono le probabilità discrete (Variabili aleatorie discrete e densità discretaUna variabile aleatoria discreta è una funzione X da Ω in R che assume un insieme finito o numerabile di valori (l'alfabeto); la sua densità discreta p_X(x) = P(X = x) basta a calcolare la probabilità di ogni evento che riguarda X.Variabili aleatorie discrete e densità discreta →, Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →, Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →) e la disuguaglianza di Jensen (Segnali, potenza e decibelRichiami che servono in tutto il corso. Unità SI e prefissi (kilo = $10^3$, bit e non byte); decibel $[x]{dB}=10\log{10}x$ per le potenze e $20\log_{10}$ per le ampiezze (prodotti = somme); banda di un segnale (primo zero, a $\alpha$ dB, di energia) e banda pratica; energia, potenza e teorema di Parseval; processi aleatori: media, potenza, autocorrelazione, stazionarietà (WSS), ergodicità, densità spettrale di potenza $\mathcal P_x(f)$ e filtraggio $\mathcal P_y=\lvert G\rvert^2\mathcal P_x$.Segnali, potenza e decibel →, §7).

1. L'informazione di un evento

Una sorgente emette ogni volta un simbolo preso da un insieme $\mathcal A_x=\{a_1,\dots,a_M\}$ (l'alfabeto, di cardinalità $M$) con probabilità $P(a_i)$. Si cerca una funzione $i(A)$ che quantifichi l'informazione ricevuta quando si scopre che l'evento $A$ è accaduto. Per essere ragionevole deve soddisfare quattro postulati:

1. $i(A)\ge0$ per ogni evento (non esiste informazione negativa);
2. $i(\Omega)=0$ (un evento certo non dà informazione);
3. se $P(A)\le P(B)$ allora $i(A)\ge i(B)$ (più è raro, più informa);
4. se $A$ e $B$ sono indipendenti, $P(A\cap B)=P(A)P(B)$ e si vuole $i(A\cap B)=i(A)+i(B)$ (le informazioni si sommano).

Per il postulato 3 l'informazione dipende solo dalla probabilità: $i(A)=g(P(A))$ con $g$ decrescente, $g(1)=0$ e, per il postulato 4, $g(ab)=g(a)+g(b)$. L'unica famiglia di funzioni con queste proprietà è il logaritmo, $g(x)=\log_c\frac1x$ con $c>1$ (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →: il logaritmo trasforma prodotti in somme). Il cambio di base $\log_cx=\frac{\log_dx}{\log_dc}$ cambia solo l'unità. Si sceglie $c=2$:

Definizione (informazione). $\displaystyle i(A)=\log_2\frac1{P(A)}$ bit (con $\ln$ si avrebbe il nat). Per la sorgente, $i_x(a)=\log_2\frac1{p_x(a)}$.

Esempio. L'estrazione del seme di una carta (cuori, quadri, fiori, picche, equiprobabili con $P=\frac14$) ha informazione $\log_24=2$ bit; scoprire una carta precisa su 52 vale $\log_252=5{,}70$ bit; un evento certo vale $0$ bit, la testa di una moneta equa $1$ bit.

2. Entropia

Definizione (entropia). L'entropia di una variabile aleatoria discreta $x$ è l'informazione media (il valore atteso di $i_x(x)$): $$\boxed{H(x)=E\left[\log_2\frac1{p_x(x)}\right]=\sum_{a\in\mathcal A_x}p_x(a)\log_2\frac1{p_x(a)}}\quad[\text{bit}].$$ Per i termini con $p=0$ si pone $0\cdot\log_2\frac10=0$ (è il limite, si veda sotto).

Misura il grado di casualità (incertezza) dell'uscita della sorgente; dipende solo dalle probabilità e non dai valori dei simboli. In termodinamica esiste un'espressione simile ($S=k_B\ln\Omega$), ma qui l'entropia è solo una media di informazioni.

Caso binario. Se $x\in\{0,1\}$ con $P(x=1)=p$: $H(p)=p\log_2\frac1p+(1-p)\log_2\frac1{1-p}$. Agli estremi $p\to0$ il termine $p\log_2\frac1p\to0$ (si vede con la regola di de l'Hôpital: $\frac{\log(1/p)}{1/p}\to\frac{-1/p}{-1/p^2}=p\to0$), quindi $H\to0$ per $p\to0$ e $p\to1$. Il massimo si trova con la derivata: $\frac{dH}{dp}=-\log_2p+\log_2(1-p)=0\Rightarrow p=\frac12$, dove $H=1$ bit.

Esempio. $p=0{,}1$: $H=0{,}1\log_210+0{,}9\log_2\frac1{0{,}9}=0{,}332+0{,}137=0{,}469$ bit. Una moneta truccata al 90% dà meno di mezzo bit per lancio.

Teorema (limiti dell'entropia). Se la sorgente ha $M$ simboli:

1. $H(x)=0$ se e solo se $x$ è quasi certamente (a.s.) costante (un simbolo ha probabilità 1, gli altri 0); altrimenti $H(x)>0$.
2. $H(x)\le\log_2M$, con uguaglianza se e solo se i simboli sono equiprobabili.

Dimostrazione. (1) Ogni termine $p\log_2\frac1p$ è $\ge0$ perché $0<p\le1$ implica $\log_2\frac1p\ge0$ e vale $0$ solo per $p=0$ o $p=1$; la somma è nulla solo se tutti i termini lo sono, cioè se un simbolo ha $p=1$. (2) Se $p_x(a)=\frac1M$ per ogni $a$, $H=\sum_a\frac1M\log_2M=\log_2M$. Altrimenti si applica Jensen alla funzione strettamente concava $\log_2$ con la variabile $\frac1{p_x(x)}$ (non a.s. costante): $$H(x)=E\left[\log_2\frac1{p_x(x)}\right]<\log_2E\left[\frac1{p_x(x)}\right]=\log_2\sum_{a}p_x(a)\cdot\frac1{p_x(a)}=\log_2M.\qquad\square$$ (l'ultima somma ha $M$ termini ciascuno uguale a 1, se si sommano i simboli con $p>0$).

Esempio. Probabilità $0{,}35,\ 0{,}22,\ 0{,}20,\ 0{,}13,\ 0{,}10$: $H=0{,}35\log_2\frac1{0{,}35}+0{,}22\log_2\frac1{0{,}22}+0{,}20\log_2\frac1{0{,}20}+0{,}13\log_2\frac1{0{,}13}+0{,}10\log_2\frac1{0{,}10}=0{,}530+0{,}481+0{,}464+0{,}383+0{,}332=2{,}19$ bit, contro $\log_25=2{,}32$ del caso equiprobabile.

3. Più variabili: entropia congiunta

Per un vettore aleatorio $\vec v=(v_1,\dots,v_N)$ con densità congiunta $p_{\vec v}$ l'entropia congiunta è $H(\vec v)=E\left[\log_2\frac1{p_{\vec v}(\vec v)}\right]$. Per due variabili $x,y$: $$H(x,y)=\sum_{a}\sum_{b}p_{xy}(a,b)\log_2\frac1{p_{xy}(a,b)}.$$

Teorema (entropia congiunta).

1. Se $y=f(x)$ (dipendenza deterministica) $H(x,y)=H(x)$; altrimenti $H(x,y)>H(x)$. Per simmetria vale lo stesso scambiando i ruoli, quindi $H(x,y)\ge\max\{H(x),H(y)\}$.
2. Se $x$ e $y$ sono indipendenti, $H(x,y)=H(x)+H(y)$; altrimenti $H(x,y)<H(x)+H(y)$.

In sintesi $\max\{H(x),H(y)\}\le H(x,y)\le H(x)+H(y)$.

Dimostrazione. (1) Se $y=f(x)$, per ogni $a$ esiste un solo $b$ con $p_{xy}(a,b)=p_x(a)$ e gli altri $b$ hanno probabilità $0$: i termini non nulli sono gli stessi di $H(x)$. Altrimenti, esiste qualche coppia con $0<p_{xy}(a,b)<p_x(a)$ (perché $p_{xy}(a,b)\le p_x(a)$ sempre, con somma su $b$ uguale a $p_x(a)$) e quindi $\log_2\frac1{p_{xy}(a,b)}>\log_2\frac1{p_x(a)}$ in quel termine: la media aumenta. (2) Se sono indipendenti $p_{xy}=p_xp_y$ e $\log_2\frac1{p_{xy}}=\log_2\frac1{p_x}+\log_2\frac1{p_y}$: mediando si somma. Nel caso generale si studia $$H(x,y)-H(x)-H(y)=E\left[\log_2\frac{p_x(a)p_y(b)}{p_{xy}(a,b)}\right]<\log_2E\left[\frac{p_x(a)p_y(b)}{p_{xy}(a,b)}\right]=\log_2\sum_{a,b}p_x(a)p_y(b)=\log_2 1=0$$ per Jensen (la funzione $\log_2$ è concava e il rapporto non è a.s. costante, se $x,y$ non sono indipendenti). $\square$

Esempio. $x$ uniforme in $\{0,1,2\}$ e $y=(x-1)^2$ (cioè $y=1,0,1$): le coppie possibili sono $(0,1),(1,0),(2,1)$ ciascuna di probabilità $\frac13$, quindi $H(x,y)=\log_23=1{,}585=H(x)$: conoscere $x$ determina $y$. Invece per $x,y$ indipendenti con $p_x=(\frac12,\frac12)$ e $p_y=(\frac14,\frac34)$: $H(x,y)=H\left(\frac18,\frac38,\frac18,\frac38\right)=1{,}811=1+0{,}811=H(x)+H(y)$.

4. Entropia condizionata

La probabilità condizionata (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →) è $p_{x|y}(a|b)=\frac{p_{xy}(a,b)}{p_y(b)}$. L'informazione dell'evento $x=a$ sapendo $y=b$ è $i_{x|y}(a|b)=\log_2\frac1{p_{x|y}(a|b)}$.

Definizione (entropia condizionata). $$H(x|y)=E\left[i_{x|y}(x|y)\right]=\sum_{a}\sum_{b}p_{xy}(a,b)\log_2\frac1{p_{x|y}(a|b)}.$$ Dice quanta informazione si guadagna in media scoprendo $x$ quando già si conosce $y$ (l'incertezza su $x$ che resta dopo aver visto $y$).

Teorema. (a) $H(x|y)=H(x,y)-H(y)$. (b) $0\le H(x|y)\le H(x)$: vale $0$ se $x$ è funzione di $y$ e vale $H(x)$ se e solo se $x$ e $y$ sono indipendenti.

Dimostrazione. (a) Da $p_{x|y}=\frac{p_{xy}}{p_y}$ segue $\log_2\frac1{p_{x|y}}=\log_2\frac1{p_{xy}}-\log_2\frac1{p_y}$; mediando su $p_{xy}$ si ottiene $H(x,y)-H(y)$. (b) $H(x|y)=H(x,y)-H(y)\ge0$ perché $H(x,y)\ge H(y)$ (§3); e $H(x,y)\le H(x)+H(y)$ dà $H(x|y)\le H(x)$, con uguaglianza se e solo se c'è indipendenza. $\square$

Esempio. Nel caso $y=(x-1)^2$ con $x$ uniforme in $\{0,1,2\}$: $H(y)=H\left(\frac13,\frac23\right)=0{,}918$ bit, quindi $H(x|y)=1{,}585-0{,}918=0{,}667$ bit (se $y=0$ si sa che $x=1$; se $y=1$ resta incerto tra $0$ e $2$, con probabilità $\frac23$: $\frac23\cdot1=0{,}667$) e $H(y|x)=H(x,y)-H(x)=0$.

5. Informazione mutua

Quanto $y$ dice su $x$? È la riduzione di incertezza su $x$ ottenuta conoscendo $y$.

Definizione (informazione mutua). $$I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)=H(y)-H(y|x).$$ È simmetrica ($I(x;y)=I(y;x)$) e vale $0\le I(x;y)\le\min\{H(x),H(y)\}$: è zero se e solo se $x$ e $y$ sono indipendenti (conoscere $y$ non dice nulla su $x$), ed è $H(x)$ se $x$ è una funzione di $y$.

Le uguaglianze seguono da (a) del teorema precedente; $I\ge0$ è la disuguaglianza $H(x,y)\le H(x)+H(y)$ di §3.

Esempio. Joint $p_{xy}=\begin{pmatrix}0{,}4&0{,}1\\0{,}1&0{,}4\end{pmatrix}$ (due bit che coincidono col 80%): $H(x)=H(y)=1$, $H(x,y)=1{,}722$, quindi $H(x|y)=0{,}722$ e $I(x;y)=1-0{,}722=0{,}278$ bit. Per l'esempio $y=(x-1)^2$: $I=H(y)-H(y|x)=0{,}918-0=0{,}918$ bit, che è anche $H(x)-H(x|y)=1{,}585-0{,}667$. Questa grandezza è quella che il canale riesce a trasportare (Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →) e quella che misura la qualità di una previsione (Esercizio - il meteorologo, entropia e informazione mutua).

6. Messaggi di $N$ simboli, rate ed efficienza

Una sorgente emette sequenze; si considerano parole $\vec x=[x_1,\dots,x_N]$ di $N$ simboli presi tutti dallo stesso alfabeto $\mathcal A_x$: l'insieme delle parole possibili è il dizionario $\mathcal A_x^N$ (di cardinalità $M^N$). Da §3, $0\le H(\vec x)\le N\log_2M$, con uguaglianza a destra per simboli equiprobabili e indipendenti.

Definizione (entropia per simbolo, rate, efficienza). Si definisce $$H_s(\vec x)=\frac{H(\vec x)}N\le\log_2M$$ (media "per simbolo", non valore atteso statistico). Se la sorgente emette $F_s$ simboli al secondo:

• bit-rate nominale $R_b=F_s\log_2M$ (si usano $\log_2M$ bit per simbolo senza codifica);
• rate di informazione $R_0=F_sH_s(\vec x)\le R_b$ (bit di informazione davvero prodotti);
• efficienza $\eta_x=\frac{H_s(\vec x)}{\log_2M}\le1$ e ridondanza $1-\eta_x$.

Se i simboli sono equiprobabili e indipendenti $R_0=R_b$ e $\eta_x=1$; altrimenti c'è ridondanza e si possono risparmiare bit (Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →).

Esempio. $M=4$ con $p=\left(\frac12,\frac14,\frac18,\frac18\right)$: $H=\frac12+\frac24+\frac38+\frac38=1{,}75$ bit. Con $F_s=1000$ simboli/s: $R_b=2000$ bit/s, $R_0=1750$ bit/s, $\eta=\frac{1{,}75}2=0{,}875$, ridondanza $12{,}5\%$.

Esempio (sorgente con memoria). $x_n$ è una sequenza di bit indipendenti equiprobabili e $y_n=x_n-x_{n-1}$ (alfabeto $\{-1,0,1\}$). $P(y_n=0)=\frac12$, $P(\pm1)=\frac14$: $H(y_n)=1{,}5$ bit, ma i $y_n$ non sono indipendenti ($y_n=1$ impone $x_{n-1}=0$ e quindi $y_{n-1}\neq-1$). Per $N$ campioni consecutivi si contano le sequenze possibili (le $2^{N+1}$ scelte di $x$ producono $2^{N+1}-1$ sequenze distinte di $y$, perché $x$ tutto-0 e tutto-1 danno la stessa) e si trova $H(y_1,\dots,y_N)=N+1-2^{-N}$: $2{,}75$ per $N=2$, $3{,}875$ per $N=3$. Per simbolo $H_s=\frac{N+1-2^{-N}}N\to1$ bit, quindi $\eta=\frac1{\log_23}=0{,}63$: l'alfabeto di 3 valori "spreca" il 37%.

Errori comuni

• Dimenticare che l'entropia dipende solo dalle probabilità: una trasformazione biunivoca dei simboli non la cambia, una non biunivoca (che fonde simboli) la diminuisce.
• Scrivere $H(x,y)=H(x)+H(y)$ senza aver verificato l'indipendenza.
• Confondere $\log_2M$ (massimo possibile) con l'entropia effettiva.
• Scambiare $H(x|y)$ con $H(y|x)$: in generale sono diverse, mentre $I(x;y)$ è simmetrica.
• Dimenticare la base 2: con $\ln$ l'entropia è in nat e i numeri cambiano di un fattore $\ln2$.