Cutset Networks: A Simple, Tractable, and Scalable Approach for Improving the Accuracy of Chow-Liu Trees
Cutset Networks: A Simple, Tractable, and Scalable Approach for Improving the Accuracy of Chow-Liu Trees
复制标题
DOI：
10.1007/978-3-662-44851-9_40
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
Tahrima Rahman;Prasanna V. Kothalkar;Vibhav Gogate
中科院分区：
文献类型：
--
作者：
Tahrima Rahman;Prasanna V. Kothalkar;Vibhav Gogate
本文提出了一种新的易处理概率模型——切集网络，用于表示多维离散分布。割集网络是根OR搜索树，其中每个OR节点表示模型中变量的条件作用，树贝叶斯网络（Chow-Liu树）位于叶子。从推理的角度来看，割集网络模拟了Pearl的割集条件反射算法的机制，这是一种流行的概率图模型的精确推理方法。我们提出了高效的算法，这些算法利用并采用了大量关于决策树归纳的研究，用于从数据中学习割集网络。我们也提出了一种期望最大化（EM）算法来学习切集网络的混合。我们在各种基准数据集上的实验清楚地表明，与学习其他可处理模型（如薄结树、潜在树模型、算术电路和和积网络）的方法相比，我们的方法具有更大的可扩展性，并提供类似或更好的准确性。
In this paper, we present cutset networks, a new tractable probabilistic model for representing multi-dimensional discrete distributions. Cutset networks are rooted OR search trees, in which each OR node represents conditioning of a variable in the model, with tree Bayesian networks (Chow-Liu trees) at the leaves. From an inference point of view, cutset networks model the mechanics of Pearl’s cutset conditioning algorithm, a popular exact inference method for probabilistic graphical models. We present efficient algorithms, which leverage and adopt vast amount of research on decision tree induction for learning cutset networks from data. We also present an expectation-maximization (EM) algorithm for learning mixtures of cutset networks. Our experiments on a wide variety of benchmark datasets clearly demonstrate that compared to approaches for learning other tractable models such as thin-junction trees, latent tree models, arithmetic circuits and sum-product networks, our approach is significantly more scalable, and provides similar or better accuracy.