Sequential Monte Carlo

Mon mémoire a pour objectif d’étudier le comportement de l’algorithme du filtrage particulaire pour des espaces d’état de grandes dimension. Cette méthode est utilisée dans de nombreux domaines, et particulièrement dans les statistiques bayésiennes. Elle permet par exemple d’estimer l’état d’un système à partir d’observations bruitées qu’on pourrait en faire. On retrouve ainsi, lorsqu’on augmente la dimension, des effets de bord et des problème de convergence assez rapidement, compte tenu de la croissance exponentielle de l’erreur. Ce mémoire essaye de comprendre les tenants et aboutissants de cette situation.

Historical Linguistics studies language change over time. If a group of languages derives from changes to a common ancestor language (proto-language) then they are said to be related. Whenever there exists a lack of written records for an ancestor language, a relevant question in Historical Linguistics is to determine whether two languages are related.

The gold standard for finding these relationships is the Comparative Method. Despite the success of the Comparative Method in finding language relationships, it suffers from at least two limitations. First, the Comparative Method involves the manual comparison of various features from a group of languages. Second, the Comparative Method doesn't provide a numerical measure of evidence for how much the database under consideration corroborates an hypothesis.

Given the above limitations, the field of Computational Historical Linguistics is presented as a complement to the Comparative Method. This field has experienced a recent expansion with the adaptation of methods from biological phylogenetics. Nevertheless, there is debate whether the evolutionary models used in phylogenetics also incorporate valid linguistical assumptions.

In this thesis, I propose a new (probability) model for the evolution of the phonology of languages. A relevant innovation of this model is that it captures the regularity of sound changes. I also describe the software that I created in order to assist in incorporating into the model a linguist's expert knowledge. I show that the knowledge obtained in this way agrees with qualitative statements known to linguists. Finally, I present a new algorithm used to compute the probability of linguistic hypotheses regarding language relationships and the occurence of regular sound changes. The main problem that this algorithm overcomes is that it efficiently explores
the possible regular sound changes, mutations in languages that simultaneously affect several words. In order to overcome this challange, I present a new variant of Nested Sequential Monte Carlo that is used to explore the large space of language relationships and regular sound changes. To the best of my knowledge, this is the first algorithm that can perform joint inference on regular sound changes and evolutionary trees. I show that this algorithm is a special case of Sequential Importance Resampling.

In this paper we propose a sequential Monte Carlo algorithm to estimate a stochastic volatility model with leverage eect, non constant conditional mean and jumps. Our idea relies on the auxiliary particle lter algorithm together with the Markov Chain Monte Carlo (MCMC) method- ology. Our method allows to sequentially evaluate the parameters and the latent processes involved in the dynamic of interest. An empirical applica- tion on simulated data and on the Standard & Poor's 500 index is presented to study the performance of the algorithm implemented.

With the advent of Big Data, inference in very large datasets is becoming increasingly common. Furthermore, business models and operational strategies demand ever more often an online, user real-time feedback solution in contrast with standard batch methods. This involves performing inference on streaming data even before it is persisted. A flexible and elegant way of performing this task is by modelling data as a Dynamic Generalised Linear Model (DGLM), fundamentally a State-Space Model (SSM) which combines a linear transition state model with an observational model following a distribution from the exponential family. Here we will explain the basics of a fully Bayesian online and sequential state estimation using sequential Monte Carlo (SMC) methods and how this class of algorithms can be implemented to perform state and parameter estimation simultaneously. The merits and shortcomings of these methods will also be discussed.

In this paper we present an online approach for joint detection and tracking for multiple targets using variable rate particle filters (VRPFs). Unlike conventional models and particle filters, the proposed method utilises the applied forces (tangential and radial components) to model target motions and does not assume the hidden state to change at the same rate as the observations. In effect not only does the proposed method enable us to model parsimoniously the manoeuvring behaviours of targets with a single dynamical model but it also provides a more efficient framework for recursive estimation of the targets' positions since much fewer states will be estimated. In addition, a target detection/termination module will be integrated in the proposed method in which a track initiation, termination, or maintenance move is randomly executed using Bayesian Monte Carlo methods. To model a more realistic observation environment Poisson process is chosen for all target originating and spurious measurements. Unlike other observation models, the proposed model does not require extensive computation for data association between active targets and observations, prior to target state estimation, as a result. To improve the quality of the particles we adopt a data-dependent importance sampling strategy in which the latest observations are involved when new particles are updated. This enables the target states to be updated as new observations arrive while keeping the number of states sufficiently low to track the manoeuvres of the targets. Computer simulations demonstrate the potential of the proposed method for detecting and tracking multiple highly manoeuverable targets in a hostile environment with high clutter density and low detection probability.

— Random finite sets are natural representations of multi-target states and observations that allow multi-sensor multi-target filtering to fit in the unifying random set framework for Data Fusion. Although the foundation has been established in the form of Finite Set Statistics (FISST), its relationship to conventional probability is not clear. Furthermore, optimal Bayesian multi-target filtering is not yet practical due to the inherent computational hurdle. Even the Probability Hypothesis Density (PHD) filter, which propagates only the first moment (or PHD) instead of the full multi-target posterior, still involves multiple integrals with no closed forms in general. This article establishes the relationship between FISST and conventional probability that leads to the development of a sequential Monte Carlo (SMC) multi-target filter. In addition, a SMC implementation of the PHD filter is proposed and demonstrated on a number of simulated scenarios. Both of the proposed filters are suitable for problems involving non-linear non-Gaussian dynamics. Convergence results for these filters are also established.

Localization schemes for wireless sensor networks can be classified as range-based or range-free. They differ in the information used for localization. Range-based methods use range measurements, while range-free techniques only use the content of the messages. None of the existing algorithms evaluate both types of information. Most of the localization schemes do not consider mobility. In this paper, a Sequential

The hydration of the hydroxyl OH radical has been investigated by microsolvation modeling and statistical mechanics Monte Carlo simulations. The microsolvation approach was based on density functional theory (DFT) calculations for OH-(H2O)(1-6) and (H2O)(1-7) clusters. The results from microsolvation indicate that the binding enthalpies of the OH radical and water molecule to small water clusters are similar. Monte Carlo simulations predict that the hydration enthalpy of the OH radical, Delta(hyd)H(OH,g), is -39.1 kJ mol(-1). From this value we have estimated that the band gap of liquid water is 6.88 eV, which is in excellent agreement with the result of Coe [J. Chem. Phys. 107, 6023 (1997)]. We have compared the structure of the hydrated OH solution with the structure of pure liquid water. The structural differences between the two systems reflect the strong role played by the OH radical as a proton donor in water. From sequential Monte Carlo/DFT calculations the dipole moment of the OH radical in liquid water is 2.2+/-0.1 D, which is similar to33% above the experimental gas phase value (1.66 D).

The reliability performance of transmission system substations is critical for overall system reliability. Failure events at main grid substations can lead to multiple outages with possible cascading consequences and widespread loss of customer load. Considerable knowledge on substation reliability analysis has been gained from the application of primarily analytical methods. The complexity, however, of substation switching operations does not lend itself to pure analytical treatment. Simulation methods are more suitable as the mathematical modeling of the relationship between events and outcomes is not always possible. The paper expands the existing methodology and describes a method to perform reliability evaluation of substation switching arrangements based on the sequential Monte Carlo simulation. The method is applied in the reliability analysis and comparison of the most commonly used substation switching configurations. The paper shows how the results of the analysis can be applied to model substations in a composite system reliability evaluation.

The electronic polarization of acetone in liquid water is obtained using an iterative procedure in the sequential Monte Carlo/quantum mechanics methodology. MP2/aug-cc-pVDZ calculations of the dipole moment of acetone in water are performed on statistically uncorrelated structures extracted from isothermic-isobaric MC simulations. After electrostatic equilibrium the calculated dipole moment of acetone is obtained as 4.80 ± 0.03 D, with an increase of 60% compared to the gas phase value. This solute polarization is used to obtain the shift of 1650 ± 42 cm -1 for the n-π ∗ transition of acetone in water, in agreement with the experimental result of 1500-1700 cm -1.

Given the actual context of increased dispersed generation and highly loaded lines, probabilistic methods are more and more required to take into account the stochastic behavior of electrical network components (possible spate of outages by use of the electrical network near its physical limits) in reliability studies. To implement those probabilistic methods, numerical Monte Carlo simulations are typically used and can be divided in two categories: sequential and non-sequential techniques.This paper deals with two wind speed sampling methods adapted for non-sequential Monte Carlo simulations, among which an original approach based on the combination of a mean statistical law (for a large geographical area like a country) and Normal distributions (to characterize smaller wind speed zones inside the country). Both proposed techniques are then applied on a self-developed non-sequential Monte Carlo simulation only taking into account generation units outages and load changes (hierarchical level HL-I). Finally, the collected simulation results allow, not only, to evaluate the impact of sampling methods on the collected reliability indices but also to decide which proposed technique will lead to the most interesting situations (larger wind power fluctuations from one state to the other) for the electrical network operation management. Note that our simulations are applied to the Belgian production park. Copyright © 2008 John Wiley & Sons, Ltd.

This paper shows how one can use Sequential Monte Carlo methods to perform what is typically done using Markov chain Monte Carlo methods. This leads to a general class of principled integration and genetic type optimization methods based on interacting particle systems.