A Recent Development of Particle Methods

A Blog Entry on Bayesian Computation by an Applied Mathematician

$$

$$

A Recent Development of Particle Filter. Tap the image to view PDF

The following is a detailed version of the poster presented at MLSS2024, S3-41, March 8 (Fri) 18:00-19:30.

Takeaways

Compared to their discrete-time counterparts, Monte Carlo methods based on continuous-time processes exhibit superior computational efficiency and mixing rates, making them more suitable for high-dimensional applications.

1 What Is Particle Filter?

Particle filters, also known as Sequential Monte Carlo methods (SMCs), were invented in (Kitagawa, 1993) and (Gordon et al., 1993) independently as an simulation-based algorithm which performs filtering in non-Gaussian and non-linear state space models, overcoming the weeknesses of then-standard Kalman-based filtering methods.¹

In particle-based approaches, a filtering distribution is approximated by a cloud of weighted samples, hence giving rise to the term ‘particle filter’. The samples are propagated to approximate the next distribution, leading to efficient sequential estimation in dynamic settings.

Recent developments have highlithgted the capability of particle filters as general-purpose samplers, extending their applicability beyond the traditional realm of temporal graphical models to a broader range of statistical inference problems. This versatility has earned them the alternative name ‘SMC’, a term reminiscent of ‘MCMC’. This poster trys to be another contribution in this direction.

2 MCMC vs. SMC

PDMPs (Piecewise Deterministic Markov Processes) (Davis, 1984), a type of continuous-time Markov processes with jumps as their only random components, play a complementary role to diffusion processes in stochastic modelling.²

In (Peters and de With, 2012), a PDMP was identified through the continuous limit of the MCMC, Metropolis-Hastings algorithm. The PDMP was further investigated and termed Bouncy Particle Sampler (BPS) in (Bouchard-Côté et al., 2018).

library(RZigZag)
library(ggplot2)
V <- matrix(c(3,1,1,3),nrow=2)
mu <- c(2,2)
x0 <- c(0,0)
result <- BPSGaussian(V, mu, n_iter = 100, x0 = x0)
ggplot() +
   geom_path(aes(x=result$Positions[1,], y=result$Positions[2,]), color="#2F579C") +
   geom_point(aes(x=result$Positions[1,], y=result$Positions[2,]), color="#2F579C") +
   labs(x="", y="", title="Bouncy Particle Sampler") +
   theme_void() +
   theme(text=element_text(size=12), axis.title=element_text(color="#2F579C"), plot.title=element_text(color="#2F579C"))

Also, other types of continuous-time MCMC algorithms have been developed, such as the Zig-Zag sampler (Bierkens et al., 2019):

V <- matrix(c(3,1,1,3),nrow=2)
mu <- c(2,2)
result <- ZigZagGaussian(V, mu, 100)
ggplot() +
   geom_path(aes(x=result$Positions[1,], y=result$Positions[2,]), color="#2F579C") +
   geom_point(aes(x=result$Positions[1,], y=result$Positions[2,]), color="#2F579C") +
   labs(x="", y="", title="Zig-Zag Sampler") +
   theme_void() +
   theme(text=element_text(size=12), axis.title=element_text(color="#2F579C"), plot.title=element_text(color="#2F579C"))

Enpirical evidence suggests that continuous-time MCMCs are more efficient than their discrete-time counterparts.

Interestingly, continuous-time algorithms seem particularly well suited to Bayesian analysis in big-data settings as they need only access a small sub-set of data points at each iteration, and yet are still guaranteed to target the true posterior distribution. (Fearnhead et al., 2018)

3 Inquiry for Continuous-time SMC

Despite the success of continuous-time MCMC, the continuous-time limit of SMC has not been fully explored. The continuous-time limit of SMC is expected to be a jump process, which is similar to PDMP, but is more diffusion-like.

MCMC has now taken a step ahead; it is time for SMC to explore its continuous-time limit!

3.1 A Generic Particle Filter: An Algorithmic Description

Procedure of a generic step of a particle filter at time \(t\)

1. Resampling Step

   Particles with high weights are duplicated, and those with the lowest weights are discarded.

2. Movement Step

   Subsequently, a MCMC move is executed from the resampled particles.

The resampling step is the key difference from sequential importance sampling methods. Particle filters incorporate a resampling step to occasionally reset the weights of the samples, while maintaining the overall distribution they represent, in order to prevent the effective number of particles participating in the estimation from becoming too small–a situation also called weight degeneracy.

3.2 A Necessary Condition: Resampling Stability

In order to have a time-step \(\Delta\to0\) limit, resampling events must occur with (at most linearly) decreasing frequency as \(\Delta\to0\).

Only the most efficient resampling schemes satisfy this property.

Root mean squared errors of marginal likelihood estimates (Chopin et al., 2022)

4 The Continuous-time Limit Process

The continuous-time limit process, if it exists, is characterized by a Feller-Dynkin process, whose infinitesimal generator is given by:

\[ \begin{align*} \mathcal{L}f(x)&=\sum_{n=1}^N\sum_{i=1}^db_i(x^n)\frac{\partial f}{\partial x^n_i}(x)\\ &\;\;+\sum_{n=1}^N\frac{1}{2}\sum_{i,j=1}^d(\sigma\sigma^\top)_{ij}(x^n)\frac{\partial ^2f}{\partial x^n_i\partial x^n_j}(x)\\ &\;\;+\sum_{a\ne1:N}\overline{\iota}(V(x),a)\biggr(f(x^{a(1:N)})-f(x^{1:N})\biggl) \end{align*} \] \[ (f\in C_c^2(\mathbb{R}^{dN}),x\in\mathbb{R}^{dN},x^n\in\mathbb{R}^d) \]

when the latent process \((X_t)\) is an Itô process given by the generator:

\[ \begin{align*} Lf(x)&=\sum_{i=1}^db_i(x)\frac{\partial f}{\partial x_i}(x)\\ &\;\;+\frac{1}{2}\sum_{i,j=1}^d(\sigma\sigma^\top)_{ij}(x)\frac{\partial ^2f}{\partial x_i\partial x_j}(x) \end{align*} \] \[ (f\in C_c^2(\mathbb{R}^d),x\in\mathbb{R}^d) \]

For details, please consult (Chopin et al., 2022, p. 3206), Theorem 19.

5 Conclusions

Summaries

SMC with efficient resampling schemes possess a continuous-time limit \(\Delta\to0\), which turns out to be a Feller-Dynkin process, a diffusion process with jumps, when \((X_t)\) is a diffusion.

6 Forthcoming Research

Ultimate Purpose

How can we leverage the knowledge of the continuous-time limit process to design efficient Sequential Monte Carlo (SMC) samplers capable of sampling from posterior distributions of diffusions?

• What are the properties of this limit jump process, and how do they change with modifications to the underlying latent process?
• How does the timing of resampling affect overall efficiency? Can insights be gained from the perspective of continuous-time limits?
• Does the continuous-time limit process improve SMC efficiency when used for particle propagation?

References

Bierkens, J., Fearnhead, P., and Roberts, G. (2019). The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data. The Annals of Statistics, 47(3), 1288–1320.

Bouchard-Côté, A., Vollmer, S. J., and Doucet, A. (2018). The bouncy particle sampler: A nonreversible rejection-free markov chain monte carlo method. Journal of the American Statistical Association, 113(522), 855–867.

Chopin, N., Singh, S. S., Soto, T., and Vihola, M. (2022). On Resampling Schemes for Particle Filter with Weakly Informative Observations. The Annals of Statistics, 50(6), 3197–3222.

Davis, M. H. A. (1984). Piecewise-deterministic markov processes: A general class of non-diffusion stochastic models. Journal of the Royal Statistical Society. Series B (Methodological), 46(3), 353–388.

Fearnhead, P., Bierkens, J., Pollock, M., and Roberts, G. O. (2018). Piecewise deterministic markov processes for continuous-time monte carlo. Statistical Science, 33(3), 386–412.

Gordon, N. G., Salmond, D. J., and Smith, A. F. M. (1993). Novel approach to nonlinear/non-gaussian bayesian state estimation. IEE Proceedings-F, 140(2), 107–113.

Kitagawa, G. (1993). A monte carlo filtering and smoothing method for non-gaussian nonlinear state space methods. In Proceedings of the 2nd u.s.-japan joint seminar on statistical time series analysis. Honolulu, hawaii, january, pages 25–29.

Murphy, K. P. (2023). Probabilistic machine learning: Advanced topics. MIT Press.

Peters, E. A. J. F., and de With, G. (2012). Rejection-free monte carlo sampling for general potentials. Physical Review E, 85(2).

Theodoridis, S. (2020). Machine learning: A bayesian and optimization perspective. Academic Press.

Footnotes

1. Good references are (Murphy, 2023) Chapter 13, and (Theodoridis, 2020, p. 881) Section 17.4.

2. (Fearnhead et al., 2018) is a great introduction to this topic.