Using algorithmic information theory and stochastic modeling to improve classification and evolutionary computation
Manuel Cebrián · Dialnet (Universidad de la Rioja) · 2007
Esta tesis presenta contribuciones teoricas y practicas de la Teoria de Informacion Algoritmica y del Modelado Estocastico (Algoritmico), La Teoria de Informacion Algoritmica es la teoria concerniente a la obtencion de una medida absoluta de la cantidad informacion contenida en un objeto. El Modelado Estocastico es una metodologia para la mejora del rendimiento de algoritmos mediante la introduccion de elementos aleatorios en su logica. Una de las mas interesantes aportaciones de la Teoria de Informacion Algoritmica es el desarrollo de una medida absoluta de similitud entre objetos. Esta medida solo puede ser estimada, al ser no computable por definicion. La estimacion tipica se basa en el uso de algoritmos de compresion de datos, siendo esta estimacion conocida como la distancia de compresion. Las dos aportaciones teoricas de esta tesis analizan la calidad de esta estimacion. La primera cuantifica la robustez de la estimacion cuando la informacion contenida en los objetos ha sido alterada por ruido externo, concluyendo que esta es considerablemente resistente al mismo. La segunda, estudia el impacto de la implementacion del algoritmo de compresion sobre la estimacion, obteniendose algunas recetas practicas para realizar dicha eleccion. Usamos variantes de la distancia de compresion para desarrollar dos aplicaciones para clasificacion y una para computacion evolutiva. La primera aplicacion considera el problema de la deteccion de similitudes entre documentos que han sido generados por una fuente comun predecesora, independientemente de si estos usan o no la misma codificacion: esto incluye la deteccion de traducciones de documentos y la reconstruccion de arboles filogeneticos a partir de material genetico. Hacemos uso de la ya demostrada utilidad de las distancias de similitud basadas en compresion en la deteccion de plagio (en el ambito educacional) para desarrollar nuestra segunda aplicacion: AC, un entorno