Approximate Probabilistic Inference via Word-Level Counting

Abstract

Hashing-based model counting has emerged as a promising approach for large-scale probabilistic inference on graphical models. A key component of these techniques is the use of xor-based 2-universal hash functions that operate over Boolean domains. Many counting problems arising in probabilistic inference are, however, naturally encoded over finite discrete domains. Techniques based on bit-level (or Boolean) hash functions require these problems to be propositionalized, making it impossible to leverage the remarkable progress made in SMT (Satisfiability Modulo Theory) solvers that can reason directly over words (or bit-vectors). In this work, we present the first approximate model counter that uses word-level hashing functions, and can directly leverage the power of sophisticated SMT solvers. Empirical evaluation over an extensive suite of benchmarks demonstrates the promise of the approach.

Full version of AAAI 2016 paper

References in corpus (3)

• Sampling Techniques for Boolean Satisfiability
• Probabilistic Inference Modulo Theories
• Structured Learning Modulo Theories

Cited by in corpus (6)

• Constrained Counting and Sampling: Bridging the Gap between Theory and Practice
• Efficient Search-Based Weighted Model Integration
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
• Bit-Vector Model Counting using Statistical Estimation
• A New Probabilistic Algorithm for Approximate Model Counting
• Counting the Number of Solutions to Constraints