Automate probabiliste

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Article principal : Théorie des automates.

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[1],[2],[3]. Une extension conduit aux automates quantiques (en).

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.

Définition[modifier | modifier le code]

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:

  • a ensemble fini d'états, noté Q;
  • un état initial i, élément de Q;
  • une ensmble 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 tout 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_1a_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,

\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[modifier | modifier le code]

Automate probabiliste.png

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&\tfrac34&\tfrac14&0\\0&1&0&0\\\tfrac12&\tfrac12&0&0\\0&0&0&1\end{pmatrix}\qquad
P(b)=\begin{pmatrix}1&0&0&0\\0&0&\tfrac12&\tfrac12\\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(ab)=(0, 0, \tfrac38 , \tfrac58 ), et la probabilité d'acceptation de ab est donc 3/8.

Langage stochastique[modifier | modifier le code]

Seuil d'acceptation[modifier | modifier le code]

Soit \eta un nombre avec 0\le \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[modifier | modifier le code]

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é \tfrac12, les mots du langage b^*aa^*b ont tous probabilité \tfrac38. Le langage accepté avec seuil \tfrac14 est la réunion de ces langages. Les langages rationnels sont tous des langages stochastiques.

Seuil isolé[modifier | modifier le code]

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|\ge\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[modifier | modifier le code]

Propriétés d'expressivité[modifier | modifier le code]

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[modifier | modifier le code]

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

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

Pour un mot binaire w=b_1b_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_j2^{n+1-j};

c'est le nombre rationnel dont 0,b_nb_{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[modifier | modifier le code]

La plupart des questions sont indécidables[4]. Ces question 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[modifier | modifier le code]

  • 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.

Notes et références[modifier | modifier le code]

  1. (Rabin, 1963)
  2. (Paz, 1971) est un livre dédié.
  3. Le chapitre 2 de (Salomaa, 1969) considère les automates probabilistes.
  4. Pour ces résultats en dimension fixe, voir (Blondel & Canterini, 2008).

Bibliographie[modifier | modifier le code]

  • 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, no 3,‎ 2008, p. 231-245 (lire en ligne)

Voir aussi[modifier | modifier le code]