A Description Classifier for the Predicate Calculus

Robert M. MacGregorAAAI 1994

Author: Robert M. MacGregor, USC Information Sciences Institute (1994)

Abstract

In the early 1990s, Description Logics (DLs) were constrained by a trade-off between expressivity and computational decidability. This paper presents a novel description classifier capable of reasoning within the full first-order predicate calculus (PC). By utilizing a structural graph-matching approach combined with "dual representations" and "auto-Socratic elaboration," the system provides a powerful reasoning engine that remains computationally viable. Evaluation against the state-of-the-art Loom classifier demonstrates that while the PC classifier is slower, it enables the representation and verification of complex logical relationships previously beyond the reach of DL systems.

1. Introduction

The primary function of a Description Logic system is the classification of concepts through the determination of subsumption relationships—automatically deciding if one definition is a logical subset of another. Historically, to ensure that these systems remained decidable and efficient, researchers restricted the underlying logic to relatively simple subsets of the predicate calculus. However, these restrictions often limited the utility of DLs in complex domains like database management. This work explores a different path: prioritizing expressivity by supporting the full predicate calculus, even at the cost of theoretical completeness.

2. Methodology

The PC classifier departs from traditional theorem-proving techniques, instead treating subsumption as a structural graph-matching problem.

2.1 Graph-Based Reasoning

Definitions are parsed into directed graphs where nodes represent variables or constants and edges represent predicates. To account for logical implications that simple matching might miss (e.g., transitivity), the system employs forward-chaining "elaboration rules" to augment the graph with inferred edges.

2.2 Dual Representations and Auto-Socratic Elaboration

To manage the computational complexity of graph matching, the system maintains two versions of each relation: a "clean" canonical graph ($g(R)$) and a "dense" elaborated graph ($e-g(R)$). Subsumption testing involves mapping the simple $g(R)$ onto the complex $e-g(S)$, significantly reducing the search space. Furthermore, "auto-Socratic elaboration" implements a demand-driven inference strategy, triggering additional reasoning only when a specific query requires it.

3. Evaluation and Results

The system was evaluated using three benchmarks: the Shared Domain Ontology (SDO), a real-world planning ontology containing approximately 1,300 definitions, and two synthetic knowledge bases from the 1992 DFKI benchmark.

The PC classifier was compared to Loom, a leading classifier of the era. As shown in Table 1, the PC classifier was approximately twice as slow as Loom across the test sets. However, this performance trade-off granted significantly higher expressive power; the PC classifier could successfully prove complex subsumptions—such as identifying relative rankings like "Third-Fastest-Ship"—that were impossible to represent in Loom or other contemporary DL systems.

Table 1: Classification times for the PC and Loom classifiers across SDO and synthetic benchmarks.

4. Conclusion

The PC classifier demonstrates that high-level reasoning over the full predicate calculus can be optimized into a process akin to compiler optimization. By accepting potential incompleteness in exchange for near-unlimited expressivity, the system provides a more flexible tool for knowledge representation. Future work will focus on refining elaboration rules to further optimize the balance between inference depth and processing speed.

Summary updated

BibTeX
@inproceedings{macgregor1994description,
  author = {Robert M. MacGregor},
  title = {{A Description Classifier for the Predicate Calculus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure