REALITrees: Rashomon Ensemble Active Learning for Interpretable Trees
Authors: Simon D. Nguyen, Hayden McTavish, Kentaro Hoffman, Cynthia Rudin, Tyler H. McCormick
Organizations: Department of Statistics, University of Washington · Department of Computer Science, Duke University · Department of Sociology, University of Washington
Active learning reduces labeling costs by selecting samples that maximize information gain. A dominant framework, Query-by-Committee (QBC), typically relies on perturbation-based diversity by inducing model disagreement through random feature subsetting or data blinding. While this approximates one notion of epistemic uncertainty, it sacrifices direct characterization of the plausible hypothesis space. We propose the complementary approach: Rashomon Ensembled Active Learning (REAL) which constructs a committee by exhaustively enumerating the Rashomon Set of all near-optimal models. To address functional redundancy within this set, we adopt a PAC-Bayesian framework using a Gibbs posterior to weight committee members by their empirical risk. Leveraging recent algorithmic advances, we exactly enumerate this set for the class of sparse decision trees. Across synthetic and established active learning baselines, REAL outperforms randomized ensembles, particularly in moderately noisy environments where it strategically leverages expanded model multiplicity to achieve faster convergence.
Figures & tables
Figure 1: (Top) REAL leverages noise-induced version-space diversity to maintain superior performance, with its advantage widening until extreme noise floors ( ϕ=0.45 ) equalize all strategies. (Bottom) Under total misspecification ( α=1.0 ), all tree-based QBC strategies underperform relative to Passive Sampling. However, BREAL and UNREAL demonstrate unique resilience, outperforming the other QBC methods and maintaining early-stage efficiency despite the structural misalignment.
Figure 2: Active Learning Efficiency Heatmap ( K=0.7 ) . This figure displays the Efficiency Ratio ( ρ ) of standard baselines relative to REAL, with values below 1.0 ( Green ) indicating superior sample efficiency for our method. The results demonstrate that REAL reaches peak predictive performance significantly faster than randomized ensembles.
Figure 3: Relative Label Efficiency ( Nrel ) across 20 datasets. Each boxplot summarizes the labeling budget required to achieve 70% , 80% , and 90% of the total possible accuracy gain. Values to the left of the dashed line ( <1.0 ) indicate superior efficiency relative to Random Sampling. Both UNREAL and BREAL maintain a significantly tighter distribution and lower median than standard baselines, demonstrating that characterizing the Rashomon set provides a more reliable and robust path to cost reduction than randomized ensembles or greedy heuristics.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Label
Committee Foundation
Weighting
Diversity Mechanism
Random
Random Forest
Uniform
Passive (Random Baseline)
QBC-RF ( m=d )
Random Forest
Uniform
Artificial (Feature Blinding)
B-QBC-RF ( m=d )
Random Forest
Gibbs
Artificial + PAC-Bayesian
QBC-RF ( m=d )
Random Forest
Uniform
Artificial (Bootstrap Only)
B-QBC-RF ( m=d )
Random Forest
Gibbs
Artificial + PAC-Bayesian
Uncertainty
Optimal Sparse Tree
—
Greedy
Appendix
Table 1: Overview of evaluated active learning configurations. We categorize strategies by their committee foundation and weighting scheme to isolate the performance gains of structural version-space characterization from those of PAC-Bayesian posterior weighting.
No.
Dataset
Src
N
d
Maj%
Lin%
GBM%
Orc%
∣R^∣
ECS
1
Anneal
UCI
812
44
96.2
100.0
100.0
100.0
2
2.0
2
Bank Marketing
UCI
4,521
23
97.1
97.7
98.1
97.7
19,024
19,023.9
4
Bar-7
SOR
1,913
14
79.0
79.0
79.0
79.0
174,331
174,328.0
5
Breast Cancer WI
UCI
699
10
91.3
91.4
91.8
91.3
116,263
116,260.4
6
Car Ealuation
UCI
1,728
15
66.7
79.3
79.3
79.3
128,546
128,544.6
7
Cheap Restaurant
SOR
2,653
15
81.8
96.8
96.8
95.9
572
572.0
Appendix
Table 2: Datasets.
Figure 4: Active Learning Benchmarks. Accuracy traces across 20 real-world and structured datasets. UNREAL (Weighted and Uniform) consistently match or exceed baseline performance, demonstrating superior sample efficiency particularly in the early stages of the labeling process.
Baselines
QBC-RF
Weighted RF
REAL (Proposed)
Dataset
Random
Uncertainty
Coreset
F=3
F=Sqrt
F=All
F=Sqrt
F=All
UNREAL
BREAL
Synth. Xor Baseline
137.4
80.7
98.0
162.2
164.7
159.4
137.5
140.3
2960.0
3035.0
Synth. Xor Phi 05
168.2
113.2
119.7
196.0
196.0
197.4
176.3
177.1
3014.6
3050.2
Synth. Xor Phi 10
186.3
135.2
135.0
215.9
215.4
217.8
195.6
192.3
3052.7
3043.3
Synth. Xor Phi 25
259.4
203.3
210.6
286.7
284.1
287.1
262.8
266.1
2940.8
2875.1
Synth. Xor Phi 45
294.1
238.5
246.7
318.3
315.3
321.2
293.2
299.3
1674.9
1661.3
Appendix
Table 3: Median experiment runtime (seconds) across 25 simulation seeds. UNREAL and BREAL denote the standard and Bayesian variants of the UNREAL algorithm, respectively.
Figure 5: Committee Size History. Evolution of the Rashomon Effective Committee Size over active learning iterations across 20 benchmark datasets. The ECS serves as a metric of model certainty, quantifying the diversity of plausible theories within the version space as the learner explores the data manifold. A high ECS reflects a broad set of competing hypotheses, while values approaching 1.0 indicate the emergence of a single dominant structural explanation.
Figure 6: Rashomon Set Size Evolution. The total count of near-optimal models identifying the ϵ -version space during each iteration. These trajectories illustrate how acquiring specific labels prunes the hypothesis space, revealing the sensitivity of model multiplicity to new evidence across diverse dataset geometries.
Figure 7: Tree Edit Distance Benchmarks. Evaluation of the alignment between the decision logic of the learned hypotheses and the ground-truth Oracle tree. A lower distance indicates that BREAL is not merely achieving predictive success through spurious correlations, but is successfully recovering the true underlying structural logic of the task.
Figure 8: Oracle Agreement Benchmarks. Tracking consensus between the active learning committee and a ground-truth "Oracle" (optimal sparse tree fitted to the full dataset). In high-multiplicity environments, Weighted UNREAL achieves higher-fidelity alignment significantly faster than randomized baselines, demonstrating that its structural uncertainty signal successfully identifies the primary decision boundaries defining the task logic.
Figure 9: Trace Plots on Parity Datasets. In high-dimensional sparse regimes ( N=100 , up to 26 noise covariates), all tree-based active learning strategies perform below Passive Sampling as noise-induced patterns dominate. As we increase the number of noisy, useless covariates, QBC-RF becomes increasingly confused by stochastic variance, whereas REAL variants demonstrate superior recovery. By focusing its query strategy on the effective version space, REAL resolves the sparse 3-bit XOR signal more reliably than QBC-RF, eventually matching the accuracy of the other baselines and exceeding the performance of randomized ensembles.
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.
Zakk Heile, Hayden McTavish, Margo Seltzer +1
Department of Computer Science, Duke University, Durham, USA · Department of Computer Science, University of British Columbia, Vancouver, Canada
Standard machine learning pipelines often admit many near-optimal models. These "Rashomon sets" pose a range of challenges and opportunities for uncertainty-aware, robust decision making. They allow users to incorporate domain knowledge and preferences that would otherwise be difficult to specify directly in an objective, and they quantify diversity among valid models for a given training dataset and objective function. However, computation of Rashomon sets, even for simple, interpretable model classes such as sparse decision trees, continues to require immense memory and runtime resources. We present PRAXIS, an algorithm to approximate this Rashomon set with orders of magnitude improvement in runtime and memory usage. We validate that PRAXIS regularly recovers almost all of the full Rashomon set. PRAXIS allows researchers and practitioners to scalably model the Rashomon set for real-world datasets. Code for PRAXIS is available at https://github.com/zakk-h/PRAXIS
Zakk Heile, Hayden McTavish, Varun Babbar +2
Department of Computer Science, Duke University, Durham, USA · Department of Computer Science, University of British Columbia, Vancouver, Canada.
Rashomon sets are model sets within one model class that perform nearly as well as a reference model from the same model class. They reveal the existence of alternative well-performing models, which may support different interpretations. This enables selecting models that match domain knowledge, hidden constraints, or user preferences. However, efficient construction methods currently exist for only a few model classes. Applied machine learning usually searches many model classes, and the best class is unknown beforehand. We therefore study Rashomon sets in the combined algorithm selection and hyperparameter optimization (CASH) setting and call them CASHomon sets. We propose TruVaRImp, a model-based active learning algorithm for level set estimation with an implicit threshold, and provide convergence guarantees. On synthetic and real-world datasets, TruVaRImp reliably identifies CASHomon sets members and matches or outperforms naive sampling, Bayesian optimization, classical and implicit level set estimation methods, and other baselines. Our analyses of predictive multiplicity and feature-importance variability across model classes question the common practice of interpreting data through a single model class.
Fiona Katharina Ewald, Martin Binder, Matthias Feurer +2
Department of Statistics, LMU Munich, Munich, Germany · Munich Center for Machine Learning (MCML), Munich, Germany · TU Dortmund University, Dortmund, Germany +1