Just Count the Satisfied Groundings: Scalable Local-Search and Sampling Based Inference in MLNs
Just Count the Satisfied Groundings: Scalable Local-Search and Sampling Based Inference in MLNs
复制标题
只需计算满意的基础：MLN 中的可扩展本地搜索和基于采样的推理
DOI：
10.1609/aaai.v29i1.9676
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Vibhav Gogate
中科院分区：
文献类型：
--
作者：
D. Venugopal;Somdeb Sarkhel;Vibhav Gogate
马尔可夫逻辑网络的各种基于采样和基于局部搜索的推理算法（例如，吉布斯采样、MC-SAT、MaxWalksat 等）的主要计算瓶颈是计算一阶公式的基数，该基数在给定所有基原子的真值分配的情况下为真。我们将此问题简化为计算约束满足问题（CSP）的解数的问题，并表明在执行过程中，基于采样的算法和基于局部搜索的算法都会重复解决该计数问题的动态版本。根据有关 CSP 和图形模型的大量文献，我们提出了一种基于精确连接树的算法，用于计算动态 CSP 的解数，分析其属性，并展示如何使用它来提高 Gibbs 采样和 MaxWalksat 的计算复杂度。对各种基准的实证测试清楚地表明，我们的新方法比现有方法的可扩展性高出几个数量级。
The main computational bottleneck in various sampling based and local-search based inference algorithms for Markov logic networks (e.g., Gibbs sampling, MC-SAT, MaxWalksat, etc.) is computing the number of groundings of a first-order formula that are true given a truth assignment to all of its ground atoms. We reduce this problem to the problem of counting the number of solutions of a constraint satisfaction problem (CSP) and show that during their execution, both sampling based and local-search based algorithms repeatedly solve dynamic versions of this counting problem. Deriving from the vast amount of literature on CSPs and graphical models, we propose an exact junction-tree based algorithm for computing the number of solutions of the dynamic CSP, analyze its properties, and show how it can be used to improve the computational complexity of Gibbs sampling and MaxWalksat. Empirical tests on a variety of benchmarks clearly show that our new approach is several orders of magnitude more scalable than existing approaches.