Modèles de Markov
Modèles de Markov
Introduction
(cid:1) Hypothèse faite jusqu'a présent : chaque donnée est
ponctuelle
(cid:1) Données indépendantes les unes des autres
(cid:1) Propriété iid : indépendantes identiquement distribuées
(cid:1) Données dépendantes
(cid:1) Dépendances temporelles
(cid:1) Dépendances spatiales
Dépendances spatiales
(cid:1) Exemple de données avec dépendances temporelles ou
spatiales
(cid:1) Signal acoustique
(cid:1) Cours boursiers
(cid:1) Flux vidéo
(cid:1) Séquences d'ADN
124
ENSI--SI3
2014-2015
Processus stochastique
(cid:1) Un processus stochastique (ou processus aléatoire) est
une séquence de variables aléatoires fondées
(
)
sur le même ensemble fondamental Ω.
K=
X
1
NX
X
,
(cid:1) Les valeurs possibles des variables aléatoires sont appelées les
états possibles du processus.
(cid:1) La variable représente l’état du processus au temps t (on
(cid:1) La variable représente l’état du processus au temps t (on
tX
X
dit aussi l’observation au temps t).
(cid:1) Les différentes variables aléatoires ne sont en général pas
indépendantes les unes des autres.
(cid:1)l’intérêt des processus stochastiques réside dans la
dépendance entre les variables aléatoires.
125
ENSI--SI3
2014-2015
Processus stochastique
(cid:1) Pour spécifier entièrement un processus stochastique, il
suffit de spécifier :
1X
(cid:1) la loi de probabilité de la première variable aléatoire
qui spécifie donc l’état du processus lors de la première
observation.
(cid:1) pour toute valeur de t > 1 la probabilité conditionnelle :
(cid:1) pour toute valeur de t > 1 la probabilité conditionnelle :
XP
(
t
=
Xj
1
=
i
1
,
K
,
X
- =
1
t
i
t
)
1
126
ENSI--SI3
2014-2015
-
Propriété de Markov
(cid:1) Une chaîne de Markov est un type particulier de
processus stochastique qui vérifie deux conditions :
(cid:1) L’état au temps t du processus ne dépend que de son état au
temps t − 1 :
XP
(
(
XP
t
=
=
Xj
Xj
1
=
=
K
,
,
X
X
i
i
1
,
,
t
1
=
=
i
i
t
)
)
1
=
=
XP
(
(
XP
t
=
=
Xj
Xj
t
1
=
=
i
i
t
)
)
1
(cid:1) La probabilité de passage d’un état i à un état j est constante,
elle ne varie pas avec le temps (Transitions indépendantes du
temps):
t
1,
£<
,
XPNt
(
=
t
Xj
t
1
==
)
i
C
127
ENSI--SI3
2014-2015
-
-
-
-
"
-
Processus de Markov
(cid:1) Un processus de Markov peut être décrit par :
(cid:1) une matrice de transition T telle que :
iT
),(
j
=
(
XP
t
=
Xj
t
1
==
)
i
C
avec
et
iT
iT
,0),(
j
j
,0),(
i
i
,
,
j
j
iT
,1),(
j
=
i
N
∑
=
1
j
(cid:1) L’état du processus à l’instant 1 donc la loi de probabilité,
p
)(i
notée , de la variable X1 :
p
=
XP
(
i
)(
=
i
)
1
128
ENSI--SI3
2014-2015
-
"
‡
"
‡
"
Processus de Markov
(cid:1) Le modèle de Markov résultant est un automate
stochastique :
(cid:1) Chaque état du processus est représenté par un état de
l’automate
(cid:1) Une transition de l’état i à l’état j est étiqueté par la probabilité :
=
a =
aij
iT
iT
j
),(
),(
j
(cid:1) Exemple :
Processus de Markov à trois états
129
ENSI--SI3
2014-2015
Exemple
(cid:1) On admet que le fait qu’il ait plu ou non un jour donné
est la seule considération à prendre en compte pour
prévoir s’il pleuvra le lendemain. Plus précisément, s’il
il pleuvra demain aussi avec une
pleut aujourd’hui,
probabilité de α et s’il ne pleut pas aujourd’hui
la
probabilité qu’il pleuve demain est β .
probabilité qu’il pleuve demain est β .
(cid:1) On convient de dire que le système est dans l’état 1 s’il
pleut et 2 s’il ne pleut pas. La situation peut être
représentée par une chaîne de Markov à deux états dont
la matrice de transition est :
a
b
1
1
a
b
130
ENSI--SI3
2014-2015
-
-
Exemple
(cid:1) De plus, la probabilité que le processus soit dans l’état 1
à l’instant 1 est égale à γ.
(cid:1) Le même processus peut être représenté par l’automate :
131
ENSI--SI3
2014-2015
Modèle de Markov observable
(cid:1) A chaque pas de temps t, on connaît l’état Xt
(cid:1) La séquence d'observations O correspond à la séquence
d’états réelle du système X.
,
1
(cid:1) Les propriétés de Markov permettent de calculer
(cid:1) Les propriétés de Markov permettent de calculer
TX
,
,
2
{
XXO
=
K
}
simplement la probabilité qu’une suite d’états particulière
de longueur T soit observée (la loi de probabilité conjointe
{
de ) :
,
,
XX
1
2
)
(
,
XXP
1
XXP
1
i
TX
K
,
,
(
XP
1
K
,
Publicité
K
X
X
}
=
)
(
)
,
T
T
1
2
i
=
(
XP
1
)
=
2
i
T
=
2
i
XXP
i
(
i
)
1
132
ENSI--SI3
2014-2015
(cid:213)
(cid:213)
-
-
Exemple
(cid:1) Système météorologique à deux états : soleil (Xsoleil ) ou
pluie (Xpluie)
p
(cid:1) Probabilités initiales, et
pluie
=
6.0
(cid:1) Probabilités de transitions, ,
soleil
p
6.0=
a
soleil
,
pluie
=
4.0
4.0=
a
soleil
,
soleil
=
7.0
pluiea
,
soleil
=
3.0
et
pluiea
,
pluie
133
ENSI--SI3
2014-2015
Exemple
(cid:1) La probabilité d'observer la séquence
{
=
XO
,
X
,
X
pluie
pluie
soleil
,
X
soleil
}
=
XPOP
(
(
)
)
(
XP
X
pluie
)
(
XP
soleil
X
pluie
)
(
XP
soleil
X
)
soleil
pluie
pluie
p
=
=
a
a
a
pluie
pluie
pluie
soleil
,
,
=
.06.03.07.06.0
pluie
soleil
0756
,
soleil
134
ENSI--SI3
2014-2015
·
·
·
Exercice
135
ENSI--SI3
2014-2015
Modèle de Markov caché MMC
(cid:1) Les états ne sont pas directement observables
(cid:1) Les observations sont des fonctions probabilistes des
is
états
(cid:1) Les observations sont discrètes, obtenues d'un ensemble
=
OOO
2
,
1
K
,
,
MO
(cid:1) Probabilité d’émission (croyance) d'observer dans un
mO
état
js
(cid:1)
136
mb
(
j
)
oP
(
t
=
sO
m
t
=
S
)
j
ENSI--SI3
2014-2015
”
Modèle de Markov caché MMC
(cid:1) Séquence d‘états S est cachée, inférence à partir de
séquence d'observations O.
(cid:1) Différentes séquences d‘états S peuvent générer une
même séquence d'observations O.
(cid:1) On veut déterminer la séquence d’états la plus vraisemblable
(cid:1) Deux sources d'incertitudes
(cid:1) Transition aléatoires entre les états
(cid:1) Observations aléatoires selon l‘état
137
ENSI--SI3
2014-2015
Exemple de modèle de Markov caché
(cid:1) Probabilités d‘émission lorsque pluie : bpluie(marche) = 0.1,
bpluie(sport) = 0.2, bpluie(étude) = 0.7
(cid:1) Probabilités d‘émission lorsque soleil : bsoleil(marche) =0.3,
bsoleil(sport) = 0.5, bsoleil(étude) = 0.2
138
ENSI--SI3
2014-2015
Composantes d'un MMC
S
=
(cid:1) Modèle formé de N états
{
,
SS
1
NS
(cid:1) Observations distinctes selon M symboles
MO
{
OOO
2
K
K
}
}
=
,
,
,
,
,
1
2
]
(cid:1) Probabilités de transitions entre états
S
)
i
sS
j
t
(cid:1) Probabilités d'observations (probabilités d‘émission, croyances)
=
aoù
]
[
=
aA
[
sOoPmboùmbB
(
j
tm
sP
(
t
=
=
=
=
+
1
S
ji
,
ji
,
)
(
)
)
(
j
t
j
[
p
=P
(cid:1) Probabilités d‘état initial
]
=
p
sP
où
( 1
A=l
(cid:1)Modèle :
(
,
,
i
i
S
)
)
i
139
ENSI--SI3
2014-2015
”
”
”
P
B
Trois questions
(cid:1) Etant donnée une séquence d'observations :
(cid:1) Quelle est la probabilité d'apparition de cette séquence ?
(cid:1) Quelle est la séquence d'états la plus probable qui a généré
cette séquence ?
cette séquence ?
(cid:1) Comment modifier le MMC pour que la probabilité
d'apparition de cette séquence soit maximale ?
140
ENSI--SI3
2014-2015
Principaux problèmes avec les MMC
(cid:1) Problème de l’évaluation
(cid:1) Etant donné un modèle λ du MMC, quelle est la probabilité
lOP
(
}
d'avoir une séquence d'observations ?
{
ooO
2
K,
To
=
)
,
1
(cid:1) Problème du décodage
Publicité
λ
(cid:1) Etant donné un modèle λ du MMC et une séquence
d'observations O, quelle est la séquence d’état
d'observations O, quelle est la séquence d’état
S
qui a vraisemblablement générée O ?
{
, 2
ss
1
K,
Ts
}
=
*
S
=
arg
max
S
lOSP
,
(
)
141
ENSI--SI3
2014-2015
Principaux problèmes avec les MMC
(cid:1) Problème de l'apprentissage du modèle
{
kO=c
(cid:1) Etant donné un jeu d'entraînement contenant des
séquences d'observations, quel est le modèle λ du MMC qui
aurait vraisemblablement généré le jeu ?
}
c
k
*
l
l
=
=
arg
arg
max
max
l
lc
lc
P
P
(
(
)
)
142
ENSI--SI3
2014-2015
Problème de l‘évaluation
(cid:1) Problème de l‘évaluation : déterminer la probabilité
lOP
(
)
(cid:1) Pour une séquence d‘états S, le calcul est direct
T
T
(
SOP
,
l
=
)
(
soP
t
t
,
l
=
)
=
1
t
(
ob
s
t
t
)
=
1
t
(cid:1) S n'est cependant pas connu en pratique, mais on a des
probabilités
probabilités
(
SP
(
sP
1
(cid:1) Probabilités jointes
)
l
=
T
)
=
2
t
(
ssP
t
t
l
,
1
)
=
p
(
SOP
,
l
=
)
(
SOP
,
l
)
(
SP
l
)
=
p
T
s
1
=
2
t
a
s
t
,
s
t
1
(
ob
s
1
1
)
s
1
T
=
2
t
a
(
ob
s
t
t
)
s
t
,
s
t
1
(cid:1) Résolution de en sommant sur tous les S possibles
∑
)
(
OP
(
SOP
=
l
l
)
)
,
lOP
(
143
ENSI--SI3
2014-2015
S
(cid:213)
(cid:213)
(cid:213)
(cid:213)
-
-
(cid:213)
-
"
Procédure avant
∑
=
l
(cid:1) Calcul de n'est pas tractable
(
,
SOP
(cid:1) Complexité algorithmique exponentielle de O(TNT )
(
OP
)
)
S
l
(cid:1) Solution : procédure de calcul avant
a
(cid:1) Variables avant donne la probabilité d'observer la
to
séquence partielle du début jusqu'au temps t,
{
,1
o
K
,
}
)(it
a
i
)(
t
{
oP
(
1
,
K
,
}
so
,
t
t
=
l
)
S
i
t -a
)(it
(cid:1) Formulation récursive, est calculée à partir des
(cid:1) Eviter de répéter les calculs en stockant les résultats
a
j
)(1
intermédiaires.
144
ENSI--SI3
2014-2015
"
”
Procédure avant
(cid:1) Procédure pour calculer
a
=
i
)(
t
{
oP
(
1
,
K
,
}
so
,
t
t
=
l
)
S
i
1.
2.
Initialisation
a
=
i
)(
1
Etape récursive
soP
(
11
=
l
S
i
,
)
sP
(
1
=
l
S
i
)
=
p
ob
(
i
1
)
i
(cid:1) Pour chaque pas de temps t = 1,…,T-1, calculer les
(cid:1) Pour chaque pas de temps t = 1,…,T-1, calculer les
N
∑
{
(
oP
1
(
Publicité
ob
j
t
)(
j
K
}
,
o
t
s
t
=
=
=
S
+
1
+
1
+
1
+
1
l
a
)
)
,
,
j
t
t +a
t +a
a
t
j
)(1
)(1
j
)(
ai
,
ji
3. Terminaison
(
OP
l
=
)
(
sOP
T
,
=
S
i
l
=
)
i
a
)(
i
T
N
∑
=
1
i
N
∑
=
1
i
=
1
(cid:1) Complexité algorithmique de la procédure avant : O(N²T)
145
ENSI--SI3
2014-2015
Procédure arrière
(cid:1) Procédure arrière : version symétrique, basée sur une
b
variable
)(it
b
i
)(
t
{
oP
(
t
+ K
,
1
,
o
T
}
,
s
t
=
l
)
S
i
(cid:1) Procédure de calcul
1. Initialisation
1. Initialisation
b
2. Récursion
1)( =iT
(cid:1) Pour chaque pas de temps t = T-1, T-2,…,1, calculer les
b
)(it
b
i
)(
t
=
{
oP
(
t
K
,
,
o
T
+
1
}
,
s
t
=
l
)
S
i
N
∑=
=
1
j
oba
ji
j
t
,
(
+
1
b
)
j
)(
+
1
t
146
ENSI--SI3
2014-2015
”
Procédures avant et arrière
147
ENSI--SI3
2014-2015
Problème du décodage
}
(cid:1) Objectif : déterminer la séquence d‘états
la plus probable étant donné une séquence d'observations
{
ooO
2
{
, 2
ss
1
K,
K,
To
Ts
}
=
=
S
,
1
=
S
*
arg
max
S
lOSP
,
(
)
Calcul de S* directement avec cette formule n'est pas tractable,
(cid:1) Calcul de S* directement avec cette formule n'est pas tractable,
complexité de O(TNT ) !
complexité de O(TNT ) !
(cid:1) Algorithme de Viterbi
: probabilité maximale d'obtenir le début de la séquence
(cid:1)
d
)(it
d'observation, jusqu'au temps t
{
=
ooP
(
,
2
1
d
t
max
K
,
ss
,
s
,
1
(cid:1) Calculer récursivement pour t = 1,2,…,T
ss
,
1
i
)(
o
t
d
,
,
2
2
1
t
} {
,
K
)(it
K
}
,
1
s
t
s
t
=
l
i
)
148
ENSI--SI3
2014-2015
-
-
Problème de l'apprentissage du modèle
)
(cid:1) Objectif : déterminer les valeurs du modèle à
(
A=
l
,
,
{ }K
=c
iO 1=
i
partir d'un jeu de séquences d'observations
(cid:1) Solution par un maximum de vraisemblance
=
*
arg
lc
P
l
)
(
max
l
(cid:1) Comme la véritable séquence d‘état n'est pas observable, on
doit se contenter de probabilités
doit se contenter de probabilités
(cid:1) Similaire à un apprentissage non-supervisé, ou on ne connaît
pas les étiquettes des données
149
ENSI--SI3
2014-2015
P
B
Problème de l'apprentissage du modèle
(cid:1) Solution : algorithme de Baum-Welch :
Similaire a l'algorithme EM, pour des MMC
(cid:1) Etape E : estimer les probabilités d’être dans un certain état et
de faire une certaine transition à partir d'un modèle (λ).
(cid:1) Etape M : estimer les paramètres du modèle (λ) à partir des
probabilités d’être dans un état et de prendre une transition.
probabilités d’être dans un état et de prendre une transition.
λ
λ
150
ENSI--SI3
2014-2015
Matlab : modèles de Markov caches
(cid:1) Statistics Toolbox de Matlab implémente des algorithmes
pour traiter des MMC
(cid:1) HMMGENERATE : générer une séquence d‘états à partir d'un
MMC
(cid:1) HMMESTIMATE : estimer probabilité d'une séquence selon un
MMC (problème de l‘évaluation)
MMC (problème de l‘évaluation)
(cid:1) HMMVITERBI : déterminer la séquence d‘états la plus probable
pour une séquence d'observations (problème du décodage)
(cid:1) HMMTRAIN : déterminer probabilités de transition d'un MMC
à partir d'observations (problème de l'apprentissage du
modèle)
151
ENSI--SI3
2014-2015