Dissertations / Theses on the topic 'Sequential Monte Carlo Filter'

This thesis work analyses the obstacles faced when adapting the particle filtering algorithm to run on massively parallel compute architectures. Graphics processing units are one example of massively parallel compute architectures which allow for the developer to distribute computational load over hundreds or thousands of processor cores. This thesis studies an implementation written for NVIDIA GeForce GPUs, yielding varying speed ups, up to 3000% in some cases, when compared to the equivalent algorithm performed on CPU. The particle filter, also known in the literature as sequential Monte-Carlo methods, is an algorithm used for signal processing when the system generating the signals has a highly nonlinear behaviour or non-Gaussian noise distributions where a Kalman filter and its extended variants are not effective. The particle filter was chosen as a good candidate for parallelisation because of its inherently parallel nature. There are, however, several steps of the classic formulation where computations are dependent on other computations in the same step which requires them to be run in sequence instead of in parallel. To avoid these difficulties alternative ways of computing the results must be used, such as parallel scan operations and scatter/gather methods. Another area where parallel programming still is not widespread is the area of pseudo-random number generation. Pseudo-random numbers are required by the algorithm to simulate the process noise as well as for avoiding the particle depletion problem using a resampling step. In this thesis a recently published counter-based pseudo-random number generator is used.

Orbit determination has long relied on the use of the Kalman filter, or specifically the extended Kalman filter, as a means of accurately navigating spacecraft. With the advent of cheaper, more powerful computers more accurate techniques such as the particle filter have been utilized. These Bayesian types of filters have in more recent years found their way to other applications. Dr. Furfaro and B. Gaudet have demonstrated the ability of the particle filter to accurately estimate the angular velocity, homogenous density, and rotation angle of a non-uniformly rotating ellipsoid shaped asteroid. This paper extends that work by utilizing a particle filter to accurately estimate the angular velocity and homogenous density of an ellipsoidal asteroid while simultaneously determining the location and mass of a mass concentration modeled as a point mass embedded within the asteroid. This work shows that by taking measurements in several locations around the asteroid, the asteroid's rotation state and mass distribution can be discerned.

In this thesis the radar target tracking problem in Bayesian estimation framework is studied. Traditionally, linear or linearized models, where the uncertainty in the system and measurement models is typically represented by Gaussian densities, are used in this area. Therefore, classical sub-optimal Bayesian methods based on linearized Kalman filters can be used. The sequential Monte Carlo methods, i.e. particle filters, make it possible to utilize the inherent non-linear state relations and non-Gaussian noise models. Given the sufficient computational power, the particle filter can provide better results than Kalman filter based methods in many cases. A survey over relevant radar tracking literature is presented including aspects as estimation and target modeling. In various target tracking related estimation applications, particle filtering algorithms are presented.

In this thesis, we consider some popular stochastic differential equation models used in finance, such as the Vasicek Interest Rate model, the Heston model and a new fractional Heston model. We discuss how to perform inference about unknown quantities associated with these models in the Bayesian framework. We describe sequential importance sampling, the particle filter and the auxiliary particle filter. We apply these inference methods to the Vasicek Interest Rate model and the standard stochastic volatility model, both to sample from the posterior distribution of the underlying processes and to update the posterior distribution of the parameters sequentially, as data arrive over time. We discuss the sensitivity of our results to prior assumptions. We then consider the use of Markov chain Monte Carlo (MCMC) methodology to sample from the posterior distribution of the underlying volatility process and of the unknown model parameters in the Heston model. The particle filter and the auxiliary particle filter are also employed to perform sequential inference. Next we extend the Heston model to the fractional Heston model, by replacing the Brownian motions that drive the underlying stochastic differential equations by fractional Brownian motions, so allowing a richer dependence structure across time. Again, we use a variety of methods to perform inference. We apply our methodology to simulated and real financial data with success. We then discuss how to make forecasts using both the Heston and the fractional Heston model. We make comparisons between the models and show that using our new fractional Heston model can lead to improve forecasts for real financial data.

With advances in micro-electronic complexity and fabrication, sophisticated algorithms for source localisation and tracking can now be deployed in cost sensitive appliances for both consumer and commercial markets. As a result, such algorithms are becoming ubiquitous elements of contemporary communication, robotics and surveillance systems. Two of the main requirements of acoustic localisation and tracking algorithms are robustness to acoustic disturbances (to maximise localisation accuracy), and low computational complexity (to minimise power-dissipation and cost of hardware components). The research presented in this thesis covers both advances in robustness and in computational complexity for acoustic source localisation and tracking algorithms. This thesis also presents advances in modelling of sound propagation in indoor environments; a key to the development and evaluation of acoustic localisation and tracking algorithms. As an advance in the field of tracking, this thesis also presents a new method for tracking human speakers in which the problem of the discontinuous nature of human speech is addressed using a new state-space filter based algorithm which incorporates a voice activity detector. The algorithm is shown to achieve superior tracking performance compared to traditional approaches. Furthermore, the algorithm is implemented in a real-time system using a method which yields a low computational complexity. Additionally, a new method is presented for optimising the parameters for the dynamics model used in a state-space filter. The method features an evolution strategy optimisation algorithm to identify the optimum dynamics’ model parameters. Results show that the algorithm is capable of real-time online identification of optimum parameters for different types of dynamics models without access to ground-truth data. Finally, two new localisation algorithms are developed and compared to older well established methods. In this context an analytic analysis of noise and room reverberation is conducted, considering its influence on the performance of localisation algorithms. The algorithms are implemented in a real-time system and are evaluated with respect to robustness and computational complexity. Results show that the new algorithms outperform their older counterparts, both with regards to computational complexity, and robustness to reverberation and background noise. The field of acoustic modelling is advanced in a new method for predicting the energy decay in impulse responses simulated using the image source method. The new method is applied to the problem of designing synthetic rooms with a defined reverberation time, and is compared to several well established methods for reverberation time prediction. This comparison reveals that the new method is the most accurate.

In parametrized continuous state-space models, one can obtain estimates of the likelihood of the data for fixed parameters via the Sequential Monte Carlo methodology. Unfortunately, even if the likelihood is continuous in the parameters, the estimates produced by practical particle filters are not, even when common random numbers are used for each filter. This is because the same resampling step which drastically reduces the variance of the estimates also introduces discontinuities in the particles that are selected across filters when the parameters change. When the state variables are univariate, a method exists that gives an estimator of the log-likelihood that is continuous in the parameters. We present a non-trivial generalization of this method using tree-based o(N²) (and as low as O(N log N)) resampling schemes that induce significant correlation amongst the selected particles across filters. In turn, this reduces the variance of the difference between the likelihood evaluated for different values of the parameters and the resulting estimator is considerably smoother than naively running the filters with common random numbers. Importantly, in practice our methods require only a change to the resample operation in the SMC framework without the addition of any extra parameters and can therefore be used for any application in which particle filters are already used. In addition, excepting the optional use of interpolation in the schemes, there are no regularity conditions for their use although certain conditions make them more advantageous. In this thesis, we first introduce the relevant aspects of the SMC methodology to the task of likelihood estimation in continuous state-space models and present an overview of work related to the task of smooth likelihood estimation. Following this, we introduce theoretically correct resampling schemes that cannot be implemented and the practical tree-based resampling schemes that were developed instead. After presenting the performance of our schemes in various applications, we show that two of the schemes are asymptotically consistent with the theoretically correct but unimplementable methods introduced earlier. Finally, we conclude the thesis with a discussion.

Sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC) methods provide computational tools for systematic inference and learning in complex dynamical systems, such as nonlinear and non-Gaussian state-space models. This thesis builds upon several methodological advances within these classes of Monte Carlo methods.Particular emphasis is placed on the combination of SMC and MCMC in so called particle MCMC algorithms. These algorithms rely on SMC for generating samples from the often highly autocorrelated state-trajectory. A specific particle MCMC algorithm, referred to as particle Gibbs with ancestor sampling (PGAS), is suggested. By making use of backward sampling ideas, albeit implemented in a forward-only fashion, PGAS enjoys good mixing even when using seemingly few particles in the underlying SMC sampler. This results in a computationally competitive particle MCMC algorithm. As illustrated in this thesis, PGAS is a useful tool for both Bayesian and frequentistic parameter inference as well as for state smoothing. The PGAS sampler is successfully applied to the classical problem of Wiener system identification, and it is also used for inference in the challenging class of non-Markovian latent variable models.Many nonlinear models encountered in practice contain some tractable substructure. As a second problem considered in this thesis, we develop Monte Carlo methods capable of exploiting such substructures to obtain more accurate estimators than what is provided otherwise. For the filtering problem, this can be done by using the well known Rao-Blackwellized particle filter (RBPF). The RBPF is analysed in terms of asymptotic variance, resulting in an expression for the performance gain offered by Rao-Blackwellization. Furthermore, a Rao-Blackwellized particle smoother is derived, capable of addressing the smoothing problem in so called mixed linear/nonlinear state-space models. The idea of Rao-Blackwellization is also used to develop an online algorithm for Bayesian parameter inference in nonlinear state-space models with affine parameter dependencies.
CNDM
CADICS

Generative adversarial networks (GANs), a type of generative modeling framework, has received much attention in the past few years since they were discovered for their capacity to recover complex high-dimensional data distributions. These provide a compressed representation of the data where all but the essential features of a sample is extracted, subsequently inducing a similarity measure on the space of data. This similarity measure gives rise to the possibility of interpolating in the data which has been done successfully in the past. Herein we propose a new stochastic interpolation method for GANs where the interpolation is forced to adhere to the data distribution by implementing a sequential Monte Carlo algorithm for data sampling. The results show that the new method outperforms previously known interpolation methods for the data set LINES; compared to the results of other interpolation methods there was a significant improvement measured through quantitative and qualitative evaluations. The developed interpolation method has met its expectations and shown promise, however it needs to be tested on a more complex data set in order to verify that it also scales well.
Generative adversarial networks (GANs) är ett slags generativ modell som har fått mycket uppmärksamhet de senaste åren sedan de upptäcktes för sin potential att återskapa komplexa högdimensionella datafördelningar. Dessa förser en komprimerad representation av datan där enbart de karaktäriserande egenskaperna är bevarade, vilket följdaktligen inducerar ett avståndsmått på datarummet. Detta avståndsmått möjliggör interpolering inom datan vilket har åstadkommits med framgång tidigare. Häri föreslår vi en ny stokastisk interpoleringsmetod för GANs där interpolationen tvingas följa datafördelningen genom att implementera en sekventiell Monte Carlo algoritm för dragning av datapunkter. Resultaten för studien visar att metoden ger bättre interpolationer för datamängden LINES som användes; jämfört med resultaten av tidigare kända interpolationsmetoder syntes en märkbar förbättring genom kvalitativa och kvantitativa utvärderingar. Den framtagna interpolationsmetoden har alltså mött förväntningarna och är lovande, emellertid fordras att den testas på en mer komplex datamängd för att bekräfta att den fungerar väl även under mer generella förhållanden.

In this report a comparison is made between four frequently encountered resampling algorithms for particle filters. A theoretical framework is introduced to be able to understand and explain the differences between the resampling algorithms. This facilitates a comparison of the algorithms based on resampling quality and on computational complexity. Using extensive Monte Carlo simulations the theoretical results are verified. It is found that systematic resampling is favourable, both in resampling quality and computational complexity.

This thesis considers the filtering and prediction problems of nonlinear noisy econometric systems. As a filter/predictor, the standard tool Extended Kalman Filter and new approaches Discrete Quantization Filter and Sequential Importance Resampling Filter are used. The algorithms are compared by using Monte Carlo Simulation technique. The advantages of the new algorithms over Extended Kalman Filter are shown.

This thesis contributes new algorithms and implementations for particle filter-based target tracking. From an algorithmic perspective, modifications that improve a batch-based acoustic direction-of-arrival (DOA), multi-target, particle filter tracker are presented. The main improvements are reduced execution time and increased robustness to target maneuvers. The key feature of the batch-based tracker is an image template-matching approach that handles data association and clutter in measurements. The particle filter tracker is compared to an extended Kalman filter~(EKF) and a Laplacian filter and is shown to perform better for maneuvering targets. Using an approach similar to the acoustic tracker, a radar range-only tracker is also developed. This includes developing the state update and observation models, and proving observability for a batch of range measurements. From an implementation perspective, this thesis provides new low-power and real-time implementations for particle filters. First, to achieve a very low-power implementation, two mixed-mode implementation strategies that use analog and digital components are developed. The mixed-mode implementations use analog, multiple-input translinear element (MITE) networks to realize nonlinear functions. The power dissipated in the mixed-mode implementation of a particle filter-based, bearings-only tracker is compared to a digital implementation that uses the CORDIC algorithm to realize the nonlinear functions. The mixed-mode method that uses predominantly analog components is shown to provide a factor of twenty improvement in power savings compared to a digital implementation. Next, real-time implementation strategies for the batch-based acoustic DOA tracker are developed. The characteristics of the digital implementation of the tracker are quantified using digital signal processor (DSP) and field-programmable gate array (FPGA) implementations. The FPGA implementation uses a soft-core or hard-core processor to implement the Newton search in the particle proposal stage. A MITE implementation of the nonlinear DOA update function in the tracker is also presented.

Le suivi visuel constitue une tâche essentielle en vision par ordinateur. Les approches Bayésiennes sont largement utilisées aujourd’hui pour résoudre la problématique du suivi visuel. Notamment grâce aux possibilités offertes par les méthodes de Monte Carlo séquentielles (SMC) qui prennent en comptes les incertitudes du model et s’adaptent à des scenarios variés. L’efficacité des méthodes SMC dépend fortement du choix de la loi de proposition qui permet d’explorer l’espace d’état.Dans cette thèse, nous cherchons à améliorer l’exploration de l’espace d’état en approchant la loi de proposition optimale. Cette loi de proposition quasi-optimale repose sur une approximation de la fonction de vraisemblance, et ce en utilisant une information de détection souple qui est à la foi plus fiable et moins couteuse à calculer. En comparaison avec les travaux antérieurs sur le sujet, notre loi de proposition quasi-optimale offre un bon compromis entre l’optimalité et la complexité algorithmique. Améliorer l’exploration de l’espace d’état est nécessaire principalement dans deux applications du suivi visuel : Le suivi des mouvements abrupts et le suivi multi objet. Dans le cadre de cette thèse on a souligné la capacité des méthodes SMC quasi-optimales à traiter les mouvements abrupts, en les comparants aux méthodes proposées dans la littérature spécifiquement pour ce type de scenario. Aussi, on a étendu notre loi de proposition quasi-optimale pour le suivi multi objet et nous en avons démontré l’intérêt. Par ailleurs, on a implémenté le filtre particulaire Local qui partitionne l’espace d’état en sous-espaces indépendants de taille inférieure tout en modélisant des interactions
In computer vision applications, visual tracking is an important and a fundamental task. Solving the tracking problematic based on a statistical formulation in the Bayesian framework has gained great interest in recent years due to the capabilities of the sequential Monte Carlo (SMC) methods to adapt to various tracking schemes and to take into account model uncertainties. In practice, the efficiency of SMC methods strongly depends on the proposal density used to explore the state space, thus the choice of the proposal is essential. In the thesis, our approach to efficiently explore the state space aims to derive a close approximation of the optimal proposal. The proposed near optimal proposal relies on an approximation of the likelihood using a new form of likelihood based on soft detection information which is more trustworthy and requires less calculations than the usual likelihood. In comparison with previous works, our near optimal proposal offers a good compromise between computational complexity and optimality.Improving the exploration of the state space is most required in two visual tracking applications: abrupt motion tracking and multiple object tracking. In the thesis, we focus on the ability of the near optimal SMC methods to deal with abrupt motion situations and we compare them to the state-of-the-art methods proposed in the literature for these situations. Also, we extend the near optimal proposal to multiple object tracking scenarios and show the benefit of using the near optimal SMC algorithms for these scenarios. Moreover, we implemented the Local PF which partition large state spaces into separate smaller subspaces while modelling interactions

Depuis les années 2000, un progrès significatif est enregistré dans les travaux de recherche qui proposent l’apprentissage de détecteurs d’objets sur des grandes bases de données étiquetées manuellement et disponibles publiquement. Cependant, lorsqu’un détecteur générique d’objets est appliqué sur des images issues d’une scène spécifique les performances de détection diminuent considérablement. Cette diminution peut être expliquée par les différences entre les échantillons de test et ceux d’apprentissage au niveau des points de vues prises par la(les) caméra(s), de la résolution, de l’éclairage et du fond des images. De plus, l’évolution de la capacité de stockage des systèmes informatiques, la démocratisation de la "vidéo-surveillance" et le développement d’outils d’analyse automatique des données vidéos encouragent la recherche dans le domaine du trafic routier. Les buts ultimes sont l’évaluation des demandes de gestion du trafic actuelles et futures, le développement des infrastructures routières en se basant sur les besoins réels, l’intervention pour une maintenance à temps et la surveillance des routes en continu. Par ailleurs, l’analyse de trafic est une problématique dans laquelle plusieurs verrous scientifiques restent à lever. Ces derniers sont dus à une grande variété dans la fluidité de trafic, aux différents types d’usagers, ainsi qu’aux multiples conditions météorologiques et lumineuses. Ainsi le développement d’outils automatiques et temps réel pour l’analyse vidéo de trafic routier est devenu indispensable. Ces outils doivent permettre la récupération d’informations riches sur le trafic à partir de la séquence vidéo et doivent être précis et faciles à utiliser. C’est dans ce contexte que s’insèrent nos travaux de thèse qui proposent d’utiliser les connaissances antérieurement acquises et de les combiner avec des informations provenant de la nouvelle scène pour spécialiser un détecteur d’objet aux nouvelles situations de la scène cible. Dans cette thèse, nous proposons de spécialiser automatiquement un classifieur/détecteur générique d’objets à une scène de trafic routier surveillée par une caméra fixe. Nous présentons principalement deux contributions. La première est une formalisation originale de transfert d’apprentissage transductif à base d’un filtre séquentiel de type Monte Carlo pour la spécialisation automatique d’un classifieur. Cette formalisation approxime itérativement la distribution cible inconnue au départ, comme étant un ensemble d’échantillons de la base spécialisée à la scène cible. Les échantillons de cette dernière sont sélectionnés à la fois à partir de la base source et de la scène cible moyennant une pondération qui utilise certaines informations a priori sur la scène. La base spécialisée obtenue permet d’entraîner un classifieur spécialisé à la scène cible sans intervention humaine. La deuxième contribution consiste à proposer deux stratégies d’observation pour l’étape mise à jour du filtre SMC. Ces stratégies sont à la base d’un ensemble d’indices spatio-temporels spécifiques à la scène de vidéo-surveillance. Elles sont utilisées pour la pondération des échantillons cibles. Les différentes expérimentations réalisées ont montré que l’approche de spécialisation proposée est performante et générique. Nous avons pu y intégrer de multiples stratégies d’observation. Elle peut être aussi appliquée à tout type de classifieur. De plus, nous avons implémenté dans le logiciel OD SOFT de Logiroad les possibilités de chargement et d’utilisation d’un détecteur fourni par notre approche. Nous avons montré également les avantages des détecteurs spécialisés en comparant leurs résultats avec celui de la méthode Vu-mètre de Logiroad
Since 2000, a significant progress has been recorded in research work which has proposed to learn object detectors using large manually labeled and publicly available databases. However, when a generic object detector is applied on images of a specific scene, the detection performances will decrease considerably. This decrease may be explained by the differences between the test samples and the learning ones at viewpoints taken by camera(s), resolution, illumination and background images. In addition, the storage capacity evolution of computer systems, the "video surveillance" democratization and the development of automatic video-data analysis tools have encouraged research into the road-traffic domain. The ultimate aims are the management evaluation of current and future trafic requests, the road infrastructures development based on real necessities, the intervention of maintenance task in time and the continuous road surveillance. Moreover, traffic analysis is a problematicness where several scientific locks should be lifted. These latter are due to a great variety of traffic fluidity, various types of users, as well multiple weather and lighting conditions. Thus, developing automatic and real-time tools to analyse road-traffic videos has become an indispensable task. These tools should allow retrieving rich data concerning the traffic from the video sequence and they must be precise and easy to use. This is the context of our thesis work which proposes to use previous knowledges and to combine it with information extracted from the new scene to specialize an object detector to the new situations of the target scene. In this thesis, we propose to automatically specialize a generic object classifier/detector to a road traffic scene surveilled by a fixed camera. We mainly present two contributions. The first one is an original formalization of Transductive Transfer Learning based on a sequential Monte Carlo filter for automatic classifier specialization. This formalization approximates iteratively the previously unknown target distribution as a set of samples composing the specialized dataset of the target scene. The samples of this dataset are selected from both source dataset and target scene further to a weighting step using some prior information on the scene. The obtained specialized dataset allows training a specialized classifier to the target scene without human intervention. The second contribution consists in proposing two observation strategies to be used in the SMC filter’s update step. These strategies are based on a set of specific spatio-temporal cues of the video surveillance scene. They are used to weight the target samples. The different experiments carried out have shown that the proposed specialization approach is efficient and generic. We have been able to integrate multiple observation strategies. It can also be applied to any classifier / detector. In addition, we have implemented into the Logiroad OD SOFT software the loading and utilizing possibilities of a detector provided by our approach. We have also shown the advantages of the specialized detectors by comparing their results to the result of Logiroad’s Vu-meter method

The availability of ultra high-frequency (UHF) data on transactions has revolutionised data processing and statistical modelling techniques in finance. The unique characteristics of such data, e.g. discrete structure of price change, unequally spaced time intervals and multiple transactions have introduced new theoretical and computational challenges. In this study, we develop a Bayesian framework for modelling integer-valued variables to capture the fundamental properties of price change. We propose the application of the zero inflated Poisson difference (ZPD) distribution for modelling UHF data and assess the effect of covariates on the behaviour of price change. For this purpose, we present two modelling schemes; the first one is based on the analysis of the data after the market closes for the day and is referred to as off-line data processing. In this case, the Bayesian interpretation and analysis are undertaken using Markov chain Monte Carlo methods. The second modelling scheme introduces the dynamic ZPD model which is implemented through Sequential Monte Carlo methods (also known as particle filters). This procedure enables us to update our inference from data as new transactions take place and is known as online data processing. We apply our models to a set of FTSE100 index changes. Based on the probability integral transform, modified for the case of integer-valued random variables, we show that our models are capable of explaining well the observed distribution of price change. We then apply the deviance information criterion and introduce its sequential version for the purpose of model comparison for off-line and online modelling, respectively. Moreover, in order to add more flexibility to the tails of the ZPD distribution, we introduce the zero inflated generalised Poisson difference distribution and outline its possible application for modelling UHF data.

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

The multi-target tracking problem essentially involves the recursive joint estimation of the state of unknown and time-varying number of targets present in a tracking scene, given a series of observations. This problem becomes more challenging because the sequence of observations is noisy and can become corrupted due to miss-detections and false alarms/clutter. Additionally, the detected observations are indistinguishable from clutter. Furthermore, whether the target(s) of interest are point or extended (in terms of spatial extent) poses even more technical challenges. An approach known as random finite sets provides an elegant and rigorous framework for the handling of the multi-target tracking problem. With a random finite sets formulation, both the multi-target states and multi-target observations are modelled as finite set valued random variables, that is, random variables which are random in both the number of elements and the values of the elements themselves. Furthermore, compared to other approaches, the random finite sets approach possesses a desirable characteristic of being free of explicit data association prior to tracking. In addition, a framework is available for dealing with random finite sets and is known as finite sets statistics. In this thesis, advanced signal processing techniques are employed to provide enhancements to and develop new random finite sets based multi-target tracking algorithms for the tracking of both point and extended targets with the aim to improve tracking performance in cluttered environments. To this end, firstly, a new and efficient Kalman-gain aided sequential Monte Carlo probability hypothesis density (KG-SMC-PHD) filter and a cardinalised particle probability hypothesis density (KG-SMC-CPHD) filter are proposed. These filters employ the Kalman- gain approach during weight update to correct predicted particle states by minimising the mean square error between the estimated measurement and the actual measurement received at a given time in order to arrive at a more accurate posterior. This technique identifies and selects those particles belonging to a particular target from a given PHD for state correction during weight computation. The proposed SMC-CPHD filter provides a better estimate of the number of targets. Besides the improved tracking accuracy, fewer particles are required in the proposed approach. Simulation results confirm the improved tracking performance when evaluated with different measures. Secondly, the KG-SMC-(C)PHD filters are particle filter (PF) based and as with PFs, they require a process known as resampling to avoid the problem of degeneracy. This thesis proposes a new resampling scheme to address a problem with the systematic resampling method which causes a high tendency of resampling very low weight particles especially when a large number of resampled particles are required; which in turn affect state estimation. Thirdly, the KG-SMC-(C)PHD filters proposed in this thesis perform filtering and not tracking , that is, they provide only point estimates of target states but do not provide connected estimates of target trajectories from one time step to the next. A new post processing step using game theory as a solution to this filtering - tracking problem is proposed. This approach was named the GTDA method. This method was employed in the KG-SMC-(C)PHD filter as a post processing technique and was evaluated using both simulated and real data obtained using the NI-USRP software defined radio platform in a passive bi-static radar system. Lastly, a new technique for the joint tracking and labelling of multiple extended targets is proposed. To achieve multiple extended target tracking using this technique, models for the target measurement rate, kinematic component and target extension are defined and jointly propagated in time under the generalised labelled multi-Bernoulli (GLMB) filter framework. The GLMB filter is a random finite sets-based filter. In particular, a Poisson mixture variational Bayesian (PMVB) model is developed to simultaneously estimate the measurement rate of multiple extended targets and extended target extension was modelled using B-splines. The proposed method was evaluated with various performance metrics in order to demonstrate its effectiveness in tracking multiple extended targets.

Target tracking in over a small-scale area using wireless sensor networks (WSNs) is a technique that can be used in applications ranging from emergency rescue after an earthquake to security protection in a building. Many target tracking systems rely on the presence of an electric device which must be carried by the target in order to reports back its location and status. This makes these systems unsuitable for many emergency applications; in such applications device-free tracking systems that where no devices are attached to the targets are needed. Radio-Frequency (RF) tomographic tracking is one such device-free tracking technique. This system tracks moving targets by analyzing changes in attenuation in wireless transmissions. The target can be tracked within the sensor network area without being required to carry an electric device.Some previously-proposed device-free tracking approaches require a time-consuming training phase before tracking can be carried out, which is time-consuming. Others perform tracking by sacrificing part of the estimation accuracy. In this thesis, we propose a novel sequential Monte Carlo (SMC) algorithm for RF tomographic tracking. It can track a single target moving in a wireless sensor network without the system needing to be trained. The algorithm adopts a particle filtering method to estimate the target position and incorporates on-line Expectation Maximization (EM) to estimate model parameters. Based on experimental measurements, the work also introduces a novel measurement model for the attenuation caused by a target with the goal of improving estimation accuracy. The performance of the algorithm is assessed through numerical simulations and field experiments carried out with a wireless sensor network testbed. Both simulated and experimental results demonstrate that our work outperforms previous RF tomographic tracking approaches for single target tracking.
Suivi de cible dans la zone à petite échelle en utilisant les réseaux de capteurs sans fil est une technique qui peut être largement utilisé dans des applications telles que le sauvetage d'urgence après un tremblement de terre, ou la protection de la sécurité dans un bâtiment. Beaucoup de systèmes de poursuite de cibles nécessitent un dispositif électrique réalisée par l'objectif de faire rapport de ses localisation instantanée et le statut. L'inconvénient rend ces systèmes ne conviennent pas pour des applications nombreuses interventions d'urgence, dispositif sans systèmes de suivi qui ne les périphériques connectés sur les objectifs sont nécessaires. Radio-Fréquence (RF) suivi tomographique est l'une des techniques dispositif de suivi-libres. Il s'agit d'un processus de suivi des cibles mobiles en analysant l'évolution de l'atténuation dans les transmissions sans fil. La cible peut être suivi dans la zone de réseau de capteurs, tandis que les appareils électriques ne doivent être effectués. Cependant, certaines approches précédentes dispositif de suivi-libre nécessite une phase d'entraînement avant de suivi, ce qui prend beaucoup de temps. Autres effectuer un suivi par scarification partie de précision de l'estimation.Dans cette thèse, nous proposons une nouvelle Monte Carlo séquentielles (SMC) algorithme de suivi RF tomographique. Il peut suivre une cible unique sans formation du système dans un réseau de capteurs sans fil. L'algorithme de filtrage particulaire adopte la méthode pour estimer la position cible et intègre en ligne Expectation Maximization (EM) pour estimer les paramètres du modèle. Sur la base de mesures expérimentales, le travail introduit également un modèle de mesure de roman pour l'atténuation provoquée par une cible pour améliorer la précision d'estimation. La performance de l'algorithme est évaluée par des simulations numériques et expériences sur le terrain avec un réseau de capteurs sans fil banc d'essai. Les deux résultats simulés et expérimentaux démontrent que notre travail surpasse précédente approche RF suivi tomographique pour le suivi de cible unique.

Particle Filter-based Acoustic Source Localisation algorithms track (online and in real-time) the position of a sound source – a person speaking in a room – based on the current data from a microphone array as well as all previous data up to that point. The first section of this thesis reviews previous research in this field and discusses the suitability of using particle filters to solve this problem. Experiments are then detailed which examine the typical performance and behaviour of various instantaneous localisation functions. In subsequent sections, algorithms are detailed which advance the state-of-the-art. First an orientation estimation algorithm is introduced which uses speaker directivity to infer head pose. Second an algorithm is introduced for multi-target acoustic source tracking and is based upon the Track Before Detect (TBD) methodology. Using this methodology avoids the need to identify a set of source measurements and allows for a large saving in computational power. Finally this algorithm is extended to allow for an unknown and time-varying number of speakers. By leveraging the frequency content of speech it is shown that regions of the surveillance space can be monitored for activity while requiring only a minor increase in overall computation. A variable dimension particle filter is then outlined which proposes newly active targets, maintains target tracks and removes targets when they become inactive.

The sequential Monte Carlo (smc) methods have been widely used for modern scientific computation. Bayesian model comparison has been successfully applied in many fields. Yet there have been few researches on the use of smc for the purpose of Bayesian model comparison. This thesis studies different smc strategies for Bayesian model computation. In addition, various extensions and refinements of existing smc practices are proposed in this thesis. Through empirical examples, it will be shown that the smc strategies can be applied for many realistic applications which might be difficult for Markov chain Monte Carlo (mcmc) algorithms. The extensions and refinements lead to an automatic and adaptive strategy. This strategy is able to produce accurate estimates of the Bayes factor with minimal manual tuning of algorithms. Another advantage of smc algorithms over mcmc algorithms is that it can be parallelized in a straightforward way. This allows the algorithms to better utilize modern computer resources. This thesis presents work on the parallel implementation of generic smc algorithms. A C++ framework within which generic smc algorithms can be implemented easily on parallel computers is introduced. We show that with little additional effort, the implementations using this framework can provide significant performance speedup.

Patterns of mutations in the DNA of modern-day individuals have been shaped by the demographic history of our ancestors. Inferring the demographic history from these patterns is a challenging problem due to complex dependencies along the genome. Several recent methods have adopted McVean's sequentially Markovian coalescent (SMC') to model these dependencies. However, these methods involve simplifying assumptions that preclude the inference of rates of migration between populations. We have developed the first method to infer directional migration rates as a function of time. To do this, we employ sequential Monte Carlo (SMC) methods, also known as particle filters, to infer parameters in the SMC' model. To improve the sampling from the state space of SMC' we have developed a sophisticated sampling technique that shows better performance than the standard bootstrap filter. We apply our algorithm, SMC², to Neanderthal data and are able to infer the time and extent of migration from the Vindija Neanderthal population into Europeans. With the large volume of sequencing data being produced from diverse populations, both modern and ancient, there is high demand for methods to interrogate this data. SMC² provides a flexible algorithm, which can be modified to suit many data applications. For instance, we show that our method performs well when the phasing of the samples is unknown, which is often the case in practice. The long runtime of SMC² is the main limiting factor in the adoption of the method. We have started to explore ways to improve the runtime, by developing an adaptive online expectation maximisation (EM) procedure.

The present thesis deals with the problems of simulation from a given target distribution and the estimation of ratios of normalizing constants, i.e. marginal likelihoods (ML). Both problems could be considerably difficult even for the simplest possible real-world statistical setups. We investigate how the combination of Hamiltonian Monte Carlo (HMC) and Sequential Monte Carlo (SMC) could be used to sample effectively from a multi-modal target distribution and to estimate ratios of normalizing constants at the same time. We call this novel combination Hamiltonian SMC (HSMC) algorithm and we show that it achieves some improvements over the existing Monte Carlo sampling algorithms, especially when the target distribution is multi-modal and/ or have complicated covariance structure. An important convergence result is proved for the HSMC, as well as an upper bound on the bias of the estimate of the ratio of MLs. Our investigation of the continuous time limit of the HSMC process reveals an interesting connection between Monte Carlo simulation and physics. We also concern ourselves with the problem of estimation of the uncertainty of the estimate of the ML of a HMM. We propose a new algorithm (Pairs algorithm) to estimate the non-asymptotic second moment of the estimate of the ML for general HMM. Later we show that there exists a linear-in-time bound on the relative variance of the estimate of the second moment of the ML obtained using the Pairs algorithm. This theoretical property of the relative variance translates in practice into a more reliable estimates of the second moment of the estimate of the MLs compared to the standard approach of running independent copies of the particle filter. We support out investigations with different numerical examples like Bayesian inference of a heteroscedastic regression, inference of a Lotka - Volterra based HMM, etc.

Sequential Monte Carlo (SMC) methods have been well studied within the context of performing inference with respect to partially observed Markov processes, and their use in this context relies upon the ability to evaluate or estimate the likelihood of a set of observed data, given the state of the latent process. In many real-world applications such as the study of population genetics and econometrics, however, this likelihood can neither be analytically evaluated nor replaced by an unbiased estimator, and so the application of exact SMC methods to these problems may be infeasible, or even impossible. The models in many of these applications are complex, yet realistic, and so development of techniques that can deal with problems of likelihood intractability can help us to perform inference for many important yet otherwise inaccessible problems; this motivates the research presented within this thesis. The main focus of this work is the application of approximate Bayesian computation (ABC) methodology to state-space models (SSMs) and the development of SMC methods in the context of these ABC SSMs for filtering and smoothing of the latent process. The introduction of ABC here avoids the need to evaluate the likelihood, at the cost of introducing a bias into the resulting filtering and smoothing estimators; this bias is explored theoretically and through simulation studies. An alternative SMC procedure, incorporating an additional rejection step, is also considered and the novel application of this rejection-based SMC procedure to the ABC approximation of the SSM is considered. This thesis will also consider the application of MCMC and SMC methods to a class of partially observed point process (PP) models. We investigate the problem of performing sequential inference for these models and note that current methods often fail. We present a new approach to smoothing in this context, using SMC samplers (Del Moral et al., 2006). This approach is illustrated, with some theoretical discussion, on a doubly stochastic PP applied in the context of finance.

Recently reconstructing evolutionary histories has become a computational issue due to the increased availability of genetic sequencing data and relaxations of classical modelling assumptions. This thesis specializes a Divide & conquer sequential Monte Carlo (DCSMC) inference algorithm to phylogenetics to address these challenges. In phylogenetics, the tree structure used to represent evolutionary histories provides a model decomposition used for DCSMC. In particular, speciation events are used to recursively decompose the model into subproblems. Each subproblem is approximated by an independent population of weighted particles, which are merged and propagated to create an ancestral population. This approach provides the flexibility to relax classical assumptions on large trees by parallelizing these recursions.
Science, Faculty of
Statistics, Department of
Graduate

La poursuite multi-cibles a pour objet le suivi d'un ensemble de cibles mobiles à partir de données obtenues séquentiellement. Ce problème est particulièrement complexe du fait du nombre inconnu et variable de cibles, de la présence de bruit de mesure, de fausses alarmes, d'incertitude de détection et d'incertitude dans l'association de données. Les filtres PHD (Probability Hypothesis Density) constituent une nouvelle gamme de filtres adaptés à cette problématique. Ces techniques se distinguent des méthodes classiques (MHT, JPDAF, particulaire) par la modélisation de l'ensemble des cibles comme un ensemble fini aléatoire et par l'utilisation des moments de sa densité de probabilité. Dans la première partie, on s'intéresse principalement à la problématique de l'application des filtres PHD pour le filtrage multi-cibles maritime et aérien dans des scénarios réalistes et à l'étude des propriétés numériques de ces algorithmes. Dans la seconde partie, nous nous intéressons à l'étude théorique des processus de branchement liés aux équations du filtrage multi-cibles avec l'analyse des propriétés de stabilité et le comportement en temps long des semi-groupes d'intensités de branchements spatiaux. Ensuite, nous analysons les propriétés de stabilité exponentielle d'une classe d'équations à valeurs mesures que l'on rencontre dans le filtrage non-linéaire multi-cibles. Cette analyse s'applique notamment aux méthodes de type Monte Carlo séquentielles et aux algorithmes particulaires dans le cadre des filtres de Bernoulli et des filtres PHD.

Monte Carlo algorithms can be used to estimate the state of a system given relative observations. In this dissertation, these algorithms are applied to physical layer communications system models to estimate channel state information, to obtain soft information about transmitted symbols or multiple access interference, or to obtain estimates of all of these by joint estimation. Initially, we develop and analyze a multiple access technique utilizing mutually orthogonal complementary sets (MOCS) of sequences. These codes deliberately introduce inter-chip interference, which is naturally eliminated during processing at the receiver. However, channel impairments can destroy their orthogonality properties and additional processing becomes necessary. We utilize Monte Carlo algorithms to perform joint channel and symbol estimation for systems utilizing MOCS sequences as spreading codes. We apply Rao-Blackwellization to reduce the required number of particles. However, dense signaling constellations, multiuser environments, and the interchannel interference introduced by the spreading codes all increase the dimensionality of the symbol state space significantly. A full maximum likelihood solution is computationally expensive and generally not practical. However, obtaining the optimum solution is critical, and looking at only a part of the symbol space is generally not a good solution. We have sought algorithms that would guarantee that the correct transmitted symbol is considered, while only sampling a portion of the full symbol space. The performance of the proposed method is comparable to the Maximum Likelihood (ML) algorithm. While the computational complexity of ML increases exponentially with the dimensionality of the problem, the complexity of our approach increases only quadratically. Markovian structures such as the one imposed by MOCS spreading sequences can be seen in other physical layer structures as well. We have applied this partitioning approach with some modification to blind equalization of frequency selective fading channel and to multiple-input multiple output receivers that track channel changes. Additionally, we develop a method that obtains a metric for quantifying the convergence rate of Monte Carlo algorithms. Our approach yields an eigenvalue based method that is useful in identifying sources of slow convergence and estimation inaccuracy.

We introduce in this Thesis several particle filter (PF) solutions to the problem of collaborative emitter tracking. In the studied scenario, multiple agents with sensing, processing and communication capabilities passively collect received-signal-strength (RSS) measurements of the same signal originating from a non-cooperative emitter and collaborate to estimate its hidden state. Assuming unknown sensor noise variances, we derive an exact decentralized implementation of the optimal centralized PF solution for this problem in a fully connected network. Next, assuming local internode communication only, we derive two fully distributed consensus-based solutions to the problem using respectively average consensus iterations and a novel ordered minimum consensus approach which allow us to reproduce the exact centralized solution in a finite number of consensus iterations. In the sequel, to reduce the communication cost, we derive a suboptimal tracker which employs suitable parametric approximations to summarize messages that are broadcast over the network. Moreover, to further reduce communication and processing requirements, we introduce a non-iterative tracker based on random information dissemination which is suited for online applications. We derive the proposed random exchange diffusion PF (ReDif-PF) assuming both that observation model parameters are perfectly known and that the emitter is always present. We extend then the ReDif-PF tracker to operate in scenarios with unknown sensor noise variances and propose the Rao-Blackwellized (RB) ReDif-PF. Finally, we introduce the random exchange diffusion Bernoulli filter (RndEx-BF) which enables the network of collaborative RSS sensors to jointly detect and track the emitter within the surveillance space.

The sequential estimation of the states (filtering) and the corresponding simultaneous estimation of the states and fixed parameters of a dynamic state-space model, being linear or not, is an important probleminmany fields of research, such as in the area of finance. The main objective of this research is to estimate sequ entially and efficiently –from a Bayesian perspective via the particle filtering methodology– the states and/or the fixed parameters of a nonstandard dynamic state-spacemodel: one that is possibly nonlinear, non-stationary or non-Gaussian. The present thesis consists of seven chapters and is structured into two parts. Chapter 1 introduces basic concepts, themotivation, the purpose, and the outline of the thesis. Chapters 2-4, the first part of the thesis, focus on the estimation of the states. Chapter 2 provides a comprehensive review of themost classic algorithms (non-simulation based: KF, EKF, and UKF; and simulation based: SIS, SIR, ASIR, EPF, and UPF1) used for filtering solely the states of a dynamic statespacemodel. All these filters scattered in the literature are not only described in detail, but also placed in a unified notation for the sake of consistency, readability and comparability. Chapters 3 and 4 confirm the efficiency of the well-established particle filtering methodology, via extensive Monte Carlo (MC) studies, when estimating only the latent states for a dynamic state-space model, being linear or not. Also, complementary MC studies are conducted to analyze some relevant issues within the adopted approach, such as the degeneracy problem, the resampling strategy, or the possible impact on estimation of the number of particles used and the time series length. Chapter 3 specifically illustrates the performance of the particle filtering methodology in a linear and Gaussian context, using the exact Kalman filter as a benchmark. The performance of the four studied particle filter variants (SIR, SIRopt, ASIR, KPF, the latter being a special case of the EPF algorithm) is assessed using two apparently simple, but important time series processes: the so-called Local Level Model (LLM) and the AR(1) plus noise model, which are non-stationary and stationary, respectively. An exhaustive study on the effect of the signal-to-noise ratio (SNR) over the quality of the estimation is additionally performed. ComplementaryMC studies are conducted to assess the degree of degeneracy and the possible effect of increasing the number of particles and the time series length. Chapter 4 assesses and illustrates the performance of the particle filtering methodology in a nonlinear context. Specifically, a synthetic nonlinear, non Gaussian and non-stationary state space model taken from literature is used to illustrate the performance of the four competing particle filters under study (SIR, ASIR, EPF, UPF) in contraposition to two well-known non-simulation based filters (EKF, UKF). In this chapter, the residual and stratified resampling schemes are compared and the effect of increasing the number of particles is addressed. In the second part (Chapters 5 and 6), extensive MC studies are carried out, but the main goal is the simultaneous estimation of states and fixed model parameters for chosen non-standard dynamic models. This area of research is still very active and it is within this area where this thesis contributes themost. Chapter 5 provides a partial survey of particle filter variants used to conduct the simultaneous estimation of states and fixed parameters. Such filters are an extension of those previously adopted for estimating solely the states. Additionally, a MC study is carried out to estimate the state (level) and the two fixed variance parameters of the non-stationary local level model; we use four particle filter variants (LW, SIRJ, SIRoptJ, KPFJ), six typical settings of the SNR and two settings for the discount factor needed in the jittering step. In this chapter, the SIRJ particle filter variant is proposed as an alternative to the well-established filter of Liu West (LW PF). The combined use of a Kalman-based proposal distribution and a jittering step is proposed and explored, which gives rise to the particle filter variant called: the Kalman Particle Filter plus Jittering (KPFJ). Chapter 6 focuses on estimating the states and three fixed parameters of the non-standard basic stochastic volatility model known as stochastic autoregressive volatility model of order one: SARV(1). After an introduction and detailed description of the stylized features of financial time series, the estimation ability of two competing particle filter variants (SIRJ vs LW(Liu andWest)) is shown empirically using simulated data. The chapter ends with an application to real data sets from the financial area: the Spanish IBEX 35 returns index and the Europe Brent Spot prices (in dollars). The contribution in chapters 5 and 6 is to propose new variants of particle filters, such as the KPFJ, the SIRJ, and the SIRoptJ (a special case of the SIRJ that uses an optimal proposal distribution) that have developed along this work. The thesis also suggests that the so-called EPFJ (Extended Particle Filter with Jittering) and the UPFJ (Unscented Particle Filter with Jittering) algorithms could be reasonable choices when dealingwith highly nonlinearmodels. In this part, also relevant issueswithin the particle filteringmethodology are discussed, such as the potential impact on estimation of the discount factor parameter, the time series length, and the number of particles used. Throughout this work, pseudo-codes are written for all filters studied and are implemented in RLanguage. The reported findings are obtained as the result of extensive MC studies, considering a variety of case-scenarios described in the thesis. The intrinsic characteristics of the model at hand guided -according to suitability– the choice of filters in each specific situation. The comparison of filters is based on the RMSE, the elapsed CPU-time and the degree of degeneracy. Finally, Chapter 7 includes the discussion, contributions, and future lines of research. Some complementary theoretical and practical aspects are presented in the appendix.
L’estimació seqüencial dels estats (filtratge) i la corresponent estimació simultània dels estats i els paràmetres fixos d’unmodel dinàmic formulat en forma d’espai d’estat –sigui lineal o no– constitueix un problema de rellevada importància enmolts camps, com ser a l’àrea de finances. L’objectiu principal d’aquesta tesi és el d’estimar seqüencialment i de manera eficient –des d’un punt de vista bayesià i usant lametodologia de filtratge de partícules– els estats i/o els paràmetres fixos d’unmodel d’espai d’estat dinàmic no estàndard: possiblement no lineal, no gaussià o no estacionari. El present treball consisteix de 7 capítols i s’organitza en dues parts. El Capítol 1 hi introdueix conceptes bàsics, lamotivació, el propòsit i l’estructura de la tesi. La primera part d’aquesta tesi (capítols 2 a 4) se centra únicament en l’estimació dels estats. El Capítol 2 presenta una revisió exhaustiva dels algorismes més clàssics no basats en simulacions (KF, EKF, UKF2) i els basats en simulacions (SIS, SIR, ASIR, EPF, UPF). Per a aquests filtres, tots esmentats en la literatura, amés de descriure’ls detalladament, s’ha unificat la notació amb l’objectiu que aquesta sigui consistent i comparable entre els diferents algorismes implementats al llarg d’aquest treball. Els capítols 3 i 4 se centren en la realització d’estudis Monte Carlo (MC) extensos que confirmen l’eficiència de la metodologia de filtratge de partícules per estimar els estats latents d’un procés dinàmic formulat en forma d’espai d’estat, sigui lineal o no. Alguns estudis MC complementaris es duen a terme per avaluar diferents aspectes de la metodologia de filtratge de partícules, com ser el problema de la degeneració, l’elecció de l’estratègia de remostreig, el nombre de partícules usades o la grandària de la sèrie temporal. Específicament, el Capítol 3 il·lustra el comportament de la metodologia de filtratge de partícules en un context lineal i gaussià en comparació de l’òptim i exacte filtre de Kalman. La capacitat de filtratge de les quatre variants de filtre de partícules estudiades (SIR, SIRopt, ASIR, KPF; l’últim sent un cas especial de l’algorisme EPF) es va avaluar sobre la base de dos processos de sèries temporals aparentment simples però importants: els anomenats Local Level Model (LLM) i el AR (1) plus noise, que són no estacionari i estacionari, respectivament. Aquest capítol estudia en profunditat temes rellevants dins de l’enfocament adoptat, coml’impacte en l’estimació de la relació entre el senyal i el soroll (SNR: signal-to-noise-ratio, en aquesta tesi), de la longitud de la sèrie temporal i del nombre de partícules. El Capítol 4 avalua i il·lustra el comportament de la metodologia de filtratge de partícules en un context no lineal. En concret, s’utilitza un model d’espai d’estat no lineal, no gaussià i no estacionari pres de la literatura per il·lustrar el comportament de quatre filtres de partícules (SIR, ASIR, EPF, UPF) en contraposició a dos filtres no basats en simulació ben coneguts (EKF, UKF). Aquí es comparen els esquemes de remostreig residual i estratificat i s’avalua l’efecte d’augmentar el nombre de partícules. A la segona part (capítols 5 i 6), es duen a terme també estudis MC extensos, però ara l’objectiu principal és l’estimació simultània dels estats i paràmetres fixos de certsmodels seleccionats. Aquesta àrea de recerca segueix sentmolt activa i és on aquesta tesi hi contribueixmés. El Capítol 5 proveeix una revisió parcial dels mètodes per dur a terme l’estimació simultània dels estats i paràmetres fixos a través de la metodologia de filtratge de partícules. Aquests filtres són una extensió d’aquells adoptats anteriorment només per estimar els estats. Aquí es realitza un estudi MC per estimar l’estat (nivell) i els dos paràmetres de variància del model LLM no estacionari; s’utilitzen quatre variants (LW, SIRJ, SIRoptJ, KPFJ) de filtre de partícules, sis escenaris típics del SNR i dos escenaris per a l’anomenat factor de descompte necessari en el pas de diversificació. En aquest capítol, es proposa la variant de filtre de partícules SIRJ (Sample Importance Resampling with Jittering) com a alternativa al filtre de referència de Liu iWest (LWPF). També es proposa i explora l’ús combinat d’una distribució d’importància basada en el filtre de Kalman i un pas de diversificació (jittering) que dóna lloc a la variant del filtre de partícules anomenada Kalman Particle Filteringwith Jittering (KPFJ). El Capítol 6 se centra en l’estimació dels estats i dels paràmetres fixos delmodel bàsic no estàndard de volatilitat estocàstica denominat Stochastic autoregressive model of order one: SARV (1). Després d’una introducció i descripció detallada de les característiques pròpies de sèries temporals financeres, es demostra mitjançant estudis MC la capacitat d’estimació de dues variants de filtre de partícules (SIRJ vs. LW(Liu iWest)) utilitzant dades simulades. El capítol acaba amb una aplicació a dos conjunts de dades reals dins de l’àrea financera: l’índex de rendiments espanyol IBEX 35 i els preus al comptat (en dòlars) del Brent europeu. La contribució en els capítols 5 i 6 consisteix en proposar noves variants de filtres de partícules, compoden ser el KPFJ, el SIRJ i el SIRoptJ (un cas especial de l’algorisme SIRJ utilitzant una distribució d’importància òptima) que s’han desenvolupat al llarg d’aquest treball. També se suggereix que els anomenats filtres de partícules EPFJ (Extended Particle Filter with Jittering) i UPFJ (Unscented Particle Filter with Jittering) podrien ser opcions raonables quan es tracta de models altament no lineals; el KPFJ sent un cas especial de l’algorisme EPFJ. En aquesta part, també es tracten aspectes rellevants dins de la metodologia de filtratge de partícules, com ser l’impacte potencial en l’estimació de la longitud de la sèrie temporal, el paràmetre de factor de descompte i el nombre de partícules. Al llarg d’aquest treball s’han escrit (i implementat en el llenguatge R) els pseudo-codis per a tots els filtres estudiats. Els resultats presentats s’obtenenmitjançant simulacionsMonte Carlo (MC) extenses, tenint en compte variats escenaris descrits en la tesi. Les característiques intrínseques del model baix estudi van guiar l’elecció dels filtres a comparar en cada situació específica. Amés, la comparació dels filtres es basa en el RMSE (RootMean Square Error), el temps de CPU i el grau de degeneració. Finalment, el Capítol 7 presenta la discussió, les contribucions i les línies futures de recerca. Alguns aspectes teòrics i pràctics complementaris es presenten en els apèndixs.
La estimación secuencial de los estados (filtrado) y la correspondiente estimación simultánea de los estados y los parámetros fijos de un modelo dinámico formulado en forma de espacio de estado –sea lineal o no– constituye un problema de relevada importancia enmuchos campos, como ser en el área de finanzas. El objetivo principal de esta tesis es el de estimar secuencialmente y de manera eficiente –desde un punto de vista bayesiano y usando la metodología de filtrado de partículas– los estados y/o los parámetros fijos de un modelo de espacio de estado dinámico no estándar: posiblemente no lineal, no gaussiano o no estacionario. El presente trabajo consta de 7 capítulos y se organiza en dos partes. El Capítulo 1 introduce conceptos básicos, la motivación, el propósito y la estructura de la tesis. La primera parte de esta tesis (capítulos 2 a 4) se centra únicamente en la estimación de los estados. El Capítulo 2 presenta una revisión exhaustiva de los algoritmos más clásicos no basados en simulaciones (KF, EKF,UKF3) y los basados en simulaciones (SIS, SIR, ASIR, EPF, UPF). Para todos estos filtros, mencionados en la literatura, además de describirlos en detalle, se ha unificado la notación con el objetivo de que ésta sea consistente y comparable entre los diferentes algoritmos implementados a lo largo de este trabajo. Los capítulos 3 y 4 se centran en la realización de estudios Monte Carlo (MC) extensos que confirman la eficiencia de la metodología de filtrado de partículas para estimar los estados latentes de un proceso dinámico formulado en forma de espacio de estado, sea lineal o no. Algunos estudios MC complementarios se llevan a cabo para evaluar varios aspectos de la metodología de filtrado de partículas, como ser el problema de la degeneración, la elección de la estrategia de remuestreo, el número de partículas usadas o el tamaño de la serie temporal. Específicamente, el Capítulo 3 ilustra el comportamiento de lametodología de filtrado de partículas en un contexto lineal y gaussiano en comparación con el óptimo y exacto filtro de Kalman. La capacidad de filtrado de las cuatro variantes de filtro de partículas estudiadas (SIR, SIRopt, ASIR, KPF; el último siendo un caso especial del algoritmo EPF) se evaluó en base a dos procesos de series temporales aparentemente simples pero importantes: los denominados Local Level Model (LLM) y el AR (1) plus noise, que son no estacionario y estacionario, respectivamente. Este capítulo estudia en profundidad temas relevantes dentro del enfoque adoptado, como el impacto en la estimación de la relación entre la señal y el ruido (SNR: signal-to-noise-ratio, en esta tesis), de la longitud de la serie temporal y del número de partículas. El Capítulo 4 evalúa e ilustra el comportamiento de la metodología de filtrado de partículas en un contexto no lineal. En concreto, se utiliza un modelo de espacio de estado no lineal, no gaussiano y no estacionario tomado de la literatura para ilustrar el comportamiento de cuatro filtros de partículas (SIR, ASIR, EPF, UPF) en contraposición a dos filtros no basados en simulación bien conocidos (EKF, UKF). Aquí se comparan los esquemas de remuestreo residual y estratificado y se evalúa el efecto de aumentar el número de partículas. En la segunda parte (capítulos 5 y 6), se llevan a cabo también estudios MC extensos, pero ahora el objetivo principal es la estimación simultánea de los estados y parámetros fijos de ciertos modelos seleccionados. Esta área de investigación sigue siendo muy activa y es donde esta tesis contribuye más. El Capítulo 5 provee una revisión parcial de losmétodos para llevar a cabo la estimación simultánea de los estados y parámetros fijos a través de lametodología de filtrado de partículas. Dichos filtros son una extensión de aquellos adoptados anteriormente sólo para estimar los estados. Aquí se realiza un estudio MC para estimar el estado (nivel) y los dos parámetros de varianza del modelo LLM no estacionario; se utilizan cuatro variantes (LW, SIRJ, SIRoptJ, KPFJ) de filtro de partículas, seis escenarios típicos del SNR y dos escenarios para el llamado factor de descuento necesario en el paso de diversificación. En este capítulo, se propone la variante de filtro de partículas SIRJ (Sample Importance resampling with Jittering) como alternativa al filtro de referencia de Liu y West (LW PF). También se propone y explora el uso combinado de una distribución de importancia basada en el filtro de Kalman y un paso de diversificación (jittering) que da lugar a la variante del filtro de partículas denominada Kalman Particle Filteringwith Jittering (KPFJ). El Capítulo 6 se centra en la estimación de los estados y de los parámetros fijos del modelo básico no estándar de volatilidad estocástica denominado Stochastic autoregressivemodel of order one: SARV (1). Después de una introducción y descripción detallada de las características propias de series temporales financieras, se demuestra mediante estudios MC la capacidad de estimación de dos variantes de filtro de partículas (SIRJ vs. LW (Liu y West)) utilizando datos simulados. El capítulo termina con una aplicación a dos conjuntos de datos reales dentro del área financiera: el índice de rendimientos español IBEX 35 y los precios al contado (en dólares) del Brent europeo. La contribución en los capítulos 5 y 6 consiste en proponer nuevas variantes de filtros de partículas, como pueden ser el KPFJ, el SIRJ y el SIRoptJ (Caso especial del algoritmo SIRJ utilizando una distribución de importancia óptima) que se han desarrollado a lo largo de este trabajo. También se sugiere que los llamados filtros de partículas EPFJ (Extended Particle Filter with Jittering) y UPFJ (Unscented Particle Filter with Jittering) podrían ser opciones razonables cuando se trata de modelos altamente no lineales; el KPFJ siendo un caso especial del algoritmo EPFJ. En esta parte, también se tratan aspectos relevantes dentro de lametodología de filtrado de partículas, como ser el impacto potencial en la estimación de la longitud de la serie temporal, el parámetro de factor de descuento y el número de partículas. A lo largo de este trabajo se han escrito (e implementado en el lenguaje R) los pseudo-códigos para todos los filtros estudiados. Los resultados presentados se obtienen mediante simulaciones Monte Carlo (MC) extensas, teniendo en cuenta variados escenarios descritos en la tesis. Las características intrínsecas del modelo bajo estudio guiaron la elección de los filtros a comparar en cada situación específica. Además, la comparación de los filtros se basa en el RMSE (Root Mean Square Error), el tiempo de CPU y el grado de degeneración. Finalmente, el Capítulo 7 presenta la discusión, las contribuciones y las líneas futuras de investigación. Algunos aspectos teóricos y prácticos complementarios se presentan en los apéndices.

This dissertation deals with the challenging tasks of real-time extended and group object tracking. The problems are formulated as joint parameter and state estimation of dynamic systems. The solutions proposed are formulated within a general nonlinear framework and are based on the Sequential Monte Carlo (SMC) method, also known as Particle Filtering (PF) method. Eour different solutions are proposed for the extended object tracking problem. The first two are based on border parametrisation of the visible surface of the extended object. The likelihood functions are derived for two different scenarios - one without clutter in the measurements and another one in the presence of clutter. In the third approach the kernel density estimation technique is utilised to approximate the joint posterior density of the target dynamic state and static size parameters. The forth proposed approach solves the extended object tracking problem based on the recently emerged SMC method combined with interval analysis , called Box Particle Filter (Box P F). Simulation results for all of the developed algorithms show accurate online tracking, with very good estimates both for the target kinematic states and for the parameters of the target extent. In addition, the performance of the Box PF and the border parametrised PF is validated utilising real measurements from laser range scanners obtained within a prototype security system replicating an airport corridor.

Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
29
Cataloged from student submitted PDF version of thesis.
Includes bibliographical references (pages 56-57).
Sequential Monte Carlo (SMC) methods form a popular class of Bayesian inference algorithms. While originally applied primarily to state-space models, SMC is increasingly being used as a general-purpose Bayesian inference tool. Traditional analyses of SMC algorithms focus on their usage for approximating expectations with respect to the posterior of a Bayesian model. However, these algorithms can also be used to obtain approximate samples from the posterior distribution of interest. We investigate the asymptotic and non-asymptotic properties of SMC from this sampling viewpoint. Let P be a distribution of interest, such as a Bayesian posterior, and let P be a random estimator of P generated by an SMC algorithm. We study ... i.e., the law of a sample drawn from P, as the number of particles tends to infinity. We give convergence rates of the Kullback-Leibler divergence KL ... as well as necessary and sufficient conditions for the resampled version of P to asymptotically dominate the non-resampled version from this KL divergence perspective. Versions of these results are given for both the full joint and the filtering settings. In the filtering case we also provide time-uniform bounds under a natural mixing condition. Our results open up the possibility of extending recent analyses of adaptive SMC algorithms for expectation approximation to the sampling setting.
by Jonathan H. Huggins.
S.M.

Many processes we encounter in our daily lives are dynamical systems that can be described mathematically using state-space models. Exact inference of both states and parameters in these models is, in general, intractable. Instead, approximate methods, such as sequential Monte Carlo and Markov chain Monte Carlo, are used to infer quantities of interest. However, sample based inference inherently introduce variance in the estimates. In this thesis we explore different aspects of how conjugacy relations in a model can improve the performance of sequential Monte Carlo-based inference methods.A conjugacy relation between the prior distribution and the likelihood implies that the posterior distribution has the same distributional form as the prior, allowing for analytic updates in place of numerical integration. In Paper I we consider state inference in state-space models where the transition density is intractable. By adding artificial noise conjugate to the observation density we can design an efficient proposal for sequential Monte Carlo inference that can reduce the variance of the state estimates. Conjugacy can also be utilized in the setting of parameter inference. In Paper II we show that the performance of particle Gibbs-type samplers, in terms of the autocorrelation of the samples, can be improved when conjugacy relations allow for marginalizing out the dependence on parameters in the state update.Despite enabling analytical evaluation of integrals, the derivation and implementation of conjugacy updates is cumbersome in all but the simplest cases, which limits the usefulness in practice. Recently, the emerging  field of probabilistic programming has changed this, by providing a framework for automating inference in probabilistic models - including identifying and utilizing conjugacy relations. In Paper II we make use of probabilistic programming to automatically exploit conjugacy in an epidemiological state-space model describing the spread of dengue fever.

Dans de nombreux problèmes, des modèles complexes non-Gaussiens et/ou non-linéaires sont nécessaires pour décrire précisément le système physique étudié. Dans ce contexte, les algorithmes de Monte-Carlo sont des outils flexibles et puissants permettant de résoudre de tels problèmes d’inférence. Toutefois, en présence de loi a posteriori multimodale et/ou de grande dimension, les méthodes classiques de Monte-Carlo peuvent conduire à des résultats non satisfaisants. Dans cette thèse, nous étudions une approche plus robuste et efficace: échantillonneur séquentiel de Monte-Carlo. Bien que cette approche présente de nombreux avantages par rapport aux méthodes traditionnelles de Monte-Carlo, le potentiel de cette technique est cependant très largement sous-exploité en traitement du signal. L’objectif de cette thèse est donc de proposer de nouvelles stratégies permettant d’améliorer l’efficacité de cet algorithme et ensuite de faciliter sa mise en œuvre pratique. Pour ce faire, nous proposons une approche adaptive qui sélectionne la séquence de distributions minimisant la variance asymptotique de l'estimateur de la constante de normalisation de la loi a posteriori. Deuxièmement, nous proposons un mécanisme de correction qui permet d’améliorer l’efficacité globale de la méthode en utilisant toutes les particules générées à travers toutes les itérations de l’algorithme (au lieu d’uniquement celles de la dernière itération). Enfin pour illustrer l’utilité de cette approche ainsi que des stratégies proposées, nous utilisons cet algorithme dans deux problèmes complexes: la localisation de sources multiples dans les réseaux de capteurs et la régression Bayésienne pénalisée
In many problems, complex non-Gaussian and/or nonlinear models are required to accurately describe a physical system of interest. In such cases, Monte Carlo algorithms are remarkably flexible and extremely powerful to solve such inference problems. However, in the presence of high-dimensional and/or multimodal posterior distribution, standard Monte-Carlo techniques could lead to poor performance. In this thesis, the study is focused on Sequential Monte-Carlo Sampler, a more robust and efficient Monte Carlo algorithm. Although this approach presents many advantages over traditional Monte-Carlo methods, the potential of this emergent technique is however largely underexploited in signal processing. In this thesis, we therefore focus our study on this technique by aiming at proposing some novel strategies that will improve the efficiency and facilitate practical implementation of the SMC sampler. Firstly, we propose an automatic and adaptive strategy that selects the sequence of distributions within the SMC sampler that approximately minimizes the asymptotic variance of the estimator of the posterior normalization constant. Secondly, we present an original contribution in order to improve the global efficiency of the SMC sampler by introducing some correction mechanisms that allow the use of the particles generated through all the iterations of the algorithm (instead of only particles from the last iteration). Finally, to illustrate the usefulness of such approaches, we apply the SMC sampler integrating our proposed improvement strategies to two challenging practical problems: Multiple source localization in wireless sensor networks and Bayesian penalized regression

Nonlinear state space models (SSMs) are a useful class of models to describe many different kinds of systems. Some examples of its applications are to model; the volatility in financial markets, the number of infected persons during an influenza epidemic and the annual number of major earthquakes around the world. In this thesis, we are concerned with state inference, parameter inference and input design for nonlinear SSMs based on sequential Monte Carlo (SMC) methods. The state inference problem consists of estimating some latent variable that is not directly observable in the output from the system. The parameter inference problem is concerned with fitting a pre-specified model structure to the observed output from the system. In input design, we are interested in constructing an input to the system, which maximises the information that is available about the parameters in the system output. All of these problems are analytically intractable for nonlinear SSMs. Instead, we make use of SMC to approximate the solution to the state inference problem and to solve the input design problem. Furthermore, we make use of Markov chain Monte Carlo (MCMC) and Bayesian optimisation (BO) to solve the parameter inference problem. In this thesis, we propose new methods for parameter inference in SSMs using both Bayesian and maximum likelihood inference. More specifically, we propose a new proposal for the particle Metropolis-Hastings algorithm, which includes gradient and Hessian information about the target distribution. We demonstrate that the use of this proposal can reduce the length of the burn-in phase and improve the mixing of the Markov chain. Furthermore, we develop a novel parameter inference method based on the combination of BO and SMC. We demonstrate that this method requires a relatively small amount of samples from the analytically intractable likelihood, which are computationally costly to obtain. Therefore, it could be a good alternative to other optimisation based parameter inference methods. The proposed BO and SMC combination is also extended for parameter inference in nonlinear SSMs with intractable likelihoods using approximate Bayesian computations. This method is used for parameter inference in a stochastic volatility model with -stable returns using real-world financial data. Finally, we develop a novel method for input design in nonlinear SSMs which makes use of SMC methods to estimate the expected information matrix. This information is used in combination with graph theory and convex optimisation to estimate optimal inputs with amplitude constraints. We also consider parameter estimation in ARX models with Student-t innovations and unknown model orders. Two different algorithms are used for this inference: reversible Jump Markov chain Monte Carlo and Gibbs sampling with sparseness priors. These methods are used to model real-world EEG data with promising results.

Thesis (Ph. D.)--Ohio State University, 2004.
Title from first page of PDF file. Document formatted into pages; contains xiv, 117 p. : ill. (some col.). Advisors: Bhavik R. Bakshi and Prem K. Goel, Department of Chemical Engineering. Includes bibliographical references (p. 114-117).

State space models represent a flexible class of Bayesian time series models which can be applied to model latent state stochastic processes. Sequential Monte Carlo (SMC) algorithms, also known as particle filters, are perhaps the most widely used methodology for inference in such models, particularly when the model is nonlinear and cannot be evaluated analytically. The SMC methodology allows for the sequential analysis of state space models in online settings for fast inference, but can also be applied to study online problems. This area of research has grown rapidly over the past 20 years and has lead to the development of important theoretical results.