Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry

We study the symmetric weighted first-order model counting task and present\nApproxWFOMC, a novel anytime method for efficiently bounding the weighted\nfirst-order model count in the presence of an unweighted first-order model\ncounting oracle. The algorithm has applications to inference in a variety of\nfirst-order probabilistic representations, such as Markov logic networks and\nprobabilistic logic programs. Crucially for many applications, we make no\nassumptions on the form of the input sentence. Instead, our algorithm makes use\nof the symmetry inherent in the problem by imposing cardinality constraints on\nthe number of possible true groundings of a sentence's literals. Realising the\nfirst-order model counting oracle in practice using the approximate\nhashing-based model counter ApproxMC3, we show how our algorithm outperforms\nexisting approximate and exact techniques for inference in first-order\nprobabilistic models. We additionally provide PAC guarantees on the generated\nbounds.\n