Abstract
Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order logic theory on a given finite domain. First-Order Logic theories that admit polynomial-time WFOMC w.r.t domain cardinality are called domain liftable. We introduce the concept of lifted interpretations as a tool for formulating closed forms for WFOMC. Using lifted interpretations, we reconstruct the closed-form formula for polynomial-time FOMC in the universally quantified fragment of FO2, earlier proposed by Beame et al. We then expand this closed-form to incorporate cardinality constraints, existential quantifiers, and counting quantifiers (a.k.a C2) without losing domain-liftability. Finally, we show that the obtained closed-form motivates a natural definition of a family of weight functions strictly larger than symmetric weight functions.
Introduction
In the field of Artificial Intelligence, probabilistic inference over large relational domains is often described using First-Order Logic (FOL). A significant challenge in this area is the computational complexity of Weighted First-Order Model Counting (WFOMC). Traditional "grounding" methods, which replace variables with every possible object in a domain, suffer from an exponential explosion in complexity as the domain size increases.
"Lifted inference" offers a solution by exploiting symmetries within the logic, allowing for reasoning about groups of identical objects rather than individuals. While the two-variable fragment of FOL ($FO^2$) is known to be domain-liftable, existing algorithms are often complex and rely on indirect mathematical tools. This paper presents a unified, closed-form combinatorial formula for WFOMC in $FO^2$ and its extension with counting quantifiers ($C^2$), providing a direct and efficient path for inference.
Methodology: Lifted Interpretations and Combinatorial Counting
The authors' approach centers on three primary pillars that enable the derivation of a closed-form formula.
Lifted Interpretations
The core innovation is the introduction of "lifted interpretations." Unlike standard interpretations that assign truth values to grounded atoms, lifted interpretations assign values to atoms with variables. This abstraction allows the framework to count "types" of elements (1-types) and pairs (2-types) across the domain.
Principle of Inclusion-Exclusion (PIE)
To incorporate existential ($\exists x$) and counting quantifiers ($\exists^{=m} x$), the authors employ the Principle of Inclusion-Exclusion. This technique transforms complex constraints into a weighted sum of simpler, universally quantified formulas, ensuring that the resulting expressions remain domain-liftable.
Combinatorial Counting
The final closed-form formula is built using multinomial coefficients and power terms. It effectively counts the number of ways to distribute $n$ domain elements into various types such that the underlying logic formula is satisfied.
Key Insights
- Unified Framework: The paper demonstrates that existential quantifiers, cardinality constraints, and counting quantifiers can be integrated into a single combinatorial framework, simplifying what were previously treated as distinct algorithmic challenges.
- Enhanced Expressivity: By extending WFOMC to "count distributions," the authors allow for weight functions that depend on the number of elements satisfying a property. This enables the modeling of complex distributions, such as those requiring an even number of successes, which are not possible with standard symmetric weights.
- Domain-Liftability of $C^2$: The paper proves that for a fixed formula, the model count can be computed in polynomial time relative to the domain size $n$, confirming that the $C^2$ fragment is domain-liftable.
Conclusion and Future Directions
This work provides a powerful mathematical tool for probabilistic relational modeling by deriving a direct, closed-form formula for WFOMC in $C^2$. While the results are currently limited to the two-variable fragment and function-free languages, the "lifted interpretation" methodology offers a promising avenue for exploring more complex logic fragments. Future work may extend these techniques to description logics or specific fragments of higher-order logic, potentially pushing the boundaries of efficient lifted inference.
Summary updated