Part of Advances in Neural Information Processing Systems 11 (NIPS 1998)
Xavier Boyen, Daphne Koller
Inference is a key component in learning probabilistic models from par(cid:173) tially observable data. When learning temporal models, each of the many inference phases requires a traversal over an entire long data se(cid:173) quence; furthermore, the data structures manipulated are exponentially large, making this process computationally expensive. In [2], we describe an approximate inference algorithm for monitoring stochastic processes, and prove bounds on its approximation error. In this paper, we apply this algorithm as an approximate forward propagation step in an EM algorithm for learning temporal Bayesian networks. We provide a related approxi(cid:173) mation for the backward step, and prove error bounds for the combined algorithm. We show empirically that, for a real-life domain, EM using our inference algorithm is much faster than EM using exact inference, with almost no degradation in quality of the learned model. We extend our analysis to the online learning task, showing a bound on the error resulting from restricting attention to a small window of observations. We present an online EM learning algorithm for dynamic systems, and show that it learns much faster than standard offline EM.