teoría de la distorsión de la tasa

La teoría de tasa-distorsión es una rama importante de la teoría de la información que proporciona los fundamentos teóricos para la compresión de datos con pérdidas ; aborda el problema de determinar el número mínimo de bits por símbolo, medido por la tasa R , que debe comunicarse a través de un canal, de modo que la fuente (señal de entrada) pueda reconstruirse aproximadamente en el receptor (señal de salida ) sin exceder una distorsión esperada D.

La teoría de la relación tasa-distorsión proporciona una expresión analítica para determinar cuánta compresión se puede lograr utilizando métodos de compresión con pérdidas. Muchas de las técnicas de compresión de audio, voz, imagen y video existentes incluyen transformaciones, cuantificación y procedimientos de asignación de tasa de bits que aprovechan la forma general de las funciones de tasa-distorsión.

La teoría de la tasa-distorsión fue creada por Claude Shannon en su obra fundamental sobre la teoría de la información.

En la teoría de tasa-distorsión, la tasa se entiende generalmente como el número de bits por muestra de datos que se almacenará o transmitirá. La noción de distorsión es objeto de debate continuo. ^{[ 1 ]} En el caso más simple (que es el que se utiliza en la mayoría de los casos), la distorsión se define como el valor esperado del cuadrado de la diferencia entre la señal de entrada y la de salida (es decir, el error cuadrático medio ). Sin embargo, dado que sabemos que la mayoría de las técnicas de compresión con pérdida operan sobre datos que serán percibidos por consumidores humanos (escuchar música , ver imágenes y vídeos), la medida de distorsión debería modelarse preferiblemente en función de la percepción humana y quizás de la estética : al igual que el uso de la probabilidad en la compresión sin pérdida , las medidas de distorsión pueden identificarse en última instancia con funciones de pérdida como las utilizadas en la estimación bayesiana y la teoría de la decisión . En la compresión de audio, los modelos perceptuales (y, por lo tanto, las medidas de distorsión perceptual) están relativamente bien desarrollados y se utilizan de forma rutinaria en técnicas de compresión como MP3 o Vorbis , pero a menudo no son fáciles de incluir en la teoría de tasa-distorsión. En la compresión de imágenes y vídeo, los modelos de percepción humana están menos desarrollados y su inclusión se limita principalmente a la matriz de ponderación ( cuantización , normalización ) de JPEG y MPEG .

Las funciones de distorsión miden el costo de representar un símbolo.${\displaystyle x}$mediante un símbolo aproximado${\displaystyle {\hat {x}}}$Las funciones de distorsión típicas son la distorsión de Hamming y la distorsión de error cuadrático.

Las funciones que relacionan la tasa y la distorsión se encuentran como la solución del siguiente problema de minimización:

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{ sujeto a }}D_{Q}\leq D^{*}.}$

Aquí${\displaystyle Q_{Y\mid X}(y\mid x)}$, a veces llamado canal de prueba, es la función de densidad de probabilidad condicional (PDF) de la salida del canal de comunicación (señal comprimida).${\displaystyle Y}$para una entrada dada (señal original)${\displaystyle X}$, y${\displaystyle I_{Q}(Y;X)}$es la información mutua entre${\displaystyle Y}$y${\displaystyle X}$definido como

${\displaystyle I(Y;X)=H(Y)-H(Y\mid X)\,}$

dónde${\displaystyle H(Y)}$y${\displaystyle H(Y\mid X)}$son, respectivamente, la entropía de la señal de salida Y y la entropía condicional de la señal de salida dada la señal de entrada:

${\displaystyle H(Y)=-\int _{-\infty }^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y))\,dy}$

${\displaystyle H(Y\mid X)=-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)\log _{2}(Q_{Y\mid X}(y\mid x))\,dx\,dy.}$

El problema también puede formularse como una función de tasa de distorsión, donde encontramos el ínfimo sobre las distorsiones alcanzables para una restricción de tasa dada. La expresión relevante es:

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y]]{\text{ sujeto a }}I_{Q}(Y;X)\leq R.}$

Ambas formulaciones dan lugar a funciones que son inversas entre sí.

La información mutua puede entenderse como una medida de la incertidumbre 'a priori' que el receptor tiene sobre la señal del emisor ( H ( Y )), disminuida por la incertidumbre que queda después de recibir información sobre la señal del emisor (${\displaystyle H(Y\mid X)}$). Por supuesto, la disminución de la incertidumbre se debe a la cantidad de información comunicada, que es${\displaystyle I\left(Y;X\right)}$.

Por ejemplo, en caso de que no haya comunicación alguna, entonces${\displaystyle H(Y\mid X)=H(Y)}$y${\displaystyle I(Y;X)=0}$Alternativamente, si el canal de comunicación es perfecto y la señal recibida${\displaystyle Y}$es idéntico a la señal${\displaystyle X}$en el remitente, entonces${\displaystyle H(Y\mid X)=0}$y${\displaystyle I(Y;X)=H(X)=H(Y)}$.

En la definición de la función tasa-distorsión,${\displaystyle D_{Q}}$y${\displaystyle D^{*}}$son la distorsión entre${\displaystyle X}$y${\displaystyle Y}$para un dado${\displaystyle Q_{Y\mid X}(y\mid x)}$y la distorsión máxima prescrita, respectivamente. Cuando utilizamos el error cuadrático medio como medida de distorsión, tenemos (para señales de amplitud continua ):

${\displaystyle D_{Q}=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }P_{X,Y}(x,y)(xy)^{2}\,dx\,dy=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)(xy)^{2}\,dx\,dy.}$

Como muestran las ecuaciones anteriores, el cálculo de una función de tasa-distorsión requiere la descripción estocástica de la entrada.${\displaystyle X}$en términos del PDF${\displaystyle P_{X}(x)}$y luego tiene como objetivo encontrar la función de densidad de probabilidad condicional.${\displaystyle Q_{Y\mid X}(y\mid x)}$que minimizan la tasa para una distorsión dada${\displaystyle D^{*}}$Estas definiciones pueden formularse desde una perspectiva de teoría de la medida para tener en cuenta también las variables aleatorias discretas y mixtas.

A menudo resulta difícil obtener una solución analítica a este problema de minimización, salvo en algunos casos, para los que a continuación presentamos dos de los ejemplos más conocidos. Se sabe que la función de tasa-distorsión de cualquier fuente obedece a varias propiedades fundamentales, siendo las más importantes que se trata de una función convexa (U) continua y monótonamente decreciente , por lo que la forma de la función en los ejemplos es típica (incluso las funciones de tasa-distorsión medidas en la vida real tienden a tener formas muy similares).

Aunque las soluciones analíticas a este problema son escasas, existen límites superiores e inferiores para estas funciones, incluido el famoso límite inferior de Shannon (SLB), que en el caso de fuentes de error cuadrático y sin memoria, establece que para fuentes arbitrarias con entropía diferencial finita,

${\displaystyle R(D)\geq h(X)-h(D)\,}$

donde h ( D ) es la entropía diferencial de una variable aleatoria gaussiana con varianza D. Este límite inferior es extensible a fuentes con memoria y otras medidas de distorsión. Una característica importante del límite inferior de Shannon es que es asintóticamente ajustado en el régimen de baja distorsión para una amplia clase de fuentes y, en algunas ocasiones, coincide con la función de tasa-distorsión. Los límites inferiores de Shannon generalmente se pueden encontrar si la distorsión entre dos números cualesquiera se puede expresar como una función de la diferencia entre el valor de estos dos números.

El algoritmo de Blahut-Arimoto , coinventado por Richard Blahut , es una elegante técnica iterativa para obtener numéricamente funciones de tasa-distorsión de fuentes de alfabeto de entrada/salida finitas arbitrarias, y se ha trabajado mucho para extenderlo a instancias de problemas más generales.

El cálculo de la función de distorsión de la tasa requiere conocer la distribución subyacente, información que a menudo no está disponible en las aplicaciones actuales de ciencia de datos y aprendizaje automático. Sin embargo, este desafío puede abordarse mediante estimadores de la función de distorsión de la tasa basados ​​en aprendizaje profundo. ^{[ 2 ]} Estos estimadores se denominan comúnmente «estimadores neuronales» e implican la optimización de una forma variacional parametrizada de la función objetivo de distorsión de la tasa.

Cuando se trabaja con fuentes estacionarias con memoria, es necesario modificar la definición de la función de distorsión de la tasa y debe entenderse como un límite tomado sobre secuencias de longitud creciente.

${\displaystyle R(D)=\lim _{n\rightarrow \infty }R_{n}(D)}$

dónde

${\displaystyle R_{n}(D)={\frac {1}{n}}\inf _{Q_{Y^{n}\mid X^{n}}\in {\mathcal {Q}}}I(Y^{n},X^{n})}$

y

${\displaystyle {\mathcal {Q}}=\{Q_{Y^{n}\mid X^{n}}(Y^{n}\mid X^{n},X_{0}):E[d(X^{n},Y^{n})]\leq D\}}$

donde los superíndices denotan una secuencia completa hasta ese momento y el subíndice 0 indica el estado inicial.

Supongamos que queremos transmitir información sobre una fuente al usuario con una distorsión que no exceda D. La teoría de tasa-distorsión nos dice que al menos${\displaystyle R(D)}$bits/símbolo de información de la fuente deben llegar al usuario. También sabemos por el teorema de codificación de canal de Shannon que si la entropía de la fuente es H bits/símbolo y la capacidad del canal es C (donde${\displaystyle C<H}$), entonces${\displaystyle H-C}$Se perderán bits/símbolos al transmitir esta información a través del canal dado. Para que el usuario tenga alguna esperanza de reconstruir con una distorsión máxima D , debemos imponer el requisito de que la información perdida en la transmisión no exceda la pérdida máxima tolerable de${\displaystyle H-R(D)}$bits/símbolo. Esto significa que la capacidad del canal debe ser al menos tan grande como${\displaystyle R(D)}$. ^{[ 5 ]}

• Algoritmo de Blahut-Arimoto : una clase de algoritmos en teoría de la información. 
• Compresión de datos : codificación compacta de datos digitales. 
• Decorrelación : proceso de reducción de la correlación dentro de una o más señales. 
• Optimización de la relación tasa-distorsión
• Empaquetamiento de esferas – Estructura geométrica 
• Ruido blanco : un tipo de señal en el procesamiento de señales. 

• Marzen, Sarah; DeDeo, Simon. "PyRated: un paquete de Python para la teoría de la distorsión de la tasa" . PyRated es un paquete de Python muy simple para realizar el cálculo más básico en la teoría de la distorsión de la tasa: la determinación del "libro de códigos" y la tasa de transmisión R , dados una función de utilidad (matriz de distorsión) y un multiplicador de Lagrange beta .
• Herramienta de aprendizaje de compresión de imágenes y vídeo VcDemo