Grammaire non contextuelle pondérée

Une grammaire algébrique pondérée ${\displaystyle G}$ est composée

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

Le nombre ${\displaystyle p(X\to \alpha )}$ est le poids de la règle ${\displaystyle 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 ${\displaystyle X}$,

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

Le score d'un arbre de dérivation ${\displaystyle t}$ est le nombre

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

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

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

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

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

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

et on définit

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

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

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