Inducción gramatical

Existen varios métodos para la inducción de gramáticas libres de contexto probabilísticas . ^{[ 6 ] [ 7 ]}

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 dado también genera un ejemplo negativo, debe descartarse. Este enfoque particular puede caracterizarse como "prueba de hipótesis" y guarda cierta similitud con el algoritmo de espacio de versiones de Mitchel . El texto de Duda, Hart y Stork (2001) proporciona un ejemplo sencillo que ilustra claramente el proceso, pero la viabilidad de este enfoque de ensayo y error sin guía para problemas más complejos es dudosa.

La inducción gramatical mediante algoritmos evolutivos consiste en desarrollar una representación de la gramática de un lenguaje objetivo a través de un proceso evolutivo. Las gramáticas formales pueden representarse fácilmente como estructuras de árbol de reglas de producción que pueden someterse a operadores evolutivos. Este tipo de algoritmos se derivan del paradigma de programación genética desarrollado por John Koza . Otros trabajos iniciales sobre lenguajes formales simples utilizaron la representación de cadenas binarias de los 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. Logró encontrar análogos a los operadores genéticos dentro del conjunto estándar de operadores de árbol. Por ejemplo, el intercambio de subárboles es equivalente al proceso correspondiente de cruce genético, donde subcadenas de un código genético se trasplantan a un individuo de la siguiente generación. La aptitud se mide puntuando la salida 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 de gramáticas.

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 un idioma determinado. El operador de aptitud de la gramática se basa en una medida de su rendimiento al analizar un grupo de oraciones del idioma de destino. En una representación arbórea de una gramática, un símbolo terminal de una regla de producción corresponde a un nodo hoja del árbol. Sus nodos padres corresponden a un símbolo no terminal (por ejemplo, un sintagma nominal o un sintagma verbal ) en el conjunto de reglas. Finalmente, el nodo raíz podría corresponder a un símbolo no terminal de una oración.

Como todos los algoritmos voraces , los algoritmos de inferencia gramatical voraces toman, de forma iterativa, las decisiones que parecen ser las mejores en cada etapa. Estas decisiones suelen referirse a la creación de nuevas reglas, la eliminación de reglas existentes, la elección de una regla para aplicar o la fusión de algunas reglas existentes. Dado que existen varias maneras de definir "la etapa" y "la mejor opción", también existen varios algoritmos de inferencia gramatical voraces.

Estos algoritmos generadores de gramática libre de contexto toman la decisión después de cada símbolo leído:

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

Estos algoritmos generadores de gramática libre 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.

Un enfoque más reciente se basa en el aprendizaje distribucional. Los algoritmos que utilizan estos enfoques se han aplicado al aprendizaje 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. ^{[ 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 dicho patrón es el conjunto de todas sus instancias básicas no vacías, es decir, todas las cadenas resultantes de la sustitución 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 finito de cadenas de entrada si su lenguaje es mínimo (con respecto a la inclusión de conjuntos) entre todos los lenguajes de patrones que engloban dicho conjunto.

Angluin proporciona 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 dependen de que x sea la única variable, el número de estados se puede reducir drásticamente. ^{[ 9 ]}

Erlebach et al. presentan una versión más eficiente del algoritmo de aprendizaje de patrones de Angluin, así como una versión paralela. ^{[ 10 ]}

Arimura et al. muestran que una clase de lenguaje obtenida a partir de uniones limitadas de patrones puede aprenderse 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 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 patrones en un lenguaje preciso.

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

• Identificar las variables ocultas de un conjunto de datos utilizando datos del mundo real en lugar de estímulos artificiales, lo cual era habitual en aquel entonces.
• Formule distribuciones previas para las variables ocultas y modelos para las variables observadas que forman los vértices de un grafo 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.
• Sintetizar (muestrear) a partir de los modelos, no solo analizar señales con ellos.

La teoría de patrones, de amplio alcance matemático, abarca el álgebra y la estadística, así como las propiedades topológicas locales y entrópicas globales.