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
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. O algoritmo é análogo ao utilizado pelos Modelo oculto de Markov.
Aplicações
Processamento de Linguagem Natural
Gramáticas livre-de-contexto foram originalmente concebidas em uma tentativa de modelar linguagens naturais, ou seja, aquelas normalmente falada pelos humanos. 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, 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.
RNA
Gramáticas livre-de-contexto são ápteis a modelar a segunda estrutura do RNA. 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
Com a publicação do Teorema de Gold 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 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.
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.
Ver também
Leitura adicional
-
Rivas E, Eddy SR (2001). «Noncoding RNA gene detection using comparative sequence analysis». BMC Bioinformatics. 2. 8 páginas. PMC 64605
. PMID 11801179. doi:10.1186/1471-2105-2-8
