La inducción gramatical (o inferencia gramatical [1] ) es un procedimiento de aprendizaje automático que restaura la gramática formal de un idioma a partir de un conjunto de observaciones (ejemplos) con una pertenencia conocida a ese idioma. Como resultado del procedimiento se construye un modelo de objetos observables en forma de un conjunto de reglas de inferencia o reglas de generación , un autómata finito o un autómata de otro tipo. En términos más generales, la inferencia gramatical es una de las áreas del aprendizaje automático en las que el espacio de ejemplo consiste en objetos combinatorios discretos como cadenas, árboles, gráficos.
La inferencia gramatical a menudo se centra en el problema del aprendizaje de autómatas finitos de varios tipos (consulte el artículo Regular Language Induction para obtener detalles de estos enfoques), ya que ha habido algoritmos eficientes para resolver este problema desde la década de 1980.
Desde principios de la década de 2000, estos enfoques se han extendido a la tarea de inferir gramáticas independientes del contexto y formalismos más ricos, como múltiples gramáticas independientes del contexto y gramáticas paralelas múltiples independientes del contexto. Otras clases de gramáticas para las que se estudió la inferencia gramatical también se estudiaron para otras clases de gramáticas: gramáticas contextuales y lenguajes de patrones .
El tipo de aprendizaje más simple es cuando el algoritmo de aprendizaje recibe solo un conjunto de ejemplos y, a veces, contraejemplos, de las palabras del idioma en cuestión. También hay otros modelos de aprendizaje. Una de las alternativas frecuentemente estudiadas es el caso en que el aprendiz puede preguntar sobre la pertenencia de la palabra a la lengua, como, por ejemplo, en el modelo de aprendizaje exacto o el modelo docente mínimamente adecuado introducido por Angluin [2] .
Se ha desarrollado una amplia variedad de métodos para la inferencia gramatical. Las dos fuentes clásicas son los artículos de Fu de 1977 [3] y 1982 [4] . Duda, Hart y Stork [5] también dedicaron una pequeña sección a este problema y citan muchas fuentes. El método básico de prueba y error que presentaron se analiza a continuación. Para conocer enfoques para subclasificar lenguajes regulares , en particular, consulte Inducción de lenguajes regulares . Un libro más reciente es el de de la Higuera (2010) [1] , que cubre la teoría de la inferencia gramatical en lenguajes regulares y autómatas finitos. D'Ulisia, Ferri y Grifoni [6] revisaron investigaciones sobre métodos de inferencia para lenguajes naturales.
El método propuesto en la sección 8.7 de Dowd, Hart y Stork [5] propone adivinar secuencialmente las reglas gramaticales y contrastarlas con observaciones positivas y negativas. El conjunto de reglas se amplía para que se pueda generar cada ejemplo positivo, pero si un conjunto de reglas dado genera un ejemplo negativo, debe descartarse. Este enfoque particular se puede describir como "prueba de hipótesis" y es algo similar al algoritmo de espacio de versiones de Mitchell . El texto del artículo de Dowd, Hart y Storck [5] brinda un ejemplo simple que ilustra bien el proceso, pero la viabilidad de un enfoque de prueba y error no guiado para problemas más grandes es cuestionable.
La inferencia gramatical por medio de algoritmos evolutivos es el proceso de evolución de la representación de la gramática de la lengua meta a través de algún proceso evolutivo. Las gramáticas formales se pueden representar fácilmente como árboles de reglas de inferencia a los que se pueden aplicar operadores evolutivos. Los algoritmos de este tipo tienen su origen en la programación genética , cuyo pionero fue John Koza . Otros trabajos iniciales sobre lenguajes formales simples utilizaron una representación de cadena binaria de algoritmos genéticos, pero la estructura jerárquica interna de las gramáticas que subyacen al lenguaje de forma aumentada de Backus-Naur hace que los árboles sean un enfoque más flexible.
Koza introdujo los programas Lisp como árboles. Se las arregló para encontrar analogías entre los operadores genéticos con los operadores estándar en los árboles. Por ejemplo, el intercambio de subárboles es equivalente al proceso correspondiente de cruce genético , donde las subcadenas del código genético se convierten en la individualidad de la próxima generación. La validez se mide evaluando el código una función Lisp . Analogías similares entre las estructuras de árbol de las representaciones de Lisp y las representaciones de árbol de las gramáticas hacen posible la técnica de aplicar la programación genética para la inducción gramatical.
En el caso de la inducción gramatical, la transferencia de subárboles corresponde al intercambio de reglas de inferencia, lo que hace posible analizar frases de un determinado idioma. El operador de validez para una gramática se basa en alguna medida de qué tan bien analiza un grupo de oraciones del idioma de destino. En la representación en árbol de la gramática, el símbolo terminal de la regla generadora corresponde a una hoja del árbol. Su nodo principal coincide con un carácter no terminal (como una frase nominal o una frase verbal ) en el conjunto de reglas. Después de todo, el nodo raíz puede corresponder a una secuencia de no terminales.
Como todos los algoritmos codiciosos , los algoritmos de inferencia codiciosos toman iterativamente la decisión que parece mejor en esa etapa. Una decisión generalmente se entiende como la creación de una nueva regla, la eliminación de una regla existente, la elección de una regla aplicable, la fusión de reglas existentes. Dado que los conceptos de "etapa" y "mejor" se pueden definir de diferentes maneras, se han creado varios algoritmos de inferencia codiciosos.
Los siguientes algoritmos para generar gramáticas libres de contexto toman una decisión después de leer cada carácter:
Los siguientes algoritmos para generar gramáticas libres de contexto primero leen la secuencia completa de caracteres y luego comienzan a tomar decisiones:
Los enfoques más recientes se basan en el aprendizaje distributivo . Los algoritmos que utilizan estos enfoques se han aplicado a la enseñanza de gramáticas libres de contexto y lenguajes ligeramente sensibles al contexto , y se ha demostrado que son correctos y eficientes para grandes subclases de estas gramáticas [7] [8]
Angluin definió un patrón como "una cadena de caracteres constantes del alfabeto Σ y caracteres variables de un conjunto disjunto". El lenguaje de dichos patrones es el conjunto de todos los ejemplos básicos no vacíos, es decir, todas las cadenas obtenidas reemplazando adecuadamente los caracteres variables con cadenas no vacías de caracteres constantes [nota 1] . Se dice que un patrón es descriptivo de un conjunto finito de cadenas si su lenguaje es mínimo (dada la inclusión del conjunto) entre todos los lenguajes de patrones, incluido el conjunto de entrada.
Angluin ha proporcionado un algoritmo polinomial para calcular, a partir de un conjunto de filas de entrada dado, todos los patrones descriptivos de una sola variable x[nota 2] . Con este fin, construye un autómata que representa todos los posibles patrones relevantes. Usando argumentos sofisticados sobre la longitud de las palabras que dependen solo de una sola variable x, el número de estados puede reducirse significativamente [9] .
Erlebach et al dieron una versión más eficiente del algoritmo de aprendizaje de patrones de Angluin, así como una versión paralela del algoritmo [10] .
Arimura et al., han demostrado que una clase de lenguajes obtenidos a partir de un grupo limitado de muestras se pueden entrenar en tiempo polinomial [11] .
La teoría de patrones ( ing. patrón teoría ), formulada por Ulf Grenander [12] , es un formalismo matemáticopara describir el conocimiento sobre el mundo en forma de patrones. La diferencia del enfoque propuesto para la inteligencia artificial de otros es que no comienza con la definición de algoritmos y máquinas para el reconocimiento y clasificación de patrones. Más bien, el método prescribe un vocabulario para formular y reescribir patrones en un lenguaje preciso.
Además del nuevo lenguaje algebraico, se ha introducido un nuevo enfoque estadístico con el objetivo de:
Los principios de la inducción gramatical se han aplicado a otros aspectos del procesamiento del lenguaje natural y (entre muchas otras tareas) a la percepción del lenguaje natural [13] , la traducción automática basada en ejemplos [14] , el análisis de morfemas y la derivación del Origen de los topónimos. La inducción gramatical también se ha utilizado para la compresión sin pérdidas [15] y la inferencia estadística a través de los principios de mensajes de longitud mínima y descripciones de longitud mínima . La inducción gramatical también se ha utilizado en algunos modelos probabilísticos de adquisición del lenguaje [16] .
| Aprendizaje automático y minería de datos | |
|---|---|
| Tareas | |
| Aprendiendo con un maestro | |
| análisis de conglomerados | |
| Reducción de dimensionalidad | |
| Pronóstico estructural | |
| Detección de anomalías | |
| Graficar modelos probabilísticos | |
| Redes neuronales | |
| Aprendizaje reforzado |
|
| Teoría | |
| revistas y congresos |
|