Vzájemná informace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Vztah mezi entropiemi H(X) a H(Y), sdruženou entropií H(X,Y), podmíněnou entropií H(X|Y), H(Y|X) a vzájemnou informací I(X; Y) pro dvojici náhodných proměnných X, Y.

Vzájemná informace (anglicky Mutual information, MI) nebo (dříve) transinformace dvou náhodných proměnných je v teorii pravděpodobnosti a teorii informace míra vzájemné závislosti proměnných. Obvyklou jednotkou pro měření vzájemné informace je jeden bit.

Definice vzájemné informace[editovat | editovat zdroj]

Formálně lze vzájemnou informaci dvou diskrétních náhodných proměnných X a Y definovat jako:

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

kde p(x,y) je sdružená distribuční funkce proměnných X a Y a p(x) resp. p(y) jsou marginální distribuční funkce proměnných X resp. Y.

V případě spojité náhodné proměnné je sumace nahrazena určitým dvojným integrálem:

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

kde p(x,y) je sdružená hustota pravděpodobnosti X a Y, a p(x) resp. p(y) jsou marginální hustoty pravděpodobností X resp. Y.

Jestliže použijeme logaritmus o základu 2, bude jednotkou vzájemné informace bit.

Intuitivně je vzájemná informace mírou informace, kterou sdílí náhodné proměnné X a Y: udává, do jaké míry znalost jedné z těchto proměnných snižuje nejistotu o druhé. Pokud jsou náhodné proměnné X a Y nezávislé, což znamená, že znalost X nedává žádnou informaci o Y a naopak, pak jejich vzájemná informace je nulová. Opačným extrémem je, když X je deterministickou funkcí Y a Y je deterministickou funkcí X; pak veškerá informace nesená náhodnou proměnnou X je sdílená s Y, a proto znalost X určuje hodnotu Y a naopak. Důsledkem toho je, že v tomto případě vzájemná informace je totéž jako nejistota obsažená v Y (nebo X) samotné, čili entropie Y (nebo X). Navíc tato vzájemná informace je stejná jako entropie X, i jako entropie Y. (Velmi speciálním případem této situace je, když X a Y jsou ve skutečnosti stejnou náhodnou proměnnou.)

Vzájemná informace je míra nedílné závislosti vyjádřená sdruženým rozdělením náhodných proměnných X a Y vztaženým ke sdruženému rozdělení proměnných X a Y, kdyby byly nezávislé. Vzájemná informace proto měří závislost v následujícím smyslu: I(X; Y) = 0 právě tehdy, když X a Y jsou nezávislé náhodné proměnné. To je dobře vidět v jednom směru:, jestliže X a Y jsou nezávislé, pak p(x,y) = p(x) p(y) a proto:

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

Vzájemná informace je vždy nezáporná (tj. I(X;Y) ≥ 0; viz níže) a symetrická (tj. I(X;Y) = I(Y;X)).

Vztah k jiným veličinám[editovat | editovat zdroj]

Vzájemnou informaci lze ekvivalentně vyjádřit jako


\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}

kde H(X) a H(Y) jsou marginální entropie, H(X|Y) a H(Y|X) jsou podmíněné entropie a H(X,Y) je sdružená entropie X a Y. Při použití Jensenovy nerovnosti na definici vzájemné informace můžeme ukázat, že I(X;Y) je nezáporná, a odtud \ H(X) \ge H(X|Y).

Intuitivně: pokud entropii H(X) chápeme jako míru nejistoty hodnoty náhodné proměnné, pak H(X|Y) je míra toho, co Y neříká o X. To je „množství zbývající nejistoty o X, když je Y známé“ a proto pravou stranu první z těchto rovnic můžeme číst jako „množství nejistoty v X, minus množství nejistoty v X, která zůstává, když je Y známé“, což je totéž jako „množství nejistoty o X, když je odstraněna znalost Y“. To potvrzuje intuitivní význam vzájemné informace jako množství informace (tj. snížení nejistoty), které znalost jedné proměnná poskytuje o druhé.

Všimněte si, že v diskrétním případě H(X|X) = 0, a proto H(X) = I(X;X). Tedy I(X;X) ≥ I(X;Y) a můžeme formulovat základní princip, že každá náhodná proměnná obsahuje nejméně tolik informace o sobě jako libovolná jiná proměnná.

Vzájemnou informaci lze také vyjádřit Kullbackovou-Leiblerovou divergencí součinu p(x) × p(y) marginálních rozdělení náhodných proměnných X a Y, a sdruženého rozdělení náhodných proměnných p(x,y):

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

Pokud označíme p(x|y) = p(x, y) / p(y), pak


\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}

neboli vzájemnou informaci můžeme také chápat jako očekávánou hodnotu Kullbackovy-Leiblerovy divergence jednorozměrného rozdělení p(x) X a podmíněného rozdělení pravděpodobnosti p(x|y) náhodné proměnné X pro Y: čím rozdílnější jsou distribuce p(x|y) a p(x), tím větší je informační zisk.

Varianty vzájemné informace[editovat | editovat zdroj]

Bylo navrženo několik variant vzájemné informace pro různé speciální potřeby. Patří mezi ně normalizované varianty a zobecnění na více než dvě proměnné.

Metrika[editovat | editovat zdroj]

Mnoho aplikací vyžaduje metriku, tj. míru vzdálenosti mezi body. Hodnota

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

splňuje podmínky pro metriku (trojúhelníková nerovnost, nezápornost, identita nerozlišitelných a symetrie). Tato vzdálenostní metrika je také známa jako variace informace.

Protože platí d(X,Y) \le H(X,Y), lze tuto metriku přirozeně normalizovat:

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

Metrika D je univerzální metrikou v tom smyslu, že pokud libovolná jiná míra vzdálenosti říká, že X a Y si jsou blízké, pak také D o nich bude tvrdit, že si jsou blízké[1].

Množinově teoretická interpretace vzájemné informace (viz obrázek pro podmíněnou entropii) ukazuje, že

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

což je efektivně Jaccardova vzdálenost mezi X a Y.

Podmíněná vzájemná informace[editovat | editovat zdroj]

Někdy je užitečné vyjádřit vzájemnou informaci dvou náhodných proměnných podmíněnou třetí proměnnou:

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)},

což lze zjednodušit na

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)}.

Podmínění třetí náhodnou proměnnou může vzájemnou informaci zvýšit i snížit, ale vždy platí, že

I(X;Y|Z) \ge 0

pro diskrétní, sdruženě distribuované náhodné proměnné X, Y, Z. Tento výsledek slouží jako základní stavební blok pro důkaz dalších nerovností v teorii informace.

Vícerozměrná vzájemná informace[editovat | editovat zdroj]

Bylo navrženo několik zobecnění vzájemné informace na více než dvě náhodné proměnné, jako například celková korelace a interakce informace. Jestliže na Shannonovu entropii pohlížíme jako na znaménkovou míru v kontextu informačních diagramů, jak je vysvětleno v článku Teorie informace a teorie míry, pak jediná definice vícerozměrné vzájemné informace, které dává smysl, je tato:

I(X_1;X_1) = H(X_1)

a pro n > 1,

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

kde (jak je uvedeno výše) definujeme

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

Tato definice vícerozměrné vzájemné informace je identická (až na znaménko, když je počet náhodných proměnných lichý) s definicí interakční informace.

Jestliže A a B jsou dvě množiny proměnných, pak vzájemná informace mezi nimi je:

I(A,B) = H(A\cup B)+H(A\cap B) - H(A) - H(B),

Aplikace[editovat | editovat zdroj]

Slepé použití informačních diagramů k odvození výše uvedené definice bylo kritizováno a opravdu se ukázalo, že jeho použití je dosti omezené, protože je obtížné vizualizovat nebo pochopit význam této veličiny pro větší počet náhodných proměnných, protože pro n \ge 3. může mít nulovou, kladnou i zápornou hodnotu.

Mnoharozměrné zobecnění, které maximalizuje vzájemnou informaci mezi sdruženým rozdělením a ostatními cílovými proměnnými se však s úspěchem používá pro výběr příznaků[2].

Vzájemná informace se používá i v oblasti zpracování signálu jako míra podobnosti dvou signálů. Například FMI metrika[3] je mírou výkonnosti slučování obrazů využívající vzájemnou informaci pro měření množství informace o výchozích obrazech, kterou obsahuje sloučený obraz.

Normalizované varianty[editovat | editovat zdroj]

Normalizované varianty vzájemné informace poskytují omezující koeficienty[4] nebo koeficienty nejistoty[5]


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

Hodnoty obou koeficientů se mohou lišit. V některých případech může být požadována symetrická míra, jako například následující míra redundance:

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

který nabývá nejmenší hodnoty nula, když jsou proměnné nezávislé, a maximální hodnoty

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

když je jedna proměnná při znalosti jiné zcela nadbytečná. Viz článek Redundance. Další symetrická míra je symetrická nejistota (Witten & Frank 2005), daná

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

která reprezentuje vážený průměr dvou koeficientů nejistoty[5]

Jestliže uvažujeme vzájemnou informaci jako speciální případ celkové korelace nebo duální celkové korelace, pak normalizované verze jsou postupně

\frac{I(X;Y)}{\min\left[ H(X),H(Y)\right]} a \frac{I(X;Y)}{H(X,Y)} \; .

Jiné normalizované verze jsou definované následujícími výrazy[6][7].


\frac{I(X;Y)}{\min\left[ H(X),H(Y)\right]}, ~~~~~~~ \frac{I(X;Y)}{H(X,Y)}, ~~~~~~~ \frac{I(X;Y)}{\sqrt{H(X)H(Y)}}

Hodnota

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

je metrika, tj. vyhovuje trojúhelníkové nerovnosti, a dalším podmínkám pro metriku.

Vážené varianty[editovat | editovat zdroj]

V tradiční formulaci vzájemné informace

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

je každá událost nebo objekt daný (x,y) vážený příslušnou pravděpodobností p(x,y). To znamená, že všechny objekty nebo události jsou (až na pravděpodobnost jejich výskytu) ekvivalentní. Některé aplikace však vyžadují, aby určité objekty nebo události byly významnější než jiné, nebo aby určité vzorky asociací byly sémanticky důležitější než jiné.

Například deterministické zobrazení \{(1,1),(2,2),(3,3)\} můžeme považovat za silnější než deterministické zobrazení \{(1,3),(2,1),(3,2)\}, přestože tyto vztahy dávají stejnou vzájemnou informaci. Důvodem je, že vzájemná informace není citlivá na žádné inherentní uspořádání hodnot proměnných (Cronbach 1954, Coombs & Dawes 1970, Lockhead 1970), a proto vůbec není citlivá na formu relačního zobrazení mezi příslušnými proměnnými. Pokud požadujeme, aby první relace, která ukazuje shodu na všech hodnotách proměnné, byla považována za silnější než druhá relace, pak je možné použít váženou vzájemnou informaci (Guiasu 1977) definovanou takto:

 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)},

Takto definovaná vážená vzájmená informace přiřazuje každé pravděpodobnosti souvýskytu hodnot proměnných p(x,y) váhu w(x,y). To umožňuje, aby určité pravděpodobnosti mohly mít větší nebo menší význam než jiné, což dovoluje kvantifikaci relevantních holistických faktorů. Ve výše uvedeném příkladě použití větších relativních vah pro w(1,1), w(2,2) a w(3,3) přináší efekt přiřazení větší důležitosti relaci \{(1,1),(2,2),(3,3)\} než relaci \{(1,3),(2,1),(3,2)\}, což může být žádoucí v určitých případech rozpoznávání vzorků, apod. Ale vážené vzájemné informaci a jejím vlastnostem nebylo věnováno mnoho matematické práce.

Upravená vzájemná informace[editovat | editovat zdroj]

Na rozdělení pravděpodobnosti lze pohlížet jako na rozdělení množiny na třídy ekvivalence. Můžeme se pak ptát:, jestliže určitá množina byla rozdělena náhodně, jaké by bylo rozdělení pravděpodobnosti? Jaká by byla očekávaná hodnota vzájemné informace? Upravená vzájemná informace (anglicky adjusted mutual information, AMI) odečítá očekávanou hodnotu MI, takže AMI je rovna nule, pokud dvě různé distribuce jsou náhodné, a je rozvna jedné, pokud dvě distributions jsou identické. AMI se definuje podobně jako upravený Rand index dvou různých rozdělení množiny.

Absolutní vzájemná informace[editovat | editovat zdroj]

Při použití myšlenek Kolmogorovovy složitosti můžeme považovat vzájemnou informace dvou posloupností nezávislou na libovolném rozdělení pravděpodobnosti:


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

Aby se ukázalo, že tato veličina je až na logaritmický člen symetrická (I_K(X;Y) \approx I_K(Y;X)), je nutné řetězové pravidlo pro Kolmogorovovy složitosti. Aproximace této veličiny pomocí komprese může být použita pro definování metriky pro provedení hierarchického clusteringu posloupnosti bez doménové znalosti posloupnosti.

Vzájemná informace pro diskrétní data[editovat | editovat zdroj]

Pokud množina možných hodnot náhodných proměnných X a Y je diskrétní, pozorovaná data lze summarizovat v kontingenční tabulce, s řádkovou proměnnou X (nebo i) a sloupcovou proměnnou Y (nebo j). Vzájemná informace je jednou z měr asociace nebo korelace mezi řádkovými a sloupcovými proměnnými. Jiné míry asociace zahrnují statistiku testu dobré shody (Pearsonova chí-kvadrát testu), statistiku G-testu, apod. Vzájemná informace se totiž rovná statistice G-testu vydělené 2N, kde N je velikost vzorku.

Ve speciálním případě, když počet stavů pro řádkové i sloupcové proměnné je 2 (i,j=1,2), pak počet stupňů volnosti Pearsonova chí-kvadrát testu je 1. Ze čtyř termů v sumě

 \sum_{i,j } p_{ij} \log \frac{p_{ij}}{p_i p_j }

je pouze jeden nezávislý. To je důvod, aby vzájemná informace funkce měla přesný vztah s korelační funkcí  p_{X=1, Y=1}-p_{X=1}p_{Y=1} pro binární posloupnosti[8].

Aplikace vzájemné informace[editovat | editovat zdroj]

V mnoha aplikacích chceme maximalizovat vzájemnou informaci (tedy rostoucí závislosti), což je často ekvivalentem minimalizace podmíněné entropie. Příklady zahrnují:

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Mutual information na anglické Wikipedii.

  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. [s.l.] : Cambridge University Press, 2008. ISBN 0-521-86571-9.  
  3. Haghighat, M. B. A., Aghagolzadeh, A., & Seyedarabi, H. (2011). A non-reference image fusion metric based on mutual information of image features Computers & Electrical Engineering, 37(5), 744-756.
  4. Coombs, C. H., Dawes, R. M. & Tversky, A.. Mathematical Psychology: An Elementary Introduction. [s.l.] : Prentice-Hall, Englewood Cliffs, NJ, 1970.  
  5. a b "Section 14.7.3. Conditional Entropie a Mutual Informace", {{{title}}}. ISBN 978-0-521-88068-8. 
  6. Yao, Y. Y.. Entropy Measures, Maximum Entropy Principle and Emerging Applications. [s.l.] : Springer, 2003. Dostupné online. Kapitola Information-theoretic measures for knowledge discovery and data mining.  
  7. STREHL, Alexander. Cluster ensembles – a knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research. 2002. Dostupné online [PDF]. DOI:10.1162/153244303321897735.  
  8. Wentian Li. Mutual information functions versus correlation functions. J. Stat. Phys.. 1990. DOI:10.1007/BF01025996.  
  9. [1] Parsing a Natural Language Using Mutual Information Statistics by David M. Magerman and Mitchell P. Marcus
  10. Hugh Everett Teorie of Univerzální Wavefunction, Thesis, Princeton University, (1956, 1973), pp 1–140 (stránka 30)
  11. Hugh Everett, Relative State Formulation of Quantum Mechanics, Reviews of Modern Fyzika vol 29, (1957) pp 454–462.

Literatura[editovat | editovat zdroj]

  • Clustering by compression. IEEE Transactions on Information Theory. 2005. Dostupné online [PDF]. DOI:10.1109/TIT.2005.844059.  
  • 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.
  • Word association norms, mutual information, and lexicography. Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics. 1989. Dostupné online.  
  • Guiasu, Silviu. Information Theory with Applications. [s.l.] : McGraw-Hill, New York, 1977. ISBN 978-0070251090.  
  • LI, Ming. An introduction to Kolmogorov complexity and its applications. New York : Springer-Verlag. 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.
  • David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1 (available free online)
  • Haghighat, M. B. A., Aghagolzadeh, A., & Seyedarabi, H. (2011). A non-reference image fusion metric based on mutual information of image features. Computers & Electrical Engineering, 37(5), 744-756.
  • Athanasios Papoulis. Probability, Random Variables, and Stochastic Processes, second edition. New York: McGraw-Hill, 1984. (See Chapter 15.)
  • Witten, Ian H. & Frank, Eibe. Data Mining: Practical Machine Learning Tools and Techniques. [s.l.] : Morgan Kaufmann, Amsterdam, 2005. Dostupné online. ISBN 978-0-12-374856-0.  
  • Peng, H.C., Long, F. a 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. 2005. Dostupné online.  
  • Andre S. Ribeiro, Stuart A. Kauffman, Jason Lloyd-Price, Bjorn Samuelsson a Joshua Socolar. Mutual Information in Random Boolean models of regulatory networks. Physical Review E. 2008.  
  • WELLS, W.M. III. Multi-modal volume registration by maximization of mutual information. Medical Image Analysis. 1996. Dostupné online [PDF]. DOI:10.1016/S1361-8415(01)80004-9. PMID 9873920.  

Související články[editovat | editovat zdroj]