Inférence dans les chaînes semi-markoviennes cachées M-stationnaires

 Dans ce chapitre, nous étudions les méthodes d’estimation et de segmentation vues au chapitre précédent dans le cadre de deux modèles généralisant les chaînes de Markov cachées classiques. Ces deux modèles font partie de la famille générale de chaînes de Markov “triplets”. Nous commen¸cons par rappeler la famille des modèles de Markov “couples”, qui généralisent les modèles de Markov cachés. Nous introduisons ensuite les chaînes “triplets” [95, 102] et nous rappelons un de leurs intérêts, important pour les applications pratiques et développé récemment dans la thèse de P. Lanchantin [65], qui réside dans leur aptitude à traiter des données cachées non stationnaires. Dans un second temps, nous précisons les deux modèles particuliers introduits dans cette thèse. Le premier modèle est celui des chaînes semi-markoviennes, qui peuvent être vues comme des CMT particuliers. Nous présentons des résultats théoriques montrant que la semi-markovianité classique, o`u le temps aléatoire de séjour dans un état est à valeurs dans N, peut également se modéliser par un temps de séjour “minimal”. Nous définissons ainsi une sous-famille des modèles semi-markoviens cachés classiques et montrons leur intérêt, au niveau du temps de calcul, par rapport aux démarches fondées sur les chaînes semi-markoviennes classiques. Ensuite, nous étendons ce modèle au cas non stationnaire. L’intérêt des nouveaux modèles est validé par des expérimentations.

Chaînes de Markov couples et chaînes de Markov cachées 

Soit Z = (Xn, Yn)1≤n≤N un processus o`u chaque Xn prend ses valeurs dans un ensemble fini X = {ω1, . . ., ωK} et chaque Yn prend ses valeurs dans un R-espace vectoriel de dimension finie Y. Notons p(z1:N ) la densité de Z par rapport à la mesure produit (ν ⊗ λY) N , o`u ν est la mesure de décompte sur X et λY est la mesure de Lebesgue sur Y. Supposons que Z est une chaîne de Markov couple. D’après la factorisation de la loi de Z et l’équivalence entre factorisation et markovianité vue au chapitre 2, on en déduit que p(x1:N |y1:N ) et p(y1:N |x1:N ) sont des distributions markoviennes. La chaîne sera dite stationnaire si les densités p(zn, zn+1) ne dépendent pas de n.

Chaînes de Markov cachées M-stationnaires 

Le modèle

 Dans cette section, chaque Xn prend ses valeurs dans l’ensemble fini X = {ω1, . . ., ωK}, chaque Un prend ses valeurs dans l’ensemble fini Λ = {λ1, . . ., λM} et chaque Yn dans un espace vectoriel de dimension finie Y

Inférence dans le modèle de chaînes de Markov cachée Mstationnaires

 Nous détaillerons uniquement l’estimation des paramètres de la loi p(x1:N , u1:N ), l’estimation des paramètres de p(yn|xn) étant déjà étudiée au chapitre 2. Soit y1:N = (y1, . . ., yN ) la réalisation observée de Y . Les paramètres à estimer sont p(un+1|un) et p(xn+1|xn, un+1). Les estimations de p(un+1|un) et p(xn+1|xn, un+1) sont obtenues à partir de celle de p(xn, un, xn+1, un+1). Nous supposerons que la chaîne (X, U) est stationnaire et réversible, soit p(xn = ωi , un = λk, xn+1 = ωj , un+1 = λl) = p(xn = ωj , un = λl , xn+1 = ωi , un+1 = λk) et indépendant de n. Notons θq le vecteur paramètre obtenu à l’itération q de ICE. Afin d’estimer p(xn, un, xn+1, un+1), nous devons nous donner un estimateur à partir des données complètes (x1:N , u1:N , y1:N ).

Chaînes semi-markoviennes cachées 

Dans cette section, nous présentons les chaînes semi-markoviennes cachées et nous proposons d’écrire celles-ci comme un cas particulier de chaîne de Markov triplet. Les chaînes semimarkoviennes généralisent les chaînes de Markov pour des temps de séjour non nécessairement distribués suivant une loi géométrique. Parmi les applications du modèle semi-markovien, on peut citer la génétique [18, 25, 33], la reconnaissance vocale [42, 73, 83, 108], la reconnaissance de caractères [91, 109, 121], la segmentation d’images [41] ou l’analyse de modèles graphiques [52]. Nous commen¸cons par donner la définition générale d’une chaîne semi-markovienne cachée ainsi que certaines de ses propriétés. Une étude plus approfondie des propriétés des chaînes semi-markoviennes est disponible dans [8, 32, 75]. Dans un second temps, nous proposons un modèle semi-markovien particulier original. Nous verrons que ce nouveau modèle permet l’utilisation de l’algorithme de Baum-Welsh avec une complexité algorithmique réduite. Nous conclurons le chapitre par des expérimentations utilisant le modèle original de chaînes semi-markoviennes cachées M-stationnaires. 

Définition et propriétés d’une chaîne semi-markovienne

Nous choisissons de définir une chaîne semi-markovienne à valeurs dans un espace fini comme la marginale d’une chaîne de Markov. Une définition plus générale peut se trouver dans [74]. Définition 

(Chaîne semi-markovienne)

Soit X un ensemble fini. On définit les quantités suivantes : – la probabilité π sur X ; – la transition q(.|.) sur X 2 vérifiant q(x|x) = 0 ; – pour tout x ∈ X , les densités de probabilité d(x, .) sur N ∗ . Un processus X = (Xn)n≥1 tel que chaque Xn prend ses valeurs dans X est une chaîne semimarkovienne de loi initiale π, de transition q et de loi de durée d s’il existe un processus U = (Un)n≥1, o`u chaque Un prend ses valeurs dans N ∗ , tel que (X, U) soit une chaîne de Markov homogène Dans cette définition, on remarque que la transition q et la loi de temps de séjour d ne dépendent pas de n, la chaîne semi-markovienne est alors qualifiée d’“homogène”. Notons que un représente le temps de séjour restant de la chaîne dans Xn = xn, la variable aléatoire Un est appelée “temps de récurrence avant”.

Proposition 3.3.1. Soit X = (Xn)n≥1 un processus à valeurs dans un ensemble fini X = {ω1, . . ., ωK} de chaîne immergée X˜, soit V = (Vn)n≥1 la suite des instants de saut de X et soit T = (Tn)n≥1 le processus des temps de séjour. X est une chaîne semi-markovienne homogène de transition q et de loi de durée d si et seulement si les deux conditions suivantes sont satisfaites : 1. pour tout n, X˜ n+1 est indépendante des variables aléatoires X˜ 1, . . ., X˜ n, T1, . . ., Tn conditionnellement à X˜ n et la loi de X˜ n+1 sachant X˜ n ne dépend pas de n ; 2. pour tout n, Tn+1 est indépendante des variables aléatoires X˜ 1, . . ., X˜ n+1, T1, . . ., Tn conditionnellement à X˜ n+1 et la loi de Tn+1 sachant X˜ n+1 ne dépend pas de n. Sous ces conditions, la transition q et la loi de durée d sont données par : – q(ωj |ωi) = p(˜xn+1 = ωj |x˜n = ωi); – d(ωj , u) = p(tn+1 = u|x˜n+1 = ωj ).