Deriving Provably Correct Explanations for Decision Trees: The Impact of Domain Theories

Gilles Audemard, Jean-Marie Lagniez, Pierre Marquis, Nicolas SzczepanskiIJCAI 2024

Introduction

Decision trees are frequently cited as the gold standard for "intrinsically interpretable" machine learning models. Their hierarchical structure allows users to trace a path from root to leaf to understand a specific prediction. However, this simplicity often relies on a hidden assumption: that the features used in the tree are logically independent. In real-world applications, features are often deeply linked—for instance, categorical variables are mutually exclusive, and numerical thresholds are ordered. This paper investigates how these logical dependencies, formalized as "Domain Theories" ($\Sigma$), fundamentally alter the computational complexity of explaining decision tree outputs.

The Challenge of Logical Dependencies

In eXplainable AI (XAI), we typically seek two types of explanations:

  1. Abductive Explanations (AXp): "Why did the model classify this instance as X?"
  2. Contrastive Explanations (CXp): "Why didn't the model classify this instance as Y?"

Standard approaches find these by examining paths in the tree. However, if a tree contains conditions like Age > 40 and Age > 30, these are not independent. Ignoring these relationships leads to explanations that are either redundant or suggest impossible scenarios.

Example of a decision tree with logically dependent features (e.g., $A_1 \ge 40$ implies $A_1 \ge 30$).

The authors define a constrained decision-function as a pair $(f, \Sigma)$, where $f$ is the decision tree and $\Sigma$ is the domain theory. The core question is how the inclusion of $\Sigma$ impacts the difficulty of finding provably correct explanations.

Methodology: Mapping the Complexity

The researchers performed a rigorous theoretical analysis across eight explanation queries, ranging from finding a single subset-minimal explanation to enumerating all minimum-size explanations. They tested these against five classes of domain theories:

  • Valid: No constraints (the baseline "standard" case).
  • Any $\Sigma$: General propositional logic.
  • Tractable $\Sigma$: Theories where logical entailment is polynomial-time.
  • Horn $\Sigma$: Often used for hierarchical attributes.
  • Krom $\Sigma$: Binary clauses, common for numerical ranges and categorical data.

The Complexity Landscape

The study reveals a significant "complexity gap." While decision trees are easy to explain when features are independent, adding a domain theory often shifts the problem from polynomial time (P) to NP-hard.

Complexity map for deriving abductive and contrastive explanations under various domain theories ($\Sigma$).

Key findings from the complexity map include:

  • Abductive Asymmetry: Finding a single subset-minimal abductive explanation remains tractable (in P) if the domain theory itself is tractable. However, finding the absolute smallest (minimum-size) explanation is almost always NP-hard.
  • Contrastive Difficulty: Contrastive explanations are much more sensitive to domain theories. Finding even one subset-minimal contrastive explanation becomes NP-hard for general theories.
  • The Krom "Safe Haven": Krom theories—which cover most common numerical and ordinal constraints—preserve the tractability of many explanation tasks, making them a vital tool for practical XAI.

Practical Implications and Conclusion

This research highlights that the "interpretability" of decision trees is conditional. Developers must account for the logical structure of their data to provide meaningful explanations. The identification of Krom theories as a tractable middle ground offers a path forward for building efficient, provably correct XAI tools. Future work will look toward extending these results to tree ensembles like Random Forests and exploring knowledge compilation to simplify complex domain theories into tractable forms.

Summary updated

BibTeX
@inproceedings{audemard2024deriving,
  author = {Gilles Audemard and Jean-Marie Lagniez and Pierre Marquis and Nicolas Szczepanski},
  title = {{Deriving Provably Correct Explanations for Decision Trees: The Impact of Domain Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}

Loading related content...

Figure