Language learning with correction queries

Abstract

In the field of grammatical inference, the goal of any learning algorithm is to identify a target concept from a given class by having access to a specific type of information. The main learning settings are Gold's model of learning in the limit and Angluin's query learning. This dissertation is primarily concerned with the second approach.<br/>We thoroughly investigate a recently introduced, linguistic motivated, type of query called Correction Query (CQ). We consider three possible definitions, and for each of them we give necessary and sufficient conditions for a language class to be learnable with these types of queries. Furthermore, we compare the model of learning with CQs with other well-known Gold-style and query learning models when no efficiency constraints are imposed. Results are also obtained for the restricted version of the model of learning with CQs in polynomial time. <br/>Additionally, we discuss the learnability of deterministic finite automata (DFAs) with correction and equivalence queries. We design several learning algorithms and we present a comparison between our algorithms and the standard algorithm for learning DFAs with membership and equivalence queries. These results are furthermore extended from string languages to tree languages.

Dentro del ámbito de la inferencia gramatical, el objetivo de cualquier algoritmo de aprendizaje consiste en identificar un concepto de una clase dada, teniendo acceso a un tipo específico de información. Los dos modelos de aprendizaje principales son: el modelo de aprendizaje en el límite propuesto por Gold y el modelo de aprendizaje a partir de preguntas de Angluin. Esta tesis se centra fundamentalmente en el segundo tipo de aprendizaje. En esta tesis doctoral investigamos a fondo un tipo de preguntas introducidas recientemente, por motivos lingüísticos, denominada PREGUNTA DE CORRECCIÓN. Nosotros consideramos tres posibles definiciones, y para cada uno de ellos presentamos condiciones necesarias y suficientes para que una clase de lenguajes sea identificable con estos tipos de preguntas. Además, comparamos estos tres modelos de aprendizaje a partir de preguntas de corrección con otros modelos de aprendizaje, en el caso general (sin ninguna restricción de tiempo) y también imponiendo que los algoritmos sean polinómicos.Además, investigamos el aprendizaje de autómata finitos deterministas (AFD) con preguntas de corrección y equivalencia. Diseñamos varios algoritmos de aprendizaje y presentamos una comparación entre nuestros algoritmos y el algoritmo estándar de aprendizaje a partir de preguntas de pertenencia y equivalencia. Estos resultados son, además, extendidos para los lenguajes de árboles.