Fast particle smoothing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast particle smoothing: if I had a million particles

Full text

Pdf (241 KB)

Source

ACM International Conference Proceeding Series; Vol. 148 archive
Proceedings of the 23rd international conference on Machine learning table of contents

Pittsburgh, Pennsylvania

Pages: 481 - 488

Year of Publication: 2006

ISBN:1-59593-383-2

Authors

Mike Klaas	University of British Columbia, Canada
Mark Briers	Cambridge University, UK
Nando de Freitas	University of British Columbia, Canada
Arnaud Doucet	University of British Columbia, Canada
Simon Maskell	Advanced Signal and Information Processing Group, QinetiQ, UK
Dustin Lang	University of Toronto, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 71, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1143844.1143905 What is a DOI?

ABSTRACT

We propose efficient particle smoothing methods for generalized state-spaces models. Particle smoothing is an expensive O(N²) algorithm, where N is the number of particles. We overcome this problem by integrating dual tree recursions and fast multipole techniques with forward-backward smoothers, a new generalized two-filter smoother and a maximum a posteriori (MAP) smoother. Our experiments show that these improvements can substantially increase the practicality of particle smoothing.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bresler, Y. (1986). Two-filter formula for discrete-time non-linear Bayesian smoothing. IJC, 43, 629--641.
	2	Briers, M., Doucet, A., & Maskell, S. R. (2004). Smoothing algorithms for state-space models (Technical Report CUED/F-INFENG/TR.498). Cambridge University Engineering Department.
	3	Cemgil, A., & Kappen, H. (2003). Monte Carlo methods for tempo tracking and rhythm quantization. JAIR, 18, 45--81.
	4	Doucet, A., de Freitas, N., & Gordon, N. J. (Eds.). (2001). Sequential Monte Carlo methods in practice. Springer-Verlag.
	5	Felzenswalb, P. F., Huttenlocher, D. P., & Kleinberg, J. M. (2003). Fast Algorithms for Large-State-Space HMMs with Application to Web Usage Analysis. NIPS 16.
	6	Fraser, D. C., & Potter, J. E. (1969). The optimum linear smoother as a combination of two optimum linear filters. IEEE Transactions on Automatic Control, 987--390.
	7	Godsill, S. J., Doucet, A., & West, M. (2001). Maximum a posteriori sequence estimation using Monte Carlo particle filters. Ann. Inst. Stat. Math., 53, 82--96.
	8	Gray, A., & Moore, A. (2000). 'N-Body' Problems in Statistical Learning. NIPS 4 (pp. 521--527).
	9	Gray, A., & Moore, A. (2003). Rapid evaluation of multiple density models. Artificial Intelligence and Statistics.
	10	L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
	11	Greengard, L., & Sun, X. (1998). A new version of the Fast gauss transform. Doc. Math., ICM, 575--584.
	12	Michael Isard , Andrew Blake, A Smoothing Filter for CONDENSATION, Proceedings of the 5th European Conference on Computer Vision-Volume I, p.767-781, June 02-06, 1998
	13	Kim, S., Shephard, N., & Chib, S. (1998). Stochastic volatility: Likelihood inference and comparison with ARCH models. Review of Economic Studies, 65, 361--93.
	14	Kitagawa, G. (1996). Monte Carlo filter and smoother for non-Gaussian nonlinear state space models. JCGS, 5, 1--25.
	15	Klaas, M., Lang, D., & de Freitas, N. (2005). Fast maximum a posteriori inference in Monte Carlo state spaces. Artificial Intelligence and Statistics.
	16	Lang, D., & de Freitas, N. (2004). Beat tracking the graphical model way. NIPS. Cambridge, MA: MIT Press.
	17	Mayne, D. Q. (1966). A solution of the smoothing problem for linear dynamic systems. Automatica, 4, 73--92.
	18	Moore, A. (2000). The Anchors Hierarchy: Using the triangle inequality to survive high dimensional data (Technical Report CMU-RI-TR-00-05). Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
	19	Okuma, K., Taleghani, A., de Freitas, N., Little, J., & Lowe, D. (2004). A boosted particle filter: Multitarget detection and tracking. ECCV. Prague.
	20	Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	21	Jaco Vermaak , Arnaud Doucet , Patrick Pérez, Maintaining Multi-Modality through Mixture Tracking, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1110, October 13-16, 2003
	22	Changjiang Yang , Ramani Duraiswami , Nail A. Gumerov , Larry Davis, Improved Fast Gauss Transform and Efficient Kernel Density Estimation, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.464, October 13-16, 2003