论文标题
近似加权的一阶模型计数：利用快速近似模型计数器和对称性
Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry
论文作者
论文摘要
我们研究了对称加权的一阶模型计数任务，并呈现ActoWFOMC，这是一种在存在未加权的一阶模型计数Oracle的情况下有效地界定加权一阶模型计数的新颖方法。该算法具有推论多种一阶概率表示的应用，例如马尔可夫逻辑网络和概率逻辑程序。至关重要的是，对于许多应用程序，我们对输入句子的形式没有任何假设。取而代之的是，我们的算法利用了问题中固有的对称性，通过对句子文字的可能真实基础的数量施加基础性约束。在实践中使用近似基于哈希的模型计数器ACOTMC3实现一阶模型计数Oracle，我们展示了我们的算法在一阶概率模型中的表现如何优于现有的近似和精确技术。我们还提供生成界限的PAC保证。
We study the symmetric weighted first-order model counting task and present ApproxWFOMC, a novel anytime method for efficiently bounding the weighted first-order model count in the presence of an unweighted first-order model counting oracle. The algorithm has applications to inference in a variety of first-order probabilistic representations, such as Markov logic networks and probabilistic logic programs. Crucially for many applications, we make no assumptions on the form of the input sentence. Instead, our algorithm makes use of the symmetry inherent in the problem by imposing cardinality constraints on the number of possible true groundings of a sentence's literals. Realising the first-order model counting oracle in practice using the approximate hashing-based model counter ApproxMC3, we show how our algorithm outperforms existing approximate and exact techniques for inference in first-order probabilistic models. We additionally provide PAC guarantees on the generated bounds.
