Entropia (teoria dell'informazione)

Da Wikipedia, l'enciclopedia libera.

Nota disambigua – Se stai cercando altri significati, vedi Entropia.

Nella teoria dell'informazione - e in rapporto alla teoria dei segnali - l'entropia misura la quantità di incertezza o informazione presente in un segnale aleatorio. Da un altro punto di vista l'entropia è la minima complessità descrittiva di una variabile aleatoria, ovvero il limite inferiore della compressione dei dati. La connessione con l'entropia termodinamica sta nel rapporto di compressione: al diminuire della temperatura corrisponde la riduzione della ridondanza del segnale, e quindi l'aumento della compressione. L'entropia dell'informazione raggiunge un minimo che, in generale è diverso da zero, al contrario dell'entropia termodinamica (vedi terzo principio della termodinamica). 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 a 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" »

Indice

1 Definizione formale
- 1.1 Entropia di sorgenti senza memoria
  - 1.1.1 Dimostrazione
- 1.2 Entropia di sorgenti con memoria
2 Esempi
3 Utilizzi
4 Bibliografia
5 Voci correlate
6 Collegamenti esterni

[modifica] Definizione formale

[modifica] Entropia di sorgenti senza memoria

Fig.1 - Entropia di una sorgente binaria

L'entropia di una variabile aleatoria $X$ è la media dell'autoinformazione $I (x i)$ delle realizzazioni della variabile stessa ( $x 1, x 2,..., x n$ ):

$H(X)=E\left[I\left(x_i\right)\right]=\sum_{i=1}^n{I(x_{i}) \cdot P(x_{i})} = \sum_{i=1}^n{P(x_i) \cdot \log_2{1 \over P(x_i)}}$

La base del logaritmo originariamente utilizzata da Shannon fu quella naturale (che introdusse l'utilizzo di una particolare unità di misura, nat), tuttavia è oggi di uso comune la base 2 in quanto consente di ottenere dei risultati più chiari (in particolare, il valore di entropia ottenuta è misurato in bit).

Si nota molto facilmente che:

$H(X) \ge 0$

L'entropia di una sorgente binaria con probabilità p e 1-p è (vedi Fig.1):

$H(X)=p\log_2{1 \over p}+(1-p)\log_2{1 \over 1-p}$

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 zeri o sempre uni). 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.

Si dimostra che per l'entropia vale sempre la relazione:

$H(X) \le \log_{2}{n}$

dove $n$ è la numerosità dell'alfabeto di messaggi considerati (nel caso della moneta, $n = 2$ ) e quindi rappresenta il numero di casi possibili che si possono verificare.

[modifica] Dimostrazione

Poiché $\log_e{x} \le x-1$ ,

$H(X)-\log_2{n} = \sum_{i=1}^{n} p_i \log_2{1 \over p_i} - \sum_{i=1}^{n} p_i \log_2{n} = \sum_{i=1}^{n} p_i \log_2{ 1 \over p_i n } \le \log_{2}{e}\sum_{i=1}^{n}p_i \left({{1 \over{p_in}}-1}\right) = 0$

L'uguaglianza con il limite superiore si verifica soltanto nel caso in cui i messaggi emessi dalla sorgente siano equiprobabili.

[modifica] Entropia di sorgenti con memoria

L'entropia delle sorgenti con memoria è ragionevolmente minore dell'entropia di una sorgente senza memoria. Infatti i messaggi 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 i bit di bianco/nero di un fax. È chiaro che un bit di bianco sarà probabilmente preceduto da un altro bit di bianco. Si potrebbe quindi pensare di codificare non un singolo bit ma ad esempio coppie di bit. Per quanto detto in precedenza le coppie di bit dello stesso colore hanno una probabilità maggiore di presentarsi, da cui deriva una minore entropia.

[modifica] Esempi

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, ma anche che il suo grado di ordine aumenta, e con esso il nostro livello d'informazione. Al limite, alla temperatura zero, tutte le molecole sono ferme, l'entropia è zero e l'ordine è il massimo possibile, e con esso è massima l'informazione; infatti non esiste più alcuna alternativa fra cui scegliere.

[modifica] 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.).

[modifica] Bibliografia

Giuseppe Arcidiacono, Entropia, sintropia, informazione, Di Renzo Editore, 1991
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
Chen, X., Brent, F., Li, M., McKinnon, B, Seker, A., [http://citeseer.ist.psu.edu/cache/papers/cs/28171/http:zSzzSzwww.cs.ucsb.eduzSz~mlizSzsid.pdf/chen02theory.pdf Shared
Olivier Costa de Beauregard, Irreversibilità, entropia, informazione: il secondo principio della scienza del tempo, Di Renzo Editore, 1994

Information and Program Plagiarism Detection], 2002

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

[modifica] Voci correlate

[modifica] Collegamenti esterni

Entropy and Von Neumann

Categoria: Teorie dell'informatica

See also ebooksgratis.com: no banners, no cookies, totally FREE.