particle filter
(1.8 hours to learn)
Summary
The particle filter is a Monte Carlo algorithm for posterior inference in temporal models. The posterior is approximated with a weighted set of discrete particles. In each step, each particle's state is extended according to a proposal distribution, and its weight is updated based on the likelihood of the evidence. The algorithm is useful in robotics and in visual tracking because it doesn't require storing the entire history.
Context
This concept has the prerequisites:
- hidden Markov models (The particle filter is an algorithm for inference in hidden Markov models.)
- Monte Carlo estimation (The particle filter is a Monte Carlo algorithm.)
- importance sampling (Importance sampling is one step of the particle filter.)
- conditional distributions (The particle filter approximates the conditional distribution of the states given the observations.)
Goals
- Know the steps of the particle filter algorithm.
- Be aware that an important advantage of the algorithm is that it does not require storing the entire history.
- Be aware that the following are major sources of variance in the estimator, and that effective performance can depend on the details of the implementation:
- the proposal distribution
- the resampling method
Core resources (read/watch one of the following)
-Paid-
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location:
Section 23.5, "Particle filtering," pages 823-831
→ Probabilistic Graphical Models: Principles and Techniques
A very comprehensive textbook for a graduate-level course on probabilistic AI.
Location:
Section 15.3.3, "Particle filtering," pages 665-674
→ Monte Carlo Statistical Methods (2005)
A monograph on Monte Carlo methods.
- Section 14.2, "Generalized importance sampling," pages 546-547
- Section 14.3, "Particle systems," pages 547-559
Supplemental resources (the following are optional, but you may find them useful)
-Paid-
→ Monte Carlo Strategies in Scientific Computing (2001)
A monograph on Monte Carlo methods.
Location:
Section 3.3, "Nonlinear filtering," pages 64-67
See also
- The particle filter is a special case of the more general sequential Monte Carlo framework.