Karthik Gopalratnam, Henry Kautz, Daniel S. Weld
Continuous-time Bayesian networks (CTBNs), are an elegant modeling language for structured stochastic processes that evolve over continuous time. The CTBN framework is based on homogeneous Markov processes, and defines two distributions with respect to each local variable in the system, given its parents: an exponential distribution over when the variable transitions, and a multinomial over what is the next value. In this paper, we present two extensions to the framework that make it more useful in modeling practical applications. The first extension models arbitrary transition time distributions using Erlang-Coxian approximations, while maintaining tractable learning. We show how the censored data problem arises in learning the distribution, and present a solution based on expectation-maximization initialized by the Kaplan-Meier estimate. The second extension is a general method for reasoning about negative evidence, by introducing updates that assert no observable events occur over an interval of time. Such updates were not defined in the original CTBN framework, and we show show that their inclusion can significantly improve the accuracy of filtering and prediction. We illustrate and evaluate these extensions in two real-world domains, email use and GPS traces of a person traveling about a city.
Content Area: 13. Markov Decision Processes & Uncertainty
Subjects: 3.6 Temporal Reasoning; 3.4 Probabilistic Reasoning
Submitted: May 10, 2005