Unsupervised Learning of Sampling Distributions for Particle Filters

Fernando Gama, Nicolas Zilberstein, Martin Sevilla, Richard G. Baraniuk, Santiago Segarra

TL;DR

This paper introduces a framework to learn the sampling distributions for particle filters using deep neural networks instead of manually designing them. By training in an unsupervised manner—maximizing the likelihood of observed measurements without needing ground-truth state trajectories—the authors demonstrate that learned distributions significantly outperform traditional, manually designed baselines across various nonlinear and non-Gaussian systems.

What Problem Does This Paper Address?

Estimating the hidden states of a nonlinear dynamical system (like tracking a spacecraft or modeling an epidemic) is a fundamental challenge in signal processing. Particle Filters (PFs) are a go-to tool for this, working by simulating multiple "particles" (plausible state trajectories) and weighting them based on how well they match observed data.

The "Achilles' heel" of PFs is the sampling distribution (or importance function). If this distribution is poorly designed, you encounter weight degeneracy: after a few steps, only one particle has a significant weight, making the estimator inaccurate and computationally wasteful. Traditionally, engineers design these distributions by hand (e.g., the "minimum-degeneracy" distribution), but these are often mathematically intractable or too simplistic for complex real-world systems. Furthermore, existing machine learning approaches to this problem usually require "supervised" data—access to the true hidden states—which are almost never available in practice.

Methods

The authors propose learning the sampling distribution $\pi$ directly from sequences of measurements $\{y_t\}$. They introduce four neural network architectures to parameterize this distribution:

  1. Fully-Connected (MLP): A parametric approach that learns to output the mean and covariance of a Gaussian distribution. It uses "algorithm unrolling," treating each time step as a layer in a deep network.
  2. Recurrent Neural Networks (RNN/LSTM): Similar to the MLP but uses a hidden state to capture long-term temporal dependencies in the trajectory, which a standard Markovian design might miss.
  3. Graph Neural Networks (GNN): Designed for systems with spatial or relational structure (e.g., power grids or sensor networks). GNNs allow the model to scale to high-dimensional states by exploiting the underlying graph topology.
  4. Non-parametric (Arbitrary Transform): Instead of assuming a Gaussian shape, this model learns a nonlinear mapping that transforms a simple uniform random variable into a complex state sample. This is essentially a lightweight version of a normalizing flow.

The "Secret Sauce": All models are trained unsupervised. They use the reparameterization trick to backpropagate through the sampling process and maximize the likelihood that the generated states could have produced the actual observed measurements.

Datasets

The paper evaluates the methods using four simulated dynamical system scenarios:

  • Linear Gaussian: A baseline to compare against the theoretically optimal Kalman Filter.
  • Nonlinear Gaussian: Where the state transition involves an absolute value function.
  • Linear Non-Gaussian: Using exponential and uniform noise distributions instead of Gaussian noise.
  • SIR Epidemic Model: A real-world inspired nonlinear, non-Gaussian discrete-time model representing Susceptible, Infected, and Recovered populations.

Key Insights and Ideas

  • Learning > Designing: Manually designed "optimal" distributions (like the minimum-degeneracy one) are only optimal under very specific, often unrealistic assumptions. Neural networks can find "better-than-optimal" distributions by adapting to the specific nuances of the data.
  • Structural Priors Matter: While generic MLPs work well, incorporating structural knowledge—like time (RNNs) or connectivity (GNNs)—acts as a powerful regularizer. For example, GNNs showed better stability in the nonlinear Gaussian case because they respect the system's internal relationships.
  • Unsupervised is Viable: You don't need to know the "true" state to train a state estimator. If you have a model of how states produce measurements, you can use the measurements themselves as a training signal.

Key Results

  • Superior Accuracy: In the Linear Gaussian case, the learned sampling distributions achieved a Normalized Mean Squared Error (MSE) nearly an order of magnitude lower than the standard designed minimum-degeneracy distribution.
  • Robustness to Noise: In non-Gaussian scenarios (exponential noise), the RNN-based particle filter remained stable and accurate, while the traditional baseline's performance degraded significantly.
  • SIR Model Success: In the epidemic simulation, the MLP-based "FCNN" method achieved the lowest error in estimating infected populations, significantly outperforming the baseline in capturing the "peak" of the infection curve.

Limitations and Future Work

  • Model Dependency: The unsupervised training still requires a known transition and measurement model. If the physical model itself is wrong, the learned distribution will likely inherit those errors.
  • Invertibility in Non-parametric Models: The "Arbitrary Transform" method requires the neural network to be invertible to calculate importance weights. Ensuring this invertibility while maintaining high model capacity remains a design challenge.
  • Future Directions: The authors suggest exploring more complex "normalizing flows" and adding regularization techniques like dropout to improve generalization in even higher-dimensional systems.

Summary updated

Abstract

Accurate estimation of the states of a nonlinear dynamical system is crucial for their design, synthesis, and analysis. Particle filters are estimators constructed by simulating trajectories from a sampling distribution and averaging them based on their importance weight. For particle filters to be computationally tractable, it must be feasible to simulate the trajectories by drawing from the sampling distribution. Simultaneously, these trajectories need to reflect the reality of the nonlinear dynamical system so that the resulting estimators are accurate. Thus, the crux of particle filters lies in designing sampling distributions that are both easy to sample from and lead to accurate estimators. In this work, we propose to learn the sampling distributions. We put forward four methods for learning sampling distributions from observed measurements. Three of the methods are parametric methods in which we learn the mean and covariance matrix of a multivariate Gaussian distribution; each method exploits a different aspect of the data (generic, time structure, graph structure). The fourth method is a nonparametric alternative in which we directly learn a transform of a uniform random variable. All four methods are trained in an unsupervised manner by maximizing the likelihood that the states may have produced the observed measurements. Our computational experiments demonstrate that learned sampling distributions exhibit better performance than designed, minimum-degeneracy sampling distributions.
BibTeX
@article{gama2023unsupervised,
  author = {Fernando Gama and Nicolas Zilberstein and Martin Sevilla and Richard G. Baraniuk and Santiago Segarra},
  title = {{Unsupervised Learning of Sampling Distributions for Particle Filters}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  url = {https://openreview.net/forum?id=B79TnjPNTn},
}

Loading related content...

Figure