The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance
Authors: Jon Donnelly
Srikar Katta
Cynthia Rudin
Edward P Browne
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Rashomon Effect
Variable Importance
XAI
Stability
Interpretable Machine Learning

Abstract: Quantifying variable importance is essential for answering high-stakes questions in fields like genetics, public policy, and medicine. Current methods generally calculate variable importance for a given model trained on a given dataset. However, for a given dataset, there may be many models that explain the target outcome equally well; without accounting for all possible explanations, different researchers may arrive at many conflicting yet equally valid conclusions given the same data. Additionally, even when accounting for all possible explanations for a given dataset, these insights may not generalize because not all good explanations are stable across reasonable data perturbations. We propose a new variable importance framework that quantifies the importance of a variable across the set of all good models and is stable across the data distribution. Our framework is extremely flexible and can be integrated with most existing model classes and global variable importance metrics. We demonstrate through experiments that our framework recovers variable importance rankings for complex simulation setups where other methods fail. Further, we show that our framework accurately estimates the _true importance_ of a variable for the underlying data distribution. We provide theoretical guarantees on the consistency and finite sample error rates for our estimator. Finally, we demonstrate its utility with a real-world case study exploring which genes are important for predicting HIV load in persons with HIV, highlighting an important gene that has not previously been studied in connection with HIV.

The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance
Jon Donnelly*
Srikar Katta
Department of Computer Science
Department of Computer Science
Duke University
Duke University
Durham, NC 27708
Durham, NC 27708
j jon wownelly@duke
sr Brikar. kattauduke edu
Cynthia Rudin
Edward P. Browne
Department of Computer Science
Department of Medicine
Duke University
University of North Carolina at Chapel Hill
Durham, NC 27708
Chapel Hill, NC 27599 epbrosme@email unc edu
rudinodkk..... edu
Abstract
Quantifying variable importance is essential for answering high-stakes questions in fields like genetics, public policy, and medicine. Current methods generally calculate variable importance for given model trained on given dataset. However, for given dataset, there may be many models that explain the target outcome equally well; without accounting for all possible explanations, different researchers may arrive at many conflicting yet equally valid conclusions given the same data. Additionally, even when accounting for all possible explanations for given dataset, these insights may not generalize because not all good explanations are stable across reasonable data perturbations. We propose new variable importance framework that quantifies the importance models and is stable across the data distribution. Our framework is extremely flexible and can be integrated with most existing model classes and global variable importance metries. We demonstrate through experiments that framework recovers variable importance rankings for complex simulation setups where other methods fail. Further, show that framework accurately estimates the true importance a variable for the underlying data distribution. We provide theoretical guarantees the consistency and finite sample error rates for estimator. Finally, we demonstrate its utility with a real-world case study exploring which genes are important for predicting HIV load in persons with HIV, highlighting an important gene that has not previously been studied in connection with HIV.
variable across the set of all good
Introduction
Variable importance analysis enables researchers to gain insight into a domain or a model. Scientists are often interested in understanding causal relationships between variables, but running randomized experiments is time-consuming and expensive. Given an observational dataset, we can use global variable importance measures to check if there predictive relationship between two variables. is particularly important in high stakes real world domains such as genetics 44 34), finance [37] and criminal justice
15| 24
where randomized controlled trials are impractical or unethical. Variable
*on Donnelly and Srikar Katta contributed equally to this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

0.4
Largest Min Model Relincce
Model Reliance
0.2
Smallest Max Model Reliance
0.0-
10
100
1000
10000
Rashomon Set Size per Bootstrapped Dataset
Bootstrap Iteration
(a) The number of models in each Rashomon set
(b) Model reliance range across each Rashomon set
Figure 1: Statistics of Rashomon sets computed across 500 bootstrap replicates of given dataset sampled from the Monk 3 data generation process
The original dataset consisted of 124 observations, and the Rashomon set was calculated using its definition in Equation [ with parameters specified in Section of the supplement. The Rashomon set size is the number of models with loss below a threshold. Model reliance is measure of variable importance for a single variable in this case, X2 - and Model Class Reliance (MCR) is its range over the Rashomon set. Both the Rashomon set size and model class reliance are unstable across bootstrap iterations.
importance would ideally be measured as the importance of each variable to the data generating process. However, the data generating process is never known in practice, so prior work generally draws insight by analyzing variable importance for surrogate model, treating that model and its variable importance as truth.
This approach can be misleading because there may be many good models for a given dataset phenomenon referred as the Rashomon effect 40 and variables that are important for one good model on given dataset are not necessarily important for others. As such, any insights drawn from single model need not reflect the underlying data distribution or even the consensus among good models. Recently, researchers have sought to overcome the Rashomon effect by computing Rashomon sets, the set of all good (i.e., low loss) models for a given dataset [5] [2]. However, the set of all good models is not stable across reusonable perturbations (e.g,, boolstrap or jackknife) of single dataset, with stability defined as in [50]. This concept of stability is one of the three pillars of veridical data science [33. Note that there is wide agreement on the intuition behind stability, but not its quantification
[2. As such, in line with other stability research, we do not subscribe to a formal definition and treat stability general notion 22
33 50 51). In order to ensure trustworthy analyses, variable importance measures must account for both the Rashomon effect and stability.
Figure provides a demonstration of this problem: across 500 bootstrap replicates from the same data set, the Rashomon set varies wildly- --r--ram ranging from ten models to over ten thousand suggesting that we should account for its instability in any computed statistics. This instability is further highlighted when considering the Model Class Reliance (MCR) variable importance, which is the range of model reliance (i.e., variable importance) values across the Rashomon set for the given dataset [1] (we define MCR and the Rashomon set more rigorously in Sections 2 and respectively). In particular, for variable X2, one interval ranging from -0.1 to 0.33 suggests that there exist good models that do not depend on this variable at all (0 indicates the variable is not important); on the other hand, another MCR from bootstrapped dataset ranges from 0.33 to 0.36, suggesting that this variable is essential to all good models. Because of this instability, different researchers may draw very different conclusions about the same data distribution even when using the same method.
In this work, we present a framework unifying concepts from classical nonparametric estimation with recent developments on Rashomon sets to overcome the limitations of traditional variable importance measurements. We propose a stable, model- and casaubleimpotttncc-- imporraacce-ettric-gnnoiii estimand that quantifies variable importance across all good models for the empirical data distribution and corresponding bootstrap-style estimation strategy. Our method creates a cumulative density function (CDF) for variable importance over all variables via the framework shown in Figure 2 Using the CDF, we can compute a variety of statistics (e.g., expected variable importance, interquartile range, and eredible regions) that can summarize the variable importance distribution.
The rest this work is structured as follows. After more formally introducing our variable importance framework, we theoretically guarantee the convergence of our estimation strategy and derive error bounds. We also demonstrate experimentally that our estimand captures the true variable importance for the data generating process more accurately than previous work. Additionally, illustrate the

---

Step 1: Bootstrap
Step
Step 3: Find Importances
Step
Step 5:
Find Rashomon Set
Find CDF
Find PDF
Donsity RID.
loso Bo D
RID,
PDF of RID)
PE Model Class
fE Rushomon Set
E (hrin Prrse]
E [Qrii 9tras]
Figure 2: An overview of our framework. Step We bootstrap multiple datasets from the original.
Step 2: We show the loss values over the model class for each bootstrapped dataset, differentiated by color. The dotted line marks the Rashomon threshold; all models whose loss is under the threshold are in the Rashomon set for that bootstrapped dataset. On top. we highlight the number of bootstrapped datasets for which the corresponding model is in the Rashomon set. Step 3: We then compute the distribution of model reliance (variable importance VI) values for variable across the Rashomon set for each bootstrapped dataset. Step 4: We then average the corresponding CDF across bootstrap replicates into single CDF (in purple). Step 5: Using the CDF, compute the marginal distribution (PDF) of variable importance for variable j across the Rashomon sets of bootstrapped datasets.
generalizability of our variable importance metric by analyzing the reproducibility of our results given new datasets from the same data generation process. Lastly, we use our method to analyze which transcripts and chromatin patterns in human T cells are associated with high expression of HIV RNA. Our results suggest an unexplored link between the LINC00486 gene and HIV load.
Code is available at hutps//ghhhkkcom///ooooo////sssa httpi//moop_eisiiiiitiee Distribution,
2 Related Work
The key difference between our work and most others is the way it incorporates model uncertainty, also called the Rashomon effect 77. The Rashomon effect is the phenomenon in which many different models explain dataset equally well. It has been documented in high stakes domains including
healthcare, finance, and recidivism prediction [14 30 15 The Rashomon effect has been leveraged
to create uncertainty sets for robust optimization 43 perform responsible statistical inference
11, and to gauge whether simple yet accurate models exist for a given dataset [40]. One barrier to studying the Rashomon effect is the fact that Rashomon sets are computationally hard to calculate for
non-trivial model classes. Only within the past year has code been made available to solve for (and
store) the full Rashomon set for any nonlinear function class that of decision trees 49 This work enables us to revisit the study of variable importance with a new lens.
A classical way to determine the importance of variable is to leave it out and see if the loss changes. This is called algorithmic reliance [15) or leave one covariate out (LOCO) inference [25] The problem with these approaches is that the performance of the model produced by algorithm will not change if there exist other variables correlated with the variable of interest.
Model reliance (MR) methods capture the global variable importance (VI) of given feature for specific model [1]. (Note that MR is limited refer to permutation importance [15. while we use the term MR to refer to any metric capturing global variable importance of given feature and model. We use and MR interchangably when the relevant model is clear from context.) Several methods for measuring the MR of a model from specific model class exist, including the variable importance measure from random forest which uses out-of-bag samples 77] and Lasso regression coefficients (20). Lundberg et al. (28 introduce way of measuring MR in tree ensembles using SHAP (77] Williamson et al. [48] develop MR based on the change in performance between the
optimal model and the optimal model using subset of features.
In addition the metrics tied to a specific model class, many MR methods can be applied to models from any model class. Traditional correlation measures [20] can measure the linear relationship (Pearson correlation) or general monotonic relationship (Spearman correlation) between a feature and predicted outcomes for model from any model class. Permutation model reliance, as discussed by 15 (1], describes how much worse a model performs when the values of a given feature are permuted such that the feature becomes uninformative. Shapley-based measures of MR, such as those
3

---

calculate the average marginal contribution of each feature to a model's predictions. A complete overview of the variable importance literature is beyond the scope of this work; for more thorough review, see, for example, (2 31. Rather than calculating the importance of a variable for single model, our framework finds the importance of variable for all models within a Rashomon set, although our framework is applicable to all of these model reliance metrics.
of [47
In contrast, model class reliance (MCR) methods describe how much a class of models (e.g., decision trees) relies on a variable. Fisher et al. [5] uses the Rashomon set to provide bounds on the possible range of model reliance for good models of a given class. Smith et al. 41 analytically find the range of model reliance for the model class of random forests. Zhang and Janson [52] introduce a way to compute confidence bounds for a specific variable importance metric over arbitrary models, which Aufiero and Janson [ extend so that it is applicable to a broad class of surrogate models in pursuit of computational efficiency. These methods report MCR as range, which gives no estimate of variable importance only a range of what values are possible. In contrast, Dong and Rudin [12 compute and visualize the variable importance for every member of a given Rashomon set in projected spaces, calculating a set of points; however, these methods have no guarantees of stability to reasonable data perturbations. In contrast, our framework overcomes these finite sample biases, supporting stronger conclusions about the underlying data distribution.
Related to our work from the stability perspective, Duncan et al. 13 developed a software package to evaluate the stability of permutation variable importance in random forest methods; we perform a similar exercise to demonstrate that current variable importance metrics computed for the Rashomon set are not stable. Additionally, Basu et al. [5] introduced iterative random forests by iteratively reweighting trees and bootstrapping to find stable higher-order interactions from random forests. Further, theoretical results have demonstrated that bootstrapping stabilizes many machine learning algorithms and reduces the variance of statisties [18 []. We also take advantage of bootstrapping s flexibility and properties to ensure stability for our variable importance.
3 Methods
3.1 Definitions and Estimands
Let Dín)_ = [(,,, = denote a dataset of n independent and identically distributed tuples, where Y, E R denotes some outcome of interest and X, E IR denotes a vector of covariates. Let g" represent the data generating process (DGP) producing D(n), Let f E J be a model in a model class (e.g.. tree in the set of all possible sparse decision trees), and let dj (f, D(a)) denote a function that measures the importance of variable j for a model f over a dataset ((x),, This can be any of the functions described earlier (c.g.. permutation importance, SHAP). Our framework is flexible with respect to the user's choice of Φ, and enables practitioners to use the variable importance metric best suited for their purpose; for instance, conditional model reliance [15] is best-suited to measure only the unique information carried by the variable (that cannot be constructed using other variables), whereas other metrics like subtractive model reliance consider the unconditional importance of the variable. Our framework is easily integrable with either of these. We only assume that the variable importance function á has bounded range, which holds for a wide class of metrics like SHAP 277. permutation model reliance, and conditional model reliance. Finally, let E(f, (("), X) represent a loss function given f. (n),, and loss hyperparameters À (e.g., regularization). We assume that our loss function is bounded above and below, which is true for common loss functions like 0-1 classification loss. well as for differentiable loss functions with covariates from bounded domain.
In an ideal setting, we would measure variable importance using g" and the whole population, but this is impossible because g" is unknown and data is finite. In practice, scientists instead use the empirical loss minimizer for specific dataset f* E arg min {(S, D(m)); however, several models could explain the same dataset equally well (i.e., the Rashomon effect). Rather than using a single model to compute variable importance, we propose using the entire Rashomon set. Given single dataset D(n), we define the Rashomon set for a model class F and parameter e as the set of all models in F whose empirical losses are within some bound & > of the empirical loss minimizer:
R(c, F,e,,, 1)) >)= {IEF: ( min ((), +
(1)
ret

---

We denote this Rashomon set by D(x) or "Rset" (this assumes fixed F, é and X). As discussed earlier, the Rashomon set can be fully computed and stored for non-linear models (e.g., sparse decision trees ). For notational simplicity, we often omit À from the loss function.
While the Rashomon set describes the set of good models for single dataset, Rashomon sets vary across permutations (c.g., subsampling and resampling schemes) of the given data. We introduce a stable quantity for variable importance that accounts for all good models and all permutations from the data using the random variable RIV. R/V is defined by its cumulative distribution function (CDF), the Rashomon Importance Distribution (RID):
RID,(k; E, F,, A) = P D/ ~n
(RIV, (E, F,,,D ; s k)
(2)
Hf Re D 1 Re
: (J )) - k)]
E E(-))
ml
vol of Rset s.t. variable j's importance is at most k- vol of Rset
= =(D
where 9 denotes the variable importance metric being computed on variable j. h E [omin @max] For continuous model class (e.g.. linear regression models), the cardinality in the above definition becomes the volume under a measure on the function class, usually & on parameter space. RID constructs the cumulative distribution function (CDF) for the distribution of variable importance
across Rashomon sets; as & increases, the value of (E, D(") A) S k) becomes closer to 1. The probability and expectation are taken with respect to datasets of size n sampled from the empirical distribution Pa. which is the same as considering all possible resamples of size n from the originally observed dataset D(*), Equation (2) weights the contribution of (f, D(")) for each model f by the proportion of datasets for which this model a good explanation (i.e., in the Rashomon set). Intuitively, this provides greater weight to the importance of variables for stable models.
We now define an analogous metric for the loss function E; we define the Rashomon Loss Distribu- tion (RID) evaluated at l as the expected fraction of functions in the Rashomon set with loss below k. Here, RLV is a random variable following this CDF.
RID F, F,e, A) = D("))~p.
[RIV(E,F,E, (1)) (()) sk)
[H E RE D(m))
((J,Di S k}]
= En( PPn
R pinno
| k - minser e(S, D(") F, F, ([E,FF4;A)
=Ep(n)>p
This quantity shows how quickly the Rashomon set "fills up" on average as loss changes. If there are many near-optimal functions, this will grow quickly with k.
In order connect RID for model class F the unknown DGP g², make Lipschitz-continuity. style assumption on the relationship between RLD and RID relative to a general model class FF and {g*). To draw this connection, we define the loss CDF for g", called LD*, over datasets of size as:
LD (k; E, n, Pn, A) = En(d) ~P, 116(0", ""("", p(()) <
One could think of LD measuring how quickly the DGP's Rashomon set fills up as loss changes. Here, LD* is the analog of RLD for the data generation process.
Assumption 1. If
P (RLD(,,,FF,,2 A), LD (1::;:,,, n, Pu, ))) S y then
p (RID, ( (58, Fe,, RID,(5e, (9 [,"), A)) d(7)
for function d [0, fmax mmin) -> [0, Φmax - Mmin) such that lim d(7) = 0. Here, p represents any distributional distance metric (e.g., 1- W.sssersteein.
5

---

Assumption 1 saas that a Rashomon set consisting of good approximations for g" in terms of loss will also consist of good approximations for g" terms of variable importance. More formally, from this assumption, we know that p(LD", RID) - O, the variable importance distributions will converge: p (RID) e, Pn; A), (: e, {g"), Pn. X)) - O. We demonstrate that this assumption realistic for variety of model classes like linear models and generalized additive models in Section C of the supplement.
3.2 Estimation
We estimate RID; for each variable j by leveraging bootstrap sampling to draw new datasets from the empirical data distribution:
sample observations from observed dataset, construct its Rashomon set, and compute the j-th variable's importance for each model in the Rashomon set, After repeating this process for B bootstrap iterations, we estimate RID by weighting each model f's realized variable importance score (evaluated on each bootstrapped dataset) by the proportion of the bootstrapped datasets for which f is in the Rashomon set and the size of each Rashomon set in which f appears. Specifically, let D( represent the dataset sampled with replacement from D(x) in iteration ...... B of the bootstrap procedure. For each dataset D) we find the Rashomon set Finally, we compute an empirical estimate RID, of RID, by computing:
Re "!
RID, 1 Σ ER $5 (0)) - k}]
1
D
B
R
D
Under Assumption can directly connect our estimate RID
E F, P., X) to the DGP's
variable importance distribution RID(E;; Emax, {g" } Pa, A), which Theorem formalizes.
Theorem 1. Let Assumption 7 hold for distributional distance p(A1, A2) between distributions A1 and Az For any t > 0, j (O....,p) as p (LD*(; X), RLD(1 e. F,e, - 0 and B xc,
P (ki F, RRDD--RID,,,,,, ('),, A) 2 21) +
For set of models that performs sufficiently well in terms of loss, RID; thus recovers the CDF of variable importance for the true model across reasonable perturbations. Further, we can provide a finite sample bound for the estimation of a marginal distribution between RID, and RID, for the model class J, as stated in Theorem 2 Note that this result does require Assumption [
Theorem 2. Let L > 0 and 5 E (0, 1) be some pre-specified values. Then, with probability at least
1 8 with respect to bootstrap samples of size n1
E P.. A) -RID, F,,, st
with number of bootstrap samples B 2 1 In (2) for any k [Qmin Pmaxx]
Because we use bootstrap procedure, we can control the number of bootstrap iterations to ensure that the difference between RID, and RID; is within some pre-specified error. (As defined earlier, RID; is the expectation over infinite bootstraps, whereas RID); is the empirical average over B bootstraps.) For example, after 471 bootstrap iterations, find that RID, (k:; e, F. f, A) is within 0.075 of RID,(K; e, E, Pa,, X) for any given with 90% confidence. It also follows that as B tends infinity, the estimated RIV, will converge to the true value.
Since we stably estimate the entire distribution of variable importance values, we can create (I) stable point estimates of variable importance (e.g., expected variable importance) that account for the Rashomon effect, (2) interquantile ranges of variable importance, and (3) confidence regions that characterize uncertainty around point estimate of variable importance. We prove exponential rates of convergence for these statistics estimated using our framework in Section B of the supplement.
Because our estimand and our estimation strategy (1) enable us to manage instability, (2) account for the Rashomon effect, and (3) are completely model-agnostic and flexibly work with most existing variable importance metrics, RID is valuable quantification of variable importance.

---

Experiments With Known Data Generation Processes
1.00
Classification
Proportion
0.75
0.50
0.25
0.00
RID
GOSDTIC
VIC+ GOSDT
MR
RF
Pormite RF
RF
GOSDT
Lasso
Adaboost MR
Mft
Lasio Shop RF
CMR Lanso
LOCO Lasso L Loco
RF Pearson
Sparman
LOCO Adaborrt
PDP PDP
RF
Stability Rashomon
Rashomon only
Stability only
(via bootstrapping)
1.00
Recovery Proportion
Chen's
0.75
Monk
0.50
Monk 3
Friedman's
0.00
Method
RID + GOSDT (94.64%)
VIC GOSDT (8116%)
AdaBoost (90.62 62%)
GOSDT
LASSO
RF (84.98%) (100%)
Recovery Correct (%)
(93.49%)
(80.9 (80.92%)
Classifications Correct (36)
(100%)
(100%)
(83.33%)
(83.33%)
(83.33%)
Figure 3: (Top) The proportion of features ranked correctly by each method on each data set represented as a stacked barplot. The figures are ordered by method performance across the four simulation setups. (Bottom) The proportion of independent DGP dj(sub) calculations on 500 new datasets from the DGP that were contained within the box-and-whiskers range computed using single training (with bootstrapping in all methods except VIC) for each method and variable in each simulation. Underneath each method's label, the first row shows the percentage of times across all 500 independently generated datasets and variables that the DGP's variable importance was inside of that method's 's mox--andwhissee interval. The second row shows the percentage of pairwise rankings correct for each method (from the top plot). Higher better.
4.1 RID Distinguishes Important Variables from Extraneous Variables
There is no generally accepted ground truth measure for variable importance, so we first eval- uate whether a variety of variable importance methods can correctly distinguish between vari- ables used to generate the outcome (in a known data generation process) versus those that are not. We consider the following four data generation processes (DGPs). Chen's DGP ( Y= 1[-2 + +mx( X2, xxxpx Here, only X X1.... X, are relevant. Friedman's DGP [7] Y = 1[10 + 20(X3 0.5) - 10XX 5X, + E 2 15]. where ,,...., .gg (4, 1). ~ (O, 1). Here, only XI...., are relevant. The Monk 1 DGP [2]: Y max [1 X2), n[x, 1)), where the variables XI,...,X, Xa have domains of 2, 3, or unique integer values. Only X1, X2, X5 are important.
2 2.048), where XI...., S5.....10..
N/ 1).
The Monk DGP 42 Y max (1 [X,
and Xa 11, * 4 and X₂ 7 3)) for the same covariates Monk Also, 5% label noise is added. Here, X4, and X5, are relevant.
We compare the ability of RID to identify extrancous variables with that of the following baseline methods, whose details are provided in Section D of the supplement: subtractive model reliance uu of random forest (RF) (6). LASSO 200 boosted decision trees [16]. and generalized optimal sparse decision trees (GOSDT) 26 conditional model reliance (CMR) [5]; the impurity based model reliance metric for RF from 7 the LOCO algorithm reliance 25 for RF and Lasso; the Pearson and
Spearman correlation between each feature and the outcome; the mean of the partial dependency plot 28 for RF; and mean of variable importance clouds (VIC) 12 for the Rashomon set of GOSDT's 49). If we do not account for instability and simply learn model and calculate variable importance, baseline models generally perform poorly, as shown
(PDP) 19 for each feature; the SHAP value

---

in Section E of the supplement. Thus, we chose to account for instability in a way that benefits the baselines. We evaluate each baseline method for each variable across 500 bootstrap samples and compute the median VI across bootstrups, with the exception of VIC for VIC, we take the median VI value across the Rashomon set for the original dataset, as VIC accounts for Rashomon uncertainty. Here, we aim to see whether we can identify extraneous (i.e., unimportant variables). For a DGP with C' extraneous variables, we classify the C' variables with the smallest median variable importance values as extraneous. We repeat this experiment with different values for the Rashomon threshold in Section E of the supplement.
Figure 3 (top) reports the proportion of variables that are correctly classified for each simulation setup as a stacked barplot. RID identifies all important and unimportant variables for these complex simulations. Note that four other baseline methods - MR RF, RF Impurity. RF Permute, and VIC also differentiated all important from unimportant variables. Motivated by this finding, we next explore how well methods recover the true value for subtractive model reliance on the DGP, allowing us to distinguish between the best performing methods on the classification task.
4.2 RID Captures Model Reliance for the True Data Generation Process
RID allows us to quantify uncertainty in variable importance due to both the Rashomon effect and instability. We perform an ablation study investigating how accounting for both stability and the Rashomon effect compares to having one without the other. We evaluate what proportion of subtractive model reliances calculated for the DGP on 500 test sets are contained within uncertainty intervals generated using only one training dataset. This experiment tells us whether the intervals created on a single dataset will generalize.
To create the uncertainty interval on the training dataset and for each method, we first find the subtractive model reliance (( across 500 bootstrap iterations of a given dataset for the four algorithmss shown in Figure 3 (bottom) (baseline results without bootstrapping are in Section E of the supplementary material). Additionally, we find the VIC for the Rashomon set of GOSDTs on the original dataset. We summarize these model reliances (500 bootstraps 28 variables across datasets x 4 algorithms + 8,247 models in VIC's + 10,840,535 total models across Rsets x 28 variables from RID) by computing their box-and-whisker ranges (1.5 Interquartile range (46)). To compare with "ground truth," we sample 500 test datasets from the DGP and calculate d(sub) for the DGP for that dataset. For example, assume the DGP is Y = X² + E. We would then use f(X) = X² as our predictive model and evaluate ((sab) (f. D())) on f for each of the 500 test sets. We then check if the box-and-whiske range of each method's interval constructed on the training set contains the computed ((sub) for the DGP for each test dataset. Doing this allows us to understand whether our interval contains the true ((sub) for each test set.
Figure 33 (bottom) illustrates the proportion of times that the test variable importance values fell within the uncertainty intervals from training. These baselines fail to capture the test ((swb) entirely for at least one variable (< 0.05% recovery proportion). Only RID both recovers important/uninportant classifications perfectly and achieves a strong recovery proportion at 95%.
4.3 RID is Stable
Our final experiment investigates the stability of VIC and MCR (which capture only Rashomon uncertainty but not stability) to RID, which naturally considers data perturbations. We generate 50 independent datasets from each DGP and compute the moo--nddwhiskee ranges (BWR) of each uncertainty metric for each dataset; for every pair of BWRs for given method, we then calculate the Jaccard similarity between BWR's. For each generated dataset, we then average the Jaccard similarity across variables. Figure 4 shows these intervals for each non-extrancous variable from Chen's DGP. Supplement E.4 presents a similar figure for each DGP, showing that only RID's 's intervals overlap across all generations for all datasets.
Figure 5 displays the similarity scores between the box and whisker ranges of MCR, VIC, and RID across the 50 datasets for each DGP. Note that Monk 1 has no noise added, so instability should not be a concern for any method. For datasets including noise, MCR and VIC achieve median similarity below 0.55; RID's median similarity is 0.69; it is much more stable.
8

---

Chen's
MCR
VIC
RID pou pf buidhudl
000 u 1
Model Reliance
0.2
0.1
4:0 jol 4lfo/
Mllh..l mnthhhhhtatt indaaa
Lilpa ||
0.2
0.1
a
0.0
0.2
10 1
0.1
0.0
10
20
30
40
50
0
10
20
30
40
50
0
10
20
30
40
50
Dataset
Figure We generate 50 independent datasets from Chen's DGP and calculate MCR, BWRs for VIC, and BWRs for RID. The above plot shows the interval for each dataset for each non-null variable in Chen's DGP. All red-colored intervals do not overlap with least one of the remaining 49 intervals.
Median Jaccard
Similarity
0.75
Method
0.50
MCR
VIC
0.25
RID
0.00
Chen's
Friedman's
Monk 1
Monk 3
Figure 5: Median Jaccard similarity scores across 50 independently generated MCR, VIC, and RID box and whisker ranges for each DGP; perfect similarity. Error bars show 95% confidence interval around the median.
Case Study
Having validated RID on synthetic datasets, we demonstrate its utility in real world application: studying which host cell transcripts and chromatin patterns are associated with high expression of Human Immunodeficienccy Virus (HIV) RNA. We analyzed dataset that combined single cell RNAseq/ATAAseq profiles for 74,031 individual HIV infected cells from two different donors in the aims of finding new cellular cofactors for HIV expression that could be targeted to reactivate the latent HIV reservoir in people with HIV (PWH). A longer description of the data is in [29]. Finding results on this type of data allows load prediction and might generalize to large portions of the population.
create hypotheses for which genes important for HIV
To identify which genes are stably importance across good models, we evaluated this dataset using RID over the model class of sparse decision trees using subtractive model reliance. We selected 14,614 samples (all 7,307 high HIV load samples and 7,307 random low HIV load samples) from the overall dataset in order to balance labels, and filtered the complete profiles down to the top 100 variables by individual AUC. We consider the binary classification problem of predicting high versus low HIV load. For full experimental details, see Section D of the supplement. Section E.5 of the supplement contains timing experiments for RID using this dataset.
Figure @illsstrates the probability that RID greater than 0 for the 10 highest probability variables (0 is when the variable is not important at all). We find that LINC00486 less explored gene - is the most important variable, with
NC00046 (0) 78.4%. LINC00486 is long non-coding RNA (i.e., it functions as an RNA molecule but does not encode protein like most genes), and there no literature on this gene and HIV, making this association a novel one. However, recent work [45] has shown that LINC00486 can enhance EBV (Epstein-Banl -Bar virus) infection by activating NF-xB.

---

0.8
10 Most Important Genes
0.6
LINCU0486
PPP3CA
P(RIV;
0.4-
PDE4D
TANK
ACTR
PTPRC
HNRNPA2BI
RBPJ
0.2
RPS19
MALATI
0.0
Gene
Figure 6: Probability of each gene's 's model reliance being greater than 0 across Rashomon sets across bootstrapped datasets for the ten genes with the highest P(R/V, > 0). We ran 738 bootstrap iterations to ensure that IP (RIV, > 0) is within 0.05 of PP (RIV, > 0) with 95% confidence (from Theorem
suggesting a possible mechanism and supporting future study. Notably, RID also highlighted PDE4D, which interacts with
well established that NF-rB can regulate HIV expression 332 23
the Tat protein and thereby HIV transcription [39] INNRNAAB1, which promotes HIV expression
by altering the structure of the viral promoter
[8 and MALATI, which has recently been shown to
be an important regulator of HIV expression
35 These three findings validate prior work and show
that RID can uncover variables that are known to interact with HIV.
Note that previous methods even those that account for the Rashomon effect could not produce this result. MCR and VIC do not account for instability. For example, after computing MCR for 738 bootstrap iterations, we find that the MCR for the LINC00486 gene has overlap with O in 16.2% of bootstrapped datasets, meaning MCR would not allow us to distinguish whether LINC00486 important or not 96.2% of the time. Without RID, we would not have strong evidence that LINC00486 is necessary for good models. By explicitly accounting for instability, we increase trust in our analyses.
Critically, RID also found very low importance for the majority of variables, allowing researchers to dramatically reduce the number of possible directions for future experiments designed to test gene's functional role. Such experiments are time consuming and cost tens of thousands of dollars per donor, so narrowing possible future directions small set of genes is of the utmost importance. Our analysis provides manageable set of clear directions for future work studying the functional roles of these genes in HIV.
Conclusion and Limitations
We introduced RID, method for recovering the importance of variables in way that accounts for both instability and the Rashomon effect. We showed that R/D distinguishes between important and extraneous variables, and that RID better captures the true variable importance for the DGP than prior methods. We showed through a case study in HIV load prediction that RID) can provide insight into complicated real world problems. Our framework overcomes instability and the Rashomon effect, moving beyond variable importance for a single model and increasing reproducibility.
RID can be directly computed for any model class for which the Rashomon set be found at the time of publishing, decision trees, linear models, and GLMs. A limitation that currently, there relatively few model classes for which the Rashomon set can be computed. Therefore, future work should aim to compute and store the Rashomon set of a wider variety of model classes. Future work may investigate incorporating Rashomon sets that may be well-approximated (e.g., GAMs, 10), but not computed exactly, into the RID approach. Nonetheless, sparse trees are highly flexible, and using them with RID improves the trustworthiness and transparency of variable importance measures, enabling researchers to uncover important, reproducible relationships about complex processes without being misled by the Rashomon effect.
Acknowledgements
We gratefully acknowledge support from NIH/NIDA ROI ROIDA054994, NIH/NIAID ROLAN A114381,,,, DOE DE-SC0023199 194, NSF IIS-2147061, and NSF IIS-2130250.
10

---

References
[1]
André Altmann, Laura Toloşi, Oliver Sander, and Thomas Lengauer. Permutation importance: corrected feature importance measure. Bioinformaticx, 26(10):1340-3344 2010.
[2] Alejandro Barredo Arrieta, Natalia Diaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, et al. Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AL Information Fusion, 58:82-115 115, 2020.
[3] Massimo Aufiero and Lucas Janson. Surrogate- global sensitivity analysis with statistical guarantees via floodgate. arXiv preprint arXiv:2208.0555 05885. 2022.
[4] F Bachelerie, J Alcami, F NF--B induction on infection of monocytes. Nature, 350(6320):709-777 -720 1991.
and JL Virelizier. HIV enhancer activity perpetuated by
[5] Sumanta Basu, Karl Kumbier, James Brown, and Bin Yu. Iterative random forests to discover predictive and stable high-order interactions. Proceedings of the National Academy of Sciences, 115(8):1943-15))
2018.
[6] Leo Breiman. Random forests. Machine learning. 45:5-32, 2001.
[7] Leo Breiman. Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical Science, 16(3):199-231, 2001.
[8] Peter Bühlmann and Bin Yu. Analyzing bagging. The Annals of Statistics, 30(4):927-961, 2002.
Jianbo Chen, Mitchell Stem, Martin Wainwright, and Michael Jordan. Kereel feature selection via conditional covariance minimization. Advances in Neural Information Processing Systems, 30, 2017.
[10] Zhi Chen, Chudi Zhong, Margo Seltzer, and Cynthia Rudin. Understanding and exploring the whole set of good sparse generalized additive models. Advances Neural Information Processing Systems, 36, 2023.
[11] Beau Coker, Cynthia Rudin, and Gary King. A theory of statistical inference for ensuring the robustness of scientific results. Management Science, 67(10) 74-6197, 2021.
[12] Jiayun Dong and Cynthia Rudin. Exploring the cloud of variable importance for the set of all good models. Nature Machine Intelligence, 2(12) (1-88280) 2020.
[13] James Dunean, Rush Kapoor, Abhineet Agarwal, Chandan Singh, Bin Yu. Veridicalflow: a python package for building trustworthy data science pipelines with PCS. Journal of Open Source Software, 7(69); 3895, 2022.
[14] Alexander D) A'morr Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Fisenstein, Matthew Hoffman, et al. Underspecification presents challenges for credibility in modern machine learning. Journal of Machine Learning Research, 2020.
[15] 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 prediction models simultancously. Journal of Machine Learning Research, 20 1-81 2019.
[16] Yoav Freund and Robert F. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-139, 1997.
[17] Jerome H Friedman. Multivariate adaptive regression splines. The Annals of Statistics, 19(1):1667 1991.
[18] Yves Grandvalct. Stability of bagged decision trees. In Proceedings of the XLIII Scientific Meeting of the Itaiian Statistical Sociery, pages 221-230. CLEUP, 2006.
[19] Brandon Greenwell, Bradley Boehmke, and Andrew McCarthy, simple and effective model-based variable importance measure. arXiv preprint 180.::88000075. 2018.
[20] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[21] Giles Hooker, Lucas Mentch, and Siyu Zhou. Unrestricted permutation forces extrapolation: variable importance requires at least more model, or there is no free variable importance. Statistics and Computing, 31(6):1-16 16, 2021.
[22] Alexandros Kalousis. Julien Prados, and Melanie Hilario. Stability of feature selection algorithms. In Fifth IEEE International Conference Data Mining (ICDM'05), pages 8 -p. IEEE, 2005.
[23] Marcus Kretzschmar, Michael Meisterernst, Claus Scheidereit, Gen Li, and Robert G Roeder. Tran- scriptional regulation of the HIV-1 promoter by NF-x B in vitro. Genes & Development, 6(5):761-774, 1992.
[24] Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. How we analyzed the compas recidivism algorithm. ProPublica, May 2016. URL machine- bias- risk- assessments-eeeeeeessessssssssse in- wwiminal-sentenncian. sentencing
11

---

[25] Jing Lei, Max G' Gelll, Alessandro Rinaldo. Ryan J Tibshirani. and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113($23):1094-1111 2018.
[26] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. International Conference on Machine Learning, pages 6150- 6160. PMLR, 2020.
[27] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In L. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4765-4774, Curran Associates, Inc., 2017.
[28] Scott M Landherg, Gabriel G Erion, and Su-In Lec. Consistent individualized feature attribution for tree ensembles. arXiv preprint / 038888 2018.
[29] Ashokkumar Manickam, Jackson J Peterson, Yuriko Harigaya, David M Murdoch, David Margolis, Alex Oesterling, Zhicheng Guo, Cynthia D Rudin, Yuchao Jiang, and Edward P Browne. Integrated single-cell multiomic analysis of HIV latency reversal reveals novel regulators of viral reactivation. bioRxiv, pages 2022-07, 2022.
[30] Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification. In International Conference on Machine Learning, pages
PMLR, 2020.
[31] Dang Minh, H Xiang Wang. Y Fen Li, and Tan N Nguyen. Explainable artificial intelligence: a compre- hensive review. Artificial Intelligence Review, pages 1-66, 2022.
[32] Christopher C Nixon, Maud Mavigner, Gavin C Sampey, Alyssa D Brooks. Rae Ann Spagnuolo, David M Irlbock, Cameron Mattingly, Phong T Ho, Nils Schoof, Corinne G Cammon, et al. Systemic HIV and SIV latency reversal via non non-canonical NF-BB signalling in vivo. Noture, 578(7793): 2020.
[33] Sarah Nogucira, Konstantinos Sechidis, and Gavin Brown. On the stability of feature selection algorithms. The Journal of Machine Learning Research, 18(1):6345-6398 2017.
[34] Gherman Novakovsky, Nick Dexter, Maxwell W Libbrecht, Wyeth W Wasserman, and Sara Mostafavi. Ohtaining genetics insights from deep learning via explainable artificial intelligence. Nature Reviews Genetics, pages 1-13, 2022.
[35] Di Qu, Wei- Wei Sun. Li Li, Li Ma, Li Sun, Xia Jin, Taisheng Li, Wei Hou, and Jian-Hua Wang. Long noncoding RNA MALATI releases epigenetic silencing of HIV-1 replication by displacing the polycomb repressive complex from binding to the LTR promoter. Nucleic Acids Research, 47(6):3013-3027 2019.
[36] Alessandro Rinaldo, Larry Wasserman, and Max Gelll.. Bootstrapping and sample splitting for high- dimensional, assumption- inference. The Annals of Statistics, 47(6):3438 3469, 2019, doi: 10.1214/ 18- AOS1784.
[37] Cynthia Rudin and Joanna Radin. Why are we using black box models in Al when we don't need to? lesson from an explainable AI competition. Harvard Data Science Review, 1(2):10 162, 2019.
[38] Mattco Scalabrin, aaria Frasson, Emanuela Ruggiero, Rosalba Perrone, Flena Tosoni, Sara Lago, Mar- tina Tassinari, Giorgio Palú, and Sara N Richter. The cellular protein hnRNP A2/B1 enhances HIV-1 transcription by unfolding LTT promoter G-quadruplexes. Scientific Reports, 7(1):1-13, 2017.
[39] Paola Secchiero, Davide Zella, Sabrina Curreli, Prisco Mirandola, Silvano Capitani, Robert Gallo, and Giorgio Zauli. Pivotal role of cyclic nucleoside phosphodiesterase 4 in tat-mediated CD4+ T cell hyperactivation and HIV type replication. Proceedings of the National Academy of Sciences, 97(26): 14620-14625, 2000.
[40] Lesia Semenova, Cynthia Rudin, and Ronald Parr. On the existence of simpler machine learning models. 2022. [41] Gavin Smith, Roberto Mansilla, and James Goulding. Model class reliance for random forests. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22305-22315. Curran Associates, Inc., 2020.
In 2022 ACM Conference Fairness, Accountability, and Transparency, pages
[42] S. Thrun, J. Bala, F. Bloedorn, I. Bratko, B. Cestnik, J. Cheng, K. De Jong, S. Dzeroski, R. Hamann, K. Kaufman, S. Keller, I. Kononenko, J. Kreuziger, R.S. Michalski, T. Mitchell, P. Pachowicz, B. Roger, H. Vafaie, W. Van de Velde, W. Wenzel, J. Wnek, and J. Zhang. The MONK's problems: A perfor- mance comparison of different learning algorithms. Technical Report CMU-CS-91-197, Carnegie Mellon University. Computer Science Department, Pittsburgh, PA, 1991.
[43] Theja Tulabandhula and Cynthia Rudin. Robust optimization using machine learning for uncertainty sets. ECML/PKDD 2014, page 121, 2014.
[44] Fang Wang. Shujia Huang, Rongsui Gao. Yuwen Zhou, Changxiang Lai, Zhichao Li, Wenjie Xian, Xiaobo Qian, Zhiyu Li. Yushan Huang, et al. Initial whole-genome sequencing and analysis of the host genetic contribution to COVID-19 severity and susceptibility. Cell Discovery, 6(1):83, 2020.
12

---

[45] Wen-Fang Wang, Hui-Juan Zhong, Shu Cheng, Di Fu, Yan Zhao, Hua-Man Cai. Jie Xiong, and Wei-Li Zhao. A nuclear NKRF interacting long noncoding RNA controls EBV eradication and suppresses tumor progression natural killer/T-cell lymphoma. Biochimica et Biophysica Acta (BBA) -Molecular Basis of Disease, page 166722, 2023.
[46] Wikipedia contributors. Box plot, 2023. httttpe://ee..wkipppdeeeee http::/wwww...poa..o.ooooooaeeaa http:p//..aa...iioooo..o.......d accessed 4-Ma3-2023J.
[Online;
[47] Brian Williamson and Jean Feng. Efficient nonparametric statistical inference on population fcature importance using shapley values. In International Conference Machine Learning, pages 10282-10291. PMLR, 2020.
[48] Brian D Williamson, Peter B Gilbert, Noah R Simon, and Marco Carone. A general framework for inference on algoritmm-agostic variable importance. Journal of the American Statistical Association, pages 1-14, 2021.
[49] Rui Xin, Chudi Zhong, 7hi Chen, Takuya Takagi, Margo Seltzer, and Cynthia Rudin. Exploring the whole rashomon set of sparse decision trees. Advances in Neural Information Processing Systems, 35: 22305-22315, 2022.
[50] Bin Yu. Stability. Bernoulli, 19(4): 1484 - 1500, 2013. doi: 10.3150/13-BEISP14
[51] Bin Yu and Karl Kumbier. Veridical data science. Proceedings the National Academy of Sciences, 117 (8):3920-392) 2020. doi: 10.1073/pnas.190111 1911321117.
[52] Lu Zhang and Lucas Janson. Floodgate: inference for model-free variable importance. arXiv preprint arXiv:2007.01283 2020.
13


Reviews:
[{"review_id": "kqZ5KEqpsz", "reviewer": "Reviewer_tvv9", "summary": "The paper presents a new method to find important predictive variables for a set of good prediction models (Rashomon set). The Ranshomon set is often unstable when some perturbations are added to the dataset. The present solution is based on an importance metric called Rashomon Importance Distribution (RID). Bootstrap sampling is proposed to estimate the cdf of RID. The method assesses the importance of each variable using the CDF that takes into account the Rashomon sets from different bootstrapped samples. This reduces the instability in variable selection due to the instability of the underlying Rashomon set.", "questions": "See weaknesses. ", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Originality: The instability problem of variable selection for a Rashomon set is underexplored in the literature. The instability issue is more challenging than finding important variables for one model on one particular dataset. \n2. Quality: The paper is relatively well written. The proposed method is intuitive. A set of simulations and real-data studies demonstrate the value of the proposed method in applications.\n3. Clarity: The assumption of the proposed method is clear. Some basic consistency analysis is provided for the bootstrapping procedure.\n4. Significance: The paper makes a good contribution to addressing the instability problem that deserves more attention from the field.", "weaknesses": "1. Notation. For example in equation (2), the probability in the LHS is not indexed by n but the expectation in the RHS is an empirical distribution on the n observations. This is very confusing for me. What exactly the bootstrapping procedure is estimating? Is the unknown expectation assuming n observations drawn from an unknown distribution, or something else?\n2. Assumption 1. The connection between Rashomon Importance Distribution for a particular feature j and Rashomon Loss Distribution (RLD) is still not very convincing to me. The author should provide more intuitive explanations in the main text (e.g. using a linear model as an example). The current form of the assumption doesn't seem to hold for many model classes. \n3. The method is demonstrated in terms of finding the important variables. But does the method increases the false discovery of many non-important variables? More clarification and experiments can be provided on this aspect. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments.\n\n\nFirst, we would like to clarify the meaning of Equation 2. Equation 2 specifies the quantity we hope to estimate: the distribution of variable importance for all good models across all reasonable perturbations for the given dataset. However, considering all perturbations of the dataset is computationally intractable  (note that there are (2(n-1) choose (n-1)) unique bootstraps for a dataset of size n), which is why we propose our bootstrapping procedure for estimating RID. We make no assumptions on the process generating the originally observed dataset; rather, we estimate this quantity for a fixed dataset.\nTo make this notation clearer, we propose the following change: we will replace $RID_j(\\varepsilon, \\mathcal{F}, \\ell; \\lambda)$ with $RID_j(\\mathcal{D}^{(n)}, \\varepsilon, \\mathcal{F}, \\ell; \\lambda).$\n\n\nPartially in response to reviewer tvv9’s comment, we discuss Assumption 1 in the combined response.\n\n\nFinally, the RID framework does not necessarily increase false discovery rates. All of our simulated datasets include extraneous/irrelevant features. Chen’s DGP contains 6 irrelevant features, Friedman’s DGP contains 1 irrelevant feature, and the Monk DGPs contain 3 irrelevant features. The number of irrelevant covariates come from the papers with these original simulation setups. Our experiments show that RID consistently produces lower variable importance values for unimportant variables than for important variables. Furthermore, the recovery experiments in Figure 2 (bottom) demonstrate that RID’s box and whisker range contains the true model reliance; for unimportant variables, the true model reliance is 0. Therefore, it is unlikely that RID would confuse an unimportant variable as seeming important.\n\nAdditionally, practitioners especially concerned with false discovery may integrate our framework with existing false discovery rate control methods (e.g., Benjamini-Hochberg or Knockoffs) and expect the first variables excluded to be the extraneous ones. Further, RID produces an entire distribution of variable importance, allowing practitioners to ask questions like “what is the probability each variable has a model reliance greater than 0?” By calibrating the lowest acceptable probability for calling a variable truly important, practitioners may control how many variables are considered “important”, further controlling false discovery rates.\n"}, {"review_id": "zxpg1I5xqg", "reviewer": "Reviewer_zs1J", "summary": "This paper introduces a method for assessing the variable importance in prediction, when the goal is to understand variable importance as defined with respect to the underlying data-generating process, as opposed to a specific model.  To that end, a method is proposed which incorporates the concept of Rashomon sets (models whose performance is approximately optimal) and stability (e.g., considering Rashomon sets over different bootstrapped replications of the data) to construct a distribution of variable importance measures for each variable.\n", "questions": "Here I have collected relevant questions that appear in my review above.  As stated previously, I am willing to update my score given compelling answers to some of these questions.\n\n1. (W1) How would you explain to a skeptical audience why we should be primarily concerned with variable importance measures that are not linked to a particular model?\n2. (W2) If I were interested in making claims like \"the lower bound of the variable importance over the Rashomon set is higher than L with high probability\", is that something that could be read out from the RID?\n3. (W2) It appears that [16] (Fisher et al. 2019) gives finite-sample / high-probability bounds on the upper/lower bounds of variable importance over the Rashomon set.  How should I think about the difference between the \"stability\" goal of this work (which is fundamentally a finite-sample concern) compared to the goal of providing high-probability bounds in that work?\n4. (W3) How would you formally define \"stability\" in this context, and why we should expect the approach in question to achieve it?\n\nOf these questions, I am most interested in the answers to 2-4. I understand that 1 is a bit more subjective, and despite appearing first, it has the smallest impact on my score.\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall, I rather enjoyed this paper, modulo some reservations that I outline in the \"weaknesses\" section. The presentation of the claimed contributions is clear, the contextualization to related work seems thoughtful, and the experiments support the main argument.\n\nFirst of all, I found much of the presentation to be quite clear.  Figures 1 and 2, for instance, give a fairly clear summarization of the motivating problem and the corresponding method.\n\nSecond, I found the technical contribution to be fairly clear relative to related work. Here, the main contribution appears to be the incorporation of bootstrapping to incorporate finite-sample uncertainty and improve stability, relative to related work that considers Rashomon sets for variable importance (e.g., citation [16] in this work).\n\nThird, while the main contribution (focusing on \"stability\") was not quite as formalized as I might have liked, the experiments in Section 4 seem to provide compelling evidence that the proposed approach more captures variable importance more reliably than baseline methods, including a fairly long list of alternative approaches.", "weaknesses": "There are a few points in this paper that I felt were somewhat unclear.  I look forward to discussion with the authors during the response period, and I am willing to change my score.  I focus here on motivation for the given approach, and justification for the claims of \"stability\", which I found lacking in places. Generally, I found the technical results to be fairly straightforward consequences of the assumptions.\n\n### (W1) Motivation for \"stable\" variable importance somewhat unclear\n\nThe main weakness of this paper, in my view, lies in the motivation. In several places, the importance (no pun intended) of finding the \"ground truth\" variable importance measures is stated as an obvious fact, without justification.  For instance, on line 24 it is claimed that \"Variable importance would ideally be measured as the importance of each variable to the data generating process\".\n\nIt is not clear to me why this claim should be obvious - rather, it seems reasonable that we might want to understand variable importance in the context of a specific model, trained on a specific dataset, to better understand what drives the predictions of that model from an explainability perspective.\n\nFor instance, Fisher et al. 2019, cited in this paper as [16], give a fairly nuanced view when introducing the idea of Model Class Reliance (from my skim).  As I understood that work, the motivation for establishing a range of possible values for variable importance (VI) stems not necessarily from a desire to understand \"the data generating process\", but from the desire to understand variable importance for a single model. The catch is that the *model of interest may be proprietary and not available to the user* (e.g., in recidivism prediction).  In that setting, having upper and lower bounds on VI allows us to draw some conclusions (e.g., if the lower-bound is particularly high, we can conclude under some assumptions that the proprietary model depends on this feature).\n\nI think one could make a similar argument here, e.g., if the exact underlying dataset is also not available to us, we might be concerned about the sensitivity of our VI analysis to small differences in the data-generating process.  I would appreciate some comment from the authors on this question of the general motivation for finding stable variable importance measures.\n\n### (W2) Why consider distributions vs bounds?\n\nI had some trouble understanding the motivation for the Rashomon Importance Distribution.\n\nThis distribution seems to be something like \"averaging\" over the bootstrap replicates. As I understood it, if a variable's importance is at most k in one bootstrap sample, for all models in the Rashomon set, but greater than k for all models in the Rashomon set in 99 other bootstrap samples, then we will average these to say that the CDF at k is 1/100.\n\nIt wasn't clear to me how this approach would fit with the goal of establishing upper/lower bounds for importance measures.  I suppose that one could do this using quantiles of the resulting distribution, but it's not entirely clear to me what that would be measuring.\n\nTL;DR: If I were interested in something like \"the lower bound of the variable importance over the Rashomon set is higher than L with high probability\", is that something that could be read out from the RID?  That would seem like a more natural characterization of \"stability\" of results.\n\nAs an aside, it appears that [16] (Fisher et al. 2019) gives finite-sample / high-probability bounds on the upper/lower bounds of variable importance over the Rashomon set.  How should I think about the difference between the \"stability\" goal of this work (which is fundamentally a finite-sample concern) compared to the goal of providing high-probability bounds in that work?\n\n### (W3) What is stability, exactly, and why should we expect this method to achieve it?\n\nGiven that one of the main distinctions to prior work appears to be the focus on \"stability\", I was hoping to see some formal definition for what that means, and why the bootstrapping approach in this paper should be expected to achieve it.\n\nPresumably achieving stability is not the same as accurately estimating RID, since RID is defined in such as way that it can be estimated, for any sample size, with arbitrary precision. This fact is due to the definition of RID as an expectation over a bootstrapping distribution, with respect to our given dataset of size $n$ (see lines 158-161), allowing one to simply take more bootstrap replicates to estimate it precisely (as noted on lines 203-205).  If stability is a problem caused by finite samples sizes, then presumably it cannot be solved by simply re-sampling a small dataset.\n\nThe fact that the given strategy achieves stability seems to be taken as a given, e.g., RID is introduced on lines 150-151 as \"we define a stable quantity for variable importance\", it is said that \"intuitively, this [Eq 2] provides greater weight to the importance of variables for stable models\" (line 163), then it is concluded that \"since we stably estimate the entire distribution of variable importance values, we can create stable point estimates\" (lines 209-210), etc.\n\nI would be curious to get the thoughts of the authors on what stability means in this context, and why we should expect the approach in question to achieve it - is this simply a question of intuition, to be backed up by experiments?  If so, please just clarify that upfront.\n\n## Other minor points\n\nIt would be nice to discuss Assumption 1 in a bit more detail, explaining why it is necessary, when we might expect it to hold, etc.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments. We respond to each concern below, following the same numbering used in the review. \n\n(W1) The goal of measuring variable importance for a particular model is different than ours. Scientists are often interested in understanding causal relationships between variables, but running randomized experiments is time-consuming and expensive. Given an observational dataset, we can use global variable importance measures to check if there is some relationship between two variables. If there is no relationship, we can be confident that there is little to no causal relationship. In this setting, the researcher is not interested in variable importance for a particular model but rather for the dataset as a whole. After isolating the handful of variables for which the variable importance is non-negligible, we can run randomized experiments to investigate true causal relationships. This is the use-case in our case-study: we trim the genes-of-interest in HIV load studies from 100 to five, considerably reducing the cost and time of further research.\n\n(W2.1) Yes, we can make this claim! This is the strategy we use to identify a handful of genes that are associated with high expression of Human Immunodeficiency Virus (HIV) RNA. Figure 5 displays the probability of the lower bound on conditional model reliance over Rashomon sets and data perturbations being greater than 0. This analysis could be repeated for any threshold value.\n\n(W2.2) We would first like to specify what we mean by stability. Stability is a desiderata of trustworthy analyses: a procedure is considered “stable” if small perturbations to the observed dataset (e.g., replacing a single observation) do not significantly change the computed statistic. Prior work has pointed out that there is wide agreement on the intuition behind stability, but very little on how to quantify it (Kalousis et al. 2005; Nogueira et al., 2017). As such, in line with other stability research, we do not subscribe to a formal definition and treat stability as a general notion (Yu, 2013; Yu and Kumbier, 2020; Kalousis et al. 2005; Nogueira et al., 2017). \n\nBecause variable importance is often used for high stakes decision making, we need to ensure that our variable importance metrics are robust to such sampling issues. Otherwise, decision makers may be working with faulty, non-reproducible insights. While stability is fundamentally a finite-sample concern, we only ever work with finite-sample data in practice.\nFisher et al.’s model class reliance (MCR) differs from ours because it (1) does not consider stability issues and (2) a range of min/max values is highly susceptible to outlier problems.\n\nAs shown in Figure 1 (b) and in section D4 of the supplement (Figures 8-11), MCRs are scattered across these bootstrap iterations and do not generalize to different draws from the same DGP. These results suggest that using MCRs can lead to analyses that may not generalize well. In contrast, our intervals remain stable in both settings, as shown in Figure 4  and in section D4 of the supplement (Figures 8-11).\n\nAdditionally, MCR only describes the min/max values that the model reliance could potentially be. These intervals may be less meaningful because they do not describe the interval of likely values of variable importance; outlier values of variable importance may drive MCRs to be very wide and not useful. In contrast, because we estimate a distribution of variable importance over Rashomon sets and bootstrap perturbations, we can compute measures like the highest probability regions (Figure 3 (bottom)), mean variable importance values (Figure 3 (top)), or the probability that each variable has variable importance above some target value (Figure 5). The distribution offers far more flexibility than the MCR. \n\n(W3) We discuss our definition of stability in our answer to W2.2. The stability literature has often used subsampling/resampling methods and our bootstrapping approach similarly yields stability. For example, Basu et al. (2018) use the bootstrapping procedure to find high order interactions of features that are stable to data perturbations. Additionally, in the context of algorithmic stability (Bousquet and Elisseeff, 2002), bagging has been shown to stabilize decision tree algorithms (Buhlmann and Yu, 2002; Grandvalet, 2006). Further, we show empirically that RID’s intervals are far more similar between independently generated datasets than the other methods that account for the Rashomon effect in Figure 4 , demonstrating that bootstrapping also stabilizes our variable importance measurements.\n\nReferences\n\nSumanta Basu, Karl Kumbier, James B Brown, and Bin Yu. Iterative random forests to discover predictive and stable high-order interactions. Proceedings of the National Academy of Sciences, 115(8):1943–1948, 2018.\n\nOlivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research 2: 499-526, 2002.\n\nPeter Bühlmann and Bin Yu. Analyzing bagging. The annals of Statistics, 30(4):927–961, 2002.\n\nYves Grandvalet. Stability of bagged decision trees. In Proceedings of the XLIII Scientific Meeting of the Italian Statistical Society, pages 221–230. CLEUP, 2006.\n\nBin Yu and Karl Kumbier. Veridical data science. Proceedings of the national academy of sciences,\n117(8), 3920–3929. 2020.\n\nBin Yu. Stability. Bernoulli, Bernoulli 19(4): 1484-1500, 2013.\n\nSarah Nogueira, Konstantinos Sechidis, and Gavin Brown. On the stability of feature selection algorithms. The Journal of Machine Learning Research 18.1: 6345-6398, 2017.\n\nAlexandros Kalousis, Julien Prados, and Melanie Hilario. Stability of feature selection algorithms. In IEEE International Conference on Data Mining (ICDM’05), 2005."}, {"review_id": "mdJZZAdpPH", "reviewer": "Reviewer_eXQc", "summary": "The paper studies the problem of quantifying variable importance in a stable manner. The authors argue that multiple models may explain a target outcome equally well for a given dataset. However, current methods to quantify variable importance only account for one of these models; therefore, without accounting for different explanations, different researchers may arrive at conflicting (and valid) conclusions. To solve this problem, the authors propose a framework to quantify variable importance that accounts for the set of all good models. The authors provide empirical and theoretical results to support their framework. \n", "questions": "* Are there any losses in using an approximation for the Rashomon set instead of the “True” empirical Rashomon set? Intuitively, there seems to be a tradeoff between the approximation for the Rashomon set and the RID. It would be interesting to have a result highlighting it in the main paper. \n\n* Can authors include an experiment like the one in Figure 3 top but for more complex data generation processes? For example, consider the ground truth DGP to be a deep neural network and calculate variable importance using decision trees. \n", "limitations": "The authors discuss the limitations of the proposed method. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper discusses an important and interesting problem of assigning variable importance while considering the whole set of good models and ensuring stability. This problem can interest the community studying the impacts of the Rashomon effect and, more broadly, the interpretability community. \n\n* The authors provide compelling experimental results in synthetical data, indicating that the proposed method can capture variable importance in data generation. They also compare with other methods in the literature and show that RID performs better or equal to state-of-the-art methods (Figure 3 top).\n\n* Theoretical results in Theorems 1 and 2 ensure that estimating by bootstrapping converges to the value of interest. \n\n* The Case study in Section 5 is fascinating. Unlike others in the literature, the authors demonstrate that their method associates a specific gene with HIV – previously an unknown relationship. \n", "weaknesses": "* The Rashomon set is still unknown for most model classes, making the application of the method infeasible using the tools presented in the paper. \n\n* Assumption 1 seems reasonable for model classes such as linear models and GAMs. However, how it will behave in more complicated classes is still unknown.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments. Since another reviewer also raised concerns about relatively few model classes having known Rashomon sets, we have addressed this issue in the combined response. We also address reviewer eXQC’s question about Assumption 1 in the combined response for similar reasons. Finally, we have addressed both of reviewer eXQc’s questions in the combined response in order to reference figures showing new results. "}, {"review_id": "vldsMWQOrz", "reviewer": "Reviewer_gRCY", "summary": "This paper proposes a variable importance framework, the Rashomon importance distribution (RID), that is robust to both the Rashomon effect and to dataset resampling. It motivates the need for such a framework, and surveys existing related methods. It then provides a detailed theoretical explanation of the proposed variable importance (a distribution) and a method for its estimation. The paper presents several experiments which demonstrate that RID can distinguish between important and unimportant/extraneous variables more reliably than previous methods. It then presents a case study in immunology (HIV research) wherein RID was able to identify a variable importance that was previously undetected, creating a lead for future investigation. \n", "questions": "In Equation 2. (and others in the form of a ratio of model set cardinalities), did you consider a heterogenous weighting of the set members (the models), for instance a weight which decreases based on their deviance from optimality? ", "limitations": "The limitations could be emphasized a little more. For instance the claim in the abstract that “[Our framework] can be integrated with most existing model classes” is really only true in a theoretical sense. There are many model classes for which even estimating the Rashomon set is computationally prohibitive, let alone do so for hundreds of bootstrap resampled datasets. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is a very strong paper overall. \nThe quality of the writing and overall presentation (figures, equations, etc.) is excellent, within the top 5% of papers. \nThe authors are very familiar with the relevant prior work in the area, which is clearly demonstrated in the Related Work section.\nThe technical contributions are important. They further strengthen the arguments for using simple, interpretable model classes (like sparse trees).\nThe inclusion of a case study where the method creates real value in an important research area demonstrates its practical value. \n", "weaknesses": "The paper’s main weakness is its (current) lack of practical applicability to non-linear model classes outside of sparse trees. Because of this, the paper’s impact at a venue where most researchers (the vast majority perhaps) are working primarily with neural networks and transformers may be more limited. That said, I think this work along with the related work it highlights nonetheless merits visibility. Collectively, this vein of research creates a compelling argument for using inherently interpretable models, and has the potential to shift the default tools used by data science practitioners. \n\nSuggestions:\n\nThe paper could be strengthened by running some of the experiments in Section 4 on real datasets for which a subset of the variables are known to be important/unimportant, (extraneous ones may also be added).  \n\nSome of the plot colors could be improved for greater visual clarity / contrast. For instance the greens/blues in figures 2 & 3 bleed into each other, especially when printed. \n\nIt would be good to refer the reader to Appendix Section D.3 in Section 4.3 on the stability of RID, possibly putting the discussion on robustness to $\\varepsilon$ there. \n\nIn the main text, it would be good to note that a timing analysis was conducted, referring the reader to Section D.5.\n\nIt would have been interesting to investigate the stability of RID across different dataset resample methods (e.g. bootstrap v.s. subsampling).\n\nIt would be good to explicitly list some of the model classes for which the RID can currently be computed.\n\nNitpicking a little…\nLine 140: Unless I’m mistaken, g* tells us P(X,Y), while f^* often aims to model P(Y|X), and needs to be used alongside some approximation of P(X) to be a surrogate for g*.\nLine 149: “the Rashomon set describes the set of good explanations for a single dataset” -- this is only true if the models themselves are interpretable. \nLines 162 and 187: seem to describe a model’s variable importance score as though it is fixed (independent of the dataset draw), i.e. by describing it as being a quantity weighted by the number of datasets for which f is in the Rashomon set, rather than something that can vary with each dataset (and only included when f is in the Rashomon set). The mathematical notation clarifies this however.\nLine 286: “For real datasets” -- I think you mean the remaining synthetic datasets that include noise\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their thoughtful comments. We particularly appreciate the comments suggesting formatting/writing improvements; we do not specifically reference each of these in our response, but we do plan to integrate them into our camera ready version of the work.\n\nWe acknowledge reviewer gRCY’s concern that this work may not have the largest splash at a conference where neural networks and transformers currently dominate; however, NeurIPS has always valued a broad set of problems, including those in scientific and high-stakes domains (many of which are not neural network related). RID is likely to have a large impact in domains like genetics, biology, and ecology. Within the past year, Rashomon sets have become available for trees (which was a Neurips oral in 2022) and GAMs, and new ones are likely to come out soon, adding to the impact of this work. As we discussed in the general response, trees and GAMs are already used for a huge variety of applications and are as accurate as deep learning models for tabular data sets across domains.\n\nWe like the idea of repeating the experiments from Section 4 on a real dataset with known important/unimportant variables, but we have had trouble finding a non-synthetic dataset in which we are certain which variables are important. Even if we add extraneous variables, it is difficult to repeat our experiments from Section 4 because a dataset may already contain some extraneous variables. As such, we would need to find a dataset where we are completely certain which variables are important and which are unimportant. That said, we are open to suggestions if any such datasets come to mind!\n\nWe agree that it may be interesting to investigate the impact of different resampling methods on RID. While we have not had time to explore this experimentally, we believe that subsampling and bootstrapping should produce similar results. It has been shown that both subsampling and bootstrapping can induce stability (Basu et al., 2018; Meinhausen and Buhlmann, 2010; Buhlmann and Yu, 2002; Grandvalet 2006). Since both methods have been shown to be effective in the stability literature, we would expect both to be effective here. Additionally, with a large enough dataset, RID should not differ significantly when using bootstrapping or subsampling because of the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality. The DKW inequality states that as the number of observations increases, the empirical cumulative distribution function will converge to the cumulative distribution function (CDF) from which samples were drawn at a rate of $\\sqrt{n}$. Then – by using the triangle inequality – we see that the distance between the empirical CDFs of a subsampled and a bootstrap sampled dataset would converge at a rate of $O(\\sqrt{n})$. Because RID is a function of these datasets that are also similar, the bootstrap and subsampled datasets’ RIDs should be similar.\n\nWe did consider heterogeneously weighing models while developing our framework, but we opted not to include an explicit weighting because our bootstrap framework implicitly weights for optimality. The truly closest-to-optimal models should generalize well and will therefore show up in many of the bootstrapped Rashomon sets; on the other hand, models that only fit a specific bootstrapped dataset well will only belong to a single bootstrapped Rashomon set. Therefore, near-optimal models’ variable importance estimates will contribute more to RID’s calculation than overfitting models that are far from optimal. If we were to heterogeneously weight the model's contributions by loss, we would inflate the measurements from over-fitting models, which would skew our analyses.\n\nReferences\n\nSumanta Basu, Karl Kumbier, James B Brown, and Bin Yu. Iterative random forests to discover predictive and stable high-order interactions. Proceedings of the National Academy of Sciences, 115(8):1943–1948, 2018.\n\nMeinshausen, Nicolai, and Peter Bühlmann. Stability selection. Journal of the Royal Statistical Society Series B: Statistical Methodology 72.4: 417-473, 2010.\n\nPeter Bühlmann and Bin Yu. Analyzing bagging. The annals of Statistics, 30(4):927–961, 2002.\n\nYves Grandvalet. Stability of bagged decision trees. In Proceedings of the XLIII Scientific Meeting of the Italian Statistical Society, pages 221–230. CLEUP, 2006."}]

Author rebuttal:
We would like to thank all reviewers for their thoughtful and constructive feedback. We hope our response addresses some of the issues raised, and look forward to our continued discussion.

Reviewers gRCY and eXQc noted that Rashomon sets can only be computed for a handful of model classes. We would like to note that generalized additive models (GAMs) and decision trees are two of the most effective model classes – often as accurate as neural networks – for tabular data, the setting we focus on in this paper. The papers that we cited (McTavish et al., 2022; Liu et al., 2022) showed performance at least as good as black box baselines for the challenging FICO dataset for the 2018 Explainable ML Challenge. It is also worth noting that the kind of variable importance we are interested in, variable importance for a DGP, is most relevant for tabular data. For example, in computer vision it is unlikely that any individual pixel may be meaningfully “important” or “unimportant”. Therefore, our framework is already useful for many practitioners. Further, the idea of computing Rashomon sets is quite new. As such, we expect the number of algorithms for computing Rashomon sets to continue to grow rapidly with time.

Reviewers tvv9, zs1J, and eXQc noted that a more thorough justification of Assumption 1 is needed and that the current form of the assumption may not hold for many model classes. In response to these comments, we propose to relax the assumption from: 

If  $\rho\left(RLD(\varepsilon, \mathcal{F}, \ell;\lambda),  LD(\ell, n;\lambda) \right) \leq \gamma$, then $\rho\left(RID_j(\varepsilon, \mathcal{F}, \ell; \lambda), RID_j(\varepsilon, \{g^*\}, \ell ; \lambda) \right) \leq d(\gamma)$ for a monotonically increasing function $d: [0, \ell_{\max} - \ell_{\min}] \to [0, \phi_{\max} - \phi_{\min}]$ such that $d(0)=0.$ 

To the following relaxed assumption:

$\rho\left(RLD(\varepsilon, \mathcal{F}, \ell;\lambda),  LD^*(\ell, n;\lambda) \right) \leq \to 0 \implies \rho\left(RID_j(\varepsilon, \mathcal{F}, \ell; \lambda), RID_j(\varepsilon, \{g^*\}, \ell ; \lambda) \right) \to 0$.

The new assumption states that, as the distance between $RLD$ and $LD$ converges to 0, the distance between $RID_j(\varepsilon, \mathcal{F}, \ell; \lambda)$  and $ RID_j(\varepsilon, \{g^*\}, \ell ; \lambda)$ will also converge to 0. We expect this to hold for many model classes and variable importance metrics since it simply requires that models that are extremely close to the DGP in terms of loss must reason on similar variables. Note that the examples given in Section C of the supplement also satisfy this modified assumption, as they show that a stronger version of it holds.

Reviewer eXQc asked whether RID is sensitive to using estimated Rashomon sets (rather than exactly computed Rashomon sets, as in the main paper). Although we cannot yet give a definitive answer to this question, we conducted an experiment studying how consistent RID was when some of each Rashomn set is missing. In order to evaluate this, we randomly removed 25%, 50%, and 75% of models from each Rashomon set when computing RID for Friedman’s DGP. We used the same hyperparameter settings as in our experiments on Friedman’s DGP as in the main paper. We found that RID maintained equal performance in terms of importance classification and near-equal performance in recovery performance across all three settings. Therefore, if estimation error is independent between bootstrap iterations and models are only omitted from the Rashomon set (rather than added), we believe that RID will function well with estimated Rashomon sets. Figure 1 of the attached documents illustrates this result.

Reviewer eXQc suggested we evaluate RID using a more complicated data generation process, particularly a neural network. As such, we also evaluated the ability of RID to discriminate between extraneous and important variables for a DGP in the form of a neural network. Our DGP consisted of five fully connected layers with a rectified linear unit (ReLU) non-linearity between each pair. The first four layers used the weight matrix: $\begin{bmatrix} -3 & -2 & -1 & 1 & 2 & 3 \end{bmatrix}^T \begin{bmatrix} -1 & -0.9 & -0.8 & 0.8 & 0.9 & 1 \end{bmatrix}$. The final layer used the weight matrix: $ \begin{bmatrix} -1 & -0.9 & -0.8 & 0.8 & 0.9 & 1 \end{bmatrix}$.

We generated 25 features uniformly at random, between 0 and 1, and computed the outcome as a function of the first 6 features. Standard normal noise was added to the output of the DGP, and a binary label was constructed indicating whether the outcome was positive or negative. As shown in Figure 2 of the attached documents, we found that RID perfectly discriminates between extraneous and important features. However, RID did not recover all true MR values. We believe this is because sparse decision trees struggle to represent a dense neural network (which is something a user could figure out empirically and correct for). However, it is worth noting that this DGP is closer to a unrealistic “game-like” setting like chess, which requires a high-complexity model, than that of a more practical setting like medical records, where not all information is observed and the outcome may be far from deterministic function of the inputs. For such a dense DGP, another model class such as generalized additive models may be more appropriate. Nonetheless, RID succeeds in identifying extraneous variables even when modeling a difficult DGP using a less appropriate model class.

References

Hayden McTavish, 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.

Jiachang Liu, Chudi Zhong, Margo Seltzer, and Cynthia Rudin. Fast sparse classification for generalized linear and additive models. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.

Meta-review: There was a consensus that this is a strong contribution that should be presented in NeurIPS
Decision: Accept (spotlight)