Theory of segmented particle filters. (English) Zbl 1338.65023

Chan, Hock Peng; Heng, Chiang-Wee; Jasra, Ajay

Adv. Appl. Probab. 48, No. 1, 69-87 (2016).

Summary: We study the asymptotic behavior of a new particle filter approach for the estimation of hidden Markov models. In particular, we develop an algorithm where the latent-state sequence is segmented into multiple shorter portions, with an estimation technique based upon a separate particle filter in each portion. The partitioning facilitates the use of parallel processing, which reduces the wall-clock computational time. Based upon this approach, we introduce new estimators of the latent states and likelihood which have similar or better variance properties compared to estimators derived from standard particle filters. We show that the likelihood function estimator is unbiased, and show asymptotic normality of the underlying estimators.

MSC:

65C60	Computational problems in statistics (MSC2010)
62M05	Markov processes: estimation; hidden Markov models
62M20	Inference from stochastic processes and prediction
65C05	Monte Carlo methods
65Y05	Parallel numerical computation

Keywords:

parallel processing; sequential Monte Carlo; standard error estimation; numerical example; estimation of hidden Markov models; algorithm; particle filter

References:

[1]	Anderson, T. W. (1984). An Introduction to Multivariate Statistical Analysis . 2nd edn. John Wiley, New York. · Zbl 0651.62041
[2]	Andrieu, C., Doucet, A. and Holenstein, R. (2010). Particle Markov chain Monte Carlo methods. J. R. Statist. Soc. B 72 , 269-342. · Zbl 1184.65001
[3]	Billingsley, P. (1986). Probability and Measure , 2nd edn. John Wiley, New York. · Zbl 0649.60001
[4]	Briers, M., Doucet, A. and Singh, S. S. (2005). Sequential auxiliary particle belief propagation. In Proc. 8th Internat. Conf. Information Fusion, IEEE, New York.
[5]	Cappé, O., Moulines, É. and Ryden, T. (2005). Inference in Hidden Markov Models . Springer, New York. · Zbl 1080.62065
[6]	Chan, H. P. and Lai, T. L. (2013). A general theory of particle filters in hidden Markov models and some applications. Ann. Statist. 41 , 2877-2904. · Zbl 1293.60071
[7]	Chan, H. P. and Lai, T. L. (2014). A new approach to Markov chain Monte Carlo with applications to adaptive particle filters. Unpublished manuscript.
[8]	Chopin, N. (2004). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Ann. Statist. 32 , 2385-2411. · Zbl 1079.65006
[9]	Chopin, N., Jacob, P. E. Papaspiliopoulos, O. (2013). SMC\(^2\): an efficient algorithm for sequential analysis of state space models. J. R. Statist. Soc. B 75 , 397-426.
[10]	Del Moral, P. (2004). Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications . Springer, New York. · Zbl 1130.60003
[11]	Douc, R. and Moulines, E. (2008). Limit theorems for weighted samples with applications to sequential Monte Carlo methods. Ann. Statist. 36 , 2344-2376. · Zbl 1155.62056
[12]	Doucet, A. and Johansen, A. M. (2011). A tutorial on particle filtering and smoothing: fifteen years later. In The Oxford Handbook of Nonlinear Filtering , Oxford University Press, pp. 656-704. · Zbl 05919872
[13]	Fearnhead, P., Wyncoll, D. and Tawn, J. (2010). A sequential smoothing algorithm with linear computatonal cost. Biometrika 97 , 447-464. · Zbl 1406.62093
[14]	Gordon, N. J., Salmond, D. J. and Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEEE Proc. Radar Signal Process. 140 , 107-113.
[15]	Künsch, H. R. (2005). Recursive Monte Carlo filters: algorithms and theoretical analysis. Ann. Statist. 33 , 1983-2021. · Zbl 1086.62106
[16]	Lee, A. and Whiteley, N. (2014). Forest resampling for distributed sequential Monte Carlo. Preprint. Available at http://arxiv.org/abs/1406.6010. · Zbl 1302.60139
[17]	Lee, A. \et (2010) On the utility of graphics cards to perform massively parallel simulation of advanced Monte Carlo methods. J. Comp. Graph. Statist. 19 , 769-789.
[18]	Lindsten, F. \et (2014). Divide-and-conquer with sequential Monte Carlo. Preprint. Available at http://arxiv.org/abs/1406.4993.
[19]	Persing, A. and Jasra, A. (2013). Likelihood computation for hidden Markov models via generalized two-filter smoothing. Statist. Prob. Lett. 83 , 1433-1442. · Zbl 1417.62234
[20]	Vergé, C., Dubarry, C., Del Moral, P. and Moulines, É. (2015). On parallel implementation of sequential Monte Carlo methods: the island particle model. Statist. Comput. 25 , 243-260. · Zbl 1331.65023