Exploring the Whole Rashomon Set of Sparse Decision Trees
Authors: Rui Xin
Chudi Zhong
Zhi Chen
Takuya Takagi
Margo Seltzer
Cynthia Rudin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Rashomon Set
Sparse Decision Trees
Interpretability

Abstract: 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.

Exploring the Whole Rashomon Set of Sparse Decision Trees
Rui Xin'
Chudi Zhong
Zhi Chen'
Takuya Takagi²
Margo Seltzer?
Cynthia Rudin
Duke University Fujitsu Laboratories Ltd. The University of British Columbia
Srui.xin926, chudi zzong, zhi Jhw.eiehhukeeeee.. edu
takagi. aakagi.takuya@furr takuya@fujitss.coom com, mseltzer@cs. .ut...ubccc.... ca, cynthia@cs.. duke.
Abstract
In any given machine learning problem, there might be many models that explain the data almost equally well. However, most learning algorithms return only one these models, leaving practitioners with no practical way to explore alternative models that might have desirable properties beyond what could be expressed by a loss function. The Rashomon set the set of these all almost-optimal models. Rashomon sets be large in size and complicated in structure, particularly for highly nonlinear function classes that allow complex interaction terms, such 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 non-trivial problem with highly nonlinear discrete function class, This allows the user an unprecedented level of control over model choice among all models that 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: can be used 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 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 new lens, enabling users to choose models rather than be at the mercy of an algorithm that produces only single model.
Introduction
The Rashomon set is the set of almost-equally-optinn models 2 Rashomon sets were named for the Rashomon effect Leo Breiman, whereby many equally good models could explain the data well (3]. The Rashomon effect helps understand that there is not just one "best" explanation for the data, but many diverse equally predictive models. The existence of Rashomon sets has important practical implications: practitioners may not want to use the single model from the Rashomon set that was output by a machine learning algorithm. Instead, they may want to explore the Rashomon set to find models with important properties, such as interpretability. faimesss, or they may want to choose model that agrees with possible causal hypotheses, monotonicity trends, ease of caleulation, simply domain intuition. In light of viewing the learning problem this way, the whole paradigm that machine learning should provide only one "optimal" model makes little sense:
of specific variables,
Equual Contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

perhaps we should turn the optimization problem into a feasibility problem, and insist that we find all setooiiimmteeeuuuallly
models and allow the user to choose among them. Perhaps the tiny sacrifice of small amount of empirical risk can make the difference between model that can be used and one that cannot.
While wishing for full Rashomon sets is easy, actually finding them can be extremely difficult for nonlinear function classes. Consider sparse decision trees, which is the focus of this work. Trees have wildly nonlinear relationships between features, where every leaf of depth d represents an interaction between features of order d. Even for trees of depth at most 4 with only 10 binary features, the number of possible trees (the size of the hypothesis space) is more than 9.338 x 10 models [4]. This complexity explains why no previous work has been able to provide full Rashomon sets for optimal sparse trees, nor for any non-trivial function class with a large number of interactions.
While the hypothesis space of sparse trees is huge, the Rashomon set of good sparse trees is a small subset of it. In fact, the Rashomon set is often small enough to store, even if the function class itself too large be enumerated. Thus, rather than enumerate all sparse trees and store just those in the Rashomon set, we use analytical bounds to prove that large portions of the search space do not contain any members of the Rashomon set and can safely be excluded. This allows us to home in on just the portion of the space containing the Rashomon set. We store the Rashomon set in a specialized data structure, which permits memory- -fficciett storage and easy indexing of the Rashomon set's members. The combination of these strong bounds and efficient representation enable us to provide the first complete enumeration of the Rashomon set for sparse decision trees on real-world datasets. Our method is called TreeFARMS, for "Trees FAst RashoMon Sets."
The Rashomon sets compute give us an unprecedented lens through which to examine learning problems, We can now directly answer questions such as: Size: How large is the Rashomon set? Does its size vary between datasets? Variable importance: How does variable importance change among trees within the Rashomon set? Perhaps this will give us a better sense of how important a variable is to dataset, rather than just to one model. Variability in predictions: Do the models in the Rashomon set all predict similarly on the data? Robustness: How does the Rashomon set change if we remove a subset of data? Rashomon sets for other losses: How can we construct Rashomon sets for balanced accuracy and Fl-score? In this work, we show how the answers to these questions can be computed directly after running our algorithm for finding the Rashomon set.
2 Related Work
Rashomon sets. Leo Breiman 3 proposed the Rashomon effect to describe the fact that many models exist for the same data. Rashomon sets occur in healthcare, finance, They have been used for decision making 7 and robustness of estimation 8) Semenova et al. show that when the Rashomon set large, models with various important properties such as interpretability and fairness can exist inside it. Other works use the Rashomon set to study the range of variable importance among all well-performing models 12 9.. which provides a better sense of how important a variable is in general, rather than how important it is to specific model. Other works find diverse near-optimal solutions for integer linear programs [10 Kissel et al. [12 find collections of accurate models through model path selection. They collect models using forward selection and use these as a collection of accurate models. Our work differs from these works in that we find the full Rashomon set of class of sparse decision trees real problems.
criminal justice, justice, etc. [5] 6
enumerates trees built from greedy top-down decision tree induction. Our method differs as our trees are not built using greedy induction but by searching the entire binary decision tree space, and our goal is to enumerate all well pell-oerf trees, not simply the features in the greedy trees. Hara et al. [15 [6] enumerate linear models and rule lists or rule sets in descending order of their objective values. However, they find only one model for any given set of itemsets (association rules). Thus, they enumerate and store only small subset of the Rashomon set.
Model enumeration. Ruggieri 13 14
Decision trees. Decision tree algorithms have a long history 17
but the vast majority 18 19
of work on trees has used greedy induction 120, 21 to avoid solving the NP-complete problem of finding an optimal tree [22]. However, greedy tree induction provides suboptimal trees, which has propelled research since the 1990s on mathematical optimization for finding optimal decision trees 4 23
26 28 29 3D as well as dynamic programming with branch-and-bourd
31
32
33
34]
We refer readers to two recent reviews of this area [35 36).

---

Bayesian frees. Bayesian analysis has long aimed to produce multiple almost-optimal models through sampling from the posterior distribution. While it might reasonably seem like a method such as BART [37 or random forest (38 might sample effectively from the Rashomon set, as our experiments show (Figure T]. they do not.
3 Bounds for Reducing the Search Space
We denote the training dataset as (x;;, y:) ) F=1 where E 13P are binary features. Our notation uses yi E {0. 1) as labels, while our method can be generalized to multiclass classification as well. Let f(t,,,,, x,)) predicted labels given t. We define the objective function as the combination of the misclassification loss and sparsity penalty the number of leaves: Obj(t, x, y) = E(t, + All,, where He is the number of leaves in tree and is a regularization parameter.
Σ [ūx # yi] be the loss of tree t on the training set, where {0e [0 are
Definition 1. fe-Rashomon set) Let heet be benchmark model or reference model from T, where T is a set of binary decision trees. The c-Rashomon set is a set of all trees t E T with Obj x) at most (1 + c) (bj(tret; X, y):
Reelle, leef 7) = (L
(I)
For example, we permit models within 2% of the reference objective value, we would set to be 0.02. Note that we use Rea(e) to represent Ree( (e, tee. T) when tut and T are clearly defined. We use 0.- := (1 + e) x Obj x. y) to denote the threshold of the Rashomon set. Typically, the reference model is empirical risk minimizer tee arg mintemrs Obj x. y). Recent advances in decision tree optimization have allowed us to find this empirical risk minimizer, specifically using the GOSDT algorithm 31 32.
Our goal is to store Reet fred, T), sample from it, and compute statistics from it.
Customized analytical bounds, leveraging tools from [31 help reduce the search space for Rashomon set construction. As every possible tree is being grown in the process of dynamic programming, some of its leaves will have been determined ("fixed"), and others will not have yet been determined ("unfixed"). Bounds for these incomplete trees compare two quantities: the performance that might be achieved in the best possible case, when every unfixed part of the tree has perfect classification for all of its points, and 0., the threshold of the Rashomon set. If the first is larger - i.e., worse than de. we know that extensions of the tree will never be in the Rashomon set. Each partial tree t (that is, tree that can be extended) is represented in terms of five variables: tax are the "fixed" leaves we do not extend during this part of the search (there will be a different copy of the tree elsewhere in the search where these leaves will potentially be split), dūs are the labels of the data points within the fixed leaves, (splis are the "unfixed" leaves we could potentially split during the exploration of this part of the search space (with labels dsplit) and H, is the number of leaves in the current tree. Thus, our current position in the search space is a partial tree / = (láx, Ōáx laplits Osplit Hz). The theorems below allow us exclude large portions of the search space.
Theorem 3.1. (Basic Rashomon Lower Bound) Let te be the threshold of the Rashomon set. Given a tree = (tax, Sax Explia: Seplits Ht). let b(tnx x, x,y) := E(trx) X. + XH, denote the lower bound of the objective for tree I. If b(lax; y) > Os, then the tree I. and all of its children are not in the e- C-Rashomon set.
We can tighten the basic Rashomon lower bound by using knowledge of equivalent points (3). Data points are equivalent they have exactly the same feature values. Let Q be set of leaves. Capture is an indicator function that equals 1 if x; falls into one of the leaves in Ω and O otherwise, in which case we say that cap(x,, S2) = 1. Let 6, be set of equivalent points and qu be the minority class label among points in cu. A dataset consists of multiple sets of equivalent points. Let feu V enumerate these sets. The bound below incorporates equivalent points.
Theorem 3.2. (Rashomon Equivalent Points Bound) Let 0 be the threshold of the Rashomon set. Let t be a tree with leaves fix txpli and lower bound b(tax: x. y). Let besgive (tsplin x, y) := -E Σu= cap(x,, taplis) A 1[x; E ew] A 1[y qu] be the lower bound on the misclassification loss of the unfixed leaves. Let B(t, y) y) == b(tnx; x. + bequio (tsplit x,y) be the Rashomon lower bound of t. If (t,,x,y) 0., tree and all its children are not in the e- E-Rashomon set.
We can use this bound recursively on all subtrees we discover during the process of dynamic programming, If, at any time, we find the sum of the lower bounds of subproblems created by split
3

---

exceed the threshold of the Rashomon set, the split that led to these subproblems will never produce any member of the Rashomon set. This is formalized in the Rashomon Equivalent Points Bound for Subtrees, Theorem E.1 in Appendix [ which dramatically helps reduce the search space. We also use the "lookahead" " bound, used in GOSDT 31, which looks one split forward and cuts all the children of tree t if x,,, + + O--
Storing, Extracting, and Sampling the Rashomon Set
The key to TreeFARMS's scalability is a novel Model Set representation. The Model Set (MS) is set of hierarchical maps; each map is a Model Set Instance (MSI). Conceptually, we identify MSI by a <subproblem, objective> pair; in reality, we use pointers to improve execution time and reduce memory consumption. A MSI can represent a terminal (leaf) node, an internal node, or both (See Appendix AA]. A leaf MSI stores only the subproblem's prediction and the number of false positives and negatives (or false predictions of each class in the case of multiclass classification). An internal MSI, M, is a map whose keys are the features on which to split the subproblem and whose values are arry of pairs, each referring to left and right MSIs whose objectives sum to the objective of M. TreeFARMS' efficiency stems from the fact that the loss function for decision trees takes discrete number of values (approximately equal to the number of samples in the training data set), while the number of trees in the Rashomon set is frequently orders magnitude larger. Therefore, many trees (and subtrees) have the same objective. By grouping together trees with the same objective, we avoid massive amounts of data duplication and computation. See Appendix A for an example. Equipped with these data structures, we now present our main algorithm.
4.1 TreeFARMS Implementation
We implement TreeFARMS in GOSDT 31 which uses a cennamic-proraamminn wwatiiiinnn-ttttheeee with-bounds formulation to find the optimal sparse decision trees, Each subproblem is defined by support set 8a {{0, 13"d such that the 7th element is 1 iff x; satisfies the Boolean assertion a that corresponds to a decision path in the tree. For each subproblem in the dynamic program, GOSDT keeps track of upper and lower bounds on its objective. It stores these subproblems and their bounds a dependency graph, which expresses the relationships between subproblems. TreeFARMS transforms GOSDT in two key ways. First, while searching the space, TreeFARMS prunes the search space by removing only those subproblems whose objective lower bound is greater than the thresholds defined by the Rashomon set bound, O., rather than GOSDT's objective-based upper bound. Second, rather than finding the single best model expressed by the dependency graph, TreeFARMS returns all models in the Rashomon set defined by 8z.
4.2 Extraction Algorithm
TreeFARMS (Alg. D constructs the dependency graph using the bounds from Section
3 and Extract
(Alg. 2) extracts the Rashomon set from the dependency graph.
TreeFARMS (Algorithm I): Line 1: Call GOSDT to find the best objective. Line 2: Using the best objective from Line 1, compute 0., as defined in Definition I Lines 3-6: Configure and execute (the modified) GOSDT to produce dependency graph containing all subproblems in the Rashomon set. Lines 7-10: Initialize the parameters needed by extract and then call it to extract the Rashomon set from the dependency graph.
Extract (Algorithm 2): We present an abbreviated version of the algorithm here with the full details in Appendix B Line I: Check to see if we already have the Rashomon set for the given problem and scope: if so, return immediately. Lines 2-3: If we can make a prediction for the given subproblem that produces loss less than or equal to scope (using Theorems 3.] and 3.2p. then the leaf for this subproblem should be part of trees in the Rashomon set, so we add it to our Model Set. Lines 4-12: Loop over each feature and consider splitting the current problem on that feature. Lines 5-6: Skip over any splits that either do not appear in the dependency graph or whose objectives produce a value greater than scope (using Theorem E. Lines 7-9: Find all subtrees for left and right that should appear in trees in the Rashomon set, and construct the set of MSI identifiers for each. Lines 10-12. Now, take the cross product of the sets of MSI identifiers. For each pair, determine if the sum of the objectives for those MSI are within scope (using Theorem E.I. D. If so, we add the left/rghht pair to

---

the appropriate MSI, creating a new MSI if necessary. When this loop terminates, all trees in the Rashomon set are represented in MS.
4.3 Sampling from the Rashomon Set
If we store the entire Rashomon set in memory, then sampling is unnecessary. However, sometimes the set is too large to fit in memory (e.g.. the COMPAS data set [40] with a regularization of 0.005 and Rashomon threshold that is within 15% of optimal produces 10 trees). Our Model Set representation permits easy uniform sampling of the Rashomon set that can be used to explore the set with much lower computational burden. Appendix presents sampling algorithm.
Algorithm TreeFAARM((x,y + Rest
// Given dataset y), X, and return the set, Ryer of all trees whose objective in t..
1: opt gosdllopttimll_ohe
X) // Use GOSDT to find opl, the objective of the optimal tree. 0g opt. (1 + Compute O., which is the threshold of Rashomon Set.
3: gosdt.hest_cure cesst__ureet____ _obj <- 0. // Set and fix GOSDT's s best current objective R to 0g
II Disable leaf accuracy bound and incremental accuracy bound GOSDT (see Algorithm (37)).
which are used to find optimal trees but could remove near-optimal trees in the Rashomon set gosdt.leaf
5: cecu_aaccuracy + False // Disable leaf accuracy bound.
_accuracccccccaaaac f- False // Disable incremental accuracy bound. 6: gosdttfit(x,, y. A) // Run the branch-ani uand-bound algorithm using new settings of bounds. graph() // Return dependency graph obtained from branch-and aand-bunddddd..a 8: global MS < R} // Initialize Rashomon Model Set MS, which is global data structure.
7: G + -gooddt.get (osdd.ger_graph()
9: P < 'ones(y ( // Create the subproblem representation for the entire dataset.
10: extract(G, P, (2) ) // Fill in MS with trees in the Rashomon set.
11: return MSp
Algorithm 2 extract(G, sub, scope) (Detailed algorithm in Appendix
B
// Given a dependency graph, G; subproblem, sub; and maximum allowed objective value, scope, populate the global variable MS with the Rashomon set for sub within scope.
// Check if we have already solved the subproblem sub. SOLVED is presented in Alg.
1: if SOLVED(MS, sub, scope) then return
2: if G[sub] I scope then Check if we should create leaf. (Theorems 3.1 and 3.2
3: MS t- MS U newLeaft sub) // newLeaf is presented in Alg. 3
Consider splits on each feasible split feature skipping those not G or with bounds too large.
4: for each feature E (1,M)do do subi, sub, + splil(sub..j)
6: if either subi, sub, not in G G[subi] + G[sub,]] > scope then continue
// Find Model Sets Instances for left and right.
7:
extract G, subt, scope G[sub,]]
8: extract( sub,, scope - G[subi]
9:
left, right +- MS .MS.ub
10:
for each (m,,,,)) E (left x right) do // Consider cross product of left/right MSI. // Skip trees with objective outside of scope. (Theorem) E.I
11: if (m)( + obj(m,,) > scope then continue
12: MS MS U add( obj(mu) obj(m,), ma, my) // Add pair Model Set.
// MS now contains all MSI for sub with objective less than or equal to scope.
13: return
Applications of the Rashomon Set
Besides allowing users an unprecedented level of control over model choice, having access to the Rashomon set unlocks powerful new capabilities. We present three example applications here.
5

---

5.1 Variable Importance for Models in the Rashomon Set via Model Class Reliance
The problem with classical variable importance techniques is that they generally provide the impor- tance of one variable to one model. However, just because variable is important to one model does not mean that it is important general. To answer this more general question. we consider model class reliance (MCR) [2]. MCR provides the range of variable importance values across the set of all perforrrfog models. MCR_ and MCR, denote the lower and upper bounds of this range, respectively. A feature with a large MCR- is important in all well-perf models; feature with small MCR is unimportant to every well- well-performing model. Past work managed to calculate MCR only for convex loss in linear models [2]. For decision trees, the problem is nonconvex and intractable using previous methods. A recent work [41) estimates MCR for random forest, leveraging the fact that the forest's trees are grown greedily from the top down; the optimized sparse trees we consider are entirely different, and as we will show, many good sparse trees are difficult to obtain through sampling. Since TreeFARMS we can directly calculate variable importance for every tree in the Rashomon set and then find its minimum and maximum compute the MCR, as described in Appendix D See Section 6.2 for the results. If the Rashomon set is too large to enumerate, sampling (Section can be used to obtain sample estimates for the MCR (shown in Section 6.2).
enumerate the whole Rashomon set of decision trees,
5.2 Rashomon Sets Beyond Accuracy: Constructing the Rashomon Set for Other Metries
For imbalanced datasets, high accuracy is not always meaningful. Metrics such as balanced accuracy and Fl-score are better suited for these datasets. We show that, given the Rashomon set constructed using accuracy, we can directly find the Rashomon sets for balanced accuracy and Fl-score.
Let qt be the proportion of positive samples and q be the proportion of negative samples, i.e., qt + q-= 1. Let Gmin = min(1) q)) and Gmax == max(g+ ..)). Let F PR and FNR be the false positive and false negative rates. We define the Accuracy Rashomon set as Ag == {t E T q FPR + q FNR + AHf, S 0}. where 0 the objective threshold of the Accuracy Rashomon set, similar to 0, in Section 3 The next two theorems guide us to find the Balanced Accuracy or FI-Score Rashomon set from the Accuracy Rashomon set. Their proofs are presented Appendix
We use d in these theorems to denote the objective threshold of Balanced Accuracy or F1-
Rashomon sets.
Theorem 5.1. (Accuracy Rashomon set covers Balanced Accuracy Rashomon set) Let Bg = {t
T FPR, FNR, + AHI, S 88 be the Balanced Accuracy Rashomon set. If
2
02 min (24 9max + (25 - 1) + +(1 1-2qmin )22h)
where d is the depth limit, then Vt E Bs, t E Ag-
Theorem 5.2. (Accuracy Rashomon set covers F1-Score Rashomon set) Let
FPRR - FNRR Fs Fs:= IET 29 + + - FNFNR,
+ +AII {o]
be the Fi-score Rashomon set. Suppose qt E (0, a E (0,1), and 5 AH, E (0, If
(8- 0 2 min mmxx (7-5 8 then VL E Fs, E Ag-
12- A24), 166 < v2- 1] 26 1 2 v2 1] + 3 - 2v2)).
We can use Theorems and 5.2 above to find trees in the Balanced Accuracy or F1-score Rashomon set directly by searching through the Accuracy Rashomon set with objective threshold 0 that satisfies the inequality constraint. In our implementation, we first use GOSDT to find the optimal tree w.r.t. misclassification loss and then calculate its objective w.r.t. balanced accuracy and Fl-score. Then we set ō and the corresponding 9. This guarantees that the Rashomon sets for balanced accuracy and F1 Fl-score objective not empty. Experiments in Section 6.3 illustrate this calculation.
5.3 Sensitivity to Missing Groups of Samples
Though sparse decision trees are usually robust (since predictions are made separately in each leaf), are also interested in how sample or group of samples influences all well-performing models

---

(i.e.. whether this subset of points is inftuential (4]]. Influence functions cannot be calculated for decision trees since they require differeeniaailityy. The following two theorems help us find optimal or near-optimal trees for dataset in which a group of instances has been removed by searching through the Rashomon set obtained from the full dataset. Here, we consider the misclassification loss.
Let E be the optimal tree trained on the reduced dataset (. ( where K is a set of indices of instances that we remove from the original dataset. Let K| denote the cardinality of the set K. Overloading notation to include the dataset, let (e, t", T, y) Raeele,t", T) (see Eq (T) be the Rashomon set of the original dataset, where 1" is the optimal tree trained on the original dataset. We define the e' c'-Rashomon
the reduced dataset as
R (E', i", T, XINK,) M Obj(t, X(,.) vnan) S( (1 (.OOb,C,,,,,,,MM. ((KKA)-KKK))
Theorem 5.3. (Optimal tree after removing group of instances is still in full-dataset Rashomon set) I ox x.y) then i" E BRaetee 1", ; y)
k|
Now we consider not only the optimal tree on the reduced dataset but also the near-optimal trees. Theorem 5,4. (Rashomon set after removing a group of instances is within full-dataset Rashomon [2+2]|K]
set) If 2 c'+ "xObjit" x,y then Vt E Re ,,,,",TTxe, T. E Reeele, ,T,,,),
Experiments
Our evaluation answers the following questions: 1. How does TreeFARMS compare baseline methods for searching the hypothesis space? ($6.T), 2. How quickly can we find the entire Rashomon set? ($6.1). 3. What does the Rashomon set look like? What can we learn about its structure? ($..2
4. What does MCR look like for real datasets? ($6.2), 5. How do balanced accuracy and Fl-score
Rashomon sets compare to the accuracy Rashomon set? ($6 6..3.. and 6. How does removing samples affect the Rashomon set? 6.4)
Finding the Rashomon set is computationally difficult due to searching an exponentially growing search space. We use datasets from the UCI Machine Learning Repository [Car Evaluation, Congres- sional Voting Records, Monk2, and Iris, see 43) a penguin dataset (44), a criminal recidivism dataset ICOMPAS, shared by 40). the Fair Isaac (FICO) credit risk dataset [45) used for the Explainable MI. Challenge, and four coupon datasets (Bar, Coffee House, Cheap Restaurant, and Expensive Restaurant) 46) that come from surveys. More details are in Appendix F
6.1 Performance and Timing Experiments
Our method directly constructs the Rashomon set of decision trees of a dataset. While, to the best of our knowledge, there is no previous directly comparable work, there are several methods one might naturally consider to find this set. One might use methods that sample from the high-posterior region of tree models, though we would not know how many samples need to extract the full Rashomon set. Thus, the first baseline method we consider is sampling trees from the posterior distribution of Bayesian Additive trees [47 48) We used the R package BART (37), setting the number of trees in each iteration to 1. Many ensemble methods combine a diverse set of trees. The diversity in this set comes from fitting on different subsets of data. Trees produced by these methods would be natural approaches for finding the Rashomon set. We thus generated trees from three different methods (Random Forest
38 CART 20). and GOSDT 31). on many subsets of our original data.
Figure compares the Rashomon set with the four basclines on the Monk2, COMPAS, and Bar datasets. We show the number of distinct trees versus the objective value. We sort the trees with respect to their objective values, so all methods show an increasing trend. TreeFARMS (in purple) found orders of magnitude more distinct frees in the Rashomon set than any of the four baselines on all of the datasets. The baseline methods tend to find many duplicated trees. For example, in 46 seconds, BART finds only 488 distinct trees Monk2, whereas TreeFARMS found 108. Other methods find ~20,000 distinct trees. Most trees found by the baselines are not even in the Rashomon set, i.e., most of their trees have objective values higher than the threshold of the Rashomon set.
[ggure[Ssoww run times, specifically, Fig. ( shows that TreeFARMS finds trees in the Rashomon set at a dramatically faster rate than the basclines. Appendix G.I has more results.
7

---

Rashomon Set us Baselines (Monk2)
Reshoman Set Beselines
Rashamon Set Baselines (Bar)
[COMPAS]
BART (3460)
0.32
DUIT (28)
SART 126702250
RF 12007333
0.50-
Rf (19g107)
0.60
RF (12 (121844356)
chnteempping (300316))
colteammiing (134004)
CAiT complra (186671781)
0.6
0.40
(68)
(10r12)
objerbbv
0.5
Bourd faut
0.bb
Bound of faat
12033
0.50
Sounsl fldd.
0.44
0.4
0.40
0.3
15a
104
104 16"
sorted
sonted Indices
Indices
Figure Comparison of trees in the Rashomon set (A = 0.01, = 0.1) and trees generated by baselines. Trees in the Rashomon set have objective below the dashed line. (A/B) in legend represents that A trees among B trees trained by the baseline are in the Rashomon set. For example, RF (196/767) means 196 trees among 767 distinct trees trained by Random Forest are in the Rashomon set. Indices are in log scale to accommodate differences in orders of magnitude of tree counts among methods.
The takeaway from this experiment is that natural baselines find at best tiny sliver of the Rashomon set. Further, the way we discovered this was to develop a method that actually enumerates the Rashomon set. We would not have known, using any other way we could think of, that sampling- based approaches barely scratch the surface of the Rashomon set.
(0) A-0.02
c-0.05
(C) irees
Rewhamen wel per second
COMPAS
Bar-7
10
Alarrihir Potaset
Mark2
COMPAS
Pengu
TreeFARiss
$7458.10
19102.16
Lar Evaluation
Time
L03
BART
0.08
1.34.0.1 0.17
0.15
Congressional wezing
0.00
2.34
0.78
RCD
10
CART samping 0.20
2.117
0.08
Nonk2
GOSDT sampling
0.04
2:30
0.05
0.05
0.30
0.15
0.03
0.02
0.05
0.04
Figure 2: (a), (b) Run times for computing Rashomon sets as a function of and À respectively. (c) Number of trees in the Rashomon set found by each method per second. The total time is approximately 46, 3, and 270 seconds for Monk2, COMPAS, and Bar respectively. TreeFARMS is the only algorithm guaranteed to find all trees in the Rashomon set. (Appendix GhT results for all the datasets.)
6.2 Variable Importance: Model Class Reliance
Without TreeFARMS, it has not been possible to compute overall variable importance calculations such as MCR for complex function classes with interaction terms such as decision trees. Here, we exactly compute MCR on the COMPAS and Bar datasets (see Figure 3). For the COMPAS dataset (left ffattuess related to prior counts generally have high MCR which means these features very important for some trees in the Rashomon set. For the Bar dataset (right subfigure). features "Bar_ 113" and "Bar 4-8" have dominant MCR, and MCR compared with other features, indicating that for all well-performing trees, these features the most important. This makes sense, since people who go to bars regularly would be likely to accept a coupon for a bar.
Sampling for MCR: Sampling has massive memory benefit over storing the whole Rashomon set, because we do not need to store the samples. Since MCR requires computing extreme value statistics (max and min over the Rashomon set), it poses test for the sampling technique posed in Section 4.3 Figure 3 shows sampled MCR and its convergence to true MCR. 25% of the samples are usually sufficient. More results are shown in Appendix G.3
6.3 Balanced Accuracy and F1-score Rashomon set from Accuracy Rashomon set
As discussed in Section 5.2 Rashomon sets of balanced accuracy and FI-Score are contained in the Rashomon set for accuracy. Figure shows trees in the Accuracy Rashomon set, which covers the Balanced Accuracy Rashomon set (Teft) and Fl-score Rashomon set (right). The black dashed line indicates the corresponding objective thresholds and blue dots below the dashed line are trees
8

---

MCR (COMPAS)
MCR (Bar)
3
Chidrennumber maritalstatus Sinje
sarpple 1%
proors:2-3
ed vdtaration Graduata degres
carple 21%
carple 3%
1rors:=
gender, Femele
carple 100%
priors:-0-
passanger, Kidrs
MR coooiiiaal bre
passangor Friendii
juvenile 0
55
pwentee-felrriess-
expiration 1d
age:<46-
Restaurant20 1050 4-1-
agex226
CarryAwey 4-8
age:<23-
Bar g18
agc:<21-
1-3
sexiFemale
Bar
135
125
model class rellance
Figure 3: Variable Importance: Model class reliance on the COMPAS and Bar (A 0.01, e = 0.05). Red dots indicate the model reliance (variable importance) calculated from the optimal tree. Each line connects MCR and MCR, + showing the range of variable importance among all good models.
bacc (Takeaway Food N=598, P=1682) 1-0.005, trees-8479
(Cheap Restaurant N=772 P=1881)
A-
0.000, trees-4039 4039
Esample trees with oytional ace objectiat
(PP/ FNMP (lenves)
Thee with optinal at obpective
0.155
expre in don'
biece sbyertive
Upper
Thee with optinal baco dbsective
Root node proskt
11 objertive
0.133
0.125
0.17
Loder sourd of ret
destintionsoo urgent piace
Timeadge ppri
time:
0.199
0.125
Smandam
dinctionnaaee
a1130
tinanipm (all
mingk
a117%
027
toCospari
ecjective (FP-FMY(P--) + nleaves)
objective
(IF--FNDEP4)) nleaves)
Figure 4: Example of Balanced Accuracy Rashomon set (left) and FI-Score Rashomon set (right). # trees indicates the number of trees in the Balanced Accuracy or Fi-score Rashomon set. Trees in the yellow region have optimal accuracy objective and trees in the green region have optimal balanced accuracy or Fi-score objective.
in these Rashomon sets. Note that the tree with the minimum misclassification objective is not the tree that optimizes other evaluation metrics. For example, in the left subfigure, single root node that predicts all samples as has the optimal accuracy objective (in yellow), while another 6-leaf tree minimizes the balanced accuracy objective (in green). Actually, many trees have better balanced accuracy objective than the tree that minimizes the accuracy objective. A similar pattern holds for the Fl-score Rashomon set (see right subtigure). Some trees that have worse accuracy objectives are better in terms of the Fl-score objective. More figures are shown in Appendix G.4
reduced rset (Expensive Restaurant) remove 1% samples with excensive restaurant A-0.01, # trees-144 141
reduced rset (Expensive Restaurant] remove 1% samples with incomes- 12500
SCC objective on the reduced dataset
SCc objective on the P0000-0 detaset
A-0.01, trees-263
BA24
0422
Optinall afar nroe 1S Lor Curphite sa 1250
Ia Tran
accugstion SEmpiE!
Opt afst 15 cando exparssi restarae
0.24
0402
0.02-
9422
0404
6425
6422 8:400
0.06
0402
0/04
B405
0400
0,06 6432
#Cc obyective on the full deleset
Btc objective on the full deleset
Figure Example Rashomon sets and optimal trees after we remove the 1% of samples with "number of times to expensive restaurant 2 4" (left) and "income 2 $12,500" (right) on the Expensive Restaurant dataset. The optimal tree on the full dataset is shown in the gray region and optimal trees on the corresponding reduced datasets are in the orange region.

---

6.4 Rashomon set after removing group of samples
shows Shows accuracy objective on full dataset versus the objective on the reduced dataset after 1% of samples with "number of times to expensive restaurant 2 4" (left) and "income 2 $12,500" (right) are removed. The black dashed line indicates the objective threshold the reduced Rashomon set and blue dots below the dashed line trees in the reduced Rashomon set. As both scatter plots show high correlation between the accuracy objective on the full dataset and the reduced dataset, indicating sparse near-optimal trees robust the shift in sample distribution. In other words, well well-perfonning trees trained on the full dataset are usually still well-performing some samples removed. Optimal trees on the reduced dataset might be different, comparing the trees in the orange region and blue region. More results are shown in Appendix G.5
see,
by
7 Conclusion
This work opens the door to interesting discussions on variable importance, distributional shift, and user options. By efficiently representing all optimal and slightly suboptimal models for complex nonlinear function classes with interactions between variables, we provide a range of new user- centered capabilities for machine learning systems, and new understanding of the importance of variables. Importantly, TreeFARMS allows users choice rather than handing them single model.
Acknowledgements
We thank the anonymous reviewers for their suggestions and insightful questions. The authors acknowledge funding from the National Science Foundation under grants IIS-2147061 and IIS- 2130250, National Institute Drug Abuse under grant RO1 DA054994, Department of Energy under grants DE-SC002 1358 and DE-SC0023194, and National Research Traineeship Program under NSF grants DGE-2022044 and CCF-1934966 We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), Nous remercions le Conseil de recherches en sciences naturelles en génie du Canada (CRSNG) de son soutien.
Code Availability
Implementations of TreeFARMS is available at http:///ghhll.commmueeeyssgpgpts
References
[1] Lesia Semenova, Cynthia Rudin, and Ronald Parr. On the existence of simpler machine learning models. In ACM Conference on Fairness, Accountability, and Transparency (ACM FAccT), 2022.
[2] Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models are wrong, but many are useful: Learning a variable's importance by studying an entire class of prediction models simultaneously. Journal of Machine Learning Research, 20(177): 2019.
[3] Leo Breiman. Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical Science, 19(3):199-29) 2001.
[4] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[5] Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al. Under- specification presents challenges for credibility in modern machine learning. arXiv preprint arXiv:201 1.03395, 2020.
[6] Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification. In International Conference Machine Learning, pages 6765-6774, PMLR, 2020.
10

---

[7] Theja Tulabandhula and Cynthia Rudin. Robust optimization using machine learning for uncertainty sets. arXiv preprint arXiv:1407.1097, 2014.
[8] Beau Coker, Cynthia Rudin, and Gary King. A theory of statistical inference for ensuring the robustness of scientific results. Management Science, 2021.
[9] Jiayun Dong and Cynthia Rudin. Exploring the cloud of variable importance for the set of all good models. Nature Machine Intelligence 2(12):1108224, 10-824, 2020.
[10] Emilie Danna, Mary Fenelon, Zonghao Gu, and Roland Wunderling. Generating multiple solutions for mixed integer programming problems. In International Conference Integer Progrumming and Combinatorial Optimization, pages 280-294. Springer, 2007.
[11] Izuwa Ahanor, Hugh Medal, and Andrew C Trapp. Diversitree: Computing diverse sets of near- optimal solutions to mixed-intege -nttger optimization problems. arXiv preprint arXiv:2204.03822, 2022.
[12] Nicholas Kissel and Lucas Mentch. Forward stability and model path selection. arXiv preprint arXiv:200303462. 2021.
[13] Salvatore Ruggieri. Enumerating distinct decision trees. In International Conference on Machine Learning, pages 2960-2968. PMLR, 2017.
[14] Salvatore Ruggieri. Complete search for feature selection in decision trees. Journal of Machine Learning Research, 20:10411, 2019.
[15] Satoshi Hara and Takanori Machara. Enumerate lasso solutions for feature selection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[16] Satoshi Hara and Masakazu Ishihata. Approximate and exact enumeration of rule models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[17] James N Morgan and John A Sonquist. Problems in the analysis of survey data, and proposal. Journal of the American Statistical Association, 18(302):415-44 434, 1963.
[18] Harold J. Payne and William S. Meisel. An algorithm for constructing optimal binary decision trees. IEEE Transactions on Computers, 26(09):905-916, 1977.
[19] Wei-Yin Loh. Fifty years of classification and regression trees. International Statistical Review, 82(3):329-348, 2014.
[20] I. Breiman, JH Friedman, R Olshen, and CJ Stone. Classification and Regression Trees. Wadsworth, 1984.
[21] J Ross Quinlan. C 4.5: Programs for machine learning. The Morgan Kaufmann Series in Machine Learning, 1993.
[22] Hyafil Laurent and Ronald I. Rivest, Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15-17, 1976.
(23) Kristin P Bennett and Jennifer A Blue. Optimal decision trees. Rensselaer Polytechnic Institute Math Report, 214:24, 1996.
[24] Alireza Farhangfar, Russell Greiner, and Martin Zinkevich. A fast way to produce near-optimal fixed-depth decision trees. In Proceedings of the 10th international symposium artificial intelligence and mathematics (ISAIM-2008), 2008.
[25] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 10697): 1082, 2017.
[26] Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using binary lin- ear program formulation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1625-1632, 2019.
11

---

[27] Matheus Guedes Vilas Boas, Haroldo Gambini Santos, Luiz Henrique de Campos Merschmann, and Greet Vanden Berghe. Optimal decision trees for the algorithm selection problem: in- teger programming based approaches. International Transactions in Operational Research, 28(5):2759-2781 27811, 2021.
[28] Oktay Günlük, Jayant Kalagnanam, Minhan Li, Matt Menickelly, and Katya Scheinberg. Opti- mal decision trees for categorical data via integer programming. Journal of Global Optimization, pages 1-28, 2021.
[29] Sina Aghaci, Andrés Gómez, and Phebe Vayanos. Strong optimal classification trees. arXiv preprint arXiv:2103.15965, 2021.
[30] Nina Narodytska, Alexey Ignatiev, Filipe Pereira, Joao Marques-Sinn Silla, and IS RAS. Learning optimal decision trees with SAT. In IJCAI, pages 1362-1368, 2018.
[31] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pages 6150-6160. PMLR, 2020.
[32] Hayden MaTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast sparse decision tree optimization via reference ensembles. In AAAI Conference on Artificial Intelligence, 2022.
[33] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and- search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3146-3155 2020.
[34] Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J Stuckey. Murtree: optimal classification trees via dynamic programming and search. Journal of Machine Learning Research, 23(26): 1-47, 2022.
[35] Emilio Carrizosa, Cristina Molero-Río. and Dolores Romero Morales. Mathematical optimiza- tion classification and regression trees. Top, 29(1):5-33, 2021.
[36] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and grand challenges. Statistics Surveys, 16:1-85, 2022.
[37] Rodney Sparapani, Charles Spanbauer, and Robert McCulloch. Nonparametric machine learning and efficient computation with Bayesian additive regression trees: The BART R package. Journal of Statistical Software, 97(1):1-66, 2021.
[38]
Leo Breiman. Random forests. Machine learning, 200))
[39] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18:1 18:1-78, 2018.
[40] J. Larson, S. Mattu, L. Kirchner, and J. Angwin. How we analyzed the COMPAS recidivism algorithm. ProPublica, 2016.
[41] Gavin Smith, Roberto Mansilla, and James Goulding. Model class reliance for random forests. Advances in Neural Information Processing Systems, 33:22305-22311 2020.
[42] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pages 1894-1894. PMLR, 2017.
[43] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[44] Kristen B Gorman, Tony D Williams, and William R Fraser. Ecological sexual dimorphism and environmental variability within a community of antarctic penguins (genus pygoscelis). PlaS one, 9000,,,,,, 2014.
12

---

[45] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine. and UC Berkeley. Explainable Machine Learning Challenge. htttps://commnnig fico com/s /s 2018.
[46] Tong Wang, Cynthia Rudin, Finale Doshi Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. bayesian framework for learning rule sets for interpretable classification. The Journal of Machine Learning Research, 18(1):3357-2393 2017.
[47] Hugh A Chipman, Edward I George, and Robert E McCulloch. Bayesian CART model search. Journal of the American Statistical Association, 93(443):935 948, 1998.
[48] Hugh A Chipman, Edward I George, and Robert E. McCulloch. BART: Bayesian additive regression trees. The Annals of Applied Statistics, 4(1)::66-22))) 298, 2010.
[49] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2830, 2011.
[50] Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimension reduction tools work: an empirical approach deciphering I-SNE, UMAP, TriMAP. and PaCMAP for data visualization. J Mach. Learn. Res, 22:1-73, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] TreeFARMS's models should not be interpreted as causal. TreeFARMS creates sparse binary decision trees and thus has limited capacity. TreeFARMS's s models inherit flaws from data was trained on. TreeFARMS is not yet customized to given application, which can be done in future
work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We cannot think of any.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] see Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] see Code Availability and Appendix F and G
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see Appendix and
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] see Appendix
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] see Appendix (F and G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes)
(b) Did you mention the license of the assets? [Yes] The code and data we used all have
MIT licenses.
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
We include our code as URL in Code Availability.
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "imw51RHUOv5", "reviewer": "Reviewer_N1V8", "summary": "The paper present a method called TreeFARMS, which is a combination of analytical bounds and a specialized representation that produces enumerations of the Rashomon set for sparse decision trees. This methodology provides insight into the size of the Rashomon set, how variable importance changes over the set, predictive consistency across rashomon sets, and rashomon sets for other losses.", "questions": "What was the motivation for using the model set representation?", "limitations": "The authors discuss the paper's limitations. They specifically clarify that the models should not be interpreted as causal and also focuses on sparse binary decisions trees as the model class. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents bound to reduce the search space for Rashomon set construction. The basic lower bound and the rashomon equivalent points bound. They implement the algorithm using dynamic programming to find the optimal sparse decision trees. The work builds on existing literature focused on Rashomon sets and multiplicity to open an important discussion on variable importance and distributional shifts.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UQ5gKpTxx3-", "reviewer": "Reviewer_4Gdc", "summary": "This paper presents the first algorithm TreeFARMS, a branch & bound algorithm with memoization (or dynamic programming with pruning bounds) to completely enumerate the Rashomon set of sparse decision trees. The Rashomon set is the set of almost-equally as good trees as the given reference tree. As recently proposed, the GOSDT algorithm [3][32] can find the empirical risk minimizer among sparse decision trees. TreeFARMS use this optimal tree as the reference for the Rashomon set, and also use its dependency graph as a model search space. The basic idea is to decompose search for decision trees into subproblems, and recursively solve child problems with maintaining these problems (dependency graph) and with pruning problem space with bounds. Extending this search strategy with a specialized data structure called Model Set (MS) representation enables the full enumeration of the Rashomon set of all sparse decision trees in the search space of GOSDT. Clear use cases of this complete enumeration such as the size of the Rashomon set, the variability of feature importances, the variability of predictions, and the sample dependency of the Rashomon set are further provided and discussed in detail.", "questions": "- Because the title includes \"sparse\", and thus could you explain why enumeration is limited to \"sparse\", and what does the paper mean by the word \"sparse\", or explicitly (but concisely?) explain the dependency inherited from GOSDT? \n\n- Could you add the table of contents for the supplementary document? I wanted to know the results for \"the size of Rashomon set\", which is the first example use-case mentioned in Introduction, but at the first glance, they are sort of hidden by other detailed information.\n\n- Is the \"dependency graph\" actually a tree, a DAG, or a cyclic graph? I'm not sure about the connection, but I felt some abstract similarity to topics such as decision diagram (DD) representation of logical functions and traversing an enumeration tree, the search space of gSpan algorithm for all subgraph patterns, with bounds as in https://doi.org/10.1109/TPAMI.2016.2567399 for example.\n\n", "limitations": "No specific concerns on limitations and negative societal impact of this work.\n", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- This paper presents the first very powerful algorithm to completely enumerate the Rashomon set of optimal sparse decision trees thanks to GOSDT algorithm, pruning bounds, and MS data structures. This would be quite impactful because the instability or multiplicity of good models, for decision trees in particular, is a long standing interests in decision tree learning since Breiman.\n\n- The paper also showed several clear use cases with detailed analysis. Full enumeration of the Rashomon set enables to analyze the size of Rashomon set, the variability of feature importances, the variability of predictions, and the sensitivity to missing groups of samples.\n\n\n### Weaknesses\n\n- Though the paper comes with a detailed supplementary document, some descriptions are hard to follow at the first glance due to the strong dependency on GOSDT. For example, the main algorithm of TreeFARMS, Algorithm 1, includes undefined procedure such as gosdt.get_graph or gosdt.configure_bounds. Since this is the main result, much more self-contained explanations would be appreciated.\n\n- Also due to the implicit dependency on GOSDT, several important points would be unclearly presented. For example, one big issue is why the paper title includes \"sparse\" although Algorithm 1 and 2 have no sparsity-inducing parts apparently. If I understand it, the model search space for complete enumeration comes from GOSDT targeting sparse decision trees, and thus, TreeFARMS also results in enumerating sparse trees. Furthermore, it uses \"GOSDT lookahead bounds\" in actual that are not directly described in this paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NF5_Fy1euYl", "reviewer": "Reviewer_PEzG", "summary": "The authors propose the TreeFARMS method, which is able to enumerate the Rashomon set of all sparse decision trees over binary variables and labels that are optimal within a user-provided multiplicative factor in terms of 0-1 loss, which they also show to be sufficient for the derivation of balanced accuracy and F1 score. This algorithm employs a branch-and-bound search over the search state of trees represented as their leaves, some of which are fixed and some as of yet \"unfixed\"; it then uses a simple bound (that ignores \"unfixed\" leaves) and another that tightens the former by considering data point groups with identical features (termed equivalent points). TreeFARMS heavily relies on implementation details of the existing GOSDT algorithm and extensions for storing different decision trees. The authors show that their proposal outperforms heuristic methods in terms of accuracy, and demonstrate the model class reliance of the variables on an intuitive example dataset.", "questions": "1. What is the sampling distribution? If not uniform among the entire Rashomon set, what is your intuition on which models are preferably included?\n\n2. What is the relation between your method and the MCR method of Smith et al. for Random Forests?\n\n[1] Gavin Smith, Roberto Mansilla, and James Goulding. Model Class Reliance for Random Forests.\n", "limitations": "The manuscript does not include a discussion of the limitations of the proposal.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First work on providing the complete Rashomon set for optimal sparse trees.\n\nProvide theoretical foundations for deriving the Rashomon set for other losses (balanced accuracy+F1).\n\nProvide experimental evaluations for theoretically interesting applications of the Rashomon set: variable importance, and sensitivity to missing values.\n\nAlthough overall solid work, the key novelty of the manuscript is limited to Sections 5.2 and 5.3 as it otherwise effectively extends an existing algorithm to enumerate the Rashomon set and the investigation of existing MCR.\n\nThe writing is good in general, but the authors are guilty of overselling; the manuscript will improve by removing exaggerations (e.g., “at the mercy of an algorithm”, “only scratch the surface of”) or allegations “this complexity explains why no previous works”, in lieu of a formal complexity result.\n\nA clear limitation is the use of only binary labels and variables. The experiments show that setting the multiplicative and regularisation parameters provides little a-priori control on the number of models in the resulting set (e.g. it can be up to 10e12 in given configurations, line 190). \n\nThe statistics during sampling are not clear to this reviewer. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5HDSfrmGnAz", "reviewer": "Reviewer_e6ES", "summary": "The paper studies the problem of enumerating the Rashomon set for sparse decision trees.  The Rashomon set is the set of all almost-optimal models, and the paper provides the first result in enumerating it for highly nonlinear discrete models. The paper proposes an algorithm, TreeFARMS, to enumerate the Rashomon set for sparse decision trees, which stores the Rashomon set in a specialized and memory efficient data structure. The experimental evaluation, which considers several datasets from different domains, shows that the ability of enumerating the Rashomon set empowers the user with the ability to answer novel questions, such as: how does the variable importance change among trees within the Rashomon set? Do all almost-optimal models provide the same prediction for the same instance? How does the Rashomon set change if a subset of the data is removed? ", "questions": "No questions", "limitations": " There is no discussion, but the introduction provides some motivation for why the paper may have a positive impact.", "rating": 9, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- overall, the paper provides a significant, high-quality, and original contribution\n- the problem of enumerating the Rashomon set is very interesting in general, and very challenging for sparse decision trees\n- the paper is clearly written and provides a clear motivation for the problem and a nice summary of the main contributions\n- the methodological and algorithm contributions are sound\n- the  experimental evaluation is clearly presented and comprehensive. It clearly shows how the proposed tool can be used to study the space of well-performing sparse decision trees\n \nNo weaknesses\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept