Dimensión de la información

En teoría de la información , la dimensión de información es una medida de información para vectores aleatorios en el espacio euclidiano , basada en la entropía normalizada de versiones finamente cuantificadas de los vectores aleatorios . Este concepto fue introducido por primera vez por Alfréd Rényi en 1959. ^{[ 1 ]}

En pocas palabras, es una medida de la dimensión fractal de una distribución de probabilidad . Caracteriza la tasa de crecimiento de la entropía de Shannon dada por discretizaciones cada vez más finas del espacio.

En 2010, Wu y Verdú proporcionaron una caracterización operativa de la dimensión de información de Rényi como el límite fundamental de la compresión de datos casi sin pérdidas para fuentes analógicas bajo diversas restricciones de regularidad del codificador/decodificador.

La entropía de una variable aleatoria discreta${\displaystyle Z}$es

${\displaystyle \mathbb {H} _{0}(Z)=\sum _{z\in supp(P_{Z})}P_{Z}(z)\log _{2}{\frac {1}{P_{Z}(z)}}}$

dónde${\displaystyle P_{Z}(z)}$es la medida de probabilidad de${\displaystyle Z}$cuando${\displaystyle Z=z}$y el${\displaystyle supp(P_{Z})}$denota un conjunto${\displaystyle \{z|z\in {\mathcal {Z}},P_{Z}(z)>0\}}$.

Dejar${\displaystyle X}$Sea una variable aleatoria arbitraria de valor real. Dado un entero positivo${\displaystyle m}$creamos una nueva variable aleatoria discreta

${\displaystyle \langle X\rangle _{m}={\frac {\lfloor mX\rfloor }{m}}}$

donde el${\displaystyle \lfloor \cdot \rfloor }$es el operador piso que convierte un número real al mayor entero menor que él.

${\displaystyle {\underline {d}}(X)=\liminf _{m\rightarrow \infty }{\frac {\mathbb {H} _{0}(\langle X\rangle _{m})}{\log _{2}m}}}$

y

${\displaystyle {\bar {d}}(X)=\limsup _{m\rightarrow \infty }{\frac {\mathbb {H} _{0}(\langle X\rangle _{m})}{\log _{2}m}}}$

se denominan dimensiones de información inferior y superior de${\displaystyle X}$respectivamente. Cuando${\displaystyle {\underline {d}}(X)={\bar {d}}(X)}$, llamamos a esta dimensión de información de valor de${\displaystyle X}$,

${\displaystyle d(X)=\lim _{m\rightarrow \infty }{\frac {\mathbb {H} _{0}(\langle X\rangle _{m})}{\log _{2}m}}}$

Algunas propiedades importantes de la dimensión de la información${\displaystyle d(X)}$:

• Si la condición es leve${\displaystyle \mathbb {H} (\lfloor X\rfloor )<\infty }$se cumple, tenemos${\displaystyle 0\leq {\underline {d}}(X)\leq {\bar {d}}(X)\leq 1}$.
• Para un${\displaystyle n}$vector aleatorio de dimensión${\displaystyle {\vec {X}}}$, la primera propiedad puede generalizarse a${\displaystyle 0\leq {\underline {d}}({\vec {X}})\leq {\bar {d}}({\vec {X}})\leq n}$.
• Basta con calcular las dimensiones de información superior e inferior al restringirse a la subsecuencia exponencial.${\displaystyle m=2^{l}}$.
• ${\displaystyle {\underline {d}}(X)}$y${\displaystyle {\bar {d}}(X)}$se mantienen sin cambios si se utilizan funciones de redondeo o de techo en la cuantización.

Si la dimensión de la información${\displaystyle d}$existe, uno puede definir el${\displaystyle d}$entropía -dimensional de esta distribución por

${\displaystyle \mathbb {H} _{d(X)}(X)=\lim _{n\rightarrow +\infty }(\mathbb {H} _{0}(\langle X\rangle _{n})-d(X)\log _{2}n)}$

siempre que exista el límite. Si${\displaystyle d=0}$, la entropía cero-dimensional es igual a la entropía de Shannon estándar.${\displaystyle \mathbb {H} _{0}(X)}$. Para dimensión entera${\displaystyle d=n\geq 1}$, el${\displaystyle n}$La entropía dimensional es la${\displaystyle n}$Integral de -veces que define la entropía diferencial correspondiente .

En 1994, Kawabata y Dembo propusieron una nueva forma de medir la información basada en el valor de distorsión de la tasa de una variable aleatoria. La medida se define como

${\displaystyle d_{R}(X)=-2{\frac {R(X,D)}{\log D}},}$

dónde${\displaystyle R(X,D)}$es la función de distorsión de tasa que se define como

${\displaystyle R(X,D)=\min _{\|X-{\hat {X}}\|_{2}\leq D}I(X,{\hat {X}}),}$

o equivalentemente, información mínima que podría conducir a una${\displaystyle D}$-aproximación cercana de${\displaystyle X}$.

Además, demostraron que dicha definición es equivalente a la definición de dimensión de información. Formalmente,

${\displaystyle d_{R}(X)=d(X).}$

Utilizando la definición anterior de dimensión de información de Rényi, se define una medida similar a la entropía d -dimensional en Charusaie, Amini y Rini 2022. Este valor${\displaystyle b(X)}$que se denomina sesgo de tasa dimensional se define de manera que capture el término finito de la función de distorsión de tasa. Formalmente,

${\displaystyle R(X,D)=-{\frac {d(X)}{2}}\log {\frac {2\pi eD}{d(X)}}+b(X).}$

El sesgo de tasa dimensional es igual a la tasa d -dimensional para distribuciones continuas , discretas y mixtas discretas-continuas. Además, se puede calcular para un conjunto de variables aleatorias singulares , mientras que la entropía d -dimensional no necesariamente existe en ese caso.

Finalmente, el sesgo de tasa dimensional generaliza la entropía de Shannon y la entropía diferencial , ya que se podría encontrar la información mutua.${\displaystyle I(X;Y)}$utilizando la siguiente fórmula:

${\displaystyle I(X;Y)=b(X)+b(Y)-b(X,Y).}$

Según el teorema de descomposición de Lebesgue , ^{[ 2 ]} una distribución de probabilidad puede representarse de forma única mediante la mezcla

${\displaystyle v=pP_{Xd}+qP_{Xc}+rP_{Xs}}$

dónde${\displaystyle p+q+r=1}$y${\displaystyle p,q,r\geq 0}$;${\displaystyle P_{Xd}}$es una medida de probabilidad puramente atómica (parte discreta),${\displaystyle P_{Xc}}$ es la medida de probabilidad absolutamente continua, y${\displaystyle P_{Xs}}$ es una medida de probabilidad singular con respecto a la medida de Lebesgue pero sin átomos (parte singular). Sea${\displaystyle X}$ sea ​​una variable aleatoria tal que${\displaystyle \mathbb {H} (\lfloor X\rfloor )<\infty }$. Supongamos la distribución de${\displaystyle X}$puede representarse como

${\displaystyle v=(1-\rho )P_{Xd}+\rho P_{Xc}}$

dónde${\displaystyle P_{Xd}}$es una medida discreta y${\displaystyle P_{Xc}}$es la medida de probabilidad absolutamente continua con${\displaystyle 0\leq \rho \leq 1}$. Entonces

${\displaystyle d(X)=\rho }$

Además, dado${\displaystyle \mathbb {H} _{0}(P_{Xd})}$ y entropía diferencial${\displaystyle h(P_{Xc})}$, el${\displaystyle d}$-La entropía dimensional viene dada simplemente por

${\displaystyle \mathbb {H} _{\rho }(X)=(1-\rho )\mathbb {H} _{0}(P_{Xd})+\rho h(P_{Xc})+\mathbb {H} _{0}(\rho )}$

dónde${\displaystyle \mathbb {H} _{0}(\rho )}$ es la entropía de Shannon de una variable aleatoria discreta${\displaystyle Z}$con${\displaystyle P_{Z}(1)=\rho }$y${\displaystyle P_{Z}(0)=1-\rho }$y dado por

${\displaystyle \mathbb {H} _{0}(\rho )=\rho \log _{2}{\frac {1}{\rho }}+(1-\rho )\log _{2}{\frac {1}{1-\rho }}}$

Ejemplo

Consideremos una señal que tiene una distribución de probabilidad gaussiana .

Hacemos pasar la señal a través de un rectificador de media onda que convierte todos los valores negativos a 0 y mantiene todos los demás valores. El rectificador de media onda se puede caracterizar por la función

${\displaystyle f(x)={\begin{cases}x,&{\text{if }}x\geq 0\\0,&x<0\end{cases}}}$

Luego, a la salida del rectificador, la señal tiene una distribución gaussiana rectificada . Se caracteriza por una masa atómica de peso 0,5 y tiene una función de densidad de probabilidad gaussiana para todos${\displaystyle x>0}$.

Con esta distribución de mezcla, aplicamos la fórmula anterior y obtenemos la dimensión de información.${\displaystyle d}$de la distribución y calcular la${\displaystyle d}$entropía -dimensional.

${\displaystyle d(X)=\rho =0.5}$

La parte derecha normalizada de la distribución gaussiana de media cero tiene entropía.${\displaystyle h(P_{Xc})={\frac {1}{2}}\log _{2}(2\pi e\sigma ^{2})-1}$, por eso

${\displaystyle {\begin{aligned}\mathbb {H} _{0.5}(X)&=(1-0.5)(1\log _{2}1)+0.5h(P_{Xc})+\mathbb {H} _{0}(0.5)\\&=0+{\frac {1}{2}}({\frac {1}{2}}\log _{2}(2\pi e\sigma ^{2})-1)+1\\&={\frac {1}{4}}\log _{2}(2\pi e\sigma ^{2})+{\frac {1}{2}}\,{\text{ bit(s)}}\end{aligned}}}$

Se muestra ^{[ 3 ]} que la dimensión de la información y la entropía diferencial están estrechamente relacionadas.

Dejar${\displaystyle X}$sea ​​una variable aleatoria con densidad continua${\displaystyle f(x)}$.

Supongamos que dividimos el rango de${\displaystyle X}$en contenedores de longitud${\displaystyle \Delta }$Por el teorema del valor medio , existe un valor${\displaystyle x_{i}}$dentro de cada contenedor de tal manera que

${\displaystyle f(x_{i})\Delta =\int _{i\Delta }^{(i+1)\Delta }f(x)\;\mathrm {d} x}$

Consideremos la variable aleatoria discretizada${\displaystyle X^{\Delta }=x_{i}}$si ${\displaystyle i\Delta \leq X<(i+1)\Delta }$.

La probabilidad de cada punto de soporte${\displaystyle X^{\Delta }=x_{i}}$es

${\displaystyle P_{X^{\Delta }}(x_{i})=\int _{i\Delta }^{(i+1)\Delta }f(x)\;\mathrm {d} x=f(x_{i})\Delta }$

Dejar${\displaystyle S=\operatorname {supp} (P_{X^{\Delta }})}$. La entropía de${\displaystyle X^{\Delta }}$es

${\displaystyle {\begin{aligned}\mathbb {H} _{0}(X^{\Delta })&=-\sum _{x_{i}\in S}P_{X^{\Delta }}\log _{2}P_{X^{\Delta }}\\&=-\sum _{x_{i}\in S}f(x_{i})\Delta \log _{2}(f(x_{i})\Delta )\\&=-\sum _{x_{i}\in S}\Delta f(x_{i})\log _{2}f(x_{i})-\sum _{x_{i}\in S}f(x_{i})\Delta \log _{2}\Delta \\&=-\sum _{x_{i}\in S}\Delta f(x_{i})\log _{2}f(x_{i})-\log _{2}\Delta \\\end{aligned}}}$

Si establecemos${\displaystyle \Delta =1/m}$y${\displaystyle x_{i}=i/m}$Entonces estamos haciendo exactamente la misma cuantización que la definición de dimensión de información. Dado que el reetiquetado de los eventos de una variable aleatoria discreta no cambia su entropía, tenemos

${\displaystyle \mathbb {H} _{0}(X^{1/m})=\mathbb {H} _{0}(\langle X\rangle _{m}).}$

Esto produce

${\displaystyle \mathbb {H} _{0}(\langle X\rangle _{m})=-\sum {\frac {1}{m}}f(x_{i})\log _{2}f(x_{i})+\log _{2}m}$

y cuando${\displaystyle m}$es suficientemente grande,

${\displaystyle -\sum \Delta f(x_{i})\log _{2}f(x_{i})\approx \int f(x)\log _{2}{\frac {1}{f(x)}}\mathrm {d} x}$

que es la entropía diferencial${\displaystyle h(x)}$de la variable aleatoria continua. En particular, si${\displaystyle f(x)}$es integrable de Riemann, entonces

${\displaystyle h(X)=\lim _{m\rightarrow \infty }\mathbb {H} _{0}(\langle X\rangle _{m})-\log _{2}(m).}$

Comparándolo con el${\displaystyle d}$La entropía n-dimensional muestra que la entropía diferencial es exactamente la entropía unidimensional.

${\displaystyle h(X)=\mathbb {H} _{1}(X).}$

De hecho, esto puede generalizarse a dimensiones superiores. Rényi demuestra que, si${\displaystyle {\vec {X}}}$es un vector aleatorio en un${\displaystyle n}$espacio euclidiano de -dimensiones${\displaystyle \Re ^{n}}$con una distribución absolutamente continua con una función de densidad de probabilidad${\displaystyle f_{\vec {X}}({\vec {x}})}$y entropía finita de la parte entera (${\displaystyle H_{0}(\langle {\vec {X}}\rangle _{m})<\infty }$), tenemos ${\displaystyle d({\vec {X}})=n}$

y

${\displaystyle \mathbb {H} _{n}({\vec {X}})=\int \cdots \int f_{\vec {X}}({\vec {x}})\log _{2}{\frac {1}{f_{\vec {X}}({\vec {x}})}}\mathrm {d} {\vec {x}},}$

si la integral existe.

La dimensión de información de una distribución proporciona un límite superior teórico para la tasa de compresión, si se desea comprimir una variable proveniente de dicha distribución. En el contexto de la compresión de datos sin pérdidas, se busca comprimir números reales con otros números reales de precisión infinita.

El objetivo principal de la compresión de datos sin pérdidas es encontrar representaciones eficientes para las realizaciones de la fuente.${\displaystyle x^{n}\in {\mathcal {X}}^{n}}$por${\displaystyle y^{n}\in {\mathcal {Y}}^{n}}$. A${\displaystyle (n,k)-}$código para${\displaystyle \{X_{i}:i\in {\mathcal {N}}\}}$es un par de asignaciones:

• codificador:${\displaystyle f_{n}:{\mathcal {X}}^{n}\rightarrow {\mathcal {Y}}^{k}}$que convierte la información de una fuente en símbolos para su comunicación o almacenamiento;
• descifrador:${\displaystyle g_{n}:{\mathcal {Y}}^{k}\rightarrow {\mathcal {X}}^{n}}$Es el proceso inverso, que consiste en convertir los símbolos del código de nuevo a un formato que el destinatario entienda.

La probabilidad de error de bloque es${\displaystyle {\mathcal {P}}\{g_{n}(f_{n}(X^{n}))\neq X^{n}\}}$.

Definir${\displaystyle r(\epsilon )}$ser el ínfimo de${\displaystyle r\geq 0}$de tal manera que exista una secuencia de${\displaystyle (n,\lfloor rn\rfloor )-}$códigos tales que${\displaystyle {\mathcal {P}}\{g_{n}(f_{n}(X^{n}))\neq X^{n}\}\leq \epsilon }$para todos suficientemente grandes${\displaystyle n}$.

Entonces${\displaystyle r(\epsilon )}$Básicamente, proporciona la relación entre la longitud del código y la longitud de la fuente, y muestra qué tan bueno es un par codificador-decodificador específico. Los límites fundamentales en la codificación de fuente sin pérdidas son los siguientes. ^{[ 4 ]}

Consideremos una función codificadora continua.${\displaystyle f(x):{\mathbb {R} }^{n}\rightarrow {\mathbb {R} }^{\lfloor Rn\rfloor }}$con su función de decodificación continua${\displaystyle g(x):{\mathbb {R} }^{\lfloor Rn\rfloor }\rightarrow {\mathbb {R} }^{n}}$. Si no imponemos ninguna regularidad en${\displaystyle f(x)}$y${\displaystyle g(x)}$, debido a la rica estructura de${\displaystyle \Re }$, tenemos el mínimo${\displaystyle \epsilon }$-tasa alcanzable${\displaystyle R_{0}(\epsilon )=0}$a pesar de${\displaystyle 0<\epsilon \leq 1}$Esto significa que se puede construir un par codificador-decodificador con una tasa de compresión infinita.

Para obtener algunas conclusiones no triviales y significativas, dejemos${\displaystyle R^{*}(\epsilon )}$el mínimo${\displaystyle \epsilon -}$tasa alcanzable para codificador lineal y decodificador Borel. Si variable aleatoria${\displaystyle X}$tiene una distribución que es una mezcla de parte discreta y continua. Entonces${\displaystyle R^{*}(\epsilon )=d(X)}$a pesar de${\displaystyle 0<\epsilon \leq 1}$Supongamos que restringimos el decodificador a una función continua de Lipschitz y${\displaystyle {\bar {d}}(X)<\infty }$ se mantiene, entonces el mínimo${\displaystyle \epsilon -}$tasa alcanzable${\displaystyle R(\epsilon )\geq {\bar {d}}(X)}$a pesar de${\displaystyle 0<\epsilon \leq 1}$.

El papel fundamental de la dimensión de la información en la compresión de datos sin pérdidas se extiende más allá de los datos i.i.d. Se demuestra que, para procesos específicos (por ejemplo, procesos de media móvil), la relación de compresión sin pérdidas también es igual a la tasa de la dimensión de la información. ^{[ 5 ]} Este resultado permite una mayor compresión que no era posible considerando únicamente la distribución marginal del proceso.

• Dimensión fractal
• Dimensión de correlación
• Entropía (teoría de la información)

• Çınlar, Erhan (2011). Probabilidad y estocástica . Textos de posgrado en matemáticas. Vol.  261. Springer. doi : 10.1007/978-0-387-87859-1 . ISBN 978-0-387-87858-4.

• Cover, Thomas M.; Thomas, Joy A. (2012). Elementos de la teoría de la información (2.ª  ed.). Wiley. págs. 247–248 . ISBN  9781118585771.

• Rényi, A. (marzo de 1959). "Sobre la dimensión y entropía de las distribuciones de probabilidad" . Acta Mathematica Academiae Scientiarum Hungaricae . 10 ( 1– 2): 193– 215. doi : 10.1007/BF02063299 . ISSN 0001-5954 . S2CID 121006720 .  

• Wu, Yihong; Verdu, S. (agosto de 2010). "Dimensión de información de Rényi: límites fundamentales de la compresión analógica casi sin pérdidas". IEEE Transactions on Information Theory . 56 (8): 3721– 3748. doi : 10.1109/TIT.2010.2050803 . ISSN 0018-9448 . S2CID 206737933 .  
• Charusaie, M.; Amini, A.; Rini, S. (mayo de 2022). "Medidas de compresibilidad para vectores aleatorios singulares afines" . IEEE Transactions on Information Theory . 68 (9): 6245– 6275. arXiv : 2001.03884 . doi : 10.1109/TIT.2022.3174623 .

• Kawabata, T.; Dembo, A. (septiembre de 1994). "La dimensión de distorsión de tasa de conjuntos y medidas" . IEEE Transactions on Information Theory . 40 (5): 1564– 1572. doi : 10.1109/18.333868 .