Provably optimal decision trees with arbitrary splitting rules in polynomial time

• URL: http://arxiv.org/abs/2503.01455v1
• Date: Mon, 03 Mar 2025 12:14:53 GMT
• Title: Provably optimal decision trees with arbitrary splitting rules in polynomial time
• Authors: Xi He, Max A. Little,
• Abstract summary: We provide the first axiomatic definition of decision trees.<n>We refer to decision trees that satisfy the axioms as proper decision trees.<n>We develop the first provably correct-time algorithm for solving the optimal decision tree problem.
• Score: 1.9405875431318445
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In this paper, we introduce a generic data structure called decision trees, which integrates several well-known data structures, including binary search trees, K-D trees, binary space partition trees, and decision tree models from machine learning. We provide the first axiomatic definition of decision trees. These axioms establish a firm mathematical foundation for studying decision tree problems. We refer to decision trees that satisfy the axioms as proper decision trees. We prove that only proper decision trees can be uniquely characterized as K-permutations. Since permutations are among the most well-studied combinatorial structures, this characterization provides a fundamental basis for analyzing the combinatorial and algorithmic properties of decision trees. As a result of this advancement, we develop the first provably correct polynomial-time algorithm for solving the optimal decision tree problem. Our algorithm is derived using a formal program derivation framework, which enables step-by-step equational reasoning to construct side-effect-free programs with guaranteed correctness. The derived algorithm is correct by construction and is applicable to decision tree problems defined by any splitting rules that adhere to the axioms and any objective functions that can be specified in a given form. Examples include the decision tree problems where splitting rules are defined by axis-parallel hyperplanes, arbitrary hyperplanes, and hypersurfaces. By extending the axioms, we can potentially address a broader range of problems. Moreover, the derived algorithm can easily accommodate various constraints, such as tree depth and leaf size, and is amenable to acceleration techniques such as thinning method.

Related papers

• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity [22.57063332430197]
  We focus on fundamental pruning operations of subtree replacement and raising. While optimal pruning can be performed in time for subtree replacement, the problem is NP-complete for subtree raising. For example, while subtree raising is hard for small domain size, it can be solved in $D2d cdot |I|O(1)$ time, where $|I|$ is the input size.
  arXiv  Detail & Related papers  (2025-03-05T15:02:46Z)
• An Algorithmic Framework for Constructing Multiple Decision Trees by Evaluating Their Combination Performance Throughout the Construction Process [1.8749305679160366]
  Predictions using a combination of decision trees are known to be effective in machine learning. We propose a new algorithmic framework that constructs decision trees simultaneously and evaluates their combination performance.
  arXiv  Detail & Related papers  (2024-02-09T14:58:07Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• Construction of Decision Trees and Acyclic Decision Graphs from Decision Rule Systems [0.0]
  We study the complexity of constructing decision trees and acyclic decision graphs representing decision trees from decision rule systems. We discuss the possibility of not building the entire decision tree, but describing the computation path in this tree for the given input.
  arXiv  Detail & Related papers  (2023-05-02T18:40:48Z)
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.7812210699650152]
  Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one?<n>We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up.
  arXiv  Detail & Related papers  (2022-03-06T14:04:06Z)
• Decision Machines: Congruent Decision Trees [0.0]
  We propose Decision Machines, which embed Boolean tests into a binary vector space and represent the tree structure as a matrices. We explore the congruence of decision trees and attention mechanisms, opening new avenues for optimizing decision trees and potentially enhancing their predictive power.
  arXiv  Detail & Related papers  (2021-01-27T12:23:24Z)
• 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)
• 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)
• 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)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs) We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching.
  arXiv  Detail & Related papers  (2020-02-12T17:43:23Z)

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.