Transcript Document

Nonlinear and Non-Gaussian
Estimation with A Focus on
Particle Filters
Prasanth Jeevan
Mary Knox
May 12, 2006
Background
• Optimal linear filters
 Wiener  Stationary
 Kalman  Gaussian Posterior, p(x|y)
• Filters for nonlinear systems
 Extended Kalman
 Particle
Extended Kalman Filter (EKF)
• Locally linearize the non-linear functions
• Assume p(xk|y1,…,k) is Gaussian
Particle Filter (PF)
• Weighted point mass or “particle” representation
of possibly intractable posterior probability
density functions, p(x|y)
• Estimates recursively in time allowing for online
calculations
• Attempts to place particles in important regions
of the posterior pdf
• O(N) complexity on number of particles
Particle Filter Background
[Ristic et. al. 2004]
• Monte Carlo Estimation
• Pick N>>1 “particles” with distribution p(x)
Assumption: xi is independent
Importance Sampling
• Cannot sample directly from p(x)
• Instead sample from known importance
density, q(x), where:
• Estimate I from samples and importance
weights
where
Sequential Importance Sampling
(SIS)
• Iteratively represent posterior density function by random
samples with associated weights
Assumptions: xk Hidden Markov process, yk conditionally
independent given xk
Degeneracy
• Variance of sample weights increases with time
if importance density not optimal [Doucet 2000]
• In a few cycles all but one particle will have
negligible weights
 PF will updating particles that contribute little in
approximating the posterior
• Neff, estimate of effective sample size
[Kong et. al. 1994]:
Optimal Importance Density
[Doucet et. al. 2000]
• Minimizes variance of importance weights to
prevent degeneracy
• Rarely possible to obtain, instead often use
Resampling
• Generate new set of
samples from:
• Weights are equal
after i.i.d. sampling
• O(N) complexity
• Coupled with SIS,
these are the two key
components of a PF
Sample Impoverishment
• Set of particles with
low diversity
 Particles with high
weights are selected
more often
Sampling Importance
Resampling (SIR)
[Gordon et. al. 1993]
• Importance density is the transitional prior
• Resampling at every time step
SIR Pros and Cons
• Pro: importance density and weight
updates are easy to evaluate
• Con: Observations not used when
transitioning state to next time step
A Cycle of SIR
Auxiliary SIR - Motivation
[Pitt and Shephard 1999]
• Want to use observation
when exploring the state
space ( ’s)
 To have particles in regions of
high likelihood
• Incorporate
at time k-1
into resampling
 Looking one step ahead to
choose particles
ASIR - from SIR
• From SIR we had
• If we move the likelihood inside we get:
• We don’t have
• Use
though
, a characterization of
 such as
given
ASIR continued
• So then we get:
• And the new importance weight becomes:
ASIR Pros & Cons
• Pro
 Can be less sensitive to peaked likelihoods and
outliers by using observation
 Outliers - Model-improbable states that can result in a
dramatic loss of high-weight particles
• Cons
 Added computation per cycle
 If
is a bad characterization of
(ie. large
process noise), then resampling suffers, and
performance can degrade
Simulation Linear
• System Equations:
where v ~ N(0,6) and w ~ N(0,5)
Simulation Linear
10 Samples
Simulation Linear
50 Samples
Simulation Linear
Table 1: Mean Squared Error Per Time Step
Filter
10
Number of Particles
50
100
KF
0.0349
0.0351
ASIR
0.7792
SIR
0.9053
1000
0.0352
0.0886
0.0350
0.0417
0.0977
0.0496
0.0354
0.0350
Simulation Nonlinear
• System Equations:
where v ~ N(0,6) and w ~ N(0,5)
Simulation Nonlinear
10 Samples
Simulation Nonlinear
50 Samples
Simulation Nonlinear
100 Samples
Simulation Nonlinear
1000 Samples
Simulation Nonlinear
Table 2: Mean Squared Error Per Time Step
Filter
10
EKF
812.08
ASIR
30.14
37.97
SIR
Number of Particles
50
100
1000
826.20
20.15
827.94
18.81
838.75
17.86
22.62
21.49
19.78
Conclusion
• PF approaches KF optimal estimates as
N
• PF better than EKF for nonlinear systems
• ASIR generates ‘better particles’ in certain
conditions by incorporating the observation
• PF is applicable to a broad class of system
dynamics
 Simulation approaches have their own limitations
 Degeneracy and sample impoverishment
Conclusion (2)
• Particle filters composed of SIS and
resampling
 Many variations to improve efficiency (both
computationally and for getting ‘better’
particles)
• Other PFs: Regularized PF,
(EKF/UKF)+PF, etc.