Continuous Time Markov Networks

T. El-Hay, N. Friedman, D. Koller, and R. Kupferman

Proc. Twenty Second Conf. on Uncertainty in Artificial Intelligence (UAI 06), 2006.



A central task in many applications is reasoning about processes that change over continuous time. Recently, Nodelman et al. introduced continuous time Bayesian networks (CTBNs), a structured representation for representing Continuous Time Markov Processes over a structured state space. In this paper, we introduce continuous time Markov networks (CTMNs), an alternative representation language that represents a different type of continuous-time dynamics, particularly appropriate for modeling biological and chemical systems. In this language, the dynamics of the process is described as an interplay between two forces: the tendency of each entity to change its state, which we model using a continuous-time proposal process that suggests possible local changes to the state of the system at different rates; and a global fitness or energy function of the entire system, governing the probability that a proposed change is accepted, which we capture by a Markov network that encodes the fitness of different states. We show that the fitness distribution is also the stationary distribution of the Markov process, so that this representation provides a characterization of a temporal process whose stationary distribution has a compact graphical representation. We describe the semantics of the representation, its basic properties, and how it compares to CTBNs. We also provide an algorithm for learning such models from data, and demonstrate its potential benefit over other learning approaches.