Entropia (teoria dell'informazione)

Nella teoria dell'informazione l'entropia è una misura della quantità di informazione contenuta in un messaggio trasferito attraverso un canale di comunicazione. L'unità di misura tipica di questa grandezza è il Bit.

Storia

Si deve a Claude Shannon lo studio dell'entropia nella teoria dell'informazione. Il suo primo lavoro sull'argomento si trova nell'articolo Una teoria matematica della comunicazione del 1948. Nel primo teorema di Shannon, o teorema di Shannon sulla codifica di sorgente, egli dimostrò che una sorgente casuale d'informazione non può essere rappresentata con un numero di bit inferiore alla sua entropia, cioè alla sua autoinformazione media. Tale risultato era implicito nella definizione dell'entropia di John Von Neumann, anche se lo stesso Von Neumann, interrogato al riguardo da Shannon nel forse unico scambio di opinioni tra loro, non ritenne la cosa degna di attenzione. Come ricordò Shannon più tardi a proposito del risultato da lui trovato:

«La mia più grande preoccupazione era come chiamarla. Pensavo di chiamarla informazione, ma la parola era fin troppo usata, così decisi di chiamarla incertezza. Quando discussi della cosa con John Von Neumann, lui ebbe un'idea migliore. Mi disse che avrei dovuto chiamarla entropia, per due motivi: "Innanzitutto, la tua funzione d'incertezza è già nota nella meccanica statistica con quel nome. In secondo luogo, e più significativamente, nessuno sa cosa sia con certezza l'entropia, così in una discussione sarai sempre in vantaggio»

Definizione

Informazione intrinseca

L'informazione intrinseca di un evento, detta anche autoinformazione, è la quantità d'incertezza associata allo stesso. Più concretamente è l'informazione che si ottiene affermando che tale evento si sia realizzato o meno, rimuovendo quindi l'incertezza associata. L'autoinformazione è la forma più semplice di entropia definita da Shannon, e costituisce il punto di partenza nella definizione di altri concetti della teoria dell'informazione.

L'ambiguità esistente tra incertezza ed informazione non deve stupire. Esse si presentano infatti come due facce della stessa medaglia: senza incertezza non c'è informazione, e quanta più incertezza c'è nel segnale aleatorio, tanto più informativo è rivelare qual è la determinazione del segnale.

Formalmente, sia $X$ una sorgente di eventi $x$, l'entropia $I$ associata ad un singolo evento è definita dalla seguente scrittura:

$I(x)=-\log _{b}p(x)$

dove $p(x)$ è la probabilità che l'evento $x$ accada.

Il logaritmo nasce dal fatto che attraverso la notazione posizionale è possibile distinguere $N$ eventi equiprobabili con l'utilizzo di sole $\log _{b}N$ cifre, dove $b$ è la base di numerazione. Significa quindi che l'informazione di un evento può essere vista come la quantità di cifre in base $b$ da utilizzare per distinguere l'evento accaduto da tutti gli altri eventi possibili. Il logaritmo diventa indispensabile se, considerando due eventi indipendenti la cui probabilità è data dal prodotto delle singole probabilità, si vuole che l'entropia totale sia la somma delle entropie dei singoli eventi.

Entropia di una sorgente di informazione

Entropia di una variabile di Bernoulli

Nel caso delle sorgenti di informazione, per entropia si intende una grandezza utile a stimare a priori il rateo della quantità di informazione emessa. Assunto che non sia possibile conoscere a priori quale dato verrà emesso in un certo istante, ma solo la sua probabilità, si definisce l'entropia della sorgente come la media pesata dell'autoinformazione dei simboli emissibili rispetto alla loro probabilità di emissione, a meno di una costante positiva di proporzionalità:

$H=-K\sum _{i}{p(x_{i})\log {p(x_{i})}}$

Nel caso l'alfabeto della sorgente sia costituito di simboli indipendenti, ovvero equiprobabili, l'espressione dell'entropia si riduce a:

$H=-K\sum _{i}{\log {p(x_{i})}}$

Nel caso particolare in cui la sorgente sia del tipo continuo invece che discreto è necessario descrivere l'entropia utilizzando l'espressione integrale omologa:

$H=-K\int {p(x)\log {p(x)}}dx$

Entropia congiunta

Entropie individuali $H(X),H(Y)$, congiunte $H(X,Y)$, e condizionali per una coppia di sottosistemi correlati $X,Y$ con informazione mutua $I(X;Y)$.

L'entropia congiunta di due variabili aleatorie discrete $X$ e $Y$ è semplicemente l'entropia della coppia: $(X,Y)$. Questo implica che, se $X$ e $Y$ sono indipendenti, allora la loro entropia congiunta è la somma delle loro entropie individuali.

Per esempio, se $(X,Y)$ rappresenta la posizione di un pezzo di scacchi ($X$ la riga ed $Y$ la colonna), allora l'entropia congiunta della riga e della colonna su cui è posto il pezzo sarà l'entropia della posizione del pezzo.

$H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)$

Nonostante la notazione simile, l'entropia congiunta non deve essere confusa con l'entropia incrociata.

Entropia condizionale

L'entropia condizionale è la quantità di informazione necessaria per descrivere il valore di una variabile aleatoria $\mathrm {X}$ noto il valore di un'altra variabile aleatoria $Y$. È anche nota come "equivoco di $X$ con $Y$".
Nel contesto dei canali di telecomunicazione rappresenta l'incertezza rimanente su un dato in corso di trasmissione, rispetto all'informazione già trasmessa.

Formalmente l'entropia condizionale $H$ di una variabile aleatoria $X$, data la variabile aleatoria $Y$ è definita dalla seguente scrittura:

$H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=\sum _{x,y}p(x,y)\log {\frac {p(y)}{p(x,y)}}$

Un'importante corollario di questa definizione è che l'entropia condizionale si può esprimere come differenza tra l'entropia congiunta $H(X,Y)$ e l'entropia intrinseca di $Y$.

$H(X|Y)=H(X,Y)-H(Y)$

Informazione mutua

L'informazione mutua è la quantità di informazione su una variabile aleatoria che può essere ricavata osservandone un'altra. In un sistema di comunicazione è importante che sia massimizzata la quantità di informazione condivisa dai segnali inviati e ricevuti. L'informazione mutua di $X$, relativamente a $Y$ è:

$I(X;Y)=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}$

Un'importante proprietà dell'informazione mutua è che

$I(X;Y)=H(X)-H(X|Y).\,$

Ossia, conoscendo Y, possiamo risparmiare in media $I(X;Y)$ bit nella codifica di X, rispetto al caso in cui Y è ignota.

L'informazione mutua è simmetrica;

$I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,$

L'informazione mutua può essere espressa come media della Divergenza di Kullback–Leibler della probabilità a posteriori di X, dato il valore di Y, rispetto alla probabilità a priori di X:

$I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))].$

In altre parole, essa misura quanto, in media, la probabilità della distribuzione X cambia se conosciamo il valore di Y. Questo è spesso calcolato come divergenza dal prodotto delle distribuzioni marginali rispetto alla vera distribuzione congiunta:

$I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y)).$

L'informazione mutua può essere considerata una statistica per stabilire l'indipendenza tra una coppia di variabili ed ha una distribuzione asintotica ben specificata.

Entropia relativa

L'entropia relativa, anche nota come "divergenza di Kullback-Leible", è un modo per confrontare due distribuzioni: una "vera" distribuzione di probabilità p(X) ed una distribuzione arbitraria q(X). Se comprimiamo dei dati in un qualche modo, per cui q(x) è la distribuzione seguita dai dati compressi, quando in realtà la distribuzione dei dati è p(x), la divergenza di Kullback–Leibler è il numero di bit addizionali medi per dato necessari alla compressione. È quindi definita come

$D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}$

Legame con l'entropia termodinamica

Dalla definizione statistica dell'entropia termodinamica si intuisce che l'informazione e questa grandezza termodinamica siano in qualche modo correlati. Gli studi approfonditi in questo campo sono legati al lavoro pionieristico di Claude Shannon nel campo della teoria dell'informazione.

Nel 1948 Claude Shannon infatti enuncia il teorema di unicità dell'entropia: dato un insieme di caratteri alfanumerici $A=\{A(1),A(2),A(3),\ldots ,A(n)\}$ e detta $p(i)$ la probabilità di osservare il simbolo $A(i)$, si definisce una funzione di entropia $\mathbb {H} (p(0),p(1),\ldots ,p(n))$, che deve rispettare le tre condizioni seguenti:

• se $A(k)$ ha probabilità $p(k)=0$ di verificarsi, allora $\mathbb {H} (p(0),p(1),\ldots ,p(k-1),0)=\mathbb {H} (p(0),p(1),\ldots ,p(k-1))$;
• dati i sistemi indipendenti $A$ e $B$, si ha la seguente condizione di subadditività: $\mathbb {H} (A,B)<\mathbb {H} (A)+\mathbb {H} (B)$;
• l'entropia $\mathbb {H}$ è massima quando $p(i)=1/r$ (dove $r$ è il numero totale di stati).

Allora si dimostra che tale definizione di entropia $\mathbb {H}$ è ben posta ed è l'unica possibile.

L'informazione viene matematicamente espressa dalla relazione

$I=-\log _{2}P$

che, utilizzando il logaritmo in base 2 della probabilità $P$ che si verifichi un dato evento, permette di ottenere un valore misurato in bit. 1 bit equivale ad esempio all'informazione ottenibile dal lancio di una moneta ($P=0,5$).

Dall'entropia espressa dalla relazione di Boltzmann è facile ricavare l'uguaglianza

$S=\log _{2}P$

che permette di esprimere l'entropia nella medesima unità di misura dell'informazione, ossia il bit. Notare come $P$ si identifichi con $\Gamma$. In conclusione si dimostra che vale la relazione

$I=-S$

che si può enunciare come "a un aumento di entropia corrisponde una perdita di informazione su un dato sistema, e viceversa".

Grandezze associate

Efficienza di un alfabeto

Dato un alfabeto di $N$ simboli, la sua entropia $\log _{b}(N)$ nel trasmettere informazioni è massima se tutti i simboli vengono utilizzati con la stessa frequenza e si può definire l'efficienza dell'alfabeto come il rapporto tra la sua entropia e quella massima possibile per un alfabeto di $N$ simboli:

$\eta [X]={\frac {-\sum _{i=1}^{N}{\mathbb {P} (x_{i})\cdot \log _{b}{\mathbb {P} (x_{i})}}}{\log _{b}{N}}}.$

Per comprimere file senza perdere informazione è necessario appunto utilizzare un alfabeto più efficiente. Se si osserva un file compresso con un editor di testo o esadecimale si può notare la grande casualità dei byte in esso contenuti. Algoritmi che permettono di migliorare una codifica poco efficiente sono ad esempio la codifica di Huffman e la codifica aritmetica, entrambe le codifiche devono stimare la probabilità con cui si presentavano i simboli della codifica precedente per poterla migliorare.

Esempi

Fig.1 - Entropia di una sorgente binaria

L'entropia di una sorgente binaria $X$ che ha probabilità $p$ di produrre $1$, probabilità $q$ di produrre $0$ e di conseguenza $p+q=1$ è (vedi Fig. 1):

$\mathbb {H} [X]=-\left(p\log _{2}{p}+q\log _{2}{q}\right)=-\left[p\log _{2}{p}+\left(1-p\right)\log _{2}\left(1-p\right)\right].$

Vale quindi 1 bit in caso di equiprobabilità dei risultati, e 0 bit nel caso in cui la sorgente sia completamente prevedibile (e cioè emetta sempre 0 o sempre 1). Tale risultato è ragionevole in quanto nel primo caso si afferma che è necessario un bit d'informazione per ogni messaggio emesso dalla sorgente, mentre nel secondo caso non è necessario alcun bit in quanto si conosce a priori il valore di tutti i messaggi e quindi la sorgente è del tutto inutile.

Per far capire la stretta correlazione tra entropia dell'informazione ed entropia della termodinamica possiamo fare il seguente esempio:

Consideriamo un sistema fisico in date condizioni di temperatura, pressione e volume, e stabiliamone il valore dell'entropia; in connessione è possibile stabilire il grado di ordine e quindi l'ammontare delle nostre informazioni (in senso microscopico). Supponiamo ora di abbassare la temperatura lasciando invariati gli altri parametri: osserviamo che la sua entropia diminuisce poiché il suo grado di ordine aumenta (ordine statico che corrisponde alla mancanza di movimento, lavoro) e con esso il nostro livello d'informazione. Al limite, alla temperatura prossima allo zero assoluto, tutte le molecole sono "quasi" ferme, l'entropia tende al minimo e l'ordine (cristallizzato, non quello dell'organizzazione neghentropica che necessita di un sistema aperto) è il massimo possibile e con esso si ha la massima certezza d'informazione; infatti non esiste più alcuna alternativa fra cui scegliere.

Bibliografia

• (EN) Claude Elwood Shannon, A mathematical theory of communication, in ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, n. 1, New York (NY, USA), Association for Computing Machinery, 1º gennaio 2001 [prima pubblicazione 1948], DOI:10.1145/584091.584093, ISSN 1559-1662.

• (EN) Robert Mario Fano, Transmission of information; a statistical theory of communications, MIT Press, 1961.

• R. Bonazzi, R. Catena, S. Collina, L. Formica, A. Munna e D. Tesini, Telecomunicazioni per l'ingegneria gestionale. Codifica di sorgente. Mezzi di trasmissione. Collegamenti, Pitagora Editrice, 2004, ISBN 88-371-1561-X.

• (EN) Xin Chen, Brent Francia, Ming Li, Brian McKinnon e Amit Seker, A theory of uncheatable program plagiarism detection and its practical implementation (PDF), 5 maggio 2002. URL consultato il 15 dicembre 2008.

• Olivier Costa de Beauregard, Irreversibilità, entropia, informazione: il secondo principio della scienza del tempo, Di Renzo Editore, 1994.

• (EN) Thomas M. Cover e Joy A. Thomas, Elements of Information Theory, 2ª ed., Hoboken (NJ, USA), Wiley, 2006, ISBN 978-0-471-24195-9.

• (EN) Michael Wise, Improved Detection Of Similarities In Computer Program And Other Texts (PDF), 1996.

• (EN) M. Tribus e E.C. McIrvine, Energy and information, in Scientific American, n. 224, Nature Publishing Group, 1971, pp. 178-184.

• (EN) Shigeru Furuichi, Flavia-Corina Mitroi-Symeonidis e Eleutherius Symeonidis, On some properties of Tsallis hypoentropies and hypodivergences, in Entropy, n. 16, MDPI, 15 ottobre 2014, DOI:10.3390/e16105377, ISSN 5377-5399.

• (EN) Shigeru Furuichi e Flavia-Corina Mitroi-Symeonidis, Mathematical inequalities for some divergences, in Physica A: Statistical Mechanics and its Applications, n. 391, Science Direct, 2012, pp. 388-400, DOI:10.1016/j.physa.2011.07.052, ISSN 0378-4371.

• (EN) Shigeru Furuichi, Nicuşor Minculete e Flavia-Corina Mitroi-Symeonidis, Some inequalities on generalized entropies, in Journal of Inequalities and Applications, 2012:226, Springer, 2012, DOI:10.1186/1029-242X-2012-226.

• (EN) Dènes Petz, Entropy, von Neumann and the von Neumann entropy (PDF), in John von Neumann and the Foundations of Quantum Physics, Dordrecht, Kluwer Academic Publishers, 2001, DOI:10.1016/S1355-2198(03)00070-4, ISBN 0792368126, ISSN 1355-2198. URL consultato il 22 marzo 2005 (archiviato dall'url originale il 9 maggio 2005).

Voci correlate

• Entropia
• Negentropia, l'entropia differenziale
• Compressione dei dati
• Claude Shannon
• John von Neumann

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «entropia»
• Wikimedia Commons contiene immagini o altri file sull'entropia

Collegamenti esterni

• entropia, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Lucio Bianco e Maurizio Talamo, ENTROPIA, in Enciclopedia Italiana, V Appendice, Istituto dell'Enciclopedia Italiana, 1992.
• entropia, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• Antonio Di Meo, entropia, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• entropìa, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.
• entropìa, su sapere.it, De Agostini.
• entropia, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) entropy / Shannon’s entropy, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Entropy, su MathWorld, Wolfram Research.
• (EN) Lukasz Kozlowski, Shannon entropy calculator, su shannonentropy.netmark.pl.