Partition MCMC for Inference on Acyclic Digraphs

By Jack Kuipers, Giusi Moffa. 2015

110 citations recorded by the source corpus.

ABSTRACT Acyclic digraphs are the underlying representation of Bayesian networks, a widely used class of probabilistic graphical models. Learning the underlying graph from data is a way of gaining insights about the structural properties of a domain. Structure learning forms one of the inference challenges of statistical graphical models. Markov chain Monte Carlo (MCMC) methods, notably structure MCMC, to sample graphs from the posterior distribution given the data are probably the only viable option for Bayesian model averaging. Score modularity and restrictions on the number of parents of each node allow the graphs to be grouped into larger collections, which can be scored as a whole to improve the chain’s convergence. Current examples of algorithms taking advantage of grouping are the biased order MCMC, which acts on the alternative space of permuted triangular matrices, and nonergodic edge reversal moves. Here, we propose a novel algorithm, which employs the underlying combinatorial structure of DAGs to define a new grouping. As a result convergence is improved compared to structure MCMC, while still retaining the property of producing an unbiased sample. Finally, the method can be combined with edge reversal moves to improve the sampler further. Supplementary materials for this article are available online.

Subfields: Artificial Intelligence, Graph Learning, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Graph Learning

In Probabilistic & Bayesian Methods

Citations in the corpus

Bayesian Structure Learning with Generative Flow Networks (2022, methodology): “This was further reﬁned by either modifying the underlying space of the Markov chain (Kuipers and Moffa, 2017; Niinimäki et al., 2016), or its local moves (Mansinghka et al., 2006; Eaton and Murphy, 2007a; Kuipers et al., 2021).”
Tree inference for single-cell data (2016, unknown): “This marginalization is equivalent to grouping all attachments to the same tree into a single object, which is responsible for the similarly large speed-up for sampling Bayesian networks in order MCMC [38] and more recently partition MCMC [39].”
DiBS: Differentiable Bayesian Structure Learning (2021, background): “Several works try to remedy its poor mixing behavior [38–40].”
Towards Scalable Bayesian Learning of Causal DAGs (2020, methodology): “[16, 19], implemented in the BiDAG package, with some major modifications.”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “Proposing such a move from Λ to Λ (cid:48) and accepting with probability while accounting for the neighbourhood sizes (following Kuipers and Moﬀa, 2017) is suﬃ-cient to sample partitions proportionally to their posterior probability in the search space.”
Variational Causal Networks: Approximate Bayesian Inference over Causal Structures (2021, methodology): “A popular choice for such an approach is the Markov Chain Monte Carlo (MCMC) with suitably chosen energy functions and heuristics [8, 26, 25, 22, 14, 9].”