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

Discovering the Hidden Structure of Complex Dynamic SystemsComputer Science Dept. Stanford University Stanford, CA 94305-9010 xb@cs.stanford.edu

Xavier Boyen

Inst. of Computer Science Hebrew University Jerusalem, 91904, Israel nir@cs.huji.ac.il

Nir Friedman

Computer Science Dept. Stanford University Stanford, CA 94305-9010 koller@cs.stanford.edu

Daphne Koller

AbstractDynamic 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 sufcient statistics. We propose a novel approximation scheme that allows these su cient statistics to be computed e ciently. 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.

1 IntroductionMany real world phenomena are naturally modeled as dynamic systems: the stock market, measurements of a patient's vital signs in an intensive care unit, vehicles on a freeway, etc. Knowledge of a system's dynamics is essential for many tasks, including prediction, monitoring, and the detection of anomalies.

Real world complex systems are typically highly structured, consisting of several interacting entities. Dynamic Bayesian networks (DBNs) provide a representational language for modeling such structured systems. By representing a system's state via several variables, and describing the relations between them, a DBN can capture the underlying structure of the system dynamics, e.g., which stocks depend on which other and on what external variables. Compared to less structured representations such as hidden Markov models (HMMs), DBNs support e ective approximate inference Boyen and Koller 1998b] and feature more robust learning due to their reduced number of parameters. Recent work has made signi cant progress on the problem of learning Bayesian networks from data (see, for example, Heckerman 1999]. These ideas have recently been applied to the problem of learning DBNs in the presence of partially observable data Friedman et al. 1998], using the Structural EM (SEM) algorithm Fr

iedman 1997]. The basic outline of SEM is as follows: Each iteration starts with the current candidate DBN. In the E-step, the missing data is completed using the expected value relative to the current DBN, and the completed data is used to gather expected su cient statistics| the completed\counts" corresponding to various events. In the M-step, These statistics are then used to score a variety of new candidate structures, and the best scoring candidate is selected. After one or more structural changes, the completed data and statistics are recomputed. The methods described by Friedman et al., su er from two major shortcomings. First, their approach has signi cant computational cost when applied to complex processes such as stock market data. Second, as this algorithm does not change the variables in the network, hidden variables must be prespeci ed by the user. In this paper, we outline these limitations and suggest methods that address both issues. The computational cost of the SEM approach is due

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科Discovering the hidden structure of complex dynamic systems全文阅读和word下载服务。