PaperlayerView exact revision on arXiv

Source-linked AI summary

Shapley values for feature selection: The good, the bad, and the axioms

Daniel Fryer, Inga Strümke, Hien Nguyen

arXiv:2102.10936v1cs.LGcs.AIstat.ML

TL;DR

Feature selection requires choosing a subset that optimizes an evaluation function while controlling complexity, but Shapley-based methods are often justified through axioms whose relevance to that goal is uncertain. The paper analyzes this issue with toy counterexamples and simulations across formulations including SHAP and SAGE, finding that axiomatic guarantees do not generally ensure feature-selection suitability and may sometimes imply the opposite.

  • Problem

    Feature selection seeks a subset of features that maximizes an evaluation function while minimizing a complexity cost, yet the relevance of Shapley values depends on the specific game formulation.

  • Method

    The paper scrutinizes Shapley axioms using abstract toy examples and simulations with multiple game formulations, including SHAP and SAGE.

  • Results

    Shapley axioms do not generally guarantee suitability for feature selection and may in some cases imply the opposite; SHAP performed poorly in three experiments, while SAGE performed favourably in two.

  • Takeaways & Limitations

    Shapley-based feature selection requires scrutiny of the game formulation and caution about treating abstract axioms as guarantees of relevance or fairness.

Abstract

from arXiv · show

The Shapley value has become popular in the Explainable AI (XAI) literature, thanks, to a large extent, to a solid theoretical foundation, including four "favourable and fair" axioms for attribution in transferable utility games. The Shapley value is provably the only solution concept satisfying these axioms. In this paper, we introduce the Shapley value and draw attention to its recent uses as a feature selection tool. We call into question this use of the Shapley value, using simple, abstract "toy" counterexamples to illustrate that the axioms may work against the goals of feature selection. From this, we develop a number of insights that are then investigated in concrete simulation settings, with a variety of Shapley value formulations, including SHapley Additive exPlanations (SHAP) and Shapley Additive Global importancE (SAGE).

I. INTRODUCTION

Feature selection seeks a compact subset of features that maximizes an evaluation function while controlling complexity. The paper examines whether Shapley-based attribution and its axioms are actually aligned with that goal.

  • Feature selection chooses a subset S of d features to maximize C(S) while minimizing a cost increasing with |S|.
  • The Shapley value has become popular for interpretable feature attribution in fitted ML models, including SHAP, Shapley Effects, and SAGE.
  • The paper argues that Shapley axioms do not generally guarantee suitability for feature selection and may sometimes imply the opposite.
  • The authors use axiomatic scrutiny, abstract toy examples, and concrete simulations to investigate Shapley-based feature selection.
  • Shapley values assign feature worth through a game formulation defined by the evaluation function and how features are removed from the model.
  • The Shapley value averages a feature’s marginal contributions across all subsets excluding that feature, using specified weights.

B. The Shapley value axioms

The Shapley value is uniquely characterized in transferable utility games by four axioms, but that uniqueness depends on the chosen characteristic function and game formulation. The axioms therefore do not by themselves establish feature-selection suitability.

  • Efficiency, null player, symmetry, and additivity are presented as four axioms that uniquely define the Shapley value in a TU game.
  • Efficiency: Efficiency distributes the full model’s worth among features without loss.
  • Null player: The null-player axiom assigns zero value to a feature that contributes nothing to every submodel it enters.
  • Symmetry and additivity: Symmetry gives equal Shapley values to features that play equal roles, while additivity preserves addition of evaluation functions.
  • Alternative axiomatisation: Balanced contributions is described as an alternative single axiom replacing axioms 2–4 and requiring cooperating feature pairs to share gains or losses equally.
  • Shapley values vary greatly across characteristic functions and game formulations, and exact computation is often replaced by approximation because the formula is exponential in feature count.

C. Feature selection in general

Feature selection evaluates subsets against goals such as compact description, predictive performance, or statistical significance, which can trade off against one another. Methods differ in how they search or score candidate submodels.

  • Feature-selection objectives include describing a data-generating process, improving prediction, and maximizing model or parameter significance or power.
  • Wrapper methods: Wrapper methods evaluate trained submodels chosen by sequential elimination or heuristic search and are specific to the modeling task.
  • Filter methods: Filter methods avoid model training and rank features using intrinsic data properties such as covariance or mutual information.
  • An evaluation function is monotonic when adding features never decreases its value.
  • AIC and BIC are popular non-monotonic evaluation functions used with stepwise procedures.

D. Shapley values for feature selection

The simplest Shapley-based selection procedure chooses an objective, computes feature values, and retains the highest-ranking features or those above a threshold. Several alternatives modify coalition search or selection strategy.

  • Attribution selection chooses an objective function, computes Shapley values for all features, and selects the k highest-ranking features.
  • The final selection step can instead retain features whose Shapley values exceed a chosen threshold.
  • Published variants include restricted coalition sizes with stepwise selection, genetic algorithms, and model averaging based on interaction components.

III. THE MEANING OF THE AXIOMS

The section uses toy games to show that Shapley values average contributions across submodels, which can conflict with selecting an optimal, possibly smaller model. Efficiency likewise allocates the full-model evaluation even when a different submodel is optimal.

  • A. The meaning of model averaging: Shapley values average marginal contributions across submodels, so average feature performance may not reflect performance in optimal submodels.The section contrasts broad averaging with selecting features based specifically on contributions to optimal submodels.
  • A. The meaning of model averaging: In the taxicab game, the optimal equal-cost model contains player 3 alone, while players 1 and 2 are useless for model selection despite contributing to some coalitions.Their contributions arise in non-optimal coalitions, including the empty set for player 1.
  • A. The meaning of model averaging: Dominant-feature interactions can make superfluous features appear valuable because Shapley averaging includes their improved performance within submodels containing the dominant feature.The paper suggests fixing dominating features first as a possible response, but then feature selection may no longer be needed.
  • B. The meaning of efficiency: Efficiency distributes the full-model evaluation C(F) losslessly, rather than the value of the selected model, narrowing the compatible model-averaging procedures.This distinction is especially important for non-monotonic evaluation functions.
  • B. The meaning of efficiency: For non-monotonic evaluation functions, Shapley values sum to the full-model payoff rather than the maximum payoff over all feature subsets.Although exact Shapley computation evaluates all submodels and thereby exposes the optimum, estimating the optimum first can make subsequent feature selection unnecessary.

C. The meaning of balanced contributions

Balanced contributions and related Shapley axioms can distribute credit in ways that conflict with feature selection. The secret-holder example shows that features receiving lower attributions may be essential to an optimal submodel.

  • C. The meaning of balanced contributions: Balanced contributions can replace the null-player, symmetry, and additivity axioms, but symmetry may be undesirable for strongly correlated features.With correlated features, symmetry gives approximately equal attributions even when selecting one feature would suffice.
  • C. The meaning of balanced contributions: Balanced contributions share a coalition’s residual earnings equally among its players, while Shapley weighting emphasizes contributions to especially small or large coalitions.The weighting of coalition sizes follows the binomial coefficients in the Shapley formulation.
  • C. The meaning of balanced contributions: Poor singleton-model performance can receive substantial weight even when singleton models are unattractive for model selection.This follows because contributions to extreme coalition sizes receive higher weights than contributions near d/2.
  • C. The meaning of balanced contributions: In the secret-holder game, players 2 and 3 receive twice player 1’s attribution, although selecting {2, 3} gives suboptimal performance.The payoff comparisons include C({1, 2}) = 10, C({2, 3}) = 7, and C({1, 3}) = 10.
  • C. The meaning of balanced contributions: Because the full model contains the secret-holding player, discarding player 2 or 3 would be preferable to selecting {2, 3}.The paper uses this example to caution against equating high Shapley values with strongest contributors to model performance.

IV. EXPERIMENTATION

The simulations test Shapley-based feature selection under known data-generating processes and multiple formulations. They show that SHAP FSelection and R2 can rank an irrelevant feature above Markov boundary members, whereas SAGE succeeds in the first experiment.

  • IV. EXPERIMENTATION: The experiments simulate known data-generating processes using multiple evaluation functions and formulations, including SHAP FSelection and SAGE.SHAP FSelection ranks features by mean absolute SHAP values of model predictions, while SAGE is also evaluated.
  • A. Markov boundary experiment 1: The first experiment predicts Y from X1, X2, X3, and Z, where X1, X2, and X3 are Markov boundary members and Z is conditionally redundant given them.The DGP includes irreducible uncertainty terms ε and γ, each distributed as N(0, 4).
  • A. Markov boundary experiment 1: The three Markov boundary features receive smaller Shapley values than non-Markov boundary feature Z under the R2 formulation.Thus the R2 ranking prefers Z over each of X1, X2, and X3.
  • A. Markov boundary experiment 1: With n = 10^6 and XGBoost regression, SHAP FSelection ranks (Z, X1, X2, X3) with mean absolute SHAP values (1.4, 1.1, 1.1, 1.1).A top-3 procedure therefore includes Z instead of one Markov boundary member.
  • A. Markov boundary experiment 1: SAGE assigns scores (1, 4, 4, 4) to (Z, X1, X2, X3), successfully highlighting the appropriate features in this scenario.The paper contrasts this with the poor model-selection results from SHAP FSelection and R2.

B. Markov boundary experiment 2

This experiment varies ℓ in a discrete-data-generating process to examine how SHAP, SAGE, and m formulations rank features for selection. SAGE performs well across the investigated parameter range, whereas SHAP and m perform poorly.

  • B. Markov boundary experiment 2: The evaluation function m assigns the value max {P(Y = 1|X_S = x_S), P(Y = 0|X_S = x_S)} to each feature coalition.X_S denotes the vector of features indexed by S.
  • B. Markov boundary experiment 2: At ℓ = 0.05, SHAP FSelection ranks X1, X2, X3, while SAGE ranks X2, X3, X1.The corresponding mean absolute SHAP values are (1.43, 0.50, 0.40), and SAGE values are (0.0797, 0.0787, 0.0003).
  • B. Markov boundary experiment 2: The experiment generalizes a data-generating process by varying ℓ across 0.05 to 0.95 and computes SHAP FSelection and SAGE values.Twenty datasets were simulated on an equally spaced grid of ℓ values.
  • B. Markov boundary experiment 2: SAGE performs admirably across the investigated parameter space, while the SHAP and m formulations perform poorly.The comparison is based on differences in attribution between X1 and X2, with similar behavior for X1 and X3.

C. A secret holder experiment

The secret-holder experiment evaluates Shapley-based feature selection over a two-parameter grid. It finds regions where X2 and X3 are preferred even though X1 is part of both optimal size-two submodels.

  • C. A secret holder experiment: The study simulates 6,561 datasets over an 81 × 81 grid of (t1, t2), with each parameter ranging from −2 to 2 in 0.05 increments.Shapley values are computed using a conditional log likelihood evaluation function.
  • C. A secret holder experiment: Pathologies occur approximately where t2 = ±(|t1| + α) for 0 < α < 0.4.The pathological region is identified from the parameter-grid results.
  • C. A secret holder experiment: At t1 = 2 and t2 = 2.2, X2 and X3 are favoured in feature selection despite X1 being the “secret holder” and belonging to both optimal size-two submodels.The result is described as occurring although X1 is the member shared by both optimal submodels.
  • C. A secret holder experiment: At this setting, mean absolute SHAP values are (0.97, 1.52, 1.48), while SAGE values are (4.6, 5.8, 5.9).SHAP and SAGE disagree on whether X2 or X3 is most important, but neither gives precedence to X1.

D. A taxicab experiment

The taxicab experiment constructs data from a maximum-of-features response and evaluates a correct predictive model using a mean-squared-error difference. The setting reproduces the paper’s first toy example.

  • D. A taxicab experiment: The response is generated as Y = max{X1, X2, . . . , Xd} + ε, with ε ∼ N(0, 1).The experiment uses a maximum-based generative model with Gaussian noise.
  • D. A taxicab experiment: The predictive model is the correct model, ˆY = max{X1, X2, . . . , Xd}.The model is evaluated using a difference between mean squared errors.
  • D. A taxicab experiment: The concrete setting uses d = 3 with (a1, a2, a3) = (5, 10, 20).The characteristic function is evaluated under these parameter choices.
  • D. A taxicab experiment: The resulting Shapley values reproduce the scenario in Example 1.The authors state that the concrete construction generates the earlier toy scenario.

V. DISCUSSION

The discussion argues that Shapley-value suitability for feature selection depends on the game formulation rather than following automatically from the axioms. The authors call for more empirical study of appropriate formulations and axioms.

  • V. DISCUSSION: Across three experiments, SHAP FSelect performed poorly in all cases, while SAGE performed favourably in two.The experiments used reasonable evaluation functions and game formulations on potentially pathological data-generating processes.
  • V. DISCUSSION: The axioms do not generally guarantee that the Shapley value suits feature selection and may sometimes imply the opposite.This is the paper’s stated confirmation from the experiments.
  • V. DISCUSSION: The relevance of the Shapley value to feature selection is governed by the specific game formulation, and its justification from the axioms is non-trivial.The discussion emphasizes nuance in applying Shapley values to machine-learning tasks.
  • V. DISCUSSION: Future work should thoroughly explore game-theoretic solution concepts, formulations, and axioms across practical feature-selection and attribution tasks.The authors specifically call for extensive empirical studies.
Loading 2102.10936v1…