La inducción gramatical (o inferencia gramatical ) [1] es el proceso en el aprendizaje automático de aprender una gramática formal (generalmente como una colección de reglas de reescritura o producciones o, alternativamente, como una máquina de estados finitos o un autómata de algún tipo) a partir de un conjunto de observaciones, construyendo así un modelo que da cuenta de las características de los objetos observados. En términos más generales, la inferencia gramatical es esa rama del aprendizaje automático donde el espacio de instancias consiste en objetos combinatorios discretos como cadenas, árboles y gráficos.
La inferencia gramatical a menudo se ha centrado en el problema del aprendizaje de máquinas de estados finitos de varios tipos (véase el artículo Inducción de lenguajes regulares para obtener detalles sobre estos enfoques), ya que existen algoritmos eficientes para este problema desde la década de 1980.
Desde principios de siglo, estos enfoques se han extendido al problema de la inferencia de gramáticas libres de contexto y formalismos más ricos, como las gramáticas libres de contexto múltiples y las gramáticas libres de contexto múltiples paralelas. Otras clases de gramáticas para las que se ha estudiado la inferencia gramatical son las gramáticas categoriales combinatorias , [2] las gramáticas libres de contexto estocásticas , [3] las gramáticas contextuales y los lenguajes de patrones.
La forma más simple de aprendizaje es aquella en la que el algoritmo de aprendizaje simplemente recibe un conjunto de ejemplos extraídos del lenguaje en cuestión: el objetivo es aprender el lenguaje a partir de ejemplos del mismo (y, raramente, a partir de contraejemplos, es decir, ejemplos que no pertenecen al lenguaje). Sin embargo, se han estudiado otros modelos de aprendizaje. Una alternativa que se estudia con frecuencia es el caso en el que el aprendiz puede hacer consultas de pertenencia como en el modelo de aprendizaje de consulta exacta o el modelo de profesor mínimamente adecuado introducido por Angluin. [4]
Existe una amplia variedad de métodos para la inferencia gramatical. Dos de las fuentes clásicas son Fu (1977) y Fu (1982). Duda, Hart y Stork (2001) también dedican una breve sección al problema y citan varias referencias. El método básico de ensayo y error que presentan se analiza a continuación. Para enfoques para inferir subclases de lenguajes regulares en particular, véase Inducción de lenguajes regulares . Un libro de texto más reciente es de la Higuera (2010), [1] que cubre la teoría de la inferencia gramatical de lenguajes regulares y autómatas de estados finitos. D'Ulizia, Ferri y Grifoni [5] proporcionan un estudio que explora los métodos de inferencia gramatical para lenguajes naturales.
Existen varios métodos para la inducción de gramáticas probabilísticas libres de contexto . [6] [7] [ se necesita más explicación ]
El método propuesto en la Sección 8.7 de Duda, Hart & Stork (2001) sugiere adivinar sucesivamente reglas gramaticales (producciones) y probarlas contra observaciones positivas y negativas. El conjunto de reglas se expande de modo que sea posible generar cada ejemplo positivo, pero si un conjunto de reglas dado también genera un ejemplo negativo, debe descartarse. Este enfoque particular puede caracterizarse como "prueba de hipótesis" y tiene cierta similitud con el algoritmo de espacio de versiones de Mitchel . El texto de Duda, Hart & Stork (2001) proporciona un ejemplo simple que ilustra bien el proceso, pero la viabilidad de un enfoque de prueba y error no guiado de este tipo para problemas más sustanciales es dudosa.
La inducción gramatical mediante algoritmos evolutivos es el proceso de evolución de una representación de la gramática de un idioma de destino a través de algún proceso evolutivo. Las gramáticas formales se pueden representar fácilmente como estructuras de árbol de reglas de producción que se pueden someter a operadores evolutivos. Los algoritmos de este tipo se derivan del paradigma de programación genética iniciado por John Koza . [ cita requerida ] Otros trabajos tempranos sobre lenguajes formales simples utilizaron la representación de cadenas binarias de algoritmos genéticos, pero la estructura inherentemente jerárquica de las gramáticas expresadas en el lenguaje EBNF hizo que los árboles fueran un enfoque más flexible.
Koza representó los programas Lisp como árboles. Pudo encontrar análogos a los operadores genéticos dentro del conjunto estándar de operadores de árboles. Por ejemplo, intercambiar subárboles es equivalente al proceso correspondiente de cruce genético, donde las subcadenas de un código genético se trasplantan a un individuo de la siguiente generación. La aptitud se mide puntuando el resultado de las funciones del código Lisp. Análogos similares entre la representación de Lisp estructurada en árboles y la representación de gramáticas como árboles hicieron posible la aplicación de técnicas de programación genética para la inducción gramatical.
En el caso de la inducción gramatical, el trasplante de subárboles corresponde al intercambio de reglas de producción que permiten el análisis de frases de algún idioma. El operador de aptitud para la gramática se basa en alguna medida de qué tan bien se desempeñó al analizar un grupo de oraciones del idioma de destino. En una representación de árbol de una gramática, un símbolo terminal de una regla de producción corresponde a un nodo hoja del árbol. Sus nodos padre corresponden a un símbolo no terminal (por ejemplo, una frase nominal o una frase verbal ) en el conjunto de reglas. En última instancia, el nodo raíz podría corresponder a una oración no terminal.
Al igual que todos los algoritmos voraces , los algoritmos de inferencia de gramática voraz toman, de manera iterativa, decisiones que parecen ser las mejores en esa etapa. Las decisiones tomadas generalmente tratan sobre cuestiones como la creación de nuevas reglas, la eliminación de reglas existentes, la elección de una regla que se aplicará o la fusión de algunas reglas existentes. Debido a que existen varias formas de definir "la etapa" y "lo mejor", también existen varios algoritmos de inferencia de gramática voraz.
Estos algoritmos de generación de gramática libre de contexto toman la decisión después de cada símbolo leído:
Estos algoritmos generadores de gramática libre de contexto primero leen toda la secuencia de símbolos dada y luego comienzan a tomar decisiones:
Un enfoque más reciente se basa en el aprendizaje distributivo. Los algoritmos que utilizan estos enfoques se han aplicado al aprendizaje de gramáticas independientes del contexto y de lenguajes ligeramente sensibles al contexto , y se ha demostrado que son correctos y eficientes para grandes subclases de estas gramáticas. [8]
Angluin define un patrón como "una cadena de símbolos constantes de Σ y símbolos variables de un conjunto disjunto". El lenguaje de un patrón de este tipo es el conjunto de todas sus instancias básicas no vacías, es decir, todas las cadenas resultantes del reemplazo consistente de sus símbolos variables por cadenas no vacías de símbolos constantes. [nota 1] Un patrón se denomina descriptivo para un conjunto de entrada finito de cadenas si su lenguaje es mínimo (con respecto a la inclusión de conjuntos) entre todos los lenguajes de patrones que subsumen el conjunto de entrada.
Angluin ofrece un algoritmo polinomial para calcular, para un conjunto de cadenas de entrada dado, todos los patrones descriptivos en una variable x . [nota 2] Para ello, construye un autómata que representa todos los patrones posiblemente relevantes; utilizando argumentos sofisticados sobre longitudes de palabras, que se basan en que x es la única variable, el recuento de estados se puede reducir drásticamente. [9]
Erlebach et al. ofrecen una versión más eficiente del algoritmo de aprendizaje de patrones de Angluin, así como una versión paralelizada. [10]
Arimura et al. muestran que una clase de lenguaje obtenida a partir de uniones limitadas de patrones se puede aprender en tiempo polinomial. [11]
La teoría de patrones , formulada por Ulf Grenander [12], es un formalismo matemático que describe el conocimiento del mundo en forma de patrones. Se diferencia de otros enfoques de la inteligencia artificial en que no comienza por prescribir algoritmos y maquinaria para reconocer y clasificar patrones, sino que prescribe un vocabulario para articular y reformular los conceptos de patrones en un lenguaje preciso.
Además del nuevo vocabulario algebraico, su enfoque estadístico fue novedoso en su objetivo de:
Amplia en su cobertura matemática, la teoría de patrones abarca el álgebra y la estadística, así como las propiedades topológicas locales y entrópicas globales.
El principio de inducción gramatical se ha aplicado a otros aspectos del procesamiento del lenguaje natural , y se ha aplicado (entre muchos otros problemas) al análisis semántico , [2] la comprensión del lenguaje natural , [13] la traducción basada en ejemplos , [14] la adquisición del lenguaje , [15] la compresión basada en gramática , [16] y la detección de anomalías . [17]
Los códigos basados en gramática o la compresión basada en gramática son algoritmos de compresión basados en la idea de construir una gramática libre de contexto (CFG) para la cadena que se va a comprimir. Los ejemplos incluyen algoritmos universales de compresión de datos sin pérdida . [18] Para comprimir una secuencia de datos , un código basado en gramática se transforma en una gramática libre de contexto . Se sabe que el problema de encontrar la gramática más pequeña para una secuencia de entrada ( problema de la gramática más pequeña ) es NP-hard, [19] por lo que se proponen muchos algoritmos de transformación de gramática desde puntos de vista teóricos y prácticos.
Generalmente, la gramática producida se comprime aún más mediante codificadores estadísticos como la codificación aritmética .
