On Explaining Decision Trees

By Yacine Izza, Alexey Ignatiev, Joao Marques-Silva. 2020

116 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Mathematical optimization in classification and regression trees (2021, background): “Moreover, this type of explanations, i.e., the ones given by the 1 3 Mathematical optimization in classification and regression… path from the root to the corresponding leaf node, can be arbitrarily long (Izza et al. 2020).”
Globally-Consistent Rule-Based Summary-Explanations for Machine Learning Models: Application to Credit-Risk Evaluation (2019, unknown): “We briefly note the follow up work to ours by Izza et al. (2020), Marques-Silva et al. (2020) who develop similar solutions to Ignatiev et al. (2019) in the context of other ML models (decision trees and linear classifiers).”