Utente:Jaconotar/sandbox

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 senza perdita d'informazione. 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).

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 formale

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})$ dei possibili valori 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)\geq 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 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.

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

H(X)\leq \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.

Dimostrazione

Poiché $\log _{e}{x}\leq 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}\leq \log _{2}{e}\sum _{i=1}^{n}p_{i}\left({{1 \over {p_{i}n}}-1}\right)=0

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.

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 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: Definito infatti un insieme di caratteri alfanumerici A={A(1),A(2),A(3),...A(n)} e definita p(i) la probabilità di osservare il simbolo A(i) si definisce infatti H(p(0),p(1),...p(n)) entropia. Essa deve rispettare tre condizioni:

se A(k) ha probabilità p(k)=0 di verificarsi allora H(p(0), p(1),... p(k-1),0) = H(p(0), p(1),... p(k-1))
dati i sistemi indipendenti A e B si ha la subadditività: H(A,B)< H(A)+H(B)
L'entropia H è massima se p(i)=1/r (dove r numero totale di stati)

allora la definizione di Entropia è ben data ed è l'unica possibile.

L'informazione viene matematicamente espressa dalla relazione

\operatorname {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

\operatorname {S} =log_{2}P

che permette di esprimere l'entropia nella medesima unità di misura dell'informazione, ovvero il bit. Notare come P si identifichi con $\Gamma$ .

In conclusione si dimostra che vale la relazione

\operatorname {I} =-S

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

L'applicazione dei concetti di informazione ed entropia risulta molto utile, oltre che nel campo dell'informatica e delle scienze della comunicazione, anche in termodinamica e nell'ambito delle scienze naturali in generale. Consideriamo ad esempio un sistema formato da un solido ionico cristallino: in fase solida gli ioni occuperanno posizioni ben definite all'interno del reticolo e quindi la loro posizione risulterà facilmente identificabile; il sistema sarà caratterizzato da elevata informazione e bassa entropia. Passando via via prima allo stato liquido e poi a quello aeriforme, la posizione dei singoli ioni risulterà non più univoca ma tendente a variare fino alla massima variabilità dello stato aeriforme; di conseguenza l'informazione tende a diminuire mentre l'entropia aumenta fino al valore massimo associato alla fase aeriforme.

Generalizzazioni

Entropia di Rényi

L'entropia di Rényi è una famiglia di funzionali che generalizza l'entropia di Shannon. È definita dalla formula

H_{\alpha }(X)={\frac {1}{1-\alpha }}\log {\left(\sum _{i=1}^{n}{{p_{i}}^{\alpha }}\right)}

per $\alpha \geq 0$ e $\alpha \neq 1$ . È possibile dimostrare che, per $\alpha \rightarrow 1$ , Ciao Sapiens!

Bibliografia

Claude E. Shannon A Mathematical Theory of Communication, 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