A Uniform Language to Explain Decision Trees

• URL: http://arxiv.org/abs/2310.11636v2
• Date: Tue, 21 May 2024 17:34:45 GMT
• Title: A Uniform Language to Explain Decision Trees
• Authors: Marcelo Arenas, Pablo Barcelo, Diego Bustamante, Jose Caraball, Bernardo Subercaseaux,
• Abstract summary: 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.
• Score: 6.658444706223188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The formal XAI community has studied a plethora of interpretability queries aiming to understand the classifications made by decision trees. However, a more uniform understanding of what questions we can hope to answer about these models, traditionally deemed to be easily interpretable, has remained elusive. In an initial attempt to understand uniform languages for interpretability, Arenas et al. (2021) proposed FOIL, a logic for explaining black-box ML models, and showed that it can express a variety of interpretability queries. However, we show that FOIL is limited in two important senses: (i) it is not expressive enough to capture some crucial queries, and (ii) its model agnostic nature results in a high computational complexity for decision trees. In this paper, we carefully craft two fragments of first-order logic that allow for efficiently interpreting decision trees: Q-DT-FOIL and its optimization variant OPT-DT-FOIL. We show that our proposed logics can express not only a variety of interpretability queries considered by previous literature, but also elegantly allows users to specify different objectives the sought explanations should optimize for. Using finite model-theoretic techniques, we show that the different ingredients of Q-DT-FOIL are necessary for its expressiveness, and yet that queries in Q-DT-FOIL can be evaluated with a polynomial number of queries to a SAT solver, as well as their optimization versions in OPT-DT-FOIL. Besides our theoretical results, we provide a SAT-based implementation of the evaluation for OPT-DT-FOIL that is performant on industry-size decision trees.

Related papers

• P-FOLIO: Evaluating and Improving Logical Reasoning with Abundant Human-Written Reasoning Chains [97.25943550933829]
  We present P-FOLIO, a human-annotated dataset consisting of diverse and complex reasoning chains. We use P-FOLIO to evaluate and improve large-language-model (LLM) reasoning capabilities.
  arXiv  Detail & Related papers  (2024-10-11T19:22:57Z)
• Crafting Interpretable Embeddings by Asking LLMs Questions [89.49960984640363]
  Large language models (LLMs) have rapidly improved text embeddings for a growing array of natural-language processing tasks. We introduce question-answering embeddings (QA-Emb), embeddings where each feature represents an answer to a yes/no question asked to an LLM. We use QA-Emb to flexibly generate interpretable models for predicting fMRI voxel responses to language stimuli.
  arXiv  Detail & Related papers  (2024-05-26T22:30:29Z)
• 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)
• Leveraging Structured Information for Explainable Multi-hop Question Answering and Reasoning [14.219239732584368]
  In this work, we investigate constructing and leveraging extracted semantic structures (graphs) for multi-hop question answering. Empirical results and human evaluations show that our framework: generates more faithful reasoning chains and substantially improves the QA performance on two benchmark datasets.
  arXiv  Detail & Related papers  (2023-11-07T05:32:39Z)
• Getting MoRE out of Mixture of Language Model Reasoning Experts [71.61176122960464]
  We propose a Mixture-of-Reasoning-Experts (MoRE) framework that ensembles diverse specialized language models. We specialize the backbone language model with prompts optimized for different reasoning categories, including factual, multihop, mathematical, and commonsense reasoning. Our human study confirms that presenting expert predictions and the answer selection process helps annotators more accurately calibrate when to trust the system's output.
  arXiv  Detail & Related papers  (2023-05-24T02:00:51Z)
• Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
  We use Boundless DAS to efficiently search for interpretable causal structure in large language models while they follow instructions. Our findings mark a first step toward faithfully understanding the inner-workings of our ever-growing and most widely deployed language models.
  arXiv  Detail & Related papers  (2023-05-15T17:15:40Z)
• Explanation Selection Using Unlabeled Data for Chain-of-Thought Prompting [80.9896041501715]
  Explanations that have not been "tuned" for a task, such as off-the-shelf explanations written by nonexperts, may lead to mediocre performance. This paper tackles the problem of how to optimize explanation-infused prompts in a blackbox fashion.
  arXiv  Detail & Related papers  (2023-02-09T18:02:34Z)
• APOLLO: A Simple Approach for Adaptive Pretraining of Language Models for Logical Reasoning [73.3035118224719]
  We propose APOLLO, an adaptively pretrained language model that has improved logical reasoning abilities. APOLLO performs comparably on ReClor and outperforms baselines on LogiQA.
  arXiv  Detail & Related papers  (2022-12-19T07:40:02Z)
• 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)
• Foundations of Symbolic Languages for Model Interpretability [2.3361634876233817]
  We study the computational complexity of FOIL queries over two classes of ML models often deemed to be easily interpretable. We present a prototype implementation of FOIL wrapped in a high-level declarative language.
  arXiv  Detail & Related papers  (2021-10-05T21:56:52Z)

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.