Desigualdades en la teoría de la información

Concepto en la teoría de la información

Las desigualdades son muy importantes en el estudio de la teoría de la información . Existen diversos contextos en los que aparecen estas desigualdades.

Desigualdades entrópicas

Consideremos una tupla de variables aleatorias con un número finito (o como máximo contable) de soportes en el mismo espacio de probabilidad . Hay 2 ⁿ subconjuntos para los que se pueden calcular entropías ( conjuntas ). Por ejemplo, cuando n  = 2, podemos considerar las entropías y . Satisfacen las siguientes desigualdades (que juntas caracterizan el rango de las entropías marginales y conjuntas de dos variables aleatorias): ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ ${\displaystyle n}$ ${\displaystyle H(X_{1}),}$ ${\displaystyle H(X_{2}),}$ ${\displaystyle H(X_{1},X_{2})}$

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

De hecho, todos ellos pueden expresarse como casos especiales de una única desigualdad que involucra la información mutua condicional , a saber:

${\displaystyle I(A;B|C)\geq 0,}$

donde , , y cada una denota la distribución conjunta de algún subconjunto arbitrario (posiblemente vacío) de nuestra colección de variables aleatorias. Las desigualdades que pueden derivarse como combinaciones lineales de esto se conocen como desigualdades de tipo Shannon . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

Para valores mayores hay restricciones adicionales sobre los posibles valores de entropía. Para hacer esto preciso, un vector en indexado por subconjuntos de se dice que es entrópico si hay una distribución discreta conjunta de n variables aleatorias tal que es su entropía conjunta , para cada subconjunto . El conjunto de vectores entrópicos se denota , siguiendo la notación de Yeung. ^[1] No es cerrado ni convexo para , pero se sabe que su cierre topológico es convexo y, por lo tanto, puede caracterizarse por las (infinitas) desigualdades lineales satisfechas por todos los vectores entrópicos, llamadas desigualdades entrópicas . ${\displaystyle n}$ ${\displaystyle h}$ ${\displaystyle \mathbb {R} ^{2^{n}}}$ ${\displaystyle \{1,\dots ,n\}}$ ${\displaystyle X_{1},\dots ,X_{n}}$ ${\displaystyle h_{I}=H(X_{i}\colon i\in I)}$ ${\displaystyle I}$ ${\displaystyle \Gamma _{n}^{*}}$ ${\displaystyle n\geq 3}$ ${\displaystyle {\overline {\Gamma _{n}^{*}}}}$

El conjunto de todos los vectores que satisfacen desigualdades de tipo Shannon (pero no necesariamente otras desigualdades entrópicas) contiene . Esta contención es estricta para y las desigualdades posteriores se conocen como desigualdades de tipo no Shannon . Zhang y Yeung informaron la primera desigualdad de tipo no Shannon, ^[2] a menudo denominada desigualdad de Zhang-Yeung. Matus ^[3] demostró que ningún conjunto finito de desigualdades puede caracterizar (por combinaciones lineales) todas las desigualdades entrópicas. En otras palabras, la región no es un politopo . ${\displaystyle {\overline {\Gamma _{n}^{*}}}}$ ${\displaystyle n\geq 4}$ ${\displaystyle {\overline {\Gamma _{n}^{*}}}}$

Límites inferiores para la divergencia de Kullback-Leibler

En la teoría de la información, muchas desigualdades importantes son, en realidad, límites inferiores para la divergencia de Kullback-Leibler . Incluso las desigualdades de tipo Shannon pueden considerarse parte de esta categoría, ya que la información de interacción puede expresarse como la divergencia de Kullback-Leibler de la distribución conjunta con respecto al producto de las marginales y, por lo tanto, estas desigualdades pueden considerarse un caso especial de la desigualdad de Gibbs .

Por otra parte, parece mucho más difícil derivar límites superiores útiles para la divergencia de Kullback–Leibler. Esto se debe a que la divergencia de Kullback–Leibler D _KL ( P || Q ) depende muy sensiblemente de eventos que son muy raros en la distribución de referencia Q . D _KL ( P || Q ) aumenta sin límite a medida que un evento de probabilidad finita distinta de cero en la distribución P se vuelve extremadamente raro en la distribución de referencia Q , y de hecho D _KL ( P || Q ) ni siquiera está definido si un evento de probabilidad distinta de cero en P tiene probabilidad cero en Q . (De ahí el requisito de que P sea absolutamente continuo con respecto a Q .)

Desigualdad de Gibbs

Esta desigualdad fundamental establece que la divergencia de Kullback-Leibler no es negativa.

Desigualdad de Kullback

Otra desigualdad relativa a la divergencia de Kullback-Leibler se conoce como desigualdad de Kullback . ^[4] Si P y Q son distribuciones de probabilidad en la línea real con P absolutamente continua con respecto a Q, y cuyos primeros momentos existen, entonces

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

donde es la función de tasa de grandes desviaciones , es decir , el conjugado convexo de la función generadora de cumulantes , de Q , y es el primer momento de P. ${\displaystyle \Psi _{Q}^{*}}$ ${\displaystyle \mu '_{1}(P)}$

El límite de Cramér-Rao es un corolario de este resultado.

Desigualdad de Pinsker

La desigualdad de Pinsker relaciona la divergencia de Kullback-Leibler y la distancia de variación total . Establece que si P , Q son dos distribuciones de probabilidad , entonces

${\displaystyle {\sqrt {{\frac {1}{2}}D_{KL}^{(e)}(P\parallel Q)}}\geq \sup\{|P(A)-Q(A)|:A{\text{ is an event to which probabilities are assigned.}}\}.}$

dónde

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

es la divergencia de Kullback-Leibler en nats y

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

es la distancia de variación total.

Otras desigualdades

Incertidumbre de Hirschman

En 1957, ^[5] Hirschman demostró que para una función (razonablemente bien comportada) tal que y su transformada de Fourier la suma de las entropías diferenciales de y no es negativa, es decir ${\displaystyle f:\mathbb {R} \rightarrow \mathbb {C} }$ ${\displaystyle \int _{-\infty }^{\infty }|f(x)|^{2}\,dx=1,}$ ${\displaystyle g(y)=\int _{-\infty }^{\infty }f(x)e^{-2\pi ixy}\,dx,}$ ${\displaystyle |f|^{2}}$ ${\displaystyle |g|^{2}}$

${\displaystyle -\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 conjeturó, y más tarde se demostró, ^[6] que un límite más preciso de lo que se alcanza en el caso de una distribución gaussiana , podría reemplazar al lado derecho de esta desigualdad. Esto es especialmente significativo ya que implica, y es más fuerte que, la formulación de Weyl del principio de incertidumbre de Heisenberg . ${\displaystyle \log(e/2),}$

La desigualdad de Tao

Dadas variables aleatorias discretas , , y , tales que toman valores solo en el intervalo [−1, 1] y están determinadas por (tales que ), tenemos ^{[7] [8]} ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y'}$ ${\displaystyle X}$ ${\displaystyle Y'}$ ${\displaystyle Y}$ ${\displaystyle H(Y'|Y)=0}$

${\displaystyle \operatorname {E} {\big (}{\big |}\operatorname {E} (X|Y')-\operatorname {E} (X\mid Y){\big |}{\big )}\leq {\sqrt {I(X;Y\mid Y')\,2\log 2}},}$

relacionar la expectativa condicional con la información mutua condicional . Esta es una consecuencia simple de la desigualdad de Pinsker . (Nota: el factor de corrección log 2 dentro del radical surge porque estamos midiendo la información mutua condicional en bits en lugar de en nats ).

Comprobador de pruebas basado en máquinas de desigualdades de teoría de la información

Actualmente, se encuentran disponibles varios algoritmos de verificación de pruebas basados ​​en máquinas. Los algoritmos de verificación de pruebas generalmente verifican las desigualdades como verdaderas o falsas. Los algoritmos de verificación de pruebas más avanzados pueden producir pruebas o contraejemplos. ^[9] ITIP es un verificador de pruebas basado en Matlab para todas las desigualdades de tipo Shannon. Xitip es una versión de código abierto y más rápida del mismo algoritmo implementado en C con una interfaz gráfica. Xitip también tiene una función de análisis de lenguaje incorporada que admite una gama más amplia de descripciones de variables aleatorias como entrada. AITIP y oXitip son implementaciones basadas en la nube para validar las desigualdades de tipo Shannon. oXitip utiliza el optimizador GLPK y tiene un backend C++ basado en Xitip con una interfaz de usuario basada en web. AITIP utiliza el solucionador Gurobi para la optimización y una mezcla de Python y C++ en la implementación del backend. También puede proporcionar el desglose canónico de las desigualdades en términos de medidas de información básica. ^[9]

Véase también

• Desigualdad en el procesamiento de datos
• Límite Cramér–Rao
• Desigualdad de potencia de entropía
• Vector entrópico
• Desigualdad de Fano
• Desigualdad de Jensen
• Desigualdad de Kraft
• Desigualdad de Pinsker

Referencias

1. Yeung, RW (1997). "Un marco para desigualdades de información lineal". IEEE Transactions on Information Theory . 43 (6): 1924–1934. doi :10.1109/18.641556.)
2. Zhang, Z.; Yeung, RW (1998). "Sobre la caracterización de la función de entropía a través de desigualdades de información". IEEE Transactions on Information Theory . 44 (4): 1440–1452. doi :10.1109/18.681320.
3. Matus, F. (2007). Infinitas desigualdades de información . Simposio Internacional IEEE sobre Teoría de la Información de 2007.
4. Fuchs, Aimé; Letta, Giorgio (1970). "L'Inégalité de KULLBACK. Aplicación a la teoría de la estimación". Séminario de Probabilités IV Universidad de Estrasburgo. Apuntes de conferencias de matemáticas. vol. 124. Estrasburgo. págs. 108-131. doi :10.1007/bfb0059338. ISBN 978-3-540-04913-5.Sr. 0267669  .{{cite book}}: CS1 maint: location missing publisher (link)
5. Hirschman, II (1957). "Una nota sobre la entropía". Revista Americana de Matemáticas . 79 (1): 152–156. doi :10.2307/2372390. JSTOR  2372390.
6. Beckner, W. (1975). "Desigualdades en el análisis de Fourier". Anales de Matemáticas . 102 (6): 159–182. doi :10.2307/1970980. JSTOR  1970980.
7. Tao, T. (2006). "Revisión del lema de regularidad de Szemerédi". Contribución. Matemática discreta . 1 : 8–28. arXiv : math/0504472 . Código Bibliográfico :2005math......4472T.
8. Ahlswede, Rudolf (2007). "La forma final de la desigualdad de Tao que relaciona la expectativa condicional y la información mutua condicional". Avances en Matemáticas de las Comunicaciones . 1 (2): 239–242. doi : 10.3934/amc.2007.1.239 .
9. Ho, SW; Ling, L.; Tan, CW; Yeung, RW (2020). "Probar y refutar desigualdades de información: teoría y algoritmos escalables". IEEE Transactions on Information Theory . 66 (9): 5525–5536. doi :10.1109/TIT.2020.2982642. S2CID  216530139.

Enlaces externos

• Thomas M. Cover, Joy A. Thomas. Elementos de la teoría de la información , Capítulo 16, "Desigualdades en la teoría de la información" John Wiley & Sons, Inc. 1991 ISBN impreso 0-471-06259-6 ISBN en línea 0-471-20061-1  
• Amir Dembo, Thomas M. Cover, Joy A. Thomas. Desigualdades teóricas de la información. IEEE Transactions on Information Theory, vol. 37, n.º 6, noviembre de 1991. pdf
• ITIP: http://user-www.ie.cuhk.edu.hk/~ITIP/
• Sitio web de Xitip: http://xitip.epfl.ch
• NR Pai, Suhas Diggavi, T. Gläßle, E. Perron, R.Pulikkoonattu, RW Yeung, Y. Yan, oXitip: Un demostrador de desigualdades teóricas de la información en línea http://www.oxitip.com
• Siu Wai Ho, Lin Ling, Chee Wei Tan y Raymond W. Yeung, AITIP (Demostración de desigualdad teórica de la información): https://aitip.org
• Nivedita Rethnakar, Suhas Diggavi, Raymond. W. Yeung, InformationInequalities.jl: Explorando desigualdades teóricas de la información, Julia Package, 2021 [1]