My home page
My group
Professional activities

Daphne Koller Publications

Tractable Inference for Complex Stochastic Processes (1998)

by X. Boyen and D. Koller

Abstract: The monitoring and control of any dynamic system depends crucially on the ability to reason about its current status and its future trajectory. In the case of a stochastic system, these tasks typically involve the use of a belief state-a probability distribution over the state of the process at a given point in time. Unfortunately, the state spaces of complex processes are very large, making an explicit representation of a belief state intractable. Even in dynamic Bayesian networks (DBNs), where the process itself can be represented compactly, the representation of the belief state is intractable. We investigate the idea of maintaining a compact approximation to the true belief state, and analyze the conditions under which the errors due to the approximations taken over the lifetime of the process do not accumulate to make our answers completely irrelevant. We show that the error in a belief state contracts exponentially as the process evolves. Thus, even with multiple approximations, the error in our process remains bounded indefinitely. We show how the additional structure of a DBN can be used to design our approximation scheme, improving its performance significantly. We demonstrate the applicability of our ideas in the context of a monitoring task, showing that orders of magnitude faster inference can be achieved with only a small degradation in accuracy.

Download Information

X. Boyen and D. Koller (1998). "Tractable Inference for Complex Stochastic Processes." Proc. Fourteenth Annual Conference on Uncertainty in AI (UAI) (pp. 33-42). pdf full.pdf

Bibtex citation

  author =       "X. Boyen and D. Koller",
  booktitle =    "Proc. Fourteenth Annual Conference on Uncertainty in
                 AI (UAI)",
  title =        "Tractable Inference for Complex Stochastic Processes",
  pages =        "33--42",
  year =         "1998",

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal