Improving the particle filter in high dimensions using conjugate artificial process noise

Anna Wigren, Lawrence M. Murray, Fredrik Lindsten

TL;DR

This paper tackles the "degeneracy" problem in particle filters, a common issue in high-dimensional systems that makes standard methods unreliable. They propose a novel approach by slightly modifying the system model to include artificial process noise, which then enables a more effective particle filter proposal. This method significantly improves performance on both linear-Gaussian and chaotic non-linear models, offering a practical way to handle complex, high-dimensional inference tasks.

What Problem Does This Paper Address?

Particle filters are powerful tools for estimating the state of dynamic systems, especially when models are non-linear or non-Gaussian. However, a major hurdle, particularly in high-dimensional systems (where the number of variables is large), is "particle degeneracy." This occurs when the weights assigned to the particles (which represent the probability distribution of the system's state) become highly uneven. Essentially, one or a few particles dominate, making the filter's estimate unreliable and prone to significant errors. This degeneracy is a major bottleneck for applying particle filters to real-world problems in fields like oceanography, weather prediction, and epidemiology, which often involve high-dimensional data.

Methods

The core of the paper's contribution lies in a clever workaround to enable a more efficient particle filter proposal. Instead of directly trying to improve the standard particle filter for the original, potentially intractable model, they propose to approximate the model itself. This approximation involves adding an "artificial process noise" in an extra state update. This modification, controlled by a parameter $\epsilon$, effectively "roughens" the system dynamics.

The key innovation is how this modified model allows for a better particle filter proposal. The authors leverage the idea of a "locally optimal proposal," which is known to minimize particle weight variance but is often impossible to implement for complex models. By introducing the artificial noise, they create a scenario where a combined proposal can be used: it first propagates particles using the standard method and then uses a modified, locally optimal-like step that accounts for the artificial noise and the current observation. This combined proposal, along with a corresponding weight update, is designed to combat degeneracy. The trade-off is that while this reduces variance, it introduces a controlled bias into the model.

Datasets

The paper evaluates its proposed method on two synthetic datasets generated from:

  1. A 10-dimensional linear-Gaussian state space model.
  2. A 10-dimensional non-linear Lorenz'96 model, known for exhibiting chaotic behavior.

For both models, only half of the states are observed at each time step, and the measurement noise covariance is significantly smaller than the process noise covariance, making the estimation problem challenging.

Key Insights and Ideas

  • Approximating the Model, Not Just the Filter: Instead of solely focusing on improving the particle filter algorithm itself, the paper demonstrates the power of slightly altering the underlying system model to enable better filtering. This is a significant shift in perspective for tackling degeneracy.
  • Bridging the Gap to Locally Optimal Proposals: The artificial noise acts as a bridge, allowing the benefits of a locally optimal proposal (reduced variance) to be harnessed even when the original model's transition density is intractable.
  • Bias-Variance Trade-off as a Tuning Mechanism: The parameter $\epsilon$ for the artificial noise is explicitly framed as a knob to control the bias-variance trade-off. This provides a clear way to tune the method for different applications, balancing accuracy with computational stability.
  • Covariance Choice Matters: The choice of the covariance matrix for the artificial noise (e.g., block-diagonal vs. weighted sample covariance) significantly impacts performance, with the weighted sample covariance often providing more robust results, especially for chaotic systems.

Key Results

  • Significant Improvement over Standard Particle Filter: For both the linear-Gaussian and Lorenz'96 models, the proposed method shows substantial improvements in marginal log-likelihood and mean squared error (MSE) compared to the standard particle filter, especially in scenarios where the standard filter degenerates.
  • Approaching Kalman Filter Performance: In the linear-Gaussian case, the proposed method can achieve performance very close to that of the true Kalman filter (the optimal Bayesian solution for linear-Gaussian systems) for certain ranges of $\epsilon$.
  • Reduced Degeneracy: The method effectively reduces particle degeneracy, as evidenced by higher effective sample sizes (ESS) and a lower probability of the ESS dropping below critical thresholds.
  • Bias-Variance Trade-off Demonstrated: The results clearly illustrate the expected bias-variance trade-off: increasing $\epsilon$ reduces variance (improving MSE and log-likelihood stability) but increases model bias.

Limitations and Future Work

  • Curse of Dimensionality Still a Concern: While the method improves performance in high dimensions, the authors acknowledge that for extremely high-dimensional problems (thousands of dimensions), it will likely still struggle, suggesting the need to combine this approach with other techniques.
  • Tuning Parameter $\epsilon$: The paper relies on empirical evaluation to find suitable values for $\epsilon$. Future work could focus on developing adaptive schemes or rules-of-thumb for automatically tuning $\epsilon$ online.
  • Covariance Matrix Selection: Further investigation into optimal choices for the artificial process noise covariance matrix is suggested.
  • System Identification: The authors note that their method, by improving filtering performance, also has direct implications for system identification, which is an area for future exploration.

Summary updated

Abstract

The particle filter is one of the most successful methods for state inference and identification of general non-linear and non-Gaussian models. However, standard particle filters suffer from degeneracy of the particle weights, in particular for high-dimensional problems. We propose a method for improving the performance of the particle filter for certain challenging state space models, with implications for high-dimensional inference. First we approximate the model by adding artificial process noise in an additional state update, then we design a proposal that combines the standard and the locally optimal proposal. This results in a bias-variance tradeoff, where adding more noise reduces the variance of the estimate but increases the model bias. The performance of the proposed method is empirically evaluated on a linear-Gaussian state space model and on the non-linear Lorenz’96 model. For both models we observe a significant improvement in performance over the standard particle filter.
BibTeX
@inproceedings{wigren2018improving,
  author = {Anna Wigren and Lawrence M. Murray and Fredrik Lindsten},
  title = {{Improving the particle filter in high dimensions using conjugate artificial process noise}},
  booktitle = {IFAC-PapersOnLine},
  year = {2018},
  doi = {10.1016/j.ifacol.2018.09.207},
}
Figure