Teorema de procesamiento de la información

[gL.edu] Este artículo recoge contribuciones de Daniel Gracia Garallar, Adrià Espí Escrihuela, elaboradas en el contexto de la Clarificación conceptual en torno a la "teoría de la información", bajo la supervisión de José María Díaz Nafría.

Definiciones

El Teorema de Procesamiento de la Información (en inglés, data-processing inequality) establece que ningún proceso de transformación de datos puede aumentar la información contenida en una señal de datos.

De forma sucinta, podemos definir el Teorema de Procesamiento de la Información como:

Si $X\rightarrow Y\rightarrow Z$ (i. e., si las tres variables aleatorias forman una cadena de Markov), entonces $I(X;Y)\geq I(X;Z)$.

Propiedades

Supongamos las variables aleatorias $X$, $Y$ y $Z$, donde la distribución condicional de $Z$ depende solo de $Y$ y es condicionalmente independiente de $X$ (esto es, las variables aleatorias forman la cadena de Markov $X\rightarrow Y\rightarrow Z$, donde la flecha indica una relación de dependencia causal). Dado el caso, la función de masa de probabilidad puede ser escrita como :

$p(x,y,z)=p(x)p(y|x)p(z|y)$

Esto implica que $X\rightarrow Y\rightarrow Z$ es posible sí, y solo sí, $X$ y $Z$ son condicionalmente independientes dada $Y$.

Por la regla de la cadena, podemos expandir la información mutua como:

$I(X;Y,Z)=I(X;Z)+I(X;Y|Z)=I(X;Y)+I(X;Z|Y)$

Como $X$ y $Z$ son condicionalmente independientes dada $Y$, sabemos que $I(X;Z|Y)=0$, y puesto que $I(X;Y|Z)\geq 0$, concluimos que:

$I(X;Y)\geq I(X;Z)$

De modo similar, puede probarse que:

$I(Y;Z)\geq I(X;Z)$

Aplicación

El teorema establece que, por mero procesamiento de datos, no podemos aumentar la información original presente en estos. P. ej., si tenemos una imagen digital en la que se ha eliminado parcialmente un fragmento (quizás borrando un texto) o una señal musical sobre la que se ha aplicado un filtro paso banda (quizás eliminando un instrumento), esta información no podrá ser recuperada (salvo que se aporten nuevos datos).

Del teorema pueden extraerse múltiples corolarios relevantes aplicables a la teoría de la información:

• Limitación del procesamiento. Ningún proceso de transformación puede aumentar la información contenida en una serie de datos. Nótese que esto no implica que la serie de datos contenga información aún desconocida; sencillamente, advierte que el procesamiento no generará información no disponible. Este caso lo encontramos, p. ej., en las capturas de datos de los radiotelescopios, donde generalmente pueden encontrarse datos útiles enterrados en ingentes cantidades de ruido, solo accesibles tras arduas labores de cómputo. Pero adviértase: los datos siempre estuvieron ahí; el procesamiento solo los recupera, no los genera.
• Transmisión de datos. En la transmisión de datos a través de un canal ruidoso, la información recibida solo puede ser igual o inferior a la información transmitida: si los datos de la fuente $X$ se ponen a disposición a través de un canal $Y$ que, a su vez, se proyecta sobre un receptor $Z$, entonces el receptor $Z$ solo puede saber de la fuente $X$ tanto como se conserve en el canal $Y$ que, si es ruidoso, podría alterar el mensaje original. En este caso, como expresa explícitamente el teorema, $Z$ solo puede conocer de $X$ lo mismo, o menos, que haya conservado $Y$.
• Compresión de datos. Este teorema también es aplicable a procesos de compresión de datos. Cuando los datos se comprimen para reducir su tamaño, parte de la información puede ser descartada de manera irreversible, sobre todo como es lógico en técnicas de compresión con pérdida como por ejemplo el formato JPEG para imágenes o MP3 para audio (cf. codificación de fuente, señal de audio). En estos casos, se suele lograr una reducción importante en el tamaño del archivo, donde la información eliminada no se puede recuperar después en ningún caso. Esto subraya la necesidad de elegir de forma cuidadosa las técnicas de compresión en función de las necesidades de calidad y el propósito de los datos que se procesan.