×

Stability properties of some particle filters. (English) Zbl 1296.60098

The author deals with filtering problems for hidden Markov models. He considers a hidden Markov model which is a bivariate, discrete-time Markov chain \(((X_n, Y_n);n\geq0)\), where the signal process \((X_n)\) is also a Markov chain, with a (noncompact) state-space \(X\), and each observation \(Y_n\), with values in the observation space \(Y\), is conditionally independent of the rest of the bi-variate process given \(X_n\). The spaces \(X\) and \(Y\) are assumed to be Polish spaces endowed with their respective Borel \(\sigma\)-algebras. For observations \((y_0,y_1,\dots)\), a recursive one-step-ahead prediction filter is defined as the sequence \(((\pi_n);n\geq0)\) of conditional distributions of \(X_n\) given \((Y_0,Y_1,\dots,Y_{n-1})=(y_0,y_1,\dots,y_{n-1})\) and \(((Z_n);n\geq0)\) – the joint density of \((Y_0,Y_1,\dots,Y_{n-1})\) evaluated at \((y_0,y_1,\dots,y_{n-1})\). Hidden Markov models are simple and yet flexible models which have found countless applications. However, in many practical situations, \(((\pi_n);n\geq0)\) and \(((Z_n);n\geq0)\) are not available in closed form. Particle filters are a class of stochastic algorithms which yield approximations \((\pi_n^N)\) and \((Z_n^N)\) of \((\pi_n)\) and \((Z_n)\) using \(N\) samples. A large number of variations and extensions of this algorithm have been developed. However, there are still very few results which establish stability over time of particle filtering methods.
The author of the present paper proves some stability properties of a standard particle filter under assumptions which are verifiable for some hidden Markov models with noncompact state spaces. It is known that, under some mild conditions, the error associated with particle approximation of filtering distributions satisfies a central limit theorem. The first stability property obtained by the author is a time-uniform bound on the corresponding asymptotic variance. The second stability property obtained is a linear-in-time bound on the nonasymptotic, relative variance of the particle approximations of normalizing constants. These two properties are established by first proving some multiplicative stability and exponential moment results for the Feynman-Kac formulas underlying the particle filter. The adopted approach involves Lyapunov functions, multiplicative stability ideas in a weighted \(\infty\)-norm setting, which allows treatment of a noncompact state space. The main assumptions are typically satisfied under some constraints on the observation component of the hidden Markov model and/or the observation sequence driving the filter.

MSC:

60G35 Signal detection and filtering (aspects of stochastic processes)
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
93B35 Sensitivity (robustness)
93D20 Asymptotic stability in control theory
93E10 Estimation and detection in stochastic control theory
93E11 Filtering in stochastic control theory
65C40 Numerical analysis or methods applied to Markov chains
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cérou, F., Del Moral, P. and Guyader, A. (2011). A nonasymptotic theorem for unnormalized Feynman-Kac particle models. Ann. Inst. Henri Poincaré Probab. Stat. 47 629-649. · Zbl 1233.60047 · doi:10.1214/10-AIHP358
[2] 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 · doi:10.1214/009053604000000698
[3] Del Moral, P. (2004). Feynman-Kac Formulae : Genealogical and Interacting Particle Systems with Applications . Springer, New York. · Zbl 1130.60003
[4] Del Moral, P., Doucet, A. and Singh, S. S. (2010). A backward particle interpretation of Feynman-Kac formulae. M 2 AN Math. Model. Numer. Anal. 44 947-975. · Zbl 1209.65009 · doi:10.1051/m2an/2010048
[5] Del Moral, P., Doucet, A. and Jasra, A. (2012). On adaptive resampling strategies for sequential Monte Carlo methods. Bernoulli 18 252-278. · Zbl 1236.60072 · doi:10.3150/10-BEJ335
[6] Del Moral, P. and Guionnet, A. (2001). On the stability of interacting processes with applications to filtering and genetic algorithms. Ann. Inst. Henri Poincaré Probab. Stat. 37 155-194. · Zbl 0990.60005 · doi:10.1016/S0246-0203(00)01064-5
[7] Del Moral, P. and Jacod, J. (2001). Interacting particle filtering with discrete time observations: Asymptotic behaviour in the Gaussian case. In Stochastics in Finite and Infinite Dimensions : In Honor of Gopinath Kallianpur (T. Hida, R. L. Karandikar, H. Kunita, B. S. Rajput, S. Watanabe and J. Xiong, eds.). Birkhäuser, Basel. · Zbl 1056.93574
[8] Del Moral, P., Patras, F. and Rubenthaler, S. (2009). Tree based functional expansions for Feynman-Kac particle models. Ann. Appl. Probab. 19 778-825. · Zbl 1189.60171 · doi:10.1214/08-AAP565
[9] 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 · doi:10.1214/07-AOS514
[10] Douc, R., Fort, G., Moulines, E. and Priouret, P. (2009). Forgetting the initial distribution for hidden Markov models. Stochastic Process. Appl. 119 1235-1256. · Zbl 1159.93357 · doi:10.1016/j.spa.2008.05.007
[11] Douc, R., Garivier, A., Moulines, E. and Olsson, J. (2011). Sequential Monte Carlo smoothing for general state space hidden Markov models. Ann. Appl. Probab. 21 2109-2145. · Zbl 1237.60026 · doi:10.1214/10-AAP735
[12] Doucet, A., Godsill, S. and Andrieu, C. (2000). On sequential Monte Carlo sampling methods for Bayesian filtering. Stat. Comput. 10 197-208.
[13] Favetto, B. (2012). On the asymptotic variance in the central limit theorem for particle filters. ESAIM Probab. Stat. 16 151-164. · Zbl 1273.60046 · doi:10.1051/ps/2010019
[14] Gordon, N. J., Salmond, D. J. and Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. In IEE Proceedings F on Radar and Signal Processing 140 107-113. IET.
[15] Heine, K. and Crisan, D. (2008). Uniform approximations of discrete-time filters. Adv. in Appl. Probab. 40 979-1001. · Zbl 1155.93039 · doi:10.1239/aap/1231340161
[16] Kleptsyna, M. L. and Veretennikov, A. Y. (2008). On discrete time ergodic filters with wrong initial data. Probab. Theory Related Fields 141 411-444. · Zbl 1141.60337 · doi:10.1007/s00440-007-0089-7
[17] Kontoyiannis, I. and Meyn, S. P. (2005). Large deviations asymptotics and the spectral theory of multiplicatively regular Markov processes. Electron. J. Probab. 10 61-123 (electronic). · Zbl 1079.60067 · doi:10.1214/EJP.v10-231
[18] Künsch, H. R. (2005). Recursive Monte Carlo filters: Algorithms and theoretical analysis. Ann. Statist. 33 1983-2021. · Zbl 1086.62106 · doi:10.1214/009053605000000426
[19] LeGland, F. and Oudjane, N. (2003). A robustification approach to stability and to uniform particle approximation of nonlinear filters: The example of pseudo-mixing signals. Stochastic Process. Appl. 106 279-316. · Zbl 1075.93541 · doi:10.1016/S0304-4149(03)00041-3
[20] LeGland, F. and Oudjane, N. (2004). Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters. Ann. Appl. Probab. 14 144-187. · Zbl 1060.93094 · doi:10.1214/aoap/1075828050
[21] Oudjane, N. and Rubenthaler, S. (2005). Stability and uniform particle approximation of nonlinear filters in case of non ergodic signals. Stoch. Anal. Appl. 23 421-448. · Zbl 1140.93485 · doi:10.1081/SAP-200056643
[22] Pitt, M. K. and Shephard, N. (1999). Filtering via simulation: Auxiliary particle filters. J. Amer. Statist. Assoc. 94 590-599. · Zbl 1072.62639 · doi:10.2307/2670179
[23] van Handel, R. (2009). Uniform time average consistency of Monte Carlo particle filters. Stochastic Process. Appl. 119 3835-3861. · Zbl 1176.93076 · doi:10.1016/j.spa.2009.09.004
[24] Whiteley, N. (2012). Sequential Monte Carlo samplers: Error bounds and insensitivity to initial conditions. Stoch. Anal. Appl. 30 774-798. · Zbl 1253.82077 · doi:10.1080/07362994.2012.684323
[25] Whiteley, N., Kantas, N. and Jasra, A. (2012). Linear variance bounds for particle approximations of time-homogeneous Feynman-Kac formulae. Stochastic Process. Appl. 122 1840-1865. · Zbl 1262.60076 · doi:10.1016/j.spa.2012.02.002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.