Mise en oeuvre des MMCs

L'utilisation des MMCs en reconnaissance des formes s'effectue en trois étapes :

1. définition de la topologie de la chaîne de Markov, ce qui équivaut à construire un graphe dépendant de l'application visée (vocabulaire, syntaxe pour la RAP),

2. apprentissage du modèle : un des grands avantages de l'approche markovienne réside dans l'utilisation d'un apprentissage automatique des paramètres d'un modèle donné - quelle que soit la nature des observations (continues ou discrètes) -, ses paramètres sont optimisés de manière à maximiser la probabilité d'émission des observations données, une fois définie la topologie du modèle,

BA,,

3. reconnaissance : il s'agit, pour une suite Y= d'observations et un modèle

donné de définir :

– soit la vraisemblance d'une suite d'observations par rapport à un modèle ,

– soit de retrouver le chemin optimal , au sens probabiliste, c'est à dire la suite d'états cachés qui a vraisemblablement généré ces observations, parmi toutes les séquences s d'états possibles, soit :

Tyyy ,,........., 21

Tyy ,.......,Pr 1*s

YsYss

PrmaxargPr *

Mise en oeuvre des MMCs

D'après la formule de Bayes on a :

Remarquons que Pr(Y) ne dépend pas de la suite d'états s ; par conséquent la séquence qui donne la meilleure probabilité est celle qui maximise la probabilité conjointe Pr(Y,s) :

Pour résoudre les problèmes posés dans ces deux dernières étapes, deux algorithmes ont été développés,

- l'algorithme de Baum-Welch pour calculer la vraisemblance d'une suite d'observations,

- l'algorithme de Viterbi pour le calcul du chemin optimal.

YsY

YsPr,Pr

Pr

sYYss

,PrmaxargPr

Algorithme de Baum-Welch "avant-arrière"

• Soient une suite d'observations et soit un modèle donné, on définit deux variables et

- La variable avant (forward en anglais)

représente la probabilité d'observer les t premières observations et d'aboutir dans l'état au temps t.

- La variable arrière (backward en anglais)

représente la probabilité d'observer les t+1 dernières observations

sachant que l'on part de l'état au temps t

Tyyy ,,........., 21

iq

itti qXyyqt ,,.......,Pr, 1

,,.....,,Pr, 21 jtTttj qXyyyqt

jq

• Les variables forward et backward sont initialisées, pour

tous les états par :

La règle de Bayes permet un calcul récursif de ces deux variables :

pour t=2,...,T et

pour t=T-1,T-2,..,1et

,iq Ni1

1,1 ybq iii

1, iqT

tiji

Nj

jji ybaqtqt

1,1,

11

,1,

tjij

Nj

jji ybaqtqt

Ni1

Ni1

la vraisemblance de la suite d'observations par rapport au

modèle

Ni

iiT qTyy

11 ,,........,Pr

ii

Ni

iiT qybyy ,1,.....,Pr 1

11

Algorithme de Viterbi

• l'algorithme de Viterbi est utilisé pour la recherche du meilleur chemin, dans un graphe, ayant généré une suite d'observations selon un modèle

Il permet une réduction importante des calculs

Le chemin optimal recherché est défini par :

Tyyy ,,........., 21

,,.....,Prmaxmin

,,.....,Pr 11 TT yyche

yy

Détermination du chemin optimal

Soit la variable

le maximum, sur tous les chemins partiels possibles de

longueur t et aboutissant à l'état des probabilités

d'émission des t premières observations la probabilité d'émission le long du chemin optimal

recherché

La règle de Bayes nous donne la formule récurrente

suivante

pour t =1,...,T et pour j=1,...,N .

itiittiii

i qqqyyqt ,,...,,,...,Prmax,111

1,...,2,1

,iq

tyy ,...,1

ii

T qTyy ,max,,...,Pr 1

tjijii

j ybaqtqt },1max,

Détermination du chemin optimal

Pour déterminer le chemin optimal, on utilise une variable supplémentaire pour mémoriser, à chaque itération l'état correspondant au maximum :

l'état final du chemin optimal

la variable permet de retrouver les états précédents par une récurrence arrière :

…..

…

ijii

j aqtArgqt ,1max,

iiq

T qTq ,maxarg

.,.

TT qTq ,1

., 1 tt qtq

12 , TT qTq

., 10 qtq

Sélection d'un chemin dans le treillis entre les instants t - 1 et t

                                       

t-1 t       

Procédure d'apprentissage • L'apprentissage est une opération d'importance capitale pour un système

de reconnaissance, car le soin apporté à cette opération conditionne les performances du système. Un apprentissage incorrect ou insuffisant ne peut être compensé par la puissance des méthodes mises en jeu lors de la phase de reconnaissance. La procédure d'apprentissage se déroule en deux temps :

• le réseau markovien est construit c'est à dire que la structure du modèle, le nombre d'états ; les transitions entre états et le type de lois de probabilité définies pour les observations sont spécifiés a priori,

• la deuxième phase consiste à introduire dans les modèles markoviens les informations nécessaires contenues dans l'ensemble d'apprentissage, pour apprendre précisément les lois.

• Cette deuxième phase de la procédure d'apprentissage se réalise également en deux étapes :

- Initialisation des paramètres du modèle,- Ré-estimation de ces paramètres, à l'aide d'un procédé itératif.

Ré-estimation des paramètres

• L'estimation des paramètres des MMC la plus souvent utilisée en RAP, est l'estimation par maximum de vraisemblance, elle utilise la procédure de Baum-Welch ou celle de Viterbi.

• D'autres critères d'apprentissage existent, – critères MAP (Maximum A Posteriori),– MMI (Maximum Mutuel Information)

mais leur mise en oeuvre est généralement plus difficile.

Méthode de Baum-WelchÉtant donné l'ensemble d'apprentissage La procédure de Baum-Welch consiste à maximiser la vraisemblance

de ces observations par rapport aux paramètres du modèle.

Les paramètres optimaux du modèle sont ceux qui maximisent la probabilité d'émission de l'ensemble des observations

Pour la détermination des paramètres optimaux, on introduit une

fonction auxiliaire Q(.,.) définie par :

MYYY ,.....,1

nM

nY

1Prmaxarg

nY Mn1

,Prln,Pr, '1

' nnM

nYYQ

Méthode de Baum-Welch

• et deux modèles,

• chemin quelconque du réseau

• La formule de ré-estimation prend en considération pour chaque observation les informations le long de tous les chemins du réseau.

'