Fast Lifted MAP Inference via Partitioning
Fast Lifted MAP Inference via Partitioning
复制标题
通过分区快速提升 MAP 推理
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Vibhav Gogate
中科院分区：
文献类型：
--
作者：
Somdeb Sarkhel;Parag Singla;Vibhav Gogate
最近，人们对提升马尔可夫逻辑网络 (MLN) 的 MAP 推理算法越来越感兴趣。这些提升算法的一个关键优点是，当 MLN 中存在对称性并且可以使用提升推理规则检测这些对称性时，它们的计算复杂度比命题算法小得多。不幸的是，提升的推理规则是合理的，但并不完整，并且经常会错过许多对称性。这是有问题的，因为当无法利用对称性时，提升推理算法会为 MLN 奠定基础，并在更大的命题空间中搜索解决方案。在本文中，我们提出了一种新颖的方法，它巧妙地在接地时引入了新的对称性。我们的主要想法是划分地面原子并强制推理算法将每个部分中的所有原子视为不可区分。我们表明，通过系统地、仔细地细化（和增长）分区，我们可以构建先进的任意时间和任意空间的 MAP 推理算法。我们对几个现实世界数据集的实验清楚地表明，我们的新算法优于以前的方法，并且经常在搜索空间中找到现有提升推理规则无法检测到的有用对称性。
Recently, there has been growing interest in lifting MAP inference algorithms for Markov logic networks (MLNs). A key advantage of these lifted algorithms is that they have much smaller computational complexity than propositional algorithms when symmetries are present in the MLN and these symmetries can be detected using lifted inference rules. Unfortunately, lifted inference rules are sound but not complete and can often miss many symmetries. This is problematic because when symmetries cannot be exploited, lifted inference algorithms ground the MLN, and search for solutions in the much larger propositional space. In this paper, we present a novel approach, which cleverly introduces new symmetries at the time of grounding. Our main idea is to partition the ground atoms and force the inference algorithm to treat all atoms in each part as indistinguishable. We show that by systematically and carefully refining (and growing) the partitions, we can build advanced any-time and any-space MAP inference algorithms. Our experiments on several real-world datasets clearly show that our new algorithm is superior to previous approaches and often finds useful symmetries in the search space that existing lifted inference rules are unable to detect.