Ojämlikheter i informationsteori

Ojämlikheter är mycket viktiga i studiet av informationsteori . Det finns ett antal olika sammanhang där dessa ojämlikheter uppträder.

Entropiska ojämlikheter

Betrakta en tuppel $X_{1},X_{2},\dots ,X_{n}$ av $n$ ändligt (eller högst räknat) stödd slumpmässigt variabler på samma sannolikhetsutrymme . Det finns 2 ⁿ delmängder, för vilka ( gemensamma ) entropier kan beräknas. Till exempel, när n = 2, kan vi betrakta entropierna $H(X_{1}),$ $H(X_{2}),$ och $H(X_{1},X_{2})$ . De uppfyller följande ojämlikheter (som tillsammans karakteriserar intervallet för de marginala och gemensamma entropierna för två slumpvariabler):

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

I själva verket kan dessa alla uttryckas som speciella fall av en enda ojämlikhet som involverar den villkorade ömsesidiga informationen , nämligen

I(A;B|C)\geq 0,

där $A$ , $B$ och $C$ var och en betecknar den gemensamma fördelningen av någon godtycklig (möjligen tom) delmängd av vår samling av slumpvariabler. Ojämlikheter som kan härledas som linjära kombinationer av detta är kända som ojämlikheter av Shannon-typ .

För större $n$ finns ytterligare begränsningar för möjliga värden på entropi. För att göra detta exakt, en vektor $h$ i $\mathbb {R} ^{2^{n}}$ indexerad med delmängder av $\{ 1,\dots ,n\}$ sägs vara entropisk om det finns en gemensam, diskret fördelning av n slumpvariabler $X_{1},\dots ,X_{n}$ såsom att $h_{I}=H(X_{i}\colon i\in I)$ är deras gemensamma entropi , för varje delmängd $I$ . Uppsättningen av entropiska vektorer betecknas ${\displaystyle \Gamma _{n}^{*}} ,$ efter beteckningen Yeung. Den är inte stängd eller konvex för $n\geq 3$ , men dess topologiska stängning ${\overline {\Gamma _{n}^{*}}}$ är känd för att vara konvex och därför kan den kännetecknas av de (oändligt många) linjära ojämlikheterna som alla entropiska vektorer uppfyller, kallade entropiska ojämlikheter .

Mängden av alla vektorer som uppfyller Shannon-typ ojämlikheter (men inte nödvändigtvis andra entropiska olikheter) innehåller ${\overline {\Gamma _{n}^{*}}}$ . Denna inneslutning är strikt för $n\geq 4$ och ytterligare ojämlikheter är kända som icke-Shannon- olikheter. Zhang och Yeung rapporterade om den första ojämlikheten av icke-Shannon-typ. Matus bevisade att ingen ändlig uppsättning ojämlikheter kan karakterisera (genom linjära kombinationer) alla entropiska ojämlikheter. Med andra ord, området ${\overline {\Gamma _{n}^{*}}}$ är inte en polytop .

Nedre gränser för divergensen Kullback–Leibler

Många viktiga ojämlikheter i informationsteorin är faktiskt lägre gränser för Kullback–Leibler-divergensen . Även ojämlikheterna av Shannon-typ kan betraktas som en del av denna kategori, eftersom interaktionsinformationen kan uttryckas som Kullback–Leibler-divergensen av den gemensamma fördelningen med avseende på produkten av marginalerna, och därför kan dessa ojämlikheter ses som en speciell fallet med Gibbs ojämlikhet .

Å andra sidan verkar det vara mycket svårare att härleda användbara övre gränser för Kullback–Leibler-divergensen. Detta beror på att Kullback–Leibler-divergensen D _KL ( P || Q ) beror mycket känsligt på händelser som är mycket sällsynta i referensfördelningen Q . D _KL ( P || Q ) ökar utan gräns när en händelse med ändlig icke-noll sannolikhet i fördelningen P blir ytterst sällsynt i referensfördelningen Q , och faktiskt D _KL ( P || Q ) är inte ens definierad om en händelse av icke-noll sannolikhet i P har noll sannolikhet i Q. (Därav kravet att P ska vara absolut kontinuerlig med avseende på Q. )

Gibbs ojämlikhet

Denna grundläggande ojämlikhet säger att skillnaden mellan Kullback och Leibler är icke-negativ.

Kullbacks ojämlikhet

En annan ojämlikhet angående skillnaden mellan Kullback och Leibler är känd som Kullbacks ojämlikhet . Om P och Q är sannolikhetsfördelningar på den reella linjen med P absolut kontinuerlig med avseende på Q, och vars första moment existerar, då

D_{KL}(P\parallel Q)\geq \Psi _{Q}^{*}(\mu ' _{1}(P)),

där $\Psi _{Q}^{*}$ är den stora avvikelsehastighetsfunktionen , dvs det konvexa konjugatet av den kumulantgenererande funktionen av Q , och $\ mu '_{1}(P)$ är det första ögonblicket av P .

Cramér –Rao-gränsen är en följd av detta resultat.

Pinskers ojämlikhet

Pinskers ojämlikhet relaterar Kullback–Leibler-divergens och totalt variationsavstånd . Det står att om P , Q är två sannolikhetsfördelningar , då

{\sqrt {{\frac {1}{2}}D_{KL}^{(e)}(P\parallel Q)}}\geq \sup\{|P(A)-Q(A )|:A{\text{ är en händelse till vilken sannolikheter är tilldelade.}}\}.

var

D_{KL}^{(e)}(P\parallel Q)

är Kullback–Leibler divergensen i nats och

\sup _{A}|P(A)-Q(A)|

är det totala variationsavståndet.

Andra ojämlikheter

Hirschman osäkerhet

1957 visade Hirschman att för en (rimligt väluppfostrad) funktion $f:\mathbb {R} \rightarrow \mathbb {C}$ så att ${\displaystyle \int _{-\infty }^{\infty }|f(x)|^{2}\,dx=1,} och$ dess Fouriertransform $g(y)=\int _{-\infty }^{\infty }f(x)e^{-2\pi ixy} \,dx,$ summan av differentialentropierna för $|f|^{2}$ och $|g|^{2}$ är icke-negativ, dvs

-\int _{-\infty }^{\infty }|f(x)|^{2}\log |f(x)|^{2}\,dx-\ int _{-\infty }^{\infty }|g(y)|^{2}\log |g(y)|^{2}\,dy\geq 0.

Hirschman förmodade, och det bevisades senare, att en skarpare gräns för $\log(e/2),$ som uppnås i fallet med en gaussisk fördelning , skulle kunna ersätta höger- sidan av denna ojämlikhet. Detta är särskilt betydelsefullt eftersom det antyder, och är starkare än, Weyls formulering av Heisenbergs osäkerhetsprincip .

Taos ojämlikhet

Givet diskreta slumpvariabler $X$ , $Y$ och $Y'$ , så att $X$ endast tar värden i intervallet [−1, 1] och $Y'$ bestäms av $Y$ (så att $H(Y'|Y)=0$ ), vi har

\operatörsnamn {E} {\big (} {\big |}\operatörsnamn {E} (X|Y')-\operatörsnamn {E} (X\mid Y){\big |}{\big )}\leq {\sqrt {I(X;Y\ mitten Y')\,2\log 2}},

relatera den villkorade förväntningen till den villkorade ömsesidiga informationen . Detta är en enkel konsekvens av Pinskers ojämlikhet . (Obs: korrektionsfaktorn log 2 inuti radikalen uppstår eftersom vi mäter den villkorliga ömsesidiga informationen i bitar snarare än nats .)

Maskinbaserad provkontroll av informationsteoretiska ojämlikheter

Flera maskinbaserade provkontrollalgoritmer är nu tillgängliga. Provkontrollalgoritmer verifierar vanligtvis ojämlikheterna som antingen sanna eller falska. Mer avancerade provkontrollalgoritmer kan producera bevis eller motexempel. ITIP är en Matlab-baserad provkontroll för alla Shannon-typ Ojämlikheter. Xitip är en öppen källkod, snabbare version av samma algoritm implementerad i C med ett grafiskt gränssnitt. Xitip har också en inbyggd språkanalysfunktion som stöder ett bredare utbud av slumpvariablebeskrivningar som input. AITIP och oXitip är molnbaserade implementeringar för att validera ojämlikheter av Shannon-typ. oXitip använder GLPK optimizer och har en C++ backend baserad på Xitip med ett webbaserat användargränssnitt. AITIP använder Gurobi-lösaren för optimering och en blandning av python och C++ i backend-implementeringen. Det kan också ge en kanonisk nedbrytning av ojämlikheterna när det gäller grundläggande informationsåtgärder.

Se även

^ Yeung, RW (1997). "Ett ramverk för linjär informationsjämlikhet". IEEE-transaktioner på informationsteori . 43 (6): 1924–1934. doi : 10.1109/18.641556 . )
^ Zhang, Z.; Yeung, RW (1998). "Om karakterisering av entropifunktion via informationsjämlikheter". IEEE-transaktioner på informationsteori . 44 (4): 1440–1452. doi : 10.1109/18.681320 .
^ Matus, F. (2007). Oändligt många informationsskillnader . 2007 IEEE International Symposium on Information Theory.
^ Fuchs, Aimé; Letta, Giorgio (1970). L'inégalité de Kullback. Ansökan à la théorie de l'estimation . Séminaire de Probabilités . Föreläsningsanteckningar i matematik. Vol. 4. Strasbourg. s. 108–131. doi : 10.1007/bfb0059338 . ISBN 978-3-540-04913-5 . MR 0267669 .
^ Hirschman, II (1957). "En anteckning om entropi". American Journal of Mathematics . 79 (1): 152–156. doi : 10.2307/2372390 . JSTOR 2372390 .
^ Beckner, W. (1975). "Ojämlikheter i Fourieranalys". Annals of Mathematics . 102 (6): 159–182. doi : 10.2307/1970980 . JSTOR 1970980 .
^ Tao, T. (2006). "Szemerédis regelbundenhet lemma återbesökt". Bidrag. Diskret matematik . 1 :8–28. arXiv : math/0504472 . Bibcode : 2005math......4472T .
^ Ahlswede, Rudolf (2007). "Den slutliga formen av Taos ojämlikhet relaterad till villkorade förväntningar och villkorad ömsesidig information" . Framsteg i kommunikationsmatematik . 1 (2): 239–242. doi : 10.3934/amc.2007.1.239 .
^ ^a ^b Ho, SW; Ling, L.; Tan, CW; Yeung, RW (2020). "Bevisa och motbevisa informationsskillnader: teori och skalbara algoritmer". IEEE-transaktioner på informationsteori . 66 (9): 5525–5536. doi : 10.1109/TIT.2020.2982642 .

externa länkar

Thomas M. Cover, Joy A. Thomas. Elements of Information Theory , Kapitel 16, "Inequalities in Information Theory" John Wiley & Sons, Inc. 1991 Skriv ut ISBN 0-471-06259-6 Online ISBN 0-471-20061-1 pdf ^{[ permanent död länk ]}
Amir Dembo, Thomas M. Cover, Joy A. Thomas. Informationsteoretiska ojämlikheter. IEEE Transactions on Information Theory, Vol. 37, nr 6, november 1991. pdf
ITIP: http://user-www.ie.cuhk.edu.hk/~ITIP/
XITIP: http://xitip.epfl.ch
NR Pai, Suhas Diggavi, T. Gläßle, E. Perron, R.Pulikkoonattu, RW Yeung, Y. Yan, oXitip: An Online Information Theoretic Inequalities Prover http://www.oxitip.com
Siu Wai Ho, Lin Ling, Chee Wei Tan och Raymond W. Yeung, AITIP (Information Theoretic Inequality Prover): https://aitip.org
Nivedita Rethnakar, Suhas Diggavi, Raymond. W. Yeung, InformationInequalities.jl: Exploring Information-Theoretic Inequalities, Julia Package, 2021 [ 1]

[1] Yeung, RW (1997). "Ett ramverk för linjär informationsjämlikhet". IEEE-transaktioner på informationsteori . 43 (6): 1924–1934. doi : 10.1109/18.641556 . )

[:1-2] Zhang, Z.; Yeung, RW (1998). "Om karakterisering av entropifunktion via informationsjämlikheter". IEEE-transaktioner på informationsteori . 44 (4): 1440–1452. doi : 10.1109/18.681320 .

[3] Matus, F. (2007). Oändligt många informationsskillnader . 2007 IEEE International Symposium on Information Theory.

[4] Fuchs, Aimé; Letta, Giorgio (1970). L'inégalité de Kullback. Ansökan à la théorie de l'estimation . Séminaire de Probabilités . Föreläsningsanteckningar i matematik. Vol. 4. Strasbourg. s. 108–131. doi : 10.1007/bfb0059338 . ISBN 978-3-540-04913-5 . MR 0267669 .

[5] Hirschman, II (1957). "En anteckning om entropi". American Journal of Mathematics . 79 (1): 152–156. doi : 10.2307/2372390 . JSTOR 2372390 .

[6] Beckner, W. (1975). "Ojämlikheter i Fourieranalys". Annals of Mathematics . 102 (6): 159–182. doi : 10.2307/1970980 . JSTOR 1970980 .

[7] Tao, T. (2006). "Szemerédis regelbundenhet lemma återbesökt". Bidrag. Diskret matematik . 1 :8–28. arXiv : math/0504472 . Bibcode : 2005math......4472T .

[8] Ahlswede, Rudolf (2007). "Den slutliga formen av Taos ojämlikhet relaterad till villkorade förväntningar och villkorad ömsesidig information" . Framsteg i kommunikationsmatematik . 1 (2): 239–242. doi : 10.3934/amc.2007.1.239 .

[IEEE-66-9-9] Ho, SW; Ling, L.; Tan, CW; Yeung, RW (2020). "Bevisa och motbevisa informationsskillnader: teori och skalbara algoritmer". IEEE-transaktioner på informationsteori . 66 (9): 5525–5536. doi : 10.1109/TIT.2020.2982642 .