Using algorithmic information theory and stochastic modeling to improve classification and evolutionary computation

Resumen

Esta tesis presenta contribuciones teóricas y prácticas de la Teoría de Información Algorítmica y del Modelado Estocástico (Algorítmico), La Teoría de Información Algorítmica es la teoría concerniente a la obtención de una medida absoluta de la cantidad información contenida en un objeto. El Modelado Estocástico es una metodología para la mejora del rendimiento de algoritmos mediante la introducción de elementos aleatorios en su lógica. Una de las más interesantes aportaciones de la Teoría de Información Algorítmica es el desarrollo de una medida absoluta de similitud entre objetos. Esta medida sólo puede ser estimada, al ser no computable por definición. La estimación típica se basa en el uso de algoritmos de compresión de datos, siendo esta estimación conocida como la distancia de compresión. Las dos aportaciones teóricas de esta tesis analizan la calidad de esta estimación. La primera cuantifica la robustez de la estimación cuando la información contenida en los objetos ha sido alterada por ruido externo, concluyendo que ésta es considerablemente resistente al mismo. La segunda, estudia el impacto de la implementación del algoritmo de compresión sobre la estimación, obteniéndose algunas recetas prácticas para realizar dicha elección. Usamos variantes de la distancia de compresión para desarrollar dos aplicaciones para clasificación y una para computación evolutiva. La primera aplicación considera el problema de la detección de similitudes entre documentos que han sido generados por una fuente común predecesora, independientemente de si estos usan o no la misma codificación: esto incluye la detección de traducciones de documentos y la reconstrucción de árboles filogenéticos a partir de material genético. Hacemos uso de la ya demostrada utilidad de las distancias de similitud basadas en compresión en la detección de plagio (en el ámbito educacional) para desarrollar nuestra segunda aplicación: AC, un entorno