Entropia (teoria dell'informazione)

Nella teoria dell'informazione l'entropia di una sorgente di messaggi è l'informazione media contenuta in ogni messaggio emesso. L'informazione contenuta in un messaggio è tanto più grande quanto meno probabile era. Un messaggio scontato, che ha un'alta probabilità di essere emesso dalla sorgente contiene poca informazione, mentre un messaggio inaspettato, poco probabile contiene una grande quantità di informazione. L'entropia di una sorgente risponde a domande come: qual è il numero minimo di bit che servono per memorizzare in media un messaggio della sorgente? Quanto sono prevedibili i messaggi emessi dalla sorgente?

Si è dimostrato che una sequenza di messaggi emessi da una sorgente può essere compressa senza perdita d'informazione fino ad un numero minimo di bit per messaggio uguale all'entropia della sorgente.

Una sequenza di lettere come aaaaaaaa possiede meno entropia di una parola come alfabeto la quale a sua volta possiede ancora meno entropia di una stringa completamente casuale come j3s0vek3. L'entropia può essere vista come la casualità contenuta in una stringa, ed è strettamente collegata al numero minimo di bit necessari per rappresentarla senza errori.

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 statistica 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 contenuta in un evento

L'informazione contenuta in un evento $x$ emesso da una sorgente $X$, detta anche autoinformazione, si calcola come:

$I(x)=-\log _{b}\mathbb {P} (x),$

dove $\mathbb {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à è il prodotto delle singole probabilità si vuole che l'entropia totale sia la somma delle entropie dei singoli eventi.

Dato che spesso in informatica si usano i bit per codificare è convenzione comune utilizzare il logaritmo in base 2. L'autoinformazione si misura quindi in bit, mentre utilizzando il logaritmo naturale invece si utilizza l'unità di misura nat introdotta da Shannon. In particolare $1\ {\text{bit}}=0,69315\ {\text{nat}}$

Entropia di una sorgente

L'entropia di una sorgente è definita come il valore atteso dell'autoinformazione, ossia l'informazione media contenuta in ogni messaggio emesso:

$\mathbb {H} [X]=\mathbb {E} \left[I(X)\right]=\mathbb {E} \left[-\log _{b}{\mathbb {P} (X)}\right].$

Si può intendere come il numero di cifre in base ${\textstyle b}$ da utilizzare in media per memorizzare un singolo evento prodotto dalla sorgente.

Se la sorgente $X$ è una variabile aleatoria discreta il valore atteso si riduce ad una media dell'informazione di ogni evento $x_{i}$ pesata con la propria probabilità $\mathbb {P} (x_{i})$

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

Se la sorgente $X$ è una variabile aleatoria continua il valore atteso deve essere calcolato attraverso un integrale:

$\mathbb {H} [X]=-\int {\mathbb {P} (x)\cdot \log _{b}{\mathbb {P} (x)}}\ dx.$

L'entropia di una variabile aleatoria continua non condivide tutte le proprietà di quella per variabili discrete, ad esempio $\mathbb {H} [X]$ può risultare negativa.

La probabilità degli eventi emessi può dipendere dallo stato della sorgente o dagli eventi emessi in precedenza, in tal caso si dice che la sorgente ha memoria. L'entropia delle sorgenti con memoria è ragionevolmente minore dell'entropia di una sorgente senza memoria. Infatti gli eventi emessi dipendono in una certa misura da quelli emessi precedentemente, il che li rende più prevedibili. Come esempio si pensi ad una sorgente che emette bit bianchi/neri di un fax. Sapendo che spesso i fogli scansionati contengono spesso scritte in nero su bianco la probabilità che ci sia un bit bianco dipende dai bit precedenti, se i precedenti erano bianchi la probabilità che il prossimo bit sia bianco aumenta.

Proprietà delle variabili aleatorie discrete

Se in una sorgente $X$ esistono alcuni valori $x_{i}$ per cui $\mathbb {P} (x_{i})=0$, la loro presenza non influenza l'entropia della sorgente infatti il loro contributo alla sommatoria è $0$ come si vede tramite il limite di $x\log x$ per $x\rightarrow 0$. Come è facilmente intuibile, se questi valori non vengono mai emessi non c'è la necessità di considerarli come messaggi possibili.

Dominio dell'entropia per variabili discrete

Si dimostra per l'entropia di una variabile aleatoria discreta $X$ che può assumere $N$ valori distinti vale sempre la relazione:

$0\leq \mathbb {H} [X]\leq \log _{b}{N}.$

Dimostrazione

Osserviamo innanzitutto che naturalmente vale $\mathbb {\sum } _{i=1}^{N}{\mathbb {P} (x_{i})}=1$ . Useremo questo fatto più volte.

Nella definizione dell'entropia aggiungendo e togliendo $\log _{b}{N}$ si ottiene:

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

Poiché $-\log _{b}{N}$ è una costante, la possiamo estrarre dalla sommatoria per linearità:

$\mathbb {H} [X]=\log _{b}{N}-\sum _{i=1}^{N}{\mathbb {P} (x_{i})\cdot \left(\log _{b}{\mathbb {P} (x_{i})}+\log _{b}{N}\right)};$

che per le proprietà dei logaritmi si può scrivere come:

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

Si osserva che per ogni $x$ e $b>1$ vale che $\log _{b}{x}\leq {\frac {1}{\ln b}}\cdot (x-1)$ se si confronta il grafico del logaritmo con la retta tangente a $\log _{b}{x}$ in $x=1$ ovvero $y={\frac {1}{\ln b}}\cdot (x-1)$ . Quindi il secondo addendo dell'espressione precedente si può maggiorare:

$\sum _{i=1}^{N}{\mathbb {P} (x_{i})\cdot \log _{b}{\frac {1}{\mathbb {P} (x_{i})\cdot N}}}\leq {\frac {1}{\ln b}}\sum _{i=1}^{N}{\left({\frac {1}{N}}-\mathbb {P} (x_{i})\right)}={\frac {1}{\ln b}}(1-1)=0.$

Ossia il secondo addendo è sempre minore di $0$ e quindi:

$\mathbb {H} [X]\leq \log _{b}{N}.$

In particolare si dimostra che il massimo dell'entropia è proprio $\log _{b}{N}$ e si ottiene quando tutti gli $N$ valori sono equiprobabili.

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.

Utilizzi

Uno dei più inaspettati utilizzi dell'entropia e degli algoritmi di compressione basati su di essa, è il riconoscimento di testi, sia per crittografia, sia per pattern matching (individuazione di plagi, compressione di sequenze di DNA etc.).

Entropia e informazione

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 nella teoria dell'informazione: 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 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".

Bibliografia

• Claude E. Shannon, A Mathematical Theory of Communication Archiviato il 31 gennaio 1998 in Internet Archive., Bell system Technical Journal, vol 27, lug e ott 1948
• Robert M. Fano, Transmission of information; a statistical theory of communications., M.I.T. Press, 1961.
• Bonazzi R., Catena R., Collina S., Formica L., Munna A., Tesini D.. Telecomunicazioni per l'ingegneria gestionale. Codifica di sorgente. Mezzi di trasmissione. Collegamenti. Pitagora Editrice, 2004, ISBN 88-371-1561-X
• (EN) Chen, X., Brent, F., Li, M., McKinnon, B, Seker, A.,, A Theory of Uncheatable Program Plagiarism Detection and Its Practical Implementation (PDF), su citeseer.ist.psu.edu, 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
• T. M. Cover, J. A. Thomas, Elements of Information Theory, Wiley, 1991
• Michael Wise, Improved Detection Of Similarities In Computer Program And Other Texts, 1996
• M. Tribus, E.C. McIrvine, Energy and information, Scientific American, n. 224 (1971), pp. 178–184
  • Shigeru Furuichi, Flavia-Corina Mitroi-Symeonidis, Eleutherius Symeonidis, On some properties of Tsallis hypoentropies and hypodivergences, Entropy, 16(10) (2014), 5377-5399; DOI:10.3390/e16105377
  • Shigeru Furuichi, Flavia-Corina Mitroi, Mathematical inequalities for some divergences, Physica A 391 (2012), pp. 388-400, DOI:10.1016/j.physa.2011.07.052; ISSN 0378-4371
  • Shigeru Furuichi, Nicuşor Minculete, Flavia-Corina Mitroi, Some inequalities on generalized entropies, J. Inequal. Appl., 2012, 2012:226. DOI: 10.1186/1029-242X-2012-226

Voci correlate

• Autoinformazione
• Compressione dei dati
• Entropia (termodinamica)
• Entropia quantistica
• Negentropia, l'entropia differenziale
• Claude Shannon
• John von Neumann

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'entropia

Collegamenti esterni

• (EN) Entropia / Entropia (altra versione), su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Entropia, su MathWorld, Wolfram Research.
• Entropy and Von Neumann (PDF), su renyi.hu. URL consultato il 22 marzo 2005 (archiviato dall'url originale il 9 maggio 2005).
• Calcolatrice dell'entropia di Shannon (English)
• A Mathematical Theory of Communication Archiviato il 15 luglio 1998 in Internet Archive. Shannon 1948 (English)