An Introduction to Sequential Monte Carlo Methods and Particle Filtering and Smoothing
Brad Moskowitz
Metron, Inc.
A Monte Carlo method is an algorithm which relies on repeated random samples or trials to compute its results. The set of samples produced is a finite approximation of a probability distribution, and the desired results may include this distribution itself as well as various properties of the distribution and quantities derived from the distribution. Sequential problems are those for which the data arrive in a sequence over time ("on-line") and new or updated results are required shortly after each arrival of new data. The application of Monte Carlo methods to solve sequential problems is what leads to Sequential Monte Carlo Methods.
Particle filters are the most common form of Sequential Monte Carlo method (in fact the names are often used synonymously). A particle filter is a Sequential Monte Carlo method in which the sample is a set of weighted particles in a state-space. These particles move forward in time according to a motion model or system equation and are updated according to a measurement model each time that new data arrive (using Bayes' rule). A particle filter is often used to estimate the unknown state within the state space of some object of interest, for instance something being tracked or monitored. Particle filters typically apply to the same kinds of problems as Kalman filters and various non-linear extensions of them, such as the extended Kalman filter (EKF) or unscented Kalman filter (UKF). However, the principal advantage of particle filters is that with sufficient sample sizes they can approach the Bayesian optimal estimate, even for systems which are non-linear and non-Gaussian. There are fewer approximations in the model and therefore more accurate results are possible. Particle filters are also conceptually very simple in many instances.
In this talk I will review the mathematical basis for particle filters, taking a Bayesian approach. I will also discuss various techniques which are used in practice to improve particle filter results. Finally, time permitting I will also touch on the related subject of particle smoothing.