Título: El Método de Tipos en Modelos Árbol

Marco de Trabajo: Doctorado

Área de desarrollo: Teoría de la Información

Autor: Alvaro Martín

Contacto: almartin@fing.edu.uy

Día: MIERCOLES

Hora: 16:30

Palabras Claves: Markov, compresión, simulación

Resumen:
trabajo conjunto con Gadiel Seroussi y Marcelo Weinberger
En el método de tipos [1], el conjunto de secuencias de un largo dado n sobre un alfabeto finito se parte en clases de equivalencia, tales que todas las secuencias de una clase son equiprobables bajo cualquier modelo de una familia fijada de antemano. Por ejemplo, en la familia de modelos sin memoria sobre un alfabeto binario {0, 1}, cada clase está formada por el conjunto de secuencias de largo n que tienen entre si la misma cantidad de ceros (y de unos). En la familia de modelos inducida por una máquina de estados finita (FSM), cada clase está formada por el conjunto de secuencias de largo n que tienen entre si la misma cantidad de ocurrencias de ceros y unos en todos los estados de la FSM. En [2] se recopilan diversas aplicaciones de este método por ejemplo en prueba de hipótesis, corrección de errores de comunicación, compresión de datos, y teoría de tasa-distorsión.
Por otra parte, los modelos árbol [3, 4], o cadenas de Markov de largo variable, han tenido amplia difusión en el área de teoría de la información. En particular en compresión de datos, varios de los codificadores que alcanzan las mejores tasas de compresión para diferentes aplicaciones (por ejemplo texto) están basados explícita o implícitamente en modelos árbol. El atractivo de estos modelos tiene dos aspectos.
1) La posibilidad de “juntar" estados de una cadena de Markov que comparten la misma distribución de probabilidad condicional permite en la práctica reducir considerablemente la dimensión del espacio de parámetros que describen el modelo. En el marco de la compresión de datos universal, por ejemplo, esta reducción de parámetros conlleva una disminución en el largo esperado de código.
2) Se conocen estructuras de datos y algoritmos que permiten implementar eficientemente aplicaciones basadas en estos modelos.
En esta presentación estudiamos propiedades del método de tipos aplicado a modelos árbol, usando fundamentalmente herramientas de teoría de grafos. Derivamos una fórmula exacta para calcular el tamaño de la clase de una secuencia con respecto a un modelo árbol arbitrario. Este resultado permite enumerar las secuencias de una clase, lo cual tiene aplicaciones tanto en compresión como en simulación universal. La fórmula obtenida generaliza la fórmula de Whittle [5] que vale para cadenas de Markov. Asimismo estudiamos también la cantidad de clases diferentes sobre secuencias de largo n inducidas por un modelo árbol fijo, resultado esencial por ejemplo para el estudio de algoritmos de compresión enumerativos. En este caso derivamos una fórmula asintótica ajustada a menos de una constante multiplicativa.
Referencias
[1] I. Csiszár and J. Köorner, Information Theory: Coding Theorems for Discrete Memoryless Systems. New York: Academic, 1981.
[2] I. Csiszár, “The method of types," IEEE Trans. Inf. Theory, vol. 44, no. 6, pp. 2505-2523, Oct. 1998.
[3] J. Rissanen, “Complexity of strings in the class of Markov sources," IEEE Trans. Inf. Theory, vol. 32, pp. 526-532, Jul. 1986.
[4] M. J. Weinberger, J. Rissanen, and M. Feder, “A universal finite memory source," IEEE Trans. Inf. Theory, vol. 41, pp. 643-652, May 1995.
[5] P. Whittle, “Some distribution and moment formulae for the Markov chain," J. Roy. Statist. Soc. Ser. B, vol. 17, no. 3, pp. 235-242, 1955.