Wikipedia

Inducción gramatical

Este artículo o sección necesita ser wikificado, por favor, edítalo para que cumpla con las convenciones de estilo.
Este aviso fue puesto el 31 de agosto de 2022.

La inducción gramatical o inferencia gramatical[1]​ 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 editar

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[2]​, las gramáticas estocásticas libres de contexto[3]​, las gramáticas contextuales y los lenguajes de patrones.

Modelos de aprendizaje editar

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.[4]​

Metodologías editar

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)[1]​, que cubre la teoría de la inferencia gramatical de lenguajes regulares y autómatas de estado finito. D'Ulizia, Ferri y Grifoni[5]​ proporcionan una encuesta que explora métodos de inferencia gramatical para lenguajes naturales.

Inferencia gramatical por ensayo y error editar

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 editar

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 editar

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:

Aprendizaje distributivo editar

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[6]​.

Aprendizaje de lenguajes de patrones editar

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.[note 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 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.[note 2]​ 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.[7]​

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

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

Teoría de patrones editar

La teoría de patrones, formulada por Ulf Grenander,[10]​ 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 editar

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,[2]​ comprensión del lenguaje natural,[11]​ traducción basada en ejemplos,[12]​ 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[13]​ 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.[14]​

Véase también editar

notas editar

  1. ↑ The language of a pattern with at least two occurrences of the same variable is not regular due to the pumping lemma.
  2. ↑ x may occur several times, but no other variable y may occur

Referencias editar

  1. ↑ a b de la Higuera, Colin (2010). Grammatical Inference: Learning Automata and Grammars. Cambridge: Cambridge University Press. Archivado desde el original el 14 de febrero de 2019. Consultado el 1 de agosto de 2022. 
  2. ↑ a b Kwiatkowski, Tom, et al. "Lexical generalization in CCG grammar induction for semantic parsing." Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2011.
  3. ↑ Clark, Alexander. "Unsupervised induction of stochastic context-free grammars using distributional clustering." Proceedings of the 2001 workshop on Computational Natural Language Learning-Volume 7. Association for Computational Linguistics, 2001.
  4. ↑ Dana Angluin (1987). «Learning Regular Sets from Queries and Counter-Examples». Information and Control 75 (2): 87-106. doi:10.1016/0890-5401(87)90052-6. Archivado desde el original el 2 de diciembre de 2013. 
  5. ↑ D’Ulizia, A., Ferri, F., Grifoni, P. (2011) "A Survey of Grammatical Inference Methods for Natural Language LearningUso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).", Artificial Intelligence Review, Vol. 36, No. 1, pp. 1–27.
  6. ↑ Clark and Eyraud (2007) Journal of Machine Learning Research; Ryo Yoshinaka (2011) Theoretical Computer Science
  7. ↑ Dana Angluin (1980). «Finding Patterns Common to a Set of Strings». Journal of Computer and System Sciences 21: 46-62. doi:10.1016/0022-0000(80)90041-0. 
  8. ↑ T. Erlebach; P. Rossmanith; H. Stadtherr; A. Steger; T. Zeugmann (1997). «Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries». En M. Li; A. Maruoka, eds. Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97. LNAI 1316. Springer. pp. 260-276. 
  9. ↑ Hiroki Arimura; Takeshi Shinohara; Setsuko Otsuki (1994). «Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data». Proc. STACS 11. LNCS 775. Springer. pp. 649-660. Uso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
  10. ↑ Grenander, Ulf, and Michael I. Miller. Pattern theory: from representation to inference.Uso incorrecto de la plantilla enlace roto (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Vol. 1. Oxford: Oxford university press, 2007.
  11. ↑ Miller, Scott, et al. "Hidden understanding models of natural language." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.
  12. ↑ Brown, Ralf D. "Transfer-rule induction for example-based translation." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.
  13. ↑ Cherniavsky, Neva, and Richard Ladner. "Grammar-based compression of DNA sequences." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).
  14. ↑ Chater, Nick, and Christopher D. Manning. "Probabilistic models of language processing and acquisition." Trends in cognitive sciences 10.7 (2006): 335-344.
Obtenido de «https://es.wikipedia.org/w/index.php?title=Inducción_gramatical&oldid=154106378»