Presented at AAAI-19, this research provides a roadmap for defining "good" explanations in Artificial Intelligence and introduces a specific method for generating these explanations for decision trees. By shifting the focus from how a model works to how a decision could be changed, the authors decouple the quality of an explanation from the complexity of the underlying model.
The Problem: The Illusion of Interpretability
While Explainable AI (XAI) is a rapidly expanding field, there is little consensus on what actually constitutes a high-quality explanation. A common fallacy in the field is that certain models, such as decision trees, are inherently interpretable. However, a decision tree with a depth of 50 or hundreds of leaves is practically unreadable to a human observer.
Furthermore, many existing XAI methods are "model-agnostic," meaning they treat the AI as a black box. While this flexibility is useful, these methods often fail to guarantee critical properties such as soundness (truthfulness to the underlying model) or completeness (covering all conditions under which an explanation holds). The authors aim to bridge the gap between the theoretical properties desired from explanations and the practical algorithms used to generate them.
The Desiderata Framework
A primary contribution of the paper is the synthesis of 11 key "desiderata" (requirements) for explainable systems. These properties serve as a standardized list to systematically compare different XAI approaches. Key requirements include:
- Soundness: Is the explanation actually true to the model's internal logic?
- Parsimony: Is the explanation short and easy for a human to digest?
- Actionability: Does the explanation provide the user with a path to change the outcome?
- Contextfullness: Does it provide the necessary conditions under which the explanation remains valid?
Model-Specific Counterfactuals
To meet these desiderata, the authors propose an algorithm that generates counterfactuals specifically for decision trees. Rather than attempting to explain the entire path of a massive tree, the algorithm focuses on the logic of "what would have to change."
For example, instead of showing a user 20 logical steps that led to a loan denial, a counterfactual explanation might state: "Your loan was denied. Had your income been £10,000 higher, it would have been accepted."
The Algorithmic Approach
The proposed method "opens the box" of the decision tree to ensure soundness and completeness:
- Meta-Feature Mapping: The algorithm treats the logical conditions at each node as "meta-features."
- Distance Matrix: It maps the internal structure of the tree into a leaf-to-leaf counterfactual distance matrix.
- Efficient Search: By searching this pre-calculated matrix, the algorithm can instantly identify the "smallest" change (the nearest leaf with a different classification) required to flip the prediction.
Key Insights and Results
Decoupling Complexity
The most significant insight is that the complexity of an explanation does not need to be tied to the complexity of the model. A counterfactual remains parsimonious and actionable even if the underlying decision tree is massive. This allows developers to use high-capacity models without sacrificing user-facing interpretability.
The Value of Model-Specificity
The authors argue that being model-specific is a feature, not a limitation. By utilizing the internal structure of the decision tree, the algorithm guarantees properties that black-box explainers (like LIME or SHAP) often cannot, specifically regarding the truthfulness of the explanation relative to the model's actual decision boundary.
Regulatory Alignment
The paper highlights that counterfactuals are particularly well-suited for non-experts and align with the "right to explanation" requirements found in regulations like the GDPR. They provide the user with a clear, logical path toward a different outcome.
Limitations and Future Work
While the theoretical framework is robust, the current algorithm is limited to single decision trees and logical models. While the logic may generalize to ensembles, the authors have not yet demonstrated its application to more complex structures like Random Forests or Gradient Boosted Trees, where the search space for counterfactuals is significantly larger.
Additionally, the paper is primarily theoretical. The authors acknowledge that future work must include empirical user studies to determine which "distance functions" (the metrics used to define the "smallest" change) are most intuitive and helpful to real-world users.
Summary updated