SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration

• URL: http://arxiv.org/abs/2511.03344v1
• Date: Wed, 05 Nov 2025 10:25:08 GMT
• Title: SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration
• Authors: Elif Arslan, Jacobus G. M. van der Linden, Serge Hoogendoorn, Marco Rinaldi, Emir Demirović,
• Abstract summary: SORTD is a novel framework that improves scalability and enumerates trees in the Rashomon set in order of the objective value.<n>Our experiments show that SORTD reduces runtime by up to two orders of magnitude compared with the state of the art.
• Score: 4.567122178196833
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparse decision tree learning provides accurate and interpretable predictive models that are ideal for high-stakes applications by finding the single most accurate tree within a (soft) size limit. Rather than relying on a single "best" tree, Rashomon sets-trees with similar performance but varying structures-can be used to enhance variable importance analysis, enrich explanations, and enable users to choose simpler trees or those that satisfy stakeholder preferences (e.g., fairness) without hard-coding such criteria into the objective function. However, because finding the optimal tree is NP-hard, enumerating the Rashomon set is inherently challenging. Therefore, we introduce SORTD, a novel framework that improves scalability and enumerates trees in the Rashomon set in order of the objective value, thus offering anytime behavior. Our experiments show that SORTD reduces runtime by up to two orders of magnitude compared with the state of the art. Moreover, SORTD can compute Rashomon sets for any separable and totally ordered objective and supports post-evaluating the set using other separable (and partially ordered) objectives. Together, these advances make exploring Rashomon sets more practical in real-world applications.

Related papers

• Multi-Armed Bandits-Based Optimization of Decision Trees [0.0]
  We propose a Multi-Armed Bandits (MAB)-based pruning approach, a reinforcement learning (RL)-based technique, that will dynamically prune the tree to generate an optimal decision tree with better generalization.<n>Our proposed approach assumes the pruning process as an exploration-exploitation problem, where we are utilizing the MAB algorithms to find optimal branch nodes to prune based on feedback from each pruning actions.
  arXiv  Detail & Related papers  (2025-08-08T02:43:45Z)
• Experiments with Optimal Model Trees [1.3750624267664155]
  We show that globally optimal model trees can achieve competitive accuracy with very small trees.<n>We also compare to classic optimal and greedily grown decision trees, random forests, and support vector machines.
  arXiv  Detail & Related papers  (2025-03-17T08:03:47Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  We propose a hybrid amortized structure inference approach to learn predictive decision tree ensembles given data.<n>We show that our approach, DT-GFN, outperforms state-of-the-art decision tree and deep learning methods on standard classification benchmarks.
  arXiv  Detail & Related papers  (2025-03-10T07:05:07Z)
• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  We propose a Deep Tree-based Retriever (DTR) for efficient recommendation. DTR frames the training task as a softmax-based multi-class classification over tree nodes at the same level. To mitigate the suboptimality induced by the labeling of non-leaf nodes, we propose a rectification method for the loss function.
  arXiv  Detail & Related papers  (2024-08-21T05:09:53Z)
• 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)
• Sharded Bayesian Additive Regression Trees [1.4213973379473654]
  We introduce a randomization auxiliary variable and a sharding tree to decide partitioning of data. By observing that the optimal design of a sharding tree can determine optimal sharding for sub-models on a product space, we introduce an intersection tree structure to completely specify both the sharding and modeling using only tree structures.
  arXiv  Detail & Related papers  (2023-06-01T05:41:31Z)
• Unboxing Tree Ensembles for interpretability: a hierarchical visualization tool and a multivariate optimal re-built tree [0.34530027457862006]
  We develop an interpretable representation of a tree-ensemble model that can provide valuable insights into its behavior. The proposed model is effective in yielding a shallow interpretable tree approxing the tree-ensemble decision function.
  arXiv  Detail & Related papers  (2023-02-15T10:43:31Z)
• Exploring the Whole Rashomon Set of Sparse Decision Trees [23.136590456299007]
  We show that the Rashomon set is the set of all almost-optimal models. We provide the first technique for completely enumerating the Rashomon set for sparse decision trees. This allows the user an unprecedented level of control over model choice.
  arXiv  Detail & Related papers  (2022-09-16T16:37:26Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• 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.