Particle smoothing is useful for offline state inference and parameter learning in nonlinear/non-Gaussian state-space models. However, many particle smoothers, such as the popular forward filter/backward simulator (FFBS), are plagued by a quadratic computational complexity in the number of particles. One approach to tackle this issue is to use rejection-sampling-based FFBS (RS-FFBS), which asymptotically reaches linear complexity. In practice, however, the constants can be quite large and the actual gain in computational time limited. In this contribution, we develop a hybrid method, governed by an adaptive stopping rule, in order to exploit the benefits, but avoid the drawbacks, of RS-FFBS. The resulting particle smoother is shown in a simulation study to be considerably more computationally efficient than both FFBS and RS-FFBS. / CNDM / CADICS

We consider the smoothing problem for a class of conditionally linear Gaussian state-space (CLGSS) models, referred to as mixed linear/nonlinear models. In contrast to the better studied hierarchical CLGSS models, these allow for an intricate cross dependence between the linear and the nonlinear parts of the state vector. We derive a Rao-Blackwellized particle smoother (RBPS) for this model class by exploiting its tractable substructure. The smoother is of the forward filtering/backward simulation type. A key feature of the proposed method is that, unlike existing RBPS for this model class, the linear part of the state vector is marginalized out in both the forward direction and in the backward direction. / CNDM / CADICS

La géolocalisation indoor en temps réel a largement été étudiée ces dernières années, et de nombreuses applications y sont associées. Une estimation en temps différé de la trajectoire présente également un certain intérêt. La géolocalisation indoor en temps différé permet par exemple de développer des approches de type crowdsourcing qui tirent profit d'un grand nombre d'utilisateurs afin de récolter un grand nombre de mesures : la connaissance du trajet d'un utilisateur muni d'un smartphone permet par exemple d'alimenter une carte de fréquentation du bâtiment. Estimer la trajectoire de cet utilisateur ne nécessite pas de traitement en temps réel et peut s'effectuer en temps différé ce qui offre deux avantages. D'abord, l'approche temps réel estime une position courante uniquement avec les mesures présentes et passées, alors que l'approche temps différé permet d'avoir accès à l'ensemble des mesures et permet d'obtenir une trajectoire estimée plus régulière et plus précise qu'en temps réel. Par ailleurs, cette estimation peut se faire sur un serveur et n'a pas besoin d'être portée par un smartphone comme c'est le cas en temps réel, ce qui permet d'utiliser une puissance de calcul et un volume mémoire plus importants. L'objet de ces travaux de thèse est de proposer une estimation de la trajectoire d'un individu se déplaçant avec un smartphone recevant des mesures de puissance wifi ou bluetooth (RSS) et enregistrant des mesures inertielles (IMU). En premier lieu, sans la connaissance de la position des murs de la carte, un modèle paramétrique est proposé, basé sur un modèle de propagation d'onde adaptatif pour les mesures RSS ainsi que sur une modélisation par morceaux de la trajectoire inertielle, issue des mesures IMU. Les résultats obtenus en temps différé ont une moyenne d'erreur de 6.2m contre 12.5men temps réel. En second lieu, l'information des contraintes de déplacement induites par la présence des murs du bâtiment est ajoutée et permet d'affiner l'estimation de la trajectoire avec une technique particulaire, comme il est couramment utilisé dans la littérature. Cette seconde approche a permis de développer un lisseur particulaire ainsi qu'un estimateur du maximum a posteriori par l'algorithme de Viterbi. D'autres heuristiques numériques ont été présentées. Une première heuristique ajuste le modèle d'état de l'utilisateur, qui est initialement uniquement basé sur les mesures IMU, à partir du modèle paramétrique développé sans les murs. Une seconde heuristique met en œuvre plusieurs réalisations d'un filtre particulaire et définit deux scores basés sur les mesures RSS et sur la continuité de la trajectoire. Les scores permettent de sélectionner la meilleure réalisation du filtre. Un algorithme global, regroupant l'ensemble de ces approche permet d'obtenir une erreur moyenne de 3.6m contre 5.8m en temps réel. Enfin, un modèle d'apprentissage statistique basé sur des forêts aléatoires a permis de distinguer les trajectoires qui ont été correctement estimées en fonction d'un faible nombre de variables, en prévision d'une application au crowdsourcing. / Real time indoor geolocalization has recently been widely studied, and has many applications. Off-line (post-processing) trajectory estimation also presents some interest. Off-line indoor geolocalization makes it possible for instance to develop crowdsourcing approaches that take advantage of a large number of users to collect a large number of measurements: knowing the trajectory of a smartphone user makes it possible for instance to feed an attendance map. Estimating this trajectory does not need to be performed in real-time and can be performed off-line, two main benefits. Firstly, the real-time approach estimates a current position using present and past measurements only, when the off-line approach has access to the whole measurements, and makes it possible to obtain an estimated trajectory that is smoother and more accurate than with a real-time approach. Secondly, this estimation can be done on a server and does not need to be implemented in the smartphone as it is the case in the real-time approach, with the consequence that more computing power and size memory are available. The objective of this PhD is to provide an off-line estimation of the trajectory of a smartphone user receiving signal strength (RSS) of wifi or bluetooth measurements and collecting inertial measurements (IMU). In the beginning, without the floorplan of the building, a parametric model is proposed, based on an adaptive pathloss model for RSS measurements and on a piecewise parametrization for the inertial trajectory, obtained with IMU measurements. Results are an average error of 6.2mfor the off-line estimation against 12.5m for the real-time estimation. Then, information on displacement constraints induced by the walls is considered, that makes it possible to adjust the estimated trajectory by using a particle technique as often done in the state-of-the-art. With this second approach we developped a particle smoother and a maximum a posteriori estimator using the Viterbi algorithm. Other numerical heuristics have been introduced. A first heuristic makes use of the parametric model developed without the floorplan to adjust the state model of the user which was originally based on IMUalone. A second heuristic proposes to performseveral realization of a particle filter and to define two score functions based on RSS and on the continuity of the estimated trajectory. The scores are then used to select the best realization of the particle filter as the estimated trajectory. A global algorithm, which uses all of the aforementioned approaches, leads to an error of 3.6m against 5.8m in real-time. Lastly, a statistical machine learning model produced with random forests makes it possible to distinguish the correct estimated trajectories by only using few variables to be used in a crowdsourcing framework.

Les modèles de chaînes de Markov cachées ou plus généralement ceux de Feynman-Kac sont aujourd'hui très largement utilisés. Ils permettent de modéliser une grande diversité de séries temporelles (en finance, biologie, traitement du signal, ...) La complexité croissante de ces modèles a conduit au développement d'approximations via différentes méthodes de Monte-Carlo, dont le Markov Chain Monte-Carlo (MCMC) et le Sequential Monte-Carlo (SMC). Les méthodes de SMC appliquées au filtrage et au lissage particulaires font l'objet de cette thèse. Elles consistent à approcher la loi d'intérêt à l'aide d'une population de particules définies séquentiellement. Différents algorithmes ont déjà été développés et étudiés dans la littérature. Nous raffinons certains de ces résultats dans le cas du Forward Filtering Backward Smoothing et du Forward Filtering Backward Simulation grâce à des inégalités de déviation exponentielle et à des contrôles non asymptotiques de l'erreur moyenne. Nous proposons également un nouvel algorithme de lissage consistant à améliorer une population de particules par des itérations MCMC, et permettant d'estimer la variance de l'estimateur sans aucune autre simulation. Une partie du travail présenté dans cette thèse concerne également les possibilités de mise en parallèle du calcul des estimateurs particulaires. Nous proposons ainsi différentes interactions entre plusieurs populations de particules. Enfin nous illustrons l'utilisation des chaînes de Markov cachées dans la modélisation de données financières en développant un algorithme utilisant l'Expectation-Maximization pour calibrer les paramètres du modèle exponentiel d'Ornstein-Uhlenbeck multi-échelles / Hidden Markov chain models or more generally Feynman-Kac models are now widely used. They allow the modelling of a variety of time series (in finance, biology, signal processing, ...) Their increasing complexity gave birth to approximations using Monte-Carlo methods, among which Markov Chain Monte-Carlo (MCMC) and Sequential Monte-Carlo (SMC). SMC methods applied to particle filtering and smoothing are dealt with in this thesis. These methods consist in approximating the law of interest through a particle population sequentially defined. Different algorithms have already been developed and studied in the literature. We make some of these results more precise in the particular of the Forward Filtering Backward Smoothing and Forward Filtering Backward Simulation by showing exponential deviation inequalities and by giving non-asymptotic upper bounds to the mean error. We also introduce a new smoothing algorithm improving a particle population through MCMC iterations and allowing to estimate the estimator variance without further simulation. Part of the work presented in this thesis is devoted to the parallel computing of particle estimators. We study different interaction schemes between several particle populations. Finally, we also illustrate the use of hidden Markov chains in the modelling of financial data through an algorithm using Expectation-Maximization to calibrate the exponential Ornstein-Uhlenbeck multiscale stochastic volatility model