Modèle de Markov caché

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir MMC.

Un modèle de Markov caché (MMC) — en anglais Hidden Markov Models (HMM) (ou plus correctement, mais non employé automate de Markov à états cachés) est un modèle statistique dans lequel le système modélisé est supposé être un processus markovien de paramètres inconnus.

Les modèles de Markov cachés sont massivement utilisés notamment en reconnaissance de formes, en intelligence artificielle ou encore en traitement automatique du langage naturel.

Modèle du sac en papier[modifier | modifier le code]

Le jeu des sacs en papier[modifier | modifier le code]

Imaginons un jeu simple, avec des sacs en papier (opaques) 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 | modifier le code]

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

Dans chaque sac nous plaçons un certain nombre de jetons a et un certain nombre de jetons b : dans cet exemple, 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és 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 parties, nous sommes susceptibles 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 :

Exemple-markov-sac-papier.png

Le jeu des sacs en papier cachés[modifier | modifier le code]

Nous reprenons en partie le modèle précédent mais introduisons de nouveaux types de sacs.

  • Des sacs pour savoir dans quel sac effectuer le prochain tirage ;
  • Des sacs de sortie pour générer la séquence ;

À partir de la séquence générée, il sera généralement impossible de déterminer quels tirages ont conduit à quelle séquence, la séquence de tirage dans les sacs donnant les transitions est inconnue, c'est pourquoi on parle de sacs en papier cachés.

Exemple[modifier | modifier le code]

Repartons de l'exemple précédent. Nous conservons les sacs A et B, qui donnent les transitions, et ajoutons deux sacs A' et B' (contenant des jetons j et k ), situés juste à côté.

  • A' contient quatre jetons j et un jeton k ;
  • B' contient un jeton j et quatre jetons k.

Le jeu est le suivant :

  • On part du groupe de sacs ( A et A' ) , on tire un jeton dans le sac A' , on consigne sa valeur ( j ou k ) et on le replace dans le sac ;
  • On tire un jeton dans le sac A pour savoir dans quel groupe de sacs se feront les prochains tirages, on le replace ;
  • Si le jeton sortant du sac A est un 'a' alors les prochains tirages se feront dans le groupe de sac ( A et A' ), si c'est un 'b', il se fera dans le groupe de sac ( B et B' ) ;
  • On recommence ces opérations autant de fois que le joueur le souhaite.

À chaque étape, on tire donc un jeton dans chaque sac d'un même groupe, à savoir A et A' ou B et B', ce qui permet d'avoir une valeur ( j ou k ) qui n'indique pas directement la transition.

Le jeu génère deux séquences :

  • La séquence de sortie, connue, le résultat du jeu (ce sont les valeurs j ou k contenues dans les sacs A' et B' );
  • La séquence des transitions, inconnue (ce sont les valeurs a et b contenues dans les sacs A et B ).

Pour cet exemple, nous avons pu générer les séquences suivantes :

Séquence de transition A B A B A B B A A A B A A B A B A B A B
Séquences de sortie j j k k j k k j k j j j j k k j k k j k

On observe que des séquences de transitions identiques peuvent donner des sorties différentes, et vice-versa.

Ce jeu peut-être modélisé par un Automate de Markov à états cachés : les groupes de sacs sont les états, les tirages donnant le groupe de tirages suivant sont les transitions (avec la probabilité associée en fonction de la proportion des jetons dans les sacs A ou B), les sacs de sortie donnent les valeurs de sortie de l'automate (avec la probabilité associée en fonction de la proportion des jetons dans les sacs A' ou B').

Le jeu précédent correspond donc à l'automate de Markov à états cachés suivant :

Exemple-markov-sac-papier-cache.png

Les flèches en pointillés indiquent les sorties probables à chaque passage dans un état.

Formalisme[modifier | modifier le code]

Un automate de Markov à états cachés est un quadruplet \{ S, \Pi, A, B \} des ensembles décrits suivant :

  • S_i l'état i ;
  • \pi_i la probabilité que Si soit l'état initial ;
  • a_{ij} la probabilité de la transition S_i \rightarrow S_j ;
  • b_i(k) la probabilité d'émettre le symbole k étant dans l'état Si ;

sous contrainte :

  • \sum_{i} \pi_i = 1 la somme des probabilités des états initiaux est égale à 1 ;
  • \forall i, \sum_{j} a_{ij} = 1 la somme des probabilités des transitions partant d'un état est égale à 1 ;
  • \forall i, \sum_{k} b_{i}(k) = 1 la somme des probabilités des émissions partant d'un état est égale à 1.

Utilisation[modifier | modifier le code]

Il y a trois exemples typiques de problèmes que l'on peut chercher à résoudre avec un HMM :

  • Connaissant l'automate, calculer la probabilité d'une séquence particulière (se résout à l'aide de l'algorithme Forward)
  • Connaissant l'automate, trouver la séquence la plus probable d'état (caché) ayant conduit à la génération d'une séquence de sortie donnée (se résout avec l'algorithme de Viterbi).
  • Étant donné une séquence de sortie, retrouver l'ensemble d'états le plus probable et les probabilités des sorties sur chaque état. Se résout avec l'algorithme de Baum-Welch, appelé aussi algorithme forward-backward.

Applications[modifier | modifier le code]

Histoire[modifier | modifier le code]

Les HMM ont été décrits pour la première fois dans une série de publication de statistiques par Leonard E. Baum et d'autres auteurs après 1965.

Ils ont été appliqués dès la fin des années 1970 à la reconnaissance vocale [1]. Dans la seconde moitié des années 1980, les HMM ont commencé à être appliqués à l'analyse de séquences biologique, en particulier l'ADN [2]. Les réseaux bayésiens dynamiques introduits au tout début des années 1990 généralisent le principe des HMM.

Apprentissage des HMM[modifier | modifier le code]

Il existe plusieurs algorithmes pour réaliser l'apprentissage des paramètres d'un HMM. On peut citer notamment :

Référence[modifier | modifier le code]

  1. Lawrence R. Rabiner, « A tutorial on Hidden Markov Models and selected applications in speech recognition », Proceedings of the IEEE, vol. 77, no 2,‎ février 1989, p. 257–286 (DOI 10.1109/5.18626, lire en ligne) [1]
  2. M Bishop et Thompson E, « Maximum likelihood alignment of DNA sequences », J Mol Biol, vol. 190, no 2,‎ 20 juillet 1986, p. 159–65 (PMID 3641921, DOI 10.1016/0022-2836(86)90289-5)

Voir aussi[modifier | modifier le code]