eBabylone
.com

voir homonymes|MMC ébauche|informatique Un modèle de Markov caché' (MMC) -- en anglais ''Hidden Markov Models'' (HMM) (ou plus correctement, mais moins 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

Le jeu des sacs en papier

Imaginons un jeu simple, avec des sacs 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

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''. 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 :

Le jeu des sacs en papier cachés

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, ce pourquoi on parle de sacs en papier cachés.

Exemple

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' , 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 sac A'', on tire un jeton dans le sac ''A', on consigne sa valeur et on le replace dans le sac ;
On tire un jeton dans le sac A pour savoir dans quel groupe de sac se feront les prochains tirages, on le replace ;
On recommence ces opérations autant de fois que le joueur le souhaite. Le jeu génère deux séquences :
La séquence de sortie, connue, le résultat du jeu ;
La séquence des transitions, inconnue. 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 sac'' sont les états, les tirages donnant le groupe de tirage suivant sont les '''transitions''' (avec la probabilité associé en fonction de la proportion des jetons dans le sac), les sac de sorties donnent les 'valeurs de sortie de l'automate (même remarque pour la probabilité). Le jeu précédent correspond donc à l'automate de Markov à états cachés suivant :

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

Formalisme

Un automate à état caché de Markov est un quadruplet $\backslash \{\; S,\; \backslash Pi,\; A,\; B\; \backslash \}$ des ensembles décrits suivant :
$S\_i$ l'état i ;
$\backslash pi\_i$ la probabilité que ''Sind|i soit l'état initial ;
$a\_$ la probabilité de la transition $S\_i\; \backslash rightarrow\; S\_j$ ;
$b\_i(k)$ la probabilité d'émettre le symbole k'' étant dans l'état ''Sind|i ; sous contrainte :
$\backslash sum\_\; \backslash pi\_i\; =\; 1$ la somme des probabilités des états initiaux est égale à 1 ;
$\backslash forall\; i,\; \backslash sum\_\; a\_\; =\; 1$ la somme des probabilités des transitions partant d'un état est égale à 1 ;
$\backslash forall\; i,\; \backslash sum\_\; b\_(k)\; =\; 1$ la somme des probabilités des émissions partant d'un état est égale à 1.

Utilisation

Il y a trois exemples typiques de problème que l'on peut chercher à résoudre avec un HMM :
connaissant l'automate, calculer la probabilité d'une séquence particulière (se résoud à l'aide de l'algorithme de Viterbi)
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 également 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ésoud avec l'algorithme de Baum-Welch, appelé aussi algorithme forward-backward.

Applications

reconnaissance de la parole
traitement automatique du langage naturel (traduction automatique, étiquetage de texte, reconstruction de texte bruités...) ;
reconnaissance de l'écriture manuscrite ;
Bio-informatique.

Histoire

Les HMM ont été décrits pour la première fois dans une série de publication de statistique 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. 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.

Apprentissage des HMM

en travaux Il existe plusieurs algorithmes pour réaliser l'apprentissage des HMM. On peut citer notamment:
Algorithme de Viterbi
Algorithme Forward-Backward, aussi nommé Algorithme de Baum-Welch.

Voir aussi

Andrei Markov (mathématicien)
Chaîne de Markov
Algorithme de Viterbi
N-gramme
Processus de décision markovien partiellement observable Catégorie:Intelligence artificielle Catégorie:Processus stochastique af:Verborge Markovmodel ca:Model ocult de Markov de:Verborgenes Markow-Modell en:Hidden Markov model es:Modelo oculto de Markov fi:Markovin piilomalli id:Model Markov tersembunyi it:Modello nascosto di Markov ja:????????? nl:Hidden Markov Model ru:??????? ?????????? ?????? sl:Skriti model Markova sv:Dold Markovmodell vi:Mô hình Markov ?n zh:???????Modèle de Markov caché882311