Allen-Leonard-These

Publié par

ADELE ALLEN LEONARD^ CHAINES DE MARKOV CACHEESEssaipresentea la Facultedesetudes superieuresde l’UniversiteLavalpour l’obtentiondugradedema^ tre es sciences (M. Sc.) DEPARTEMENT DE MATHEMATIQUES ET DE STATISTIQUEFAC ULTE DES SCIENCES ET GENIEUNIVERSITE LAVALQUEBECJUILLET 2001 R esumeLes modeles de Markov caches font partie d’un domaine de connaissancesassez recent. Un tel modele est en fait compose de deux parties distinctes, unecha^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 incluronsquelques exemples ainsi qu’une application qui en est faite par les ingenieursdans le domaine du traitement de la parole. Dans le dernier chapitre nouspresenterons brievement la methode du maximum de vraisemblance utiliseea n d’estimer les param etres du modele. Finalement, nous decomposeronsun exemple en trois parties et lui appliquerons une methode ne necessitantpas l’usage de l’informatique.|||||||||||- |||||||||||||-Claude Belisle Adele Allen LeonardDirecteur de recherche Etudianteii RemerciementsJe tiens premierement a remercier mon directeur de recherche, MonsieurClaude Belisle, professeur au Departement de mathematiques et statistiquede l’Universite Laval, pour sa disponibilite, ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 32
Nombre de pages : 49
Voir plus Voir moins

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 pour P qui
sera utile pour deriver certaines proprietes defYg quand m=2:
t
0 1 0 1

1 2 2 2
k k
@ A @ A
P = +!

1 2 1 1
o u !=1−(P +P ). En ce qui concerne le cas ou m=1,ilestdegenere
12 21
dans le sens qu’un modeledeMarkovcache aunetat est tout simplement
une sequence de variables aleatoires mutuellement independantes.
1.2 Esperance, variance et correlation
Le but de cette section est de deriver des expressions pour les moyennes,
variances, covariances et autocorrelations des deux modeles decrits prece-
demment.Toutd’abord,ilestnecessaire d’etablir deux resultats utiles par
la suite.
Premierement, soit une fonction quelconque de l’observation Y d’un modele
t
de Markov cache (MMC), disons f(Y ). Il est possible de calculer son esperance
t
en conditionnant sur X . Ceci nous donne le resultat suivant :
t
m m
X X
E[f(Y )] = E[f(Y )jX = i]P[X = i]= E[f(Y )jX = i] : (1.1)
t t t t t t i
i=1 i=1
5













Deuxiemement, soit une fonction de deux observations successives d’un MMC,
disons f(Y ;Y ). On peut calculer son esperance en conditionnant sur (X ;X .
t t+k t t+k
Cela nous donne :
m
X
E[f(Y ;Y )] = E[f(Y ;Y )jX =i; X = j]
t t+k t t+k t t+k
i;j=1
P[X = i; X = j]
t t+k
m
X
k= E[f(Y ;Y )jX =i; X = j] (P )
t t+k t t+k i ij
i;j=1
m
X
= E[f(Y ;Y )jX =i; X = j] P (k): (1.2)
t t+k t t+k i ij
i;j=1
Calculons maintenant les quantites mentionnees plus haut pour un MMC
dont la distribution conditionnelle afX = ig serait une Poisson de moyenne
t
.L’equation (1.1) nous permet d’obtenir
i
m
X
E[Y]= E[YjX = i]
t t t i
i=1
m
X
=
i i
i=1
0=
o u =( ; ;:::; ), ainsi que
1 2 m
m
X
2 2E[Y ]= E[Y jX = i]
t i
t t
i=1
m
X
2= ( + ) :
i i
i
i=1
6






Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.