Bayesian structure learning using dynamic programming and MCMC

Abstract

We show how to significantly speed up MCMC sampling of DAG structures by using a powerful non-local proposal based on Koivisto’s dynamic programming (DP) algorithm (11; 10), which computes the exact marginal posterior edge probabilities by analytically summing over orders. Furthermore, we show how sampling in DAG space can avoid subtle biases that are introduced by approaches that work only with orders, such as Koivisto’s DP algorithm and MCMC order samplers (6; 5). 1