Compiling Probabilistic Graphical Models Using Sentential Decision Diagrams
Compiling Probabilistic Graphical Models Using Sentential Decision Diagrams
复制标题
使用句子决策图编译概率图形模型
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Adnan Darwiche
中科院分区：
文献类型：
--
作者：
Arthur Choi;D. Kisa;Adnan Darwiche
知识编译是一种在概率图模型中进行精确推理的强大方法，它能够有效地利用确定性和上下文特定的独立性，使其能够扩展到高度连接的模型，否则使用更传统的方法（仅基于树宽）是不可行的。以前的方法基于执行两个步骤：将模型编码为CNF，然后将CNF编译为等效但更易处理的表示（d-DNNF），其中精确推理简化为加权模型计数。在本文中，我们研究了一个自下而上的方法，这是最近提出的表示，句子决策图（SDD）。我们描述了一种新的和有效的方式来编码一个给定的模型的因素直接SDD，绕过CNF表示。要编译一个给定的模型，现在只需使用apply运算符将其因子的SDD表示结合起来，这是d-DNNFs所缺乏的。从经验上讲，我们发现我们更简单的知识编译方法与基于d-DNNFs的方法一样有效，有时甚至更快。
Knowledge compilation is a powerful approach to exact inference in probabilistic graphical models, which is able to effectively exploit determinism and context-specific independence, allowing it to scale to highly connected models that are otherwise infeasible using more traditional methods (based on treewidth alone). Previous approaches were based on performing two steps: encode a model into CNF, then compile the CNF into an equivalent but more tractable representation (d-DNNF), where exact inference reduces to weighted model counting. In this paper, we investigate a bottom-up approach, that is enabled by a recently proposed representation, the Sentential Decision Diagram (SDD). We describe a novel and efficient way to encode the factors of a given model directly to SDDs, bypassing the CNF representation. To compile a given model, it now suffices to conjoin the SDD representations of its factors, using an apply operator, which d-DNNFs lack. Empirically, we find that our simpler approach to knowledge compilation is as effective as those based on d-DNNFs, and at times, orders-of-magnitude faster.