Partition MCMC for Inference on Acyclic Digraphs

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.有向无环图（Directed Acyclic Graph, DAG）是贝叶斯网络的底层表示形式，而贝叶斯网络是一类应用广泛的概率图模型（Probabilistic Graphical Model）。从数据中学习其底层图结构，是获取某一研究领域结构特性认知的有效途径。结构学习是统计图模型的核心推理挑战之一。马尔可夫链蒙特卡洛（Markov chain Monte Carlo, MCMC）方法——尤其是结构MCMC——用于从给定数据的后验分布中采样图结构，或许是实现贝叶斯模型平均的唯一可行方案。评分模块化与各节点父节点数量的限制，可将图结构划分为更大的集合，这些集合可整体进行评分，以此提升马尔可夫链的收敛效率。当前利用分组策略的典型算法包括作用于置换三角矩阵替代空间的带偏置顺序MCMC，以及非遍历性边反转操作。本文提出一种全新算法，该算法利用有向无环图的底层组合结构来定义全新的分组方式。相较传统结构MCMC方法，该算法可提升收敛性能，同时仍能保证生成无偏采样样本的特性。最后，该方法可与边反转操作相结合，进一步优化采样器性能。本文的补充材料可在线获取。