My home page
My group
Professional activities

Daphne Koller Publications

Exploiting the Architecture of Dynamic Systems (1999)

by X. Boyen and D. Koller

Abstract: Consider the problem of monitoring the state of a complex dynamic system, and predicting its future evolution. Exact algorithms for this task typically maintain a belief state - the distribution over the states at some point in time. Unfortunately, these algorithms fail when applied to complex processes such as those represented as dynamic Bayesian networks (DBNs), as the representation of the belief state grows exponentially with the size of the process. Boyen and Koller recently proposed an efficient approximate tracking algorithm that maintains an approximate belief state that has a compact representation as a set of independent factors. Their analysis relies on a bound on the error introduced by approximating a belief state of this process by a factored one. They argue informally that their algorithm is justified in cases where the interaction between variables in the processes is ``weak''. In this paper, we give formal information-theoretic definitions for notions such as weak interaction and sparse interaction of processes. We use these notions to analyze the conditions under which the error induced by this type of approximation is small. We demonstrate several cases where our results formally support intuitions about strength of interaction.

Download Information

X. Boyen and D. Koller (1999). "Exploiting the Architecture of Dynamic Systems." Proceedings of the 16th National Conference on Artificial Intelligence (AAAI) (pp. 313-320). pdf ps.gz

Bibtex citation

  author =       "X. Boyen and D. Koller",
  booktitle =    "Proceedings of the 16th National Conference on
                 Artificial Intelligence (AAAI)",
  title =        "Exploiting the Architecture of Dynamic Systems",
  pages =        "313--320",
  year =         "1999",

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