Un automate probabiliste est un modèle de calcul qui introduit le hasard dans le fonctionnement d’un automate fini. Dans un automate ordinaire, chaque symbole lu détermine sans ambiguïté l’état suivant, selon des règles fixes. Dans un automate probabiliste, en revanche, le passage d’un état à un autre n’est plus certain: à chaque symbole lu, l’automate choisit son prochain état au hasard, selon des probabilités attribuées d’avance aux différentes transitions possibles. La lecture d’une même suite de symboles peut donc conduire à des parcours différents d’une fois sur l’autre. On ne dit plus alors qu’une suite est simplement acceptée ou rejetée, mais qu’elle l’est avec une certaine probabilité, et l’on fixe souvent un seuil au-delà duquel on considère qu’elle est reconnue. Le comportement de l’automate se décrit ainsi en termes de chances plutôt que de certitudes.
Ce modèle a été étudié dès le début des années 1960, notamment par le mathématicien Michael Rabin, dans le prolongement de la théorie des automates finis alors en plein essor. L’idée s’inscrivait dans un mouvement plus large visant à comprendre ce que le hasard apporte au calcul, mouvement dont relèvent aussi les algorithmes probabilistes. On découvrit que ces automates possèdent des propriétés subtiles: selon la manière dont on fixe le seuil d’acceptation, ils peuvent reconnaître exactement les mêmes motifs qu’un automate ordinaire, ou au contraire des ensembles bien plus riches et parfois impossibles à décrire par des moyens classiques, ce qui en fait un objet théorique d’une profondeur inattendue.
Les automates probabilistes et les modèles très proches qui en dérivent trouvent aujourd’hui de nombreuses applications, en particulier partout où l’on doit raisonner sur des phénomènes incertains. Ils sont étroitement apparentés aux chaînes de Markov et aux modèles de Markov cachés, largement utilisés en reconnaissance de la parole, en traitement automatique des langues, en bio-informatique pour analyser des séquences génétiques, ou encore dans la modélisation de systèmes soumis à des pannes aléatoires. Ils servent aussi de fondement à la vérification dite probabiliste, qui cherche à estimer la probabilité qu’un système se comporte correctement plutôt que de l’affirmer avec une certitude absolue. Le hasard, intégré au cœur de l’automate, devient ainsi un outil pour décrire et maîtriser un monde qui n’est lui-même jamais tout à fait prévisible.
Laisser un commentaire