PaperlayerView exact revision on arXiv

Source-linked AI summary

All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously

Aaron Fisher, Cynthia Rudin, Francesca Dominici

arXiv:1801.01489v5stat.ME

TL;DR

Single-model variable importance can miss how differently near-equally accurate models use covariates. The paper introduces MCR to measure that range across a model class, develops supporting theory and estimators, and applies it to reliance on race and sex in proprietary recidivism prediction.

  • Problem

    Existing VI measures generally do not account for multiple near-equally accurate models that may rely on different covariate information.

  • Method

    MCR takes the upper and lower variable-reliance limits across a Rashomon set of well-performing models, with bounds, estimator theory, and computational procedures.

  • Results

    The paper derives connections among permutation importance, U-statistics, conditional importance, conditional causal effects, and additive-model coefficients, then applies MCR to COMPAS-related recidivism prediction.

  • Takeaways & Limitations

    MCR provides a more comprehensive importance description for well-performing model classes and can inform VI for unknown proprietary models.

  • Takeaways & Limitations

    Unmeasured race proxies and conditional associations among COMPAS inputs may affect conclusions about race reliance.

Abstract

from arXiv · show

Variable importance (VI) tools describe how much covariates contribute to a prediction model's accuracy. However, important variables for one well-performing model (for example, a linear model $f(\mathbf{x})=\mathbf{x}^{T}β$ with a fixed coefficient vector $β$) may be unimportant for another model. In this paper, we propose model class reliance (MCR) as the range of VI values across all well-performing model in a prespecified class. Thus, MCR gives a more comprehensive description of importance by accounting for the fact that many prediction models, possibly of different parametric forms, may fit the data well. In the process of deriving MCR, we show several informative results for permutation-based VI estimates, based on the VI measures used in Random Forests. Specifically, we derive connections between permutation importance estimates for a single prediction model, U-statistics, conditional variable importance, conditional causal effects, and linear model coefficients. We then give probabilistic bounds for MCR, using a novel, generalizable technique. We apply MCR to a public data set of Broward County criminal records to study the reliance of recidivism prediction models on sex and race. In this application, MCR can be used to help inform VI for unknown, proprietary models.

1. Introduction

Existing variable-importance measures assess a single prediction model, but many near-equally accurate models may rely on different covariates. The paper addresses this Rashomon effect by defining MCR as the range of reliance across well-performing models and developing theory, estimation tools, and applications for proprietary models.

  • Existing VI measures describe covariate contributions to a model’s predictive accuracy, often through accuracy loss after permutation.Permutation-based measures are used in Random Forests and related perturbation methods.
  • The Rashomon effect arises because many models may fit data almost equally well while relying on entirely different covariate information.This makes a single model’s importance assessment potentially dependent on the analyst’s model choice.
  • MCR summarizes the highest and lowest reliance on a variable among well-performing models in a prespecified class.The resulting range is intended to reflect the prediction problem rather than one analyst’s fitting choices.
  • The paper connects permutation-based model reliance to U-statistics, conditional importance, conditional causal effects, and additive-model coefficients.It extends model reliance from an individual model to a model class.
  • The authors develop finite-sample bounds and computational procedures for estimating MCR and extend the framework to inference for other characteristics of well-performing models.Examples include risk predictions for a covariate profile and variation in predictions across models.
  • The framework is applied to recidivism prediction because proprietary courtroom models may rely on race, sex, or their proxies while remaining inaccessible for direct study.For COMPAS, alternative flexible models can be used to study reliance when the proprietary predictions are publicly available.

2. Notation & Technical Summary

The paper studies near-optimal models as a Rashomon set and measures how widely their reliance on a covariate can vary. It develops empirical MCR procedures, finite-sample bounds, and extensions connecting reliance to coefficients, causal effects, and conditional importance.

  • Notation: A model class F is a prespecified subset of measurable functions, evaluated with a nonnegative loss such as squared error or hinge loss.
  • Rashomon sets: The population ϵ-Rashomon set contains models whose expected loss is no more than ϵ above a reference model’s loss.These models may arise from differences in measurement, processing, parameterization, covariate selection, or other analysis choices.
  • Model reliance: Model reliance MR(f) is the ratio of expected loss after noise makes X1 uninformative to expected loss without noise.Higher MR values indicate greater reliance on X1; an MR of 2 doubles loss, whereas 1 indicates no reliance.
  • Model class reliance: Model class reliance is the range of MR values attained by well-performing models, with empirical MCR using in-sample analogues of the Rashomon set and MR.
  • Technical results: The paper derives finite-sample bounds supporting empirical MCR estimation and gives an optimization procedure with detailed implementations for regularized linear and reproducing-kernel models.For complex classes such as neural networks, computing empirical MCR remains an open problem.
  • Extensions: Extensions connect MR for additive models to coefficients, binary-covariate MR to conditional causal effects, and conditional MR to information in X1 unavailable from X2.The framework also generalizes finite-sample results to arbitrary characteristics of models in a Rashomon set.

3. Model Reliance

Model reliance quantifies how much a fixed model’s loss changes when X1 is switched with an independent value, and empirical estimators implement this operation over observed data. The paper links these estimators to permutation importance and U-statistics, enabling unbiasedness, asymptotic normality, and finite-sample bounds.

  • Definition: Model reliance compares a model’s expected loss after switching X1 with its standard expected loss using the original covariate relationship.The switch renders X1 uninformative about Y while preserving its marginal distribution.
  • Interpretation: Higher MR values indicate greater reliance: MR(f)=2 doubles loss after scrambling X1, while MR(f)=1 indicates no reliance.Values below 1 are harder to interpret because the model relies less on X1 than a random guess.
  • Estimation: Empirical switched loss aggregates losses across observed pairings of (Y, X2) with X1, excluding pairings already present in the original sample.A split-sample alternative matches the first half’s (Y, X2) values with the second half’s X1 values and vice versa.
  • Connections: MR is inspired by Random Forest permutation importance but applies to arbitrary prediction models, whereas related work often focuses on the conditional expectation function.
  • U-statistics: The empirical estimators for original loss, switched loss, and their ratio are U-statistics and are unbiased, asymptotically normal, and equipped with finite-sample probabilistic bounds under minor conditions.
  • Uniform estimation: Uniform bounds extend MR estimation from a fixed model to every model in a sufficiently regularized class, making it feasible to train and evaluate importance on the same data.
  • Limitations of existing methods: Existing variable-importance procedures may identify relationships or variable necessity without measuring how much an individual model relies on X1.Algorithm Reliance compares models trained with and without X1, so it describes a fitting algorithm’s behavior rather than either model’s individual reliance.

4. Model Class Reliance

Model class reliance (MCR) extends single-model reliance to the range of reliance across all near-optimal models in a prespecified class. The paper derives finite-sample bounds and practical conditions for estimating this range.

  • MCR studies how much any well-performing model in a prespecified class may rely on covariates of interest.It is intended to provide a more comprehensive importance measure than reliance computed for a single model.
  • The Rashomon set consists of models whose expected loss is within ε of a prespecified reference model’s loss.The empirical Rashomon set uses the analogous in-sample loss criterion.
  • MCR bounds rely on bounded-loss assumptions for individual, relative, and aggregate losses.These assumptions are central to the paper’s finite-sample guarantees, although boundedness may hold only on a particular domain.
  • Finite-sample outer bounds contain the population MCR interval with high probability, while empirical MCR estimates approach it as sampling corrections diminish.The correction term Qout approaches zero as sample size increases, and the performance threshold εout approaches ε.
  • The bounds can widen as the model class becomes more flexible because optimizing over a larger empirical Rashomon set increases uncertainty.The bounds implicitly account for model-class complexity through the size of that set.
  • Theorem 5 uniformly bounds MR estimation error across the model class, with the bound becoming smaller as n increases and r decreases.This supports estimating a model’s reliance without sample splitting under the stated conditions.

5. Extensions of Rashomon Sets Beyond Variable Importance

The Rashomon-set framework extends beyond variable importance to finite-sample inference for arbitrary characteristics of near-optimal models. The resulting intervals have rigorous coverage and an in-sample interpretation, but their practical usefulness depends on assumptions and computational tractability.

  • Extensions beyond variable importance: The framework creates finite-sample confidence intervals for arbitrary characteristics of well-performing models, not only variable importance.Examples include coefficient norms, predictions for a covariate profile, and other model summaries.
  • Finite-sample confidence intervals: Proposition 7 obtains interval endpoints by minimizing and maximizing a descriptor over an empirical Rashomon set.The interval represents descriptor values for models whose empirical loss is not substantially above that of the reference model.
  • Finite-sample confidence intervals: These intervals combine rigorous finite-sample coverage with a coherent interpretation as the descriptor range among empirically near-optimal models.The proof uses Hoeffding’s inequality to connect population performance with random-sample performance.
  • Comparison with profile likelihood: The approach does not require asymptotics or a known parametric likelihood and can target near-optimal model sets rather than one potentially misspecified model.This distinguishes it from profile likelihood intervals under the comparison described in the paper.
  • Comparison with profile likelihood: The method’s main disadvantage is that its finite-sample intervals may be wider than profile likelihood intervals.The paper therefore uses these results primarily to motivate point estimates describing Rashomon sets.
  • Extensions beyond variable importance: The framework suggests that approximate optimization methods could support approximate finite-sample inference for complex model classes such as neural networks and random forests.The paper gives this as a possible reuse of methods developed for approximate inference.

6. Calculating Empirical Estimates of Model Class Reliance

Empirical MCR is computed by optimizing linear combinations of original and switched losses over well-performing models. Binary search and related optimization procedures produce bounds, under assumptions ensuring finite reliance and tractability.

  • Empirical MCR computation reduces to minimizing linear combinations of original and switched empirical losses across the model class.The general procedure uses objectives combining ˆeorig(f) and ˆeswitch(f), rather than directly optimizing the MR ratio.
  • MCR+ requires minimizing arbitrary linear combinations, while MCR− can often use convex combinations equivalent to reweighted empirical loss minimization.For many model classes, the lower-bound computation is no harder than minimizing loss over an expanded, reweighted sample.
  • The approach assumes positive minimum original loss and may yield highly conservative results when branch-and-bound converges slowly in high-dimensional parameter spaces.The bounds remain valid, but computational convergence can be slow as the dimension of Θ increases.
  • Lemma 9 converts a nonnegative minimized objective into a lower bound on d MR for every model in the class.If ˆh−,γ(ˆg−,γ) ≥ 0, then −γ ≤ d MR(f) for all f ∈ F.
  • Binary search selects the tuning value γ that tightens MR bounds at a chosen performance threshold ϵabs.Monotonicity results ensure that the search can reduce γ until the continuation condition no longer holds.

7. MR & MCR for Linear Models, Additive Models, and Regression Models in a Reproducing Kernel Hilbert Space

The paper develops tractable MR and MCR computations for linear, additive, regularized linear, and RKHS regression models. Linear models admit interpretable reliance formulas and linear-time empirical MR computation, while MCR reduces to quadratic optimization problems.

  • Linear and additive models: For linear models, population MR is interpretable through covariances, coefficients, and model accuracy.The result is derived under squared-error loss and extends readily to additive models because permuting X1 is equivalent to permuting its additive component.
  • Linear and additive models: The empirical MR computation cost for a linear model grows linearly in n despite a quadratic number of terms in the definition.The relevant matrix products can each be computed in linear time in n.
  • Linear and additive models: For unconstrained linear models, minimizing arbitrary combinations of original and switched losses is an unconstrained quadratic program, making empirical MCR tractable.The MCR procedure repeatedly solves objectives of this form.
  • Regularized linear models: Quadratically constrained linear models reduce MCR-bound computation to a quadratic program with one quadratic constraint.The resulting problem is related to the trust-region problem and remains computationally tractable.
  • RKHS regression models: RKHS regression models support nonlinear and nonadditive covariate features while retaining tractable MCR computation through quadratic optimization.For this class, arbitrary loss combinations are quadratic in the model coefficients, enabling computable empirical MCR bounds.

8. Connections Between MR and Causality

The paper connects model reliance to causal effects and introduces conditional model reliance to isolate information unique to X1 when X1 and X2 are dependent. Conditional methods avoid evaluating impossible covariate combinations but are harder to estimate.

  • Model reliance studies how a model’s performance changes under an intervention that perturbs the underlying data.When the model is the conditional expectation function, MR connects to quantities in causal inference.
  • Under conditional ignorability and positivity, MR of the conditional expectation function equals a causal-expression involving treatment variation, residual variability, treatment effects, and CATE heterogeneity.The decomposition identifies several terms with standard causal-inference interpretations.
  • Conditional importance: Conditional model reliance measures performance degradation after removing information uniquely available in X1 while preserving dependence with X2.It conditions the perturbation on matching or otherwise accounting for X2, unlike ordinary permutation reliance.
  • Conditional importance: When X1 and X2 are independent, CMR and MR coincide; when X2 predicts X1, CMR decreases as X2 becomes more predictive of X1.Conditional MCR generally produces a range closer to 1, representing null reliance.
  • Conditional importance: CMR avoids impossible X1–X2 combinations by restricting perturbed inputs to the original covariate domain, but estimation is more difficult.Weighting and matching can be unbiased under known probability weights, while matched pairs may be rare.

9. Simulations

The simulations use toy polynomial classifiers and misspecified model classes to compare AR, MR, and MCR and assess MCR confidence-interval coverage. MCR generally provides more robust, conservative intervals, but misspecification can still cause coverage failure and wider intervals.

  • 9.1 Illustrative Toy Example with Simulated Data: The toy example contrasts AR, MR, and MCR using degree-3 polynomial classifiers and held-out test observations.The reference model and Rashomon set are defined using cross-validated training loss, with models within approximately 10% of the reference loss considered well-performing.
  • 9.1 Illustrative Toy Example with Simulated Data: MR evaluates one classifier under altered data distributions, whereas AR compares models retrained with different covariate sets.In the example, the classifier excluding X1 has d MR = 1, while the reference model has d MR = 3.47.
  • 9.1 Illustrative Toy Example with Simulated Data: MCR restricts attention to well-performing models and bounds their empirical MR values between models that minimize and maximize reliance on X1.The toy figure includes 15 models in the empirical Rashomon set, with all their MR values lying between the two endpoint models up to approximation error.
  • 9.2.1 Results: MCR-Linear achieved proper coverage through moderate misspecification at γ = 0.3, while Standard-Linear began to break down.At γ ≥ 0.4, both methods failed to provide appropriate coverage.
  • 9.2.1 Results: MCR intervals were typically 2-4 times wider than Standard-Linear intervals because they cover a reliance range rather than a single point.The broader intervals reflect the target [MCR−(ϵ), MCR+(ϵ)].
  • 9.2.1 Results: At least 95.9% of bootstrap CIs contained population-level MCR across the studied scenarios, while coverage errors mainly reflected violations of the nearly correct model-class condition.The simulations also found that larger sample sizes can exacerbate misspecification-related coverage errors.
  • 9.2.1 Results: MCR is generic and therefore less powerful than sensitivity analyses that correctly specify how misspecification occurs.Despite this limitation, the simulations found that sufficiently strong signals can still produce informative intervals.

10. Data Analysis: Reliance of Criminal Recidivism Prediction Models on Race and Sex

The paper applies MCR to flexible models predicting COMPAS scores from Broward County records to bound reliance on race, sex, and admissible covariates. Under the stated assumptions, race and sex have null-to-modest reliance relative to admissible factors.

  • 10. Data Analysis: Reliance of Criminal Recidivism Prediction Models on Race and Sex: The analysis addresses whether proprietary COMPAS predictions rely on race, sex, or unmeasured proxies for these variables.The study uses 3,373 African-American or Caucasian defendants from Broward County with recorded COMPAS scores.
  • 10. Data Analysis: Reliance of Criminal Recidivism Prediction Models on Race and Sex: The authors use a flexible class of linear RKHS models, squared-error loss, a predefined performance threshold, and held-out observations to estimate MR and MCR.The model class and reference model are trained on 500 observations, with 2,873 observations held out for estimation.
  • 10.1 Results: The MCR range for inadmissible variables was [1.00,1.56], with a bootstrap 95% CI of [1.00, 1.73].This bounds the reliance of any well-performing model in the class under the analysis assumptions.
  • 10.1 Results: The results imply that race and sex play somewhere between a null role and a modest role in determining COMPAS scores, and are less important than admissible factors.The empirical MR values were 1.09 for inadmissible variables and 2.78 for admissible variables.
  • 10.1 Results: The MCR range for admissible variables was [1.77,3.61], with a bootstrap 95% CI of [1.62, 3.96].Admissible variables include age, number of priors, and felony indication.
  • 10.2 Discussion & Limitations: The analysis notes that variables can be both reasonable predictors and proxies for race, complicating the distinction between admissible and inadmissible inputs.Unmeasured proxies and conditional associations may also contribute to race-related prediction.

11. Conclusion

The conclusion presents MCR as a range-based importance measure for well-performing models and extends the Rashomon-set framework beyond variable importance. It also identifies computational, model-selection, and asymptotic directions for future work.

  • 11. Conclusion: MCR gives upper and lower limits on how important a variable set can be to any well-performing model in a prespecified class.The paper presents MCR as more comprehensive than single-model importance measures.
  • 11. Conclusion: The paper derives MCR bounds and connects permutation importance with U-statistics, conditional variable importance, conditional causal effects, and additive-model coefficients.These results support point estimation and inference for MCR.
  • 11. Conclusion: Future work includes exact or approximate MCR computation for additional model classes and loss functions.The current computational approach uses convex optimization when empirical-loss minimization is convex.
  • 11. Conclusion: If MCR+ is small for a variable, no well-performing predictive model can heavily depend on that variable, indicating that it can be eliminated.This suggests a variable-selection use of the Rashomon-set framework.
  • 11. Conclusion: The theoretical analysis assumes that the model class F and reference model fref are prespecified.The authors have not studied Rashomon-set behavior when the training and analysis sample sizes grow at different rates.
  • 11. Conclusion: Rashomon sets can support finite-sample inference for attributes beyond variable importance, including risk predictions for particular covariate profiles.The paper also identifies characterization of Rashomon-set size and generalization as ongoing research directions.

A.3 Relating ˆeswitch(f) to All Possible Permutations of the Sample

The appendix relates permutation-based switched loss to all sample permutations and discusses alternative difference-based reliance measures. It also develops bounds, estimator properties, and connections to best-in-class models and profile likelihood intervals.

  • A.3 Relating switched loss to all sample permutations: The switched-loss estimator is proportional to a sum over the n^2 unique combinations of outcomes and permuted covariates.Each unique combination appears exactly (n−1)! times among the n(n!) permutation terms.
  • Bounds for best-in-class reliance: MCR bounds can be translated into probabilistic bounds for the reliance of a best-in-class model, including multiple minimizers simultaneously.When the best-in-class model equals the conditional expectation, the bound applies to that function and can support a causal statement through Proposition 19.
  • Alternative MR definitions: The ratio-based MR is defined as switched expected loss divided by original expected loss to permit comparisons across outcome scales.The appendix also considers a difference-based alternative.
  • Alternative MR definitions: Difference-based MR has computational advantages because its estimator’s mean, variance, and asymptotic distribution follow directly from U-statistics.It can also be more stable when the minimum original loss is small.
  • Alternative MR definitions: The main finite-sample results and best-in-class reliance bounds continue to hold under modified difference-based definitions.The corresponding proofs require only minor changes, and some results no longer require the original-loss lower-bound assumption.
  • Profile likelihood connection: Under likelihood assumptions, optimizing a parameter across the empirical Rashomon set yields the same interval as a contiguous profile-likelihood interval.This connects MCR-style intervals to profile likelihood confidence intervals.

B.3.3 Step 3: Probabilistically Bound the Error Term from Step 2.

The proof bounds the error term using U-statistic concentration, then extends the argument to difference-based and divide-based model-reliance definitions.

  • The empirical original and switched errors are U-statistics whose expectations equal their corresponding population errors.Hoeffding’s inequality is then applied to obtain the stated bound.
  • The same proof applies to difference-based model reliance without Assumption 3 after replacing MR, empirical MR, and Qout with their difference-based counterparts.
  • The bounds also remain valid when switched-error estimates are replaced throughout by divide-error estimates.The same Hoeffding bound applies to both empirical quantities.

B.3.4 Step 4: Combine Results to Show Eq 4.2

The proof combines a high-probability bound on model reliance with a bound on the residual term to establish Eq 4.2, then notes analogous extensions and covering-number machinery.

  • Eq 4.2 follows by bounding MCR+(ϵ) through a bracketed residual term and showing that residual is at most Qout with high probability.
  • The proof of Eq 4.3 uses the same lower-bound strategy as Eq 4.2, including analogous bounds for the minimizing model.
  • Difference-based model reliance removes Assumption 3 when the corresponding Qout,difference term replaces Qout.
  • Theorem 5 uses r-margin-expectation-covering numbers to jointly bound empirical losses for every f ∈F.
  • The covering argument approximates each f by a cover element g under a uniform mixture of population and sample distributions.Hoeffding’s inequality applies because the loss is bounded within an interval of length Bind.
  • The proof for the alternative loss formulation is obtained by replacing the relative loss and its bound with the non-standardized loss and Bind.

B.5.4 Proof of Eq B.24

The proof establishes generalization bounds for switched and original empirical errors, propagates them to MCR bounds, and derives stronger statements under uniqueness or alternative Rashomon-set definitions.

  • The switched-error proof constructs distributions that preserve the relevant marginals, then applies the same covering and Hoeffding argument used for original error.
  • The resulting deviation is bounded by a cover-element deviation plus approximation errors under the population and sample distributions.
  • Difference-based model reliance yields the same Eq 4.6 and Eq 4.7 proofs without Assumption 3 after replacing Qin with Qin,difference.
  • The proof bounds model reliance for individual models in the population ϵ-Rashomon set and identifies extremizing functions for the reliance range.
  • When the best-in-class model is unique, the resulting statement is stronger than Proposition 7 and applies with ϵ = 0.
  • An absolute-loss Rashomon set is formed by replacing relative loss with non-standardized loss, while explicitly including the reference model to ensure nonemptiness.
  • Under the absolute-loss formulation, Assumption 1 and Bind replace Assumption 2 and 2Bref in the relevant definitions and results.

B.8 Proof of Proposition 15

The proposition proof derives switched-error formulas for linear predictors and conditional-outcome functions, then establishes monotonicity properties used by later optimization arguments.

  • For a linear predictor, switched error is expanded by introducing independent covariate copies and comparing the resulting expression with original error.
  • The switched-error expression equals original error plus a covariance term involving the residual after predicting from X2 and X1.
  • The proof for the conditional-expectation function uses potential-outcome notation and the assumption (Y1, Y0) ⊥ T|C.
  • Independent copies of treatment and covariate variables are used to expand the switched-error expectation before simplifying the remaining terms.
  • Most later proofs remain valid when switched-error estimates are replaced by divide-error estimates, except for Appendix C.3.
  • The auxiliary optimization function is monotone in γ: decreasing when the selected model’s original error is below ϵabs and increasing otherwise.

C.3 Proof of Proposition 11 (Nonnegative Weights for MR Lower Bound Binary Search)

The proof establishes Proposition 11 by constructing minimizers under a distribution that breaks the dependence between X1 and (X2,Y), then relating permutation loss to the resulting model-reliance quantities. It also identifies why the analogous result may fail for the divide-based estimator.

  • Constructing the auxiliary distribution: The auxiliary distribution Dm preserves the joint distribution of (Y,X2) while making X1 independent of them.Its pointwise probability factors into the sample marginal for (Y,X2) and the sample marginal for X1.
  • Constructing the lower-bound model: The proof constructs a minimizer whose loss is unaffected by permuting X1 within the sample, yielding d_MR(ĝ−,γ1) = 1.The construction makes ĝ−,γ1 constant in its X1 argument, so permuting X1 does not change its loss.
  • Comparing minimizers: For γ2 = 0, optimality of ĝ−,γ2 and nonnegative permutation error establish the comparison inequalities needed for Proposition 11.The proof compares the objective at ĝ−,γ2 with its value at ĝ−,γ1 and combines the resulting bounds through Eqs. C.8 and C.9.
  • Completing the condition check: Condition 8 reduces to ˆeorig(ĝ−,γ2) ≤ ϵabs because the switching error is nonnegative by definition.This equivalence, combined with Eq. C.10, completes the final step of the argument.
  • Limitation of the construction: Replacing ˆeswitch with ˆedivide need not preserve the result because the divide estimator's fixed pairing does not represent expectation under X1 independent of (X2,Y).Consequently, Condition 2 of Proposition 11 does not apply to that alternative construction.
Loading 1801.01489v5…