Estimación eficiente de orden en modelos Markovianos

Abstract

En este proyecto construimos un estimador eficiente de orden de procesos de Markov de máxima verosimilitud penalizada. Es frecuente el uso de árboles de sufijos en la implementación de este tipo de estimadores. Los mismos se ven limitados por el consumo de memoria cuando crece el tamaño de la entrada. Investigaciones recientes obtuvieron una cota para el orden estimado, reduciendo las opciones posibles que debe tomar en cuenta el estimador. Haciendo uso de esta cota, propusimos usar la estructura de árboles de sufijos truncados en la implementación, incorporando la ganancia de espacio que representan frente a los árboles de sufijos. Utilizamos para su construcción una adaptación del algoritmo de Ukkonen y la representación de Kurtz. Usualmente los árboles de sufijos truncados se etiquetan mediante punteros a la cadena original. En este trabajo desarrollamos un mecanismo de etiquetado de aristas que reemplaza la cadena original por una cadena, más corta, formada a partir de ella. Los ahorros de memoria que aporta son equivalentes a la diferencia de tamaño entre el árbol de sufijos y el árbol de sufijos truncado. Es posible construirla junto con el árbol sin comprometer el tiempo de procesamiento. Evaluamos el consumo de memoria de este mecanismo sobre un conjunto de imágenes y obtuvimos diferencias significativas en comparación con el etiquetado clásico.