Introduction au filtrage en temps discret

Description

Universit´e de Rennes 1Master Recherche SISEAIntroductionau Filtrage en Temps DiscretFiltrage de Kalmanet Mod`eles de Markov Cach´esFran¸cois Le GlandINRIA Renneshttp://www.irisa.fr/aspi/legland/2010–11Table des mati`eres1 Introduction 11.1 Importance de l’information a priori . . . . . . . . . . . . . . . . . . . . . . 11.2 Prise en compte de l’information a priori . . . . . . . . . . . . . . . . . . . 62 Syst`emes lin´eaires gaussiens 153 Filtre de Kalman, et extensions 193.1 Filtre de Kalman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Extensions au cas non–lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . 254 Syst`emes non–lin´eaires non–gaussiens, et extensions 29´4.1 Equations d’´etat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29´4.2 Equations d’´etat et d’observation . . . . . . . . . . . . . . . . . . . . . . . 315 Filtre bay´esien optimal 335.1 Repr´esentation probabiliste . . . . . . . . . . . . . . . . . . . . . . . . . . 33´5.2 Equation r´ecurrente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.3 Approximation particulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 Mod`eles de Markov cach´es 416.1 Chaˆınes de Markov a` ´etat fini . . . . . . . . . . . . . . . . . . . . . . . . . 416.2 Mod`eles de Markov cach´es . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 Equations forward / backward de Baum 477.1 Equation forward . . . . . . . . ...

Informations

• Publié par: Shyam
• Nombre de lectures: 22
• Langue: Français

Extrait

Universit´edeRennes1 Master Recherche SISEA

Introduction au Filtrage en Temps Discret

Filtrage de Kalman etMod`elesdeMarkovCache´s

Franc¸oisLeGland INRIA Rennes http://www.irisa.fr/aspi/legland/

2010–11

Tabledesmati`eres

1 Introduction 1 1.1 Importance de l’information a priori . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Prise en compte de l’information a priori . . . . . . . . . . . . . . . . . . . 6

2Syste`mesline´airesgaussiens

15

3 Filtre de Kalman, et extensions 19 3.1 Filtre de Kalman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2Extensionsaucasnon–lin´eaire.........................25

4Syst`emesnon–line´airesnon–gaussiens,etextensions29 ´ 4.1Equationsd’´etat................................29 ´ 4.2Equationsd’e´tatetd’observation.......................31

5Filtrebaye´sienoptimal33 5.1Repre´sentationprobabiliste..........................33 ´ 5.2Equationr´ecurrente...............................35 5.3 Approximation particulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

6Mode`lesdeMarkovcache´s41 6.1ChaˆınesdeMark`e´tatfini.........................41 ov a 6.2Mod`elesdeMarkovcach´es...........................42

7 Equations forward / backward de Baum 47 7.1 Equation forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2 Equation backward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

i

8

9

A

Algorithme de Viterbi

Formules de re–estimation

Rappels

de

probabilit´es

de

Baum–Welsh

55

61

65

Chapitre 1

Introduction

Lefiltrageconsiste`aestimerl’e´tatd’unsyste`medynamique,c’est–a`–dire´evoluantau coursdutemps,a`partird’observationspartielles,ge´n´eralementbruite´es. Typiquement, on dispose d’une suite (Y 1  Y 2    Y n noitbo,sunetpaseesr`)d’observa traitementpr´ealabledusignalbrutrecueilliauniveaudescapteurs.Chaqueobservation Y n nocnune´’litati´el`aeetresX n par une relation probabiliste du type P[Y n ∈dy|X n =x] =g n (x y)dy  par exemple Y n =h(X n ) +V n  avec unbruitadditifV n nipe´dadneedtnX n tion.Poure’rruedro’sbreav,qmouield´elis allerplusloin,ilestn´ecessairedede´finirpluspr´ecis´ementlanotiondebruit. On trouvera a`l’AnnexeAlesrappelsdeprobabilit´esdontonaurabesoindanscecours.

1.1 Importance de l’information a priori

Telqu’ilestformul´e,leprobl`emedel’estimationdel’´etatinconnuX n pa`esrdtiar observations (Y 1  Y 2    Y n se)gnet´ne´laremal–pos´e.Pours’neocvniacnerc,noonerd´sis lecastre`ssimpleou`iln’yapasdedynamiquedansl’e´volutiondel’e´tatdusyst`eme, c’est–a–dire queX n ≡x, pour toutn, etx∈R m .unnocnierte`marneigesd´Onestunpa ` parx 0 equseisnocssupuopo,snerenplifiladicoreludapelrueiavvaarrsim.Pouetreram` les observationsd–dimensionnelles (Y 1  Y 2    Y n te`m.erai´emereduntrapad)e´epdnneltni On a donc Y n =H x+V n  ou`Hest une matriced×m.

1

2

Master Recherche SISEA 10/11

•Sim=dee´rracceriatamilts,eHtconsid´ererl’esislb,elaroospnuerevnitseamitruet suivant xb n =H −1 ( 1 n X n Y k ) =H −1 (H x 0 + n 1 X n V k ) =x 0 +H −1 1 ( n n X V k ) k=1k=1k=1 Sousl’hypothe`se 1 n X n V k −→0(1.1) k=1 quand le nombrend’observations tend vers l’infini, on obtient la convergence de l’estimateurxb n srevrdupaleuaievlavr.ee`rtrama •Sim > dola,elsrborpme`lsteeg´en´eenlmralap–soe´m,eˆemadnslecasfavorable ou`lamatriceHlaa`tsemangradeegl´maxid.oCe´orsndieffetnsenobl`elmeepr d’optimisation suivant n 2 x m ∈R in m  1 2 X |Y k −H x|   k=1 Lesconditionsd’optimalit´edupremierordrepourlaminimisationparrapporta ` x∈R m du critere ` n n n 1 2 X |Y k −H x| 2 = 1 2 X |Y k | 2 −x ∗ H ∗ ( X Y k ) +n 2 1 x ∗ H ∗ H x  k=1k=1k=1 s’´ecrivent n H ∗ H x=⇒H x= 1 n Y k  H ∗ X Y k = n n X k=1k=1 compte tenu que la matriceHesuertdecslan.Dinlegpan`o,tnede´ce´rpsam=d et la matriceHest inversible, on obtient la solution unique b −1 1 ( n x n =H n X Y k ) k=1 Danslecasconsid´ere´ici,ilyaunnombreinfinidesolutions,etonpeutseulement affirmer que bx n ∈  x∈R m :H x 1 = X n Y k   n k=1 Onv´erifieque 1 n Hb n x X Y k =H x 0 1 + n n X V k  n = k=1k=1 et`alalimitequandlenombrend’observations tend vers l’infini, on obtient sous l’hypoth`ese(1.1) Hbx n −→H x 0 

FiltragedeKalmanetMode`lesdeMarkovCach´es

3

c’est–a`–direqu’asymptotiquement,lorsquelebruitd’observationae´te´e´limin´epar moyennisation,onsaitseulementqueleparame`treinconnuxappartient au sous– espace affineI(x 0 ) de dimension (m−dpanir)´dfie I(x 0 ) =  x∈R m :H x=H x 0   L’existenced’unnombreinfinidesolutionspossiblesn’estdoncpaslie´ea`lapre´sence dubruitd’observation.Elleexistemˆemeenabsencedebruitd’observation,c’est– a`–diremeˆmesiV n ≡0, pour toutn= 12 .  •l’ineverourlPetd´miertinaonx∈I(x 0 amitnosspulpe´-utiliserdesinforno,)asse’dey mentairessurleparame`treinconnux, par exemple :xestprochedeetsr`–c–,aei’d qu’on introduit une informationa priori peut formaliser la prise en compte de. On cetteinformationsupple´mentaireenconsid´erantleprobl`emed’optimisationsuivant n x m ∈R in m  1 2 X |Y k −H x| 2 + 2 1 (x−) ∗ Σ −1 (x−)   k=1 o`uΣestunematricesyme´triqued´efiniepositive,dedimensionm conditions. Les d’optimalite´dupremierordrepourlaminimisationparrapporta`x∈R m `tirerecud n 2 1 X |Y k −H x| 2 + 1 2 (x−) ∗ Σ −1 (x−) k=1 n n = 1 2 X |Y k | 2 −x ∗ H ∗ ( X Y k ) +n 1 2 x ∗ H ∗ H x k=1k=1 + 2 1  ∗ Σ −1 −x ∗ Σ −1 + 1 2 x ∗ Σ −1 x 

s’e´crivent

n H ∗ ( X Y k ) + Σ −1 = (n H ∗ H+ Σ −1 )x k=1 =⇒(H ∗ H+ n Σ 1 −1 )x=H ∗ ( 1 n n X Y k ) + n 1 Σ −1   k=1 Enutilisantler´esultatduLemme1.1ci–dessous,aveclechoixR=IetQ=nΣ, on obtient (H ∗ H 1 + n Σ −1 ) −1 =nΣ−nΣH ∗ (HΣH ∗ + 1 n I) −1 HΣ Onende´duitque (H ∗ H+ n Σ 1 −1 ) −1 H ∗ = ΣH ∗ (HΣH ∗ + 1 n I) −1 