TL;DR
This paper introduces "decayed MCMC" filtering, a novel algorithm that adapts Markov Chain Monte Carlo (MCMC) sampling to efficiently estimate the state of partially observable systems. By prioritizing recent observations, it achieves provably bounded convergence times, outperforming traditional MCMC and competing with particle filters, especially in scenarios with long observation sequences.
What Problem Does This Paper Address?
Estimating the current state of a system based on a sequence of noisy observations is a fundamental problem in fields like control theory and AI, often referred to as "filtering." For complex systems with many states or non-linear dynamics, exactly calculating the probability distribution of the current state (the "belief state") becomes computationally intractable. This has led to the development of approximation algorithms. While particle filtering is a popular and robust method, it can diverge in certain cases and requires memory proportional to its accuracy. This paper aims to provide a new approximation algorithm that is theoretically sound, robust against divergence, and competitive with existing methods.
Methods
The core innovation is decayed MCMC filtering. Instead of standard MCMC, which samples from the entire history of states, this method uses a modified MCMC approach. It constructs a Markov chain over state trajectories (sequences of states) and uses a proposal distribution that favors "flips" (changes) in more recent state variables. This "decay" in attention to older states is controlled by a decay function.
The paper proposes an inverse polynomial decay function as a key component. This function dictates how much weight is given to updating older states versus newer ones. The theoretical analysis leverages a generalized MCMC coupling lemma to prove that, under certain conditions (ergodic underlying Markov process), the convergence time of this decayed MCMC algorithm remains bounded, even as the length of the observation sequence grows indefinitely. This boundedness is crucial for guaranteeing non-divergence.
Datasets
Not discussed in the paper. The experiments use synthetic DBNs (including HMMs and a WATER network) and a switching Kalman filter example.
Key Insights and Ideas
- Prioritizing Recent History: The intuition is that for filtering, recent states are far more relevant to the current belief state than very old ones. Decayed MCMC formalizes this by biasing sampling towards recent states.
- Provable Bounded Convergence: A major theoretical contribution is proving that with an inverse polynomial decay, the algorithm's convergence time is independent of the total observation history length. This is a significant advantage over standard MCMC, which can become prohibitively slow.
- Robustness Against Divergence: The bounded convergence directly implies that the algorithm is non-divergent, a desirable property that particle filters don't always guarantee.
- MCMC for Filtering: The paper demonstrates how MCMC, typically used for static inference, can be adapted for sequential state estimation (filtering) by operating on state trajectories.
Key Results
- Theoretical Guarantee: The paper proves that decayed MCMC with inverse polynomial decay has a convergence time that is bounded and independent of the observation sequence length (T).
- Empirical Performance: Experiments show that decayed MCMC is "at least competitive" with particle filtering and other approximation algorithms.
- Specific Examples:
- Figure 2 shows that mixing time (for a quadratic decay) is bounded as history length increases, though it depends on the DBN's mixing parameter.
- Figures 3 and 4 demonstrate that decayed MCMC (especially quadratic decay) is robust across different HMM mixing parameters, often outperforming fixed-window or exponential decay methods.
- Figure 5 shows decayed MCMC performing comparably to particle filtering on a larger WATER DBN.
- Figure 6 shows decayed MCMC performing comparably to particle filtering on a switching Kalman filter example.
Limitations and Future Work
- Continuous State Spaces: The theoretical proofs are primarily for discrete DBNs. Generalizing these proofs to continuous state spaces is suggested as future work.
- Parallel Chains: The authors suggest exploring the use of parallel chains to potentially improve efficiency.
- Adaptive Sampling: An interesting avenue for future research is adaptively choosing the number of samples based on recent evidence, a capability not easily available with sequential methods.
- Practical Implementation: While the paper shows competitive performance, further practical tuning and comparison on larger, real-world problems would be valuable.
Summary updated