Voir la source de Modèle de Markov caché

{{voir homonymes|MMC<!--|HMM-->}}{{Infobox Méthode scientifique
| image = 
| légende = 
}}Un '''modèle de Markov caché''' ('''MMC''', terme et définition normalisés par l’ISO/CÉI [ISO/IEC 2382-29:1999]) —{{En anglais|hidden Markov model}} (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 [[Chaîne de Markov|processus markovien]] de paramètres inconnus.

Contrairement à une [[chaîne de Markov]] classique, où les transitions prises sont inconnues de l'utilisateur, mais où les états d'une exécution sont connus, dans un modèle de Markov caché, les états d'une exécution sont inconnus de l'utilisateur. Seuls, certains paramètres, comme la température, etc. sont connus de l'utilisateur.

Les modèles de Markov cachés sont massivement utilisés, notamment en [[reconnaissance de formes]], en [[intelligence artificielle]] ou encore en [[Traitement automatique des langues|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 (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.

Enfin, nous notons 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'' : 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 :

{| class="wikitable"
|
! 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 :

[[Image:Exemple-markov-sac-papier.png|500px|center]]

=== 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, c'est 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'<nowiki/>'' 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 :

{| class="wikitable"
|-
! 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 :

[[Image:Exemple-markov-sac-papier-cache.png|500px|center]]

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

=== Définition formelle d'un Modèle de Markov Caché (MMC) <ref>{{article|nom=Rabiner|prénom=L.|nom2=Juang|prénom2=B.|date=1986|titre=An introduction to hidden Markov models|url=http://dx.doi.org/10.1109/massp.1986.1165342|journal=IEEE ASSP Magazine|volume=3|numéro=1|pages=4–16|doi=10.1109/massp.1986.1165342|issn=0740-7467}}</ref> ===

Formellement, un MMC est défini par :

<math>\mathit{S} = \{\mathit{s_1},\ldots,\mathit{s_N}\}</math> l'ensemble discret des <math>\mathit{N}</math> états du modèle; on désigne un état au temps <math>\mathit{t}</math> par <math>\mathit{q_t} \in \mathit{S}</math>.

<math>\mathit{V} = \{\mathit{v_1,\ldots,v_M}\}</math> l'ensemble discret des <math>\mathit{M}</math> symboles observables; on désigne un symbole au temps <math>\mathit{t}</math> par <math>\mathit{o_t} \in \mathit{V}</math>.

<math>\mathit{\pi} = \{\mathit{\pi_1,\ldots,\pi_N}\}</math> la probabilité de commencer dans l'état <math>\mathit{i}\ \ (1\ \leq \mathit{i}\ \leq\ \mathit{N})</math>.

<math>\mathit{A} = \{\mathit{a_{ij}}\}_{1 \leq \mathit{i,j} \leq \mathit{N}}</math>, où <math>\mathit{a_{ij}} = \mathit{P}(\mathit{q_{t+1} = \mathit{s_j}\ |\ \mathit{q_t} = \mathit{s_i}})</math> pour les modèles d'ordre <math>1</math>; <math>\mathit{A}</math> est la matrice des probabilités de transitions entre états.

<math>\mathit{B} = \{\mathit{b_j}(\mathit{k})\}_{1 \leq \mathit{j} \leq \mathit{N}, 1 \leq \mathit{k} \leq \mathit{M}}</math>, où <math>\mathit{b}_{\mathit{j}(\mathit{k})} = \mathit{P}(\mathit{o_t}=\mathit{v_k}\ |\ \mathit{q_t} = \mathit{s_j})</math>; <math>\mathit{B}</math> est la matrice des probabilités d'observation dans les états.

Habituellement, on désigne un MMC par le triplet <math>\{A, B, \pi\}</math>.



Les contraintes classiques d'un MMC sont<ref name=":0">{{article|auteur=[[Lawrence Rabiner|Lawrence R. Rabiner]]|titre=A tutorial on Hidden Markov Models and selected applications in speech recognition|journal=Proceedings of the [[IEEE]]|volume=77|numéro=2|pages=257–286|date=février 1989|doi=10.1109/5.18626|url=http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf|format=pdf}} [http://www.cs.cornell.edu/courses/cs481/2004fa/rabiner.pdf].</ref> :

<math>\sum_{i} \pi_i = 1, \forall s_i \in S</math> : la somme des probabilités des états initiaux est égale à 1.

<math>\sum_{j=1}^N a_{{ij}} = 1, \forall s_i \in S</math> : la somme des probabilités des transitions partant d'un état est égale à 1.

<math>\sum_{k=1}^M b_j(k) = 1, \forall s_j \in S</math> : la somme des probabilités des observations d'un état est égale à 1.

=== Définition étendue d'un MMC : MMC à états spécifiques ===

Au début des années 2000, une définition étendue des MMC a été proposée<ref name="cchcifed00">{{article|auteur=[[Christophe Choisy, Abdel Belaïd]]|titre=Apprentissage croisé en reconnaissance analytique de l’écriture
manuscrite|journal= Colloque International Francophone sur l’Ecrit et le Document - CIFEd'00|date=2000|url=https://dumas.ccsd.cnrs.fr/LABO-LORIA-SET/inria-00099039}}</ref><math>^,</math><ref>{{article|auteur=[[Christophe Choisy, Abdel Belaïd]]|titre=Cross-learning in Analytic Word Recognition Without Segmentation|journal=International Journal on Document Analysis and Recognition|volume=4|numéro=4|pages=281-289|date=2002|doi=10.1007/s100320200078}}.</ref>. Elle ajoute deux états spécifiques <math>\mathit D</math> et <math>\mathit F</math> qui modélisent respectivement les transitions permettant de (D)ébuter dans un état et de (F)inir dans un état.

Formellement, un MMC à états spécifiques est défini par :

<math>\mathit{S} = \{\mathit{s_1},\ldots,\mathit{s_N},D,F\}</math> l'ensemble discret des <math>\mathit{N}</math> états du modèle plus les deux états spécifiques <math>\mathit D</math> et <math>\mathit F</math>; on désigne un état au temps <math>\mathit{t}</math> par <math>\mathit{q_t} \in \mathit{S}</math>.

<math>\mathit{V} = \{\mathit{v_1,\ldots,v_M}\}</math> l'ensemble discret des <math>\mathit{M}</math> symboles observables; on désigne un symbole au temps <math>\mathit{t}</math> par <math>\mathit{o_t} \in \mathit{V}</math>.

<math>\mathit{A} = \{\mathit{a_{ij}} \cup \{a_{Di,i \neq D,F},a_{iF,i \neq D,F}\}\}_{1 \leq \mathit{i,j} \leq \mathit{N}}</math>, où <math>\mathit{a_{ij}} = \mathit{P}(\mathit{q_{t+1} = \mathit{s_j}\ |\ \mathit{q_t} = \mathit{s_i}})_{i,j \neq D,F}</math>, <math>\mathit{a_{Di,i \neq D,F}} = \mathit{P}(\mathit{q_1 = \mathit{s_i}\ |\ \mathit D})</math>, <math>\mathit{a_{iF,i \neq D,F}} = \mathit{P}(\mathit{\mathit F\ |\ q_T = \mathit{s_i}})</math> pour les modèles d'ordre <math>1</math>; <math>\mathit{A}</math> est la matrice des probabilités de transitions entre états.

<math>\mathit{B} = \{\mathit{b_j}(\mathit{k})\}_{1 \leq \mathit{j} \leq \mathit{N}, 1 \leq \mathit{k} \leq \mathit{M}}</math>, où <math>\mathit{b}_{\mathit{j}(\mathit{k})} = \mathit{P}(\mathit{o_t}=\mathit{v_k}\ |\ \mathit{q_t} = \mathit{s_{j,j \neq D,F}})</math>; <math>\mathit{B}</math> est la matrice des probabilités d'observation dans les états; Les états spécifiques <math>\mathit D</math> et <math>\mathit F</math> n'ont pas de probabilité d'observation.

On désigne un MMC à états spécifiques par le couple <math>\{A, B\}</math>.



Les contraintes d'un MMC à états spécifiques sont :

<math>\sum_{j=1}^N a_{{ij}} = 1,\ \forall {i,j} \in S,\ {i \neq F,j \neq D}</math>.

<math>\sum_{j=1}^N b_j(k) = 1,\ \forall k \in V,\ \forall j \in N, j \neq D,F</math>.


Notons que la probabilité de commencer en un état (<math>\mathit \pi</math>) a disparu : elle est élégamment remplacée par les transitions de <math>\mathit D</math> vers les états concernés; d'un point de vue intellectuel, ces transitions sont plus en accord avec la théorie des graphes, puisqu'il n'y a plus de cas spécifique pour le démarrage, mais des transitions comme toutes les autres; d'un point de vue technique, ces transitions sont strictement équivalentes aux probabilités de commencer dans des états, et leur réestimation conduit exactement au même résultat.

Concernant l'état <math>\mathit F</math>, il permet de sortir proprement du modèle : cela mérite quelques explications. Pour des modèles fortement structurés<ref>{{article|auteur=[[El Yacoubi, Mounim & Gilloux, M. & Sabourin, Robert & Suen, Ching]]|titre=An HMM-based approach for off-line unconstrained handwritten word modeling and recognition|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|date=09/1999|pages=752-760|url=https://www.researchgate.net/publication/3193005_An_HMM-based_approach_for_off-line_unconstrained_handwritten_word_modeling_and_recognition|volume=21|numéro=8|doi=10.1109/34.784288}}</ref>, où les états se succèdent sans auto-boucler, les états finaux sont ceux où la dernière observation peut être vue. Pour des modèles où des états bouclent sur eux-mêmes<ref name="cchcifed00"/>, la notion de fin n'est pas déterminée : théoriquement, chaque état peut être final, sauf à avoir un ou des états finaux par structuration(s) forte(s) locale(s). L'état <math>\mathit F</math> vient pallier ce manque : en assignant une probabilité de finir en des états, il contraint le modèle à évaluer cette probabilité, qui modélise alors l'équilibre entre la transition d'un état sur lui-même et sa qualité d'état final.

== Utilisation ==

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'{{Lien|langue=en|trad=Forward algorithm|fr=Forward algorithm|texte=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 ''{{Langue|en|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]], notamment pour la [[prédiction de gènes]].

== Histoire ==

Les HMM ont été décrits pour la première fois dans une série de publications de [[statistique]]s 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<ref name=":0" />.

Dans la seconde moitié des années 1980, les HMM ont commencé à être appliqués à l'analyse de [[séquence biologique|séquences biologique]], en particulier l'ADN <ref>{{article|nom=Bishop|prénom=M|auteur2=Thompson E|titre=Maximum likelihood alignment of DNA sequences|journal=J Mol Biol|date=20 juillet 1986|volume=190|numéro=2|pages=159–65|doi=10.1016/0022-2836(86)90289-5|pmid=3641921}}.</ref>. Les [[Réseau bayésien dynamique|réseaux bayésiens dynamiques]] introduits au tout début des années 1990 généralisent le principe des HMM.

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

* L'[[algorithme de Baum-Welch]] est un cas particulier de l'[[algorithme espérance-maximisation]] et utilise l'[[algorithme Forward-Backward]]. Il permet de ré-estimer les paramètres de manière itérative.
* L'[[algorithme de Viterbi]], souvent utilisé en décodage, peut également être utilisé pour l'apprentissage.
* [[Iterated Conditional Estimation ICE]]

== Références ==
{{Références}}

== Voir aussi ==
* [[Andrei Markov (mathématicien)]]
* [[Chaîne de Markov]]
* [[Propriété de Markov]]
* [[Couverture de Markov]]
* [[Algorithme de Viterbi]]
* [[Filtre de Kalman]]
* [[Théorème de Masreliez]]
* [[N-gramme]]
* [[Processus de décision markovien partiellement observable]]

{{Palette|Apprentissage automatique}}
{{portail|informatique théorique|probabilités et statistiques}}

{{DEFAULTSORT:Modele de Markov cache}}
[[Catégorie:Apprentissage automatique]]
[[Catégorie:Chaîne de Markov]]
[[Catégorie:Théorie des automates]]