First-Order Model Counting in a Nutshell

Guy Van den BroeckIJCAI 2016 · OpenReview

Abstract

First-order model counting (FOMC) is an advanced framework for probabilistic reasoning that operates on logic sentences rather than individual variables. By exploiting symmetries and exchangeability within data, FOMC enables the solution of complex inference problems in polynomial time, overcoming the exponential complexity constraints that typically hinder traditional propositional solvers.

Introduction

In modern artificial intelligence, calculating probabilities within complex systems—such as social networks or genetic models—is a fundamental challenge. A standard approach is Weighted Model Counting (WMC), which involves counting the satisfying assignments (models) of a logical formula, where each model is assigned a specific weight.

However, traditional "propositional" model counters (e.g., #SAT solvers) face significant scaling issues. They treat every individual entity as a unique variable. For instance, a rule stating "people who are stressed tend to smoke" would require a propositional solver to create a separate variable for every person in a database. As the domain size ($n$) grows, the state space explodes. This paper explores First-Order Model Counting (FOMC), which reasons about these rules at a higher level of abstraction—treating "people" as a class rather than a list of individuals—to bypass this combinatorial explosion.

Methodology

The paper outlines several core principles that allow FOMC to outperform traditional propositional methods:

  • Lifted Inference: Instead of "grounding" a formula into millions of propositional variables, FOMC uses "lifted" algorithms to reason about groups of objects simultaneously.
  • Exponentiation: For rules applying to $n$ independent individuals, FOMC can calculate the result for a single representative and raise it to the power of $n$, transforming linear-time problems into logarithmic-time ones.
  • Combinatorial Counting: In scenarios with overlapping relationships (e.g., social networks), FOMC utilizes binomial coefficients and combinatorial formulas to count satisfying assignments in polynomial time relative to the domain size.
  • Skolemization: This technique eliminates existential quantifiers while preserving the correct model count, allowing solvers to handle more expressive logical formulas.
  • Weighted Model Integration (WMI): An extension that combines FOMC with Satisfiability Modulo Theories (SMT) to manage "hybrid" scenarios involving both discrete logic and continuous numerical constraints.

Illustrative Examples

As a tutorial-style overview, the paper utilizes two primary examples to demonstrate the efficacy of FOMC:

  1. The "Smokes and Friends" Social Network: A benchmark in statistical relational learning used to show how FOMC handles recursive relationships.
  2. The Shuffled Card Deck: A theoretical example involving variables with zero conditional independence, where every card's position affects every other card.
A visualization of a highly connected relational model, such as a shuffled card deck, where every entity is interdependent.

Key Insights and Ideas

FOMC elegantly decouples qualitative structure (the logic sentence) from quantitative uncertainty (the weight function), allowing researchers to independently modify logic languages or probability distributions. The true power of FOMC lies in exchangeability: if the identity of an individual does not change the underlying rules, FOMC exploits this symmetry to skip redundant calculations.

Furthermore, the paper argues that FOMC is "strictly more powerful" than propositional counting. It can identify and utilize symmetries that are completely lost once a problem is flattened into propositions. A problem that appears "completely connected" and intractable for standard graphical models can often be solved efficiently through the lens of first-order logic.

Results

The advantages of FOMC are quantifiable through its computational complexity improvements:

  • Exponential Speedup: For simple rules over $n$ entities, propositional counters take linear time, while FOMC takes logarithmic time.
  • Polynomial vs. Exponential: In relational settings like the "Smokes/Friends" model, propositional algorithms require exponential time, whereas FOMC evaluates the problem in polynomial time.
  • The Card Deck Solution: While a standard graphical model would struggle with a table of $52^{52}$ rows for a deck of $n$ cards, the FOMC approach calculates the result ($n!$) in polynomial time.

Limitations and Future Work

Despite its power, certain distributions remain intractable if they do not exhibit exploitable symmetries. Identifying the exact boundaries of what can be "lifted" remains an active research area. Additionally, while Weighted Model Integration (WMI) addresses continuous variables, integrating complex continuous densities with first-order logic is a developing frontier. Future work focuses on "knowledge compilation," building robust compilers that translate first-order logic into efficient computational circuits.

Summary updated

BibTeX
@inproceedings{broeck2016first,
  author = {Guy Van den Broeck},
  title = {{First-Order Model Counting in a Nutshell}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=9z86N0E031},
}
Figure