La teoría de la gramática para modelar cadenas de símbolos se originó a partir del trabajo en lingüística computacional con el objetivo de comprender la estructura de los lenguajes naturales . [1] [2] [3] Las gramáticas probabilísticas libres de contexto ( PCFG ) se han aplicado en el modelado probabilístico de estructuras de ARN casi 40 años después de su introducción en la lingüística computacional . [4] [5] [6] [7] [8]
Los PCFG amplían las gramáticas libres de contexto de forma similar a cómo los modelos ocultos de Markov amplían las gramáticas regulares . A cada producción se le asigna una probabilidad. La probabilidad de una derivación (análisis sintáctico) es el producto de las probabilidades de las producciones utilizadas en esa derivación. Estas probabilidades se pueden ver como parámetros del modelo y, para problemas grandes, es conveniente aprender estos parámetros a través del aprendizaje automático . La validez de una gramática probabilística está limitada por el contexto de su conjunto de datos de entrenamiento.
Los PCFG tienen aplicación en áreas tan diversas como el procesamiento del lenguaje natural para el estudio de la estructura de moléculas de ARN y el diseño de lenguajes de programación . El diseño de PCFG eficientes debe sopesar factores de escalabilidad y generalidad. Deben resolverse cuestiones como la ambigüedad gramatical. El diseño gramatical afecta la precisión de los resultados. Los algoritmos de análisis gramatical tienen varios requisitos de tiempo y memoria.
Un ejemplo de analizador sintáctico para gramáticas PCFG es el autómata pushdown . El algoritmo analiza los no terminales gramaticales de izquierda a derecha en forma de pila . Este enfoque de fuerza bruta no es muy eficiente. En el ARN, las variantes de predicción de la estructura secundaria del algoritmo de Cocke-Younger-Kasami (CYK) proporcionan alternativas más eficientes al análisis gramatical que los autómatas pushdown. [9] Otro ejemplo de un analizador PCFG es el analizador estadístico de Stanford, que ha sido entrenado con Treebank . [10]
Los modelos PCFG amplían las gramáticas libres de contexto de la misma forma que los modelos ocultos de Markov amplían las gramáticas regulares .
El algoritmo Inside-Outside es un análogo del algoritmo Forward-Backward . Calcula la probabilidad total de todas las derivaciones que son consistentes con una secuencia dada, basándose en algún PCFG. Esto es equivalente a la probabilidad de que el PCFG genere la secuencia e intuitivamente es una medida de cuán consistente es la secuencia con la gramática dada. El algoritmo Inside-Outside se utiliza en la parametrización del modelo para estimar las frecuencias previas observadas de las secuencias de entrenamiento en el caso de los ARN.