Automate probabiliste

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 ${\displaystyle A}$ est composé des données suivantes :

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

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

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

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

pour tout état ${\displaystyle p}$ et toute lettre ${\displaystyle a}$.

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

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

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

Alors on a

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

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

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

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

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 ${\displaystyle P(a)}$ et ${\displaystyle P(b)}$ et les vecteurs ${\displaystyle \lambda }$ et ${\displaystyle \gamma }$ sont:

${\displaystyle \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 : ${\displaystyle \lambda P(a)P(b)=(0,0,{\tfrac {3}{8}},{\tfrac {5}{8}})}$, et la probabilité d'acceptation de ${\displaystyle ab}$ est donc ${\displaystyle \lambda P(a)P(b)\gamma =3/8}$.

• 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 ${\displaystyle i(p)}$ pour chaque état ${\displaystyle p}$, telle que ${\displaystyle \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 ${\displaystyle \tau }$, avec ${\displaystyle \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.