96
7 Chaînes de Markov cachées
= π ui−1 (x i − 1, x i ).
Pour l’équation de lissage, on écrit
P(U i−1 = u, U i = v | X 1:l = x 1:l ) = P(U i−1 = u | U i = v, X 1:l = x 1:l )
P(U i = v | X 1:l = x 1:l ),
puis
P(U i−1 = u | U i = v, X 1:l = x 1:l )
=
P(U i−1 = u, X 1:i−1 = x 1:i−1 , X i+1:l = x i+1:l | U i = v, X i = x i )
P(X 1:i−1 = x 1:i−1 , X i+1:l = x i+1:l | U i = v, X i = x i )
.
La propriété de Markov assure que, conditionnellement au présent, le passé
et le futur sont indépendants. On obtient donc après simplification que
P(U i−1 = u | U i = v, X 1:l = x 1:l ) = P(U i−1 = u | U i = v, X 1:i = x 1:i ).
On écrit, à nouveau, grâce à l’expression de la matrice de transition de (X, U ),
P(U i−1 = u | U i = v, X 1:i = x 1:i )
=
P(U i−1 = u, U i = v, X i = x i , | X 1:i−1 = x 1:i−1 )
P(U i = v, X i = x i | X 1:i−1 = x 1:i−1 )
=
F
i−1 (u)ρ(u, v)π v (x i−1 , x i )
P i (v)π v (x i−1 , x i )
.
On a donc obtenu
P(U i−1 = u, U i = v | X 1:l = x 1:l ) = F
i−1 (u)ρ(u, v)
L
i (v)
P i (v)
,
ce qui fournit la relation de lissage en sommant sur v.
On initialise l’algorithme en choisissant pour P
1 (u) la loi initiale (par
exemple la loi stationnaire). Les relations de prédiction et filtrage du théorème 7.2 permettent de calculer toutes les probabilités P
i et F
i par récurrence progressive. On en déduit ensuite les probabilités L
i par récurrence
rétrograde grâce à la relation de lissage du théorème 7.2 avec l’initialisation
L
l (v) = F
l (v). La figure 7.1 illustre l’efficacité de l’algorithme : la plupart du
temps la probabilité L
i (v) est supérieure à 1/2 quand U i = v (dans 95,2%
des cas exactement dans cet exemple). On voit toutefois dans cet exemple que
l’algorithme rate une zone où U vaut 1 (aux alentours de 120) et qu’il a toujours un peu de retard aux changements de régimes. L’algorithme fonctionne
d’autant mieux que les matrices π 0 et π 1 sont différentes (les deux régimes
ont des comportements très différents) et que ρ(0, 0) et ρ(1, 1) sont grands
(les plages entre deux changements de régime sont longues).
7 Chaînes de Markov cachées
= π ui−1 (x i − 1, x i ).
Pour l’équation de lissage, on écrit
P(U i−1 = u, U i = v | X 1:l = x 1:l ) = P(U i−1 = u | U i = v, X 1:l = x 1:l )
P(U i = v | X 1:l = x 1:l ),
puis
P(U i−1 = u | U i = v, X 1:l = x 1:l )
=
P(U i−1 = u, X 1:i−1 = x 1:i−1 , X i+1:l = x i+1:l | U i = v, X i = x i )
P(X 1:i−1 = x 1:i−1 , X i+1:l = x i+1:l | U i = v, X i = x i )
.
La propriété de Markov assure que, conditionnellement au présent, le passé
et le futur sont indépendants. On obtient donc après simplification que
P(U i−1 = u | U i = v, X 1:l = x 1:l ) = P(U i−1 = u | U i = v, X 1:i = x 1:i ).
On écrit, à nouveau, grâce à l’expression de la matrice de transition de (X, U ),
P(U i−1 = u | U i = v, X 1:i = x 1:i )
=
P(U i−1 = u, U i = v, X i = x i , | X 1:i−1 = x 1:i−1 )
P(U i = v, X i = x i | X 1:i−1 = x 1:i−1 )
=
F
i−1 (u)ρ(u, v)π v (x i−1 , x i )
P i (v)π v (x i−1 , x i )
.
On a donc obtenu
P(U i−1 = u, U i = v | X 1:l = x 1:l ) = F
i−1 (u)ρ(u, v)
L
i (v)
P i (v)
,
ce qui fournit la relation de lissage en sommant sur v.
On initialise l’algorithme en choisissant pour P
1 (u) la loi initiale (par
exemple la loi stationnaire). Les relations de prédiction et filtrage du théorème 7.2 permettent de calculer toutes les probabilités P
i et F
i par récurrence progressive. On en déduit ensuite les probabilités L
i par récurrence
rétrograde grâce à la relation de lissage du théorème 7.2 avec l’initialisation
L
l (v) = F
l (v). La figure 7.1 illustre l’efficacité de l’algorithme : la plupart du
temps la probabilité L
i (v) est supérieure à 1/2 quand U i = v (dans 95,2%
des cas exactement dans cet exemple). On voit toutefois dans cet exemple que
l’algorithme rate une zone où U vaut 1 (aux alentours de 120) et qu’il a toujours un peu de retard aux changements de régimes. L’algorithme fonctionne
d’autant mieux que les matrices π 0 et π 1 sont différentes (les deux régimes
ont des comportements très différents) et que ρ(0, 0) et ρ(1, 1) sont grands
(les plages entre deux changements de régime sont longues).