Incremental Recompilation of Knowledge

Goran Gogic, Christos H. Papadimitriou, Martha Sideri

Abstract

Approximating a general formula from above and below by Horn formulas (its Horn envelope and Horn core, respectively) was proposed by Selman and Kautz as a form of "knowledge compilation" to support rapid approximate reasoning. However, this scheme is traditionally static and lacks support for updates. Furthermore, existing theory update schemes are often plagued by complexity-theoretic impediments. This paper introduces "incremental recompilation," a scheme that combines Horn approximation with model-based updates. By maintaining an upper and lower Horn approximation and re-approximating after each update, the authors demonstrate that updates can be performed efficiently—specifically in linear time when the update is a single clause.

Introduction

A central challenge in Artificial Intelligence is the "vividness" of knowledge bases: the ability to reason efficiently while maintaining an accurate representation of a changing world. While general propositional reasoning is NP-hard, Horn formulas—clauses with at most one positive literal—allow for linear-time inference. To leverage this, researchers use knowledge compilation to approximate complex theories with Horn bounds.

However, two significant hurdles have historically limited this approach. First, compilation is typically static; any change to the underlying knowledge requires a costly total recompilation. Second, even if a knowledge base starts as a Horn formula, standard updates often result in non-Horn structures, destroying the computational benefits. This paper addresses these issues by proposing a dynamic, inductive framework for knowledge maintenance.

The Incremental Recompilation Framework

The authors propose representing a set of formulas $\Sigma$ through two Horn approximations:

  1. The Horn Envelope ($\overline{\Gamma}$): The strongest Horn formula implied by $\Sigma$ (an upper bound).
  2. The Horn Core ($\underline{\Gamma}$): The weakest Horn formula that implies $\Sigma$ (a lower bound).

The core of the "Incremental Recompilation" scheme is its inductive nature. When new information $\phi$ arrives, the system performs a model-based update on the current approximations and then immediately "re-approximates" the result back into the Horn domain. This ensures that the knowledge base remains in a format optimized for reasoning at every step of its evolution.

Computational Tractability

The primary contribution of this work is identifying a "tractability window" for these updates. While finding Horn envelopes is generally difficult (TRANSVERSAL-hard), the authors prove that the complexity is significantly reduced under specific conditions.

The Single-Clause Advantage

The paper demonstrates that if the update $\phi$ is a single clause, the new Horn envelope and Horn core can be computed in linear time (Theorem 4). This result is pivotal, as it suggests that incremental, piece-by-piece updates are computationally feasible, even if batch updates are not.

Hardness Results

To delineate the boundaries of this tractability, the authors provide several hardness proofs:

  • Batch Updates: Updating with a conjunction of negative clauses is shown to be NP-hard (Theorem 3).
  • Characteristic Models: The paper explores using characteristic models (an alternative representation for Horn formulas) but finds that intersecting these sets remains NP-hard (Theorem 6).
  • General Compilation: The general problem of enumerating the clauses of a Horn envelope is linked to the "transversal problem" for hypergraphs, highlighting the inherent difficulty of the non-incremental approach.

Semantic Considerations

The authors utilize Winslett’s model-based update formalism, which is particularly effective for this scheme because it is "additive." This property ensures that the lower bound continues to imply the upper bound throughout successive updates.

However, there is a "semantic price" to this efficiency. Because the system approximates at every step, the gap between the Horn core and the Horn envelope may widen over time. This "approximation drift" means the knowledge base might become less precise after a long sequence of updates, potentially requiring a full (non-incremental) recompilation to tighten the bounds eventually.

Conclusion

Incremental recompilation offers a path forward for dynamic AI systems that require both fast reasoning and the ability to incorporate new information. By restricting updates to single clauses, the authors transform an NP-hard problem into a linear-time operation. While the theoretical foundations are robust, future work remains to empirically measure the rate of "approximation drift" in practical applications, such as robotics or automated planning, to determine how often a full re-synchronization of the knowledge base is necessary.

Summary updated

Abstract

Approximating a general formula from above and below by Horn formulas (its Horn envelope and Horn core, respectively) was proposed by Selman and Kautz (1991, 1996) as a form of ``knowledge compilation,'' supporting rapid approximate reasoning; on the negative side, this scheme is static in that it supports no updates, and has certain complexity drawbacks pointed out by Kavvadias, Papadimitriou and Sideri (1993). On the other hand, the many frameworks and schemes proposed in the literature for theory update and revision are plagued by serious complexity-theoretic impediments, even in the Horn case, as was pointed out by Eiter and Gottlob (1992), and is further demonstrated in the present paper. More fundamentally, these schemes are not inductive, in that they may lose in a single update any positive properties of the represented sets of formulas (small size, Horn structure, etc.). In this paper we propose a new scheme, incremental recompilation, which combines Horn approximation and model-based updates; this scheme is inductive and very efficient, free of the problems facing its constituents. A set of formulas is represented by an upper and lower Horn approximation. To update, we replace the upper Horn formula by the Horn envelope of its minimum-change update, and similarly the lower one by the Horn core of its update; the key fact which enables this scheme is that Horn envelopes and cores are easy to compute when the underlying formula is the result of a minimum-change update of a Horn formula by a clause. We conjecture that efficient algorithms are possible for more complex updates.
BibTeX
@article{gogic1998incremental,
  author = {Goran Gogic and Christos H. Papadimitriou and Martha Sideri},
  title = {{Incremental Recompilation of Knowledge}},
  journal = {J. Artif. Intell. Res.},
  year = {1998},
  url = {https://openreview.net/forum?id=p_TFaEchHB6},
}
Figure