ArborEnum: Decision Tree Rashomon Sets over Continuous Features

• URL: http://arxiv.org/abs/2608.04310v2
• Date: Sat, 08 Aug 2026 17:44:09 GMT
• Title: ArborEnum: Decision Tree Rashomon Sets over Continuous Features
• Abstract summary: Rashomon sets are the set of all models whose regularized loss is near-optimal.<n>Decision trees are one of the few model classes for which Rashomon sets can be fully enumerated.<n>We introduce the first algorithm that enumerates decision-tree Rashomon sets while exploiting the ordered structure of continuous features.
• Score: 21.921639033742903
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Rashomon effect describes the phenomenon that many models can achieve nearly equivalent performance on the same learning task, with significant ramifications for robustness, feature importance, and customizability. These use cases motivate the computation of Rashomon sets: the set of all models whose regularized loss is near-optimal. Decision trees are one of the few model classes for which Rashomon sets can be fully enumerated, but this computation has always been conditional on a binarization of the original data, either restricting which splits each tree is allowed to make or substantially increasing the complexity of an already difficult combinatorial problem. We introduce the first algorithm that exactly enumerates decision-tree Rashomon sets while exploiting the ordered structure of continuous features. We further develop a relaxation for approximate enumeration and an anytime algorithm that progressively refines the set of candidate thresholds, producing increasingly detailed approximations that converge to the continuous-feature Rashomon set. Experiments show that coarse binarization can miss many trees, important features, and predictive multiplicity; our algorithms achieve orders-of-magnitude speedups over existing enumeration methods, with approximations providing further speedups while maintaining near-perfect recall.

Related papers

• Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again [21.921639033742903]
  We introduce Multistage Defer Trees, a sequence of sparse decision trees that each make predictions for most samples.<n>We demonstrate that we can train this model class to match the performance of complex tree-based ensembles while routing most samples through only one or a small number of sparse decision trees.
  arXiv  Detail & Related papers  (2026-06-30T00:15:00Z)
• REALITrees: Rashomon Ensemble Active Learning for Interpretable Trees [21.32484182551777]
  Rashomon Ensembled Active Learning (REAL) constructs a committee by exhaustively enumerating the Rashomon Set of all near-optimal models.<n>We show that REAL outperforms randomized ensembles in moderately noisy environments.
  arXiv  Detail & Related papers  (2026-03-24T03:27:44Z)
• SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration [4.567122178196833]
  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.
  arXiv  Detail & Related papers  (2025-11-05T10:25:08Z)
• A Unified Approach to Extract Interpretable Rules from Tree Ensembles via Integer Programming [2.1408617023874443]
  Tree ensembles are very popular machine learning models, known for their effectiveness in supervised classification and regression tasks.<n>Our work aims to extract an optimized list of rules from a trained tree ensemble, providing the user with a condensed, interpretable model that retains most of the predictive power of the full model.<n>Our extensive computational experiments offer statistically significant evidence that our method is competitive with other rule extraction methods in terms of predictive performance and fidelity towards the tree ensemble.
  arXiv  Detail & Related papers  (2024-06-30T22:33:47Z)
• Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
  We phrase semantic parsing as a two-step process: we first tag each input token with a multiset of output tokens. Then we arrange the tokens into an output sequence using a new way of parameterizing and predicting permutations. Our model outperforms pretrained seq2seq models and prior work on realistic semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-05-26T14:09:35Z)
• 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)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Partial Order in Chaos: Consensus on Feature Attributions in the Rashomon Set [50.67431815647126]
  Post-hoc global/local feature attribution methods are being progressively employed to understand machine learning models. We show that partial orders of local/global feature importance arise from this methodology. We show that every relation among features present in these partial orders also holds in the rankings provided by existing approaches.
  arXiv  Detail & Related papers  (2021-10-26T02:53:14Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Predicting Temporal Sets with Deep Neural Networks [50.53727580527024]
  We propose an integrated solution based on the deep neural networks for temporal sets prediction. A unique perspective is to learn element relationship by constructing set-level co-occurrence graph. We design an attention-based module to adaptively learn the temporal dependency of elements and sets.
  arXiv  Detail & Related papers  (2020-06-20T03:29:02Z)

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.