Open-Universe Weighted Model Counting

Vaishak Belle

Abstract

Weighted Model Counting (WMC) is a cornerstone of probabilistic inference, yet it traditionally operates under the Domain Closure Assumption, limiting its applicability to finite, known sets of objects. This paper introduces a theoretical framework for Open-Universe (OU) WMC, extending inference to infinite domains. By proving that reasoning over an infinite universe can be reduced to a finite WMC problem through the addition of a small number of "placeholder" constants, the author enables exact and efficient reasoning using existing solvers. Empirical evaluations demonstrate that this approach outperforms existing sampling-based engines and maintains performance parity with closed-world models.

Introduction

In probabilistic AI, Weighted Model Counting (WMC) is used to quantify the likelihood of events by counting the weighted truth assignments of a logical formula. However, standard WMC assumes a "Closed-World," where all relevant objects are explicitly defined. In real-world domains like computer vision or natural language processing, we often encounter "unknown unknowns"—an infinite number of potential entities not present in the initial data.

This research, presented at AAAI-17 by Vaishak Belle, bridges the gap between WMC and open-universe reasoning. It provides a formal logic-based foundation for handling infinite domains without the computational intractability typically associated with such models.

The Challenge of Domain Closure

Most relational probabilistic models, such as Markov Logic Networks, rely on the Domain Closure Assumption (DCA). Under DCA, the universe is restricted to named constants (e.g., "Alice" and "Bob"). If an alarm system is modeled with two known neighbors, the system assumes no other neighbors exist.

In an "open" universe, an infinite number of unnamed individuals could potentially trigger an event. Standard WMC cannot represent these infinite possibilities without the underlying mathematics breaking down. Previous solutions often resorted to complex sampling or restricted probabilistic programming languages that lacked a rigorous logical foundation.

Methodology: Reducing Infinite to Finite

The core innovation of this work is the introduction of Open-Universe (OU) template models and a mathematical proof that infinite counting is unnecessary for exact inference.

1. Acceptable Knowledge Bases

The framework utilizes a specific class of first-order logic formulas—universal clauses with equality. This structure is expressive enough for most AI tasks while remaining computationally manageable.

2. The Rank Reduction

The paper identifies the "rank" of a knowledge base as the maximum number of variables in any single rule. Theorem 9 proves that to reason about an infinite domain, one only needs to ground the rules using known constants plus a small set of "placeholder" constants equal to the rank of the KB. This expanded but finite set, denoted as $OU(\Delta)$, allows the problem to be treated as a standard WMC task.

3. Lifted Inference

To optimize performance, the author converts models into an Equality-free Normal Form (ENF). This enables the use of "lifted" solvers, which reason about groups of interchangeable objects simultaneously, providing significant speedups over grounding-based methods.

Experimental Evaluation

The approach was evaluated on several probabilistic benchmarks, including Pearl’s Alarm network (AlarmR, AlarmX), the "Friends and Smokers" network (Smoker1, Smoker2), and a student performance model (Grades).

Performance Comparison

The proposed method, WMCOU, was compared against BLOG, a prominent sampling-based open-universe engine. As shown in Figure 1, WMCOU significantly outperformed BLOG across multiple benchmarks. For instance, on the Grades problem, WMCOU achieved inference in 0.36 seconds, compared to 6.0 seconds for BLOG.

Comparison of WMCOU and BLOG execution times (in seconds) across benchmarks.

Open-Universe vs. Domain Closure

A key finding was the minimal overhead required to move from a closed-world (DC) to an open-universe (OU) setting. As illustrated in Figure 2, the execution times for OU semantics were nearly identical to those of DC semantics, with differences often measuring only a few milliseconds. This suggests that open-universe reasoning can be achieved with virtually no performance penalty compared to traditional methods.

Comparison of execution times (in seconds) for Open-Universe (OU) vs. Domain Closure (DC) semantics.

Conclusion

This work establishes a robust logical and computational framework for Open-Universe Weighted Model Counting. By demonstrating that infinite domains can be reduced to finite sets through symmetry and rank-based grounding, the author enables exact inference in complex, open-ended environments. Future work aims to expand this framework to include existential quantifiers within knowledge bases and more complex, identity-dependent weighting schemes.

Reference: Belle, V. (2017). Open-Universe Weighted Model Counting. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17).

Summary updated

BibTeX
@inproceedings{belle2017open,
  author = {Vaishak Belle},
  title = {{Open-Universe Weighted Model Counting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11057},
}

Loading related content...

Figure