Polynomial time algorithm for learning globally optimal Dynamic Bayesian network

This paper is concerned with the problem of learning the globally optimal structure of a dynamic Bayesian network (DBN). We propose using a recently introduced information theoretic criterion named MIT (Mutual Information Test) for evaluating the goodness-of-fit of the DBN structure. MIT has been previously shown to be effective for learning static Bayesian network, yielding results competitive to other popular scoring metrics, such as BIC/MDL, K2 and BD, and the well-known constraint-based PC algorithm. This paper adapts MIT to the case of DBN. Using a modified variant of MIT, we show that learning the globally optimal DBN structure can be efficiently achieved in polynomial time.Lecture Notes in Computer Science, vol 7064