TL;DR
Decision trees are often touted as inherently interpretable, but this paper reveals a significant issue: "explanation redundancy." This means that the paths used to explain a prediction can contain many irrelevant features, making them unnecessarily complex. The authors demonstrate this redundancy is widespread, even in optimal decision trees, and propose that future work should focus on learning trees that produce simpler explanations.
What Problem Does This Paper Address?
Machine learning models are increasingly used in high-stakes applications, making interpretability crucial. Decision trees (DTs) have long been considered a prime example of an interpretable model, where the "explanation" for a prediction is simply the path taken through the tree to reach a leaf node. However, this paper challenges this assumption by highlighting "explanation redundancy." This redundancy means that a prediction path might include features that are not actually necessary to arrive at that specific prediction. In essence, the explanation provided by a DT path can be much longer and more complex than it needs to be, undermining the very interpretability that makes DTs attractive. The authors aim to quantify and demonstrate this redundancy, showing it's not an edge case but a common phenomenon.
Methods
The paper builds upon formal definitions of explanations, specifically abductive explanations (AXp) and contrastive explanations (CXp).
- Abductive Explanations (AXp): A minimal set of features that, if assigned specific values, guarantee a particular prediction.
- Contrastive Explanations (CXp): A minimal set of features whose values, if changed, would lead to a different prediction.
The core of their work involves analyzing DTs to identify features within a prediction path that are "redundant." A feature is considered redundant if its value in the path is not essential for reaching the predicted outcome. They prove theoretically that the number of redundant features can grow with the total number of features, even in optimal DTs. They also show that DTs without explanation redundancy are a very restricted class, typically representing "generalized decision functions" (GDFs).
The paper also discusses algorithms for computing AXp's and CXp's, often leveraging techniques like propositional Horn formulas and partial MaxSAT encodings.
Datasets
The paper does not introduce new datasets. Instead, it relies on:
- Publicly available decision trees: These are DTs found in numerous publications and textbooks since the early 1980s.
- Four well-known datasets: Used for evaluating DTs trained with different tools. These include
monk1,tic-tac-toe,compas, andmonk2. - A running example DT: A decision tree from [Lelis et al., 2020] used to diagnose Meningococcal Disease (MD).
Key Insights and Ideas
- The "A+" for interpretability is misleading: The common belief that DTs are inherently and fully interpretable is a misconception.
- Redundancy is the norm, not the exception: Most deployed and learned DTs exhibit explanation redundancy. This means the paths are often longer and more complex than necessary.
- Optimal DTs are not immune: Even decision trees optimized for size or accuracy can suffer from significant explanation redundancy.
- Restricted class for non-redundant DTs: DTs that don't have explanation redundancy are rare and correspond to a very specific type of classifier (GDFs).
- Practical implications for human understanding: Shorter, more concise explanations are easier for humans to grasp. Redundant features obscure the true drivers of a prediction.
Key Results
- Theoretical proof of redundancy: The number of redundant features in a DT path can grow linearly with the total number of features.
- Experimental confirmation: A vast majority of DTs, including those from seminal papers and textbooks, show explanation redundancy.
- Ubiquitous redundancy in learned DTs: DTs learned by common tools (like those for optimal DTs) consistently exhibit redundancy, which can be substantial.
- High percentage of redundant paths: Figure 2 shows that for DTs trained with specific tools (ITI and IAI), the percentage of redundant paths can reach close to 100%.
- Significant redundant literals: Table 1 indicates that for various datasets and training tools, a high percentage of paths can be explanation-redundant, with average redundancy per path also being considerable. For example, on the
compasdataset, OSDT yields 69% redundant paths.
Limitations and Future Work
- Extended Abstract: This paper is an extended abstract of a more comprehensive work [Izza et al., 2022].
- Automated Analysis Difficulty: The authors note they were unable to obtain a specific concrete DT in a format suitable for automated analysis for one of their examples.
- Future Research Directions:
- Focus on learning DTs that produce simple explanations, rather than solely optimizing for metrics like tree depth or size.
- Investigate how to learn decision trees that inherently represent functions offering simple explanations.
Summary updated