Vzájemná informace

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 (Šablona:Vjazyce2) 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

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á 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)=\underset{Y}{\int }\underset{X}{\int }p(x,y)\log \left(\frac{p(x,y)}{p(x)p(y)}\right)dxdy,$

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

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

$\begin{array}{cc}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{array}$

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{K}\mathrm{L}}(p(x,y)\Vert p(x)p(y)).$

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

$\begin{array}{cc}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{K}\mathrm{L}}(p(x|y)\Vert p(x))\\ & ={𝔼}_Y\{D_{\mathrm{K}\mathrm{L}}(p(x|y)\Vert p(x))\}.\end{array}$

neboli vzájemnou informaci můžeme také chápat jako očekávanou 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

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

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é.

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

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)={𝔼}_Z(I(X;Y)|Z)=\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

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)={𝔼}_{X_n}(I(X_1;...;X_{n-1})|X_n).$

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

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 rysů.

Vzájemná informace se používá i v oblasti zpracování signálu jako míra podobnosti dvou signálů. Například FMI metrika 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

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

$C_{XY}=\frac{I(X;Y)}{H(Y)}\text{ 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

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 [H(X),H(Y)]}$ a $\frac{I(X;Y)}{H(X,Y)}.$

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

$\frac{I(X;Y)}{\min [H(X),H(Y)]},\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

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ájemná 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

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 (Šablona:Vjazyce2) odečítá očekávanou hodnotu MI, takže AMI je rovna nule, pokud dvě různé distribuce jsou náhodné, a je rovna jedné, pokud dvě distribuce jsou identické. AMI se definuje podobně jako upravený Rand index dvou různých rozdělení množiny.

Absolutní vzájemná informace

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

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

Aplikace vzájemné informace

Šablona:Upravit část 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í:

• V technologii vyhledávacích strojů se vzájemná informace mezi frázemi a kontexty používá jako vlastnost pro k-mean clustering pro vytváření sémantických clusterů (konceptů).
• V telekomunikacích se kapacita kanálu rovná vzájemné informaci maximalizované přes všechna vstupní rozdělení.
• Procedury diskriminativního trénování pro skryté Markovovy modely byly navrženy pomocí kriteria maximální vzájemná informace (MMI).
• Předpovídání sekundární struktury RNA používá zarovnávání více posloupností.
• Predikce fylogenetického profilování z vzájemné přítomnosti nebo dispřítomnosti funkcionálně propojených genů.
• Vzájemná informace se používá jako kritérium pro výběr a transformaci příznaků při strojovém učení. Může být používána pro charakterizaci jak relevance tak redundance proměnné, jako například u algoritmu výběr příznaků s minimální redundancí.
• Vzájemná informace se používá při určování podobnosti dvou různých shlukování.(klastrování) datových souborů. Má určité výhody proti tradičnímu Rand indexu.
• Vzájemná informace slov se často používá jako funkce důležitosti pro hledání kolokací v korpusové lingvistice. Toto má přidanou složitost ??, které ne slovo-instance je instance dvou různý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 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.
• Detekce fázové synchronizace v analýze časových řad.
• 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.
• Průměrná vzájemná informace v Takensově větě se používá pro určování embedding zpoždění parametr.
• Vzájemná informace mezi geny v datech z microarray se používá v algoritmu ARACNE pro rekonstrukci genové (regulační) sítě.
• Ve statistické mechanice lze Loschmidtův 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ákonů 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í zůstá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. Boltzmannův 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 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 [2]: 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 stromů.

Literatura

• Šablona:Citace periodika
• 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.
• Šablona:Citace periodikaŠablona:Nedostupný zdroj
• Šablona:Citace monografie
• Šablona:Citace monografie
• 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. Šablona:ISBN (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.)
• Šablona:Citace monografie Šablona:Wayback
• Šablona:Citace periodika
• Šablona:Citace periodika
• Šablona:Citace periodika Šablona:Wayback

Související články

• Bodová vzájemná informace
• Kvantová vzájemná informace