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.