Adaptive sequential Monte Carlo by means of mixture of experts

Julien Cornebise, Éric Moulines, Jimmy Olsson

Abstract: Appropriately designing the proposal kernel of particle filters is an issue of significant importance, since a bad choice may lead to deterioration of the particle sample and, consequently, waste of computational power. In this paper we introduce a novel algorithm adaptively approximating the so-called optimal proposal kernel by a mixture of integrated curved exponential distributions with logistic weights. This family of distributions, referred to as mixtures of experts, is broad enough to be used in the presence of multi-modality or strongly skewed distributions. The mixtures are fitted, via online-EM methods, to the optimal kernel through minimisation of the Kullback-Leibler divergence between the auxiliary target and instrumental distributions of the particle filter. At each iteration of the particle filter, the algorithm is required to solve only a single optimisation problem for the whole particle sample, yielding an algorithm with only linear complexity. In addition, we illustrate in a simulation study how the method can be successfully applied to optimal filtering in nonlinear state-space models.

Introduction

Particle filters, or Sequential Monte Carlo (SMC) methods, are critical for tracking hidden states in dynamic systems. However, their performance is highly sensitive to the choice of the proposal kernel—the mechanism that predicts the next state of the particles. A poor proposal leads to "weight degeneracy," where most particles receive near-zero weights, wasting computational effort on non-contributing samples. While an "optimal" proposal kernel exists theoretically, it is often intractable. This paper introduces a novel adaptive algorithm that approximates this optimal kernel using a flexible "mixture of experts" (MoE) framework.

Methodology: Adaptive Mixture of Experts

The authors propose a framework that is both flexible and computationally lean, characterized by three main components:

  1. Mixture of Experts (MoE): The proposal is modeled as a weighted sum of "experts," each being an integrated curved exponential distribution (such as a Gaussian or Student’s t-distribution). This allows the filter to handle multi-modality and skewness.
  2. Logistic Gating: Logistic weights are used to determine which expert specializes in which part of the state space, enabling the capture of complex distribution shapes.
  3. Online KL Minimization: The mixture is fitted by minimizing the Kullback-Leibler (KL) divergence between the target and the proposal. Crucially, this is achieved via stochastic approximation (an online EM-like approach), allowing parameters to adapt as the filter runs without requiring a full optimization at every step.
Table of notation and corresponding equations for key quantities in the SMC framework.

By solving a single optimization problem for the entire particle cloud at each iteration, the algorithm maintains a linear computational complexity of $O(N)$, where $N$ is the number of particles.

Experimental Evaluation

The method was evaluated using three simulated state-space models designed to test specific challenges:

  • Multivariate Linear Gaussian Model: A baseline where the true optimal proposal is known.
  • Bessel Process (Range-only tracking): A highly nonlinear model with a ring-shaped likelihood, testing the filter's ability to handle non-standard geometries.
  • Multivariate Tobit Model: A model with censored observations, creating sharp truncations that test the robustness of the proposal.
Additional notation for KL divergence and adjustment multipliers.

Key Results and Insights

  • Weight Stabilization: In the Bessel process, the adaptive MoE proposal successfully concentrated particles on the target support, drastically increasing the Effective Sample Size (ESS) compared to standard bootstrap filters, which suffered from 80% zero-weight particles.
  • Rapid Convergence: The parameters of the experts (means, covariances, and weights) typically stabilized within the first dozen iterations.
  • Robustness: The use of Student’s t-experts proved significantly more robust than Gaussian experts in models with heavy tails or sharp truncations, such as the Tobit model.
  • Efficiency: The KL divergence approach effectively decouples the adaptation of the proposal kernel from the adjustment weights, simplifying the mathematical implementation.

Conclusion

The proposed adaptive SMC algorithm provides a robust and efficient solution for complex filtering problems. While it successfully automates the adaptation of the proposal kernel ($r_{\boldsymbol{\theta}}$), future work remains in automating the adaptation of the adjustment multiplier ($a^*$) and establishing formal theoretical convergence proofs for the combined SMC and stochastic approximation framework.

Summary updated

Abstract

Appropriately designing the proposal kernel of particle filters is an issue of significant importance, since a bad choice may lead to deterioration of the particle sample and, consequently, waste of computational power. In this paper we introduce a novel algorithm adaptively approximating the so-called optimal proposal kernel by a mixture of integrated curved exponential distributions with logistic weights. This family of distributions, referred to as mixtures of experts, is broad enough to be used in the presence of multi-modality or strongly skewed distributions. The mixtures are fitted, via online-EM methods, to the optimal kernel through minimisation of the Kullback-Leibler divergence between the auxiliary target and instrumental distributions of the particle filter. At each iteration of the particle filter, the algorithm is required to solve only a single optimisation problem for the whole particle sample, yielding an algorithm with only linear complexity. In addition, we illustrate in a simulation study how the method can be successfully applied to optimal filtering in nonlinear state-space models.
BibTeX
@article{cornebise2014adaptive,
  author = {Julien Cornebise and Éric Moulines and Jimmy Olsson},
  title = {{Adaptive sequential Monte Carlo by means of mixture of experts}},
  journal = {Stat. Comput.},
  year = {2014},
  doi = {10.1007/s11222-012-9372-2},
}
Figure