Particle Filtering (Approximate Filtering for HMMs)
Particle filtering is an approximate inference algorithm for Hidden Markov Models that replaces exact belief tables with a finite set of samples (“particles”) when the state space is too large or continuous for the forward algorithm to be tractable. While the forward algorithm computes the exact filtering distribution by summing over all states, particle filtering approximates this same distribution using sampling.
Instead of storing a full probability distribution over states, particle filtering maintains a list of particles, where each particle represents a possible value of the hidden state at time . The belief distribution is represented empirically: the probability of a state is proportional to the fraction of particles occupying that state. This approximation is effective when , where is the size of the state space, yet still large enough to capture the dominant modes of the distribution.
Particle filtering proceeds iteratively and mirrors the structure of the forward algorithm, consisting of a time elapse update followed by an observation update at each timestep. During the time elapse update, each particle is propagated forward by sampling from the transition model . This step is analogous to prior sampling in Bayes nets: the transition dynamics are reflected in how particles spread across states.
During the observation update, particles are weighted according to how well they explain the newly observed evidence. For a particle in state and observation , the particle is assigned a weight proportional to the sensor likelihood . These weights are then aggregated by state and normalized to form a probability distribution over states. If all particle weights are zero, the algorithm reinitializes the particles, reflecting a failure to explain the evidence under the current sample set.
Finally, the algorithm performs a resampling step, drawing a new set of particles from the normalized weight distribution. States with higher likelihood under the evidence are more likely to be resampled, concentrating computational effort on high-probability regions of the state space. This resampling step is what allows particle filtering to continually refine its approximation as new evidence arrives.