Additive Feature Attribution Methods

This post explores the "Additive Feature Attribution Methods" class of extrinsic explainability methods (where the reference model's internals aren't analysed).

What are AFAMs?

Additive Feature Attribution Methods (AFAMs) approximate a prediction of the original model ($f$) with an explanation model ($g$) which is a linear addition of binary features (making it simpler and interpretable).

Mathematically:

$$f(x)\approx g(z^{\prime })={\varphi }_0+\sum _{i=1}^M{\varphi }_i{z}_i^{\prime }$$

Each ${\varphi }_i\in R$ is an effects of a binary feature $z_i^{\prime }\in \{0,1{\}}^M$ in the output. The different methods in the class estimate ${\varphi }_i$ differently.

Note

Explanation Model

[In their words][shap_values] : "We introduce the perspective of viewing any explanation of a model’s prediction as a model itself, which we term the explanation model." and also "Instead, we must use a simpler explanation model, which we define as any interpretable approximation of the original model.".

Finally, just for completeness:

Note

The AFAM class was identified in the paper A Unified Approach To Interpreting Model Predictions.

SHAP

Linear LIME, DeepLIFT and other methods calculate ${\varphi }_i$s differently, in turn yielding different coefficients.

The Unified Approach to Interpret Model Predictions proposes that models should have local accuracy, missingness, consistency which, they argue, lead to coefficients that are more intuitive for humans.

The terms are defined as:

• Local Accuracy: There must be equality when the input is the original one ($x$), that is $f(x)=g(x^{\prime })$.
• Missingness: If the reference vector ($x^{\prime }$) has a "missing" component ($x_i^{\prime }=0$) then the feature must have no impact, that is ${\varphi }_i=0$.
• Consistency: if one of two models is larger just turning feature $i$ on and off, then it must have a larger ${\varphi }_i$.

Their Theorem (Theorem 1) guarantees ahat a linear explanation model plus the 3 requirements leave Shapley Values (a result from game-theory found by Shapley) as the best (and unique) coefficients. Other methods violate some of these 3 properties (so the authors modify them to comply).

SHAP (SHapley Additive Explanations) Values are the Shapley Values of a conditional expectation function of the original model: $f(h_x(z^{\prime }))=\mathbb{E}[f(z)|z_S]$ (Section 4, see Figure 1). $S$ are non-zero indices.

• For example, with $\vec{z}=⟨v_1,0,v_2⟩$ then ${\varphi }_3=\mathbb{E}[f(z)|z_{1,3}]$. So the Shapley values are the change in the expected model prediction when conditioning on a feature.

Note

The most accurate Shapley Values are expensive to calculate. Approximations can be used in some cases to speed this up.

Approximating SHAP Values

The approximations can be model agnostic: Shapley Sampling Values, Quantitative Input Influence, Kernel SHAP; or they can be model-specific: Max SHAP, Deep SHAP.

The actual approximations are:

Approximation 1: Feature independence (implies non-multicollinearity).

• Shapley sampling values method,
• Quantitative Input Influence,
• Kernel SHAP (requires both assumptions).

Approximation 2, model linearity: Shapley regression values.

• SHAP provides both global (average across inputs) and local (for a given input).

Kernel SHAP

Can we modify Linear LIME's Loss function so that the values of coefficients found are Shapley values? Yes! These are also more intuitive to humans, and remove some of the heuristics (kernel selection and complexity metric) of it.

The Linear LIME quantities of proximity kernel (${\pi }_x$), complexity penalty ($\Omega (g)$) and Loss ($L$) are turned into a shapley kernel, $\Omega (g)=0$, and the same weighted loss.

The SHAP values / coefficients for this linear model with assumed-uncorrelated features can be estimated by weighted linear regression.

This method is called Kernel SHAP, and it's fast to compute.

LIME and SP-LIME

The paper "Why Should I Trust You?": Explaining the Predictions of Any Classifier proposes the Local Interpretable Model-Agnostic eXplanation (LIME) and the Submodule Picking LIME.

LIME isn't a particular model but rather a set of characteristics that explainable methods should have, according to the authors (more on this later).

Let's first look at LIME as implemented in a concrete case.

Why would this be useful? A concrete example

A linear model with few-ish, interpretable features, locally fit to a complex one is in line with LIMEs' requirements.

Local fit means fitting only in the vicinity of the input of interest. The input features may differ from those in the original model.

The original paper shows an example comparing two different models that were fit by linear ones:

Image taken from paper.

The image makes clear some of the uses of it:

• The interpretable features, alongside their contributions (weights) to the prediction, can help decide whether to trust the prediction or not.
• Feature engineering such as removing features (or certain data) that the model uses but harm generalisation,
• Comparing models is easy (through the linear proxies). It's especially useful if the original models' accuracy (and other metrics) are similar, and their features non-interpretable.
• Here, one of them is untrustworhy (right hand side), giving high weight to meaningless features.

LIME / Desiderata

The authors consider 4 properties to be desirable in an explanation model:

• Local: the interpretable or explanation model approximates the original model in the vicinity of a particular prediction. In contrast, global explanations explain the full model.
• Model-agnostic: any model can in principle be explained by this method.
• Interpretable Explanation: In this paper, "interpretable" is a desired characteristic of "explanation", and provides qualititative understanding (a simple answer to "Why was this prediction made?"). In their own words:

  An essential criterion for explanations is that they must be interpretable, i.e., provide qualitative understanding between the input variables and the response. We note that interpretability must take into account the user's limitations.

Additionally, they include 4. A global perspective, a mechanism to get a sense of the full model's behaviour.

The first 3 can be called LIME; the Submodule Picking LIME (SP-LIME), which selects LIME explanations to give a global explanation of the model.

LIME is a slightly more explicit version of the first 3 desired properties. Let's explore this.

• Which specific representations does the LIME framework consider interpretable?

  An example of an interpretable representation is a binary vector with components indicating presence / absence of a feature (e.g. a word) in the explanation model.

• Which models does the LIME paper consider interpretable?

  (...) interpretable models, such as linear models, decision trees, or falling rule lists [27], i.e. a model $g\in G$ can be readily presented to the user with visual or textual artifacts.

• Complexity is the opposite of interpretable, so the loss (we skip it here) to train the explainable model accounts for it, and gives local samples more importance than remote ones. Here $G$ being the model class of $g$:

  As not every $g\in G$ may be simple enough to be interpretable thus we let $\Omega (g)$ be a measure of complexity (as opposed to interpretability) of the explanation $g\in G$.

  The definition of complexity depends on $G$. For linear models it may be the number of weights.

• They also define a sampling procedure to create the training set. This is detailed in the concrete algorithm in the next section.

Linear LIME: An Algorithm

The paper implements LIME using the class $G$ of sparse linear models as explanation model, which we could call Linear LIME (as A Unified Approach to Interpreting Model Predictions does). Here is my interpretation of the algorithm (the primed variables denote binary vectors):

1. A model $f$ and an input vector $x\in R^n$ needs explaining,
2. Start an interpretable, binary vector $x^{\prime }\in \{0,1{\}}^{n^{\prime }}$ with only the dimensions of interest of $x$ (it may be all-ones often),
3. Generate perturbed binary variants of $x^{\prime }$ called $z_i^{\prime }$,
4. Use different $z^{\prime }$ to make variants of $x$ called $z\in R^n$.
   • Written in A Unified Approach to Interpreting Model Predictions paper as $z=h_x(z^{\prime })$.
5. Now we have training tuples $(f(z),z^{\prime },{\pi }_x(z))$.
6. Use the dataset to fit the linear model $g$ using $K-LASSO$.
   • To select $K$ interpretable features they apply $K$-LASSO.
   • LASSO is like a sparse linear regression, some coefficients are pushed to $0$ and correspond to variables we can ignore. How many are are pushed to $0$ may be controlled by the complexity penalty in the loss function.
   • This is why the number of input features for the interpretable model ($x^{\prime }$, $z^{\prime }$) may be much smaller than that of $x$, $z$.
   • Then the non-zero variables are used to fit $g$ to $f$ but now using least-squares.

SP-LIME is defined as:

[SP-LIME] a global understanding of the model by explaining a set of individual instances.

The complex part of SP-LIME is selecting instances that add the maximum insight, and avoiding repeated ones. The algorithm is briefly described later on.

SP-LIME: The Algorithm

The goal here is picking the most informative instances, and without repetition.

A coverage metric is defined: $c(V,W,I)={\sum }_j{1}_{[}\exists i\in V:W_{ij}>0]I_j$.

Here, $W$ is a matrix of weights (columns) for each instance (row).

$I$ is the global importance of a component, defined as $I_j=\sqrt{{\sum }_i{W}_{ij}}$. The larger the sum of weights is, the more important.

A marginal coverage for each candidate instance ($i$) $c_i-c$ is performed, then the instance that increases $c$ of $V$ the most is appended to it.

Note

This approximates the $V$ with the largest coverage, but it's not exact because the total max could be one that does not max it on each step!

To increase the coverage at all, it must add some non-zero value to a column of zeros.

LIME: Final Comments

Explanation models do not replace but complement accuracy or other evaluation metrics.

Robustness Fixes

• Normalised Moving Rate (NMR): tests the stability of the list against the collinearity. Smaller NMR means more stable ordering.
• Modified Index Position, in the paper's words:

  [MIP] works similarly to NMR by iteratively removing the top feature and retraining and testing the model. Thereafter, it examines how the features are reordered in the model which implies the effect of collinearity.

These two methods (MIP, NMR) can be useful both in having a reliable sorting of features, and on selecting one —most stable— of several methods.

Definition of a few concepts

Let's now look at other methods.