Inducción gramatical

La inducción gramatical o inferencia gramatical​ es el proceso dentro del 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 estado finito 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 en la que el espacio de instancia consta de objetos combinatorios discretos, como cadenas, árboles y gráficos.

Clases de gramática

La inferencia gramatical a menudo se ha centrado mucho en el problema del aprendizaje de máquinas de estados finitos de varios tipos (consulte 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 gramáticas múltiples libres de contexto y gramáticas paralelas múltiples libres de contexto. Otras clases de gramáticas para las que se ha estudiado la inferencia gramatical son las gramáticas categoriales combinatorias​, las gramáticas estocásticas libres de contexto​, las gramáticas contextuales y los lenguajes de patrones.

Modelos de aprendizaje

La forma más simple de aprendizaje es donde el algoritmo de aprendizaje simplemente recibe un conjunto de ejemplos extraídos del idioma en cuestión: el objetivo es aprender el idioma a partir de ejemplos del mismo (y, rara vez, de contraejemplos, es decir, ejemplos que no pertenecen a la lengua). Sin embargo, se han estudiado otros modelos de aprendizaje. Una alternativa estudiada con frecuencia es el caso en el que el alumno puede hacer consultas de membresía como en el modelo de aprendizaje de consulta exacta o el modelo de maestro mínimamente adecuado introducido por Angluin.​

Metodologías

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 prueba y error que presentan se analiza a continuación. Para conocer enfoques para inferir subclases de lenguajes regulares en particular, consulte Inducción de lenguajes regulares . Un libro de texto más reciente es de la Higuera (2010)​, que cubre la teoría de la inferencia gramatical de lenguajes regulares y autómatas de estado finito. D'Ulizia, Ferri y Grifoni​ proporcionan una encuesta que explora métodos de inferencia gramatical para lenguajes naturales.

Inferencia gramatical por ensayo y error

El método propuesto en la Sección 8.7 de Duda, Hart y Stork (2001) sugiere adivinar sucesivamente reglas gramaticales (producciones) y contrastarlas con observaciones positivas y negativas. El conjunto de reglas se amplía para poder generar cada ejemplo positivo, pero si un conjunto de reglas determinado también genera un ejemplo negativo, debe descartarse. Este enfoque particular se puede caracterizar como "prueba de hipótesis" y tiene cierta similitud con el algoritmo de espacio de versión de Mitchell. El texto Duda, Hart y Stork (2001) brinda un ejemplo simple que ilustra muy bien el proceso, pero la viabilidad de un enfoque de prueba y error no guiado para problemas más sustanciales es dudosa.

Inferencia gramatical por algoritmos genéticos

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 pueden representarse fácilmente como estructuras de árbol de reglas de producción que pueden estar sujetas a operadores evolutivos. Los algoritmos de este tipo provienen del paradigma de programación genética iniciado por John Koza .^{[cita requerida]} Otros trabajos iniciales 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 de Lisp como árboles. Pudo encontrar análogos a los operadores genéticos dentro del conjunto estándar de operadores de árboles. Por ejemplo, el intercambio de 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 próxima generación. La aptitud se mide calificando la salida de las funciones del código Lisp. Análogos similares entre la representación ceceo estructurada en árbol 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 sintáctico 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 principales corresponden a un símbolo no terminal (por ejemplo, un sintagma nominal o un sintagma verbal ) en el conjunto de reglas. En última instancia, el nodo raíz podría corresponder a una oración no terminal.

Inferencia gramatical por algoritmos voraces

Como todos los algoritmos voraces, los algoritmos de inferencia gramatical voraz toman, de manera iterativa, decisiones que parecen ser las mejores en esa etapa. Las decisiones que se toman generalmente se refieren a cosas 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 hay varias formas de definir 'el escenario' y 'el mejor', también hay varios algoritmos de inferencia gramaticales voraces.

Estos algoritmos generadores de gramática independientes del contexto toman la decisión después de cada símbolo de lectura:

• El algoritmo Lempel-Ziv-Welch crea una gramática libre de contexto de manera determinista, de modo que es necesario almacenar solo la regla de inicio de la gramática generada.
• Sequitur y sus modificaciones.

Estos algoritmos generadores de gramática libres de contexto primero leen toda la secuencia de símbolos dada y luego comienzan a tomar decisiones:

• Codificación de pares de bytes y sus optimizaciones.

Aprendizaje distributivo

Un enfoque más reciente se basa en el aprendizaje distributivo. Los algoritmos que utilizan estos enfoques se han aplicado para aprender gramáticas independientes del contexto y lenguajes levemente sensibles al contexto y se ha demostrado que son correctos y eficientes para grandes subclases de estas gramáticas​.

Aprendizaje de lenguajes de patrones

Angluin define un patrón como "una cadena de símbolos constantes de Σ y símbolos variables de un conjunto disjunto". El lenguaje de tal patrón es el conjunto de todas sus instancias fundamentales 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.​ Un patrón se denomina descriptivo para un conjunto finito de cadenas de entrada si su lenguaje es mínimo (con respecto a la inclusión del conjunto) entre todos los lenguajes de patrones que incluyen el conjunto de entrada.

Angluin proporciona un algoritmo polinomial para calcular, para un conjunto de cadenas de entrada dado, todos los patrones descriptivos en una variable x.​ Con este fin, construye un autómata que representa todos los patrones posiblemente relevantes; utilizando argumentos sofisticados sobre la longitud de las palabras, que se basan en que x es la única variable, el recuento de estados se puede reducir drásticamente.​

Erlebach et al. dar una versión más eficiente del algoritmo de aprendizaje de patrones de Angluin, así como una versión paralelizada.​

Arimura et al. Demuestre que una clase de lenguaje obtenida de uniones limitadas de patrones se puede aprender en tiempo polinomial.​

Teoría de patrones

La teoría de patrones, formulada por Ulf Grenander,​ es un formalismo matemático para describir el conocimiento del mundo como patrones. Se diferencia de otros enfoques de la inteligencia artificial en que no comienza prescribiendo algoritmos y maquinaria para reconocer y clasificar patrones; más bien, prescribe un vocabulario para articular y reformular los conceptos de patrón en un lenguaje preciso.

Además del nuevo vocabulario algebraico, su enfoque estadístico fue novedoso en su objetivo de:

• Identifique las variables ocultas de un conjunto de datos utilizando datos del mundo real en lugar de estímulos artificiales, lo que era común en ese momento.
• Formule distribuciones previas para variables ocultas y modelos para las variables observadas que forman los vértices de un gráfico tipo Gibbs.
• Estudia la aleatoriedad y la variabilidad de estos gráficos.
• Cree las clases básicas de modelos estocásticos aplicados enumerando las deformaciones de los patrones.
• Sintetice (muestra) a partir de los modelos, no solo analice señales con él.

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.

Aplicaciones

El principio de la 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,​ comprensión del lenguaje natural,​ traducción basada en ejemplos,​ análisis de morfemas, y derivaciones de topónimos.^{[cita requerida]} inducción gramatical también se ha utilizado para la compresión basada en la gramática​ y la inferencia estadística a través de los principios de longitud mínima del mensaje (MML) y longitud mínima de descripción (MDL).^{[cita requerida]} inducción gramatical también se ha utilizado en algunos modelos probabilísticos de adquisición del lenguaje.​

Véase también

• Aprendizaje de gramática artificial #Inteligencia artificial
• Traducción automática basada en ejemplos
• programación inductiva
• Complejidad de Kolmogorov
• Identificación de lenguaje en el límite
• gramática lineal
• Reconocimiento de patrones sintácticos

Referencias

• Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001), Pattern Classification (2 edición), New York: John Wiley & Sons .
• Fu, King Sun (1982), Syntactic Pattern Recognition and Applications, Englewood Cliffs, NJ: Prentice-Hall .
• Fu, King Sun (1977), Syntactic Pattern Recognition, Applications, Berlin: Springer-Verlag .
• Horning, James Jay (1969), A Study of Grammatical Inference (Ph.D. Thesis edición), Stanford: Stanford University Computer Science Department, ProQuest 302483145 .
• Gold, E. Mark (1967), Language Identification in the Limit 10, Information and Control, pp. 447-474, archivado desde el original el 28 de agosto de 2016, consultado el 4 de septiembre de 2016 .
• Gold, E. Mark (1967), Language Identification in the Limit 10, Information and Control, pp. 447-474 .

• Datos: Q5593673