Contributions aux méthodes de Monte Carlo

Rappels sur l’inférence bayésienne

Principe L’inférence bayésienne [17] considère un couple de variables aléatoires (x, y) de loi jointe p(x, y) (rappelons que l’on ne distingue pas en termes de notation les v.a. de leurs réalisations) où la v.a. x modélise une certaine quantité « cachée » (non directement observable) que l’on cherche à déterminer à partir de la v.a. y ∈ RDy , dépendante de x, dont on observe une réalisation. Cette modélisation trouve des applications dans de nombreux problèmes scientifiques, par exemple :
• pour un problème de localisation ou de poursuite la v.a. x pourra correspondre aux coordonnées cartésiennes de la cible et y à des mesures bruitées de position en coordonnées polaires, ou encore des mesures d’intensité de signal reçu [89, 48] ;
• un problème de segmentation d’images amènera à choisir x comme une classe (c’est-à-dire une v.a. discrète) à identifier à partir des pixels observés en niveau de gris y [75] ;
• en finance on pourra s’intéresser à l’estimation de la volatilité x en fonction des rendements passés y [16, Section 1.3.5] [78] ;
• un modèle de prévision météorologique considérera x comme une classe correspondant aux conditions climatiques avec y certaines données atmosphériques [7].
Dans la mesure où l’on cherche à estimer x à partir de y, la forme générale de notre estimateur s’écrit xb = g(y) et l’objectif consiste à construire la fonction g. Pour cela on commence par se donner une fonction de perte (ou fonction de coût) L à valeurs positives ou nulles, et plus précisément de RDx × RDx → R. Étant donné le caractère aléatoire de x et y, minimiser directement cette perte L(x, g(y)) n’a pas de sens et l’approche bayésienne s’attache donc à minimiser la perte moyenne (encore appelée « risque de Bayes ») E[L(x, g(y))]. Étant donné que E[L(x, g(y))] = E[E[L(x, g(y))|y]], on montre aisément que cette approche revient de manière équivalente à minimiser E[L(x, g(y))|y] pour tout y [82].
Estimateurs bayésiens usuels Nous mentionnons ci-dessous trois exemples d’estimateurs bayésiens obtenus à partir de trois fonctions de perte différentes. En pratique le choix et la pertinence de la fonction de perte dépendent de l’application et des objectifs considérés.

Méthodes de Monte Carlo par Chaînes de Markov

  Les méthodes de Monte Carlo par Chaînes de Markov (Markov Chain Monte Carlo – MCMC) offrent une alternative pour obtenir des échantillons suivant une certaine loi cible π (et par suite un estimateur des moments d’intérêt de π) sans pour autant tirer directement suivant π. La méthodologie est cette fois basée sur la construction d’une chaîne de Markov dont la loi stationnaire est π. Nous rappelons brièvement les principes de base des chaînes de Markov et des méthodes MCMC, puis présentons deux techniques MCMC bien établies : l’algorithme de Metropolis-Hastings (MH) en section 1.5.2 et l’échantillonneur de Gibbs en section 1.5.3 [82] [18].

Appauvrissement du support de trajectoires

   Bien que l’utilisation du rééchantillonnage permette de remédier au problème de dégénérescence des poids propre au mécanisme SIS, elle introduit (en plus de détériorer localement la variance de l’estimateur) un autre phénomène de dégénérescence. En effet le fait de resélectionner les trajectoires {xi0:t}Ni=1 à chaque fois que l’on effectue un rééchantillonnage a pour effet de supprimer entièrement les trajectoires non-sélectionnées et donc d’appauvrir considérablement l’historique de particules. Ainsi, après un certain nombre d’itérations temporelles seule une ou très peu de trajectoires ancêtres restent, c’est-à-dire que pour r < t suffisamment grand, l’ensemble {xit−r}Ni=1 ne contient qu’une seule ou très peu de particules différentes. Bien sûr, le rééchantillonnage appauvrit également le support courant à t. Ces effets de dégénérescence des trajectoires ont tendance à s’exacerber lorsque les poids intermédiaires issus du mécanisme NIS restent toujours très disparates malgré l’utilisation du rééchantillonnage ; plus précisément lorsque l’étape de pondération produit immédiatement des poids hétérogènes même en l’espace d’une unique itération temporelle, malgré l’utilisation de poids précédents wit−1 uniformes. Une telle disparité des poids survient lorsque le terme de correction p(xi0:t|y0:t) correspondant à la loi cible dans l’expression des poids admet un support sur x0:t très restreint et/ou très différent du terme qt(xi0:t) correspondant à la loi de proposition. En particulier, le mécanisme de filtrage particulaire souffre de ce problème lorsque la vraisemblance gt(·|xt), comme fonction de xt, admet un support très restreint, ou encore dans le cas de systèmes à grande dimension, c’est-à-dire où l’espace d’état des variables cachées xt est à grande dimension. Les travaux [95, 94, 8] montrent dans certains cas particuliers que pour garantir de ne pas avoir un seul poids non-nul, le nombre de particules doit croître exponentiellement en fonction de la variance des poids, laquelle est typiquement une fonction linéaire de la dimension de l’espace d’état. D’autres techniques de rééchantillonnage telles que le rééchantillonnage stratifié, résiduel ou autres alternatives au rééchantillonnage multinomial mentionnées en section 1.4.3, permettent de réduire la variance de l’estimateur SIR en comparaison du rééchantillonnage multinomial. Néanmoins, ces techniques souffrent toujours des mêmes problèmes de dégénérescence que le mécanisme rééchantillonnage multinomial en raison des duplications de trajectoires qu’elles effectuent. Afin de limiter spécifiquement ces problèmes, certaines techniques complémentaires au rééchantillonnage ont été proposées telles que la procédure de “resample-move” [27, 25]. Le resample-move réintroduit de la diversité dans le support courant et/ou passé de particules après une étape de rééchantillonnage par l’intermédiaire d’une procédure MCMC. L’idée, que nous ne détaillerons pas ici, consiste à modifier les particules et/ou trajectoires rééchantillonnées au moyen d’un noyau MCMC ayant pour cible la loi p(x0:t|y0:t). Les échantillons ainsi créés diversifient alors les particules/trajectoires précédemment dupliquées tout en respectant la même densité cible a posteriori. Un autre exemple de méthode de diversification est le filtrage particulaire régularisé [68].

Poursuite multi-cibles par mesures d’intensité de signal

   La poursuite multi-cibles est une tâche difficile qui a des applications dans plusieurs domaines, comme par exemple les réseaux de capteurs sans fil et la prédiction de mobilité des systèmes de transport intelligents. Dans ce contexte particulier, la structure principale d’un système comprend des nœuds cibles dont les états cinématiques sont inconnus et doivent être estimés ; ainsi que des nœuds capteurs qui reçoivent un certain type d’information bruitée provenant des nœuds cibles, à partir de laquelle il est possible de déduire une estimation de leur position. Diverses méthodes ont été développées afin de résoudre ce problème de localisation. Les méthodes basées sur la distance entre nœuds (par opposition aux méthodes non basées sur la distance, moins courantes) utilisent des mesures d’intensité de signal reçu (Received Signal Strength – RSS), temps d’arrivée de signaux (Time of Arrival – ToA) [40] ou angle d’arrivée de signaux (Angle of Arrival – AoA) [100] provenant des cibles. Ces deux approches par ToA et AoA produisent des estimations précises, ce qui permet une bonne localisation. Cependant l’approche ToA nécessite des horloges synchronisées au niveau des nœuds cibles, tandis que l’approche AoA nécessite une série d’antennes et reste sensible aux erreurs dues aux trajets multiples. Ce sont par conséquent des solutions coûteuses. La technique par intensité de signal reçu (RSS) [74] est beaucoup plus simple et directe, et présente de faibles coûts d’implémentation ; de ce fait, elle fait l’objet récurrent de tentatives d’optimisation de performances. La prise en compte de la corrélation des occultations (modèle de Gudmunson [39, 1]) entre différents nœuds (cibles ou capteurs) est un des moyens possibles pour améliorer cette technique. En effet, cela permet de tirer profit du fait que dans un environnement donné, la proximité implique plus ou moins la similarité du comportement en termes d’occultation. Quelques exemples de recherches comprennent [89] qui étudie la combinaison de la corrélation entre observations avec l’estimation par rétrécissement (“shrinkage”) de la matrice de covariance, ce qui entraîne une amélioration significative de la performance, mais reste limité au cas statique. Dans les travaux [66, 67, 29, 70], les corrélations entre observations sont prises en compte et des algorithmes de filtrage particulaire sont implémentés. Ceci permet une localisation relativement précise, mais ces algorithmes souffrent intrinsèquement des limitations propres à l’approche par filtrage particulaire dans le cas d’espaces d’état à grande dimension [95].

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1 Introduction aux méthodes de Monte Carlo 
1.1 Rappels sur l’inférence bayésienne
1.1.1 Principe
1.1.2 Estimateurs bayésiens usuels
1.2 Méthode de Monte Carlo brut
1.2.1 Principe
1.2.2 Méthodes de simulation
1.3 Échantillonnage d’importance
1.3.1 Échantillonnage d’importance non-normalisé
1.3.2 Échantillonnage d’importance normalisé
1.4 Échantillonnage d’importance avec rééchantillonnage 
1.4.1 Mécanisme
1.4.2 Propriétés des particules rééchantillonnées
1.4.3 Procédés alternatifs de rééchantillonnage
1.5 Méthodes de Monte Carlo par Chaînes de Markov 
1.5.1 Chaîne de Markov et principe MCMC
1.5.2 Algorithme de Metropolis-Hastings
1.5.3 Échantillonneur de Gibbs
2 Méthodes de Monte Carlo séquentielles 
2.1 Filtrage statistique et chaînes de Markov cachées 
2.1.1 Un problème de récursivité
2.1.2 Modèle de chaînes de Markov cachées
2.1.3 Calcul du filtre bayésien
2.2 Filtrage particulaire 
2.2.1 Principes
2.2.2 Aspects pratiques du filtrage particulaire
2.3 Filtrage particulaire auxiliaire 
2.3.1 Principe
2.3.2 Aspects pratiques
3 Alternatives à l’échantillonnage d’importance 
3.1 Échantillonnage d’importance normalisé à double loi de proposition
3.1.1 Introduction
3.1.2 L’estimateur DPIS
3.1.3 Une solution d’ajustement linéaire des échantillons
3.1.4 Simulations
3.2 Échantillonnage d’importance avec rééchantillonnage indépendant 
3.2.1 Introduction
3.2.2 L’estimateur SIR indépendant
3.2.3 Repondération des échantillons indépendants ?
3.2.4 Simulations
3.3 Conclusion 
4 Filtrage particulaire avec rééchantillonnage i.i.d. et semi-i.i.d. 
4.1 Filtrage particulaire avec rééchantillonnage indépendant
4.1.1 Un nouvel algorithme SIR
4.1.2 Lien avec le filtrage particulaire auxiliaire
4.1.3 Résumé
4.1.4 Simulations
4.2 Compromis coût/performance : rééchantillonnage semi-indépendant
4.2.1 Un procédé de rééchantillonnage intermédiaire
4.2.2 Performances vs. coût calculatoire
4.2.3 Une version parallélisable
4.2.4 Simulations
4.3 Conclusion 
5 Poursuite multi-cibles avec corrélations spatio-temporelles 
5.1 Problématique
5.1.1 Poursuite multi-cibles par mesures d’intensité de signal
5.1.2 Contributions et structure
5.2 Modèles d’état et d’observation
5.2.1 Modèle d’état et de mouvement des cibles
5.2.2 Modèle d’observations corrélées
5.3 Solution bayésienne proposée 
5.3.1 Inférence récursive
5.3.2 L’algorithme SMCMC proposé
5.3.3 Loi de proposition basée sur le gradient
5.4 Simulations 
5.4.1 Performance liée à la prise en compte des corrélations d’occultation
5.4.2 Performance de l’algorithme SMCMC comparé au filtrage particulaire
5.4.3 Performance de la loi de proposition gradient dans des scénarios difficiles et bruités
5.4.4 Performance de la loi de proposition gradient dans des scénarios plus faciles avec un nombre de particules variable
5.5 Conclusion 
Conclusion et perspectives
Annexes
A Preuves des résultats du chapitre 3
A.1 Preuve du Théorème 3
A.2 Preuve de la Proposition 4
A.3 Preuve de la Proposition 5
A.4 Preuve du Théorème 5
A.4.1 Convergence de BN
A.4.2 Convergence de AN
B Preuves des résultats du chapitre 4
B.1 Preuve de la Proposition 7
B.2 Preuve de la Proposition 8
B.2.1 Preuve de l’inégalité (4.46c)
B.2.2 Preuve de l’inégalité (4.46d)
B.3 Commentaires et étoffements sur ces propositions et preuves
Bibliographie

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *