Using Algorithmic Information Theory and Stochastic Modeling to Improve Classification and Evolutionary Computation

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

@PhdThesis{Cebrian_Ramos:thesis,
  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",
}

Genetic Programming entries for Manuel Cebrian

Citations