Les chaînes de Markov cachées

Les chaînes de Markov cachées (CMC) sont des modèles markoviens dont les états sont cachés.

Il existe plusieurs types de CMC. La première distinction se fait suivant la nature de la fonction de densité de probabilité utilisée pour la génération des observations. Lorsque la distribution est directement obtenue par quantification, les CMC sont qualifiés de discrets. L'utilisation d'une distribution continue, généralement approximée par une mixture de Gaussienne, conduit à des CMC continus. Il existe généralement un compromis entre ces deux familles appelé CMC semi-continu. En effet, l'utilisation d'une quantification induit une perte d'information qui peut être préjudiciable aux modèles. D'un autre côté, le passage à une modélisation continue conduit à une augmentation importante du nombre de paramètres à estimer. Les CMC semi-continus sont une alternative permettant d'optimiser le nombre global de paramètres du modèle.

Une autre distinction est effectuée entre les CMC, suivant le mode d'émission des observations. Généralement les observations sont produites par les états du modèle, on parle alors de modèles d'états. Il est cependant possible de considérer l'émission des observations lors du franchissement des transitions, il s'agit alors de modèles d'arcs. Le choix est guidé par l'application. Nous pouvons cependant mentionner qu'à nombre égal d'états, les modèles d'arcs permettent un plus grand nombre de possibilités quant à l'émission d'observations. Lors de la modélisation d'un phénomène par un modèle d'arcs, il peut être intéressant de permettre le franchissement de transitions sans émission d'observations, en particulier pour modéliser l'abscence d'un évènement.

On définit différents éléments pour une CMC:

• N est le nombre d'états cachés du modèle. On note S = { $s_1$ , $s_2$ , ..., $s_N$ } l'ensemble des états cachés. A l'instant t un état est représenté par $q_t$ ( $q_t$ $\in$ S );
  

• M le nombre de symboles distincts que l'on peut observer dans chaque état. On les représente par l'ensemble V = { $v_1$ , $v_2$ , ..., $v_M$ }. A l'instant t un symbole observable est désigné par $o_t$ ($o_t$ $\in$ V);
  

• Une matrice de probabilité de transitions, notée A = [$a_{ij}$ ], où $a_{ij}$ est la probabilité a priori de transition de l'état i vers l'état j. Dans une CMC stationnaire du $1^{er}$ ordre cette probabilité ne dépend pas de t. On définit $a_{ij}$ = P ( $q_{t+1}$ = $s_j$ $\Vert$ $q_t$ = $s_i$ ), 1 $\leq$ i, j $\leq$ N;
  

• Une matrice de distributions des probabilités, notée B = [$b_j$ (k)], associée à chaque état où $b_j$ (k) est la probabilité d'observer le symbole $v_k$ en étant à l'état $s_j$ à l'instant t. On définit $b_j$ (k) = P($o_t$ = $v_k$ $\Vert$ $q_t$ = $s_j$ ), 1 $\leq$ i $\leq$ N, 1 $\leq$ k $\leq$ M;
  

• Un vecteur $\Pi$ =[$\pi_i$ ] de distributions des probabilités de transitions initiales, où $\pi_i$ est la probabilité de commencer dans l'état i. On définit $\pi_i$ = P[$q_1$ = $s_i$ ] avec 1 $\leq$ i $\leq$ N.
  

On peut dire qu'une CMC notée $\lambda$ est définie complètement par $\lambda$ = (A, B, $\Pi$ ) (N et M sont sous entendus dans les matrices A et B ainsi que le vecteur $\Pi$ ).

La génération des observations dans une CMC se fait par la procédure suivante :

1. t = 1 choix de l'état initial, $q_1$ = $s_i$ avec la probabilité $\pi_i$ ;
2. Choix de l'observation $o_t$ = $v_k$ , avec la probabilité $b_i$ (k);
3. Transition vers le nouvel état $q_{t+1}$ = $s_j$ avec la probabilité $a_{ij}$ ;
4. t = t+1 ; si t $\leq$ T, alors retour à l'étape 2, sinon fin de procédure (avec T la longueur d'une suite d'observations).

Afin de pouvoir exploiter le modèle $\lambda$ , trois problèmes de base doivent être résolus :

1. Le problème d'évaluation : soit une séquence d'observations $O = o_{0}, o_{1}, ..., o_{T-1}$ et un modèle $\lambda$ = (A, B, $\Pi$ ), comment calculer efficacement la probabilité de cette séquence étant donné le modèle $Pr(O\vert A)$ ?
2. Le problème de décodage ou de reconnaisance : étant donnés une séquence d'observations $O = o_{0}, o_{1}, ..., o_{T-1}$ et un modèle $\lambda$ = (A, B, $\Pi$ ), comment trouver la séquence optimale d'états $Q = q_{0}, q_{1}, ..., q_{T}$ qui a produit la séquence $O$ ?
3. Le problème de ré-estimation ou d'apprentissage : étant donné un ensemble de séquences d'observations et un modèle initial $\lambda$ , comment ré-estimer les différents paramètres du modèle afin d'augmenter la vraisemblance d'apparition de la séquence d'observation. La maximisation de la vraisemblance d'un modèle probabiliste est aujourd'hui effectuée par des algorithmes efficaces, comme l'algorithme EM (Expectation Maximization) ou l'algorithme de Baum-Welch, que nous allons présenter dans une deuxième partie.