Gramática libre de contexto probabilística

Una gramática libre de contexto probabilística (GLCP) es una gramática libre de contexto en la cual cada regla tiene asignada una probabilidad. La probabilidad de un análisis sintáctico es el producto de las probabilidades de cada una de las reglas usadas en éste. De esta manera existen análisis que son más consistentes que otros. Las GLPC extienden las gramáticas libre de contextos de la misma manera que los modelos ocultos de Márkov extienden las gramáticas regulares. Las GLPC se utilizan en el procesamiento del lenguaje natural y en el estudio de moléculas de ARN dentro del campo de la Bioinformática. Las GLPC son una especialización de las gramática libres de contexto con pesos.

Técnicas

Una variante del algoritmo de CYK encuentra el camino de Viterbi de una frase dado una GLCP. El camino de Viterbi es el análisis más probable de una frase dada la GLCP.

Los algoritmos dentro-fuera son análogos al algoritmo de avance-retroceso. Pueden usarse para calcular la probabilidad total de todos los análisis consistente dada una frase, basándose en una GLCP. Esto es equivalente a la probabilidad de que una GLCP genere esa frase, e intuitivamente es una medida de cómo de consistente es la frase que es dada por la gramática.

Los algoritmos dentro-fuera pueden usarse también para calcular las probabilidades que una determinada producción sea usada en una análisis cualquiera de una frase. Esto es usado como una parte del algoritmo expectación-maximización para aprender las probabilidades de similitud máxima para una GLCP, basándose en un conjunto de frases de entrenamiento que la GLCP debe modelar. El algoritmo es análogo al usado en los modelos ocultos de Márkov.

Aplicaciones

Procesamiento del lenguaje natural

Las gramáticas libres de contexto fueron concebidas en un intento de modelar los lenguajes naturales, como los que utilizan normalmente los humanos. Otras investigaciones han extendido esta idea mediante el uso de las GLCP.

A continuación se muestra un ejemplo sencillo de una GLCP con 2 reglas. Cada regla es precedida por una probabilidad que refleja la frecuencia relativa de esta.

0.7 VP --> V NP

0.3 VP --> V NP NP

Dada esta gramática, podemos decir que el número de NPs esperados durante la derivación de VP es de 0.7 x 1 + 0.3 x 2 = 1.3. En concreto, algunos sistemas de reconocimiento del habla usan GLCP para mejorar las estimaciones de probabilidad y de este modo su ejecución.

Recientemente, las GLCP han jugado un papel decisivo en la explicación de la jerarquía de accesibilidad, la cual busca explicar por qué ciertas estructuras resultan más difícil de entender que otras.

Si se dispone de una medida probabilística de las construcciones más probables, entonces se puede calcular la entropía para estas construcciones. Si el aparato cognitivo para la sintaxis está basado en estas técnicas de la teoría de la información, entonces puede utilizarse herramientas similares a las GLCP.​

ARN

Las gramáticas libres de contexto son adecuadas para modelar las estructuras secundarias del ARN.​​

Si consideramos la siguiente gramática, donde a,c,g,u representan nucleótidos y S es el símbolo inicial (el único no terminal):

S → aSu | cSg | gSc | uSa

Esta gramática simple representa una molécula de ARN que contiene dos regiones complementarias, en las cuales sólo las parejas de complementarios canónicos están permitidas (A-U y C-G).

Utilizando las GLCP es posible modelar los emparejamientos que son más o menos consistentes dentro de distintos patrones de una molécula de ARN. Las GLCP son usadas para clasificar los patrones en familias de genes de ARN, así como en la búsqueda de secuencias de genoma de probables miembros de estas familias. También son usadas para encontrar genes de ARN.

• Elena Rivas and Sean R. Eddy (2001), "Noncoding RNA gene detection using comparative sequence analysis", BMC Bioinformatics, 2 (1): 8. [2]

Enlaces externos

• Rfam Database