Knowledge Compilation using Horn Approximations

Bart Selman, Henry A. KautzAAAI 1991 · OpenReview

Abstract

We present a new approach to developing fast and efficient knowledge representation systems. Previous approaches to the problem of tractable inference have used restricted languages or incomplete inference mechanisms, which often suffer from a lack of expressive power or a lack of formal characterization. To overcome these disadvantages, we introduce a knowledge compilation method. We allow the user to enter statements in a general, unrestricted representation language, which the system compiles into a restricted language that allows for efficient inference. Since an exact translation into a tractable form is often impossible, the system searches for the best approximation of the original information. We describe how these approximations can be used to speed up inference without sacrificing correctness or completeness.

1. Introduction: The Tractability-Expressiveness Tradeoff

In the field of Artificial Intelligence, researchers face a classic dilemma: the tradeoff between the expressiveness of a representation language and the efficiency of the reasoning it supports. General propositional logic is highly expressive but makes answering even simple queries an NP-hard problem. Conversely, restricted languages like Horn clauses—logical rules where a set of conditions implies at most one conclusion—allow for linear-time inference but cannot express basic disjunctive concepts (e.g., "A or B").

Historically, systems have either forced users into restricted languages or used "incomplete" reasoning that provides no formal guarantees. This paper proposes a middle ground called Knowledge Compilation. Instead of restricting the input, we allow the user to use general logic and then "compile" that knowledge into a tractable Horn format for faster query answering.

2. The Mechanics of Horn Approximations

Because a general logical theory $\Sigma$ cannot always be perfectly translated into Horn clauses, we approximate it using two bounds that "sandwich" the original theory:

  1. Greatest Horn Lower-bound (GLB): A Horn theory that is logically stronger than the original (it has fewer models). If the GLB does not imply a query, then the original theory definitely does not either.
  2. Least Horn Upper-bound (LUB): A Horn theory that is logically weaker than the original (it has more models). If the LUB implies a query, then the original theory definitely does too.

It is important to note that while a theory may have multiple GLBs, the LUB is unique up to logical equivalence. In terms of logical strength, the "lower" bound is more restrictive, while the "upper" bound is more permissive.

3. The Inference Strategy

This compilation enables a highly efficient query-answering strategy. When the system is asked whether $\Sigma \models \alpha$:

  • Step 1: Check the LUB. If $\text{LUB} \models \alpha$, return "Yes."
  • Step 2: Check the GLB. If $\text{GLB} \not\models \alpha$, return "No."
  • Step 3: If the query falls in the "gray area" between the bounds, the system falls back to the original, slower theory $\Sigma$.

Because Horn inference is linear in the size of the theory, the first two steps provide near-instantaneous answers for many queries. The heavy computational cost of generating these approximations is an offline "compilation" cost, which is amortized over thousands of future queries.

4. Anytime Algorithms

We provide "anytime" algorithms for generating these approximations, meaning they can be interrupted at any point to provide a valid (though perhaps less tight) bound.

  • The GLB Algorithm searches through "Horn-strengthenings" of the original clauses to find the most general Horn theory that still implies the original.
  • The LUB Algorithm uses a modified version of resolution to systematically generate "Horn prime implicates," the strongest Horn clauses implied by the theory.

5. Complexity and Limitations

While this method offers significant speedups, it faces challenges regarding the size of the compiled knowledge. The GLB is guaranteed to be no longer than the original theory, but the LUB can, in the worst case, be exponentially larger. If the LUB grows too large, the benefits of linear-time inference may be lost.

Furthermore, while this paper focuses on propositional logic, extending these techniques to First-Order Logic introduces significant complexity, as inference becomes undecidable. However, the general framework of using anytime approximations remains a promising path for scaling complex reasoning systems.

6. Conclusion

Knowledge compilation via Horn approximations provides a formal way to bridge the gap between expressive logic and efficient reasoning. By shifting the computational burden to an offline compilation phase and using a "sandwich" of bounds, we can achieve rapid inference while maintaining the ability to provide sound and complete answers when necessary.

Summary updated

Abstract

We present a new approach to developing fast and efficient knowledge representation systems. Previous approaches to the problem of tractable inference have used restricted languages or incomplete inference mechanisms -- problems include lack of expressive power, lack of inferential power, and/or lack of a formal characterization of what can and cannot be inferred. To overcome these disadvantages, we introduce a knowledge compilation method. We allow the user to enter statements in a general, unrestricted representation language, which the system compiles into a restricted language that allows for efficient inference. Since an exact translation into a tractable form is often impossible, the system searches for the best approximation of the original information. We will describe how the approximation can be used to speed up inference without giving up correctness or completeness. We illustrate our method by studying the approximation of logical theories by Horn theories. Following the formal definition of Horn approximation, we present "anytime" algorithms for generating such approximations. We subsequently discuss extensions to other useful classes of approximations.
BibTeX
@inproceedings{selman1991knowledge,
  author = {Bart Selman and Henry A. Kautz},
  title = {{Knowledge Compilation using Horn Approximations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
  url = {https://openreview.net/forum?id=rJERbRldZS},
}
Figure