Incremental Recompilation of Knowledge

Goran Gogic, Christos H. Papadimitriou, Martha SideriAAAI 1994

Introduction

In the field of Artificial Intelligence, a fundamental tension exists between the expressiveness of a knowledge base and the efficiency of reasoning over it. While general propositional logic allows for rich world modeling, answering queries within it is typically NP-complete. To circumvent this, researchers often turn to Knowledge Compilation, where a complex formula is approximated by a simpler one—such as a Horn formula—to enable linear-time reasoning. However, these compiled representations are traditionally static. When the underlying world changes, the entire compilation process must often be restarted from scratch, a task that is computationally prohibitive.

This paper introduces Incremental Recompilation, a novel framework designed to bridge the gap between fast reasoning and dynamic belief revision. By maintaining and updating Horn approximations rather than the original complex formulas, the authors provide a computationally feasible path for handling updates while ensuring that subsequent reasoning remains efficient.

The Challenge of Dynamic Knowledge

The authors identify two primary impediments to maintaining efficient knowledge bases in dynamic environments:

  1. Static Compilation: Current approximation methods are "one-shot." If a new piece of information is added, re-approximating the updated knowledge base is often as hard as the original compilation, failing to leverage the work already performed.
  2. The Counterfactual Problem: Standard methods for theory updates (belief revision) are plagued by complexity-theoretic obstacles. Even simple updates can lead to a "counterfactual problem"—deciding what holds true after a change—that is nearly impossible to solve efficiently. Furthermore, these updates often destroy the "Horn" property of a formula, rendering the knowledge base slow to query.

The Incremental Recompilation Framework

Instead of storing a single, potentially intractable formula $\Gamma$, the proposed framework represents knowledge through two bounding Horn formulas:

  • The Horn Envelope ($\overline{\Gamma}$): A "relaxed" upper bound Horn formula that is logically implied by the original knowledge.
  • The Horn Core ($\underline{\Gamma}$): A "strict" lower bound Horn formula that logically implies the original knowledge.

When new information (a clause $\phi$) is received, the system does not attempt to update the original complex formula. Instead, it performs a model-based update directly on the approximations. The process follows a two-step inductive cycle:

  1. Apply a model-based update to the current Horn envelope and core.
  2. Immediately "re-approximate" the resulting formula back into a new Horn envelope and core.

The authors highlight that Winslett’s approach to model-based updates is particularly effective here, as it ensures the upper bound continues to logically imply the lower bound after an update, maintaining the integrity of the approximation interval.

Complexity and Tractability

The core technical contribution of this work is the discovery of a "sweet spot" in logic complexity. While generating a Horn envelope from scratch is TRANSVERSAL-hard (suggesting that no efficient output-polynomial algorithm exists), the authors prove that updating an existing Horn approximation is significantly easier.

Specifically, they demonstrate that if the update is restricted to a single Horn clause, the new Horn envelope and core can be computed in linear time relative to the formula size and quadratic time relative to the update clause: $O(|\Gamma| + |\phi|^2)$. This inductive property is crucial; it ensures that the representation remains within the Horn class and does not grow uncontrollably in size over time, preventing system slowdown.

However, this tractability has limits. The paper proves that if updates are allowed to be arbitrary (non-Horn) and of unrestricted length, the problem reverts to being NP-hard. This justifies the focus on restricted update languages to maintain real-time performance.

Conclusion and Future Work

Incremental Recompilation offers a promising solution to the "counterfactual problem" by making theory updates polynomial-time within the approximation framework. By combining the strengths of knowledge compilation and belief revision, the authors provide a pathway for AI systems to operate in changing environments without sacrificing reasoning speed.

Despite these theoretical gains, the authors acknowledge several areas for future research:

  • Approximation Decay: Repeatedly updating and re-approximating may cause the bounds ($\overline{\Gamma}$ and $\underline{\Gamma}$) to drift apart, potentially reducing the quality of the answers over time. Experimental evaluation is needed to quantify this decay.
  • Non-Horn Updates: While Horn updates are efficient, extending these algorithms to broader classes of updates remains an open challenge.
  • Applications: The framework is particularly well-suited for "reasoning about action," where agents must constantly update their internal models based on new observations and actions.

Summary updated

BibTeX
@inproceedings{gogic1994incremental,
  author = {Goran Gogic and Christos H. Papadimitriou and Martha Sideri},
  title = {{Incremental Recompilation of Knowledge}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure