Abstract
Traditional AI reasoning relies on knowledge bases (KBs) represented as logical formulas, a method that often leads to NP-hard computational challenges. This paper proposes an alternative: representing a KB as a set of "characteristic models"—specific satisfying assignments that capture the essence of the knowledge. By leveraging Monotone Theory, we demonstrate that for a wide range of propositional theories, this model-based representation allows for deductive and abductive reasoning in polynomial time. This approach provides a mathematical foundation for "vivid" reasoning and generalizes previous work on Horn theories.
Introduction
In classical artificial intelligence, knowledge is typically encoded as a collection of logical rules, such as Conjunctive Normal Form (CNF) formulas. Reasoning then becomes a process of checking whether a new statement, $\alpha$, is logically implied by the knowledge base ($KB \models \alpha$). While mathematically elegant, this formula-based approach is computationally expensive, often making real-time "common-sense" reasoning impossible.
This research suggests that the bottleneck lies in the representation itself. Drawing inspiration from the "mental models" theory in cognitive psychology, we explore a model-based approach. Instead of storing rules, the system stores a carefully selected set of examples (models). We show that for many expressive classes of logic, this representation is not only compact but also enables significantly more efficient inference than traditional methods.
The Framework: Characteristic Models
The core of this approach is the identification of characteristic models. Not every satisfying assignment of a KB needs to be stored. Instead, we use Monotone Theory to identify a subset of models that can represent the entire theory for a specific set of queries.
1. The Basis and Minimal Assignments
The framework defines a "basis" ($B$), which is a set of assignments that induces a partial order over the space of all possible worlds. For any given KB, we identify the "minimal" models relative to this basis. These minimal assignments constitute the characteristic models.
2. The Model-Based Test
To determine if $KB \models \alpha$, the system performs a simple check: does every characteristic model of the KB satisfy $\alpha$? If a model exists that satisfies the KB but fails $\alpha$, the implication is false. While this test is not universal for all possible queries, it is exact for "relevant" queries—those that share a basis with the KB.
Efficiency and Compactness
A critical concern for any model-based system is the size of the representation. If we had to store every possible model, the system would suffer from exponential growth.
- DNF and Compactness: The number of characteristic models is bounded by the size of the KB’s Disjunctive Normal Form (DNF). Specifically, the size is at most $|B| \times |DNF(KB)|$. For theories where the DNF is relatively small, the model-based representation remains compact even if the rule-based (CNF) representation is complex.
- Polynomial-Time Deduction: For common query languages—including Horn, reversed Horn, and $log\ n$ CNF—reasoning with characteristic models is shown to be polynomial in the size of the representation. This allows for efficient deduction in cases where formula-based methods might be intractable.
Abductive Reasoning
Abduction—the process of finding the best explanation for an observation—is typically more computationally demanding than deduction. However, within the model-based framework, abduction becomes remarkably efficient. We present an algorithm that can find a minimal abductive explanation in time polynomial to the number of characteristic models and the number of possible assumptions. This transformation of a traditionally hard problem into a polynomial-time task is one of the most significant advantages of the model-based approach.
Generalizing Horn Theories
This work provides a unifying framework that explains why certain types of logic, like Horn theories, are easier to handle. Horn theories have a fixed, simple basis, making them a specific case of this broader model-based theory. By generalizing these properties, we can identify new classes of theories (such as $k$-quasi-Horn) that also support efficient reasoning.
Limitations and Future Directions
The primary trade-off in model-based reasoning is the Query Constraint. The efficiency gains are tied to "restricted" queries. If a query falls outside the basis of the KB, the model-based test may yield a "false positive" (concluding an implication exists when it does not).
Furthermore, the process of Knowledge Compilation—converting a formula-based KB into characteristic models—can be computationally expensive. However, this is a one-time cost that pays off during subsequent reasoning tasks.
Future research aims to extend these techniques from propositional logic to first-order logic and apply model-based reasoning to automated planning. Additionally, the authors point toward a "Learning to Reason" framework, where characteristic models are learned directly from environmental interactions rather than being compiled from pre-existing formulas.
Conclusion
By shifting the focus from logical formulas to characteristic models, we can achieve efficient, "vivid" reasoning for complex knowledge bases. This approach bridges the gap between the expressive power of logic and the computational requirements of real-time AI systems.
Summary updated