On the Compilation of Stratified Belief Bases under Linear and Possibilistic Logic Policies

Salem Benferhat, Safa Yahi, Habiba DriasIJCAI 2007

Abstract

Handling inconsistent information is a fundamental challenge in artificial intelligence. Stratified Belief Bases (SBBs) provide a framework for prioritizing information, yet reasoning within these structures is computationally demanding. This paper presents an efficient knowledge compilation approach that transforms prioritized belief bases into tractable formats like Decomposable Negation Normal Form (DNNF). By introducing a single auxiliary "abnormality" variable per priority level, the proposed method reduces the complexity of online inference from $\Delta_2^P$-complete to polynomial time.

1. Introduction: The Problem of Inconsistency

In real-world AI systems, data is frequently sourced from multiple, potentially conflicting origins. In classical propositional logic, a single contradiction allows for the derivation of any arbitrary conclusion—a principle known as ex falso quodlibet. This makes standard logic unsuitable for robust knowledge representation where inconsistencies are expected.

To address this, researchers utilize Stratified Belief Bases (SBBs). In an SBB, formulas are organized into layers (strata) based on their reliability or priority. While this structure allows for more nuanced reasoning, determining what logically follows from an SBB is computationally expensive, typically falling into the $\Delta_2^P$-complete complexity class. This necessitates many calls to an NP-complete SAT solver, making real-time query answering difficult.

2. Knowledge Compilation and Tractability

The goal of Knowledge Compilation is to shift the heavy lifting of reasoning to an offline preprocessing phase. By transforming a belief base into a "tractable" target language—such as DNNF (Decomposable Negation Normal Form) or OBDDs (Ordered Binary Decision Diagrams)—complex logical queries can be answered in polynomial time during the online phase.

However, compiling prioritized information presents unique challenges. Previous methods often required adding an auxiliary variable for every single formula in the database, significantly increasing the size and complexity of the compiled representation.

3. Methodology: Abnormality Encoding

The authors propose a streamlined encoding technique that bridges the gap between prioritized logic and standard knowledge compilation.

3.1 Stratum-Level Encoding

Instead of formula-level variables, the authors introduce a single "abnormality" variable $A_i$ for each priority level (stratum) $S_i$. Each formula $\phi$ within a stratum is transformed into the disjunction $(\phi \lor A_i)$. This encoding effectively signals that either the formula is true, or the entire priority level is considered "abnormal" and thus ignored to maintain consistency.

3.2 Inference Algorithms

The paper details two primary algorithms for online inference:

  1. Linear Order Policy: This policy evaluates strata sequentially. If a layer introduces an inconsistency, it is skipped, but the system continues to evaluate lower-priority layers to see if they can be safely integrated.
  2. Possibilistic Logic Policy: This policy is more conservative; it stops as soon as a contradiction is encountered, ignoring all subsequent layers of lower certainty.

Both algorithms utilize conditioning, a process where variables (in this case, the $A_i$ variables) are assigned truth values to "filter" the compiled base on-the-fly, isolating the most reliable consistent subset of information.

4. Key Insights and Results

The most significant contribution of this work is the minimal overhead required for compilation. Because the number of strata ($k$) is typically much smaller than the total number of formulas, adding only $k$ variables keeps the compiled base manageable.

4.1 Complexity Reduction

The research demonstrates that once the base is compiled into a tractable format, the inference task moves from $\Delta_2^P$ down to Polynomial time (P). This allows for near-instantaneous query answering in dynamic environments.

4.2 Flexibility

The stratum-based approach allows for "re-partitioning for free." Since variables represent priority levels rather than specific formulas, users can adjust the priority of an entire stratum or swap levels without the need to re-compile the entire knowledge base.

5. Limitations and Future Directions

While efficient, the "one variable per stratum" approach lacks the granularity to change the rank of an individual formula without re-compilation. For applications requiring such fine-grained control, the more expensive "one variable per formula" method remains necessary.

Furthermore, the current framework focuses on "hard" evidence—observations that are 100% certain. Future research aims to extend these results to "soft" or uncertain evidence and to integrate these compilation techniques into propagation algorithms for possibilistic networks, similar to the use of junction trees in Bayesian networks.

Summary updated

BibTeX
@inproceedings{benferhat2007compilation,
  author = {Salem Benferhat and Safa Yahi and Habiba Drias},
  title = {{On the Compilation of Stratified Belief Bases under Linear and Possibilistic Logic Policies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure