On Tackling Explanation Redundancy in Decision Trees

• URL: http://arxiv.org/abs/2205.09971v1
• Date: Fri, 20 May 2022 05:33:38 GMT
• Title: On Tackling Explanation Redundancy in Decision Trees
• Authors: Yacine Izza, Alexey Ignatiev and Joao Marques-Silva
• Abstract summary: Decision trees (DTs) epitomize the ideal of interpretability of machine learning (ML) models. This paper offers both theoretical and experimental arguments demonstrating that, as long as interpretability of decision trees equates with succinctness of explanations, then decision trees ought not to be deemed interpretable.
• Score: 19.833126971063724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision trees (DTs) epitomize the ideal of interpretability of machine learning (ML) models. The interpretability of decision trees motivates explainability approaches by so-called intrinsic interpretability, and it is at the core of recent proposals for applying interpretable ML models in high-risk applications. The belief in DT interpretability is justified by the fact that explanations for DT predictions are generally expected to be succinct. Indeed, in the case of DTs, explanations correspond to DT paths. Since decision trees are ideally shallow, and so paths contain far fewer features than the total number of features, explanations in DTs are expected to be succinct, and hence interpretable. This paper offers both theoretical and experimental arguments demonstrating that, as long as interpretability of decision trees equates with succinctness of explanations, then decision trees ought not be deemed interpretable. The paper introduces logically rigorous path explanations and path explanation redundancy, and proves that there exist functions for which decision trees must exhibit paths with arbitrarily large explanation redundancy. The paper also proves that only a very restricted class of functions can be represented with DTs that exhibit no explanation redundancy. In addition, the paper includes experimental results substantiating that path explanation redundancy is observed ubiquitously in decision trees, including those obtained using different tree learning algorithms, but also in a wide range of publicly available decision trees. The paper also proposes polynomial-time algorithms for eliminating path explanation redundancy, which in practice require negligible time to compute. Thus, these algorithms serve to indirectly attain irreducible, and so succinct, explanations for decision trees.

Related papers

• Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation [110.71955853831707]
  We view LMs as deriving new conclusions by aggregating indirect reasoning paths seen at pre-training time. We formalize the reasoning paths as random walk paths on the knowledge/reasoning graphs. Experiments and analysis on multiple KG and CoT datasets reveal the effect of training on random walk paths.
  arXiv  Detail & Related papers  (2024-02-05T18:25:51Z)
• Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers [68.76846801719095]
  We argue that the current high-level dichotomy into bias- and variance-reduction prevalent in statistics is insufficient to understand tree ensembles. We show that forests can improve upon trees by three distinct mechanisms that are usually implicitly entangled.
  arXiv  Detail & Related papers  (2024-02-02T15:36:43Z)
• Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions [93.40614719648386]
  Large language models (LLMs) are capable of answering knowledge-intensive complex questions with chain-of-thought (CoT) reasoning. Recent works turn to retrieving external knowledge to augment CoT reasoning. We propose a novel approach: Probabilistic Tree-of-thought Reasoning (ProbTree)
  arXiv  Detail & Related papers  (2023-11-23T12:52:37Z)
• A Uniform Language to Explain Decision Trees [6.658444706223188]
  We show that our proposed logics can express not only a variety of interpretability queries considered by previous literature, but also allows users to specify different objectives the sought explanations should optimize for. We provide a SAT-based implementation of the evaluation for OPT-DT-FOIL that is expressive on industry-size decision trees.
  arXiv  Detail & Related papers  (2023-10-18T00:07:38Z)
• Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
  We propose a tree-based method, termed as Social Interpretable Tree (SIT), to address this multi-modal prediction task. A path in the tree from the root to leaf represents an individual possible future trajectory. Despite the hand-crafted tree, the experimental results on ETH-UCY and Stanford Drone datasets demonstrate that our method is capable of matching or exceeding the performance of state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-26T12:18:44Z)
• Provably Precise, Succinct and Efficient Explanations for Decision Trees [32.062312674333775]
  Decision trees (DTs) embody interpretable classifiers. Work has demonstrated that predictions in DTs ought to be explained with rigorous explanations. delta-relevant sets denote that are succinct and provably precise.
  arXiv  Detail & Related papers  (2022-05-19T13:54:52Z)
• Trading Complexity for Sparsity in Random Forest Explanations [20.87501058448681]
  We introduce majoritary reasons which are prime implicants of a strict majority of decision trees. Experiments conducted on various datasets reveal the existence of a trade-off between runtime complexity and sparsity.
  arXiv  Detail & Related papers  (2021-08-11T15:19:46Z)
• On Efficiently Explaining Graph-Based Classifiers [16.199563506727316]
  This paper shows that not only decision trees (DTs) may not be interpretable but also proposed a-time algorithm for computing one PI-explanation of a DT. In addition, the paper also proposes a-time algorithm for computing one contrastive explanation.
  arXiv  Detail & Related papers  (2021-06-02T17:55:41Z)
• CDT: Cascading Decision Trees for Explainable Reinforcement Learning [19.363238773001537]
  Cascading Decision Trees (CDTs) apply representation learning on the decision path to allow richer expressivity. As a second contribution our study reveals limitations of explaining black-box policies via imitation learning with tree-based explainable models, due to its inherent instability.
  arXiv  Detail & Related papers  (2020-11-15T15:25:56Z)
• The Struggles of Feature-Based Explanations: Shapley Values vs. Minimal Sufficient Subsets [61.66584140190247]
  We show that feature-based explanations pose problems even for explaining trivial models. We show that two popular classes of explainers, Shapley explainers and minimal sufficient subsets explainers, target fundamentally different types of ground-truth explanations.
  arXiv  Detail & Related papers  (2020-09-23T09:45:23Z)
• Rectified Decision Trees: Exploring the Landscape of Interpretable and Effective Machine Learning [66.01622034708319]
  We propose a knowledge distillation based decision trees extension, dubbed rectified decision trees (ReDT) We extend the splitting criteria and the ending condition of the standard decision trees, which allows training with soft labels. We then train the ReDT based on the soft label distilled from a well-trained teacher model through a novel jackknife-based method.
  arXiv  Detail & Related papers  (2020-08-21T10:45:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.