Algoritmo de Blahut-Arimoto

Clases de algoritmos en la teoría de la información

El término algoritmo Blahut-Arimoto se utiliza a menudo para referirse a una clase de algoritmos para calcular numéricamente la capacidad teórica de la información de un canal, la función de tasa de distorsión de una fuente o una codificación de fuente (es decir, compresión para eliminar la redundancia). Son algoritmos iterativos que finalmente convergen a uno de los máximos del problema de optimización asociado con estos conceptos teóricos de la información.

Historia y aplicación

Para el caso de la capacidad del canal , el algoritmo fue inventado independientemente por Suguru Arimoto ^[1] y Richard Blahut ^[2] . Además, el tratamiento de Blahut proporciona algoritmos para calcular la distorsión de velocidad y la capacidad generalizada con restricciones de entrada (es decir, la función de costo de capacidad, análoga a la distorsión de velocidad). Estos algoritmos son más aplicables al caso de fuentes de alfabeto finito arbitrario. Se ha realizado mucho trabajo para extenderlo a instancias de problemas más generales. ^{[3] [4]} Recientemente, se propuso una versión del algoritmo que da cuenta de salidas continuas y multivariadas con aplicaciones en señalización celular. ^[5] También existe una versión del algoritmo Blahut-Arimoto para información dirigida . ^[6]

Algoritmo para la capacidad del canal

Un canal discreto sin memoria (DMC) se puede especificar utilizando dos variables aleatorias con alfabeto , y una ley de canal como una distribución de probabilidad condicional . La capacidad del canal , definida como , indica la máxima eficiencia con la que un canal puede comunicarse, en la unidad de bit por uso. ^[7] Ahora bien, si denotamos la cardinalidad , entonces es una matriz, que denotamos la entrada de fila, columna por . Para el caso de la capacidad del canal , el algoritmo fue inventado independientemente por Suguru Arimoto ^[8] y Richard Blahut . ^[9] Ambos encontraron la siguiente expresión para la capacidad de un DMC con ley de canal: ${\displaystyle X,Y}$ ${\displaystyle {\mathcal {X}},{\mathcal {Y}}}$ ${\displaystyle p(y|x)}$ ${\displaystyle C:=\sup _{p\sim X}I(X;Y)}$ ${\displaystyle |{\mathcal {X}}|=n,|{\mathcal {Y}}|=m}$ ${\displaystyle p_{Y|X}}$ ${\displaystyle n\times m}$ ${\displaystyle i^{th}}$ ${\displaystyle j^{th}}$ ${\displaystyle w_{ij}}$

${\displaystyle C=\max _{\mathbf {p} }\max _{Q}\sum _{i=1}^{n}\sum _{j=1}^{m}p_{i}w_{ij}\log \left({\dfrac {Q_{ji}}{p_{i}}}\right)}$

donde y se maximizan según los siguientes requisitos: ${\displaystyle \mathbf {p} }$ ${\displaystyle Q}$

• ${\displaystyle \mathbf {p} }$es una distribución de probabilidad en , Es decir, si escribimos como ${\displaystyle X}$ ${\displaystyle \mathbf {p} }$ ${\displaystyle (p_{1},p_{2}...,p_{n}),\sum _{i=1}^{n}p_{i}=1}$
• ${\displaystyle Q=(q_{ji})}$es una matriz que se comporta como una matriz de transición de a con respecto a la ley del canal. Es decir, para todo : ${\displaystyle m\times n}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle 1\leq i\leq n,1\leq j\leq m}$
  • ${\displaystyle q_{ji}\geq 0,q_{ji}=0\Leftrightarrow w_{ij}=0}$
  • Cada fila suma 1, es decir . ${\displaystyle \sum _{i=1}^{n}q_{ji}=1}$

Luego, al elegir una distribución de probabilidad aleatoria en , podemos generar una secuencia iterativamente de la siguiente manera: ${\displaystyle \mathbf {p} ^{0}:=(p_{1}^{0},p_{2}^{0},...p_{n}^{0})}$ ${\displaystyle X}$ ${\displaystyle (\mathbf {p} ^{0},Q^{0},\mathbf {p} ^{1},Q^{1}...)}$

${\displaystyle (q_{ji}^{t}):={\dfrac {p_{i}^{t}w_{ij}}{\sum _{k=1}^{n}p_{k}^{t}w_{kj}}}}$

${\displaystyle p_{k}^{t+1}:={\dfrac {\prod _{j=1}^{m}(q_{jk}^{t})^{w_{kj}}}{\sum _{i=1}^{n}\prod _{j=1}^{m}(q_{ji}^{t})^{w_{ij}}}}}$

Para . ${\displaystyle t=0,1,2...}$

Luego, utilizando la teoría de optimización, específicamente el descenso de coordenadas , Yeung ^[10] demostró que la secuencia efectivamente converge al máximo requerido. Es decir,

${\displaystyle \lim _{t\to \infty }\sum _{i=1}^{n}\sum _{j=1}^{m}p_{i}^{t}w_{ij}\log \left({\dfrac {Q_{ji}^{t}}{p_{i}^{t}}}\right)=C}$.

Así, dada una ley de canal , la capacidad se puede estimar numéricamente hasta una precisión arbitraria. ${\displaystyle p(y|x)}$

Algoritmo para la distorsión de la velocidad

Supongamos que tenemos una fuente con probabilidad de cualquier símbolo dado. Deseamos encontrar una codificación que genere una señal comprimida a partir de la señal original mientras minimiza la distorsión esperada , donde la expectativa se toma sobre la probabilidad conjunta de y . Podemos encontrar una codificación que minimice la función de tasa-distorsión localmente repitiendo la siguiente iteración hasta la convergencia: ${\displaystyle X}$ ${\displaystyle p(x)}$ ${\displaystyle p({\hat {x}}|x)}$ ${\displaystyle {\hat {X}}}$ ${\displaystyle \langle d(x,{\hat {x}})\rangle }$ ${\displaystyle X}$ ${\displaystyle {\hat {X}}}$

${\displaystyle p_{t+1}({\hat {x}})=\sum _{x}p(x)p_{t}({\hat {x}}|x)}$

${\displaystyle p_{t+1}({\hat {x}}|x)={\frac {p_{t}({\hat {x}})\exp(-\beta d(x,{\hat {x}}))}{\sum _{\hat {x}}p_{t}({\hat {x}})\exp(-\beta d(x,{\hat {x}}))}}}$

donde es un parámetro relacionado con la pendiente de la curva de tasa-distorsión que buscamos y, por lo tanto, está relacionado con cuánto favorecemos la compresión frente a la distorsión (más alto significa menos compresión). ${\displaystyle \beta }$ ${\displaystyle \beta }$

Referencias

1. Arimoto, Suguru (1972), "Un algoritmo para calcular la capacidad de canales discretos arbitrarios sin memoria", IEEE Transactions on Information Theory , 18 (1): 14–20, doi :10.1109/TIT.1972.1054753, S2CID  8408706.
2. Blahut, Richard (1972), "Cálculo de la capacidad del canal y funciones de tasa-distorsión", IEEE Transactions on Information Theory , 18 (4): 460–473, CiteSeerX 10.1.1.133.7174 , doi :10.1109/TIT.1972.1054855 .
3. Vontobel, Pascal O. (2003). "Un algoritmo generalizado de Blahut-Arimoto". Actas del Simposio Internacional IEEE sobre Teoría de la Información, 2003. p. 53. doi :10.1109/ISIT.2003.1228067. ISBN 0-7803-7728-1.
4. Iddo Naiss; Haim Permuter (2010). "Extensión del algoritmo Blahut-Arimoto para maximizar la información dirigida". arXiv : 1012.5071v2 [cs.IT].
5. Tomasz Jetka; Karol Nienaltowski; Tomasz Winarski; Slawomir Blonski; Michal Komorowski (2019), "Análisis teórico de la información de respuestas de señalización unicelular multivariadas", PLOS Computational Biology , 15 (7): e1007132, arXiv : 1808.05581 , Bibcode :2019PLSCB..15E7132J, doi : 10.1371/journal.pcbi.1007132 , PMC 6655862 , PMID  31299056 
6. Naiss, Iddo; Permuter, Haim H. (enero de 2013). "Extensión del algoritmo Blahut-Arimoto para maximizar la información dirigida". IEEE Transactions on Information Theory . 59 (1): 204–222. arXiv : 1012.5071 . doi :10.1109/TIT.2012.2214202. S2CID  3115749.
7. Portada, TM (2006). Elementos de la teoría de la información. Joy A. Thomas (2.ª ed.). Hoboken, NJ: Wiley-Interscience. ISBN 0-471-24195-4.OCLC 59879802  .
8. Arimoto, Suguru (1972), "Un algoritmo para calcular la capacidad de canales discretos arbitrarios sin memoria", IEEE Transactions on Information Theory , 18 (1): 14–20, doi :10.1109/TIT.1972.1054753, S2CID  8408706.
9. Blahut, Richard (1972), "Cálculo de la capacidad del canal y funciones de tasa-distorsión", IEEE Transactions on Information Theory , 18 (4): 460–473, CiteSeerX 10.1.1.133.7174 , doi :10.1109/TIT.1972.1054855 .
10. Yeung, Raymond W. (2008). Teoría de la información y codificación de redes. Nueva York: Springer. ISBN 978-0-387-79234-7.OCLC 288469056  .