Abstract:
|
Bayesian networks are a widely applicable class of statistical models in which the dependencies among variables are represented by a directed acyclic graph (DAG) with edges encoding a factorization of the likelihood. Inferring aspects of the DAG, such as the locations of edges, is known as structure learning. Because the number of DAGs on d nodes is super-exponential in d, computational challenges limit existing Bayesian methods to structure learning problems with roughly 20-30 nodes. Specifically exact posterior probabilities of edges and other specialized features can be computed in O(d2^d) time and O(2^d) space using dynamic programming. While Markov Chain Monte Carlo (MCMC) methods seek to avoid this 2^d bottleneck, they often fail to scale much beyond 30 nodes. Consequently, we develop a novel MCMC method based on partial orders. At a high level our approach resembles order MCMC, in which the Markov chain runs over the space of linear orderings of the nodes. However, using partial rather than linear orders prevents the bias of the latter and also allows the use of general priors. We compare the developed method to existing approaches using simulated and benchmark datasets.
|