Modèle de Markov cachée Hidden Markov Model (HMM)

Markov Formellement, une chaîne de Markov vériﬁe la propriété de Markov, à savoir: "Sachant le présent, le futur est indépendant du passé" Une façon très simple de construire une chaîne de Markov (X n) n≥0 est de se donner une suite de variables aléatoires Y n,n ≥ 1 indépendantes, et indépendantes de X 0, et de poser: (1 1

Les chaînes de Markov, la distribution des firmes suivant

tique à chaque ligne de B, elle est -ainsi indépendante de la distri bution d'origine Ainsi, d'après les modèles utilisant des chaînes de Markov, la concentration des firmes résulte d'une distribution stationnaire de leur taille due à la mobilité de ces entreprises La matrice A est un indicateur de la mobilité des firmes au cours d'une

Théorèmes limites pour les processus de Markov à sauts

nombres pour les processus de Markov (Darling, 2002; Darling et al , 2005) Dans les mêmes conditions, il existe aussi un théorème central limite qui permet l’approxima-tion des processus de Markov par des diffusions (Kurtz, 1971; Allain, 1976; Gilles-pie, 2000) Lorsqu’une ou plusieurs espèces moléculaires ont des faibles

Introduction - Université libre de Bruxelles

n jn2Ngest une chaîne de Markov, et écrire sa matrice de transition Exercice 3 Soit une chaîne de Markov fX n jn2Ngd'ensemble d'états Eet de matrice de transition P Pour chaque état i2E, notons ˝ i la durée d'une visite en i(si X 0 = i, ˝ i est donc le moment où la chaîne de Markov quitte pour la première fois cet état i

Modèle de Markov cachée Hidden Markov Model (HMM)

Modèle de Markov Un processus de Markov est un processus stochastique possédant la propriété de Markov La prédiction du future, sachant le présent, nʼest pas plus précise si des informations supplémentaire concernant le passé deviennent disponibles Séquence d’observations Modèle du premier ordre

Théorèmes limites pour les processus de Markov à sauts

4 L’objet Volume 8 – n˚2/2005 2 Modélisation par des systèmes de réactions chimiques, processus de Markov à sauts 2 1 Processus de Markov à sauts, quelques rappels

TP n°5 - Gaunard

Utiliser la commande précédente pour (ré)-écrire une fonction y=Exemple_bis(n)faisant la même chose mais beaucoup plus courte 2 2 Blabla théorique • On considère une suite de variables aléatoires (Xn) Lorsque la loi de Xn+1 (le futur) ne dépend que de l’état Xn (présent), on dit que (Xn) est une chaîne de Markov

f

n 0 une chaine de Markov à aleursv dans un ensemble E ni ou dénombrable et de probabilité de transition ˇ On note F n la tribu engendrée par les ariablesv aléatoires X 0;X 1; ;X n On souhaite montrer la propriété de Markov forte Dans la suite T désigne un temps d'arrêt ni 1 Enoncer précisément la propriété forte de Markov

Conception et réalisation d’un vériﬁcateur de modèles AltaRica

Réseau de Petri Chaîne de Markov Simulation stochastique Disponibilité Système de transitions Model checking Compilation automatique vers Mec 4, au LaBRI (2000) Compilation automatique vers Lustre, au LaBRI (2003) Compilation manuelle vers SMV, au CERT Conception et realisation d’un v´ eriﬁcateur de mod´ eles AltaRica – p 3/43`

Exercice arbres de décision

n Construire l'arbre de décision à partir des données suivantes en utilisant l'algorithme ID3.

n Rappel: 2

Présence Interaction avec le prof Mange à Noël Réussite Régulière Pose des questions Dinde Oui Régulière Ne pose pas de questions Canard Non Absence Pose des questions Dinde Non Régulière Pose des questions Canard Oui Régulière Ne pose pas de questions Dinde Non Régulière Ne pose pas de questions Canard Oui

Source: http://dolques.free.fr/enseignement/2012/IA/CFAI/exo.pdf c i ii ppSEntropie 1 2 log)( ∑

AValeursv

v v

SEntropie

S S

SEntropieASGain

Problème de la compression/dilation du temps

Topologies typiques

4 Comment estimer les probabilités associés à la machine à états finis? 5

Modèle de Markov

n Un processus de Markov est un processus stochastique possédant la propriété de Markov La prédiction du future, sachant le présent, nest pas plus

précise si des informations supplémentaire concernant le passé deviennent disponibles. n Séquence d'observations n Modèle du premier ordre

6 Ref: http://fr.wikipedia.org/wiki/Chaîne_de_Markov

Modèle de Markov

Typiquement représenté par une machine à états finis 7 P (q 1 N (q 2 S (q 3

0.6 0.4 0.8 0.3 0.1 0.2 0.3 0.2 0.1

Probabilités de transition: Probabilités initales: !=[p(q1),p(q2),p(q3)]

Balles dans des urnes

n N urnes et balles de différentes couleurs n Un génie joue une partie:

¨ Il choisit une urne au hasard. ¨ Il choisit une balle au hasard d'une urne. ¨ Il prend en note la couleur de la balle comme étant une observation. ¨ Il retourne la balle dans l'urne. ¨ Il répète l'opération et génère une séquence d'observations de

couleurs. 8

Simple HMM à états discrets

Correspond à un simple HMM

¨ Probabilité de l'état initial: probabilité de la sélection étant à l'urne i ¨ Probabilité d'observation: probabilité de choisir une couleur n

sachant qu'elle provienne de l'urne i ¨ Probabilité de transition: probabilité de choisir une couleur de l'urne i étant donné que le choix précédent provenait de l'urne j 9 q 1 q 2 q 3

0.6 0.4 0.8 0.3 0.2 0.2 0.1 0.1 0.3

Probabilité d'observation (3 couleurs) États (3 urnes)

Définition d'un HMM

n N: nombre d'états dans le modèle ¨ États: ¨ État au temps t: n T: nombre d'observations/trames ¨ Symboles d'observations: ¨ Observation au temps t: n Distribution de prob. de transition d'états:

¨ Transition entre l'état s

i au temps t et l'état s j au temps t+1: ¨ Ensemble de toutes les transitions d'états: 123
T

Ooooo=L

Définition d'un HMM

n Distribution de prob. d'observation o k

à l'état j:

¨ Ensemble de toutes les observations:

n Distribution des états initiaux:

¨ Ensemble de tous les états initiaux:

n Un HMM est décrit par: ()() 1, 1 jktj 11

Génération des observations

1. Choisir un état initial à partir de la distribution des états initiaux

2. Pour t =1 à T

1. Choisir o

t en fonction de la probabilité d'observation d'un symbole à l'état i :

2. Faire une transition à un nouvel état en fonction de la

probabilité de transition d'états 12

Représentation sous forme de treillis des HMM

n Chaque noeud du treillis est l'événement où une observation o t est générée alors que le modèle occupait l'état s i 13

3 Problèmes de base des HMM

1. Évaluation:

1. Problème: calculer la probabilité d'observation de la séquence

d'observations étant donnée un HMM:

2. Solution: Forward Algorithm

2. Décodage:

1. Problème: trouver la séquence d'états qui maximise la

séquence d'observations

2. Solution: Viterbi Algorithm

3. Entraînement:

1. Problème: ajuster les paramètres du modèle HMM afin de

maximiser la probabilité de générer une séquence d'observations à partir de données d'entraînement

2. Solution: Forward-Backward Algorithm

Évaluation

n doit être évaluée pour toutes les séquences d'états Q={q 1 ,q 2 ,q T } possibles: n Avec T observations et N états dans le modèle: ¨ N T séquences d'états possibles ¨ Approximativement T*N T opérations requises 15 Exemple: Pile ou face avec deux pièces de monnaie États p(États) p(FPP|États) Résultat q 0 ,q 0 ,q 0

0.50.50.5=0.125 0.50.50.5=0.125 0.015625 q

0 ,q 0 ,q 1

0.50.50.5=0.125 0.50.50.6=0.150 0.01875 q

0 ,q 1 ,q 0

0.50.50.5=0.125 0.50.60.5=0.150 0.01875 q

0 ,q 1 ,q 1

0.50.50.5=0.125 0.50.60.6=0.180 0.0225 q

1 ,q 0 ,q 0

0.50.50.5=0.125 0.40.50.5=0.100 0.0125 q

1 ,q 0 ,q 1

0.50.50.5=0.125 0.40.50.6=0.120 0.015 q

1 ,q 1 ,q 0

0.50.50.5=0.125 0.40.60.5=0.120 0.015 q

1 ,q 1 ,q 1

0.50.50.5=0.125 0.40.60.6=0.125 0.018

16 q 0 q 1

0.5 0.5 0.5 0.5

P(FPP) : 0.136125 O={Face,Pile,Pile}

Forward Algorithm

n Une approche plus efficace pour évaluer n Définissons .... n ... comme étant la probabilité d'observations o 1

à o

t avec la séquence d'états qui se termine à l'état q t =s i pour l'HMM 17

1. Initialisation:

2. Induction: 3. Terminaison:

Avec T observations et N états, ceci requiert environ N 2

T opérations

Forward Algorithm

19 o t o t+1 1j Nj s j 20 q 0 q 1

0.50.5 0.50.4 0.0619 0.1125 0.135 0.0743

Face Pile Pile

0.50.25 0.50.1125 0.50.2 0.50.135 0.1361

q 0 q 1

0.5 0.5 0.5 0.5

Backward Algorithm

n Une approche efficace pour évaluer dans la direction inverse n Définissons n comme étant la probabilité d'observations o t+1

à o

T avec la séquence d'états qui se termine à l'état q t =s i pour l'HMM 21
n Initialisation: n Induction: n Terminaison: n n Avec T observations et N états, ceci requiert environ N 2

T opérations

22
o t+1 ,o t+2 ,o M 23
24
q 0 q 1

1.0 0.55 0.3025 1.0 0.3025 0.55

Pile Pile

0.50.50.55 0.50.51.0 0.50.60.55 0.50.61.0 0.1361

q 0 q 1

0.5 0.5 0.5 0.5

Face

3 Problèmes de base des HMM

1. Évaluation:

¨ Problème: calculer la probabilité d'observation de la séquence d'observation étant donnée un HMM:

¨ Solution: Forward Algorithm

2. Décodage:

¨ Problème: trouver la séquence d'état qui maximise la séquence d'observations

¨ Solution: Viterbi Algorithm

3. Entraînement:

¨ Problème: ajuster les paramètres du modèle HMM afin de

maximiser la probabilité de générer une séquence d'observation à partir de données d'entraînement

¨ Solution: Forward-Backward Algorithm

25
Problème de décodage: chercher la séquence optimale d'états

n Critère d'optimalité: choisir la séquence d'états qui maximize la probabilité en utilisant l'algorithme de Viterbi

26
Problème de décodage: chercher les séquences optimales d'états n Définissons ... n comme étant la probabilité conjointe des observations o 1

à o

t et la séquence d'états q 1 q 2 q 3 ...q t se terminant à l'état q t =s i

étant donné l'HMM

n Nous pouvons montrer par induction que: 27
28

Algorithme de Viterbi

n Cumuler les probabilités de chemins maxima: n Garder la trace des meilleures séquences : 29

Exemple Viterbi

Séquence d'observation: GGCACTGAA

30
q 0 q 1 -0.737 -1 -1 -1.322

G G C A C T G A A

q 0 -2.737 -5.474 -8.211 -11.533 -14.007 -17.329 -19.540 -22.862 -25.658 q 1 -3.322 -6.059 -8.796 -10.948 -14.007 -16.481 -19.540 -22.014 -24.488

Séquence : q

1 q 1 q 1 q 2 q 2 q 2 q 2 q 2 q 2 Source :Exemple de Didier Gonze adapter de Borodovsky & Ekisheva (2006), p. 80- 81

3 Problèmes de base des HMM

1. Évaluation:

¨ Problème: calculer la probabilité d'observation de la séquence d'observation étant donnée un HMM:

¨ Solution: Forward Algorithm

2. Décodage:

¨ Problème: trouver la séquence d'état qui maximise la séquence d'observations

¨ Solution: Viterbi Algorithm

3. Entraînement:

¨ Problème: ajuster les paramètres du modèle HMM afin de

maximiser la probabilité de générer une séquence d'observation à partir de données d'entraînement

¨ Solution: Forward-Backward Algorithm

Entraînement des HMM

n Consiste à entraîner les paramètres du modèle HMM afin de maximiser la probabilité

n L'entraînement se fait avec l'algorithme Forward- Backward qui est aussi appelé l'algorithme Baum-Welch 32

Algorithme Forward-Backward

n Soit un modèle HMM initial, , estimons un nouvel ensemble de paramètres du modèle de telle sorte que

n Utilisons les probabilités forward et backward pour ce faire; n Et l'algorithme d'expectation-maximization:

¨ EM Algorithm

Réestimation des paramètres

n Définissons n comme la probabilité d'être à l'état s i au temps t et à l'état s j au temps t+1 étant donné le modèle et la séquence d'observations O 34
35

Réestimation des paramètres

n Définissons de nouvelles probabilités a posteriori à partir de n Nombre de transitions à partir de s i

¨ Exprimée en fréquence relative

n Nombre de transitions de s i

à s

¨ Exprimée en fréquence relative

n Nous allons utiliser ces probabilités pour ré-estimer les paramètres HMM 36

Réestimation des paramètres

n Probabilité des états initiaux: n Probabilités de transition: n Probabilités d'observations 37

Réestimation des paramètres

38
quotesdbs_dbs13.pdfusesText_19

[PDF] Modèle de Markov cachée Hidden Markov Model (HMM)

Exercice arbres de décision

AValeursv

SEntropie

SEntropieASGain

Problème de la compression/dilation du temps

Topologies typiques

Modèle de Markov

6 Ref: http://fr.wikipedia.org/wiki/Chaîne_de_Markov

Modèle de Markov

0.6 0.4 0.8 0.3 0.1 0.2 0.3 0.2 0.1

Balles dans des urnes

Simple HMM à états discrets

Correspond à un simple HMM

0.6 0.4 0.8 0.3 0.2 0.2 0.1 0.1 0.3

Définition d'un HMM

¨ Transition entre l'état s

Ooooo=L

Définition d'un HMM

à l'état j:

¨ Ensemble de toutes les observations:

¨ Ensemble de tous les états initiaux:

Génération des observations

1. Choisir un état initial à partir de la distribution des états initiaux

2. Pour t =1 à T

1. Choisir o

2. Faire une transition à un nouvel état en fonction de la

Représentation sous forme de treillis des HMM

3 Problèmes de base des HMM

1. Évaluation:

1. Problème: calculer la probabilité d'observation de la séquence

2. Solution: Forward Algorithm

2. Décodage:

1. Problème: trouver la séquence d'états qui maximise la

2. Solution: Viterbi Algorithm

3. Entraînement:

1. Problème: ajuster les paramètres du modèle HMM afin de

2. Solution: Forward-Backward Algorithm

Évaluation

0.5*0.5*0.5=0.125 0.5*0.5*0.5=0.125 0.015625 q

0.5*0.5*0.5=0.125 0.5*0.5*0.6=0.150 0.01875 q

0.5*0.5*0.5=0.125 0.5*0.6*0.5=0.150 0.01875 q

0.5*0.5*0.5=0.125 0.5*0.6*0.6=0.180 0.0225 q

0.5*0.5*0.5=0.125 0.4*0.5*0.5=0.100 0.0125 q

0.5*0.5*0.5=0.125 0.4*0.5*0.6=0.120 0.015 q

0.5*0.5*0.5=0.125 0.4*0.6*0.5=0.120 0.015 q

0.5*0.5*0.5=0.125 0.4*0.6*0.6=0.125 0.018

0.5 0.5 0.5 0.5

P(FPP) : 0.136125 O={Face,Pile,Pile}

Forward Algorithm

à o

1. Initialisation:

2. Induction: 3. Terminaison:

T opérations

Forward Algorithm

0.5*0.5 0.5*0.4 0.0619 0.1125 0.135 0.0743

Face Pile Pile

0.5*0.25 0.5*0.1125 0.5*0.2 0.5*0.135 0.1361

0.5 0.5 0.5 0.5

Backward Algorithm

à o

T opérations

1.0 0.55 0.3025 1.0 0.3025 0.55

Pile Pile

0.5*0.5*0.55 0.5*0.5*1.0 0.5*0.6*0.55 0.5*0.6*1.0 0.1361

0.5 0.5 0.5 0.5

3 Problèmes de base des HMM

1. Évaluation:

¨ Solution: Forward Algorithm

2. Décodage:

¨ Solution: Viterbi Algorithm

3. Entraînement:

¨ Solution: Forward-Backward Algorithm

à o

étant donné l'HMM

Algorithme de Viterbi

Exemple Viterbi

Séquence d'observation: GGCACTGAA

G G C A C T G A A

Séquence : q

0.50.50.5=0.125 0.50.50.5=0.125 0.015625 q

0.50.50.5=0.125 0.50.50.6=0.150 0.01875 q

0.50.50.5=0.125 0.50.60.5=0.150 0.01875 q

0.50.50.5=0.125 0.50.60.6=0.180 0.0225 q

0.50.50.5=0.125 0.40.50.5=0.100 0.0125 q

0.50.50.5=0.125 0.40.50.6=0.120 0.015 q

0.50.50.5=0.125 0.40.60.5=0.120 0.015 q

0.50.50.5=0.125 0.40.60.6=0.125 0.018

0.50.5 0.50.4 0.0619 0.1125 0.135 0.0743

0.50.25 0.50.1125 0.50.2 0.50.135 0.1361

0.50.50.55 0.50.51.0 0.50.60.55 0.50.61.0 0.1361