Allen-Leonard-These

Informations

• Publié par: Racin
• Nombre de lectures: 25
• Langue: Français

Extrait

ADELE ALLEN LEONARD
^ CHAINES DE MARKOV CACHEES
Essai
presente
a la Facultedesetudes superieures
de l’UniversiteLaval
pour l’obtention
dugradedema^ tre es sciences (M. Sc.)
DEPARTEMENT DE MATHEMATIQUES ET DE STATISTIQUE
FAC ULTE DES SCIENCES ET GENIE
UNIVERSITE LAVAL
QUEBEC
JUILLET 2001






R esume
Les modeles de Markov caches font partie d’un domaine de connaissances
assez recent. Un tel modele est en fait compose de deux parties distinctes, une
cha^nedeMarkov ametats et un ensemble de m vecteurs de probabilites,
chacun etant associe aundesetats.
Dans cet essai, nous presenterons tout d’abord le modele general avec sa no-
tation et ses nombreuses proprietes. Dans le second chapitre, nous inclurons
quelques exemples ainsi qu’une application qui en est faite par les ingenieurs
dans le domaine du traitement de la parole. Dans le dernier chapitre nous
presenterons brievement la methode du maximum de vraisemblance utilisee
a n d’estimer les param etres du modele. Finalement, nous decomposerons
un exemple en trois parties et lui appliquerons une methode ne necessitant
pas l’usage de l’informatique.
|||||||||||- |||||||||||||-
Claude Belisle Adele Allen Leonard
Directeur de recherche Etudiante
ii











Remerciements
Je tiens premierement a remercier mon directeur de recherche, Monsieur
Claude Belisle, professeur au Departement de mathematiques et statistique
de l’Universite Laval, pour sa disponibilite, son encadrement et son soutien
tant moral que nancier.
Ensuite, je voudrais remercier tous les professeurs et tous les professionnels
du departement de m^eme que tous mes collegues etudiants et etudiantes
pendant ces quelques annees passees a l’Universite Laval. Ils m’ont permis
de ne pas me decourager et de mener a terme mon projet de ma^ trise.
Finalement, il me reste a souligner ma reconnaissance a tout mon entourage,
ma famille, mes amis, pour leur support enorme, leurs encouragements et
leur con ance en moi tout au long de mes etudes.
iii








Table des matieres
1 Introduction 1
1.1 Notations............................. 3
1.2 Esperance, variance et correlation..... 5
1.3 Proprietesdistributionneles........13
2 Applications 18
2.1 Serieschronologiquesbinaires..................18
2.2 Applicationautraitementdelaparole.............25
3 Estimation des parametres 32
3.1 Methodedumaximumdevraisemblance............32
3.2 Exemplesimpled’estimation...................35
3.2.1 VariablesdeBernouli .......35
3.2.2 Cha^nedeMarkov .........36
3.2.3 ModeledeMarkovcache.................38
iv


Chapitre 1
Introduction
Les cha^ nes de Markov sont connues des math ematiciens et des ingenieurs
depuis le debut des annees 1900. Plus recemment, ils se sont interesses aun
nouveau concept : les modeles de Markov caches. Dans un modele de Markov
cache, nous avons connaissance d’une certaine sequence d’observations mais
on ne sait pas exactement de quelle facon les observations ont ete produites.
En fait, la sequence d’observation depend d’une sequence d’etats, sous-jacente
et non observee, tiree d’une cha^nedeMarkovavecespaced’etats ni. Pour
chacun des etats, il y a une distribution de probabilite nous permettant
d’obtenir une observation.
Un exemple avec quatres pieces de monnaie nous permet de bien comprendre
la presence du processus sous-jacent. Considerons deux individus, l’individu
A et l’individu B,lepremieretant cache derriere un rideau. L’individu A
dispose de quatre pieces de monnaie : deux pieces rouges, disons la piece R1
avec probabilitedepileegale a p et la piece R2 avec probabilite de pile
R1
egale a p ,etdeuxpieces noires, disons la piece N1 avec probabilite de pile
R2
1












egale a p et la piece N2 avec probabilitedepileegale a p . Achaque
N1 N2
etape, ou unite de temps, l’individu A lance une des deux pieces rouges et
une des deux pieces noires et il annonce le resultat du lancer de la piece noire
a l’individu B. Achaqueetape, ou unite de temps, l’individu A choisit les
pieces qu’il lance selon les regles suivantes. Regle 1 : Si al’etape t−1ila
obtenu une face avec la piece rouge, alors il lance al’etape t la m^eme piece
rouge qu’il a lancee al’etape t− 1; sial ’etape t− 1 il a obtenu une pile
avec la piece rouge, alors il lance al’etape t l’autre piece rouge. Regle 2 :
Achaqueetape, il lance la piece noire N1siillancelapiece rouge R1etil
lance la piece noire N2siillancelapiece rouge R2.
Supposons que les probabilites p et p sont petites, de sorte que l’individu
R1 R2
A ne change pas souvent de pieces. Supposons egalement que la probabilite
p est petite et que la probabilite p est grande. L’individu B observe alors
N1 N2
une sequence de piles et de faces qui consiste en des longs blocs comprenant
surtout des piles en alternance avec des longs blocs comprenant surtout des
faces. L’objectif de l’individu B est de modeliser ce phenomene aleatoire et
d’estimer les parametres du modele.
Dans cet essai, nous decrirons d’abord le modele utilise. Ensuite, nous expo-
serons quelques exemples et applications, notamment dans le traitement de
la parole. Finalement, nous nous pencherons sur l’estimation des parametres
du modele.
2


















1.1 Notations
Dans cet essai, l’ensemble des entiers positifsf1; 2; 3; :::g sera denote N.Soit
X =(X;t2N ) une cha^ ne de Markov homogene et ergodique (c’est- a-
t
dire irreductible et aperiodique) sur l’espace d’etats S =f1; 2;:::;mg,avec
matrice de transition P. On a donc P =(P;1 i m; 1 j m)
ij
o u P = P(X = jjX = i) pour tout temps t 1etquelsquesoient
ij t+1 t
les etats i et j dans S. Etant donnelapropriete d’ergodicitede
X ,onsait
qu’il existe une distribution stationnaire unique et strictement positive que
l’on notera =( ; ;:::; ). Dans cet essai, on supposera toujours que
1 2 m
la cha^nedeMarkov
X est stationnaire. Autrement dit, on suppose que la
variable aleatoire X est distribuee selon la loi stationnaire . Il s’en suit que
1
la suite de variables aleatoires =(X :t2N) est une suite stationnaire.
t
Soit =(Y;t2N) un processus aleatoire a valeurs entieres non-negatives
t
(T)tel que, conditionnellement a X =(X;t=1;:::;T), les variables aleatoires
t
(Y : t=1;:::;T) sont mutuellement independantes, c’est-a-dire
t
P[(Y ;:::;Y )=(y;:::;y )j(X;:::;X )=(i;:::;i )]
1 T 1 T 1 T 1 T
= P[Y = y j(X ;:::;X )=(i;:::;i )]
1 1 1 T 1 T
P[Y =yj(X;:::;X )=(i;:::;i )]:
T T 1 T 1 T
De plus, ce processus aleatoire doit satisfaire la condition suivante :
(T)P[Y = yjX =(i;:::;i ;i;i ;:::;i )] = P[Y = yjX = i]= ;
t 1 t−1 t+1 T t t t yi
pour tout 1 t T.
Dans la suite de ce chapitre, deux types de modeles seront consideres. Pour
le premier, la distribution conditionnelle de Y sera une Poisson et pour le
t
3






Y
X





6
second, ce sera une binomiale. Dans le premier cas,L(YjX = i) est une Pois-
t t
son avec moyenne .L’esperance conditionnelle de Y sachant X , E[YjX ],
i t t t t
P
n
est alors donnee par (t)= Z (t)ou Z(t)=1siX=iet 0 sinon.
i i i t
i=1
Dans ce cas, la loi de Y sachant X = i ne depend pas de t,maisseulement
t t
de i.
y
−
ie
i= = P(Y = yjX = i)= ;
t yi yi t t
y!
et ce pour tout entier non-negatif.
Dans le deuxieme cas,L(YjX = i) est une binomiale avec parametres n et p
t t t i
o un est un entier positif connu. On a donc queL(YjX)=Binomiale(n ;p(t))
t t t t
P
m
o u p(t)= p Z (t), Z (t) etant de nie comme dans le cas de la distribu-
i i i
i=1
tion Poisson. Dans ce cas, nous avons

n
t y
n −y
t= P(Y = yjX = i)= p(1− p )
t yi t t i
iy
o u y prend les valeurs 0; 1;:::;n.
t
2Dans chacun des deux modeles ci-haut, il y a m parametres permettant
de speci er le mod ele de Markov cachee ( ; ):soitmparametres ou
i
2p selon le modele choisi ainsi que m − m probabilites de transition P ,
i ij
2c’est-a-dire les elements hors-diagonale deP.Cesm−melements doivent
P
cependant satisfaire les m contraintes P 1, une pour chaque i,des
ij
j=i
contraintes de non-negativite. Dn plus, les parametres doivent satisfairent
i
la contrainte 0etlesparametres p doivent satisfairent la contrainte
i i
0 p 1.
i
Un cas particulier du modele general est celui ou m = 2. Dans ce cas, la
4






Y
X








matrice de transition deP peut s’ecrire sous la forme
0 1
1−P P
12 12
@ A
P = :
P 1−P
21 21
La condition d’ergodiciteestequivalente alacondition
0<P +P < 2 et la distribution stationnaire est donnee par
12 21

P P
21 12
=( ; )= :
1 2
P +P P +P
12 21 12 21
kDe plus, par diagonalisation de P, on obtient une expression