Gramática livre de contexto estocástica

Origem: Wikipédia, a enciclopédia livre.

Uma Gramática estocástica livre-de-contexto (GELC, ou também Gramática probabilística livre-de-contexto, GPLC) é uma gramática livre de contexto em que cada produção é aumentada com uma probabilidade. A probabilidade de uma derivação (análise) é então o produto das probabilidades das produções usadas naquela derivação. Portanto, algumas derivações são mais consistentes com uma gramática estocástica do que outras.

As GELC estendem as gramáticas livre-de-contexto da mesma forma que Modelo oculto de Markov estendem as gramáticas regulares. As GELC tem aplicações em áreas diversas como Processamento de linguagem natural para estudar as moléculas de RNA. As GELC são uma forma especializada de gramáticas livre-de-contexto ponderada.

Técnicas[editar | editar código-fonte]

Com uma variante do Algoritmo CYK encontra-se o Algoritmo de Viterbi através de uma sequência passos de um GELC dada. A análise de viterbi é a derivação mais plausível de uma sequência dada pela GELC. O Algoritmo de dentro para fora é análogo ao Algoritmo para frente e para trás, e ele pode ser usado para computar a total probabilidade de todas as derivações que são consistentes com a sequência dada, baseada em alguma GELC. Isso é equivalente a probabilidade da uma GELC gerando uma sequência, e é intuitivamente uma medida de quão consistente é uma sequência com uma gramática dada.

O Algoritmo de dentro para fora também pode ser usado para computar as probabilidades que uma dada produção será usada numa derivação aleatória de uma sequência. Isso é usado como parte de um Algoritmo esperança-minimização para aprender a máxima verossimilhança para uma GELC baseada em um conjunto de sequências que uma GELC deve modelar.[1] O algoritmo é análogo ao utilizado pelos Modelo oculto de Markov.

Aplicações[editar | editar código-fonte]

Processamento de Linguagem Natural[editar | editar código-fonte]

Gramáticas livre-de-contexto foram originalmente concebidas em uma tentativa de modelar linguagens naturais, ou seja, aquelas normalmente falada pelos humanos.[2] Como as gramáticas foram originalmente concebidas como conjuntos de regras (produções), normalmente especificadas em uma sintaxe como Backus–Naur Form, onde as regras são absolutas; tais gramáticas ainda são apropriada para inúmeras situações (notadamente, para projetar linguagens de programação). GPLC são uma tentativa de lidar com as dificuldades encontradas ao tentar estender as GLC para lidar com as complexidades das línguas naturais. Especificamente, em muitas vezes descobre-se que mais de uma regra de produção podem ser aplicadas a uma sequência de palavras, resultando em um conflito: uma análise ambígua. Isso acontece por várias razões, tais como homógrafos – palavras escritas de formas idênticas porém com muitos significados – de modo que uma mesma sequência de palavras possa ter mais de uma interpretação. Um Trocadilho é um exemplo de uma análise ambígua utilizada deliberadamente para efeito humorístico, como na manchete de jornal "Iraqi Head Seeks Arms". Uma estratégia para lidar com análise ambígua (proveniente de gramáticas mais recentes como Panini) é adicionar mais regras, ou priorizá-las para que uma regra tenha precedência sobre outras. Isso, entretanto, tem a inconveniência de proliferar regras, muitas vezes chegando ao ponto em que elas se tornam difíceis de se gerenciar. Outra dificuldade e a sobre-geração, onde estruturas não licenciadas são também geradas. Gramáticas probabilísticas contornam esses problemas usando a frequência de várias para ordená-las, resultando em uma interpretação “mais provável”. Como padrões de uso são alternados em turnos diacrônico, essas regras probabilísticas podem ser re-aprendidas, dessa forma, atualizando a gramática. Pode-se construir uma gramática probabilística de uma sintaxe formal tradicional, atribuindo a cada não-terminal uma probabilidade tomada de alguma distribuição, a ser eventualmente estimada a partir de dados de uso. Na maioria das amostras de linguagens amplas, as gramáticas probabilísticas que ajustam estas probabilidades a partir de dados normalmente realizados por gramáticas artesanais(embora algumas gramáticas baseadas em regras estão se aproximando da precisão das GPLC).

Aqui está um pequeno exemplo de uma GPLC de duas regras. Cada regra é procedida por uma probabilidade que reflete a frequência relativa com que essa regra ocorre:

0.7 VP -> V NP
0.3 VP -> V NP NP

Dada esta gramática, podemos agora dizer que o número de NPs esperado enquanto os VP’s decorrentes é de 0,7 x 1 + 0,3 x 2 = 1,3.

As probabilidades são normalmente calculadas por Aprendizagem de máquina, programas que operam com grandes volumes de textos anotados, como o Penn TreeBank, que contém uma grande coleção de artigos do Jornal Wall Street. Como tal, a validade de uma gramática probabilística é limitada pelo contexto do texto usado para treiná-la, a definição de “mais provável” é susceptível de variar com o contexto do discurso.

Um exemplo de uma análise de uma GPLC que foi treinada usando Treebank Penn é o Stanford Statistical Parser de Klein e Manningt,[3] baixável em http://nlp.stanford.edu/software/lex-parser.shtml Em particular, alguns sistemas de Reconhecimento de fala usam GELC para melhorar sua estimativa de probabilidade e, assim, seu desempenho.[4]

RNA[editar | editar código-fonte]

Gramáticas livre-de-contexto são ápteis a modelar a segunda estrutura do RNA.[5][6] A estrutura secundária do RNA envolve Nucleotídeos dentro de uma molécula de RNA de filamento único, que são complementares entre se e, portanto , pares de bases. Este emparelhamento de bases é biologicamente importante para o bom funcionamento da molécula de RNA. Grande parte desse emparelhamento de bases pode ser representado em uma gramática livre-de-contexto (a grande exceção sendo os Pseudoknot).

Por exemplo, considere a seguinte gramática, onde a,c,g,u representam os nucleotídeos e S é o símbolo inicial(e não terminal).

S -> aSu | cSg | gSc | uSa

Essa simples Gramática livre-de-contexto representa uma molécula de RNA que consiste inteiramente de duas regiões totalmente complementares, em que apenas pares canônicos complementares são permitidos (i.e. AU e CG). Anexando probabilidade as Gramaticas livre-de-contexto mais sofisticadas, é possível modelar bases ou pares de bases que são mais ou menos consistentes com uma molécula padrão de RNA. GELC são usadas para modelar os padrões de famílias de genes RNA no banco de dados Rfam, e pesquisar sequências de genomas que são membros adicionais dessas famílias. GELC são também usadas para encontrar genes RNA usando comparação genômica. Neste trabalho, homólogos de um gene RNA potencial em dois organismos relacionados são inspecionados usando técnicas das GELC para checar se a segunda estrutura é conservada. Se for, a sequência provavelmente é um gene RNA, e a estrutura secundária se presume ser conservada por causa das necessidades funcionais do gene RNA. Tem sido mostrado que as GELC poderiam prever a estrutura secundária de uma molécula de RNA de forma semelhante as técnicas já existentes: tais GELC são usadas, por exemplo, pelo programa Stemloc.

Linguística e Psicolinguística[editar | editar código-fonte]

Com a publicação do Teorema de Gold[7] em 1967 foi alegado que as gramáticas das línguas naturais regidas por regras determinísticas não poderiam ser aprendidas baseadas em exemplos positivos isolados. Este foi parte do argumento da pobreza de estímulo, apresentado em 1980[8] e implícita desde as primeiras obras de Chomsky dos anos 1950. Entre outros argumentos, o que levou ao ponto de vista do nativismo psicológico (mas ainda não comprovado), foi que uma forma de gramática, incluindo um léximo conceitual completo em algumas versões, eram hardwired desde o nascimento. No entanto, o resultado da capacidade de aprendizado do Gold pode ser facilmente contornada, se quisermos assumir que o aprendiz aprende uma aproximação quase que perfeita para o linguagem correta ou que aprendiz aprende a partir de entradas típicas ao invés de entradas arbitrárias. De fato, mostrou-se que simplesmente receber a entrada de uma pessoa que produzisse aleatoriamente exemplos positivos um pouco do que de acordo com um plano desonesto pré-especificado leva a identificabilidade no limite com probabilidade 1.[9][10]

Recentemente, gramáticas probabilísticas parecem ter ganhado alguma plausibilidade cognitiva. É sabido que existem graus de dificuldade em acessar diferentes estruturas estáticas (e.g. Hierarquia da acessibilidade para Cláusulas Relativas). Versões probabilísticas da Gramática Minimalista têm sido usadas para calcular os valores das informações teóricas, que parecem correlacionar-se bem com os dados psicolinguísticos sobre compreensibilidade e dificuldade de produção.[11]

Ver também[editar | editar código-fonte]

Referências

  1. ↑ Aycinena, M.A. (2005). Probabilistic geometric grammars for object recognition, (PhD thesis) (Tese). MASSACHUSETTS INSTITUTE OF TECHNOLOGY 
  2. ↑ Noam Chomsky: Syntactic Structures. Mouton & Co. Publishers, Den Haag, Netherlands, 1957
  3. ↑ Klein, Daniel; Manning, Christopher (2003). «Accurate Unlexicalized Parsing» (PDF). Proceedings of the 41st Meeting of the Association for Computational Linguistics: 423–430. 
  4. ↑ Beutler, R; Kaufman, T; Pfister, B. (2005). «Integrating a non-probabilistic grammar into large vocabulary continuous speech recognition». IEEE Workshop on Automated Speech recognition and Understanding: 104–109 
  5. ↑ R. Durbin, S. Eddy, A. Krogh, G. Mitchinson, ed. (1998). Biological sequence analysis : probabilistic models of proteins and nucleic acids. [S.l.]: Cambridge University Press. ISBN 9780521629713  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.
  6. ↑ Eddy SR, Durbin R (junho de 1994). «RNA sequence analysis using covariance models». Nucleic Acids Res. 22 (11): 2079–88. PMC 308124Acessível livremente. PMID 8029015. doi:10.1093/nar/22.11.2079 
  7. ↑ Gold, E. (1967). «Language identification in the limit». Information and Control. 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5 
  8. ↑ Chomsky, N. (1980). Rules and representations. Oxford: Basil Blackwell 
  9. ↑ Clark, A. (2001). «Unsupervised Language Acquisition: Theory and Practice». arXiv:cs.CL/0212024Acessível livremente [cs.CL]  Parâmetros não válidos no arXiv (ajuda)
  10. ↑ Horning, J.J. (1969). A study of grammatical inference (Tese de Ph.D.). Computer Science Department, Stanford University 
  11. ↑ John Hale (2006). «Uncertainty About the Rest of the Sentence». Dept Linguistics, Michigan State University. Cognitive Science. 30 (4): 643–672. doi:10.1207/s15516709cog0000_64 

Leitura adicional[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Obtida de "https://pt.wikipedia.org/w/index.php?title=Gramática_livre_de_contexto_estocástica&oldid=60714888"