- author = "Manuel {Cebrian Ramos}",
- title = "Using Algorithmic Information Theory and Stochastic Modeling to Improve Classification and Evolutionary Computation",
- school = "Department of Computer Science, Universidad Autonoma de Madrid",
- year = "2007",
- type = "Sobresaliente Cum Laude",
- address = "Spain",
- month = "13 " # jul,
- keywords = "genetic algorithms, genetic programming, grammatical evolution",
-
URL = "
http://digitool-uam.greendata.es:1801/webclient/DeliveryManager?pid=3411.pdf",
-
URL = "
http://hdl.handle.net/10486/2301",
- size = "244 pages",
-
abstract = "This thesis presents theoretical and practical
contributions in Algorithmic Information Theory and
(Algorithmic) Stochastic Modelling. Algorithmic
Information Theory is the theory concerned with
obtaining an absolute measure of the information
contained in an object. Stochastic Modelling is a
methodology to improve an algorithm's performance by
means of the introduction of random elements in its
logic.
One of the most interesting advances of Algorithmic Information Theory is the development of an absolute measure of similarity between objects. This measure can only be estimated, as it is incomputable by definition. The typical estimation relies on the use of data compression algorithms, being this estimation known as the compression distance. The two theoretical contributions of this thesis analyse the quality of this estimation. The first quantifies the estimation robustness when the information contained in the objects is noise-altered, concluding that it is considerably resistant to noise. The second studies the impact of the compression algorithm implementation on the estimation, yielding some practical recipes for making this choice.
We use variants of the compression distance to develop two applications for classification and one for evolutionary computation. The first application addresses the problem of detecting similarities in objects which have been generated by a predecessor common source, independently of whether they use or not the same coding scheme: this includes detecting document translation and reconstructing phylogenetic threes from genetic material. We make use of the already proved usefulness of compression based similarity distances for educational plagiarism detection to develop our second application: AC, an integrated source code plagiarism detection environment. The third application makes use of this distance as a fitness function, which is used by evolutionary algorithms to automatically generate music in a given pre-defined style.
Another three new applications are derived using Stochastic Modeling, two for evolutionary computation and one for classification. Two of them are intimately related and make use of the presence of Heavy Tail probability distributions in the optimisation processes involved in the generation of fractals by an evolutionary algorithm, and in the training process of a multilayer perceptron. This discovery is used to improve the performance of both algorithms by means of restart strategies. The last application presented in this thesis is a successful story of the use of a special randomised heuristic in a simple genetic algorithm to yield a state-of-the-art evolutionary algorithm for solving Constraint Satisfaction Problems.",
-
abstract = "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 integrado de deteccion de plagio en codigo fuente. La tercera aplicacion hace uso de esta distancia como una funcion de fitness, que es usada por algoritmos evolutivos para generar de forma automatica musica con un estilo predefinido.
Otras tres nuevas aplicaciones derivan del uso de Modelado Estocastico, dos para computacion evolutiva y una para clasificacion. Dos de ellas estan intimamente relacionadas y hacen uso de la presencia de distribuciones de probabilidad de Cola Pesada en los procesos de optimizacion involucrados en la generacion de fractales mediante un algoritmo evolutivo, y en el proceso de entrenamiento de un perceptron multicapa. Este descubrimiento se usa para mejorar el rendimiento de ambos algoritmos mediante el uso de estrategias de recomienzo. La ultima aplicacion presentada en esta tesis es una historia exitosa del uso de una heuristica aleatoria especial en un algoritmo genetico simple, obteniendose un algoritmo que equivale al estado del arte para la resolucion de Problemas de Satisfaccion de Restricciones (CSPs).",
- notes = "In english. Supervised by Manuel Alfonseca Moreno / Alfonso Ortega de la Puente",
