Informazione mutua

Da Wikipedia, l'enciclopedia libera.
Entropia individuale (H(X),H(Y)), congiunta (H(X,Y)) e condizionale per un paio di sottosistemi X,Y correlati con informazione mutua I(X; Y).

Nella teoria della probabilità e nella teoria dell'informazione, l'informazione mutua o mutua informazione (talvolta nota con il termine arcaico di transinformazione) di due variabili casuali è una quantità che misura la mutua dipendenza delle due variabili. La più comune unità di misura della mutua informazione è il bit, quando si usano i logaritmi in base 2.

Definizione dell'informazione mutua[modifica | modifica sorgente]

Formalmente, l'informazione mutua di due variabili casuali discrete X e Y può essere definita come:

 I(X;Y) = \sum_{y \in Y} \sum_{x \in X} 
                 p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)}
                              \right) }, \,\!

dove p(x,y) è la funzione di distribuzione di probabilità congiunta di X e Y, e p_1(x) e p_2(y) sono le funzioni di distribuzione di probabilità marginale rispettivamente di X e Y.

Nel caso continuo, la sommatoria è sostituita da un integrale doppio definito:

 I(X;Y) = \int_Y \int_X 
                 p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)}
                              \right) } \; dx \,dy,

dove p(x,y) è ora la funzione di "densità" di probabilità congiunta di X e Y, e p_1(x) e p_2(y) sono le funzioni di densità di probabilità marginale rispettivamente di X e Y.

Queste definizioni sono ambigue perché la base della funzione logaritmica non è specificata. Per disambiguare, la funzione I potrebbe essere parametrizzata come I(X,Y,b) dove b è la base. Alternativamente, poiché la più comune unità di misura della mutua informazione è il bit, potrebbe essere specificata una base di 2.

Intuitivamente, l'informazione mutua misura l'informazione che X e Y condividono: essa misura quanto la conoscenza di una di queste variabili riduce la nostra incertezza riguardo all'altra. Ad esempio, se X e Y sono indipendenti, allora la conoscenza di X non dà alcuna informazione riguardo a Y e viceversa, perciò la loro mutua informazione è zero. All'altro estremo, se X e Y sono identiche allora tutte le informazioni trasmesse da X sono condivise con Y: la conoscenza di X determina il valore di Y e viceversa. Come risultato, nel caso di identità l'informazione mutua è la stessa contenuta in Y (o X) da sola, vale a dire l'entropia di Y (o X: chiaramente se X e Y sono identiche, hanno identica entropia).

L'informazione mutua quantifica la dipendenza tra la distribuzione congiunta di X e Y e quale sarebbe la distribuzione congiunta se X e Y fossero indipendenti. L'informazione mutua è una misura di dipendenza nel seguente senso: I(X; Y) = 0 se e solo se X e Y sono variabili casuali indipendenti. Questo è facile da vedere in una sola direzione: se X e Y sono indipendenti, allora p(x,y) = p(x) p(y), e perciò:

 \log{ \left( \frac{p(x,y)}{p(x)\,p(y)} \right) } = \log 1 = 0. \,\!

Inoltre, la mutua informazione è non negativa (cioè I(X;Y) ≥ 0; vedi sotto) e simmetrica (cioè I(X;Y) = I(Y;X)).

Relazione con altre quantità[modifica | modifica sorgente]

L'informazione mutua può essere espressa in modo equivalente come


\begin{align}
I(X;Y) & {} = H(X) - H(X|Y) \\ 
& {} = H(Y) - H(Y|X) \\ 
& {} = H(X) + H(Y) - H(X,Y) \\
& {} = H(X,Y) - H(X|Y) - H(Y|X)
\end{align}

dove H(X) e H(Y) sono le entropie marginali, H(X|Y) e H(Y|X) sono le entropie condizionali, e H(X,Y) è l'entropia congiunta di X e Y. Poiché H(X) ≥ H(X|Y), questa caratterizzazione è coerente con la proprietà di non negatività enunciata sopra.

Intuitivamente, se l'entropia H(X) è considerata una misura dell'incertezza riguardo a una variabile casuale, allora H(X|Y) è una misura di ciò che Y non dice riguardo a X. Questo è "l'ammontare di incertezza che rimane riguardo a X dopo che Y è noto", e così il lato destro di queste uguaglianze può essere letto come "l'ammontare di incertezza in X, meno l'ammontare di incertezza in X che rimane dopo che Y è noto", che è equivalente "all'ammontare di incertezza in X che è eliminato conoscendo Y". Questo corrobora il significato intuitivo di informazione mutua come l'ammontare di informazione (cioè, la riduzione di incertezza) che la conoscenza di una delle due variabili fornisce riguardo all'altra.

Si noti che nel caso discreto H(X|X) = 0 e perciò H(X) = I(X;X). Così I(X;X) ≥ I(X;Y), e si può formulare il principio basilare che una variabile contiene almeno altrettanta informazione riguardo a sé stessa di quanta ne può fornire una qualsiasi altra variabile.

L'informazione mutua può essere espressa anche come una divergenza di Kullback-Leibler, del prodotto p(x) × p(y) della distribuzioni marginali delle due variabili casuali X e Y, per p(x,y), la distribuzione congiunta delle variabili casuali:

 I(X;Y) = D_{\mathrm{KL}}(p(x,y)\|p(x)p(y)).

Inoltre, sia p(x|y) = p(x, y) / p(y). Allora


\begin{align}
I(X;Y) & {} = \sum_y p(y) \sum_x p(x|y) \log_2 \frac{p(x|y)}{p(x)} \\
& {} =  \sum_y p(y) \; D_{\mathrm{KL}}(p(x|y)\|p(x)) \\
& {} = \mathbb{E}_Y\{D_{\mathrm{KL}}(p(x|y)\|p(x))\}.
\end{align}

Così l'informazione mutua può essere intesa anche come l'aspettativa della divergenza di Kullback-Leibler della distribuzione univariata p(x) di X dalla distribuzione condizionale p(x|y) di X data Y: più le distribuzioni p(x|y) e p(x) sono differenti, maggiore è il guadagno di informazione.

Variazioni dell'informazione mutua[modifica | modifica sorgente]

Sono state proposte parecchie variazioni sull'informazione mutua per adattarsi a varie necessità. Tra queste vi sono varianti normalizzate e generalizzazioni a più di due variabili.

Metrica[modifica | modifica sorgente]

Molte applicazioni richiedono una metrica, cioè, una misura di distanza tra punti. La quantità

d(X,Y) = H(X,Y) - I(X;Y) = H(X) + H(Y) - 2I(X;Y) = H(X|Y) + H(Y|X)

soddisfa le proprietà basilari di una metrica; in particolare, la disuguaglianza triangolare, ma anche la non negatività, indiscernibilità e simmetria. Questa metrica della distanza è nota anche come variazione dell'informazione.

Poiché si ha d(X,Y) \le H(X,Y), una variante normalizzata naturale è

D(X,Y) = d(X,Y)/H(X,Y) \le 1.

La metrica D è una metrica universale, in quanto se qualsiasi altra misura pone vicino X e Y, allora anche la D le stimerà vicine.[1]

Un'interpretazione dell'informazione secondo la teoria degli insiemi (si veda la figura per l'entropia condizionale) mostra che

D(X,Y) = 1-I(X;Y)/H(X,Y)  = 1 - H(X \cap Y)/H(X \cup Y)

che è effettivamente la distanza di Jaccard tra X e Y.

Informazione mutua condizionale[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Informazione mutua condizionale.

A volte è utile esprimere l'informazione mutua di due variabili casuali condizionate a una terza.

I(X;Y|Z) = \mathbb E_Z \big(I(X;Y)|Z\big)
    = \sum_{z\in Z} \sum_{y\in Y} \sum_{x\in X}
      p_Z(z) p_{X,Y|Z}(x,y|z) \log \frac{p_{X,Y|Z}(x,y|z)}{p_{X|Z}(x|z)p_{Y|Z}(y|z)},

che possono essere semplificate come

I(X;Y|Z) = \sum_{z\in Z} \sum_{y\in Y} \sum_{x\in X}
      p_{X,Y,Z}(x,y,z) \log \frac{p_Z(z)p_{X,Y,Z}(x,y,z)}{p_{X,Z}(x,z)p_{Y,Z}(y,z)}.

Il condizionamento a una terza variabile casuale potrebbe o aumentare o diminuire l'informazione mutua, ma è sempre vero che

I(X;Y|Z) \ge 0

per le variabili casuali discrete, distribuite congiuntamente X, Y, Z. Questo risultato è stato utilizzato come mattone basilare per provare altre disuguaglianze nella teoria dell'informazione.

Informazione mutua multivariata[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Informazione mutua multivariata.

Sono state proposte parecchie generalizzazioni della informazione mutua a più di due variabili, come la correlazione totale e l'informazione sulle interazioni. Se Shannon è vista come una misura con segno nel contesto dei diagrammi dell'informazione come spiegato nella voce Teoria dell'informazione e teoria della misura, allora l'unica definizione di informazione mutua multivariata [senza fonte] è come segue:

I(X_1;X_1) = H(X_1)

e per n > 1,

I(X_1;\,...\,;X_n) = I(X_1;\,...\,;X_{n-1}) - I(X_1;\,...\,;X_{n-1}|X_n),

dove (come sopra) definiamo

I(X_1;\,...\,;X_{n-1}|X_n) = \mathbb E_{X_n} \big(I(X_1;\,...\,;X_{n-1})|X_n\big).

(Questa definizione dell'informazione mutua multivariata è identica a quella dell'informazione sulle interazioni tranne che per un cambiamento di segno dove il numero delle variabili casuali è dispari.)

Applicazioni[modifica | modifica sorgente]

Applicare pedissequamente i diagrammi dell'informazione per derivare la definizione di cui sopra[senza fonte] è stato criticato, e in effetti ha trovato applicazione pratica piuttosto limitata, poiché è difficile visualizzare o afferrare il significato di questa quantità per un gran numero di variabili casuali. Può essere zero, positivo o negativo per qualsiasi n \ge 3.

Uno schema di generalizzazione ad alta dimensione che massimizza l'informazione mutua tra la distribuzione congiunta e altre variabili obiettivo si trova essere utile nella selezione delle caratteristiche.[2]

Varianti normalizzate[modifica | modifica sorgente]

Varianti normalizzate dell'informazione mutua sono fornite dal coefficiente di vincolo (Coombs, Dawes & Tversky, 1970) o dal coefficiente d'incertezza (Press & Flannery, 1988)


C_{XY}=\frac{I(X;Y)}{H(Y)} ~~~~\mbox{and}~~~~ C_{YX}=\frac{I(X;Y)}{H(X)}.

I due coefficienti non sono necessariamente uguali. Una misura d'informazione scalata più utile e simmetrica è la ridondanza[senza fonte]

R= \frac{I(X;Y)}{H(X)+H(Y)}

che raggiunge un minimo di zero quando le variabili sono indipendenti e un valore massimo di

R_{\max }=\frac{\min (H(X),H(Y))}{H(X)+H(Y)}

quando una variabile diventa completamente ridondante con la conoscenza dell'altra. Si veda anche Ridondanza (teoria dell'informazione). Un'altra misura simmetrica è l'incertezza simmetrica (Witten & Frank, 2005), data da

U(X,Y) = 2R = 2 \frac{I(X;Y)}{H(X)+H(Y)}

che rappresenta una media ponderata dei due coefficienti d'incertezza (Press & Flannery, 1988).

Altre versioni normalizzate sono fornite dalle seguenti espressioni (Yao, 2003; Strehl & Ghosh, 2002).


\frac{I(X;Y)}{\operatorname{min}(H(X),H(Y))}, ~~~~~~~ \frac{I(X;Y)}{H(X,Y)}, ~~~~~~~ \frac{I(X;Y)}{\sqrt{H(X)H(Y)}}

Se consideriamo la mutua informazione come un caso speciale della correlazione totale, la normalizzazione è:


\frac{I(X;Y)}{\operatorname{min}(H(X),H(Y))}

La quantità

D^\prime(X,Y)=1-\frac{I(X;Y)}{\operatorname{max}(H(X),H(Y))}

è una metrica, cioè soddisfa la disuguaglianza triangolare ecc. La metrica D^\prime è anche una metrica universale.[3]

Varianti ponderate[modifica | modifica sorgente]

Nella formulazione tradizionale dell'informazione mutua,

 I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log \frac{p(x,y)}{p(x)\,p(y)},

ciascun evento od oggetto specificato da (x,y) è ponderato mediante la probabilità corrispondente p(x,y). Questo assume che tutti gli oggetti o eventi siano equivalenti a parte la loro probabilità di occorrenza. Tuttavia, in alcune applicazioni potrebbe accadere che certi oggetti o eventi siano più significativi di altri, o che certi schemi di associazione siano semanticamente più importanti di altri.

Ad esempio, la mappatura deterministica \{(1,1),(2,2),(3,3)\} potrebbe essere considerata più forte della mappatura deterministica \{(1,3),(2,1),(3,2)\}, sebbene queste relazioni produrrebbero la stessa informazione mutua. Ciò accade perché l'informazione mutua non è affatto sensibile ad alcun ordinamento insito nei valori delle variabili (Cronbach, 1954; Coombs & Dawes, 1970; Lockhead, 1970), e perciò non è affatto sensibile alla forma della relazione tra le variabili associate. Se si deesidera che la precedente relazione — che mostrava accordo su tutti i valori delle variabili — sia stimata più forte della relazione successiva, allora è possibile utilizzate la seguente informazione mutua ponderata (Guiasu, 1977)

 I(X;Y) = \sum_{y \in Y} \sum_{x \in X} w(x,y) p(x,y) \log \frac{p(x,y)}{p(x)\,p(y)},

che pone un peso w(x,y) sulla probabilità di ogni co-occorrenza dei valori delle variabili, p(x,y). Questo consente che certe probabilità possano portate più o meno significato di altre, con ciò permettendo la quantificazione dei relativi fattori olistici o pregnanti. Nell'esempio di sopra, utilizzare pesi realtivi più grandi per w(1,1), w(2,2) e w(3,3) avrebbe l'effetto di valutare maggiore informatività per la relazione \{(1,1),(2,2),(3,3)\} che per la relazione \{(1,3),(2,1),(3,2)\}, il che potrebbe essere desiderabile in alcuni casi di riconoscimento degli schemi, e simili. Tuttavia, sono stati realizzati pochi studi matematici sull'informazione mutua ponderata.

Informazione mutua assoluta[modifica | modifica sorgente]

Usando i concetti della complessità di Kolmogorov, si può considerare l'informazione mutua di due sequenze indipendente da qualsiasi distribuzione di probabilità:


I_K(X;Y) = K(X) - K(X|Y).

Stabilire che questa quantità è simmetrica fino ad un fattore logaritmico (I_K(X;Y) \approx I_K(Y;X)) richiede la regola della catena per la complessità di Kolmogorov (Li, 1997). Si possono usare approssimazioni di questa quantità attraverso la compressione per definire una misura di distanza per eseguire un clustering gerarchico di sequenze senza avere alcuna conoscenza del dominio delle sequenze stesse (Cilibrasi, 2005).

Applicazioni dell'informazione mutua[modifica | modifica sorgente]

In molte applicazioni, si vuole massimizzare la mutua informazione (accrescendo così le dipendenze), il che è spesso equivalente a minimizzare l'entropia condizionale. Gli esempi comprendono:

Note[modifica | modifica sorgente]

  1. ^ Alexander Kraskov, Harald Stögbauer, Ralph G. Andrzejak, and Peter Grassberger, "Hierarchical Clustering Based on Mutual Information", (2003) ArXiv q-bio/0311039
  2. ^ Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze, An Introduction to Information Retrieval, Cambridge University Press, 2008, ISBN 0-521-86571-9.
  3. ^ Kraskov, et al. ibid.

Bibliografia[modifica | modifica sorgente]

  • R. Cilibrasi, Paul Vitányi, Clustering by compression (PDF) in IEEE Transactions on Information Theory, vol. 51, nº 4, 2005, pp. 1523–1545, DOI:10.1109/TIT.2005.844059.
  • Coombs, C. H., Dawes, R. M. & Tversky, A. (1970), Mathematical Psychology: An Elementary Introduction, Prentice-Hall, Englewood Cliffs, NJ.
  • Cronbach L. J. (1954). On the non-rational application of information measures in psychology, in H Quastler, ed., Information Theory in Psychology: Problems and Methods, Free Press, Glencoe, Illinois, pp. 14–30.
  • Kenneth Ward Church and Patrick Hanks. Word association norms, mutual information, and lexicography, Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics, 1989.
  • Guiasu, Silviu (1977), Information Theory with Applications, McGraw-Hill, New York.
  • Ming Li, Paul Vitányi, An introduction to Kolmogorov complexity and its applications, New York, Springer-Verlag, 1997, ISBN 0-387-94868-6.
  • Lockhead G. R. (1970). Identification and the form of multidimensional discrimination space, Journal of Experimental Psychology 85(1), 1-10.
  • Athanasios Papoulis. Probability, Random Variables, and Stochastic Processes, second edition. New York: McGraw-Hill, 1984. (See Chapter 15.)
  • Press, W. H., Flannery, B. P., Teukolsky, S. A. & Vetterling, W. T. (1988), Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, Cambridge, p. 634
  • Alexander Strehl, Joydeep Ghosh, Cluster ensembles -- a knowledge reuse framework for combining multiple partitions (PDF) in Journal of Machine Learning Research, vol. 3, 2002, pp. 583–617, DOI:10.1162/153244303321897735.
  • Witten, Ian H. & Frank, Eibe (2005), Data Mining: Practical Machine Learning Tools and Techniques, Morgan Kaufmann, Amsterdam.
  • Yao, Y. Y. (2003) Information-theoretic measures for knowledge discovery and data mining, in Entropy Measures, Maximum Entropy Principle and Emerging Applications , Karmeshu (ed.), Springer, pp. 115–136.
  • Peng, H.C., Long, F., and Ding, C., "Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 8, pp. 1226–1238, 2005. Program
  • Andre S. Ribeiro, Stuart A. Kauffman, Jason Lloyd-Price, Bjorn Samuelsson, and Joshua Socolar, (2008) "Mutual Information in Random Boolean models of regulatory networks", Physical Review E, Vol.77, No.1. arXiv:0707.3642.
  • N.X. Vinh, Epps, J. and Bailey, J., 'Information Theoretic Measures for Clusterings Comparison: Is a Correction for Chance Necessary?', in Proc. the 26th International Conference on Machine Learning (ICML'09), PDF.
  • W.M. III Wells, Viola, P., Atsumi, H., Nakajima, S., Kikinis, R., Multi-modal volume registration by maximization of mutual information (PDF) in Medical Image Analysis, vol. 1, nº 1, 1996, pp. 35–51, DOI:10.1016/S1361-8415(01)80004-9, PMID 9873920.

Voci correlate[modifica | modifica sorgente]