Relating the Structure of a Problem and Its Explanation

Eugene C. FreuderAAAI 2019 · DOI

Introduction

As AI becomes more integrated into daily life, the demand for explainability (XAI) grows. In the world of Constraint Satisfaction Problems (CSPs)—tasks like scheduling or map coloring—explaining a success is straightforward: one simply presents the solution. However, explaining failure (why a problem is unsolvable) is notoriously difficult. Traditional approaches usually focus on finding "minimal" sets of unsatisfiable constraints to keep explanations brief. However, this minimalist approach can miss the "big picture." This research explores the deep link between the underlying structure of a CSP and the structure of its explanation, providing a holistic "landscape" of a problem that is both mathematically precise and easily translatable into natural language.

Methodology: The Top-Down Approach

The paper proposes a "top-down" approach to explanation that moves from exhaustive data to compact formulas:

  1. Complete Explanations: Instead of searching for a single reason for failure, the process begins by considering every possible assignment of values to variables and identifying which constraints each assignment violates.
  2. Abstraction: These violations are grouped. For example, if multiple assignments violate only "Constraint A," they are abstracted into a single category of failure.
  3. Formulaic Representation: A compact notation is introduced to describe the "failure landscape." For instance, a formula might indicate that removing any single constraint yields a specific number of solutions.
  4. Natural Language Generation: These formulas are designed to be converted into "stories" for the user, such as: "Removing any one constraint enables two solutions... but to obtain the remaining 9 solutions, you need to remove all constraints."
Figure 1: A 3-node coloring problem used as a benchmark to demonstrate the explanation framework.

To demonstrate this theory, the author utilizes classic benchmarks like the 3-node coloring problem (Figure 1), where nodes must be colored such that no connected nodes share a color, and the 3-Queens problem.

Key Insights and the Failure Landscape

A central finding of this research is the concept of Complementarity. The paper uses power set lattices to visually demonstrate how the "explanation structure" shifts when a problem is modified. For example, changing a "not equals" constraint to an "equals" constraint often results in an explanation that is the "complement" of the original within the lattice of possible constraint violations.

Figure 2: Power set lattice visualizing the relationship between the explanation structures of an original and a modified problem.

Other key ideas include:

  • The "Landscape" Story: An explanation acts as a map, telling the user exactly how much they need to "give up" (relax constraints) to reach a solution.
  • Symmetry as a Tool: Problem symmetries are reflected in the explanation formulas, allowing for massive compression of the explanation without losing information.
  • The Good News / Bad News Conjecture: The author posits a trade-off: the harder a problem is to solve computationally, the easier it might be to find an "almost-solution" (an instantiation that violates very few constraints).

Results and Human-Centric Utility

The method demonstrates impressive compactness. For the 3-Queens problem, which has 27 possible instantiations, the entire failure landscape was reduced to a single short formula and a four-sentence English paragraph. This framework allows for "what-if" queries, enabling users to ask how many more solutions they might gain by allowing a specific number of constraint violations.

Limitations and Future Work

The primary limitation is scalability; listing all possible assignments is computationally expensive for massive real-world problems. Future directions include using machine learning to predict explanation structures from problem structures or using sampling algorithms to approximate the landscape without exhaustive search. The author also calls for a formal "explanation taxonomy" to classify different types of problem landscapes.

Summary updated

BibTeX
@inproceedings{freuder2019relating,
  author = {Eugene C. Freuder},
  title = {{Relating the Structure of a Problem and Its Explanation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019765},
}

Loading related content...

Figure