Factored Filtering of Continuous-Time Systems

E. Busra Celikkaya, Christian R. Shelton, William Lam

TL;DR

This paper introduces "factored uniformization," a novel algorithm for efficiently approximating the state distribution of continuous-time Markov systems. It tackles the challenge of intractable state spaces by maintaining a factored representation of the belief state, offering a more scalable and accurate solution than existing methods for complex systems.

What Problem Does This Paper Address?

Many real-world systems, from queueing networks to distributed computer systems and even biological processes, can be modeled as continuous-time Markovian systems. These systems evolve over time, transitioning between discrete states. A key challenge in analyzing these systems is "filtering" or "tracking" – estimating the probability distribution over the system's current state given past observations.

The problem arises when the number of possible states becomes astronomically large, often due to the combinatorial explosion of system properties. Storing or calculating the exact probability distribution over all states becomes computationally infeasible. Traditional methods struggle with this scalability issue, especially for systems with many interacting components. This paper aims to provide a practical solution for filtering in such large, continuous-time systems by leveraging factored representations of the belief state.

Methods

The core of the paper lies in developing an approximate method for computing the matrix exponential, $e^{Qt}$, which is central to propagating the state distribution over time in continuous-time Markov systems. The authors propose two main approaches for computing this:

  • ODE Integration: This involves rewriting the matrix exponential calculation as an ordinary differential equation and solving it using numerical integration methods like Runge-Kutta-Fehlberg (RKF). The fundamental operation here is multiplying the current state distribution by the rate matrix $Q$.
  • Uniformization: This technique transforms the continuous-time system into an equivalent discrete-time one. It involves sampling intervals between state changes from an exponential distribution and then using a modified stochastic matrix $M$. The matrix exponential $e^{Qt}$ can then be expressed as an infinite series involving powers of $M$.

The novelty of this paper is in developing factored approximations for these methods. Instead of representing the full state distribution as a potentially enormous vector, they maintain a factored representation, where the distribution is expressed as a product of marginal distributions over individual variables (e.g., $p(x) = \prod_i p_i(x_i)$).

Specifically, they introduce:

  • Factored RKF: Projecting the state distribution back to a factored form at each step of the ODE integration.
  • Factored Uniformization: Projecting the intermediate distributions in the uniformization series back to a factored form. This is the primary focus, and they provide theoretical bounds on the KL-divergence error introduced by this projection.

The paper also leverages Continuous Time Bayesian Networks (CTBNs) to represent the rate matrix $Q$ in a factored manner, where each variable's dynamics depend on a subset of other variables (its parents).

Datasets

The paper does not introduce new datasets. Instead, it uses:

  • Synthetic networks: Specifically, ring and toroid dynamic Ising networks with 20 binary variables, adapted from El-Hay et al. (2010). These are used to evaluate the performance of factored uniformization against other methods.
  • Real-world network: A network constructed from the British Household Panel Survey (BHPS) data set, modeling household organization, employment, income, wealth, and health. This network was previously used in Fan et al. (2010) and Nodelman et al. (2005).

These networks are used for evaluating the accuracy and computational efficiency of their proposed methods.

Key Insights and Ideas

  • Factored Representation is Key for Scalability: The fundamental insight is that for systems with many weakly interacting components, approximating the belief state as a product of marginals is more effective than trying to maintain a sparse representation of the full distribution.
  • Uniformization Offers Tractable Bounds: While both ODE integration and uniformization can be factored, uniformization allows for theoretical bounds on the KL-divergence error introduced by the factoring and projection steps. This is crucial for understanding the approximation's quality.
  • Contraction Rate is Independent of Number of Variables (for large Taylor expansions): A significant theoretical result is that for a sufficiently large number of terms in the Taylor expansion of the uniformization series, the contraction rate of the KL-divergence error becomes independent of the number of variables ($n$). This is a critical finding for scalability.
  • Experimental Validation Outperforms Existing Methods: The paper's experimental results demonstrate that factored uniformization generally achieves better time-accuracy trade-offs compared to other approximations like factored RKF, sparse uniformization, and mean-field methods, especially for complex systems.

Key Results

  • Theoretical Bounds: The paper provides theoretical bounds on the KL-divergence error for a single step of factored uniformization and for the entire Taylor expansion approximation. These bounds show that the error can be controlled.
  • Experimental Performance:
    • Factored uniformization (UF) generally outperforms factored RKF (RKFF), sparse uniformization (Us), and mean-field (MF) methods in terms of accuracy for a given runtime.
  • For the BHPS network, UF showed superior performance.
  • For synthetic networks (ring and toroid), UF was generally best, though RKFF sometimes performed better when the query node was close to the evidence.
  • Sparse uniformization (Us) can be competitive for longer running times but can suffer from infinite KL-divergence if the evidence is inconsistent with the retained states.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the contraction rate for a single step of factored uniformization is inversely proportional to $n$ (the number of variables), though this is mitigated for larger Taylor expansions.
  • The theoretical bounds are based on KL-divergence, and while informative, the practical implications of these bounds can be complex.
  • The paper notes that interval evidence (a variable staying in a state for a duration) makes analysis difficult due to normalization, though they conjecture it won't increase error in expectation.
  • Future Work:
    • The authors suggest that interval evidence could be handled more rigorously.
  • They also mention that while their methods are applicable to other compact representations of rate matrices (like Petri nets or edge-valued decision diagrams), they focused on CTBNs. Extending to these other representations could be a future direction.
  • Further exploration of the trade-offs between the number of Taylor expansion terms ($l$) and the uniformization parameter ($\alpha$) for optimal performance.

Summary updated

Abstract

We consider filtering for a continuous-time, or asynchronous, stochastic system where the full distribution over states is too large to be stored or calculated. We assume that the rate matrix of the system can be compactly represented and that the belief distribution is to be approximated as a product of marginals. The essential computation is the matrix exponential. We look at two different methods for its computation: ODE integration and uniformization of the Taylor expansion. For both we consider approximations in which only a factored belief state is maintained. For factored uniformization we demonstrate that the KL-divergence of the filtering is bounded. Our experimental results confirm our factored uniformization performs better than previously suggested uniformization methods and the mean field algorithm.
BibTeX
@inproceedings{celikkaya2011factored,
  author = {E. Busra Celikkaya and Christian R. Shelton and William Lam},
  title = {{Factored Filtering of Continuous-Time Systems}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=ano1HbZSmU},
}
Figure