Filtering Via Simulation: Auxiliary Particle Filters
Pitt, Michael K., Shephard, Neil, Journal of the American Statistical Association
In this article we model a time series [y.sub.t], t = 1, . . ., n, as being conditionally independent given an unobserved sufficient state [[Alpha].sub.t], which is itself assumed to be Markovian. The task is to use simulation to carry out on-line filtering - that is, to learn about the state given contemporaneously available information. We do this by estimating the difficult-to-compute density (or probability distribution function) f([[Alpha].sub.t] [where] [y.sub.1], . . ., [y.sub.t]) = f ([[Alpha].sub.t] [where] [Y.sub.t]), t = 1, . . ., n. We assume parametric forms for both the "measurement" density f([y.sub.t] [where] [[Alpha].sub.t]) and the "transition" density of the state f([[Alpha].sub.t+1] [where] [[Alpha].sub.t]). The state evolution is initialized by some density f([[Alpha].sub.0]).
Filtering can be thought of as the repeated application of a two-stage procedure. First, the current density must be propagated into the future via the transition density f([[Alpha].sub.t+1] [where] [[Alpha].sub.t]) to produce the prediction density
[Mathematical Expression Omitted]. (1)
Second, one moves to the filtering density via Bayes theorem,
[Mathematical Expression Omitted],
[Mathematical Expression Omitted]. (2)
This implies that the data can be processed in a single sweep, updating our knowledge about the states as we receive more information. This is straightforward if [[Alpha].sub.t] [where] [[Alpha].sub.t-1] has a finite set of known discrete points of support, as the previous calculations can be computed exactly. When the support is continuous and the integrals cannot be analytically solved, then numerical methods must be used.
Numerous attempts have been made to provide algorithms that approximate the filtering densities. Important recent work includes that of Gerlach, Carter, and Kohn (1996), Kitagawa (1987), West (1992), and those papers reviewed by West and Harrison (1997, chaps. 13 and 15).
In this article we use simulation to perform filtering following an extensive recent literature. Our approach is to extend the particle filter that has recently been suggested independently by various authors. In particular, it was used by Gordon, Salmond, and Smith (1993) on non-Gaussian state-space models. The same algorithm, with extensions to the smoothing problem, has been independently proposed by Kitagawa (1996) (and generalized in Hurzeler and Kunsch 1995) for use in time series problems. It reappeared and was then discarded by Berzuini, Best, Gilks, and Larizza (1997) in the context of a real-time application of the sequential analysis of medical patients. It was again proposed by Isard and Blake (1996) in the context of robustly tracking motion in visual clutter, under the term the "condensation" algorithm. Some statistical refinements of this general class of algorithm, generically called particle filters, have been given by Carpenter, Clifford, and Fearnhead (1998), Doucet (1998), and Liu and Chen (1998) (which were written independently of this article). The idea of calling this class of algorithm "particle filters" is from Carpenter et al. (1998), although Kitagawa (1996) used the term "particles." Similar ideas (but using stronger assumptions) are used on the blind deconvolution problem of Liu and Chen (1995) and in the sequential importance sampling algorithms of Hendry and Richard (1991) and Kong, Liu, and Wong (1994).
Here we discuss the particle filtering literature and extend it in a number of directions so that it can be used in a much broader context. The article is organized as follows. In Section 2 we analyze the statistical basis of particle filters and focus on its weaknesses. In Section 3 we introduce our main contribution, an auxiliary particle filter method. We give some numerical examples in Section 4 and state some conclusions in Section 5.
2. PARTICLE FILTERS