Entropia (teoria dell'informazione)

Da Wikipedia, l'enciclopedia libera.

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 possono essere compressi 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 memorizzarla.

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

Informazione contenuta in un evento[modifica | modifica wikitesto]

L'informazione contenuta in un evento x emesso 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 accadesse. 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 {\textstyle b} è la base di numerazione. Significa quindi che l'informazione di un evento può essere vista come la quantità di cifre in base {\textstyle 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[modifica | modifica wikitesto]

L'entropia di una sorgente è definita come il valore atteso dell'autoinformazione, ovvero 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[modifica | modifica wikitesto]

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

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

0 \le \mathbb{H}[X] \le \log_b{N}

Dimostrazione[modifica | modifica wikitesto]

Nella definizione dell'entropia aggiungendo e togliendo {\textstyle  \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)}

Dato che la somma delle dei  \mathbb{P}(x_i)
vale  1
è possibile portare fuori il termine {\textstyle  - \log_b{N}
} ottenendo:

 \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} \le  \frac{1}{\ln b} \cdot (x-1) se si confronta il grafico del logaritmo con la retta tangente a  \log_b{x} in x= 0 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}}} \le \frac{1}{\ln b}\sum_{i=1}^N{ \left(\frac{1}{N} - \mathbb{P}(x_i) \right)} = 1-1 = 0

Ovvero il secondo addendo è sempre minore di  0
e quindi:

 \mathbb{H}[X] \le \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[modifica | modifica wikitesto]

Dato un alfabeto di  N
simboli, la sua efficienza 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[modifica | modifica wikitesto]

Fig.1 - Entropia di una sorgente binaria

L'entropia di una sorgente binaria  X
che ha probabilità p di produrre {\textstyle 1}, probabilità q di produrre {\textstyle 0} e di conseguenza p+q = 1 è semplicemente (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[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".

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Controllo di autorità LCCN: (ENsh85044152 · GND: (DE4743861-7 · BNF: (FRcb11985913j (data)