Forming Concepts for Fast Inference

Henry A. Kautz, Bart SelmanAAAI 1992 · OpenReview

Abstract

Knowledge compilation speeds inference by creating tractable approximations of a knowledge base, but this advantage is lost if the approximations are too large. We show how learning concept generalizations can allow for a more compact representation of the tractable theory. We also give a general induction rule for generating such concept generalizations. Finally, we prove that unless NP ⊆ non-uniform P, not all theories have small Horn least-upper-bound approximations.

Introduction

In artificial intelligence, a fundamental tension exists between the expressiveness of a knowledge representation and the efficiency of reasoning with it. While general propositional logic allows for complex world models, determining entailment is NP-hard. Knowledge compilation addresses this by pre-processing a knowledge base into a tractable form, such as Horn clauses, where inference can be performed in linear time. However, the "best" Horn approximation—the Least Upper Bound (LUB)—often suffers from exponential size explosion, potentially negating the speed benefits of the tractable representation.

Methodology: Theory Approximation and Concept Induction

The authors propose a dual-pronged approach: Theory Approximation and Concept Induction. They define two bounds for a theory: a Greatest Lower Bound (GLB), which is always compact but incomplete, and a Least Upper Bound (LUB), which is complete for Horn queries but prone to massive size.

To mitigate the size explosion of the LUB, the authors introduce a method for "inducing" new concepts. When multiple rules share a common set of consequences, the system creates a new propositional variable—a "defined concept"—to represent that shared pattern. This process effectively compresses the representation by replacing redundant rule sets with a single intermediate variable.

Example of clausal definitions for induced concepts like CompSciBuff and PhilBuff.

As shown in the figure above, concepts like CompSciBuff or PhilBuff are defined through sets of clauses. For instance, CompSciBuff is established as equivalent to the disjunction of CompSci and ReadsMcCarthy. By introducing these intermediate terms, the theory can be expressed more compactly without losing its logical properties.

Theoretical Complexity and Key Results

The paper provides a rigorous formal analysis of these representations using circuit complexity theory.

  • Theorem 1 (The Explosion): It is proven that for a theory of size $n$, the smallest Horn representation of its LUB can be $O(2^n)$.
  • Theorem 3 (The Rescue): The authors demonstrate that through their compaction technique (inducing new concepts), an exponentially large LUB can be reduced to a polynomial size $O(n)$ relative to the original theory.
  • Theorem 5 (The Hard Limit): They establish that the existence of a universal, efficient representation for LUBs is equivalent to the major open question of whether $NP \subseteq \text{non-uniform } P$. This implies that some knowledge is inherently "bulky" if tractability is required.

Key Insights

A central insight of this work is that the exponential blowup in LUBs is often a symptom of a restrictive language. By "inventing" new variables to describe common patterns, the system performs a form of "speed-up learning." Traditionally, concept learning is viewed as a classification task; here, it is presented as a vital tool for an agent to organize internal knowledge for faster reasoning.

Discussion and Future Directions

While the induction rules presented are effective heuristics, they do not constitute a complete algorithm guaranteed to find the absolute minimum representation for any theory. Future research may explore other tractable languages, such as binary clauses, where LUBs are guaranteed to be small ($O(n^2)$). Additionally, integrating these off-line compilation steps into "anytime" reasoning systems could allow agents to improve their efficiency incrementally through experience.

Summary updated

Abstract

Knowledge compilation speeds inference by creating tractable approximations of a knowledge base, but this advantage is lost if the approximations are too large. We show how learning concept generalizations can allow for a more compact representation of the tractable theory. We also give a general induction rule for generating such concept generalizations. Finally, we prove that unless NP ⊆ non-uniform P, not all theories have small Horn least-upper-bound approximations.
BibTeX
@inproceedings{kautz1992forming,
  author = {Henry A. Kautz and Bart Selman},
  title = {{Forming Concepts for Fast Inference}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
  url = {https://openreview.net/forum?id=rJbv-lb_WH},
}
Figure