Evidence-Based Clustering for Scalable Inference in Markov Logic
Evidence-Based Clustering for Scalable Inference in Markov Logic
复制标题
用于马尔可夫逻辑中可扩展推理的基于证据的聚类
DOI：
10.1007/978-3-662-44845-8_17
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Vibhav Gogate
中科院分区：
文献类型：
--
作者：
D. Venugopal;Vibhav Gogate
提升推理算法利用一阶概率逻辑表示（例如马尔可夫逻辑网络 (MLN)）中的对称性，并且自然比基于 MLN 的命题推理算法更具可扩展性。然而，提升推理算法存在“证据问题”——证据打破对称性，并且提升推理算法的性能与命题推理算法相同（或者有时由于开销而更糟）。在本文中，我们提出了解决该问题的通用方法。我们方法的主要思想是用具有 k 个对象的 MLN 来近似具有 n 个对象的给定 MLN，使得 k << n，并且通过在较小的 MLN 上运行可能更快的推理所获得的结果尽可能接近通过在较大的 MLN 上运行推理所获得的结果。我们通过使用标准聚类算法（例如 K 均值）查找“相似”基础的聚类，并用聚类中心替换聚类中的所有基础来实现此目的。为此，我们根据向 MLN 提供的证据，开发了一种新颖的距离（或相似性）函数来测量两个基础之间的相似性。我们利用各种聚类和推理算法在不同的基准上评估了我们的方法。我们的实验清楚地表明了我们方法的通用性和可扩展性。
Lifted inference algorithms take advantage of symmetries in first-order probabilistic logic representations such as Markov logic networks (MLNs), and are naturally more scalable than propositional inference algorithms which ground the MLN. However, lifted inference algorithms have an "evidence problem" - evidence breaks symmetries, and the performance of lifted inference algorithms is the same as propositional inference algorithms (or sometimes worse, due to overhead). In this paper, we propose a general method for addressing this problem. The main idea in our method is to approximate the given MLN having, say, n objects by an MLN having k objects such that k ≪ n and the results obtained by running potentially much faster inference on the smaller MLN are as close as possible to the ones obtained by running inference on the larger MLN. We achieve this by finding clusters of "similar" groundings using standard clustering algorithms (e.g., K-means), and replacing all groundings in the cluster by their cluster center. To this end, we develop a novel distance (or similarity) function for measuring the similarity between two groundings, based on the evidence presented to the MLN. We evaluated our approach on different benchmarks utilizing various clustering and inference algorithms. Our experiments clearly show the generality and scalability of our approach.