Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations

• URL: http://arxiv.org/abs/2509.11226v1
• Date: Sun, 14 Sep 2025 12:01:02 GMT
• Title: Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
• Authors: Xi He,
• Abstract summary: In Part I, we introduce four novel definitions of the ODT problems.<n>In Part II, we present the first optimal hypersurface decision tree algorithm.
• Score: 1.972521190983547
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In the first paper (part I) of this series of two, we introduce four novel definitions of the ODT problems: three for size-constrained trees and one for depth-constrained trees. These definitions are stated unambiguously through executable recursive programs, satisfying all criteria we propose for a formal specification. In this sense, they resemble the "standard form" used in the study of general-purpose solvers. Grounded in algebraic programming theory-a relational formalism for deriving correct-by-construction algorithms from specifications-we can not only establish the existence or nonexistence of dynamic programming solutions but also derive them constructively whenever they exist. Consequently, the four generic problem definitions yield four novel optimal algorithms for ODT problems with arbitrary splitting rules that satisfy the axioms and objective functions of a given form. These algorithms encompass the known depth-constrained, axis-parallel ODT algorithm as the special case, while providing a unified, efficient, and elegant solution for the general ODT problem. In Part II, we present the first optimal hypersurface decision tree algorithm and provide comprehensive experiments against axis-parallel decision tree algorithms, including heuristic CART and state-of-the-art optimal methods. The results demonstrate the significant potential of decision trees with flexible splitting rules. Moreover, our framework is readily extendable to support algorithms for constructing even more flexible decision trees, including those with mixed splitting rules.

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)
• Provably optimal decision trees with arbitrary splitting rules in polynomial time [1.9405875431318445]
  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.
  arXiv  Detail & Related papers  (2025-03-03T12:14:53Z)
• Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem [12.1622929638257]
  We study the behaviour of Quality diversity (QD) algorithms for a classical planning problem seeking several solutions.<n>Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel.
  arXiv  Detail & Related papers  (2024-12-16T04:58:32Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• 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)
• Evolutionary algorithms for constructing an ensemble of decision trees [0.0]
  We propose several methods for induction of decision trees and their ensembles based on evolutionary algorithms. The main difference of our approach is using real-valued vector representation of decision tree. We test the predictive performance of this methods using several public UCI data sets.
  arXiv  Detail & Related papers  (2020-02-03T13:38:50Z)

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.