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 modifier

Le poids d'une dérivation ou d'un arbre de dérivation est le produit^[1] (dans le modèle multiplicatif) ou la somme^[2] (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^[3]^,^[4]).

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 modifier

Définition modifier

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^[5]) 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 modifier

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 modifier

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 modifier

Une construction de normalisation due à Chi^[4] 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 modifier

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

Note historique modifier

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^[6]. 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 modifier

[1969] : Arto Salomaa, « Probabilistic and Weighted Grammars », Information and Control, vol. 15,‎ 1969, p. 529-544.

[1997] : Zhiyi Chi, « Statistical properties of probabilistic context-free grammars », Computational Linguistics, vol. 25, n^o 1,‎ 1999, p. 131–160 (lire en ligne)

[2005] : Mark Johnson, « Weighted Context Free Grammars and proper PCFGs », 2005 — Notes d'une présentation.

[2007] : 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)

[2008] : 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.

[2009] : Manfred Droste, Werner Kuich et Heiko Vogler (éditeurs), Handbook of weighted automata, Springer-Verlag, coll. « Monographs in theoretical computer science », 2009, xvii + 608 (ISBN 978-3-642-01492-5, présentation en ligne)

[2011] : 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).

[2021] : Agnishom Chattopadhyay, Filip Mazowiecki, Anca Muscholl et Cristian Riveros, « Pumping lemmas for weighted automata », Logical Methods in Computer Science, vol. 17, n^o 3,‎ 21 juillet 2021, p. 7:1–7:21 (DOI 10.46298/lmcs-17(3:7)2021, lire en ligne)

[2023] : Yusuke Inoue, Kenji Hashimoto et Hiroyuki Seki, « An ambiguity hierarchy of weighted context-free grammars », Theoretical Computer Science, vol. 974,‎ 29 septembre 2023, article n^o 114112 (DOI 10.1016/j.tcs.2023.114112)

Articles liés modifier

Portail de l'informatique théorique

[same-1] Smith et Johnson 2007.

[add-2] Katsirelos, Narodytska et Walsh 2008.

[logLinear-3] Johnson 2005.

[Chi-4] {a et b} Chi 1999.

[5] Giegerich.

[6] Salomaa 1969.

[1]

[2]

[3]

[4]

[5]

[6]