Grammaire non contextuelle pondérée

En théorie des langages, une grammaire algébrique pondérée ou grammaire non contextuelle pondérée est une grammaire non contextuelle où un poids numérique est associé à chaque règle de production. L'intérêt de cette notion est de pouvoir distinguer les dérivations d'un même mot, donc les interprétations d'une même expression, en fonction d'un poids qui peut représenter un sens plus vraisemblable ou plus fréquent.

Description informelle

Le poids d'une dérivation ou d'un arbre de dérivation est le produit (dans le modèle multiplicatif) ou la somme (dans le modèle additif) des poids des règles de production utilisées. Dans l'évaluation du poids, chaque règle est comptée autant de fois qu'elle figure dans la dérivation.

Une grammaire algébrique probabiliste (aussi appelée stochastique) est le cas particulier des grammaires pondérées où les poids sont des probabilités (ou des logarithmes de probabilités).

Une version généralisée de l'algorithme de Cocke-Younger-Kasami peut être utilisée pour calculer la dérivation la plus légère (ou la plus lourde) pour un mot dans une grammaire.

Propriétés formelles

Définition

Une grammaire algébrique pondérée $G$ est composée

• d'un alphabet fini $V$ de symboles non terminaux ou variables
• d'un alphabet fini $A$, disjoint de $V$, de symboles terminaux ou lettres terminales
• d'un élément $S$ de $V$ appelé l'axiome
• d'un ensemble fini ${\mathcal {P}}\subset V\times (V\cup A)^{*}$de règles de dérivations ou productions,
• et d'une fonction $p:{\mathcal {P}}\to \mathbb {R} _{+}$ qui associe à chaque production $X\to \alpha$ un nombre réel positif.

Le nombre $p(X\to \alpha )$ est le poids de la règle $X\to \alpha$.

Une grammaire algébrique probabliste (on dit aussi stochastique) est une grammaire pondérée où les poids vérifient la condition supplémentaire suivante : pour toute variable $X$,

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

Score

Le score d'un arbre de dérivation $t$ est le nombre

$s(t)=\prod _{{\text{règles }}X\to \alpha }p(X\to \alpha )^{f(X\to \alpha ,t)}$

où $f(X\to \alpha ,t)$ est le nombre d'occurrences de la règle $X\to \alpha$ dans l'arbre de dérivation $t$. La fonction de partition $Z(p)$ est la somme des scores de tous les arbres de dérivation. Une grammaire est dite convergente si $Z(p)$ est fini. Dans ce cas, on peut utiliser $Z(p)$ comme constante de normalisation et définir une distribution de probabilité de Gibbs sur les arbres de dérivation par :

$P(t)=s(t)/Z(p)$

Grammaire probabiliste

Il est facile de voir que, pour une grammaire probabiliste, on a $Z(p)\leq 1$. Si $Z(p)=1$, la grammaire est dite stricte ou propre.

Transformation d'une grammaire pondérée en grammaire probabiliste

Une construction de normalisation due à Chi permet de transformer une grammaire pondérée convergente en une grammaire probabiliste. Pour cela, on note

• $T_{X}$ les arbres de dérivation dont la racine est $X$,
• $Z_{X}=\sum _{t\in T_{X}}s(t)$ (et $Z_{a}=1$ pour une lettre terminale)

et on définit

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

où on a posé $\alpha =\alpha _{1}\cdots \alpha _{k}$, avec chaque $\alpha _{i}$ une lettre.

Chi a prouvé que la grammaire pondérée par $p'$ est une grammaire probabiliste propre.

Applications

Les applications sont nombreuses en linguistique, apprentissage automatique et en modélisation des ARN.

Note historique

Avant que l'intérêt pour les grammaires pondérées ne reprenne dans le cadre de la linguistique, et même plus récemment encore dans l'analyse des séquences biologiques, une version des grammaires pondérées et probabilistes a été développée, en analogie avec les automates probabilistes. Un des premiers articles dans cette direction est celui d'Arto Salomaa. Les contraintes imposées dans cet article sont plus fortes : deux dérivations peuvent avoir un poids différent même si elles correspondent à un même arbre de dérivation.

Bibliographie

• Noah A. Smith et 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, lire en ligne)
• George Katsirelos, Nina Narodytska et Toby Walsh, « The Weighted Cfg Constraint », dans Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, coll. « Lecture Notes in Computer Science » (n^o 5015), 2008 (ISBN 978-3-540-68154-0, DOI 10.1007/978-3-540-68155-7_31, lire en ligne), p. 323-327.
• Mark Johnson, « Weighted Context Free Grammars and proper PCFGs », 2005 — Notes d'une présentation.
• Zhiyi Chi, « Statistical properties of probabilistic context-free grammars », Computational Linguistics, vol. 25, n^o 1,‎ 1999, p. 131–160 (lire en ligne)
• Arto Salomaa, « Probabilistic and Weighted Grammars », Information and Control, vol. 15,‎ 1969, p. 529-544.
• Robert Giegerich, « Introduction to Stochastic Context Free Grammars », Faculty of Technology and Center of Biotechnology, Bielefeld University, Bielefeld, Germany, 8 juin 2011 (consulté le 29 décembre 2015).

Articles liés

• Automate probabiliste
• Automate pondéré
• Modèle de Markov caché
• Algorithme de Cocke-Younger-Kasami
• Algorithme de Viterbi
• Programmation dynamique
• Bio-informatique
• Reconnaissance automatique de la parole