Algebraic Model Counting

2012/11/19 by Kimmig, Angelika, Broeck, Guy Van den, De Raedt, Luc · 7 citations
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1211.4475

Abstract

Weighted model counting (WMC) is a well-known inference task on knowledge bases, used for probabilistic inference in graphical models. We introduce algebraic model counting (AMC), a generalization of WMC to a semiring structure. We show that AMC generalizes many well-known tasks in a variety of domains such as probabilistic inference, soft constraints and network and database analysis. Furthermore, we investigate AMC from a knowledge compilation perspective and show that all AMC tasks can be evaluated using sd-DNNF circuits. We identify further characteristics of AMC instances that allow for the use of even more succinct circuits.

Cited by

• DeepGraphLog for Layered Neurosymbolic AI
• The DeepLog Neurosymbolic Machine
• A Unifying Framework for Semiring-Based Constraint Logic Programming With Negation (full version)
• Fagin's Theorem for Semiring Turing Machines
• Defining neurosymbolic AI
• On the Relevance of Logic for Artificial Intelligence, and the Promise of Neurosymbolic Learning
• A Quantum Information Theoretic Approach to Tractable Probabilistic Models

Related

• The Gradient of Algebraic Model Counting
• Scaling up Probabilistic Inference in Linear and Non-Linear Hybrid Domains by Leveraging Knowledge Compilation
• Approximate Weighted First-Order Model Counting: Exploiting Fast\n Approximate Model Counters and Symmetry
• Approximate Model Counting by Partial Knowledge Compilation
• ADDMC: Weighted Model Counting with Algebraic Decision Diagrams