Gramática não contextual ponderada

Na teoria da linguagem , uma gramática algébrica ponderada ou gramática não contextual ponderada é uma gramática não contextual em que um peso numérico está associado a cada regra de produção. O interesse desta noção é poder distinguir as derivações de uma mesma palavra, portanto as interpretações de uma mesma expressão, segundo um peso que pode representar um significado mais provável ou mais frequente.

Descrição informal

O peso de uma derivação ou árvore de derivação é o produto (no modelo multiplicativo) ou a soma (no modelo aditivo) dos pesos das regras de produção utilizadas. Na avaliação do peso, cada regra é contada tantas vezes quanto aparece na derivação.

Uma gramática algébrica probabilística (também chamada de estocástica ) é o caso especial de gramáticas ponderadas onde os pesos são probabilidades (ou logaritmos de probabilidades).

Uma versão generalizada do algoritmo Cocke-Younger-Kasami pode ser usada para calcular a derivação mais leve (ou mais pesada) de uma palavra em uma gramática.

Propriedades formais

Definição

Uma gramática algébrica ponderada é composta $G$

de um alfabeto finito de símbolos não terminais ou variáveis $V$
de um alfabeto finito , separado de , de símbolos terminais ou letras terminais $NO$ $V$
de um elemento de chamado de axioma $S$ $V$
um conjunto finito de regras ou produções , ${\ mathcal {P}} \ subset V \ times (V \ cup A) ^ {*}$
e uma função que associa um número real positivo a cada produção . ${\ displaystyle p: {\ mathcal {P}} \ to \ mathbb {R} _ {+}}$ $X \ to \ alpha$

O número é o peso da régua . ${\ displaystyle p (X \ to \ alpha)}$ $X \ to \ alpha$

Uma gramática algébrica probablística (também dizemos estocástica ) é uma gramática ponderada em que os pesos satisfazem a seguinte condição adicional: para qualquer variável , $X$

{\ displaystyle \ sum _ {X \ to \ alpha \ in R} p (X \ to \ alpha) = 1}

Pontuação

A pontuação de uma árvore de derivação é o número $t$

{\ displaystyle s (t) = \ prod _ {{\ text {regras}} X \ to \ alpha} p (X \ to \ alpha) ^ {f (X \ to \ alpha, t)}}

onde é o número de ocorrências da regra na árvore de derivação . A função de partição é a soma das pontuações de todas as árvores de derivação. Uma gramática é considerada convergente se for finita. Neste caso, podemos usar como uma constante de normalização e definir uma distribuição de probabilidade de Gibbs nas árvores de derivação por: ${\ displaystyle f (X \ to \ alpha, t)}$ $X \ to \ alpha$ $t$ ${\ displaystyle Z (p)}$ ${\ displaystyle Z (p)}$ ${\ displaystyle Z (p)}$

{\ displaystyle P (t) = s (t) / Z (p)}

Gramática probabilística

É fácil ver que, para uma gramática probabilística, temos . Sim , a gramática é estrita ou limpa. ${\ displaystyle Z (p) \ leq 1}$ ${\ displaystyle Z (p) = 1}$

Transformação de uma gramática ponderada em uma gramática probabilística

Uma construção de normalização devido ao Chi torna possível transformar uma gramática ponderada convergente em uma gramática probabilística. Para isso, notamos

$T_ {X}$ as árvores de derivação cuja raiz é , $X$
${\ displaystyle Z_ {X} = \ sum _ {t \ in T_ {X}} s (t)}$ (e para uma carta terminal) ${\ displaystyle Z_ {a} = 1}$

e nós definimos

{\ displaystyle p '(X \ to \ alpha) = {\ frac {p (X \ to \ alpha)} {Z_ {X}}} \ prod _ {i = 1} ^ {k} Z _ {\ alpha _ {i}}}

onde colocamos , com cada uma letra. ${\ displaystyle \ alpha = \ alpha _ {1} \ cdots \ alpha _ {k}}$ $\ alpha_i$

Chi provou que a gramática ponderada por é uma gramática probabilística adequada. $p '$

Formulários

Existem muitas aplicações em linguística , aprendizado de máquina e modelagem de RNA .

Nota Histórica

Antes que o interesse pelas gramáticas ponderadas fosse retomado no contexto da linguística, e ainda mais recentemente na análise de sequências biológicas, uma versão das gramáticas ponderadas e probabilísticas foi desenvolvida, em analogia com os autômatos probabilísticos . Um dos primeiros artigos nesse sentido é o de Arto Salomaa . As restrições impostas neste artigo são mais fortes: duas derivações podem ter um peso diferente, mesmo se corresponderem à mesma árvore de derivadas.

Bibliografia

Noah A. Smith e Mark Johnson , " Weighted and Probabilistic Context-Free Grammars Are Equally Expressive " , Computational Linguistics , vol. 33, n o 4,2007, p. 477 ( DOI 10.1162 / coli.2007.33.4.477 , ler online )
George Katsirelos, Nina Narodytska e Toby Walsh, “The Weighted Cfg Constraint” , em Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems , col. "Lecture Notes in Computer Science" ( n o 5015)2008( ISBN 978-3-540-68154-0 , DOI 10.1007 / 978-3-540-68155-7_31 , ler online ) , p. 323-327.
Mark Johnson , " Weighted Context Free Grammars and proper PCFGs " ,2005 - Notas de uma apresentação.
Zhiyi Chi , “ propriedades estatísticas de gramáticas probabilísticas livres de contexto ”, Computational Linguistics , vol. 25, n o 1,1999, p. 131-160 ( leia online )
Arto Salomaa, “ Probabilistic and Weighted Grammars ”, Information and Control , vol. 15,1969, p. 529-544.
Robert Giegerich, " Introdução às Gramáticas Livres de Contexto Estocástico " , Faculdade de Tecnologia e Centro de Biotecnologia, Universidade de Bielefeld, Bielefeld, Alemanha,8 de junho de 2011(acessado em 29 de dezembro de 2015 ) .