Source-linked AI summary
On Explaining Decision Trees
Yacine Izza, Alexey Ignatiev, Joao Marques-Silva
TL;DR
Decision-tree paths are often treated as interpretable, but the paper shows that they can include more literals than a minimal explanation of the prediction. It develops methods to compute and enumerate PI-explanations, and experiments find explanation-redundant paths in trees learned on many datasets.
Problem
Decision trees are widely regarded as interpretable, but the paper investigates whether their paths provide succinct explanations compared with subset-minimal feature-value explanations.
Source: §1 · p. 1, A decision tree · p. 2Method
The paper formulates PI-explanation computation using hitting sets, gives a polynomial-time algorithm for one explanation, and reduces enumeration to minimal hitting-set enumeration.
Source: §1 · p. 2, §4 · pp. 6–7Results
In learned trees, an average of 32.1% of IAI paths and 46.9% of ITI paths are explanation-redundant.
Source: §6 · p. 13Takeaways & Limitations
The experiments show that paths in learned decision trees can be proper supersets of PI-explanations, including in trees that are not redundant.
Source: §3 · p. 5, §6 · p. 13, §7 · p. 13The demonstrated interpretability gap concerns certain function classes and persists even in irreducible decision trees.
Source: §3 · p. 5
Abstract
from arXiv · showhide
Decision trees (DTs) epitomize what have become to be known as interpretable machine learning (ML) models. This is informally motivated by paths in DTs being often much smaller than the total number of features. This paper shows that in some settings DTs can hardly be deemed interpretable, with paths in a DT being arbitrarily larger than a PI-explanation, i.e. a subset-minimal set of feature values that entails the prediction. As a result, the paper proposes a novel model for computing PI-explanations of DTs, which enables computing one PI-explanation in polynomial time. Moreover, it is shown that enumeration of PI-explanations can be reduced to the enumeration of minimal hitting sets. Experimental results were obtained on a wide range of publicly available datasets with well-known DT-learning tools, and confirm that in most cases DTs have paths that are proper supersets of PI-explanations.
1 Introduction
The paper examines whether decision trees are interpretable when explanation size is measured by the feature values needed to justify a prediction. It shows that paths can greatly exceed minimal explanations and proposes methods for computing and enumerating those explanations.
1 Introduction
- A minimal decision tree can have paths with arbitrarily more literals than a constant-size PI-explanation.The difference can grow with the number of features.Source: §1 · pp. 1–2
- Across many datasets, learned trees often contain paths that are proper supersets of PI-explanations, and most paths are redundant on a significant number of datasets.For some trees, redundant paths cover as much as 98% of feature space.Source: §1 · p. 2
- A polynomial-time algorithm computes one PI-explanation, while enumeration is reduced to enumerating minimal hitting sets.The proposed formulation distinguishes explanations restricted to path literals from unrestricted explanations.Source: §1 · p. 2
- The paper evaluates trees learned by established tools on publicly available datasets and reports negligible runtimes for extracting PI-explanations.The paper studies two state-of-the-art tools and describes the datasets as publicly available.Source: §1 · p. 2
2 Preliminaries
The preliminaries define the classification setting, decision-tree paths, and PI-explanations used to compare path explanations with minimal sufficient feature values. They also illustrate that a path can include a feature value unnecessary for the prediction.
2 Preliminaries
- A classification problem maps feature assignments to classes; an instance pairs a concrete assignment with its predicted class.The paper focuses on binary classification for simplicity, while stating that its results readily apply to multiple classes.Source: §2 · p. 2, A decision tree · p. 2
- The paper studies univariate decision trees, whose paths encode consistent feature-value literals and end in class predictions.Generalized literals can restrict a feature to a subset of its domain.Source: A decision tree · p. 3
- A PI-explanation is a set of literals that entails the prediction while no proper subset does.The paper associates interpretability with irreducible sets of feature-value pairs sufficient for a prediction.Source: A decision tree · pp. 3–4
- A tree path is explanation-redundant when it is not a PI-explanation for its prediction.In the OR example, the path for (0,1) uses both feature values, although x2=1 alone explains the positive prediction.Source: A decision tree · p. 4
- The paper distinguishes its comparison with PI-explanations from prior work on local approximate explanations for decision trees.It notes that prior assessment of paths against PI-explanations had not been investigated to its knowledge.Source: A decision tree · pp. 4–5
3 Decision Trees May Not be Interpretable
Some Boolean functions admit learned decision-tree paths containing all features even though a PI-explanation has constant size. The section shows this gap can occur in an irreducible tree and in a simple PlayTennis example.
- The literal gap is n − k in an irreducible decision tree, where n is the number of features and k is the constant-size PI-explanation.The proposition establishes that such a path can be a proper superset of a PI-explanation.Source: §3 · p. 5
- For n = 4, the tree path uses four literals, while the PI-explanation needs only the last two feature values.The paper says this pattern generalizes to arbitrary even n: the path has n literals, while the PI-explanation has size 2.Source: §3 · p. 5
- The mismatch is independent of tree redundancy; it reflects a limitation of decision trees for succinctly representing certain function classes.The paper notes that its examples use nonredundant trees.Source: §3 · p. 5
- In the PlayTennis example, the path uses Humidity and Outlook, but Outlook = overcast alone entails the positive prediction.The sufficient feature value makes the Humidity condition unnecessary for that prediction.Source: §3 · p. 6
4 Extracting PI-Explanations from DTs
The section develops polynomial-time methods for identifying redundant literals on decision-tree paths and extracting one PI-explanation per path. It also distinguishes explanations restricted to a tree path from explanations that may use any feature values in the instance.
4 Extracting PI-Explanations from DTs
- A path is explanation-redundant when a literal can be dropped while the remaining literals still guarantee that every opposite-prediction path is inconsistent.The algorithm tests path features by making them universal and checking whether an opposite-prediction path becomes consistent; with filtering, redundancy checking runs in O(|T|).Source: §4 · pp. 7–8
- Computing one PI-explanation for each tree path takes O(|T|^3) in the worst case.The extraction algorithm takes O(|T|^2) per path; unlike the redundancy check, it must analyze all relevant sub-paths.Source: §4 · p. 9
- Path-restricted explanations use only literals on the consistent tree path, whereas path-unrestricted explanations may use instance literals outside that path.For the Figure 3 example, the path-restricted explanation is {(x1 = 1),(x3 = 1)}, while an unrestricted explanation is {(x2 = 1),(x3 = 1),(x4 = 1)}.Source: §4 · p. 10
5 Enumeration of PI-Explanations
The section reduces enumeration of a decision tree's PI-explanations to enumeration of minimal hitting sets. Each hitting set selects literals that rule out every path with the opposite prediction.
5 Enumeration of PI-Explanations
- The reduction provides an enumeration route for decision trees, while compiled representations can be worst-case exponential and prior iterative entailment work does not address enumeration.The paper identifies enumeration of minimal hitting sets as its solution.Source: §5 · pp. 10–11
- For each opposite-prediction path, collect the considered literals inconsistent with it; subset-minimal sets hitting every such collection are PI-explanations.The considered literals can come from the instance or from its consistent tree path.Source: §5 · p. 11
- For the Figure 3 example, considering the instance yields two path-unrestricted PI-explanations: {(x1 = 1),(x3 = 1)} and {(x2 = 1),(x4 = 1),(x3 = 1)}.These are the minimal hitting sets for the example's opposite-prediction paths.Source: §5 · p. 11
6 Experimental Results
Experiments on publicly available datasets evaluated decision trees learned with ITI and IAI. Both tools' trees frequently contained explanation-redundant paths, and removing that redundancy had negligible computational cost.
6 Experimental Results
- The evaluation used ITI and IAI on 80 publicly available datasets, reporting detailed results for 30 datasets.The experiments used categorical, non-binarized data; ITI was pruned, while IAI used an optimal tree classifier with maximal depth 6.Source: §6 · p. 11
- 32.1% of IAI paths and 46.9% of ITI paths were explanation-redundant on average across the evaluated datasets.For some trees from either tool, more than 85% of paths were redundant.Source: Table 1 · p. 12, §6 · p. 13
- Redundant paths covered an average of 20.1% of feature space for IAI and 37.7% for ITI.In some cases, redundant paths covered up to 89% of feature space for IAI and 98% for ITI.Source: Table 1 · p. 12, §6 · p. 13
- Removing explanation-redundancy had negligible computational cost for the evaluated trees.The reported average removal times were 0.06 seconds per IAI tree and 0.29 seconds per ITI tree.Source: §6 · pp. 12–13
7 Conclusions
The conclusion presents decision-tree paths as potentially containing irrelevant literals even in irreducible trees, and summarizes methods for checking redundancy, extracting one PI-explanation, and enumerating explanations.
7 Conclusions
- Even irreducible decision trees can have paths containing literals irrelevant to an explanation.The proposed methods test path redundancy, compute one PI-explanation, and connect enumeration to minimal hitting sets.Source: §7 · p. 13
- On publicly available datasets, learned-tree paths often contained irrelevant literals, including for irreducible trees.For the trees examined, algorithm runtimes were negligible or comparable to tree-learning times.Source: §7 · p. 13
- The paper concludes that decision-tree paths do not always provide succinct explanations for predictions.Its conclusion contrasts paths with PI-explanations and reports that the proposed methods can compute one explanation in polynomial time.Source: §7 · p. 13
A.1 Analysis of DT from Russel&Norvig’s Book
Analysis of the restaurant decision tree finds explanation-redundancy in 2 of its 8 paths, where some path literals are irrelevant to the prediction.
A.1 Analysis of DT from Russel&Norvig’s Book
- The decision tree decides whether to wait for a restaurant table using six features.They include restaurant alternatives, bar availability, day, hunger, patron count, and restaurant type.Source: §A.1 · pp. 16–17
- 2 of 8 restaurant-tree paths exhibit explanation-redundancy, or 25%.For redundant paths, fixing other feature values makes a path literal irrelevant to the prediction.Source: Redundancy Analysis Results · p. 17
A.2 Analysis of DT from Poole&Mackworth’s Book
The bulletin-board tree has redundant paths in 2 of 4 cases; the supplied Zhou-book passage identifies a separate drawing-classification tree but gives no path results.
A.2 Analysis of DT from Poole&Mackworth’s Book
- The bulletin-board tree predicts whether an article is read using Author, Thread, and Length.The passage describes Author as known or unknown, Thread as new or follow-up, and Length as short or long.Source: §A.2 · p. 18
- 2 of 4 bulletin-board tree paths exhibit explanation-redundancy, or 50%.In the redundant paths, fixing other feature values makes either Length or Thread irrelevant to the prediction.Source: §A.2 · p. 18
A.3 Analysis of DT from Z.-H. Zhou’s book
- The Zhou-book tree predicts whether a drawing is a cross or circle using two features.The supplied passage introduces analysis of its paths but does not state the results.Source: §A.3 · pp. 18–19
A.4 Additional Examples
The paper notes that decision trees in a non-exhaustive list of books and surveys exhibit explanation-redundancy.
A.4 Additional Examples
- Decision trees in a non-exhaustive list of books and surveys exhibit explanation-redundancy.The cited list includes.Source: §A.4 · p. 19
B Full Table of Results
Table 2 presents explanation-redundancy results for decision trees obtained with IAI and ITI on an extended set of datasets.
B Full Table of Results
- Table 2 covers explanation-redundancy in decision trees obtained with IAI and ITI.The accompanying prose says the results use an extended set of datasets; no cell values are supplied here.Source: B Full Table of Results · p. 19, Table 2 · p. 20