A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams

Hélène Fargier, Pierre Marquis, Alexandre Niveau, Nicolas SchmidtAAAI 2014 · DOI

In many AI applications—ranging from configuration problems (finding the cheapest car) to medical diagnosis (finding the most probable disease)—we work with functions that map variables to non-negative real numbers, such as costs, probabilities, or utilities. While standard models like Bayesian networks or Valued Constraint Satisfaction Problems (VCSPs) are powerful for modeling, querying them is often NP-hard. To achieve guaranteed response times, researchers use Knowledge Compilation: translating these "hard" models into a more tractable representation before queries begin.

This paper, presented at AAAI 2014, provides a rigorous theoretical framework for understanding these representations. The authors extend the famous "Knowledge Compilation Map" from Boolean logic to real-valued functions, analyzing the trade-offs between succinctness and computational tractability for various Valued Decision Diagrams (VDDs).

Valued Decision Diagram Languages

The authors perform a formal complexity analysis on four major VDD languages:

  1. ADD (Algebraic Decision Diagrams): The most basic form, where values are stored only at the leaf nodes.
  2. SLDD+ and SLDD$\times$ (Semiring-labeled): These diagrams place values on the edges, which are then aggregated via addition or multiplication along a path.
  3. AADD (Affine Algebraic Decision Diagrams): A highly succinct version that uses edge weights and offsets to maximize structure sharing.

The Query Map

The first major contribution is a systematic comparison of which VDD languages can handle specific queries (information retrieval without changing the model) in polynomial time.

Table 1: Tractability of queries for various VDD languages.

One of the most important findings is that optimization (finding the max or min assignment, denoted as OPT) is tractable across all these languages. Because VDDs are directed acyclic graphs (DAGs), finding the best value is essentially a shortest or longest path problem, which is computationally efficient.

However, there is a significant hurdle regarding "Exact Cuts." While it is easy to find assignments greater than a threshold (VA), finding assignments exactly equal to a specific value is NP-hard for edge-labeled versions like SLDD and AADD. This is because the edge labels act like a "subset sum" problem, a classic hard problem in computer science.

The Transformation Map

The authors also analyzed transformations, which involve creating a new model from an old one (e.g., marginalizing out a variable).

Table 2: Tractability of transformations for various VDD languages.

As shown in Table 2, ADD is the most versatile language, satisfying almost every transformation. In contrast, more succinct languages like AADD and SLDD are specialized; they are excellent for optimization and conditioning but fail on many "combination" transformations. Notably, the authors prove that the "apply" algorithm (used to mathematically combine two diagrams) is not polynomial-time for AADD, limiting its use in incremental model building.

The Succinctness-Tractability Trade-off

A central theme of the research is the "Succinctness Tax." AADD is significantly more succinct than ADD, meaning it can represent the same complex function in a much smaller file size. However, this compactness comes at the cost of tractability. The authors demonstrate that AADD is not "closed" under many common operations—combining two AADDs can result in a new diagram that is exponentially larger than the originals.

Conclusion and Future Work

This paper fills a critical gap in knowledge compilation research by identifying the strengths and weaknesses of real-valued diagrams. While ADD remains the most robust for general-purpose manipulation, AADD and SLDD offer powerful alternatives for optimization-heavy tasks where memory is a constraint.

Several open questions remain, including whether AADD satisfies "sentential entailment" (quickly deciding if one function always dominates another) and whether AADD and SLDD+ can support multiplicative marginalization ($\times$-Marg). Future research may also explore non-ordered decision diagrams, which could offer even greater succinctness at the potential cost of further complexity.

Summary updated

BibTeX
@inproceedings{fargier2014knowledge,
  author = {Hélène Fargier and Pierre Marquis and Alexandre Niveau and Nicolas Schmidt},
  title = {{A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8853},
}
Figure