Les automates de Markov à états cachés (ou modèles de Markov à états cachés -- Hidden Markov Model -- HMM) sont massivement utilisé notamment en reconnaissance de formes, en intelligence artificielle ou encore en traitement automatique du langage naturel.

Le jeu des sacs en papier

modifier

Imaginons un jeu simple, avec des sac en papier (opaque) contenant des jetons numérotés.

À chaque tour du jeu nous tirons un jeton d'un sac et, en fonction du jeton, passons à un autre sac. Après chaque tour, le jeton est remis dans le sac, nous notons enfin la séquence des numéros tirés.

Exemple

modifier

Nous disposons de deux sac, appelé A et B, ainsi que d'un ensemble de jetons numérotés a et b.

Dans chaque sac nous plaçons un certains nombre de jetons a et un certains nombre de jeton b. Nous plaçons dans le sac A 19 jetons b et un seul jeton a. Dans le sac B nous plaçons 4 jetons a et un seul jeton b.

  • Nous commençons par piocher un jeton au hasard dans le sac A. Si l'on pioche un jeton a, on reste sur ce sac, si l'on pioche un jeton b, on passe au sac B. On note également quel jeton a été tiré et on le remet dans le sac.
  • On recommence cette étape avec le sac en cours, jusqu'à ce que le jeu s'arrête (au bon vouloir du joueur).

Nous avons les probabilité de passer à une station suivante :

Tirage suivant en A Tirage suivant en B
Station courante en A 0.05 0.95
Station courante en B 0.8 0.2

En jouant plusieurs partie, nous sommes susceptible d'obtenir les séquences suivantes :

  • a b a b a b a a b a
  • a b b a b a b a b a
  • a b b a b b a b a b
  • ...

Ce jeu peut-être modélisé par une chaîne de Markov: chaque sac représente un état, la valeur du jeton donne la transition, la proportion de jeton d'une valeur est la probabilité de la transition.

Notre exemple du jeu du sac en papier est équivalent à l'automate de Markov suivant :