Gramàtica lliure de context provabilística

Una gramàtica lliure de context provabilística (GLCP) és una gramàtica lliure de context en la qual cada regla té assignada una provabilitat. La provabilitat d'un anàlisis sintàctic és el producte de les provabilitats de cada una de les regles usades en este. D'esta manera existixen anàlisis que són més consistents que uns atres. Les GLPC estenen les gramàtiques lliure de contexts de la mateixa manera que els models amagats de Márkov estenen les gramàtiques regulars. Les GLPC s'utilisen en el processament del llenguage natural i en l'estudi de molècules d'ARN dins del camp de la Bioinformática. Les GLPC són una especialisació de les gramàtica lliures de context en pesos.

Tècniques

Una variant del algoritme de CYK troba el camí de Viterbi d'una frase donat una GLCP. El camí de Viterbi és l'anàlisis més provable d'una frase donada la GLCP.

Els algoritmes dins-fòra són anàlecs al algoritme d'alvanç-reculada. Poden usar-se per a calcular la provabilitat total de tots els anàlisis consistent donada una frase, basant-se en una GLCP. Açò és equivalent a la provabilitat de que una GLCP genere eixa frase, i intuitivamente és una mida de cóm de consistent és la frase que és donada per la gramàtica.

Els algoritmes dins-fora poden usar-se també per a calcular les provabilitats que una determinada producció siga usada en un anàlisis qualsevol d'una frase. Açò és usat com una part del algoritme expectació-maximización per a deprendre les provabilitats de similitut màxima per a una GLCP, basant-se en un conjunt de frases d'entrenament que la GLCP deu modelar. L'algoritme és anàlec a l'usat en els models amagats de Márkov.

Aplicacions

Processament del llenguage natural

Les gramàtiques lliures de context varen ser concebudes en un intent de modelar els llenguages naturals, com els que utilisen normalment els humans. Atres investigacions han estés esta idea per mig de l'us de les GLCP.

A continuació es mostra un eixemple senzill d'una GLCP en 2 regles. Cada regla és precedida per una provabilitat que reflectix la freqüència relativa d'esta.

0.7 VP --> V NP

0.3 VP --> V NP NP

Donada esta gramàtica, podem dir que el número de NPs esperats durant la derivació de VP és de 0.7 x 1 + 0.3 x 2 = 1.3. En concret, alguns sistemes de reconeiximent del parla usen GLCP per a millorar les estimacions de provabilitat i d'esta manera la seua eixecució.

Recentment, les GLCP han jugat un paper decisiu en l'explicació de la jerarquia d'accessibilitat, la qual busca explicar per qué certes estructures resulten més difícil d'entendre que unes atres.

Si es dispon d'una mida provabilística de les construccions més provables, llavors es pot calcular la entropía per a estes construccions. Si l'aparat cognitiu per a la sintaxis està basat en estes tècniques de la teoria de l'informació, llavors pot utilisar-se ferramentes similars a les GLCP.

ARN

Les gramàtiques lliures de context són adequades per a modelar les estructures secundàries de el ARN.

Si considerem la següent gramàtica, a on a,c,g,o representen nucleòtits i S és el símbol inicial (l'únic no terminal):

S → aSu | cSg | gSc | usa

Esta gramàtica simple representa una molècula de ARN que conté dos regions complementàries, en les quals només les parelles de complementaris canònics estan permeses (A-U i C-G).

Utilisant les GLCP és possible modelar els emparejamientos que són més o menys consistents dins de distints patrons d'una molècula de ARN. Les GLCP són usades per a classificar els patrons en famílies de gens de ARN, aixina com en la busca de seqüències de genoma de provables membres d'estes famílies. També són usades per a trobar gens de ARN.