Entropia (teoria dell'informazione)

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Entropia di sorgenti senza memoria[modifica | modifica wikitesto]

Fig.1 - Entropia di una sorgente binaria

L'entropia di una variabile aleatoria X è definita come il valore atteso dell'autoinformazione I(X) della variabile aleatoria:

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

Se il numero di valori che può assumere X è finito allora il valore atteso si riduce ad una media dell'autoinformazione di ogni simbolo x_i pesata con la propria probabilità P(x_i)

H(X)= - \sum_{i=1}^n{P(x_i) \cdot \log{P(x_i)}}

Se invece X è una variabile aleatoria continua il valore atteso dell'autoinformazione deve essere calcolato attraverso un integrale:

H(X)= - \int{P(x) \cdot \log{P(x)}} \ dx

L'entropia di una variabile aleatoria continua non condivide tutte le proprietà di quella per variabili discrete, ad esempio H(X) può risultare negativa.

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, e può essere interpretato come il numero di bit necessari in media a memorizzare un simbolo emesso dalla sorgente. Esistono codifiche particolari specializzate sotto questo aspetto, come ad esempio la codifica aritmetica.

Nel caso che P(x_i) = 0 per qualche x_i il contributo all'entropia deve essere calcolato con un limite, in particolare se si fa tendere la probabilità a zero si ottiene il seguente risultato:

\lim_{x \to 0} x \log{x} = 0

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

0 \le H(X) \le \log{n}

Dimostrazione[modifica | modifica wikitesto]

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

Entropia di sorgenti con memoria[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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

H(X)=-\left (p\log{p}+q\log{q} \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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]