Compilation of propositional weighted bases

Adnan Darwiche, Pierre Marquis

Abstract

This paper investigates the use of knowledge compilation to improve the efficiency of reasoning within weighted propositional bases. While many compilation formats fail to reduce the $\Delta^p_2$-completeness of inference, the authors demonstrate that Decomposable Negation Normal Form (DNNF) enables polynomial-time clausal inference and efficient enumeration of preferred worlds.

Introduction: The Complexity of Weighted Bases

In many AI applications, such as diagnosis or preference modeling, we deal with inconsistent information or soft constraints. Penalty logic provides a formal way to handle this by assigning weights to propositional formulas. If a formula is violated, a "penalty" equal to its weight is incurred. The objective is to identify "preferred worlds"—interpretations that minimize the total penalty.

However, inference in weighted bases is computationally daunting, generally classified as $\Delta^p_2$-complete. This complexity level suggests that the problem is significantly harder than standard SAT, typically requiring a polynomial number of calls to an NP-solver. This has historically limited the use of weighted bases in large-scale industrial applications.

Table 1: Mapping of worlds to their total penalty (K_W), illustrating the search for preferred worlds with minimal cost.

The Compilation Framework

The authors propose a three-step pipeline to compile weighted bases into a format that allows for faster online querying:

  1. Normalization: Transforming the weighted base into a form where weights are attached to simple indicator variables ($holds_i$) rather than complex formulas. This preserves the original weight function while simplifying the structure.
  2. Hard Constraint Consolidation: Combining all formulas with infinite weight (constraints that must be satisfied) into a single propositional formula.
  3. Targeted Compilation: Compiling this consolidated hard constraint into a specific target language, such as Prime Implicates or DNNF.

The Magic of Decomposability

A central finding of the paper is that not all compilation targets are created equal. While formats like Blake (prime implicates) or Horn covers fail to lower the complexity of inference, Decomposable Negation Normal Form (DNNF) succeeds.

The reason lies in the "decomposability" property: in a DNNF graph, the children of any "AND" node do not share variables. This allows for a dynamic programming-like approach where minimal weights and preferred models can be computed by traversing the graph once in polynomial time.

Figure 4: Weight propagation through a DNNF graph. Bold numbers represent the computed minimum penalty for each sub-formula.

Key Results and Complexity Bottlenecks

  • Tractability Found: For weighted bases compiled into DNNF, the clausal inference problem (determining if a conclusion holds in all preferred worlds) is in P (polynomial time).
  • Efficient Enumeration: The set of all preferred models can be generated in output polynomial time from a smooth DNNF.
  • Complexity Bottlenecks: The paper confirms that for most other popular compilation targets (Blake, Horn, renamable Horn), inference remains just as hard as the uncompiled version, warning against the assumption that classical compilation benefits always extend to weighted logic.
  • Diagnostic Application: The authors provide a concrete algorithm for model-based diagnosis. Once a system description is compiled into DNNF, finding the most likely cause of a failure becomes efficient, even as observations change.

Conclusion and Future Work

While knowledge compilation into DNNF offers a path to tractability, it comes with a "space tax," as the compiled graph can be exponentially larger than the original formula. Future research will focus on applying these theoretical results to real-world industrial diagnosis systems to evaluate the practical performance gains of this polynomial-time approach.

Summary updated

BibTeX
@inproceedings{darwiche2002compilation,
  author = {Adnan Darwiche and Pierre Marquis},
  title = {{Compilation of propositional weighted bases}},
  booktitle = {NMR},
  year = {2002},
}
Figure