7.1 Algorithme progressif-rétrograde
95
— Probabilité de lissage :
L
i (v) := P(U i = v | X 1:l = x 1:l ).
C’est la probabilité que l’état caché U i soit en position v connaissant
les observations X 1:l .
Pour calculer les probabilités de lissage, on utilise un algorithme progressifrétrograde
2 : on détermine par récurrence, dans le sens croissant des indices,
les probabilités de prédiction et de filtrage, puis on en déduit, toujours par
récurrence mais descendante, les probabilités de lissage. Les relations de récurrence nécessaires à cet algorithme sont rassemblées dans le théorème suivant.
Théorème 7.2 (Prédiction, filtrage, lissage). Pour tous 1 i l et v ∈ U,
P
i (v) =
u∈U
ρ(u, v)F
i−1 (u),
F
i (v) =
π v (x i−1 , x i )P
i (v)
u∈U π u (x i−1 , x i )P i (u)
,
L
i−1 (u) = F
i−1 (u)
v∈U
ρ(u, v)
L
i (v)
P i (v)
.
Démonstration. Pour l’équation de prédiction, on fait intervenir U i−1 puis
d’utiliser le fait que les lois Loi(U i | U i−1 , X 1:i−1 ) et Loi(U i | U i−1 ) coïncident :
P
i (v) =
u∈U
P(U i−1 = u, U i = v | X i− = x i− )
=
u∈U
P(U i = v | U i−1 = u, X i− = x i− )P(U i−1 = u | X i− = x i− )
=
u∈U
ρ(u, v)F
i−1 (u)
avec la notation allégée x i− := x 1:i−1 . L’utilisation de la relation de base
P(A | B ∩ C)P(B | C) = P(A ∩ B | C) permet de traiter l’équation de filtrage :
F
i (v) =
P(U i = v, X i = x i | X 1:i−1 = x i− )
P(X i = x i | X i− = x i− )
=
P(U i = v, X i = x i | X i− = x i− )
u∈U P(U i = u, X i = x i | X i− = x i− )
=
P(X i = x i | U i = v, X i− = x i− )P(U i = v, | X i− = x i− )
u∈U P(X i = x i | U i = u, X i− = x i− )P(U i = u | X i− = x i− )
.
Or par définition de la matrice de transition de (X, U ),
P(X i = x i | U i = u, X 1:i−1 = x 1:i−1 ) = P(X i = x i | U i = u, X i−1 = x i−1 )
2. En anglais : «forward-backward».