Particle Filters for Tracking on Large Dimensional State
Spaces with Frequently Multimodal Likelihoods (and Posteriors)
| Papers (key
idea) |
Papers (applications) | Software |
Abstract |
Some Details |
Talks |
Other Papers |
Short Abstract:
We study efficient importance sampling techniques for particle
filtering (PF) when either (a) the observation likelihood (OL) is
frequently multimodal or heavy-tailed, or (b) the state space dimension
is large or both. When the OL is multimodal, but the state transition
pdf (STP) is narrow enough, the optimal importance density is
usually unimodal. Under this assumption, many techniques have been
proposed. But when the STP is broad, this assumption does not hold. We
study how existing techniques can be generalized to situations where
the optimal importance density is multimodal, but is unimodal
conditioned on a part of the state vector. Sufficient conditions to
test for the unimodality of this conditional posterior are derived. Our
result is directly extendable to testing for unimodality of any
posterior.
The number of particles, N, to accurately track
using a PF increases with state space dimension, thus making any
regular PF impractical for large dimensional tracking problems. But in
most such problems, most of the state change occurs in only a few
dimensions, while the change in the rest of the dimensions is small. We
propose to replace importance sampling from a large part of the state
space (whose conditional posterior is narrow enough) by just tracking
the mode of the conditional posterior. This introduces some extra
error, but it also greatly reduces the importance sampling dimension.
The net effect is much smaller error for a given N, especially when the
available N is small. %that a much smaller N suffices for a given error.
An important class of large dimensional problems
with multimodal OL is tracking spatially varying physical quantities
such as temperature or pressure in a large area using a network of
sensors which may be nonlinear and/or may have non-negligible failure
probabilities. Improved performance of our proposed algorithms over
existing PFs is demonstrated for this problem.
Some Details
Tracking is
the problem of causally estimating a hidden sequence of vectors, called
states,
from a sequence of observations that may be noisy and nonlinear
functions of
the state. We are developing practically implementable particle
filtering
algorithms for tracking on large dimensional state spaces. Some
examples of
important large dimensional problems are: (i) tracking the boundary
contour of
a moving/deforming object or region-of-interest from image sequences,
e.g. the
boundary of a brain tumor in sequential MRI slices or of the beating
heart;
(ii) tracking spatially varying physical quantities, e.g. temperature
or
pressure, using measurements from a network of sensors; or (iii)
time-varying
input-output transfer function estimation, e.g. neuronal response
estimation.
In
many real
applications, the observation likelihood (OL) may be heavy tailed (e.g.
due to
outliers) or multimodal, for e.g. when there are two different types of
sensors
tracking temperature at one location, each with some probability of
failure.
The number of possible modes becomes very large when tracking
temperature at
all sensor nodes. In contour tracking, multiple OL modes occur due to
cluttering objects in the background or foreground (partial occlusions)
or due
to low contrast imagery. These are examples of situations where
particle
filtering is really required (EKF, UKF, PMT etc will not work). Direct
application of particle filters for large dimensional problems is
impractical,
due to the reduction in effective particle size as dimension increases.
But, in
most large dimensional systems, at any given time, “most of the state
change”
occurs in a small number of dimensions (“effective basis”) while the
change in
the rest of the state space (“residual space”) is “small”. The
effective basis
can be time varying. This idea forms the basis of our work.
Under
certain
assumptions that imply narrowness of the state transition prior, many
efficient
importance sampling techniques have been proposed in literature. For
large
dimensional state spaces (LDSS), these assumptions may not always hold.
But, it
is usually true that at a given time, state change in all except a few
dimensions is small. We use this fact to design a simple modification (called PF-EIS)
of an existing importance sampling technique. Also,
importance sampling on an LDSS is expensive (requires large number of
particles, N) even with the best technique. But if the “residual space”
variance is small enough, we can replace importance sampling in
residual space
by posterior Mode Tracking (MT). We call
this idea PF-