Tractable Bayesian Inference of Time-Series Dependence Structure

Michael Siracusa, John W. Fisher IiiAISTATS 2009

Abstract

Understanding how multiple entities influence each other over time is a fundamental challenge across diverse fields such as biology, finance, and sports. This paper introduces a framework for performing exact Bayesian inference on the interaction structures of multiple time-series. By leveraging temporal causality and structural constraints, the authors demonstrate how to calculate exact posterior probabilities over a super-exponential number of possible graphs in polynomial time. The framework is further extended to handle non-stationary dynamics through a switching mechanism, providing a robust tool for identifying behavioral modes in complex systems.

Introduction

Structure learning in graphical models aims to uncover the underlying influence patterns between variables. However, Bayesian inference in this domain faces two significant hurdles: the need to marginalize out underlying parameters and the combinatorial explosion of possible directed graphs. For $N$ variables, there are $2^{N(N-1)}$ possible directed graphs, making exhaustive evaluation computationally infeasible. Most existing methods settle for point estimates or approximations. This work addresses these challenges by providing exact posterior uncertainty, enabling researchers to quantify the probability of specific interactions rather than just identifying a single "best" structure.

The Temporal Interaction Model (TIM)

The core of the proposed approach is the Temporal Interaction Model (TIM). The key insight is that temporal causality—where an observation at time $t$ can only be influenced by observations at time $t-1$ or earlier—naturally results in an acyclic graphical model over time. This property allows for the definition of an "interaction graph" where cycles are permitted in the summary structure without violating the acyclicity of the underlying generative process.

Temporal Interaction Model (TIM) structure showing how time-lagged dependencies form an interaction graph.

To achieve tractability, the authors employ two main strategies:

  • Conjugate Priors: By using specific priors, such as the Matrix-Normal-Inverse-Wishart for continuous data, parameters can be analytically marginalized out. This yields a closed-form expression for the evidence of a given structure.
  • Matrix Tree Theorem: By restricting the interaction graph to specific classes like directed trees or forests, the Matrix Tree Theorem can be used to calculate the sum over all possible structures (the partition function) in $O(N^3)$ time.

Switching TIM (STIM)

Real-world interactions are often non-stationary. To account for this, the authors introduce the Switching TIM (STIM), which incorporates a latent variable $z_t$ to index different interaction structures over time.

Graphical model for the Switching Temporal Interaction Model (STIM).

The STIM model uses a Gibbs sampler to switch between different TIMs, allowing the system to segment a long time series into distinct "behavioral modes." While the inference for a fixed structure remains exact, the switching sequence is inferred via MCMC.

Experimental Evaluation

The framework was evaluated across three distinct scenarios:

  • Synthetic Data: Tests on 1D random walks demonstrated that the model could accurately identify edges even with low influence strength ($ ho = 0.1$), provided sufficient samples were available.
  • Interactive Mouse-Tracking: In a controlled game where participants followed specific rules (e.g., "stay between others"), the model successfully recovered the ground-truth influence structures. It specifically showed that complex behaviors like "staying between" required more general graph classes than simple trees.
  • Basketball Tracking: Analysis of CVBASE 06 tracking data identified the ball as the primary influencer (root) with over 70% probability during offensive plays. It also revealed the role of the point guard in dictating team movement.

Discussion and Conclusion

By enforcing temporal causality, this work transforms a difficult graph inference problem into a manageable one. The ability to provide full posterior distributions rather than point estimates is particularly valuable for discovery tasks where uncertainty quantification is critical.

Future work may address current limitations, such as the requirement to pre-specify the number of states ($K$) in the STIM model—potentially through non-parametric approaches like HDP-HMM. Additionally, while $O(N^3)$ is polynomial, further optimizations may be necessary to scale the method to systems involving thousands of interacting time-series.

Summary updated

BibTeX
@article{siracusa2009tractable,
  author = {Michael Siracusa and John W. Fisher III},
  title = {{Tractable Bayesian Inference of Time-Series Dependence Structure}},
  journal = {AISTATS},
  year = {2009},
}
Figure