Gramática libre de contexto probabilística
En computación unha gramática libre de contexto probabilística (GLCP) é unha gramática libre de contexto na cal cada regra ten asignada unha probabilidade. A probabilidade dunha análise sintáctica é o produto das probabilidades de cada unha das regras usadas neste. Deste xeito existen análises que son máis consistentes que outras. As GLPC estenden as gramáticas libre de contextos da mesma xeito que os modelos ocultos de Markov estenden as gramáticas regulares. As GLPC utilízanse no procesamento da linguaxe natural e no estudo de moléculas de ARN dentro do campo da bioinformática. As GLPC son unha especialización das gramática libres de contexto con pesos.
Técnicas
[editar | editar a fonte]Unha variante do algoritmo de CYK atopa o camiño de Viterbi dunha frase dada unha GLCP. O camiño de Viterbi é a análise máis probable dunha frase dada a GLCP.
Os algoritmos dentro-fóra son análogos ao algoritmo de avance-retroceso. Poden usarse para calcular a probabilidade total de todas as análise consistente dada unha frase, baseándose nunha GLCP. Isto é equivalente á probabilidade de que unha GLCP xere esa frase, e intuitivamente é unha medida de como de consistente é a frase que é dada pola gramática.
Os algoritmos dentro-fóra poden usarse tamén para calcular as probabilidades que unha determinada produción sexa usada nunha análise calquera dunha frase. Isto é usado como unha parte do algoritmo expectación-maximización para aprender as probabilidades de similitude máxima para unha GLCP, baseándose nun conxunto de frases de adestramento que a GLCP debe modelar. O algoritmo é análogo ao usado nos modelos ocultos de Markov.
Aplicacións
[editar | editar a fonte]Procesamento da linguaxe natural
[editar | editar a fonte]As gramáticas libres de contexto foron concibidas nun intento de modelar as linguaxes naturais, como os que utilizan normalmente os humanos. Outras investigacións estenderon esta idea mediante o uso das GLCP.
A continuación móstrase un exemplo sinxelo dunha GLCP con 2 regras. Cada regra é precedida por unha probabilidade que reflicte a frecuencia relativa desta.
- 0.7 VP --> V NP
- 0.3 VP --> V NP NP
Dada esta gramática, podemos dicir que o número de NPs esperados durante a derivación de VP é de 0.7 x 1 + 0.3 x 2 = 1.3. En concreto, algúns sistemas de recoñecemento do fala usan GLCP para mellorar as estimacións de probabilidade e deste xeito a súa execución e desempeño.
Recentemente, as GLCP xogaron un papel decisivo na explicación da xerarquía de accesibilidade, a cal busca explicar por que certas estruturas resultan máis difícil de entender que outras.
Se se dispón dunha medida probabilística das construcións máis probables, entón pódese calcular a entropía para estas construcións. Se o aparello cognitivo para a sintaxe está baseado nestas técnicas da teoría da información, entón poden empregarse ferramentas similiares ás GLCP.[1]
ARN
[editar | editar a fonte]As gramáticas libres de contexto son adecuadas para modelar as estruturas secundarias do ARN[2][3].
Se consideramos a seguinte gramática, onde a,c,g,ou reprensentan nucleótidos e S é o símbolo inicial (o único non terminal):
- S → aSu | cSg | gSc | usa
Esta gramática simple representa unha molécula de ARN que contén dúas rexións complementarias, nas cales só as parellas de complementarios canónicos están permitidas (A-Ou e C-G).
Utilizando as GLCP é posible modelar os emparellamentos que son máis ou menos consistentes dentro de distintos patróns dunha molécula de ARN. As GLCP son usadas para clasificar os patróns en familias de xenes de ARN, así como na procura de secuencias de xenoma de probables membros destas familias. Tamén son usadas para atopar xenes de ARN.
Notas
[editar | editar a fonte]- ↑ John Ale (2006). Uncertainty About the Rest of the Sentence. Cognitive Science 30 (Dept Linguistics, Michigan State University). pp. 643–672. doi:10.1207/s15516709cog0000_64.
- ↑ Durbin, Eddy, Krogh, Mitchison, Biological sequence analysis, Cambridge University Press, 1998. This bioinformatics textbook includes an accessible introduction to the use of SCFGs for modelling RNA, as well as the history of this application to 1998.
- ↑ Sexan R. Eddy and Richard Durbin (1994), "RNA sequence analysis using covariance models", Nucleic Acids Research, 22 (11): 2079-88. [1] Arquivado 30 de maio de 2020 en Wayback Machine.
- Elena Rivas e Sexan R. Eddy (2001), "Noncoding RNA gene detection using comparative sequence analysis", BMC Bioinformatics, 2 (1): 8. [2]
