On the learnibility of Mildly Context-Sensitive languages using positive data and correction queries

摘要

APRENDIBILIDAD DE LENGUAJES SUAVEMENTE DEPENDIENTES DEL CONTEXTO UTILIZANDO DATOS POSITIVOS Y PREGUNTAS DE CORRECCION Con esta tesis doctoral aproximamos la teoria de la inferencia gramatical y los estudios de adquisicion del lenguaje, en pos de un objetivo final: ahondar en la comprension del modo como los ninos adquieren su primera lengua mediante la explotacion de la teoria inferencial de gramaticas formales. Nuestras tres principales aportaciones son: 1. Introduccion de una nueva clase de lenguajes llamada Simple p-dimensional external contextual (SEC). A pesar de que las investigaciones en inferencia gramatical se han centrado en lenguajes regulares o independientes del contexto, en nuestra tesis proponemos centrar esos estudios en clases de lenguajes mas relevantes desde un punto de vista linguistico (familias de lenguajes que ocupan una posicion ortogonal en la jerarquia de Chomsky y que son suavemente dependientes del contexto, por ejemplo, SEC). 2. Presentacion de un nuevo paradigma de aprendizaje basado en preguntas de correccion. Uno de los principales resultados positivos dentro de la teoria del aprendizaje formal es el hecho de que los automatas finitos deterministas (DFA) se pueden aprender de manera eficiente utilizando preguntas de pertinencia y preguntas de equivalencia. Teniendo en cuenta que en el aprendizaje de primeras lenguas la correccion de errores puede jugar un papel relevante, en nuestra tesis doctoral hemos introducido un nuevo modelo de aprendizaje que reemplaza las preguntas de pertinencia por preguntas de correccion. 3. Presentacion de resultados basados en las dos previas aportaciones. En primer lugar, demostramos que los SEC se pueden aprender a partir de datos positivos. En segundo lugar, demostramos que los DFA se pueden aprender a partir de correcciones y que el numero de preguntas se reduce considerablemente. Los resultados obtenidos con esta tesis doctoral suponen una aportacion importante para los estudios en inferencia gramatical (hasta el momento las investigaciones en este ambito se habian centrado principalmente en los aspectos matematicos de los modelos). Ademas, estos resultados se podrian extender a diversos campos de aplicacion que gozan de plena actualidad, tales como el aprendizaje automatico, la robotica, el procesamiento del lenguaje natural y la bioinformatica. ON THE LEARNABILITY OF MILDLY CONTEXT-SENSITIVE LANGUAGES USING POSITIVE DATA AND CORRECTION QUERIES With this dissertation, we bring together the Theory of the Grammatical Inference and Studies of language acquisition, in pursuit of our final goal: to go deeper in the understanding of the process of language acquisition by using the theory of inference of formal grammars. Our main three contributions are: 1. Introduction of a new class of languages called Simple p-dimensional external contextual (SEC). Despite the fact that the field of Grammatical Inference has focused its research on learning regular or context-free languages, we propose in our dissertation to focus these studies in classes of languages more relevant from a linguistic point of view (families of languages that occupy an orthogonal position in the Chomsky Hierarchy and are Mildly Context-Sensitive, for example SEC). 2. Presentation of a new learning paradigm based on correction queries. One of the main results in the theory of formal learning is that deterministic finite automata (DFA) are efficiently learnable from membership query and equivalence query. Taken into account that in first language acquisition the correction of errors can play an important role, we have introduced in our dissertation a novel learning model by replacing membership queries with correction queries. 3. Presentation of results based on the two previous contributions. First, we prove that SEC is learnable from only positive data. Second, we prove that it is possible to learn DFA from corrections and that the number of queries is reduced considerably. The results obtained with