Back

ⓘ Vzájemná informace



Vzájemná informace
                                     

ⓘ Vzájemná informace

Vzájemná informace nebo 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.

                                     

1. Definice vzájemné informace

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

I X ; Y = ∑ y ∈ Y ∑ x ∈ X p x, y log ⁡ p x, y p x p y), {\displaystyle IX;Y=\sum _{y\in Y}\sum _{x\in X}px,y\log {\left{\frac {px,y}{px\,py}}\right)},\,\!}

kde p x, y je sdružená pravděpodobnostní funkce proměnných X a Y a p x resp. p y jsou marginální pravděpodobnostní 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 = ∫ Y ∫ X p x, y log ⁡ p x, y p x p y) d x d y, {\displaystyle IX;Y=\int _{Y}\int _{X}px,y\log {\left{\frac {px,y}{px\,py}}\right)}\;dx\,dy,}

kde p x, y je sdružená hustota pravděpodobnosti X a Y, a p x {\displaystyle px} resp. p y {\displaystyle py} 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. Dusledkem 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 ⁡ p x, y p x p y) = log ⁡ 1 = 0. {\displaystyle \log {\left{\frac {px,y}{px\,py}}\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).

                                     

2. Vztah k jiným veličinám

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

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 {\displaystyle {\begin{aligned}IX;Y&{}=HX-HX|Y\\&{}=HY-HY|X\\&{}=HX+HY-HX,Y\\&{}=HX,Y-HX|Y-HY|X\end{aligned}}}

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 mužeme ukázat, že I X ; Y je nezáporná, a odtud H X ≥ H X | Y {\displaystyle \ HX\geq HX|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 mužeme číst jako "množství nejistoty v X, minus množství nejistoty v X, která zustá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 muž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 K L p x, y ‖ p x p y). {\displaystyle IX;Y=D_{\mathrm {KL} }px,y\|pxpy).}

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

I X ; Y = ∑ y p y ∑ x p x | y log 2 ⁡ p x | y p x = ∑ y p y D K L p x | y ‖ p x) = E Y { D K L p x | y ‖ p x) }. {\displaystyle {\begin{aligned}IX;Y&{}=\sum _{y}py\sum _{x}px|y\log _{2}{\frac {px|y}{px}}\\&{}=\sum _{y}py\;D_{\mathrm {KL} }px|y\|px)\\&{}=\mathbb {E} _{Y}\{D_{\mathrm {KL} }px|y\|px)\}.\end{aligned}}}

neboli vzájemnou informaci mužeme také chápat jako očekávanou hodnotu Kullbackovy-Leiblerovy divergence jednorozměrného rozdělení p 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.

                                     

3.1. Varianty vzájemné informace Metrika

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 − 2 I X ; Y = H X | Y + H Y | X {\displaystyle dX,Y=HX,Y-IX;Y=HX+HY-2IX;Y=HX|Y+HY|X}

splňuje podmínky pro metriku. Tato vzdálenostní metrika je také známa jako variace informace.

Protože platí d X, Y ≤ H X, Y {\displaystyle dX,Y\leq HX,Y}, lze tuto metriku přirozeně normalizovat:

D X, Y = d X, Y / H X, Y ≤ 1. {\displaystyle DX,Y=dX,Y/HX,Y\leq 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é.

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 {\displaystyle DX,Y=1-IX;Y/HX,Y}

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

                                     

3.2. Varianty vzájemné informace Podmíněná vzájemná informace

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 = E Z I X ; Y | Z) = ∑ z ∈ Z ∑ y ∈ Y ∑ x ∈ X p z p X, Y | Z x, y | z log ⁡ p X, Y | Z x, y | z p X | Z x | z p Y | Z y | z, {\displaystyle IX;Y|Z=\mathbb {E} _{Z}{\big }IX;Y|Z{\big)}=\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}p_{Z}zp_{X,Y|Z}x,y|z\log {\frac {p_{X,Y|Z}x,y|z}{p_{X|Z}x|zp_{Y|Z}y|z}},}

což lze zjednodušit na

I X ; Y | Z = ∑ z ∈ Z ∑ y ∈ Y ∑ x ∈ X p X, Y, Z x, y, z log ⁡ p z p X, Y, Z x, y, z p X, Z x, z p Y, Z y, z. {\displaystyle IX;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}zp_{X,Y,Z}x,y,z}{p_{X,Z}x,zp_{Y,Z}y,z}}.}

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

I X ; Y | Z ≥ 0 {\displaystyle IX;Y|Z\geq 0}

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



                                     

3.3. Varianty vzájemné informace Vícerozměrná vzájemná informace

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 diagramu, 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 {\displaystyle IX_{1};X_{1}=HX_{1}}

a pro n > 1, {\displaystyle n> 1,}

I X 1 ;. ; X n = I X 1 ;. ; X n − 1 − I X 1 ;. ; X n − 1 | X n, {\displaystyle IX_{1};\.\,;X_{n}=IX_{1};\.\,;X_{n-1}-IX_{1};\.\,;X_{n-1}|X_{n},}

kde jak je uvedeno výše definujeme

I X 1 ;. ; X n − 1 | X n = E X n I X 1 ;. ; X n − 1 | X n). {\displaystyle IX_{1};\.\,;X_{n-1}|X_{n}=\mathbb {E} _{X_{n}}{\big }IX_{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 B jsou dvě množiny proměnných, pak vzájemná informace mezi nimi je:

I A, B = H A ∪ B + H A ∩ B − H A − H B, {\displaystyle IA,B=HA\cup B+HA\cap B-HA-HB,}
                                     

3.4. Varianty vzájemné informace Aplikace

Slepé použití informačních diagramu 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 ≥ 3 {\displaystyle n\geq 3} muž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 rysu.

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

                                     

3.5. Varianty vzájemné informace Normalizované varianty

Normalizované varianty vzájemné informace poskytují omezující koeficienty nebo koeficienty nejistoty

C X Y = I X ; Y H Y a C Y X = I X ; Y H X. {\displaystyle C_{XY}={\frac {IX;Y}{HY}}~~{\mbox{ a }}~~C_{YX}={\frac {IX;Y}{HX}}.}

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

R = I X ; Y H X + H Y {\displaystyle R={\frac {IX;Y}{HX+HY}}}

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

R max = min H X, H Y) H X + H Y {\displaystyle R_{\max }={\frac {\minHX,HY)}{HX+HY}}}

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 = 2 R = 2 I X ; Y H X + H Y {\displaystyle UX,Y=2R=2{\frac {IX;Y}{HX+HY}}}

která reprezentuje vážený pruměr dvou koeficientu nejistoty

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

I X ; Y min }},~~~~~~~{\frac {IX;Y}{HX,Y}},~~~~~~~{\frac {IX;Y}{\sqrt {HXHY}}}}

Hodnota

D ′ X, Y = 1 − I X ; Y max H X, H Y) {\displaystyle D^{\prime }X,Y=1-{\frac {IX;Y}{\maxHX,HY)}}}

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



                                     

3.6. Varianty vzájemné informace Vážené varianty

V tradiční formulaci vzájemné informace

I X ; Y = ∑ y ∈ Y ∑ x ∈ X p x, y log ⁡ p x, y p x p y, {\displaystyle IX;Y=\sum _{y\in Y}\sum _{x\in X}px,y\log {\frac {px,y}{px\,py}},}

je každá událost nebo objekt daný x, y {\displaystyle x,y} vážený příslušnou pravděpodobností p x, y {\displaystyle px,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 duležitější než jiné.

Například deterministické zobrazení { 1, 1, 2, 2, 3, 3 } {\displaystyle \{1.1.2.2.3.3\}} mužeme považovat za silnější než deterministické zobrazení { 1, 3, 2, 1, 3, 2 } {\displaystyle \{1.3.2.1.3.2\}}, přestože tyto vztahy dávají stejnou vzájemnou informaci. Duvodem je, že vzájemná informace není citlivá na žádné inherentní uspořádání hodnot proměnných, a proto vubec 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 = ∑ y ∈ Y ∑ x ∈ X w x, y p x, y log ⁡ p x, y p x p y, {\displaystyle IX;Y=\sum _{y\in Y}\sum _{x\in X}wx,ypx,y\log {\frac {px,y}{px\,py}},}

Takto definovaná vážená vzájemná informace přiřazuje každé pravděpodobnosti souvýskytu hodnot proměnných p x, y {\displaystyle px,y} váhu w x, y {\displaystyle wx,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 faktoru. Ve výše uvedeném příkladě použití větších relativních vah pro w 1, 1 {\displaystyle w1.1}, w 2, 2 {\displaystyle w2.2} a w 3, 3 {\displaystyle w3.3} přináší efekt přiřazení větší duležitosti relaci { 1, 1, 2, 2, 3, 3 } {\displaystyle \{1.1.2.2.3.3\}} než relaci { 1, 3, 2, 1, 3, 2 } {\displaystyle \{1.3.2.1.3.2\}}, což muže být žádoucí v určitých případech rozpoznávání vzorku, apod. Ale vážené vzájemné informaci a jejím vlastnostem nebylo věnováno mnoho matematické práce.

                                     

3.7. Varianty vzájemné informace Upravená vzájemná informace

Na rozdělení pravděpodobnosti lze pohlížet jako na rozdělení množiny na třídy ekvivalence. Muž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ě ruzné distribuce jsou náhodné, a je rovna jedné, pokud dvě distribuce jsou identické. AMI se definuje podobně jako upravený Rand index dvou ruzných rozdělení množiny.

                                     

3.8. Varianty vzájemné informace Absolutní vzájemná informace

Při použití myšlenek Kolmogorovovy složitosti muž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. {\displaystyle I_{K}X;Y=KX-KX|Y.}

Aby se ukázalo, že tato veličina je až na logaritmický člen symetrická I K X ; Y ≈ I K Y ; X {\displaystyle 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 muže být použita pro definování metriky pro provedení hierarchického clusteringu posloupnosti bez doménové znalosti posloupnosti.

                                     

3.9. Varianty vzájemné informace Vzájemná informace pro diskrétní data

Pokud množina možných hodnot náhodných proměnných X a Y je diskrétní, pozorovaná data lze sumarizovat 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 stavu pro řádkové i sloupcové proměnné je 2 i,j=1.2, pak počet stupňu volnosti Pearsonova chí-kvadrát testu je 1. Ze čtyř termu v sumě

∑ i, j p i j log ⁡ p i j p i p j {\displaystyle \sum _{i,j}p_{ij}\log {\frac {p_{ij}}{p_{i}p_{j}}}}

je pouze jeden nezávislý. To je duvod, 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 {\displaystyle p_{X=1,Y=1}-p_{X=1}p_{Y=1}} pro binární posloupnosti.



                                     

4. Aplikace vzájemné informace

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í:

  • Predikce fylogenetického profilování z vzájemné přítomnosti nebo dispřítomnosti funkcionálně propojených genu.
  • V telekomunikacích se kapacita kanálu rovná vzájemné informaci maximalizované přes všechna vstupní rozdělení.
  • V technologii vyhledávacích stroju se vzájemná informace mezi frázemi a kontexty používá jako vlastnost pro k-mean clustering pro vytváření sémantických clusteru konceptu.
  • Vzájemná informace se používá v lékařským imaging pro registraci obrazu. Je-li dán referenční obrázek například sken moygu a druhý obrázek, který se_chce_umístit do stejné soustavy souřadnic jako referenční obrázek, tento druhý obrázek se deformuje tak, aby se maximalizovala vzájemná informace mezi ním a referenčním obrázkem.
  • Vzájemná informace se používá jako kritérium pro výběr a transformaci příznaku při strojovém učení. Muže být používána pro charakterizaci jak relevance tak redundance proměnné, jako například u algoritmu výběr příznaku s minimální redundancí.
  • Detekce fázové synchronizace v analýze časových řad.
  • Ve statistické mechanice lze Loschmidtuv paradox vyjádřit pomocí vzájemné informace. Loschmidt si všiml, že musí být nemožné odvodit fyzikální zákon, který není časově symetrický například druhý termodynamický zákon pouze z fyzikálních zákonu odpovídajících této symetrii. Ukázal, že Boltzmannova H-věta vychází z předpokladu vzájemné nekorelovanosti rychlostí částic v plynu, což ruší symetrii času inherentní v H-větě. Lze ukázat, že jestliže systém je popsán hustotou pravděpodobnosti ve fázovém prostoru, pak z Liouvilleovy věty vyplývá, že sdružená informace sdružená entropie se znaménkem minus určitého rozdělení zustává konstantní v čase. Sdružená informace se rovná vzájemné informaci zvětšené o sumu všech marginálních informací marginální entropie se znaménkem minus pro každou souřadnici částice. Boltzmannuv předpoklad množství na zanedbáváme vzájemná informace při výpočtu entropie, což dává termodynamickou entropii dělenou Boltzmannovou konstantou.
  • Vzájemná informace slov se často používá jako funkce duležitosti pro hledání kolokací v korpusové lingvistice. Toto má přidanou složitost?, které ne slovo-instance je instance dvou ruzných slov; rather, jeden počítá instance, kde se obě slova objeví bezprostředně za sebou nebo blízko sebe; to nepatrně komplikuje výpočet, protože očekávaná pravděpodobnost, že se jedno slovo objeví nejvýše N slov od druhého, roste s N.
  • Vzájemná informace mezi geny v datech z microarray se používá v algoritmu ARACNE pro rekonstrukci genové regulační sítě.
  • Předpovídání sekundární struktury RNA používá zarovnávání více posloupností.
  • V metodě infomax pro neuronové sítě a v dalších metodách strojového učení, včetně používání metody infomax v analýze nezávislých komponent.
  • Pruměrná vzájemná informace v Takensově větě se používá pro určování embedding zpoždění parametr.
  • Procedury diskriminativního trénování pro skryté Markovovy modely byly navrženy pomocí kriteria maximální vzájemná informace MMI.
  • Vzájemná informace se používá při určování podobnosti dvou ruzných shlukování.klastrování datových souboru. Má určité výhody proti tradičnímu Rand indexu.
  • Vzájemná informace se používá při učení struktury Bayesovských sítí a dynamických Bayesovských sítí, kteréžto vysvětlují kauzální vztah mezi náhodnými proměnnými, jak dokládá GlobalMIT toolkit: učení globálně optimálních dynamických Bayesovských sítí s vzájemně informačním testovacím kritériumem.
  • Oblíbená účelová funkce v učení rozhodovacích stromu.
                                     

5. Literatura

  • 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.
  • CILIBRASI, R.; VITÁNYI, Paul, 2005. Clustering by compression. IEEE Transactions on Information Theory. Dostupné online: Morgan Kaufmann, Amsterdam, 2005. Dostupné online. ISBN 978-0-12-374856-0.
  • 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. arXiv:0707.3642.
  • WELLS, W.M. III, 1996. Multi-modal volume registration by maximization of mutual information. Medical Image Analysis. Dostupné v archivu pořízeném dne 2008-09-06. DOI:10.1016/S1361-84150180004-9. PMID 9873920. Archivováno 6. 9. 2008 na Wayback Machine
Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →