Entropisk vektor

Den entropiska vektorn eller entropiska funktionen är ett begrepp som uppstår inom informationsteorin . Den representerar de möjliga värdena för Shannons informationsentropi som delmängder av en uppsättning slumpvariabler kan ta . Att förstå vilka vektorer som är entropiska är ett sätt att representera alla möjliga ojämlikheter mellan entropier av olika delmängder. Till exempel, för två slumpvariabler $X_{1},X_{2}$ , deras gemensamma entropi (entropin för den slumpmässiga variabeln som representerar paret $X_{ 1},X_{2}$ ) är som mest summan av entropierna av $X_{1}$ och av $X_{2}$ :

$H(X_{1},X_{2})\leq H(X_{1})+H(X_{2} })$

Andra informationsteoretiska mått som villkorlig information , ömsesidig information eller total korrelation kan uttryckas i termer av gemensam entropi och är därmed relaterade till motsvarande ojämlikheter. Många ojämlikheter som tillfredsställs av entropiska vektorer kan härledas som linjära kombinationer av några grundläggande, kallade Shannon-typ ojämlikheter . Det har dock bevisats att redan för $n=4$ variabler är ingen ändlig uppsättning linjära olikheter tillräcklig för att karakterisera alla entropiska vektorer.

Definition

Shannons informationsentropi för en slumpvariabel $X$ betecknas $\displaystyle H(X)}$ { . För en tuppel av slumpvariabler $X_{1},X_{2},\ldots ,X_{n}$ anger vi den gemensamma entropin för en delmängd $X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}}$ som ${\displaystyle H(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})} ,$ eller mer kortfattat som ${ \displaystyle H(X_{I})}$ , där $I=\{i_{1},i_{2},\dots ,i_{k} \}$ . Här $X_{I}$ förstås som den slumpmässiga variabeln som representerar tupeln $(X_{i_{1}},X_{ i_{2}},\dots ,X_{i_{k}})$ . För den tomma delmängden $I=\emptyset$ anger $X_{I}} en deterministisk variabel med entropi 0.$ displaystyle

En vektor h i $\mathbb {R} ^{2^{n}}$ indexerad av delmängder av $\{1,2,\dots ,n \}$ kallas en entropisk vektor av ordningen $n$ om det finns en tupel av slumpvariabler $X_{1},X_{2},\ldots , X_{n}$ så att $h(I)=H(X_{I})$ för varje delmängd $I\subseteq \{1,2,\dots ,n\}$ .

Mängden av alla entropiska vektorer av ordningen $n$ betecknas med $\Gamma _{n}^{*}$ . Zhang och Yeung bevisade att den inte är stängd (för $n\geq 3$ ), utan dess stängning , ${\bar {\Gamma _{n}^{*}} }$ , är en konvex kon och kännetecknas därför av de (oändligt många) linjära olikheter den uppfyller. Att beskriva regionen ${\bar {\Gamma _{n}^{*}}}$ är alltså ekvivalent med att karakterisera alla möjliga olikheter på ledentropier.

Exempel

Låt X , Y vara två oberoende slumpvariabler med diskret enhetlig fördelning över mängden $\{0,1\}$ . Sedan

$H(X)=H(Y)=1$

(eftersom var och en är jämnt fördelad över en uppsättning med två element), och

$H(X,Y)=H(X)+H(Y)=2$

(eftersom de två variablerna är oberoende, vilket betyder att paret $(X_{1},X_{2})$ är jämnt fördelat över ${\displaystyle (0,0),(0,1),(1,0),(1,1)} .$ ) Den motsvarande entropiska vektorn är alltså:

$v=(0,1,1,2)^{\mathsf {T}}\in \Gamma _{2}^{*}$

Å andra sidan är vektorn $(0,1,1,3)^{\mathsf {T}}$ inte entropisk (det vill säga ${\displaystyle (0,1,1,3)^{\mathsf {T}}\not \in \Gamma _{2}^{*}} ),$ eftersom alla par av slumpvariabler (oberoende eller inte) ska uppfylla $H(X,Y)\leq H(X)+H(Y)$ .

Karakteriserande entropiska vektorer: regionen Γ _n ^*

Shannon-typ ojämlikheter och Γ _n

För en tupel av slumpvariabler $X_{1},X_{2},\ldots ,X_{n}$ uppfyller deras entropier:

$1)\quad H(X_{\emptyset })=0$

$2)\quad H(X_{ I})\leq H(X_{J})$ , för alla $I\subseteq J\subseteq \{1,\dots ,n\}$

I synnerhet $H(X_{I})\geq 0$ , för alla $I\subseteq \{1,\dots ,n\ }$ .

Shannon -ojämlikheten säger att en entropisk vektor är submodulär :

${\displaystyle 3)\quad H(X_{I})+H(X_{J} )\geq H(X_{I\cup J})+H(X_{I\cap J})} ,$ för alla $I,J\subseteq \{1 ,\dots ,n\}$

Det motsvarar ojämlikheten som säger att den villkorade ömsesidiga informationen är icke-negativ:

${\begin{aligned}I(X;Y\mid Z)&=H(X\ mitten av Z)-H(X\mitten Y,Z)\\&=H(X\mitten Z)+H(Y\mitten Z)-H(X,Y\mitten Z)\\&=H(X, Z)+H(Y,Z)-H(X,Y,Z)-H(Z)\\&\geq 0\end{aligned}}$

(För en riktning, observera detta uttrycker den sista formen Shannons olikhet för delmängder $X,Z$ och $Y,Z$ av tuppeln $X,Y ,Z$ ; för den andra riktningen, ersätt $X=X_{I}$ , $Y=X_{J}$ , $Z =X_{I\cap J}$ ).

Många ojämlikheter kan härledas som linjära kombinationer av Shannon-ojämlikheter; de kallas Shannon-typ ojämlikheter eller grundläggande information ojämlikheter av Shannons informationsmått. Uppsättningen vektorer som uppfyller dem kallas $\Gamma _{n}$ ; den innehåller $\Gamma _{n}^{*}$ .

Mjukvara har utvecklats för att automatisera uppgiften att bevisa ojämlikheter av Shannon-typ. Givet en olikhet kan sådan programvara avgöra om den givna olikheten är en giltig olikhet av Shannon-typ (dvs om den innehåller konen ${\displaystyle \Gamma _{n}} )$ .

Ojämlikheter av icke-Shannon-typ

Frågan om huruvida ojämlikheter av Shannon-typ är de enda, det vill säga om de helt karakteriserar regionen $\Gamma _{n}^{*}$ ställdes först av Te Su Han 1981 och närmare bestämt av Nicholas Pippenger 1986. Det är inte svårt att visa att detta är sant för två variabler, det vill säga $\Gamma _{2}^{*}=\Gamma _{2 }$ . För tre variabler bevisade Zhang och Yeung att $\Gamma _{3}^{*}\neq \Gamma _{3}$ ; men det är fortfarande asymptotiskt sant, vilket betyder att stängningen är lika: ${\overline {\Gamma _{3}^{*}}}=\Gamma _{3}$ . 1998 visade Zhang och Yeung att ${\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}$ för alla ${\ displaystyle n\geq 4}$ , genom att bevisa att följande olikhet på fyra slumpvariabler (i termer av villkorlig ömsesidig information) är sann för vilken entropisk vektor som helst, men inte är Shannon-typ:

$2I(X_{3},X_{4})\leq I(X_{1},X_{2})+I(X_{1}:X_{3},X_{4 })+3I(X_{3}:X_{4}|X_{1})+I(X_{3}:X_{4}|X_{2})$

Ytterligare ojämlikheter och oändliga familjer av ojämlikheter har hittats. Dessa ojämlikheter ger yttre gränser för ${\overline {\Gamma _{n}^{*}}}$ bättre än Shannon-typgränsen $\Gamma _{n}$ . 2007 bevisade Matus att ingen ändlig uppsättning linjära olikheter är tillräcklig (för att härleda alla som linjära kombinationer), för $n\geq 4$ variabler. Med andra ord, området ${\overline {\Gamma _{4}^{*}}}$ är inte polyedriskt. Huruvida de kan karakteriseras på något annat sätt (som gör det möjligt att effektivt avgöra om en vektor är entropisk eller inte) förblir ett öppet problem.

Analoga frågor för von Neumanns entropi i kvantinformationsteorin har övervägts.

Inre gränser

Vissa inre gränser för ${\overline {\Gamma _{n}^{*}}}$ är också kända. Ett exempel är att ${\overline {\Gamma _{4}^{*}}}$ innehåller alla vektorer i $\Gamma _{4}$ som dessutom uppfyller följande olikhet (och de som erhålls genom att permutera variabler), kända som Ingletons olikhet för entropi :

$I(X_{1 };X_{2})+I(X_{3};X_{4}\mitten X_{1})+I(X_{3};X_{4}\mitten X_{2})-I(X_{ 3};X_{4})\geq 0$

Entropi och grupper

Gruppkarakteriserbara vektorer och kvasilikformiga fördelningar

Betrakta en grupp $G$ och undergrupper $G_{1},G_{2},\dots ,G_{n}$ av $G$ . Låt $G_{I}$ beteckna $\bigcap _{i\in I}G_{i}$ för $I\ subseteq \{1,\dots ,n\}$ ; detta är också en undergrupp av $G$ . Det är möjligt att konstruera en sannolikhetsfördelning för $n$ slumpvariabler $X_{1},\dots ,X_{n}$ så att

$H(X_{I})=\log {\frac {|G|}{|G_{I}|}}$ .

(Konstruktionen tar i huvudsak ett element $a$ av $G$ likformigt slumpmässigt och låter $X_{i}$ vara motsvarande coset $aG_{i}$ ). Varje informationsteoretisk ojämlikhet innebär således en gruppteoretisk sådan. Till exempel, den grundläggande olikheten $H(X,Y)\leq H(X)+H(Y)$ innebär att

$|G|\cdot |G_{1}\cap G_{2}|\geq |G_{1}|\cdot |G_{2}|.$

Det visar sig att det omvända i huvudsak är sant. Mer exakt sägs en vektor vara gruppkarakteriserbar om den kan erhållas från en tupel av undergrupper enligt ovan. Uppsättningen av gruppkarakteriserbara vektorer betecknas $\Upsilon ^{n}$ . Som sagt ovan, $\Upsilon ^{n}\subseteq \Gamma _{n}^{*}$ . Å andra sidan, $\Gamma _{n}^{*}$ (och därmed ${\overline {\Gamma _{n}^{*}}}$ ) ingår i den topologiska stängningen av den konvexa stängningen av $\Upsilon ^{n}$ . Med andra ord gäller en linjär olikhet för alla entropiska vektorer om och endast om den gäller för alla vektorer $h$ av formen ${\displaystyle h_{I}=\log {\frac {|G|}{|G_{I}|}}} , där I {\displaystyle I} går över delmängder av$ någon $av$ undergrupper $G_{1},G_{2},\dots ,G_{n}$ i en grupp $G$ .

Gruppkarakteriserbara vektorer som kommer från en abelisk grupp tillfredsställer Ingletons ojämlikhet.

Kolmogorov komplexitet

Kolmogorovs komplexitet uppfyller i huvudsak samma ojämlikheter som entropi. Beteckna nämligen Kolmogorov-komplexiteten för en finit sträng $x$ som $K(x)$ (det vill säga längden på det kortaste programmet som matar ut $x$ ). Den gemensamma komplexiteten för två strängar $x,y$ , definierad som komplexiteten för en kodning av paret $\langle x,y\rangle$ , kan betecknas $K(x,y)$ . På liknande sätt kan den villkorliga komplexiteten betecknas $K(x|y)$ (längden på det kortaste programmet som matar ut $x$ givet $y$ ). Andrey Kolmogorov märkte att dessa föreställningar beter sig på samma sätt som Shannon-entropi, till exempel:

$K(a)+K(b)\geq K(a,b )-O(\log |a|+\log |b|)$

År 2000, Hammer et al. bevisat att en olikhet verkligen gäller för entropiska vektorer om och endast om motsvarande olikhet i termer av Kolmogorov-komplexitet håller upp till logaritmiska termer för alla tuplar av strängar.

Se även

• Ojämlikheter i informationsteori

•   Thomas M. Cover, Joy A. Thomas. Elements of information theory New York: Wiley, 1991. ISBN 0-471-06259-6
•   Raymond Yeung. A First Course in Information Theory , Kapitel 12, Information Ojämlikheter , 2002, Skriv ut ISBN 0-306-46791-7