BARTHÉLEMY CABOUAT
THIBAULT MATHIEU
ENCADRÉS PAR JEAN-MARC BARDET
MAI 2014

Travail d’étude et de recherche :
Les chaînes de Markov cachées Table des matières
Introduction 2
Présentation générale 3
Chaînes de Markov 3
Propriété de Markov 3
Homogénéité 4
Noyaux de transition 5
Modèle de Markov caché 5
Définition 5
Exemple 7
Propriétés 9
Inférence 12
Estimateurs de paramètres : les MLE 12
Probabilité d’une séquence d’observations : l’algorithme Forward-Backward 15
Algorithme de Viterbi 17
Notations 17
Principe 18
Applications 20
Simulations Matlab 20
Inférence paramétrique 20
Algorithme de Viterbi 24
Application à la domotique 26
Conclusion 31
Bibliographie 32

Introduction

Les modèles de Markov cachés ont été introduits par Baum et son équipe dans les années 60. Ils sont apparentés aux automates probabilistes, c’est-à-dire définis par une structure composée d’états et de transitions ainsi que par un ensemble de distributions de probabilité sur ces transitions. Les chaînes de Markov cachées sont utilisées dans différents cadres, que ce soit au niveau des objectifs visés ou bien des espaces considérés (discrets, continus).
Les applications en sont nombreuses dans des domaines tels que le traitement du signal, la reconnaissance de la parole, le text mining (filtrage de spam, reconnaissance de parties de discours), la finance de marché, la bio-informatique, la physique quantique...
Notre objectif est de proposer une vue d’ensemble de la théorie des chaînes de Markov cachées à travers une première partie. Certains algorithmes classiques d’estimation seront exposés dans une deuxième partie avant de présenter quelques applications des chaînes de Markov dans une troisième et dernière partie. Présentation générale

Il est essentiel dans un premier temps de bien comprendre les objets qui seront étudiés dans ce TER. Pour cela, nous allons aborder les définitions théoriques des chaînes de Markov, notamment cachées, et énoncer certaines propriétés intéressantes qui orientent leur étude.

Chaînes de Markov

Propriété de Markov

Une chaîne de Markov est un processus stochastique à temps discret et états discrets X_n possédant la propriété de Markov, dont une définition est donnée ci-dessous :
Déf. 1.1. X_n vérifie la propriété de Markov faible si :

Où Edésigne l’espace des états possibles de X_n.
Cette propriété signifie que l’état futur d’une chaine de Markov ne dépend que de l’état actuel. Autrement dit, la connaissance des états passés n’apporte pas d’information utile supplémentaire pour la prédiction probabiliste du futur.
Exemple : soit E={soleil, pluie}
Les probabilités dites de transition (voir plus loin) sont : P(Soleil │Soleil)=0,7 ;
P(Pluie│Soleil)=0,3 ;
P(Pluie│Pluie)=0,6
P(Soleil│Pluie)=0,4
Les probabilité initiales sont : P(Soleil)=0,2 et P(Pluie)=0,8
Ainsi, la probabilité d’avoir la séquence {‘Soleil’,’Pluie’,’Soleil’,’Pluie’} est d’après la propriété de Markov : P(Soleil)*P(Pluie│Soleil)*P(Soleil│Pluie)*P(Pluie│Soleil) = 0,2*0,3*0,4*0,3=0,0072

D’autre part, on peut poser une hypothèse d’homogénéité sur la chaîne de Markov considérée :

Homogénéité

Déf 1.2. X_n est une chaîne de Markov homogène si :

Cette propriété correspond à une invariabilité des probabilités de transition par rapport au temps. Celle-ci permet notamment de définir la matrice de transition et les noyaux de transition :

Noyaux de transition

Déf 1.3. Si X_n est une chaîne de Markov homogène, on définit A sa matrice de transition d’un état vers un autre par :

Déf 1.4. L’état du processus à l’instant 1 est la loi de probabilité, notée π, de la variable X_1 :

Modèle de Markov caché

Définition

Dans les chaînes de Markov, les observations correspondent aux états du processus. Or dans un modèle de Markov caché, on ne peut pas observer directement les états du processus, mais seulement des symboles (aussi appelés observables) émis par les états selon une certaine loi de probabilité.
Au vu d’une séquence d’observation, on ne peut pas savoir par quelle séquence d’états (ou chemin) le processus est passé, d’où le nom de modèle de Markov caché (MMC).
On distingue le processus 〖X= X〗_1,X_2,…,X_n qui représente l’évolution des états du MMC et le processus O= O_1,O_2,…,O_n qui représente la suite des symboles émis par le MMC.

On définit différents éléments pour une chaîne de Markov cachée : n est le nombre d’états cachés du modèle. On note S = {s_1,s_2,…,s_n} l’ensemble des états caches; A l’instant t, un état est représenté par X_t 〖(X〗_tϵ S) m est le nombre de symboles distincts que l’on peut observer dans chaque état. On les représente par l’ensemble V = {v_1,v_2,…,v_m}. A l’instant t, un symbole observable est désigné par O_t

Une matrice de probabilité de transitions, notée A = [a_ij], où a_ij est la probabilité a priori de transition de l’état i vers l’état j. On définit a_ij= P(X_(t+1)= s_j │X_t= s_i ), 1 ≤ i, j ≤ n

Une matrice de distributions des probabilités, notée B=[b_jk], associée à chaque état où b_jk est la probabilité d’observer le symbole v_k en étant à l’état s_j à l’instant t. On définit b_jk= P(V_t= v_k │X_t= s_j )

Un vecteur π=[π_i] de distribution des probabilités de transitions initiales, où π_i est la probabilité de commencer à l’état i : π_i=P(X_1= s_i)
On peut dire qu’une chaîne de Markov cachée notée λ est définie complètement par λ = (A,B, π) car n et m sont sous-entendus dans les matrices A et B ainsi que le vecteur π.

La génération des observations dans une chaîne de Markov cachée se fait par la procédure suivante :
T=1 choix de l’état initial, X_1=s_i avec la probabilité π_i
Choix de l’observation O_t=v_k avec la probabilité b_ik
Transition vers le nouvel état X_(t+1) =〖 s〗_j avec la probabilité a_ij
T=t+1 ; si t≤T, alors retour à l’étape 2, sinon fin de procédure (avec T la longueur d’une suite d’observations)
Exemple

Une mère livre un livre dans le jardin et voit son enfant regarder la télévision. Les observations (faîtes par la mère) sont : {« dehors » ; « intérieur »} suivant que l’enfant joue « dehors » ou qu’il regarde la TV à l’ « intérieur ». Les états cachés de la chaîne de Markov sont {« émission »;« pub »} suivant que l’enfant regarde une émission TV ou la publicité.
La mère observe son enfant pendant une demi-journée depuis le jardin. A chaque heure, la mère observe son enfant. Elle a observé la séquence d’observations suivantes O : O={« intérieur » ; « dehors » ; « dehors » ; « intérieur » ; « dehors »}. On suppose qu’il est plus probable d’avoir de la « pub » après de la pub. Prenons comme probabilités de transition :
P(Pub │Pub)=0,8 ; P(émission │Pub)=0,2 ;
P(émission │émision)=0,6 ; P(Pub │émission)=0,4.
Les probabilités de distributions (ou d’émission) sont :
P(dehors │pub)=0,9 ;
P(intérieur │pub)=0,1 ;
P(dehors │émission)=0,3 ;
P(intérieur │émission)=0,7
Initialement, la probabilité de tomber sur une émission est plus grande : P(émission)=0,9.
Nous connaissons ainsi les matrices A et B ainsi que la distribution de probabilité initiale π.
Le graphe de la chaîne de Markov donne :

A partir de la séquence d’observations O={« intérieur » ; « dehors » ; « dehors » ; « intérieur » ; « dehors »}, nous pouvons résoudre trois problèmes que nous pouvons généraliser pour n’importe qu’elle séquence d’observations O= O_1,O_2,…,O_(T-1) : Le problème d’évaluation : soit une séquence d’observations O= O_1,O_2,…,O_(T-1) et un modèle λ = (A,B, π), comment calculer la probabilité que λ ait généré cette séquence O? Le problème de décodage : soit une séquence d’observations O= O_1,O_2,…,O_(T-1) et un modèle λ = (A,B, π), comment trouver la séquence la plus probable d’états 〖X= X〗_1,X_2,…,X_T qui a généré la séquence O ? Le problème d’apprentissage : soit une séquence d’observations O= O_1,O_2,…,O_(T-1) et une structure générique de modèle de Markov caché , comment trouver les paramètres de ce modèle (A,B et π) qui correspond au mieux aux séquences observées.

Ces problèmes seront résolus grâce aux différents algorithme que nous allons voir par la suite.
Propriétés

Une propriété intéressante des chaînes de Markov cachées est que étant donnée une séquence d’états (X_1,X_2,〖…,X〗_n), les observations (Y_1,Y_2,〖…,Y〗_n) sont conditionnellement indépendantes les unes des autres. Ceci semble assez naturel, car la connaissance d’une séquence d’états suffit pour déterminer la distribution de probabilités des observations : les observations n’ont pas d’influence directe entre elles, une fois la séquence d’états fixée.

Preuve. Il nous suffit ici de montrer que pour tout n-uplet de fonctions boréliennes définies sur (f_1,f_2,…〖,f〗_n), on a
E[∏_(i=1)^p▒〖f_i (Y_i ) 〗┤| X_1,〖…,X〗_n]=∏_(i=1)^p▒〖E[f_i (Y_i )┤| X_1,〖…,X〗_n]〗
Où Y désigne l’espace des valeurs possibles des Y_i.
On note y= (y_1,y_2…,y_n )∈Y^n et x= (x_1,x_2…,x_n )∈X^n
Or, pour tout n-uplet de fonctions boréliennes définies sur X (l’espace des états des X_i) (f_1,f_2,…〖,f〗_n) on a
E[∏_(i=1)^n▒〖f_i (Y_i ) 〗 h(X_1,〖…,X〗_n )]
=∑_(y ∈ Y^n,x ∈ X^n)▒〖[∏_(i=1)^n▒〖f_i (y_i )] 〗 h(x)P[(X_1,…,X_n)=x ∩ (Y_1,…,Y_n )=y]〗
=∑_(y ∈ Y^n,x ∈ X^n)▒〖[∏_(i=1)^n▒〖f_i (y_i )] 〗 h(x)[∏_(j=1)^n▒〖a_(x_j x_(j+1) ) b_(x_j y_(j ) ) 〗〗]
=∑_(y ∈ Y^n,x ∈ X^n)▒〖h(x)[∏_(j=1)^n▒〖f_j (y_j ) b_(x_j y_j ) 〗〗]∏_(j=1)^n▒a_(x_j x_(j+1) )
=∑_(y ∈ Y^n)▒〖∏_(j=1)^n▒〖f_j (y_j ) b_(x_j y_j ) 〗[∑_(x ∈ X^n)▒〖h(x)〗 ∏_(j=1)^n▒〖a_(x_j x_(j+1) )]〗〗
=∏_(j=1)^n▒∑_(y ∈ Y^n)▒〖f_j (y_j ) b_(x_j y_j ) [∑_(x ∈ X^n)▒〖h(x)〗 ∏_(j=1)^n▒〖a_(x_j x_(j+1) )]〗〗
=E_(X_1,〖…,X〗_n ) [h(X_1,〖…,X〗_n ) ∏_(i=1)^n▒∑_(y ∈ Y^n)▒〖f_j (y_j ) b_(x_j y_j )]〗
En particulier, si on pose h(X)=1/(P(X=x)) 1_({X=x}) , on a :
E[∏_(i=1)^n▒〖f_i (Y_i ) 〗 | (X_1,〖…,X〗_n )]
=E_(X_1,〖…,X〗_n ) [∏_(i=1)^n▒∑_(y ∈ Y^n)▒〖f_i (y_i ) b_(x_j y_j ) | (X_1,〖…,X〗_n )]〗
=∏_(i=1)^n▒〖E[ f_i (Y_i )|〗 (X_1,〖…,X〗_n )]
(On peut prouver l’indépendance en posant f_i (Y_i )=1_{Y_i=y_i } ∀ y_i.) Inférence

Les méthodes qui vont être présentées ici ont des buts différents.
On commencera par présenter les estimateurs de paramètres basés sur le maximum de vraisemblance, utiles dans le cadre des phases d’apprentissage.
On s’intéressera ensuite à deux cas faisant intervenir des algorithmes de calcul :
Dans un cas, il s’agira de calculer la probabilité d’obtenir une séquence d’observations donnée, lorsqu’on connaît les paramètres de la chaîne de Markov cachée (probabilités de transition, probabilités d’émission). L’algorithme forward-backward sera utile, et nous en profiterons pour aborder son utilisation dans le cadre de l’apprentissage.
Dans l’autre cas, l’inférence portera sur une suite d’états à déterminer à partir de la connaissance du modèle et d’une suite d’observations. Dans ce but, nous aborderons alors les méthodes de lissage ainsi que les méthodes de Monte Carlo utiles dans ce cadre.

Estimateurs de paramètres : les MLE

Dans cette partie, on s’efforcera d’estimer les paramètres du modèle de Markov caché considéré, c’est-à-dire les probabilités de transition de 〖(X〗_n) et les probabilités d’émission P(Y_k=a|X_k=i). Ce passage est indispensable si les paramètres sont inconnus, pour pouvoir passer à d’autres estimations. Dans les applications des chaînes de Markov cachées, on trouve presque toujours des phases d’apprentissage (training-testing) visant à approcher les valeurs des paramètres.
On cherche à maximiser les vraisemblances correspondantes aux paramètres considérés (MLE : Maximum Likelihood Estimators).
Une façon intuitive d’estimer les distributions des transitions de 〖(X〗_n) et les probabilités conditionnelles P(Y_k=a|X_k=i) est de compter le nombre de réalisations qui correspondent à ces transitions.

On définit ainsi les trois indicateurs suivants : C_X (i)=∑_(k=1)^n▒δ_(X_k,i) le nombre de fois où 〖(X〗_n) a pris la valeur i ; C_(Y,X) (a,i)=∑_(k=1)^n▒δ_(X_k,i) ×δ_(Y_k,a) le nombre de fois où 〖(X〗_n) a pris la valeur i en même temps que 〖(Y〗_n) a pris la valeur a ; C_(X,X) (i,j)=∑_(k=2)^n▒δ_(X_(k-1),i) ×δ_(X_k,j) le nombre de fois où 〖(X〗_n) a pris la valeur i avant de prendre la valeur j immédiatement ensuite.
Un estimateur de la probabilité de transition de l’état i vers l’état j serait alors :
T ̂_ij=(C_(X,X) (i,j))/(C_X (i) )
On a donc que 〖M ̂=(T ̂_ij)〗_(1≤i,j≤n).
Démontrer que cet estimateur maximise la vraisemblance se fait de la même façon que pour une chaîne de Markov non cachée, dans ce cas. On passera donc par une optimisation via la maximisation du Lagrangien sous la contrainte que la somme d’une distribution de probabilités vaut 1.

Preuve. On notera la séquence d’états x=(x_1,…,x_t,…,x_T)
La vraisemblance est ici définie par l(M)=log⁡P(x,M) =log⁡∏_(t=1)^T▒T_(x_(t-1) x_t )
=∑_(t=1)^T▒〖log⁡(T_(x_(t-1) x_t ))〗
Le problème d’optimisation est donc le suivant :
{█(max_M l(M)@∑_(j=1)^n▒〖T_ij=1〗 ∀i∈[|1..n|] (1)@T_ij≥0 ∀ (i,j)∈[|1..n|]^2 (2))┤

Avec des hypothèses suffisantes (espace convexe, fonction cible C^1 et/ou différentiable en tout point de cet espace, fonctions contraintes〖 C〗^1 dans l’intérieur de l’espace), on peut utiliser le Lagrangien pour trouver un maximum :
L(M,λ)=∑_(i=1)^n▒∑_(j=1)^n▒∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) log⁡(T_ij)〗+∑_(i=1)^n▒〖λ_i (1-∑_(j=1)^n▒T_ij )〗
∂L/(∂T_ij )=∂/(∂T_ij ) ∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) log⁡(T_ij ) 〗+∂/(∂T_ij ) λ_i (1-∑_(i=1)^n▒T_ij )
=1/T_ij ∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) 〗-λ_i
∂L/(∂T_ij )=0⟺T_ij=1/λ_i ∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) 〗
En injectant dans la condition (1) :
1-∑_(j=1)^n▒T_ij =0⟺1-∑_(j=1)^n▒〖1/λ_i ∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) 〗〗=0
⟺λ_i=∑_(j=1)^n▒∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) 〗 λ_i=∑_(t=1)^T▒δ_(X_(t-1),i) .
Ainsi, on obtient l’expression de l’estimateur maximisant la vraisemblance :
(T_ij ) ̂=(∑_(t=1)^T▒〖δ_(X_(t-1),i)×δ_(X_t,j) 〗)/(∑_(t=1)^T▒δ_(X_(t-1),i) ).

Ce résultat est assez intuitif, puisqu’il s’agit du ratio (nombre de fois où X est passé de i à j)/(nombre de fois où X est passé par l^' état i).

Un estimateur des probabilités d’émission est défini par :
Î(a,i)=(C_(Y,X) (a,i))/(C_X (i) )=(nombre de fois où X,dans l^' état i,a émis a)/(nombre de fois où X est passé par l^' état i)
Ces estimateurs sont les estimateurs maximisant la vraisemblance.

Probabilité d’une séquence d’observations : l’algorithme Forward-Backward

On se place dans le cadre où les paramètres suivants sont supposés connus : Les probabilités de transition, représentées par la matrice de transition A=(a_ij )_(0≤i,j≤n) où a_ij=P(X_k=s_j│X_(k-1)=s_i ) Les probabilités d’émission, représentées par la matrice de transition B=〖(b_ij)〗_(0≤i≤n)^(0≤j≤p) où a_ij=P(X_k=s_j│X_(k-1)=s_i )
Où p=Card(V) et n=Card(S).
La suite d’observations sera désignée par y=(y_1,…,y_t,…,y_T ) et la séquence d’états par x=(x_1,…,x_t,…,x_T ).
La probabilité d’observer y, étant donnés A et B, est alors :
P(y │A,B)= ∑_(x∈S^T)▒〖P(y,x ┤|A,B)〗
=∑_(x∈S^T)▒〖P[ (y│x) │ A,B] .P(x|A,B)〗
=∑_(x∈S^T)▒〖(∏_(t=1)^T▒〖P[(y_t│x_t ) │ A,B] 〗.∏_(t=1)^T▒〖P[(x_t│x_(t-1) )| A,B)]〗〗
Par la propriété de Markov ainsi que l’indépendance conditionnelle démontrée dans la première partie.
D’où P(y │A,B)=∑_(x∈S^T)▒〖(∏_(t=1)^T▒B_(x_t y_t ) .∏_(t=1)^T▒〖A_(x_(t-1) x_t ))〗〗.
Evaluer cette somme directement requiert de l’ordre de S^T opérations. Pour des modèles un minimum complexes, ceci n’est pas envisageable, et il va falloir avoir recours à des algorithmes performants pour effectuer le calcul. L’un d’eux, l’algorithme forward se base sur le fait que la probabilité d’une séquence peut se décomposer en envisageant tous les cas états finaux possibles pour une séquence d’états :
P(y │A,B)=P(y_1,…,y_t,…,y_T │A,B)
=∑_(i=1)^n▒〖P(y_1,…,y_t,…,y_T,x_T=s_i │A,B) 〗
≝∑_(i=1)^n▒〖α_i (T) 〗.
Les α_i (t) représentent alors la probabilité des t premières observations en supposant un état final〖 s〗_i. On peut les calculer de manière récursive, ce qui réduit grandement le nombre d’opérations nécessaires :
Initialisation.α_i (0)= A_0i,i=1…n
Récursion.α_i (t)=∑_(j=1)^n▒〖α_j (t-1) A_ji B_(iy_t ) 〗,i=1…n,t=1..T
La complexité de l’algorithme est alors O(S.T), ce qui est bien inférieur au O(S^T) initial.
Un algorithme similaire, l’algorithme backward, fonctionne dans le sens inverse en partant des dernières observations pour remonter jusqu’aux premières mais procède sur le même schéma et principe.

Algorithme de Viterbi

Si l’on suppose la donnée complète du modèle de Markov (paramètres, probabilités de départ, probabilités d’ignition) on peut chercher à estimer la séquence d’états ayant le plus probablement impliqué une suite observée. L’algorithme de Viterbi, que nous allons maintenant présenter, permet d’estimer une telle séquence en réduisant le nombre d’opérations nécessaires par un processus récursif.

Notations
Si n∈N*, on note x=(x_1,x_2,…,x_n ) la séquence d’états à estimer y=(y_1,y_2,…,y_n ) la suite d’observations q(i,j) la probabilité de transition d’un état i à un état j où (i,j)∈N² π_k=P(x_1=k) la probabilité de démarrer à l’état k dans la chaîne de Markov.

Principe

L’objectif est la maximisation de la vraisemblance de la séquence d’états, qui est ici la probabilité d’avoir suivi une séquence x en connaissant une séquence d’observation y et les paramètres du modèle λ :
L(x)=P(x|y,λ)
Calculer 〖max〗_x (L(x)) directement demande un nombre d’opérations beaucoup trop grand pour être envisageable (si S est le cardinal de l’espace des états de la chaîne de Markov, la complexité serait de l’ordre de (nS^n ) ).
Exemple. Supposons que la météo à Paris peut prendre trois états (ensoleillé, nuageux, pluvieux), et que selon la météo je décide chaque matin de prendre mon parapluie ou non. La concierge de mon immeuble (qui ne sort jamais, supposerons-nous pour l’occasion) me voit descendre avec ou sans mon parapluie chaque matin pendant une semaine. Elle aurait 15309 opérations à réaliser pour déterminer la séquence d’états de la météo la plus probable sur la semaine complète. En utilisant l’algorithme de Viterbi, elle n’en aurait que 63 !

L’idée est d’estimer pour chaque sous suite d’observations 〖(y〗_1),〖(y〗_1,y_2),〖(y〗_1,y_2,y_3)… 〖(y〗_1,…,y_n) les séquences d’états 〖(x〗_1),〖(x〗_1,x_2),〖(x〗_1,x_2,x_3)… 〖(x〗_1,…,x_n) ayant le plus probablement mené à ces sous-suites, en ne faisant varier à chaque fois que l’état final : une fois 〖(x〗_1) déterminé, on le garde en mémoire pour déterminer ensuite 〖(x〗_1,x_2), etc.

Initialisation.V_(1,k)=P(y_1 |k)×P(X_1=k)
Récursion.V_(t,k)=P(y_t |k)×〖max〗_x (T_xk×P(X_1=k))
A chaque fois qu’on passe en revue les x pour trouver celui qui établit le maximum, on le stocke en mémoire. En posant finalement〖 x〗_T=〖argmax〗_x (V_(T,x)), on retrouve la séquence d’états cachés ayant le plus probablement généré la séquence d’observations. Applications

Simulations Matlab

Afin de mettre en pratique les différentes méthodes décrites, nous avons utilisé le logiciel Matlab 2013 pour simuler des états et des observations de chaînes de Markov cachées discrètes, sur des longueurs variables et pour des paramètres donnés. Nous avons ainsi pu tester l’efficacité et la performance de l’estimation de paramètres et de l’algorithme de Viterbi.

Inférence paramétrique

En nous basant sur les estimateurs décrits en deuxième partie, voici le script écrit qui a permis d’approcher les paramètres (probabilités de transition et d’émission) : Ce script a été testé avec des performances satisfaisantes sur des modèles simples (2 états possibles pour la chaîne de Markov et 6 valeurs d’observations). L’erreur d’estimation sur les probabilités de transition était de 0.0259, et de 0.0212 pour les probabilités d’émission pour un échantillon de 1000 observations et états.

Erreur estimation des probabilités d’émission en fonction de la taille de l’échantillon

Algorithme de Viterbi

Une fois une chaîne de Markov générée, on peut chercher à résoudre le problème de décodage via l’algorithme de Viterbi. Voici le code utilisé pour cela, sur une chaîne de Markov avec les mêmes paramètres :

Les résultats associés montrent un taux de précision d’environ 60% sur la détermination des états cachés, quelle que soit la taille de l’échantillon choisie.

On peut se placer dans un cadre « post-apprentissage », où les paramètres ont été inférés, pour essayer de décoder les états cachés. Le différentiel des résultats de Viterbi est alors faible, bien que dépendant de l’apprentissage (ici réalisé avec l’inférence vu au premier point). Application à la domotique

T.L.M. van Kasteren, G. Englebienne, and B.J.A. Kröse ont réalisé en 2010-2011 une série d’expérimentations ayant pour but d’automatiser la reconnaissance d’activité humaine dans la maison et son identification. Dans ce cadre, 3 sujets vivant seuls ont été suivis pendant 25 jours dans leur logement. Une dizaine de capteurs ont été installés dans les meubles, placards, douches, cuisines… relevant des données comme la température, la pression, le mouvement (senseurs infrarouges), permettant de déterminer lorsque quelqu’un passait devant, ouvrait un tiroir, la fenêtre, tirait la chasse d’eau, etc. Plan des logements. Les capteurs sont signalés en rouge.
La façon de recueillir les données a été celle du « last-fired sensor », où pour ainsi dire la parole était donnée au capteur ayant en dernier changé d’état (lorsqu’un capteur émet un 1, tous ceux qui émettaient également 1 passent à 0 jusqu’à ce que le premier repasse à 0). Lorsqu’on oublie de fermer un placard avant de dormir, l’état du capteur associé resterait sur 1, ce qui induirait en erreur l’apprentissage des paramètres. Ici, seuls les changements d’états sont remarqués, ce qui permet de se repérer par rapport à des évènements plutôt qu’à des actions sur la durée.
Les données recueillies étaient binaires (pour les capteurs mesurant une grandeur, le basculement de 0 à 1 se faisait sur un seuil donné), toutes les 30 secondes. Après un benchmark, il s’est avéré que 30 secondes était une durée impliquant seulement 1% d’erreur due à la discrétisation du temps.
Plusieurs méthodes mathématiques ont été mis en place pour permettre de passer de ces mesures à la classification de l’activité humaine en cours : la méthode « Bayésienne naïve », la méthode des HMM, celle des HSMM (modèles semi-markoviens) et celle des -champs aléatoires conditionnels (CRF).
Nous allons nous intéresser à celle des HMM en particulier.
L’ensemble de ces symboles (un par capteur, soit une dizaine) relevés à un instant t correspond à une observation. Les états cachés à retrouver sont alors les activités humaines, qui ont été classifiées à l’avance en une douzaine de catégories.
Les données sont disponibles au téléchargement sur le lien suivant : https://sites.google.com/site/tim0306/datasets
Notre projet d’exploiter ces données pour évaluer la performance des HMM dans le cadre de l’expérience, en nous appuyant sur les données traitées, nettoyées et agencées par les auteurs, a cependant rapidement rencontré des embûches comme notamment la taille des données à traiter. En effet, il s’agit de 3 sujets, dont une douzaine de capteurs ont fourni une information toute les 30 secondes pendant 25 jours d’affilée, soit environ 54000 observations relevées et 648000 valeurs. Nos ordinateurs personnels ont alors eu du mal à effectuer la moindre opération sur ces données, même en utilisant des algorithmes performants comme celui de Viterbi.
On peut néanmoins commenter les résultats obtenus par les auteurs, qui ont pu aller jusqu’au bout du processus.
L’apprentissage des différents paramètres s’est fait sur la base du « leave one day out », c’est-à-dire que le set de données a été utilisé sur 24 jours pour estimer les paramètres de la chaine de Markov cachée, avant de tester l’adéquation de ces paramètres avec les résultats du 25e jour. En faisant tourner le jour utilisé pour les tests sur les 25, on peut encore consolider ces estimations.
Les performances des différentes modélisations ont été résumées en terme de précision, rappel, F-score dans les tables ci-dessous : La précision indique quel pourcentage des états signalés était juste, tandis que le rappel indique combien d’états justes ont été signalés sur leur nombre total.
Pour illustrer ces concepts, imaginons que j’ai pris 5 douches et que j’ai fait 6 fois la cuisine sur ces derniers jours. Un modèle estimant que j’ai pris 4 douches, à 4 instants parmi les 5 où j’ai effectivement pris des douches, aura une précision 100%, mais seulement 80% de rappel (4/5). Par contre, s’il estime en plus que j’ai pris 2 autres douches, mais qu’à un de ces instants je faisais en fait la cuisine, sa précision tombe à 83% alors que son rappel grimpe à 100%.
Toute performance d’estimation est donc un compromis entre précision et rappel, et le F-score permet de prendre en compte les scores dans ces deux domaines.
De ce point de vue, on remarque que les HMM ne déméritent pas face au modèle Naive Bayesian et Conditional Random Field, leur F-score étant généralement supérieur. Cependant, les modèles semi-markoviens (HSMM) signent de meilleures performances en général. La complexité accrue de ces modèles nécéssite cependant plus d’apprentissage, et plus de calculs pour aboutir à ces résultats.
On notera enfin que les CRF disposent d’une très bonne précision, malgré un faible rappel, les rendant très discriminants lorsqu’ils prennent une décision, même s’ils restent la plupart du temps indécis. Conclusion

Les chaînes de Markov cachées sont un procédé de modélisation particulièrement adapté aux situations de prises de décisions par déduction. Il s’agit de partir d’une observation, et de la comparer à une base d’apprentissage ou bien de calculer ce qui a pu la provoquer en terme probabilistes. La difficulté pour les mettre en place réside essentiellement en la capacité à identifier des systèmes bien décrits par des chaînes de Markov, et à en extraire des données pertinentes avant tout. De nombreux procédés de calcul permettent d’augmenter drastiquement les quantités de données qu’il est possible de prendre en compte. Avec l’augmentation des capacités de calcul, l’exactitude de ces modèles ne peut que s’améliorer, même si la première condition nécessaire pour cela reste de choisir judicieusement les variables à observer et les phénomènes à modéliser. Bibliographie KASTEREN T.L.M. van, ENGLEBIENNE G., KROSE B.J.A,
Human activity recognition from wireless sensor network data: Benchmark and software, 2011 RAMAGE Daniel, Hidden Markov Models Fundamentals, CS229 Section Notes. Stanford University, 2007 PARDOUX E., Processus de Markov et applications, 2006 LACOUR Claire, Estimation non paramétrique adaptive pour les chaînes de Markov cachées. Thèse de doctorat en mathématiques. Paris : université Paris Descartes, 2007 TREVEZAS Samis, Etude de l’estimation du maximum de vraisemblance dans des modèles Markoviens, semi-Markoviens et semi-Markoviens cachés avec applications. Thèse de doctorat en mathématiques. Compiègne : Université de Technologie de Compiègne, 2008