Literati: Towards Anytime Optimal Shape Generalized Trees via AO*

• URL: http://arxiv.org/abs/2609.09299v1
• Date: Tue, 08 Sep 2026 18:00:21 GMT
• Title: Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
• Abstract summary: Shape Generalized Trees (SGTs) generalize shape functions, improving expressivity and enabling more compact trees.<n>Existing SGT induction algorithms are greedy and offer no optimality guarantees.<n>We introduce Literati, the first algorithm for optimal SGT induction.
• Score: 3.469167914196103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision trees are prized for their interpretability and strong performance on tabular data, but popular greedy top-down induction algorithms can yield suboptimal and unnecessarily complex structures. Optimal decision tree methods address this through global optimization, yet remain restricted to axis-aligned threshold splits, which limit the expressivity of each node and often force deep, complex trees to capture non-linear feature effects. Shape Generalized Trees (SGTs) generalize threshold splits to learnable univariate shape functions, improving expressivity and enabling more compact trees. However, existing SGT induction algorithms are greedy and offer no optimality guarantees. In this work, we introduce Literati, the first algorithm for optimal SGT induction. We propose a novel AND/OR graph formulation of the problem that jointly optimizes tree structure and shape function complexity. To solve this AND/OR graph, we develop an AO*-based algorithm with two enhancements that improve anytime performance while preserving optimality: a secondary heuristic for OR-node selection and a round-robin policy for AND-node exploration. Across 24 real-world datasets, Literati achieves higher training and test accuracy than state-of-the-art tree approaches.

Related papers

• Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction [16.87091101554527]
  We develop a joint feature- and sample-space computation framework based on STreeD.<n>Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives.<n> Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems.
  arXiv  Detail & Related papers  (2026-09-05T02:42:53Z)
• TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees [73.0940890296463]
  probabilistic values are used to rank features for explaining local predicted values of decision trees.<n>TreeGrad computes the gradients of the multilinear extension of the joint objective in $O(L)$ time for decision trees with $L$ leaves.<n>TreeGrad-Ranker aggregates the gradients while optimizing the joint objective to produce feature rankings.<n>TreeGrad-Shap is a numerically stable algorithm for computing Beta Shapley values with integral parameters.
  arXiv  Detail & Related papers  (2026-02-12T06:17:12Z)
• 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)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)
• Near Optimal Decision Trees in a SPLIT Second [16.99892407039875]
  Decision tree optimization is fundamental to interpretable machine learning.<n>Recent approaches find the global optimum using branch and bound with dynamic programming.<n>We introduce a family of algorithms called SPLIT that moves us significantly forward in achieving this ideal balance.
  arXiv  Detail & Related papers  (2025-02-21T22:57:17Z)
• Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound [1.3654846342364308]
  An optimal classification tree that maximizes training performance within a given size limit is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three.<n>We propose a novel algorithm that optimize trees directly on the continuous feature data using dynamic programming with branch-and-bound.<n>Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedys.
  arXiv  Detail & Related papers  (2025-01-14T07:46:33Z)
• 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)
• 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)

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.