Inapproximability of sufficient reasons for decision trees

• URL: http://arxiv.org/abs/2304.02781v1
• Date: Wed, 5 Apr 2023 23:02:03 GMT
• Title: Inapproximability of sufficient reasons for decision trees
• Authors: Alexander Kozachinskiy
• Abstract summary: In this note, we establish the hardness of approximation of the problem of computing the minimal size of a $delta$-sufficient reason for decision trees.
• Score: 91.75627458356654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this note, we establish the hardness of approximation of the problem of computing the minimal size of a $\delta$-sufficient reason for decision trees.

Related papers

• Causal Discovery and Classification Using Lempel-Ziv Complexity [2.7309692684728617]
  We introduce a novel causality measure and a distance metric derived from Lempel-Ziv complexity. We evaluate the effectiveness of the causality-based decision tree and the distance-based decision tree.
  arXiv  Detail & Related papers  (2024-11-04T08:24:56Z)
• On the Trade-off between the Number of Nodes and the Number of Trees in a Random Forest [8.340919965932443]
  We show that the majority function of $n$ variables can be represented by a bag of $T$ ($ n$) decision trees each with size if $n-T$ is a constant. A related result on the $k$-out-of-$n$ functions is presented too.
  arXiv  Detail & Related papers  (2023-12-16T02:09:34Z)
• Properly Learning Decision Trees with Queries Is NP-Hard [5.117810469621253]
  We prove that it is NP-hard to properly PAC learn decision trees with queries. We simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization.
  arXiv  Detail & Related papers  (2023-07-09T04:29:43Z)
• Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
  We propose an efficient algorithm that takes into account metrics related to the depths of the leaves in a decision tree. In experiments on 16 datasets, our algorithm yields better results than decision-tree clustering algorithms.
  arXiv  Detail & Related papers  (2021-12-29T18:22:28Z)
• On the Explanatory Power of Decision Trees [20.87501058448681]
  We show that the set of all sufficient reasons of minimal size for instance given a decision tree can be exponentially larger than the size of the input. We show how the explanatory importance of a feature and the number of sufficient reasons can be obtained via a model counting operation. Unlike sufficient reasons, the set of all contrastive explanations for an instance given a decision tree can be derived, minimized and counted in time.
  arXiv  Detail & Related papers  (2021-08-11T15:08:11Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  We analyze the output of state-of-the-arts on many languages from the Universal Dependency Treebank. The worst constraint-violation rate we observe is 24%.
  arXiv  Detail & Related papers  (2020-10-06T08:31:14Z)
• 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)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  We present a novel approach to formulate different notions of causal reasoning, over binary acyclic models, as optimization problems. We show that both notions are efficiently automated. Using models with more than $8000$ variables, checking is computed in a matter of seconds, with MaxSAT outperforming ILP in many cases.
  arXiv  Detail & Related papers  (2020-06-05T10: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.