Parallel Subspace Sampling for Particle Filtering in Dynamic Bayesian Networks

Eva Besada-Portas, Sergey M. Plis, Jesús Manuel de la Cruz, Terran LaneECML/PKDD 2009 · OpenReview

Abstract

Monitoring the variables of real-world dynamic systems is a difficult task due to their inherent complexity and uncertainty. Particle Filters (PF) perform that task, yielding probability distributions over unobserved variables. However, they suffer from the curse of dimensionality: the number of particles grows exponentially with the dimensionality of the hidden state space. This problem is aggravated when the initial distribution of variables is not well known, as in global localization problems. We present a new parallel PF for systems whose variable dependencies can be factored into a Dynamic Bayesian Network (DBN). The new algorithm significantly reduces the number of particles while independently exploring different subspaces of hidden variables to build particles consistent with past history and measurements. We demonstrate this approach on complex dynamical system estimation problems, showing that our method successfully localizes and tracks hidden states in cases where traditional PFs fail.

Introduction

Particle Filters are a powerful class of algorithms for estimating the hidden states of dynamic systems, such as tracking a robot's position or monitoring environmental changes. They work by maintaining a "cloud" of particles that represent a probability distribution of possible states. However, as the number of variables (dimensions) in a system increases, the volume of the state space grows exponentially. In these vast spaces, random particles are highly likely to fall into regions of near-zero probability, leading to "particle depletion." This phenomenon causes the filter to lose track of the true state because none of its particles are near the actual truth.

Methodology: Parallel Subspace Sampling

The proposed framework addresses the curse of dimensionality by using a "divide and conquer" strategy based on the structure of Dynamic Bayesian Networks (DBNs).

Factored Subspaces

If a system's variables can be partitioned into independent or loosely coupled groups, the algorithm samples these subspaces in parallel. The DBN's graph structure—specifically its parents, children, and isochronal links—is used to determine which variables must be sampled together and which can be handled independently.

A Dynamic Bayesian Network (DBN) partitioned into two parallel subspaces, P1 and P2.

Hybrid Particle Construction

The core innovation of this method is the ability to construct "hybrid" particles. A particle that has a low overall probability may still contain highly accurate information about a specific subset of variables. By identifying these "locally good" components across different particles and stitching them together, the algorithm can create a new hybrid particle that resides in a high-probability region of the joint state space.

Illustration of combining low-probability particles into a high-probability hybrid particle.

Informed Proposal Distribution

Unlike standard filters that guess the next state based solely on the previous one, this approach uses current measurements (likelihoods) to weight which subspace components are most promising. This allows the filter to "reset" or recover if it becomes lost; if all particles lose weight, the algorithm accepts new samples based on the current proposal, enabling recovery from total tracking failure.

Experimental Results

The authors evaluated the Parallel Subspace Sampling method across three distinct domains:

  • Repelling Objects Simulation: In a system of 10 mobile objects repelled by an unknown force, standard filters failed to converge even with 1,000 particles. The new method achieved high convergence rates using only 20 to 100 particles.
  • Sea Rescue Simulation: This test involved a UAV tracking multiple objects in the ocean. The proposed method significantly outperformed traditional filters as the difficulty of the initial search area increased.
  • Real-World fMRI Data: Tracking 42 hidden variables representing neural activity in the brain, the parallel filter achieved higher log-likelihood scores and lower variance than standard particle filters, indicating a much better fit to the real-world data.

Conclusion

Parallel Subspace Sampling provides a principled way to rescue Particle Filters from the curse of dimensionality. By exploiting the structural dependencies of a system to create hybrid particles, the method maintains tracking accuracy with significantly fewer particles than traditional approaches. While calculating the proposal distribution adds some computational overhead per particle, the gain in robustness and the ability to handle high-dimensional hidden states make it a vital advancement for complex dynamical system estimation.

Summary updated

Abstract

Monitoring the variables of real world dynamic systems is a difficult task due to their inherent complexity and uncertainty. Particle Filters (PF) perform that task, yielding probability distribution over the unobserved variables. However, they suffer from the curse of dimensionality problem: the number of particles grows exponentially with the dimensionality of the hidden state space. The problem is aggravated when the initial distribution of the variables is not well known, as happens in global localization problems. We present a new parallel PF for systems whose variable dependencies can be factored into a Dynamic Bayesian Network. The new algorithms significantly reduce the number of particles, while independently exploring different subspaces of hidden variables to build particles consistent with past history and measurements. We demonstrate this new PF approach on some complex dynamical system estimation problems, showing that our method successfully localizes and tracks hidden states in cases where traditional PFs fail.
BibTeX
@inproceedings{besadaportas2009parallel,
  author = {Eva Besada-Portas and Sergey M. Plis and Jesús Manuel de la Cruz and Terran Lane},
  title = {{Parallel Subspace Sampling for Particle Filtering in Dynamic Bayesian Networks}},
  booktitle = {ECML/PKDD},
  year = {2009},
  url = {https://openreview.net/forum?id=nNpHeLT0LQh},
}
Figure