Chapitre2 Les chaînes de Markov cachées

Les chaînes de Markov cachées

2.1 : Introduction
Les modèles de Markov cachées MMCs sont des modèles statistiques, riches et
largement utilisés en traitement du signal. Ils sont développés par Andrew Markov (étudiant de
Chebyshev), et ils sont premièrement, orientés vers des objectifs linguistiques dans des travaux
de littérature Russe [29]. Ceux sont des outils efficaces en modélisation des données
séquentielles ou ‘time-series Data’ [31]. Utilisés par la suite dans des problèmes de
reconnaissance de la parole par Baker, leur théorie de base est introduite par Baum et ses
collègues à la fin des années soixante.
Actuellement, ces modèles sont, de plus en plus adoptés en reconnaissance automatique
de la parole, pour l’analyse des séquences ADN 4, et dans des problèmes liés à l’écriture et le
traitement de texte.
Aussi, leur utilisation en visionique est vaste. Ils sont implémentés en segmentation
d’images, reconnaissance des visages, interprétation des gestes, ainsi que la modélisation de
l’arrière plan et récemment en traitement vidéo.

4
: l’acide nucléique appelé : Acide Désoxyribonucléique

13
Chapitre2 Les chaînes de Markov cachées

Ce chapitre constitue le support théorique de base de notre étude. Nous allons donc,
donner une vue générale de ces modèles, les éléments particuliers intervenant dans leur
construction, les problèmes liés à leur utilisation et les solutions usuelles de ces derniers.

2.2 : Chaînes de Markov et extension aux chaînes cachées

2.2.1 : Chaîne de Markov
Supposons X  ( X 1 X 2 ... X T ) une séquence de variables aléatoires prenant leurs valeurs
dans un ensemble fini   1 ,  2 ,..., K  appelé l’espace d’état.
On définie un processus aléatoire, qui à chaque instant, visite l’un des K états
possibles. A l’instant suivant, ce système (processus) change d’état, avec possibilité de rester à
l’état actuel, suivant un ensemble de probabilités ; Fig ( 2.1 ) .

ω1

ω3

ω2

Fig ( 2.1 ) : Graphe d’états d’une Chaîne de Markov à

trois états

Une description probabiliste complète du processus, nécessite la spécification de l’état

actuel (à l’instant t ), ainsi que tous les états précédents [29, 31].
Pour un processus Markovien du premier ordre, cette spécification est arrondie à l’état
actuel et son précédent adjacent. Cela est produit par l’équation suivante :

P  X t   j / X t 1   i ,..., X 1  1   P  X t   j / X t 1   i  …………………..… (2.1)

Les probabilités conditionnelles P  X t   j / X t 1   i  sont dites des probabilités de

Transition, et sont notées aijt . aijt ne dépendra pas du temps si elle est la même à deux temps

14
Chapitre2 Les chaînes de Markov cachées

déférents t et t ' . Dans ce cas, les aijt seront notées tout simplement les aij ; constituant ainsi

une matrice carrée d’ordre K ; appelée Matrice de Transition, et nommée A . Signalons que
K est le nombre d’états possibles, dans lesquels peut évoluer le processus. On écrit :

aij  P X t  j / X t 1 i  …………………….…………………...…….………….... (2.2)

et la matrice de transition sera:

A aij  P X t  j / X t 1 i  , 1 i, j  K …...……………….………………….. (2.3)

Les éléments aij vérifient les propriétés stochastiques suivantes :

1/ 0  aij  1 i, j
K ………………................….……………. (2.4)
2/  j 1
aij  1 i  1,..., K

Désignons par Pt  , le vecteur stochastique défini par P X t   i  avec : i  1,..., K ,

ainsi P1 sera le vecteur des distributions initiales ( à l’instant t 1 ). On note ce vecteur par  ,
tel que chacun de ses éléments est donné par:

 i  P X 1  i  ………………………………………………...…….………….... (2.5)

De même, les  i ; éléments de  , vérifient les propriétés stochastiques précédentes :

1/ 0  i 1 i
K ……………..……...……..…………………………. (2.6)
2/ i1 i  1 i

Notons donc, qu’une chaîne de Markov est entièrement définie par sa matrice de
transition A et ses distributions initiales, données par le vecteur  .

15
Chapitre2 Les chaînes de Markov cachées

Cela en effet, peut être résumée par la définition ci-après :

Définition :
Chaîne de Markov
T
Une chaîne de Markov est un processus stochastique X   X t t 1 tel
que :
t , P  X t / X t 1 i , X t 2 ..., X 1   P  X t / X t 1  .

 i  P X 1  i 
De plus, si P  X t   j / X t 1   i   aij , t , si ces probabilités appelées

probabilités de transition sont indépendantes de t , alors la chaîne est dite

homogène.

2.2.2 : Graphe d’indépendance d’une chaîne de Markov

La chaîne de Markov appartient à la famille des signaux pouvant être représentés par
des graphes ; où les cercles sont étiquetés par les états possibles, et les arcs désignent les
transitions valables ente ces états. Le graphe d’indépendance d’une chaîne de Markov est
donné par la Fig ( 2.2 ) :

Fig ( 2.2 ) : Graphe d’indépendance d’une chaîne de Markov

La figure ci-dessus représente un processus Markovien observable. Ses sorties donnent

directement les états, dont chacun est attaché à un évènement physique observable [31].
La probabilité jointe d’une séquence d’état X  ( X 1 X 2 ...X T ) est facilement calculée
pour une chaîne de Markov. Elle est donnée par un produit de probabilités comme suit :

P X 1 , X 2 ,..., X T   P X 1   P X 2 / X 1   P X 3 / X 1 , X 2   ...  P X T / X 1 , X 2 ,..., X T 1  .. (2.7)

16
Chapitre2 Les chaînes de Markov cachées

En intégrant la propriété de Markov donnée par la formule (2.1), l’équation (2.7) devient :

P X 1 , X 2 ,..., X T   P X 1   P X 2 / X 1   P X 3 / X 2   ...  P X T / X T 1  ……………. (2.8)

Cette dernière est condensée donnant l’écriture suivante:

T 1
P X 1 , X 2 ,..., X T    X 1   a X t X t 1 ………………………………….……….…… (2.9)
t 1

Nous citons un petit exemple qui met en valeur la notion de la Chaîne de Markov, et
permet de mesurer la probabilité d’une séquence d’états bien définie. Remarquons que cette
mesure de probabilité est évaluée par un simple produit.

Exemple
Utilisation de chaîne de Markov dans une prédiction météo :
Assumons que chaque jour, le temps est dans l’un des trois états suivants :
o Etat 1 : pluvieux.
o Etat  2 : nuageux.

o Etat  3 : ensoleillé.

On donne la matrice de transition A par:

0.4 0.3 0.3
A  0.2 0.6 0.2
 0.1 0.1 0.8

et le vecteur initial  par :   0 0 1 .

La question posée est :

Sachant qu’aujourd’hui est ensoleillé, et avec un tel modèle, quelle est la probabilité
que le temps suit, dans les sept (07) jours qui suivent, la séquence d’observation O donnée
par :
O   3 ,  3 ,  3 , 1 , 1 ,  3 ,  2 ,  3  pour t  1,2,...,8 .

17
Chapitre2 Les chaînes de Markov cachées

Une telle probabilité est exprimée par PO / mod èle  tel que :

PO / mod èle   P 3 ,  3 ,  3 , 1 , 1 ,  3 ,  2 ,  3 / mod èle  avec PO / mod èle  dénote

la probabilité de la séquence d’observations O sachant ce modèle.

En utilisant la propriété de la chaîne de Markov marquée par (2.8), la formule précédente
PO / mod èle   P 3   P 3 /  3   P 3 /  3   P1 /  3   P1 / 1   P 3 / 1 
 P 2 /  3   P 3 /  2 
devient:   3  a33  a33  a31  a11  a13  a32  a 23
 1  0.8  0.8  0.1  0.4   0.3  0.1  0.2
 1.536  10  4

2.2.3 : Chaîne de Markov cachée

Maintenant, on ajoute des observations ; on considère que X est un processus caché, et
on souhaite déterminer ses états par l’intermédiaire du vecteur d’observations Y .
Donc, un modèle de Markov caché; noté MMC est un processus stochastique double
[31], avec :
 Un premier processus X caché, constitué d’un ensemble d’états connectés entre elles
par des probabilités de transition.
 Un deuxième processus Y observable, constitué d’un ensemble de sorties; dites
observations. Chaque sortie peut être émise par n’importe quelle état caché,
conformément à une fonction densité de probabilité de sortie.
On peut annoncer la définition ci après :

Définition :
Chaîne de Markov cachée
Une chaîne de Markov cachée ‘CMC’ est un processus stochastique double
 X , Y  [35], tel que :
T
- X   X t t 1 , soit une chaîne de Markov homogène. Elle est définie par sa
distribution initiale  et sa matrice de transition A .
T
- Y  Yt t 1 , soit un processus observable et indépendant conditionnellement à

X ; tel que : PY / X    P X t / Yt  .

t

18
Chapitre2 Les chaînes de Markov cachées

2.2.4 : Graphe d’indépendance d’une chaîne de Markov cachée

Graphiquement, on représente une chaîne de Markov cachée par la figure Fig ( 2.3 ) .
On dit qu’on a une dépendance ponctuelle de Y relativement à X .

Fig ( 2.3 ) : Graphe d’indépendance d’une chaîne de Markov cachée

2.3 : Lois d’observation

Plusieurs approches ont été successivement proposées dans le choix des lois
d’observation rattachées aux états cachées du modèle. Si l’espace d’observation est déscret et
fini, chaque distribution b j . est entièrement définie par la reconnaissance de la probabilité

d’émission de chacun des points de l’espace. y1 , y 2 ,..., y M  . La valeur de M , donne la taille
de cet espace d’observation. L’ensemble des lois d’observation est B  b j .1 j  K , et

entièrement caractérisé par le vecteur b j m.;1  j  K ;1  m  M .

Chaque paramètre b j m  détermine la probabilité que le point y m soit émis par la

distribution b j . , l’ensemble des probabilités b j m  vérifiant, pour chaque état  j du modèle

la contrainte :
j :  b m  1
1 m M
j

Lorsque l’espace d’observation est continu, plusieurs choix sont possibles pour les
fonctions densités de probabilité, et sont en général basés sur des gaussiennes. L’ensemble des
lois d’observation F  f j .1 j  K est alors caractérisé par la connaissances des K densités de

probabilité f1 , f 2 ,..., f K associées aux K classes considérées.

19
Chapitre2 Les chaînes de Markov cachées

2.4 : Eléments d’une chaîne de Markov cachée

A fin d’utiliser une chaîne de Markov cachée, il est indispensable de spécifier les
caractéristiques ci-après. On parle d’éléments de cette chaîne :
 K : Nombre d’états dans le modèle. Chaque état a une signification physique
déterminée, selon l’application prise. On dénote les états individuels par
  1 ,  2 ,..., K  . L’état, à l’instant t est noté X t .
 M : Nombre de symboles observés. Ils correspondent aux sorties physiques du système
modélisé. On dénote les symboles individuels par y1 , y 2 ,..., y M  . Celui, à l’instant t est

noté Yt . La structure, elle aussi, est imposée par le phénomène étudié.

   : matrice de transition, avec:

A aij
aij  P  X t   j / X t 1   i  , 1  i, j  K .

    i  : probabilités initiales de transition, avec :

 i  P X 1  i  , 1 i  K .

 B  b j  y t  : probabilités d’émission, tel que :

b j  y t  : est la probabilité d’émettre le symbole y t à l’instant t , sachant que l’état à ce

moment est X t   j . On écrit :

b j  y t   P Yt  y t / X t   j 

 T : Longueur de la séquence d’observations Y ; avec Yt est le symbole observé à

l’instant t .

Donc, en utilisant une notation compacte, un MMC est noté par    , A, B  désignant
les paramètres complets d’un modèle de Markov caché.

2.5 : Types principaux des modèles MMCs

A toute chaîne de Markov est associé un graphe d’états, représentatif des possibilités
d’évolution séquentielle du processus modélisé. Sa topologie dépend directement des positions
relatives des zéros dans la matrice A de transition. La structure d’un MMC diffère donc, selon
le phénomène à étudier. Parmi celles les plus utilisées, on cite deux types importants : « MMC
ergodique » et « MMC gauche-droit » [31,33], tout deux présentés par la figure : Fig ( 2.4 ) .

20
Chapitre2 Les chaînes de Markov cachées

Celui ergodique de Fig (2.4.a), est un cas spécifique ; où le modèle est dit
complètement connecté, et toutes les possibilités d’évolution sont permises a priori. Autrement
dit, tous les aij sont positifs, et la matrice A est pleine. Cela permet d’atteindre n’importe quel

état en passant par n’importe quel chemin.

Tandis que un MMC à matrice A triangulaire supérieure appelé « gauche-droit » ou
‘Left-Right’ est illustré dans Fig (2.4.b). Celui-ci est particulièrement adapté à la modélisation
d’évolution temporelle de processus (parole, gestes). Ce type se dote de la propriété
d’accroissance de l’indice d’état relativement au temps (pas de retour arrière). Il est notamment
choisi pour modéliser les signaux dont les caractéristiques changent avec le temps. La propriété
fondamentale de ce genre est :
0 , i  1
aij  0 , si i  j , et  i  
1 , i  1
Il revient de souligner que le graphe d’états d’un MMC n’est pas à confondre avec le
graphe d’indépendance, lequel représente le modèle « déroulé » dans le temps, en soulignant
graphiquement la dépendance ponctuelle des observations relativement aux états.

Fig ( 2.4 ) : Graphes d’état de deux types des modèles MMCs

(a) Modèle ergodique, (b) Modèle gauche-droit

2.6 : Les trois problèmes liés aux MMCS

Etant donné un MMC, la plus part des applications sont réduites à résoudre les trois
problèmes essentiels liés à une chaîne de Markov cachée [29, 30, 31, 32]. Autrement dit, pour
une modélisation à base de chaînes de Markov cachées, il faut répondre aux trois questions
suivantes :

21
Chapitre2 Les chaînes de Markov cachées

Soit  un MMC donné, et soit Y  Y1 , Y2 ,...,YT  une séquence d’observation donnée :

2.6.1 : Evaluation
Le problème d’évaluation est celui permettant de répondre à la question suivante:

Calculer PY /   ?

Où PY /   est la probabilité d’une séquence d’observations Y sachant le modèle  . C’est le

problème nommé aussi, par ‘Scoring’. Par exemple, si on dispose de plusieurs modèles
compétitifs, cette démarche permet de choisir le meilleur modèle générant cette séquence
d’observations Y .

2.6.2 : Optimisation
Dans ce cas la, on se tente de déterminer la démarche convenable, amenant à la réponse
de la question posée ainsi:

Comment choisir une séquence d’état X   X 1 , X 2 ,..., X T  , qui est optimale ?

On cherche, donc à décoder les états qui correspondent de mieux à la séquence d’observations
Y ; c’est pour quoi on utilise souvent le nom : ‘Decoding’.
Alors, cette partie est la section dans laquelle on découvre les états cachées d’un MMC ;
ou bien, trouver la séquence d’état correcte. Notons que cette dernière n’existe pas ; c’est
plutôt une estimation meilleure. C’est pourquoi en pratique, on se sert des critères
d’optimisation ; d’où le nom optimisation donné à ce problème.

2.6.3 : Apprentissage
Ce problème s’occupe d’ajuster les paramètres du modèle  , dans l’objectif de
maximiser la probabilité d’observation annoncée au premier problème; donc :

 
Trouver  ? tel que :   arg max PY /   .


22
Chapitre2 Les chaînes de Markov cachées

Cela signifie d’adapter les paramètres  , A, B  du modèle, pour mieux décrire

l’application. La séquence d’observation Y utilisée, dans ce cas est appelée séquence
d’apprentissage ; notée parfois YTraining .

Ce dernier problème est crucial, puisqu’il permette de mieux adapter le modèle choisi
au phénomène considéré.

2.7 : Solutions des trois problèmes

Dans ce paragraphe, nous allons donner, en bref, les solutions usuelles des trois
problèmes ci-dessus selon [31].

2.7.1 : Premier problème : évaluation

On veut trouver la probabilité d’une séquence d’observations Y sachant le modèle  .
C’est déterminer la mesure de vraisemblance PY /   .
Rappelons que :

P Yt / X t   bX t Yt  ………………………………………………….……………. (2.10)

et :

PY , X /    PY / X ,    P X /   ……………….………………….……………. (2.11)

Tel que PY , X /   : est la probabilité jointe de Y et X sachant ce modèle  .

La démarche suivie pour mesurer la probabilité PY /  est d’énumérer toutes les
séquences possibles de longueur T.
Mais pour le moment, considérons X   X 1 , X 2 ,..., X T  , une séquence d’état fixe. Selon la

propriété d’indépendance conditionnelle des observations, la probabilité PY / X ,   est

donnée par :

T
PY / X ,     PYt / X t ,   ……………………………………….…………… (2.12)
t 1

23
Chapitre2 Les chaînes de Markov cachées

Accordée à l’équation (2.10), la formule (2.12) devient comme suit :

T
P Y / X ,     bX t Yt  ……………………………………….…………………. (2.13)
t 1

Ou encore :

P Y / X ,    bX1 Y1   bX 2 Y2   ...  bX T 1 YT 1   bXT YT  ..……………….……………. (2.14)

d’une part.
D’autre part, rappelons la formule (2.9):

T 1
P  X /     X 1   a X t X t 1
t 1

La probabilité d’une séquence d’observations Y sachant  est donnée donc, par la

somme de toutes les probabilités jointes, associées aux combinaisons d’état possibles, donnant
chacune une séquence X d’états de même longueur T . On écrit :

PY / sur tous les X PY / X,   P X /  …………………………….……………. (2.15)

En substituant (2.9) et (2.14) dans (2.15), on obtient la mesure de vraisemblance comme suit :

PY /    sur tous les X  X1  bX 1 Y1   a X 1X 2  b X 2 Y2   a X 2 X 3  ...  b X T 1 YT 1   a X T 1X T  bX T YT  .. (2.16)

remarque  :

Le calcul précédant de PY /   , fait appel à un nombre de multiplications de

 
l’ordre de 2  T  1  K T , associé à K T  1 additions [31]. Il semble être difficile à
effectuer même pour des petites valeurs de K et T .
A titre d’exemple, pour un nombre d’états de K  2 , et une séquence
d’observations de T  100 de longueur, le nombre total d’opérations est de l’ordre de
2  100  2   100  2
100 101

24
Chapitre2 Les chaînes de Markov cachées

Cet accès de calcul peut être résolu en utilisant la procédure nommée ‘Forward-
Backward’. Elle est basée sur le détermination des deux probabilités ‘Forward’ ;  t i  , et

‘Backward’ ;  t i  , dont les spécifications et méthodes de calcul seront données au chapitre

suivant.
Notons maintenant que :

 t i   PY1 , Y2 ,...,Yt , X t   i /   ……………………………….….……………. (2.17)

C’est la probabilité de la séquence d’observations partielle jusqu’à l’instant t avec le système

est dans la classe  i à ce dernier moment t , sachant le modèle  .

Et :

 t i   PYt 1 , Yt  2 ,...,YT / X t   i ,   …………………..…….…….……………. (2.18)

Cette quantité représente la probabilité de la séquence d’observations partielle débutant à

l’instant t  1 et allant jusqu’à l’instant final, sachant qu’au moment t , le système est dans la
classe  i , et aussi sachant le modèle  .

2.7.2 : Deuxième problème : ‘decoding’

Contrairement au premier problème, ou on peut donner une réponse exacte et unique, la
solution de celui-ci est non spécifique. La diversité des critères conduit à un choix large de
méthodes. Rappelons qu’on cherche la séquence d’état optimale, associée à un vecteur
d’observations donnée [29, 31].
Parmi les politiques d’optimisation, l’un s’intéresse à chaque état seul. Il désigne, donc
l’état attendu par optimisation individuelle. Cette démarche est basée sur le calcul de la
probabilité  t i  ; la probabilité d’être à l’état  i à l’instant t sachant l’observation

complète Y et le modèle  . La probabilité en question est donnée par :

 t i   P X t   i / Y ,   …………………………………………….……………. (2.19)

De même, cette probabilité sera exprimée ultérieurement à l’aide des probabilités

‘Forward’ et ‘Backward’ ;  t i  et  t i  respectivement.

25
Chapitre2 Les chaînes de Markov cachées

La séquence d’état optimale est alors déterminée, par l’accumulation des états
optimaux. Chaque état vérifie cette caractéristique tout seul et indépendamment des autres. On
ecrit:

Xt optimal  arg max  t i  , 1  t  T …………….……………….……………. (2.20)

1 i  K

Un autre néglige les états isolés et exploite la notion « chemin ». Il s’intéresse donc, aux
chemins partiaux optimaux. Un des premiers dits algorithmes, utilisé avec les MMCs, est
l’algorithme de Viterbi. Il détermine ce chemin optimal progressivement, tout en conservant
l’optimalité partielle [29, 31, 35]. Pour utiliser ce dernier, une nouvelle probabilité à introduire,
est  t i  avec :

 t i   max P X 1 , X 2 ,..., X t   i , Y1 , Y2 ,..., Yt /   ………………...…………. (2.21)

X 1 , X 2 ,..., X t 1

Cette mesure représente la probabilité jointe maximale correspondante aux sous séquences
d’observations et d’état ; Y1 , Y2 ,...,Yt  et  X 1 , X 2 ,..., X t 1  respectivement, et avec le processus

se trouvant actuellement à l’état  i .

Par induction, on trouve:

 t 1  j    max  t i   aij   b X t 1  j Yt 1  …………….…………….……………. (2.22)

 X1 , X 2 ,..., X t 

Une fois de plus, on fait une accumulation d’états vérifiant la maximisation, en se

servant d’un accumulateur  (tableau), avec :

2  t  T
 t  j   arg max  t 1 i   aij  ,  ………….……………….……………. (2.23)
1 i  K 1  j  K

L’algorithme complet de Viterbi est donné ultérieurement au chapitre suivant.

26
Chapitre2 Les chaînes de Markov cachées

2.7.3 : Troisième problème : ‘training’

Ce problème est classé, comme étant, le plus difficile des trois. Sa solution vise à
déterminer une méthode capable d’ajuster les paramètres de  ; c’est maximiser P YTraining /  

au sens du maximum de vraisemblance [31], dont les paramètres estimés  sont donnés
comme suit:


  arg max PYTraining /   ……………….………………………….……………. (2.24)


Dans la littérature, il n’y a pas de méthodes analytiques spécifiques pour maximiser la

probabilité précédente. On se sert donc, des procédures itératives. Un algorithme répondu, dans
ce domaine est celui de Baum-Welch, connu aussi par algorithme ‘Forward_Backward’.
D’autres utilisent son équivalent, dit algorithme EM ; pour ‘Expectation-Modification’.
Pour appliquer ces procédures itératives, on a besoin de définir une nouvelle
probabilité, nomée  t i, j  , et mesurant le fait d’être à l’état  i à l’instant t , et à l’état  j à

l’instant suivant, sachant la séquence d’observations Y et le modèle  . On exprime celle ci

par :

 t i, j   P X t   i , X t 1   j / Y ,   …………….……………….……………. (2.25)

Cette nouvelle quantité est écrite en fonction des deux fameuses probabilités ‘Forward’
et ‘Backward’. Par la suite, on déduit tous les paramètres nécessaires à la mise à jours du
modèle (voir chapitre suivant).

remarque  :
Notons seulement que cette algorithme démarre d’un MMC initial connu, dont
les paramètres affectent sa performance attendue. Une bonne initialisation, alors est
toujours demandée.

27
Chapitre2 Les chaînes de Markov cachées

2.8 : Conclusion
Les Modèles de Markov cachés MMCs, précisément les Chaînes de Markov Cachées,
sont donc des outils de modélisation très utiles. Leur choix en vue de résoudre un problème
bien défini nécessite une spécification complète de leurs éléments ; à savoir: la matrice de
transition, les distributions initiales et les densités d’émission des observations.
Ces modèles peuvent être classés comme des méthodes probabilistes, d’une part.
D’autre part, ils appartiennent à la famille des modèles pouvant être représentés
graphiquement à l’aide d’arcs et de cercles.
Pour la modélisation d’un phénomène quelconque par ces outils là, il est donc,
indispensable de répondre aux trois problèmes essentiels associés à ces modèles, dont nous
avons brièvement, nommé et donné les solutions usuelles utilisées. Nous avons aussi, défini les
diverses probabilités intermédiaires nécessaires à l’intégration des algorithmes destinés à
établir ces solutions.

Ainsi, le chapitre suivant couvre plus largement, les procédures et les algorithmes
dédiés à la résolution de ces problèmes, et l’exploitation de ces MMCs dans des domaines
variés. Par la suite, nous verrons leur intégration en vue de la détection d’objet mobile.

28