Compilation for Critically Constrained Knowledge Bases

AAAI 1996

TL;DR

This paper introduces a novel hybrid approach to knowledge compilation for propositional logic, significantly speeding up reasoning for "critically constrained" knowledge bases. By combining an exact compilation method based on the Davis-Putnam procedure with a fallback approximate method, the authors achieve an order of magnitude improvement in query answering speed and compilation efficiency compared to existing techniques.

What Problem Does This Paper Address?

Reasoning with propositional knowledge bases (KBs), especially those expressed in conjunctive normal form (CNF), is often computationally expensive, falling into the co-NP-complete complexity class. Knowledge compilation (KC) aims to address this by transforming a KB into a "compiled" form that allows for faster query answering. However, existing KC methods are either approximate (not always providing the correct answer) or exact but can be prohibitively slow for complex KBs. This paper focuses on a specific class of KBs called "critically constrained" Random 3SAT instances. These KBs are "on the edge" of unsatisfiability, meaning adding a few more clauses would likely make them inconsistent. For these particular KBs, answering queries with the uncompiled form is hard, but with a good compiled form, it becomes easy. The challenge is to efficiently compile these critically constrained KBs without incurring excessive computational cost.

Methods

The paper proposes two main KC approaches:

  1. DP-based Exact KC: This method leverages a modified version of the "Davis-Putnam" (DP) proof procedure. Instead of just determining satisfiability, the modified DP procedure (called DPPI) is used to generate an irredundant prime implicant cover for the input KB. This cover, a disjunctive normal form (DNF), serves as an exact compiled representation (Fc) that allows for tractable propositional reasoning.
  2. Bootstrapped Approximate KC: This is a hybrid approach designed to handle KBs that are too complex for exact compilation within resource limits. It first attempts exact compilation using DPPI. If DPPI hits a resource limit (time or memory), the system falls back to an aggressive approximate KC method. This fallback method uses the partial results from the truncated DPPI run as a lower bound (Fib) to accelerate the computation of an upper bound (Fub). This "bootstrapping" allows the approximate compilation to be more efficient by leveraging the information already gathered.

The paper also introduces a "brute-force" approximate KC method as a baseline for comparison. This method generates upper bounds by checking each literal for its presence in a unit implicate.

Datasets

The primary benchmark used in this paper is critically constrained Random 3SAT instances. These instances are parameterized by the number of variables (n) and the number of clauses (m). The paper specifically focuses on instances where the ratio of clauses to variables is around 4.3, which is known to be the "critical window" for Random 3SAT where satisfiability is hardest. The experiments were conducted with KBs of varying sizes, specifically for n = 75, 100, 150, and 200 variables.

Key Insights and Ideas

  • "Critically constrained" KBs are the sweet spot for KC: These KBs are hard to reason with directly but can be compiled efficiently, leading to significant speedups.
  • Leveraging DP for Implicant Generation: The Davis-Putnam procedure, traditionally used for satisfiability, can be adapted to generate prime implicants, forming the basis for exact knowledge compilation.
  • Hybrid Approach is Key: For KBs that are too large for exact compilation, a hybrid strategy that combines exact and approximate methods, using the partial results of the exact method to boost the approximate one, is highly effective.
  • Bootstrapping for Efficiency: Using a partially compiled exact representation as a lower bound to accelerate the computation of an approximate upper bound is a powerful technique.
  • Approximate KC can be made more efficient: The brute-force baseline is improved upon by the bootstrapped approach, which uses more sophisticated techniques to derive the approximate bounds.

Key Results

The paper demonstrates significant performance improvements:

  • DPPI (Exact KC): For easy-to-compile critically constrained KBs, DPPI achieved compilation overhead savings of about 50 times and increased average query speed by 2-3 orders of magnitude compared to the brute-force approach.
  • Bootstrapped KC (Hybrid): This approach handles all critically constrained Random 3SAT KBs and achieves average savings of an order of magnitude in both compilation time and query speed compared to the brute-force method.
  • Comparative Evaluation: When compared to Kautz and Selman's (1994) work, Bootstrapped KC showed improvements in query time ratio (α) and break-even point (β) by factors of 12.4 and 171, respectively, for n=75. DPPI on the "skimmed-off" easy queries showed even larger improvements.

Limitations and Future Work

  • Resource Limits: The effectiveness of the bootstrapped approach is dependent on the allocated resources for the initial DPPI phase. If DPPI is severely limited, the benefits might be reduced.
  • General KBs: The paper focuses specifically on "critically constrained" Random 3SAT KBs. The performance on other types of KBs, especially those with many unconstrained variables, is not explicitly detailed.
  • Future Work: The authors suggest that recognizing "candidate subsets" of variables within larger KBs that are critically constrained could lead to more targeted and efficient compilation. They also mention the potential for KC in dynamic knowledge recompilation scenarios where KBs are frequently modified.

Summary updated

BibTeX
@inproceedings{1996compilation,
  title = {{Compilation for Critically Constrained Knowledge Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure