Algorithms for Propositional KB Approximation

AAAI 1998

TL;DR

This paper introduces new algorithms for approximating large propositional knowledge bases (KBs) using renamable Horn logic. The authors present methods for generating "greatest lower bounds" (GLBs) that are more accurate than previous Horn-based approaches, offering a better trade-off between approximation quality and computational feasibility.

What Problem Does This Paper Address?

Knowledge compilation aims to transform complex, intractable knowledge bases (KBs) into simpler, tractable forms for efficient querying. A key technique is approximation using "greatest lower bounds" (GLBs) and "lowest upper bounds" (LUBs). While LUBs can be exponentially large, GLBs are generally smaller but can still be computationally expensive to generate. Specifically, this paper tackles the challenge of efficiently computing Horn GLBs for large KBs and extends this to the more general class of renamable Horn logic, which includes Horn logic as a subset. The goal is to find a tractable representation that is as close as possible to the original KB without being overly complex to compute.

Methods

The paper introduces two main algorithmic contributions:

  • Horn GLB Generation: The core algorithm builds upon the Davis-Putnam (DP) procedure. Instead of directly searching for a Horn GLB of the entire KB, it iteratively strengthens the KB by incorporating implicants. When an implicant is found, the KB is replaced by its "I-strengthening" (a modified version based on the implicant), making the subsequent search more constrained. This approach is designed to handle larger KBs than brute-force methods. For extremely large KBs, a preprocessing step is introduced that uses a local search method to find a model and strengthen the KB before applying the main DP-based algorithm.
  • Renamable Horn GLB (RH-GLB) Generation: This is the paper's primary novel contribution. It leverages the fact that any Horn GLB of a renamed KB (using a "Horn renaming") corresponds to a renamable Horn GLB of the original KB. The authors establish conditions under which considering specific models of the KB as renamings is sufficient. They propose an algorithm that iteratively improves a renamable Horn bound by considering renamings derived from models of the KB. The algorithm uses the previously developed Horn GLB generation procedure on these renamed KBs. A key optimization is introduced to prune the search space by identifying partial interpretations that cannot lead to a better bound.

Datasets

The paper uses two types of benchmarks for evaluation:

  • Random 3-CNF and 4-CNF Formulae: These are randomly generated instances with varying numbers of variables and clauses, used to test the efficiency of the Horn GLB generation algorithms.
  • Asynchronous Circuits Design Benchmarks: These are real-world instances from the DIMACS SAT challenge, used to evaluate both Horn GLB and renamable Horn GLB generation times.

Key Insights and Ideas

  • I-Strengthening for Tractability: The concept of "I-strengthening" is crucial. By replacing a KB with an I-strengthening based on an implicant, the problem of finding a Horn GLB becomes more constrained, making it computationally feasible for larger KBs.
  • Renamable Horn as a Better Approximation: The renamable Horn class, being more general than Horn logic, allows for tighter approximations. This means RH-GLBs can be closer to the original KB (in terms of the number of models) than Horn GLBs.
  • Model-Based Renaming is Sufficient: A significant theoretical result is that to find a renamable Horn GLB, it's sufficient to consider renamings derived from models of the KB. This dramatically reduces the search space compared to considering all possible renamings.
  • "Anytime" Algorithms: Both the Horn GLB and RH-GLB algorithms are "anytime" procedures. This means they can be interrupted at any point and will return a valid, albeit potentially suboptimal, lower bound, making them useful in time-constrained scenarios.

Key Results

  • Efficiency for Large KBs: The proposed algorithms demonstrate the ability to compute Horn GLBs for large KBs (e.g., 1000 variables, 4000 clauses) within reasonable timeframes (seconds to minutes), whereas previous methods were intractable.
  • Tighter Renamable Horn Bounds: Experimental results (Figure 1) show that renamable Horn GLBs approximate the original KB more closely (fewer models) than Horn GLBs, indicating improved approximation quality.
  • Preprocessing for Extreme Cases: The preprocessing step allows for handling extremely large KBs where direct DP-based search would fail.

Limitations and Future Work

  • Computational Complexity of RH-GLB: While the paper provides algorithms and theoretical justifications for RH-GLB generation, the authors acknowledge that the search space for renamable Horn GLBs is still potentially huge. They suggest that further research is needed to investigate the computational complexity of generating these bounds.
  • Experimental Scope: The experimental evaluation primarily focuses on the efficiency of generating lower bounds. While qualitative results on tightness are presented, a more comprehensive comparison with other knowledge compilation techniques would be beneficial.
  • Tractable Covers: The authors mention that their algorithms can be modified to generate more compact tractable covers, suggesting this as a direction for future work.

Summary updated

BibTeX
@inproceedings{1998algorithms,
  title = {{Algorithms for Propositional KB Approximation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}

Loading related content...

Figure