Discovering the Hidden Structure of Complex Dynamic Systems
  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.
