Automate probabiliste

En mathématiques et en informatique théorique, et notamment en théorie des automates, un automate probabiliste est une généralisation des automates finis non déterministes; chaque transition de l'automate est équipée d'une probabilité (un nombre réel entre 0 et 1). Les transitions sont représentées de manière compacte par des matrices qui sont des matrices stochastiques. Les langages reconnus par les automates probabilistes sont appelés langages stochastiques; ils comprennent, et étendent, la famille des langages rationnels. En particulier, le nombre de langages stochastiques est non dénombrable (alors que celui des langages rationnels est dénombrables).

Le concept d'automate probabiliste a été introduit par Michael O. Rabin en 1963. Une extension conduit aux automates quantiques.

Définition

Un automate probabiliste est formé d'un automate fini non déterministe, où de plus chaque transition est équipée d'une probabilité, c'est-à-dire d'un nombre réel entre 0 et 1 vérifiant une certaine condition de cohérence.

Comme pour une automate fini (non déterministe) usuel, une automate probabiliste sur un alphabet $A$ est composé des données suivantes :

• un ensemble fini d'états, noté $Q$ ;
• un état initial $i$, élément de $Q$ ;
• un ensemble $T$ d'états terminaux ou finals ;
• un ensemble ${\mathcal {F}}\subset Q\times A\times Q$ de transitions.

De plus, chaque transition $(p,a,q)$ de ${\mathcal {F}}$ porte un nombre réel positif $\pi (p,a,q)$, appelé sa probabilité, avec la condition que, pour chaque état $p$ et chaque lettre $a$, la somme des $\pi (p,a,q)$, pour $(p,a,q)$ dans ${\mathcal {F}}$, est égal à 1.

Cette condition s'exprime plus simplement en posant $\pi (p,a,q)=0$ si $(p,a,q)$ n'est pas une transition. Alors elle revient à :

$\sum _{q\in Q}\pi (p,a,q)=1$,

pour tout état $p$ et toute lettre $a$.

On définit une $Q\times Q$-matrice $P(a)$ pour chaque lettre $a$, par

$P(a)_{p,q}=\pi (p,a,q)$

La condition sur la distribution des probabilités s'exprime alors par la condition que les matrices P(a) sont de matrices stochastiques.

On étend la fonction $\pi$ aux mots comme suit: Soit $w$ un mot, et soit $p{\xrightarrow {w}}q$ un chemin de $p$ à $q$ d'étiquette $w$. La probabilité de ce chemin est le produit des probabilités des transitions qui le composent. La probabilité $\pi (p,w,q)$ est défini comme la somme des probabilités des chemins $p{\xrightarrow {w}}q$ de $p$ à $q$ d'étiquette $w$. Cette définition s'exprime matriciellement comme suit: on pose $w=a_{1}a_{2}\cdots a_{n}$, et on définit la $Q\times Q$-matrice $P(w)$ comme le produit des matrices $P(a_{1}),P(a_{2}),\ldots ,P(a_{n})$ :

$P(w)=P(a_{1})P(a_{2})\cdots P(a_{n})$.

Alors on a

$P(w)_{p,q}=\pi (p,w,q)$.

La probabilité d’acceptation d'un mot $w$ dans l'automate probabiliste ${\mathcal {A}}$ est la somme des probabilités $\pi (i,w,t)$, où $i$ est l'état initial et où$t$ parcourt les états terminaux. On la note $\pi _{\mathcal {A}}(w)$. Cette valeur aussi s'exprime matriciellement. C'est le nombre

$\pi _{\mathcal {A}}(w)=\lambda P(w)\gamma$,

où $\lambda$ est le $Q$-vecteur ligne dont toutes les coordonnées sont nulles sauf celle d'indice $i$ qui vaut 1, et où $\gamma$ est le $Q$-vecteur colonne dont les coordonnées sont nulles sauf celles dont l'indice est dans $T$, et qui valent 1.

Exemple

Un automate probabiliste. L'état 1 est initial, l'état 4 est final. Les probabilités sont indiquées à côté des étiquettes. L'absence signifie probabilité 1.

Pour l'exemple de droite d'un automate à quatre états, les matrices $P(a)$ et $P(b)$ et les vecteurs $\lambda$ et $\gamma$ sont:

$\lambda =(1,0,0,0)\qquad P(a)={\begin{pmatrix}0&{\tfrac {3}{4}}&{\tfrac {1}{4}}&0\\0&1&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&0\\0&0&0&1\end{pmatrix}}\qquad P(b)={\begin{pmatrix}1&0&0&0\\0&0&{\tfrac {1}{2}}&{\tfrac {1}{2}}\\0&0&0&1\\0&0&0&1\end{pmatrix}}\qquad \gamma ={\begin{pmatrix}0\\0\\1\\0\end{pmatrix}}$

On a par exemple : $\lambda P(a)P(b)=(0,0,{\tfrac {3}{8}},{\tfrac {5}{8}})$, et la probabilité d'acceptation de $ab$ est donc $\lambda P(a)P(b)\gamma =3/8$.

Langage stochastique

Seuil d'acceptation

Soit $\eta$ un nombre avec $0\leq \eta <1$. Le langage accepté par l'automate probabiliste ${\mathcal {A}}$ avec seuil $\eta$ est l'ensemble des mots dont la probabilité d'acceptation est supérieure à $\eta$. C'est l'ensemble $L({\mathcal {A}},\eta )$ défini par

$L({\mathcal {A}},\eta )=\{w\in A^{*}\mid \lambda P(w)\gamma >\eta \}$

Le nombre $\eta$ est aussi appelé point de coupure (cut point en anglais).

Langage stochastique

Un langage stochastique est un langage de la forme $L({\mathcal {A}},\eta )$, pour un automate probabiliste ${\mathcal {A}}$ et une valeur de seuil $\eta$. Dans l'exemple ci-dessus, les mots du langage $b^{*}a$ ont tous probabilité ${\tfrac {1}{2}}$, les mots du langage $b^{*}aa^{*}b$ ont tous probabilité ${\tfrac {3}{8}}$. Le langage accepté avec seuil ${\tfrac {1}{4}}$ est la réunion de ces langages. Les langages rationnels sont tous des langages stochastiques.

Seuil isolé

Un seuil ou point de coupure est isolé s'il existe un nombre réel $\delta >0$ tel que

$\left|\pi _{\mathcal {A}}(w)-\eta \right|\geq \delta$

pour tout mot $w$. Dans l'exemple ci-contre, il n'existe pas de mot accepté avec une probabilité comprise strictement plus grande que 1/2, donc tout nombre strictement plus grand est isolé. Un langage stochastique est isolé si son point de coupure est isolé.

Propriétés

Propriétés d'expressivité

Tous les langages rationnels sont stochastiques et certaines restrictions des langages stochastiques sont rationnelles :

• Tout langage stochastique dont le seuil est 0 est rationnel.
• Tout langage stochastique isolé est rationnel.

Mais on n'a pas l'égalité comme le montre l'exemple suivant.

Exemple d'un langage stochastique qui n'est pas rationnel

Considérons l'automate à deux états sur l'alphabet binaire donné par les matrices :

$\lambda =(1,0)\qquad P(0)={\begin{pmatrix}1&0\\{\tfrac {1}{2}}&{\tfrac {1}{2}}\end{pmatrix}}\qquad P(1)={\begin{pmatrix}{\tfrac {1}{2}}&{\tfrac {1}{2}}\\0&1\end{pmatrix}}\qquad \gamma ={\begin{pmatrix}0\\1\end{pmatrix}}$

Pour un mot binaire $w=b_{1}b_{2}\cdots b_{n}$, le coefficient $P(w)_{1,2}$ de la matrice $P(w)$ est égal à

$P(w)_{1,2}=\sum _{j=1}^{n}b_{j}2^{n+1-j}$;

c'est le nombre rationnel dont $0,b_{n}b_{n-1}\cdots b_{1}$ est l'écriture binaire. Pour une valeur de seuil $\eta$, le langage $L({\mathcal {A}},\eta )$ accepté par cet automate est donc l'ensemble des mots représentant l'écriture binaire retournée de nombre plus grand que $\eta$. Il est clair que si $\eta <\eta '$, alors $L({\mathcal {A}},\eta )\subset L({\mathcal {A}},\eta ')$ et que l'inclusion est stricte. Il en résulte qu'il existe un nombre non dénombrable de langages de la forme $L({\mathcal {A}},\eta )$ pour cet automate; comme le nombre de langages rationnels est dénombrable, cela implique l'existence de langages stochastiques non rationnels (même s'ils ne sont pas montrés constructivement par cet argument.

Questions décidables et indécidables

La plupart des questions sont indécidables. Ces questions peuvent également se formuler au moyen de l'image d'un automate probabiliste, défini comme l'ensemble $\Omega ({\mathcal {A}})=\{\pi _{\mathcal {A}}(w)\mid w\in A^{*}\}$.

• Le problème du vide, c'est-à-dire de savoir si le langage $L({\mathcal {A}},\eta )$ accepté est vide ou non, est indécidable pour $0<\eta <1$. C'est le problème de savoir si $\Omega ({\mathcal {A}})$ contient une valeur supérieur à $\eta$.

• Le problème du seuil isolé, c'est-à-dire de savoir si un nombre $\eta$ est un seuil isolé pour une automate ${\mathcal {A}}$, est indécidable. C'est le problème de savoir s'il existe un intervalle ouvert centré autour de $\eta$ qui est disjoint de $\Omega ({\mathcal {A}})$.

• Le problème de l'existence d'un seuil isolé, c'est-à-dire de savoir s'il existe un nombre $\eta$ qui est un seuil isolé pour ${\mathcal {A}}$, est indécidable. C'est le problème de savoir si $\Omega ({\mathcal {A}})$ est dense dans l'intervalle $[0,1]$.

Généralisations

• On peut étendre la définition sans augmenter la puissance d'acceptation des automates probabilistes en remplaçant l'état initial par une distribution initiale, c'est-à-dire une valeur positive ou nulle $i(p)$ pour chaque état $p$, telle que $\sum _{p\in Q}i(p)=1$. De même, on peut doter l'automate d'une distribution terminale, donc remplacer l'ensemble des états terminaux par une fonction $\tau$, avec $\sum _{p\in Q}\tau (p)=1$.

• Un automate probabiliste est une forme particulière de représentation linéaire d'une série formelle rationnelle en variables non commutatives : c'est le cas particulier où les matrices sont stochastiques.

• Un modèle de Markov caché est très proche des automates probabilistes.

• Une généralisation géométrique conduit aux automates quantiques. Un état est représenté par un point dans un espace projectif complexe, les matrices forment un ensemble pris dans le groupe unitaire. Le point de coupure est vu comme une limite d'une valeur maximale de l'angle quantique^{[réf. souhaitée]}.

Notes et références

Bibliographie

• Michael O. Rabin, « Probabilistic Automata », Information and Control, vol. 6,‎ 1963, p. 230-245
• Azaria Paz, Introduction to probabilistic automata, Academic Press, coll. « Computer science and applied mathematics », 1971
• Arto Salomaa, Theory of Automata, Pergamon Press, 1969
• Vincent Blondel et Vincent Canterini, « Undecidable Problems for Probabilistic Automata of Fixed Dimension », Theory of Computing Systems, vol. 36, n^o 3,‎ 2008, p. 231-245 (lire en ligne)

Voir aussi

• Modèle de Markov caché
• Automate fini
• Théorie des automates
• Grammaire algébrique probabiliste
• Algorithme de Viterbi
• Programmation dynamique
• Bio-informatique
• Reconnaissance automatique de la parole