Efficient general hidden Markov model inference with conditional particle filters and bridge backward sampling

Music City Center 

The backward/ancestor sampling conditional particle filter (BS-CPF) (Whiteley, J. Roy. Stat. Soc. B 2010; Lindsten, Jordan and Schön, J. Mach. Learn. Res., 2014) are Markov transitions targeting the smoothing distribution of a general state space hidden Markov model. They are known to scale extremely well for long data records, with provable O(log T) mixing times where T is the data record length, leading to overall complexity of O(T log T) [1].

The standard version of the BS-CPF, however, are not well-suited for hidden Markov models having with 'weakly informative' observations and stiff dynamics. Such a scenario occurs when we have access to a good Gaussian approximation for the smoothing distribution, or when the model is a time-discretisation of a continuous-time (path integral type) model. The inefficiency occurs for two reasons: commonly used multinomial resampling is unsuitable for weakly informative observations and introduces excess variance; and a slowly mixing dynamic model renders the backward sampling step ineffective. We discuss a modified method [2] that resolves the former issue by replacing multinomial resampling by a conditional version of recently suggested variant of systematic resampling. To avoid the degeneracy issue of backward sampling, we introduce a generalisation that involves backward sampling with an auxiliary `bridging' step.

The presentation is based on the following papers:

[1] J. Karjalainen, A. Lee, S. S. Singh and M. Vihola. Mixing time of the conditional backward sampling particle filter.
arXiv:2312.17572

[2] S. Karppinen, S. S. Singh and M. Vihola. Conditional particle filters with bridge backward sampling. Journal of Computational and Graphical Statistics, 33(2):364–378, 2024. doi:10.1080/10618600.2023.2231514

conditional particle filter, Gaussian approximation, hidden Markov model, general state-space model, Markov chain Monte Carlo, mixing time