Advances in exact Bayesian structure discovery in Bayesian networks

Understand

We consider a Bayesian method for learning the Bayesian network structure from complete data.

• Recently, Koivisto and Sood (2004) presented an algorithm that for any single edge computes its marginal posterior probability in O(n 2^n) time, where n is the number of attributes; the number of parents per attribute is bounded by a constant.
• In this paper we show that the posterior probabilities for all the n (n - 1) potential edges can be computed in O(n 2^n) total time.
• This result is achieved by a forward-backward technique and fast Moebius transform algorithms, which are of independent interest.