Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules

• URL: http://arxiv.org/abs/2503.01455v2
• Date: Thu, 23 Oct 2025 08:48:37 GMT
• Title: Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
• Authors: Xi He, Max A. Little,
• Abstract summary: We present an axiomatic framework for analyzing the algorithmic properties of decision trees.<n>The central focus of this paper is a special class of decision tree problems-which we term proper decision trees-due to their versatility and effectiveness.<n>We show that memoization is generally impractical in terms of space complexity, as both datasets and subtrees must be stored.
• Score: 2.5505924504226223
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We present an axiomatic framework for analyzing the algorithmic properties of decision trees. This framework supports the classification of decision tree problems through structural and ancestral constraints within a rigorous mathematical foundation. The central focus of this paper is a special class of decision tree problems-which we term proper decision trees-due to their versatility and effectiveness. In terms of versatility, this class subsumes several well-known data structures, including binary space partitioning trees, K-D trees, and machine learning decision tree models. Regarding effectiveness, we prove that only proper decision trees can be uniquely characterized as K-permutations, whereas typical non-proper decision trees correspond to binary-labeled decision trees with substantially greater complexity. Using this formal characterization, we develop a generic algorithmic approach for solving optimal decision tree problems over arbitrary splitting rules and objective functions for proper decision trees. We constructively derive a generic dynamic programming recursion for solving these problems exactly. However, we show that memoization is generally impractical in terms of space complexity, as both datasets and subtrees must be stored. This result contradicts claims in the literature that suggest a trade-off between memoizing datasets and subtrees. Our framework further accommodates constraints such as tree depth and leaf size, and can be accelerated using techniques such as thinning. Finally, we extend our analysis to several non-proper decision trees, including the commonly studied decision tree over binary feature data, the binary search tree, and the tree structure arising in the matrix chain multiplication problem. We demonstrate how these problems can be solved by appropriately modifying or discarding certain axioms.

Related papers

• Foundational theory for optimal decision tree problems. II. Optimal hypersurface decision tree algorithm [1.972521190983547]
  In Part I of this series, we rigorously defined the proper decision tree model through four axioms.<n>In Part II, we introduce the first hypersurface decision tree (HODT) algorithm.
  arXiv  Detail & Related papers  (2025-09-15T15:38:44Z)
• 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)
• Learning accurate and interpretable tree-based models [27.203303726977616]
  We develop approaches to design tree-based learning algorithms given repeated access to data from the same domain.<n>We propose novel parameterized classes of node splitting criteria in top-down algorithms, which interpolate between popularly used entropy and Gini impurity based criteria.<n>We extend our results to tuning popular tree-based ensembles, including random forests and gradient-boosted trees.
  arXiv  Detail & Related papers  (2024-05-24T20:10:10Z)
• 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)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• 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.