PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploring the Whole Rashomon Set of Sparse Decision Trees

Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, Cynthia Rudin

arXiv:2209.08040v2cs.LGcs.AI

TL;DR

Practitioners often face many almost-equally-good models, but algorithms typically return only one, limiting exploration of alternatives. TreeFARMS completely enumerates sparse decision-tree Rashomon sets using analytical bounds and a specialized representation. The resulting sets support analysis of variable importance and other model-choice questions.

  • Problem

    Many models can explain data almost equally well, but learning algorithms commonly return one model, leaving practitioners without a practical way to explore alternatives with desirable properties.

    Source: §1 · p. 1

  • Method

    TreeFARMS uses analytical bounds to exclude parts of the search space and a specialized Model Set representation to enumerate sparse decision-tree Rashomon sets.

    Source: §1 · p. 2, §4 · p. 4

  • Results

    The enumerated sets support direct analysis of variable importance, prediction variability, robustness to data removal, and Rashomon sets for other losses.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Access to the Rashomon set gives users a choice among approximately equally good models rather than a single algorithm-selected model.

    Source: §7 · p. 10

Abstract

from arXiv · show

In any given machine learning problem, there may be many models that could explain the data almost equally well. However, most learning algorithms return only one of these models, leaving practitioners with no practical way to explore alternative models that might have desirable properties beyond what could be expressed within a loss function. The Rashomon set is the set of these all almost-optimal models. Rashomon sets can be extremely complicated, particularly for highly nonlinear function classes that allow complex interaction terms, such as decision trees. We provide the first technique for completely enumerating the Rashomon set for sparse decision trees; in fact, our work provides the first complete enumeration of any Rashomon set for a non-trivial problem with a highly nonlinear discrete function class. This allows the user an unprecedented level of control over model choice among all models that are approximately equally good. We represent the Rashomon set in a specialized data structure that supports efficient querying and sampling. We show three applications of the Rashomon set: 1) it can be used to study variable importance for the set of almost-optimal trees (as opposed to a single tree), 2) the Rashomon set for accuracy enables enumeration of the Rashomon sets for balanced accuracy and F1-score, and 3) the Rashomon set for a full dataset can be used to produce Rashomon sets constructed with only subsets of the data set. Thus, we are able to examine Rashomon sets across problems with a new lens, enabling users to choose models rather than be at the mercy of an algorithm that produces only a single model.

1 Introduction

The paper argues that practitioners may need to explore many almost-equally-good models rather than accept a single model, especially when other properties matter. It introduces TreeFARMS to completely enumerate sparse decision-tree Rashomon sets and use them to study model choice and related questions.

1 Introduction

  • The Rashomon set contains almost-equally-optimal models, which practitioners may explore for properties such as interpretability, fairness, or use of specific variables.Other desired properties include agreement with causal hypotheses or domain intuition.Source: §1 · p. 1
  • The authors suggest that a small sacrifice in empirical risk can distinguish a usable model from one that is not.They propose treating learning as a feasibility problem that finds approximately-equally-good models for users to choose among.Source: §1 · p. 2
  • Sparse decision trees pose a difficult enumeration problem: even trees of depth at most 4 with 10 binary features have more than 9.338 × 10^20 possible models.The paper says this complexity had prevented full Rashomon-set enumeration for optimal sparse trees and other non-trivial function classes with many interactions.Source: §1 · p. 2
  • TreeFARMS combines analytical bounds that exclude search regions with a specialized data structure to completely enumerate sparse decision-tree Rashomon sets on real-world datasets.The authors describe this as the first complete enumeration of a Rashomon set for sparse decision trees.Source: §1 · p. 2
  • After finding the Rashomon set, the authors show how to study variable importance, prediction variability, robustness to data removal, and sets for other losses.They present these as questions that can be answered directly after running their algorithm.Source: §1 · p. 2

2 Related Work

Prior work studies Rashomon sets, model enumeration, decision-tree optimization, and Bayesian sampling, but the authors distinguish their contribution as finding the full set of well-performing sparse decision trees on real problems.

Rashomon sets

  • Earlier Rashomon-set work studies properties such as interpretability, fairness, and ranges of variable importance, while this paper finds the full set of well-performing sparse decision trees on real problems.The passage also describes prior work on diverse near-optimal integer programs and model-path collections.Source: §2 · p. 2

Model enumeration

  • Unlike greedy tree enumeration, this work searches the entire binary decision-tree space to find all well-performing trees, rather than features in greedy trees.Other cited enumeration methods store only one model for a given set of itemsets, and thus only a small subset of the Rashomon set.Source: §2 · p. 2

Decision trees

  • Greedy induction avoids the NP-complete problem of finding an optimal tree but produces suboptimal trees, motivating optimization and dynamic-programming approaches.The passage cites mathematical optimization and dynamic programming with branch-and-bound as alternatives.Source: §2 · p. 2

Bayesian trees

  • Although Bayesian methods such as BART and random forests sample multiple models, the paper's Figure 1 experiments find that they do not effectively sample the Rashomon set.The passage contrasts posterior sampling with the authors' experimental finding.Source: §2 · p. 3

3 Bounds for Reducing the Search Space

The section develops lower bounds for excluding partial trees that cannot meet the Rashomon threshold. It tightens these bounds using equivalent data points and applies them recursively to prune the search.

3 Bounds for Reducing the Search Space

  • The objective combines training misclassification loss with a sparsity penalty on the number of leaves, and the ϵ-Rashomon set includes trees whose objective is at most (1 + ϵ) times the reference objective.The reference is typically an empirical risk minimizer, and ϵ sets the permitted relative objective gap.Source: §3 · p. 3
  • For a partial tree, the basic lower bound uses fixed-leaf loss plus the leaf penalty; if it exceeds the Rashomon threshold, the tree and all its extensions can be excluded.The bound assumes the unfixed parts could classify their points perfectly, giving a best-case objective for comparison with the threshold.Source: §3 · p. 3
  • The equivalent-points bound tightens the lower bound by accounting for the unavoidable misclassification loss among identical-feature points in unfixed leaves.Equivalent points have exactly the same feature values, and the bound uses their minority-class label.Source: §3 · p. 3
  • The bounds can be applied recursively during dynamic programming to reject splits whose resulting subproblem lower bounds exceed the Rashomon threshold.The paper also uses a lookahead bound that prunes children when the lower bound plus λ exceeds the threshold.Source: §3 · pp. 3–4

4 Storing, Extracting, and Sampling the Rashomon Set

TreeFARMS represents and extracts the Rashomon set through a dependency graph and a Model Set data structure, with uniform sampling available when the set is too large to store in memory.

4 Storing, Extracting, and Sampling the Rashomon Set

  • The Model Set groups trees with the same objective in hierarchical maps, reducing duplicated storage and computation because many trees share objective values.A Model Set Instance can represent a leaf, an internal node, or both; internal maps link split features to left and right instances.Source: §4 · p. 4

4.1 TreeFARMS Implementation

  • TreeFARMS modifies GOSDT to prune only subproblems whose lower bounds exceed the Rashomon threshold, then returns all models within that threshold.GOSDT's objective-based pruning could remove near-optimal models, so TreeFARMS instead uses the Rashomon-set bound.Source: §4.1 · p. 4

4.2 Extraction Algorithm

  • The extraction algorithm builds the Rashomon set by adding eligible leaves and combining left-right subtree instances only when their objectives remain within scope.It skips splits absent from the dependency graph or exceeding the scope, and the completed Model Set represents all trees in the set.Source: §4.2 · pp. 4–5

4.3 Sampling from the Rashomon Set

  • When the set is too large to fit in memory, the Model Set supports uniform sampling to explore it with lower computational burden.The paper gives the example of COMPAS with regularization 0.005 and a threshold within 15% of optimal, producing 10^12 trees.Source: §4.3 · p. 5

5 Applications of the Rashomon Set

The applications include deriving balanced-accuracy and F1-score Rashomon sets from accuracy-based sets and relating reduced-data trees to the full-data Rashomon set.

5 Applications of the Rashomon Set

  • The paper presents access to the Rashomon set as a basis for multiple applications.The supplied passages do not detail the variable-importance application.Source: §5 · p. 5

5.2 Rashomon Sets Beyond Accuracy: Constructing the Rashomon Set for Other Metrics

  • Accuracy-based Rashomon sets can be searched to find the corresponding balanced-accuracy and F1-score sets.The paper says the theorems provide objective-threshold constraints for that search.Source: §5.2 · p. 6

5.3 Sensitivity to Missing Groups of Samples

  • Removing a group of instances leaves the reduced-dataset optimal tree in the full-data Rashomon set when ϵ ≥ 2|K| n×Obj(t∗,x,y).This is Theorem 5.3’s stated condition.Source: §5.3 · p. 7
  • A reduced-dataset Rashomon set is contained in the full-data set when ϵ ≥ ϵ′ + (2+ϵ′)|K| n×Obj(t∗,x,y).Theorem 5.4 applies this condition to every tree in the reduced-data set.Source: §5.3 · p. 7

6 Experiments

The experiments compare TreeFARMS with natural baselines and use the enumerated Rashomon sets to examine variable importance, alternative metrics, and sample-removal shifts. Across these applications, the results show that baseline searches cover little of the set, while near-optimal trees can remain well-performing after some samples are removed even when the optimal tree changes.

6 Experiments

  • The experiments used UCI, penguin, COMPAS, FICO, and coupon datasets, comparing TreeFARMS with BART, Random Forest, CART, and GOSDT among other evaluation questions.The evaluation also examined runtime, Rashomon-set structure, model class reliance, alternative metrics, and the effect of removing samples.Source: §6 · p. 7, §6.1 · p. 7

6.1 Performance and Timing Experiments

  • TreeFARMS found orders of magnitude more distinct Rashomon-set trees than four baselines across Monk2, COMPAS, and Bar, and found them at a dramatically faster rate.Most baseline trees fell outside the Rashomon set; the authors conclude that natural baselines find at best a tiny sliver of it.Source: §6.1 · pp. 7–8, Figure 1 · p. 8, Figure 2 · p. 8

6.2 Variable Importance: Model Class Reliance

  • On COMPAS, prior-count features generally had high MCR+, while Bar_1-3 and Bar_4-8 had dominant MCR+ and MCR− across well-performing Bar trees.Sampling for MCR had a large memory benefit over storing the full set, and 25% of samples were usually sufficient for convergence to true MCR.Source: §6.2 · p. 8, Figure 3 · p. 9

6.3 Balanced Accuracy and F1-score Rashomon set from Accuracy Rashomon set

  • Trees optimizing balanced accuracy or F1-score need not minimize accuracy; some trees with worse accuracy objectives perform better on those metrics.The examples include a single-root all-positive accuracy optimum and a six-leaf balanced-accuracy optimum.Source: §6.3 · pp. 8–9, Figure 4 · p. 9

6.4 Rashomon set after removing a group of samples

  • After either specified 1% sample removal, full- and reduced-dataset accuracy objectives were highly correlated, but reduced-dataset optimal trees could differ.The removals concerned the expensive-restaurant-frequency and income criteria in the Expensive Restaurant dataset.Source: Figure 5 · p. 9, §6.4 · p. 10

7 Conclusion

TreeFARMS represents optimal and slightly suboptimal models for nonlinear function classes with variable interactions. The resulting capabilities give users a choice among models rather than a single algorithm-selected model.

7 Conclusion

  • TreeFARMS provides user-centered capabilities by efficiently representing optimal and slightly suboptimal models for complex nonlinear function classes with interactions between variables.The authors identify variable importance, distributional shift, and user options as areas the work opens for discussion.Source: §7 · p. 10

Checklist

The checklist reports that the paper discusses limitations and provides reproduction-related details. It also records disclosures about proofs, error bars, and asset attribution and licensing.

Checklist

  • The checklist marks limitations as discussed: TreeFARMS models are not causal, have limited capacity as sparse binary trees, inherit flaws from training data, and are not yet application-customized.Application customization is identified as possible future work.Source: Checklist · p. 13
  • The checklist points to Appendix E for complete proofs and to the code-availability materials and Appendices F and G for reproduction details and training information.It reports that error bars are included in Appendix G.Source: Checklist · p. 13
  • The checklist reports citations for existing assets and says the code and data licenses are included.The supplied checklist passage identifies these items as completed.Source: Checklist · p. 13

A The Model Set Representation

The Model Set represents trees through reusable subproblem/objective instances, and TreeFARMS recursively extracts the trees within a specified objective scope. The representation also supports sampling and measuring feature reliance across the Rashomon set.

A The Model Set Representation

B The TreeFARMS Algorithm

  • TreeFARMS recursively builds the set by adding feasible leaves and combining child MSIs, while excluding combinations whose objective exceeds scope.The full-data Rashomon set is represented by the Model Set for the complete dataset.Source: B The TreeFARMS Algorithm · pp. 16–17

C Sampling from the Rashomon Set

  • Sampling draws a random index from the total tree count and maps it to a unique tree using counts stored for each MSI and split entry.These counts support sampling when the Rashomon set is too large to materialize in memory.Source: C Sampling from the Rashomon Set · p. 18

D Model Class Reliance of Decision Trees

  • Model reliance compares a tree’s loss after permuting a feature with its original loss, including the leaf penalty in both quantities.The model class reliance interval gives the minimum and maximum model reliance across trees in the ϵ-Rashomon set.Source: D Model Class Reliance of Decision Trees · p. 19
  • Computing both model class reliance bounds is difficult for trees because the discrete optimization with interaction terms is nonconvex.The paper identifies access to an enumerated Rashomon set as a way to compute these bounds.Source: D Model Class Reliance of Decision Trees · p. 19

E Theorems and Proofs

The theorems establish conditions relating Rashomon sets across pruning, accuracy-based and other metric-based sets, and instance removal. In particular, they characterize when trees from reduced-data sets remain in the full-dataset Rashomon set.

Theorems 3.1–3.2

  • A tree and all its descendants can be pruned when the fixed-leaf loss plus leaf penalty exceeds the Rashomon threshold, with equivalent-point errors strengthening the bound.The strengthened bound adds unavoidable misclassification loss among leaves that can still be split.Source: E Theorems and Proofs · p. 20

Theorem E.1

  • A tree is outside the ϵ-Rashomon set when the sum of the equivalent-points bounds for its left and right subtrees exceeds the threshold.The subtree bounds are each no greater than their subtree's loss plus leaf penalty.Source: E Theorems and Proofs · p. 20

Theorem 5.1

  • The Accuracy Rashomon set covers the Balanced Accuracy Rashomon set when its objective threshold is sufficiently large relative to the balanced-accuracy constraint.The proof bounds the accuracy objective over the feasible FPR–FNR region in two cases, depending on whether 2(δ − λHt) is below 1.Source: E Theorems and Proofs · pp. 21–22

Theorem 5.2

  • Under the stated assumptions on class proportions and δ − λHt, the Accuracy Rashomon set covers the F1-score Rashomon set.The proof bounds accuracy across two cases in the FPR–FNR plane.Source: E Theorems and Proofs · pp. 22, 23, 26

Theorem 5.3

  • If ϵ ≥ 2|K|/n × Obj(t∗, x, y), the optimal tree trained after removing instances K remains in the full-dataset ϵ-Rashomon set.The proof bounds the objective change between the original and reduced datasets for both the original optimal tree and the reduced-data optimal tree.Source: E Theorems and Proofs · pp. 26–27

E Theorems and Proofs

  • If ϵ ≥ ϵ′ + (2+ϵ′)|K| n×Obj(t∗,x,y), every tree in Rset(ϵ′, ˜t∗, T, x[\K,·], y[\K]) belongs to Rset(ϵ, t∗, T, x, y).This bounds how much larger the full-dataset tolerance ϵ must be than the reduced-dataset tolerance ϵ′ for the inclusion to hold.Source: E Theorems and Proofs · pp. 27–28

F Experimental Datasets

The experiments cover UCI, penguin, COMPAS, FICO, and coupon datasets. Preprocessing converts or selects features into binary representations for the experiments.

F Experimental Datasets

  • The experiments include UCI, penguin, COMPAS, FICO, and coupon datasets, with tasks including arrest prediction, loan default, and coupon acceptance.The datasets are publicly available.Source: F Experimental Datasets · pp. 28–29

F.1 Preprocessing

  • Preprocessing one-hot encodes categorical datasets, discretizes Iris features into three equal parts, and uses selected thresholds or previously discretized features for other datasets.Breast Cancer features and thresholds come from a gradient-boosted tree with 40 stumps; COMPAS and FICO use discretized binary features produced in earlier work.Source: §F.1 · p. 29
  • For coupon datasets, missing observations are removed and 15 binary features are selected using variable importance from gradient-boosted trees.The selected features are based on models with 100 depth-3 weak classifiers.Source: §F.1 · p. 29

G.1 Scalability and Efficiency of Calculating Rashomon set with TreeFARMS versus Baselines

Across the evaluated datasets, TreeFARMS found more distinct trees in the Rashomon set than the baselines and was the only method guaranteed to find the full set. It also found more in-set trees per second than every baseline.

G.1 Scalability and Efficiency of Calculating Rashomon set with TreeFARMS versus Baselines

  • The comparison used matched run times for baseline sampling and averaged baseline results across five random seeds.TreeFARMS is deterministic; Figure 10 uses the first random seed’s results.Source: §G.1 · pp. 30–31
  • TreeFARMS found more Rashomon-set trees per second than every baseline on all datasets.Source: §G.1 · p. 31
  • TreeFARMS found more distinct Rashomon-set trees than the four baselines across the evaluated datasets and was the only method guaranteed to find the full set.Figure 10 compares the trees found by each method; its legend reports how many baseline trees belong to the Rashomon set.Source: Figure 10 · p. 31, §G.1 · p. 31

G.2 Landscape of the Rashomon set

The Monk2 landscape, variable-importance estimates, and alternative-metric Rashomon sets illustrate how examining many near-optimal trees reveals variation beyond a single optimal tree.

G.2 Landscape of the Rashomon set

  • Monk2 embeddings using tree-edit, prediction, and feature-set distances show diverse root splits rather than a shared root feature.The embeddings use PaCMAP after retaining the best tree for each unique feature set.Source: §G.2 · pp. 31–32, Figure 11 · p. 33
  • The ten best Monk2 trees occupy different parts of the embedding, and the five sparsest trees with accuracy above 0.7 are also diverse.Source: §G.2 · p. 32, Figure 11 · p. 33
  • Constraining Monk2 trees to use head_shape=square but neither head_shape=round nor jacket_color=red yields trees with features unlike those on the left, even when roots match.Source: §G.2 · p. 32, Figure 11 · p. 33

G.3 Variable Importance: Model Class Reliance

  • On COMPAS, prior-count features often have high MCR+; on Bar and Coffee House, named usage features have dominant MCR+ and MCR−.Source: §G.3 · p. 33
  • Sampled model class reliance generally converged to the full-set estimate even when sampling only 1% or 5% of trees.The study tested sampling proportions of 1%, 5%, and 25%; Figure 12 also shows the full-set estimate.Source: §G.3 · p. 33, Figure 12 · p. 34

G.4 Balanced Accuracy and F1-score Rashomon set from Accuracy Rashomon set

  • The Accuracy Rashomon set includes trees for balanced-accuracy and F1-score Rashomon sets, but the accuracy-optimal tree need not optimize either metric.For balanced accuracy, one example contrasts an accuracy-optimal single-split tree with a three-leaf balanced-accuracy-optimal tree.Source: §G.4 · p. 33, Figure 13 · p. 34, Figure 14 · p. 35

G.5 Rashomon set after removing a group of samples

After removing 1% of samples, sparse near-optimal trees remained robust to the sample-distribution shift, although the optimal tree could change.

G.5 Rashomon set after removing a group of samples

  • After 1% of samples were removed, accuracy objectives on full and reduced datasets remained highly correlated, but the optimal trees could differ.Figure 15 compares the full-dataset optimal trees with optimal trees from the reduced datasets.Source: §G.5 · p. 35, Figure 15 · p. 36

Related papers

Loading 2209.08040v2…