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[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
Définition
Une grammaire algébrique pondérée est composée
- d'un alphabet fini de symboles non terminaux ou variables
- d'un alphabet fini , disjoint de , de symboles terminaux ou lettres terminales
- d'un élément de appelé l'axiome
- d'un ensemble fini de règles de dérivations ou productions,
- et d'une fonction qui associe à chaque production un nombre réel positif.
Le nombre est le poids de la règle .
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 ,
- .
Score
Le score d'un arbre de dérivation est le nombre
où est le nombre d'occurrences de la règle dans l'arbre de dérivation . La fonction de partition est la somme des scores de tous les arbres de dérivation. Une grammaire est dite convergente si est fini. Dans ce cas, on peut utiliser comme constante de normalisation et définir une distribution de probabilité de Gibbs sur les arbres de dérivation par :
Grammaire probabiliste
Il est facile de voir que, pour une grammaire probabiliste, on a . Si , la grammaire est dite stricte ou propre.
Transformation d'une grammaire pondérée en grammaire probabiliste
Une construction de normalisation due à Chi[4] permet de transformer une grammaire pondérée convergente en une grammaire probabiliste. Pour cela, on note
- les arbres de dérivation dont la racine est ,
- (et pour une lettre terminale)
et on définit
où on a posé , avec chaque une lettre.
Chi a prouvé que la grammaire pondérée par 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[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.
Notes et références
Bibliographie
- [1969] : Arto Salomaa, « Probabilistic and Weighted Grammars », Information and Control, vol. 15, , p. 529-544.
- [1997] : Zhiyi Chi, « Statistical properties of probabilistic context-free grammars », Computational Linguistics, vol. 25, no 1, , p. 131–160 (lire en ligne)
- [2005] : Mark Johnson, « Weighted Context Free Grammars and proper PCFGs », — 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, no 4, , 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 » (no 5015), (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 », , 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, (consulté le ).
- [2021] : Agnishom Chattopadhyay, Filip Mazowiecki, Anca Muscholl et Cristian Riveros, « Pumping lemmas for weighted automata », Logical Methods in Computer Science, vol. 17, no 3, , 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, , article no 114112 (DOI 10.1016/j.tcs.2023.114112)
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
Portail de l'informatique théorique