Visualizza wikitesto di Entropia (teoria dell'informazione)

{{torna a|Teoria dell'informazione#Entropia}}
{{NN|informatica|marzo 2015|}}

Nella [[teoria dell'informazione]] l{{'}}'''entropia''' è una misura della quantità di [[informazione]] contenuta in un [[messaggio]] trasferito attraverso un [[canale di comunicazione]].<ref>{{Treccani|v=1|entropia}};<br>{{Treccani|entropia}};<br>{{Treccani|informazione|Informazione}}</ref>
L'[[unità di misura]] tipica di questa [[grandezza fisica|grandezza]] è il [[Bit]].<ref>{{Treccani|bit|Bit}}</ref>

== Storia ==
{{vedi anche|Cronologia della teoria dell'informazione}}

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 [[#entropia di una sorgente di informazione|autoinformazione media]].<ref>{{cita|Shannon 2001}}.</ref>
Tale risultato era implicito nella definizione dell'[[entropia (termodinamica)|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:
{{Citazione|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 intrinseca ===
L'informazione intrinseca di un [[Evento (teoria della probabilità)|evento]], detta anche ''autoinformazione'', è la quantità d'incertezza associata allo stesso.
Più concretamente è l'informazione che si ottiene affermando che tale evento si sia realizzato o meno, rimuovendo quindi l'incertezza associata.
L'autoinformazione è la forma più semplice di entropia definita da Shannon, e costituisce il punto di partenza nella definizione di altri concetti della [[teoria dell'informazione]].

L'ambiguità esistente tra incertezza ed informazione non deve stupire. Esse si presentano infatti come due facce della stessa medaglia: senza incertezza non c'è informazione, e quanta più incertezza c'è nel segnale aleatorio, tanto più informativo è rivelare qual è la determinazione del segnale.

Formalmente, sia <math>X</math> una [[Variabile casuale|sorgente]] di eventi <math>x</math>, l'entropia <math>I</math> associata ad un singolo evento è definita dalla seguente scrittura:

:<math>I(x) = -\log_b p(x)</math>

dove <math>p(x)</math> è la probabilità che l'evento <math>x</math> accada. 

Il logaritmo nasce dal fatto che attraverso la [[notazione posizionale]] è possibile distinguere <math>N</math> eventi equiprobabili con l'utilizzo di sole <math>\log_b N</math> cifre, dove <math>b</math> è la [[Base (aritmetica)|base di numerazione]]. Significa quindi che l'informazione di un evento può essere vista come la quantità di cifre in base <math>b</math> 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à è data dal prodotto delle singole probabilità, si vuole che l'entropia totale sia la somma delle entropie dei singoli eventi.<ref>{{cita|Shannon 2001|p. 1}}.</ref>

=== Entropia di una sorgente di informazione ===
[[File:Binary entropy plot.png|thumb|upright=0.8|Entropia di una variabile di [[Bernoulli]]]]

Nel caso delle sorgenti di informazione, per entropia si intende una grandezza utile a stimare a priori il [[velocità di trasmissione|rateo della quantità di informazione emessa]]. Assunto che non sia possibile conoscere a priori quale [[dato]] verrà emesso in un certo istante, ma solo la sua probabilità, si definisce l'entropia della sorgente come la media pesata dell'[[#informazione intrinseca|autoinformazione]] dei [[simbolo (telecomunicazioni)|simboli]] emissibili rispetto alla loro probabilità di emissione, a meno di una costante positiva di proporzionalità:<ref>{{cita|Shannon 2001|pp. 9-14,27-28}}.</ref>

:<math>H = -K\sum_{i}{ p(x_i) \log{p(x_i)} }.</math>

Nel caso l'[[alfabeto (teoria dei linguaggi formali)|alfabeto]] della sorgente sia costituito di simboli indipendenti, ovvero equiprobabili, l'espressione dell'entropia si riduce a:

:<math>H = -K \sum_{i}{ \log{p(x_i)} }.</math>

Nel caso particolare in cui la sorgente sia del tipo continuo invece che discreto è necessario descrivere l'entropia utilizzando l'espressione [[integrale]] omologa:

:<math>H = -K \int{ p(x) \log{p(x)} } dx.</math>

=== Entropia congiunta ===
{{U|verso=da|Entropia congiunta|Matematica|ottobre 2023}}
[[File:Entropy-mutual-information-relative-entropy-relation-diagram.svg|thumb|upright=0.8|Entropie [[#informazione intrinseca|individuali]] <math>H(X),H(Y)</math>, [[#entropia congiunta|congiunte]] <math>H(X,Y)</math>, e [[#entropia condizionale|condizionali]] per una coppia di sottosistemi correlati <math>X,Y</math> con [[#informazione mutua|informazione mutua]] <math>I(X;Y)</math>.]]

L'entropia congiunta di due variabili aleatorie discrete <math>X</math> e <math>Y</math> è semplicemente l'entropia della coppia: <math>(X,Y)</math>. Questo implica che, se <math>X</math> e <math>Y</math> sono [[indipendenza (probabilità)|indipendenti]], allora la loro entropia congiunta è la somma delle loro entropie individuali.

Per esempio, se <math>(X,Y)</math> rappresenta la posizione di un pezzo di [[scacchi]] (<math>X</math> la riga e <math>Y</math> la colonna), allora l'entropia congiunta della riga e della colonna su cui è posto il pezzo sarà l'entropia della posizione del pezzo.

:<math>H(X,Y) = \mathbb{E}_{X,Y} [-\log p(x,y)] = - \sum_{x,y} p(x,y) \log p(x,y).</math>

Nonostante la notazione simile, l'entropia congiunta non deve essere confusa con l'[[entropia incrociata]].

=== Entropia condizionale ===
{{U|verso=da|Entropia condizionale|Matematica|ottobre 2023}}

L'entropia condizionale è la quantità di informazione necessaria per descrivere il valore di una variabile aleatoria <math>\Chi</math> noto il valore di un'altra variabile aleatoria <math>Y</math>. È anche nota come "equivoco di <math>X</math> con <math>Y</math>".<br>
Nel contesto dei [[canale (telecomunicazioni)|canali di telecomunicazione]] rappresenta l'incertezza rimanente su un [[dato]] in corso di trasmissione, rispetto all'informazione già trasmessa.

Formalmente l'entropia condizionale <math>H</math> di una variabile aleatoria <math>X</math>, data la variabile aleatoria <math>Y</math> è definita dalla seguente scrittura:

:<math>H(X|Y) = \mathbb E_Y [H(X|y)] = -\sum_{y \in Y} p(y) \sum_{x \in X} p(x|y) \log p(x|y) = \sum_{x,y} p(x,y) \log \frac{p(y)}{p(x,y)}.</math>

Un'importante corollario di questa definizione è che l'entropia condizionale si può esprimere come differenza tra l'[[#entropia congiunta|entropia congiunta]] <math>H(X,Y)</math> e l'[[#informazione intrinseca|entropia intrinseca]] di <math>Y</math>.

:<math>H(X|Y) = H(X,Y) - H(Y).</math>

=== Informazione mutua ===
{{vedi anche|Informazione mutua}}

L'informazione mutua è la quantità di informazione su una variabile aleatoria che può essere ricavata osservandone un'altra. In un sistema di comunicazione è importante che sia massimizzata la quantità di informazione condivisa dai segnali inviati e ricevuti. L'informazione mutua di <math>X</math>, relativamente a <math>Y</math> è:

:<math>I(X;Y) = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)\, p(y)}.</math>

Un'importante proprietà dell'informazione mutua è che

:<math>I(X;Y) = H(X) - H(X|Y).</math>

Ossia, conoscendo ''Y'', possiamo risparmiare in media <math>I(X;Y)</math> bit nella codifica di ''X'', rispetto al caso in cui ''Y'' è ignota.

L'informazione mutua è simmetrica;

:<math>I(X;Y) = I(Y;X) = H(X) + H(Y) - H(X,Y).</math>

L'informazione mutua può essere espressa come media della [[Divergenza di Kullback-Leibler|Divergenza di Kullback–Leibler]] della [[probabilità a posteriori]] di ''X'', dato il valore di ''Y'', rispetto alla probabilità a priori di ''X'':

:<math>I(X;Y) = \mathbb E_{p(y)} [D_{\mathrm{KL}}( p(X|Y=y) \| p(X) )].</math>

In altre parole, essa misura quanto, in media, la probabilità della distribuzione ''X'' cambia se conosciamo il valore di ''Y''. Questo è spesso calcolato come divergenza dal prodotto delle distribuzioni marginali rispetto alla vera [[distribuzione di probabilità congiunta|distribuzione congiunta]]:

:<math>I(X; Y) = D_{\mathrm{KL}}(p(X,Y) \| p(X)p(Y)).</math>

L'informazione mutua può essere considerata una statistica per stabilire l'indipendenza tra una coppia di variabili ed ha una distribuzione asintotica ben specificata.

=== Entropia relativa ===
{{vedi anche|Divergenza di Kullback-Leibler}}

L'entropia relativa, anche nota come "divergenza di Kullback-Leible", è un modo per confrontare due distribuzioni: una "vera" [[distribuzione di probabilità]] ''p(X)'' ed una distribuzione arbitraria ''q(X)''. Se comprimiamo dei dati in un qualche modo, per cui ''q(x)'' è la distribuzione seguita dai dati compressi, quando in realtà la distribuzione dei dati è ''p(x)'', la divergenza di Kullback–Leibler è il numero di bit addizionali medi per dato necessari alla compressione. È quindi definita come

:<math>D_{\mathrm{KL}}(p(X) \| q(X)) = \sum_{x \in X} p(x) \log\frac{p(x)}{q(x)}.</math>

== Legame con l'entropia termodinamica ==
{{vedi anche|entropia (termodinamica)}}

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: dato un insieme di caratteri alfanumerici <math>A=\{A(1),A(2),A(3),\ldots,A(n)\}</math> e detta <math>p(i)</math> la probabilità di osservare il simbolo <math>A(i)</math>, si definisce una funzione di entropia <math>\mathbb{H}(p(0),p(1),\ldots, p(n))</math>, che deve rispettare le tre condizioni seguenti:
* se <math>A(k)</math> ha probabilità <math>p(k)=0</math> di verificarsi, allora <math>\mathbb{H}(p(0), p(1),\ldots, p(k-1),0) = \mathbb{H}(p(0), p(1),\ldots, p(k-1))</math>;
* dati i sistemi indipendenti <math>A</math> e <math>B</math>, si ha la seguente condizione di subadditività: <math>\mathbb{H}(A,B)< \mathbb{H}(A)+\mathbb{H}(B)</math>;
* l'entropia <math>\mathbb{H}</math> è massima quando <math>p(i)=1/r</math> (dove <math>r</math> è il numero totale di stati).

Allora si dimostra che tale definizione di entropia <math>\mathbb{H}</math> è ben posta ed è l'unica possibile.

L'informazione viene matematicamente espressa dalla relazione

:<math>I = -\log_2 P</math>

che, utilizzando il [[logaritmo]] in base 2 della [[probabilità]] <math>P</math> che si verifichi un dato evento, permette di ottenere un valore misurato in [[Bit (informatica)|bit]]. 1 bit equivale ad esempio all'informazione ottenibile dal lancio di una moneta (<math>P = 0,5</math>).

Dall'entropia espressa dalla relazione di Boltzmann è facile ricavare l'uguaglianza

:<math>S = \log_2 P</math>

che permette di esprimere l'entropia nella medesima unità di misura dell'informazione, ossia il bit. Notare come <math>P</math> si identifichi con <math>\Gamma</math>. In conclusione si dimostra che vale la relazione

:<math>I = -S</math>

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

===Il secondo principio della termodinamica nei sistemi quantistici isolati===
L'entropia di Shannon è la definizione appropriata di entropia da applicarsi ai sistemi quantistici completamente isolati dall'ambiente circostante. Essa consente di modellare per questi ultimi il [[secondo principio della termodinamica]]<ref>{{Cita pubblicazione|nome=Florian|cognome=Meier|nome2=Tom|cognome2=Rivlin|nome3=Tiago|cognome3=Debarba|data=2025-01-14|titolo=Emergence of a Second Law of Thermodynamics in Isolated Quantum Systems|rivista=PRX Quantum|volume=6|numero=1|p=010309|accesso=2025-02-08|doi=10.1103/PRXQuantum.6.010309|url=https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.6.010309}}</ref><ref>{{Cita web|lingua=en|autore=Vienna University of Technology|url=https://phys.org/news/2025-01-quantum-theory-thermodynamics-contradiction-entropy.html|titolo=Quantum theory and thermodynamics: No contradiction with new entropy definition, study says|sito=phys.org|accesso=2025-02-08}}</ref><ref>{{Cita web|lingua=en|url=https://www.sciencedaily.com/releases/2025/01/250129115500.htm|titolo=Even quantum physics obeys the law of entropy|sito=ScienceDaily|accesso=2025-02-08}}</ref>. Ad esempio, per lo [[spin]] di un [[elettrone]], che può essere orientato verso l'alto o verso il basso, si avrà:<ref>{{Cita web|lingua=it-it|autore=HDblog.it|url=https://www.hdblog.it/curiosita/articoli/n607949/entropia-quantistica-seconda-legge-termodinamica/|titolo=Le leggi dell'entropia si applicano anche al mondo quantistico, lo afferma uno studio|sito=HDblog.it|data=2025-02-06|accesso=2025-02-08}}</ref>
{{citazione|Se esiste un solo possibile risultato di misurazione che si verifica con certezza del 100%, l'entropia di Shannon è zero. Non ci sarà alcuna sorpresa nel risultato e non si apprenderà nulla di nuovo. Se invece ci sono molti valori possibili con probabilità simili, l'entropia di Shannon è elevata.}}

== Grandezze associate ==
=== Efficienza di un alfabeto ===
Dato un alfabeto di <math>N</math> simboli, la sua entropia <math>\log_b(N)</math> 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 <math>N</math> simboli:

:<math>\eta[X] = \frac{-\sum_{i=1}^N{ \mathbb{P}(x_i) \cdot \log_b{\mathbb{P}(x_i)}}}{\log_b{N}}.</math>

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 ==
[[File:Binary entropy plot.svg|thumb|Fig.1 - Entropia di una sorgente binaria]]

L'entropia di una sorgente binaria <math>X</math> che ha probabilità <math>p</math> di produrre <math>1</math>, probabilità <math>q</math> di produrre <math>0</math> e di conseguenza <math>p+q = 1</math> è (vedi Fig. 1):

:<math>\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].</math>

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.

== Note ==
<references/>

== Bibliografia ==
* {{cita pubblicazione
|titolo  = A mathematical theory of communication
|autore  = [[Claude Elwood Shannon]]
|rivista = ACM SIGMOBILE Mobile Computing and Communications Review
|volume  = 5
|numero  = 1
|editore = [[Association for Computing Machinery]]
|città   = New York (NY, USA)
|data    = 1 gennaio 2001
|annooriginale = prima pubblicazione 1948
|lingua  = en
|issn    = 1559-1662
|doi     = 10.1145/584091.584093
|cid     = Shannon 2001
}}

* {{cita pubblicazione
|titolo  = Transmission of information; a statistical theory of communications
|url  = https://archive.org/details/transmissionofin0000fano
|autore  = [[Robert Mario Fano]]
|editore = MIT Press
|anno    = 1961
|lingua  = en
}}

* {{cita pubblicazione
|titolo  = Telecomunicazioni per l'ingegneria gestionale. Codifica di sorgente. Mezzi di trasmissione. Collegamenti
|autore1 = R. Bonazzi
|autore2 = R. Catena
|autore3 = S. Collina
|autore4 = L. Formica
|autore5 = A. Munna
|autore6 = D. Tesini
|editore = Pitagora Editrice
|anno    = 2004
|ISBN    = 88-371-1561-X
}}

* {{cita pubblicazione
|titolo = A theory of uncheatable program plagiarism detection and its practical implementation
|autore1 = Xin Chen
|autore2 = Brent Francia
|autore3 = Ming Li
|autore4 = Brian McKinnon
|autore5 = Amit Seker
|url     = http://citeseer.ist.psu.edu/cache/papers/cs/28171/http:zSzzSzwww.cs.ucsb.eduzSz~mlizSzsid.pdf/chen02theory.pdf
|data    = 5 maggio 2002
|accesso = 15 dicembre 2008
|lingua  = en
}}

* {{cita pubblicazione
|titolo  = Irreversibilità, entropia, informazione: il secondo principio della scienza del tempo
|autore  = [[Olivier Costa de Beauregard]]
|editore = Di Renzo Editore
|anno    = 1994
}}

* {{cita libro
|titolo   = Elements of Information Theory
|url   = https://archive.org/details/elementsofinform0000cove_m4w2
|autore   = Thomas M. Cover
|autore2  = Joy A. Thomas
|editore  = Wiley
|città    = Hoboken (NJ, USA)
|anno     = 2006
|edizione = 2
|lingua   = en
|ISBN     = 978-0-471-24195-9
}}

* {{cita pubblicazione
|titolo = Improved Detection Of Similarities In Computer Program And Other Texts
|autore = [[Michael Wise]]
|url    = http://citeseer.ist.psu.edu/cache/papers/cs/2964/ftp:zSzzSzftp.cs.su.oz.auzSzmichaelwzSzdoczSzyap3.pdf/wise96yap.pdf
|anno   = 1996
|lingua = en
}}

* {{cita pubblicazione
|titolo  = Energy and information
|autore1 = M. Tribus
|autore2 = E.C. McIrvine 
|rivista = [[Scientific American]]
|numero  = 224
|pp      = 178-184
|editore = Nature Publishing Group
|anno    = 1971
|lingua  = en
}}

* {{cita pubblicazione
|titolo  = On some properties of Tsallis hypoentropies and hypodivergences
|autore1 = Shigeru Furuichi
|autore2 = Flavia-Corina Mitroi-Symeonidis
|autore3 = Eleutherius Symeonidis
|rivista = [[Entropy (rivista)|Entropy]]
|numero  = 16
|editore = MDPI
|data    = 15 ottobre 2014
|ISSN    = 5377-5399
|DOI     = 10.3390/e16105377
|lingua  = en
}}

* {{Cita pubblicazione
|titolo  = Mathematical inequalities for some divergences
|autore1 = Shigeru Furuichi
|autore2 = Flavia-Corina Mitroi-Symeonidis
|rivista = Physica A: Statistical Mechanics and its Applications
|numero  = 391
|pp      = 388-400
|editore = Science Direct
|ISSN    = 0378-4371
|DOI     = 10.1016/j.physa.2011.07.052
|anno    = 2012
|lingua  = en
}}

* {{cita pubblicazione
|titolo  = Some inequalities on generalized entropies
|autore1 = Shigeru Furuichi
|autore2 = Nicuşor Minculete
|autore3 = Flavia-Corina Mitroi-Symeonidis
|rivista = Journal of Inequalities and Applications
|numero  = 2012:226
|editore = Springer
|anno    = 2012
|DOI     = 10.1186/1029-242X-2012-226
|lingua  = en
}}

* {{cita pubblicazione
|autore  = Dènes Petz
|titolo  = Entropy, von Neumann and the von Neumann entropy
|rivista = John von Neumann and the Foundations of Quantum Physics
|editore = Kluwer Academic Publishers
|città   = Dordrecht
|anno    = 2001
|url     = http://www.renyi.hu/~petz/7vn.pdf
|urlmorto     = sì
|urlarchivio  = https://web.archive.org/web/20050509160627/http://www.renyi.hu/~petz/7vn.pdf
|dataarchivio = 9 maggio 2005
|accesso = 22 marzo 2005
|ISBN    = 0792368126
|ISSN    = 1355-2198
|DOI     = 10.1016/S1355-2198(03)00070-4
|lingua  = en
}}

== Voci correlate ==
* [[Entropia]]
* [[Negentropia]], l'entropia differenziale
* [[Compressione dei dati]]
* [[Claude Shannon]]
* [[John von Neumann]]

== Altri progetti ==
{{interprogetto|preposizione=sull'|wikt=entropia}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{cita web
|autore = Lukasz Kozlowski
|titolo = Shannon entropy calculator
|url    = http://www.shannonentropy.netmark.pl
|lingua = en
}}

{{Metodi di compressione}}

{{Controllo di autorità}}
{{Portale|informatica|matematica}}

[[Categoria:Teoria dell'informazione]]