Formally Explaining Decision Tree Models with Answer Set Programming

• URL: http://arxiv.org/abs/2601.03845v1
• Date: Wed, 07 Jan 2026 12:07:45 GMT
• Title: Formally Explaining Decision Tree Models with Answer Set Programming
• Authors: Akihiro Takemura, Masayuki Otani, Katsumi Inoue,
• Abstract summary: We propose a method for generating various types of explanations, namely, sufficient, contrastive, majority, and tree-specific explanations.<n>Compared to SAT-based approaches, our ASP-based method offers greater flexibility in encoding user preferences and supports enumeration of all possible explanations.
• Score: 4.263043028086137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision tree models, including random forests and gradient-boosted decision trees, are widely used in machine learning due to their high predictive performance. However, their complex structures often make them difficult to interpret, especially in safety-critical applications where model decisions require formal justification. Recent work has demonstrated that logical and abductive explanations can be derived through automated reasoning techniques. In this paper, we propose a method for generating various types of explanations, namely, sufficient, contrastive, majority, and tree-specific explanations, using Answer Set Programming (ASP). Compared to SAT-based approaches, our ASP-based method offers greater flexibility in encoding user preferences and supports enumeration of all possible explanations. We empirically evaluate the approach on a diverse set of datasets and demonstrate its effectiveness and limitations compared to existing methods.

Related papers

• Leveraging Predictive Equivalence in Decision Trees [25.79772180003752]
  Decision trees are widely used for interpretable machine learning.<n>We present a representation of decision trees that does not exhibit predictive equivalence.<n>We show that decision trees are surprisingly robust to test-time missingness of feature values.
  arXiv  Detail & Related papers  (2025-06-17T03:11:30Z)
• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThink is a simple yet effective scheme that integrates externally estimated task difficulty and internally measured model uncertainty.<n>It learns to compress reasoning length in accordance with scene complexity and predictive confidence.<n> Experimental results demonstrate that the proposed approach improves both reasoning efficiency and overall segmentation performance.
  arXiv  Detail & Related papers  (2025-05-29T17:55:49Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  We propose a hybrid amortized structure inference approach to learn predictive decision tree ensembles given data.<n>We show that our approach, DT-GFN, outperforms state-of-the-art decision tree and deep learning methods on standard classification benchmarks.
  arXiv  Detail & Related papers  (2025-03-10T07:05:07Z)
• Inherently Interpretable Tree Ensemble Learning [7.868733904112288]
  We show that when shallow decision trees are used as base learners, the ensemble learning algorithms can become inherently interpretable. An interpretation algorithm is developed that converts the tree ensemble into the functional ANOVA representation with inherent interpretability. Experiments on simulations and real-world datasets show that our proposed methods offer a better trade-off between model interpretation and predictive performance.
  arXiv  Detail & Related papers  (2024-10-24T18:58:41Z)
• Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
  We propose a novel framework that utilizes large language models (LLMs) to identify effective feature generation rules. We use decision trees to convey this reasoning information, as they can be easily represented in natural language. OCTree consistently enhances the performance of various prediction models across diverse benchmarks.
  arXiv  Detail & Related papers  (2024-06-12T08:31:34Z)
• Understanding the Language Model to Solve the Symbolic Multi-Step Reasoning Problem from the Perspective of Buffer Mechanism [68.05754701230039]
  We construct a symbolic multi-step reasoning task to investigate the information propagation mechanisms in Transformer models.<n>We propose a random matrix-based algorithm to enhance the model's reasoning ability.
  arXiv  Detail & Related papers  (2024-05-24T07:41:26Z)
• Even-if Explanations: Formal Foundations, Priorities and Complexity [18.126159829450028]
  We show that both linear and tree-based models are strictly more interpretable than neural networks. We introduce a preference-based framework that enables users to personalize explanations based on their preferences.
  arXiv  Detail & Related papers  (2024-01-17T11:38:58Z)
• 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)
• DeforestVis: Behavior Analysis of Machine Learning Models with Surrogate Decision Stumps [46.58231605323107]
  We propose DeforestVis, a visual analytics tool that offers summarization of the behaviour of complex ML models. DeforestVis helps users to explore the complexity versus fidelity trade-off by incrementally generating more stumps. We show the applicability and usefulness of DeforestVis with two use cases and expert interviews with data analysts and model developers.
  arXiv  Detail & Related papers  (2023-03-31T21:17:15Z)
• On Tackling Explanation Redundancy in Decision Trees [19.833126971063724]
  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.
  arXiv  Detail & Related papers  (2022-05-20T05:33:38Z)
• Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
  We propose an architecture called Iterative Retrieval-Generation Reasoner (IRGR) Our model is able to explain a given hypothesis by systematically generating a step-by-step explanation from textual premises. We outperform existing benchmarks on premise retrieval and entailment tree generation, with around 300% gain in overall correctness.
  arXiv  Detail & Related papers  (2022-05-18T21:52:11Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

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.