My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Discovering the hidden structure of complex dynamic systems (1999)

by X. Boyen, N. Friedman, and D. Koller


Abstract: Dynamic Bayesian networks provide a compact and natural representation for complex dynamic systems. However, in many cases, there is no expert available from whom a model can be elicited. Learning provides an alternative approach for constructing models of dynamic systems. In this paper, we address some of the crucial computational aspects of learning the structure of dynamic systems, particularly those where some relevant variables are partially observed or even entirely unknown. Our approach is based on the Structural Expectation Maximization (SEM) algorithm. The main computational cost of the SEM algorithm is the gathering of expected sufficient statistics. We propose a novel approximation scheme that allows these sufficient statistics to be computed efficiently. We also investigate the fundamental problem of discovering the existence of hidden variables without exhaustive and expensive search. Our approach is based on the observation that, in dynamic systems, ignoring a hidden variable typically results in a violation of the Markov property. Thus, our algorithm searches for such violations in the data, and introduces hidden variables to explain them. We provide empirical results showing that the algorithm is able to learn the dynamics of complex systems in a computationally tractable way.


Download Information

X. Boyen, N. Friedman, and D. Koller (1999). "Discovering the hidden structure of complex dynamic systems." Proceedings of the 15th Annual Conference on Uncertainty in AI (UAI) (pp. 206-215). pdf ps.gz

Bibtex citation

@inproceedings{Boyen+al:UAI99,
  author =       "X. Boyen and N. Friedman and D. Koller",
  booktitle =    "Proceedings of the 15th Annual Conference on
                 Uncertainty in AI (UAI)",
  title =        "Discovering the hidden structure of complex dynamic
                 systems",
  year =         "1999",
  pages = "206--215",
}

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