Machine Learning 2. Lecture 12. Interpretability and…

What this lecture is about

A good model is not necessarily an understandable one: an accurate ensemble of trees or a deep neural network gives an answer but does not say why it is what it is. Yet an explanation of a decision is often needed no less than the decision itself: an expert needs it to trust the model, the person about whom the decision was made needs it to understand its reasons, a regulator needs it to check the model's compliance with norms. The lecture has three parts. The first introduces the notions of interpretability and explainability, lists models that are interpretable by their design, and visual methods of interpretation. The second covers methods that explain a model through its features: permutation feature importance, the Shapley value from cooperative game theory and the methods built on it, and the local surrogate models LIME, Anchors and SHAP. In the third, the same idea of the Shapley value is carried over from features to training objects, and counterfactual explanations are considered — the answer to the question "what needs to change in the object for the model's decision to be different".

Interpretability and explainability

Goals, tasks, basic notions

Definition (Explainability (XAI, eXplainable Artificial Intelligence)).

Interpretability: passive interpretability of the model's design or of its prediction on an object.
Explainability: active generation of explanations as additional output for an object.
Comprehensibility: the possibility of presenting the learned regularities as knowledge understandable to people.
Understandability, Transparency: transparency of the whole process of building the model, of its parts and of intermediate results.

"Do you want an interpretable model, or the one that works?" [Yann LeCun, NIPS'17]

V. Belle, I. Papantonis. Principles and practice of explainable machine learning. 2020.

The words "interpretability" and "explainability" are often used as synonyms, but the distinction between them is useful. Interpretability is a property of the model itself: its design or its answer on an object can be understood simply by looking at it. Explainability is an active action: for an object, along with the answer, an explanation is also generated, which is itself output of the model or of a special method. Broader still are the notions of the comprehensibility of the learned regularities and the transparency of the whole process of building the model. Yann LeCun's question, put on the slide, states a common objection: interpretability is often bought at the cost of accuracy, and then one has to choose between an understandable model and a model that works. A good part of the methods in this lecture make it unnecessary to choose: the model remains as complex as you like, and the explanations are built on top of it.

Definition (Explainability: who needs explanations, why, and which?).

Who: domain experts. Why: trust in models, extracting knowledge from data.
Who: end users. Why: understanding the reasons for the decisions made.
Who: regulators. Why: auditing the compliance of models with standards and norms.
Who: researchers, developers. Why: understanding the properties of models, products and services.
Who: beneficiaries, managers. Why: understanding the effect of models on business processes.

A. B. Arrieta et al. Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI. 2019.

Different addressees need different explanations. An expert needs to make sure that the model relies on meaningful regularities and, perhaps, to extract new knowledge about the subject area from it. An end user — for example, a customer who was refused a loan — needs to understand the reasons for the particular decision about them. A regulator needs to check that the model does not violate standards and norms. Explanations help a developer find errors in the data and in the model, and a manager understand how the model affects business processes.

Interpretable models

Some models are interpretable by their design.

Definition (Interpretable machine learning models).

Linear models $y = w_{1} x_{1} + w_{2} x_{2} + w_{0}$ : a weight shows how much $y$ changes when $x_{j} + 1$ .
Generalised linear models and logistic regression $g (E (y)) = w_{1} f_{1} (x_{1}) + w_{2} f_{2} (x_{2})$ : explanation of the change in the probability $p (y)$ .
A decision tree: the path from the root explains why the decision was made.
Rule induction: an explanation of the decision in natural language.
Metric classifiers: the nearest neighbours explain why the decision was made.
Bayesian networks and the naive Bayes classifier: an explanation of the dependencies between variables.

A. B. Arrieta et al. Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI. 2019.

All these models have appeared in the course. In a linear model the weight of a feature is the change in the answer when the feature increases by one. In a decision tree and in a logical rule, the explanation is the chain of conditions itself that led to the answer; it can be read in natural language: "if the feature $x_{1}$ is large, then the class is such-and-such". A metric classifier explains an answer by precedents: the object is assigned to a class because these objects of the training sample are similar to it. A Bayesian network shows explicitly which variables depend on which.

Feature importance in linear regression

Let us start with the simplest interpretable model, multivariate linear regression, and see how reliable its "obvious" explanation by weights really is.

Definition (Reminder. Multivariate linear regression). The linear regression model on $n$ features $f_{1} (x), \dots, f_{n} (x)$ :

f (x, α) = j = 1 \sum n α_{j} f_{j} (x), α \in R^{n} .

The least squares method, training on a sample $(x_{i}, y_{i})_{i = 1}^{ℓ}$ :

Q (α) = i = 1 \sum ℓ (f (x_{i}, α) - y_{i})^{2} = ∥ F α - y ∥^{2} \to α min;

$α^{*} = (F^{T} F)^{- 1} F^{T} y$ is the solution of the least squares problem, $F = (f_{j} (x_{i}))_{ℓ \times n}$ .

The coefficient of determination $R^{2} \in [0, 1]$ , the higher the better:

R^{2} = 1 - \frac{min _{α} ∥ F α - y ∥ ^{2}}{min _{c} ∥ c - y ∥ ^{2}} = 1 - \frac{∥ F α ^{*} - y ∥ ^{2}}{∥ y ˉ - y ∥ ^{2}} = \frac{y ^{T} F α ^{*} - ℓ y ˉ ^{2}}{y ^{T} y - ℓ y ˉ ^{2}} = y^{T} F α^{*} = j = 1 \sum n α_{j}^{*} (f_{j}^{T} y) for y^{T} y = 1, y ˉ = 0.

The coefficient of determination compares the model's residual sum of squares with the sum of squared deviations from the mean, that is, with the error of the simplest model, a constant. If there is a constant among the features, the vector $F α^{*}$ is the projection of $y$ onto the linear span of the features, and $∥ F α^{*} - y ∥^{2} = y^{T} y - y^{T} F α^{*}$ ; hence the third equality. If, moreover, the target vector is centred and normalised, $R^{2}$ decomposes into a sum of terms over the features. This decomposition will be needed later.

Definition (Feature importance estimates in linear regression).

The coefficient $α_{j}^{*}$ equals the change in $f$ when $f_{j}$ increases by 1:
- it ignores the scale, shift, variance and correlations of the features, and multicollinearity (a source of overfitting).
The $t$ -statistic of the importance of a feature (feature importance) takes into account the variance of the estimate $α_{j}^{*}$ :

$T_{j} = \frac{α _{j}^{*}}{σ ^ ( F ^{T} F ) _{j j}^{- 1}} \sim t_{ℓ - n}, σ^^{2} = \frac{Q ( α ^{*} )}{ℓ - n};$
- it makes it possible to test the hypothesis $α_{j}^{*} = 0$ ;
- to compute the p-value for this hypothesis;
- and confidence intervals for $α_{j}^{*}$ .
The net effect $NEF_{j}$ of a feature in the decomposition of $R^{2}$ :

$R^{2} = y^{T} F α^{*} = j = 1 \sum n α_{j}^{*} (f_{j}^{T} y) = j = 1 \sum n NEF_{j} (for y^{T} y = 1, y ˉ = 0) .$

The weight $α_{j}^{*}$ is a poor measure of a feature's importance for many reasons. It depends on the scale of the feature: if distance is measured in kilometres rather than metres, the weight grows a thousandfold, although the feature has not become more important. It says nothing about how reliably it is estimated: under multicollinearity the weights can be huge in absolute value and at the same time unstable, and that, as we know, is a source of overfitting.

The $t$ -statistic corrects some of these shortcomings: it divides the weight by the standard error of its estimate. If the noise is normal, then under the hypothesis $α_{j} = 0$ it has Student's distribution with $ℓ - n$ degrees of freedom. This makes it possible to test the hypothesis that a feature is insignificant, to compute a p-value for it, and to build confidence intervals for the coefficient.

TikZ diagram — The densities of Student's distribution $t_{ν}$ with $ν$ degrees of freedom. As $ν$ grows the tails become lighter, and as $ν \to \infty$ the distribution turns into the standard normal (dashed line).

The net effect of a feature is its term in the decomposition of $R^{2}$ : the product of the weight and the correlation of the feature with the target variable. The sum of the net effects equals the share of explained variance. With correlated features, however, net effects too are unstable and can even be negative; we will return to this question when we talk about the Shapley value.

Example (The bike rental forecasting problem). $x_{i}$ is a date, $y_{i}$ is the number of bikes rented; $Weight = α_{j}^{*}$ ; the standard error $SE = σ^(F^{T} F)_{j j}^{- 1}$ ; $t = ∣ T_{j} ∣$ ; Intercept is the free term, the coefficient of the feature $f_{1} = 1$ .

Feature	Weight	SE	$t$
(Intercept)	2399.4	238.3	10.1
season SUMMER	899.3	122.3	7.4
season FALL	138.2	161.7	0.9
season WINTER	425.6	110.8	3.8
holiday	−686.1	203.3	3.4
workingday	124.9	73.3	1.7
weathersit MISTY	−379.4	87.6	4.3
weathersit RAIN/SNOW/STORM	−1901.5	223.6	8.5
temp	110.7	7.0	15.7
hum	−17.4	3.2	5.5
windspeed	−42.5	6.9	6.2
days_since_2011	4.9	0.2	28.5

UCI ML Repository: Bike Sharing Dataset. Christoph Molnar. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. 2019.

The example shows that weights and $t$ -statistics say different things. The largest weight in absolute value belongs to bad weather (rain, snow and storms reduce rentals by almost two thousand bikes a day), but the largest $t$ -statistic belongs to the feature "number of days since the beginning of 2011", whose weight is only 4.9: this feature reflects the growing popularity of the rental service and is estimated very reliably. The temperature weight of 110.7 means that each degree adds about a hundred and ten rented bikes. The season "fall" is statistically insignificant: $t = 0.9$ , and the confidence interval for its weight covers zero.

Weights and $t$ -statistics describe the model as a whole. Often something else is needed: to explain why a particular forecast came out on a particular object.

Definition (Feature importance estimates for a fixed object).

The importance of a feature (contribution, effect) $eff_{j} (x) = α_{j} f_{j} (x)$ :
- takes scale into account, but not shift or correlations.
Situational importance $α_{j} (f_{j} (x) - f ˉ_{j})$ :
- takes scale and shift into account, but not correlations.

Boxplots show the distributions ${eff_{j} (x_{i})}_{i = 1}^{ℓ}$ , and separate marks show the effects on a particular chosen object $x_{i}$ . Such a plot explains which features produced a low forecast on the given object.

Christoph Molnar. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. 2019.

The forecast of a linear model is a sum of the contributions of the features, so the contribution $α_{j} f_{j} (x)$ is naturally taken as a measure of how much the feature influenced the answer. But the contribution is measured from zero, and zero is often nothing special for a feature: zero temperature is not the "absence" of temperature. Situational importance measures the contribution from the feature's mean over the sample and answers the question of how much this object differs from a "typical" one because of the given feature. Neither estimate takes correlations between features into account.

Visual methods: partial dependence plots

For a nonlinear model the contribution of a feature is no longer expressed by a single number. But one can draw how the model's answer depends on the feature.

Definition (Partial Dependence Plot (PDP)). How does the model $f (x)$ depend on a part of the features $S \subseteq {f_{1}, \dots, f_{n}}$ ? Let $x = (x_{S}, x ~)$ , where $x_{S}$ are the features from $S$ and $x ~$ the remaining features.

g (x_{S}) = E_{x ~} f (x_{S}, x ~) = \int f (x_{S}, x ~) d P (x ~) or \int f (x_{S}, x ~) d P (x ~ ∣ x_{S}) .

Estimating the integral by the Monte Carlo method:

g^(x_{S}) = \frac{1}{ℓ} i = 1 \sum ℓ f (x_{S}, x ~_{i}) or g^(x_{S}) = \frac{\sum _{i} K ( x _{S} , x _{S i} ) f ( x _{S} , x ~ _{i} )}{\sum _{i} K ( x _{S} , x _{S i} )} .

Christoph Molnar. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. 2019.

To see how the model depends on the features $S$ , the values of the remaining features are averaged out. In the first variant, the values $x_{S}$ are substituted into all the objects of the sample, and the other features are taken as they are; this estimates the integral over the marginal distribution of $x ~$ . The drawback is that with correlated features such substitution produces unrealistic objects — a hot day in January, for example. The second variant averages over the conditional distribution: the objects of the sample are weighted by a kernel according to how close their values $x_{S i}$ are to $x_{S}$ , so that only plausible combinations enter the average. Typical plots for the bike problem: rentals grow with temperature and level off in hot weather, and fall with high humidity and strong wind.

Definition (Individual Conditional Expectation plots (ICE)). Individual Conditional Expectation is a PDP for individual objects: $f (x) = f (x_{S}, x ~)$ , where $x_{S}$ are the features from $S$ and $x ~$ the remaining features.

The plot of the dependence $g_{i} (x_{S}) = f (x_{S}, x ~_{i})$ for each $x_{i} = (x_{S i}, x ~_{i})$ shows how the model's prediction on the object would change if the value of the chosen feature $x_{S}$ , $∣ S ∣ = 1$ , were changed.

Christoph Molnar. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. 2019.

A PDP is the mean of the ICE curves. Averaging can hide the fact that a feature acts differently on different objects: if on half the objects the forecast grows with the feature and on the other half it falls, the PDP will be almost horizontal, and the feature will seem unimportant. A set of ICE curves shows such heterogeneity at once.

Interpretation in the feature space

Permutation feature importance

The next method works for any model and estimates the importance of a feature by how much the quality of the model deteriorates if that feature is "spoiled".

Definition (Permutational feature importance (PFI)).

PFI_{j} = Q^{j} / Q or Q^{j} - Q,

the losses on the original sample and after shuffling:

Q = i \sum L (f (x_{i}), y_{i}), Q^{j} = i \sum L (f (x ~_{i}^{j}), y_{i}),

where $f (x)$ is the trained model, $L (f, y)$ the loss function, and $x ~_{i}^{j}$ the object $x_{i}$ with the substitution $f_{j} (x_{i}) \to f_{j} (x_{rand})$ .

Advantages: any model; training once; correlations are taken into account.

Drawback: shuffling can produce unrealistic objects.

Christoph Molnar. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. 2019.

The values of the $j$ -th feature are randomly shuffled between objects, so that the link between the feature and the answer is destroyed while its distribution stays the same. The model is not retrained: it was trained once, and on the spoiled sample only its losses are computed. If the feature matters to the model, the losses will grow noticeably; if not, they will hardly change. Since the other features are kept, the interactions of the $j$ -th feature with them also enter the estimate. The drawback is the same as with PDP: with correlated features, shuffling creates combinations of values that do not occur in the data, and the model is evaluated where it was not trained.

The Shapley value

A deeper idea came from cooperative game theory. The contribution of a feature to the quality of a model depends on which other features are in it: two strongly correlated features are each important separately, but together each adds almost nothing to the other. So a feature has to be assessed over all possible "coalitions" of features.

Definition (The Shapley value (from cooperative game theory)). The features $F = {f_{1}, \dots, f_{n}}$ play a cooperative game:

$V (S)$ is the joint payoff of a coalition $S \subseteq F$ , $V (\emptyset) = 0$ ;
the players join $S$ one by one, in an order given by a permutation $π$ ;
$Δ (j, S) = V (S \cup j) - V (S)$ is the utility of the player $f_{j}$ in the coalition $S$ ;
$S_{π j} \subset F$ is the set of players that come before $f_{j}$ in the permutation $π$ .

The Shapley value $ϕ$ is a fair division of the total payoff:

ϕ_{j} = \frac{1}{n !} π \sum Δ (j, S_{π j}) = S \subseteq F ∖ f_{j} \sum \frac{∣ S ∣ ! ( n - ∣ S ∣ - 1 )!}{n !} Δ (j, S),

where $∣ S ∣!$ is the number of ways to form the coalition $S$ ; $(n - ∣ S ∣ - 1)!$ is the number of ways to continue forming the coalition after $f_{j}$ joins $S$ ; $n!$ is the number of permutations $π$ of the set of $n$ players.

Lloyd Stowell Shapley. A value for n-person games. 1952.

The meaning of the formula is this. The players enter the coalition one at a time in random order, and each is credited with what they added to the payoff at the moment of their arrival. The Shapley value is the player's mean addition over all $n!$ orders. In the second form the sum runs over the coalitions $S$ that do not contain $f_{j}$ : the coalition $S$ comes before $f_{j}$ in exactly $∣ S ∣! (n - ∣ S ∣ - 1)!$ permutations.

Theorem (Shapley). The Shapley value is the only division that satisfies the axioms:

efficiency: $\sum_{j = 1}^{n} ϕ_{j} = V (F)$ ;
symmetry (anonymity of the players): $\forall j, k : (\forall S Δ (j, S) = Δ (k, S)) \Rightarrow ϕ_{j} = ϕ_{k}$ ;
no free ride for a "dummy": $\forall j : (\forall S Δ (j, S) = 0) \Rightarrow ϕ_{j} = 0$ ;
consistency ( $Δ_{1}$ , $Δ_{2}$ are two utility functions): $\forall j : (\forall S Δ_{1} (j, S) ⩽ Δ_{2} (j, S)) \Rightarrow ϕ_{1 j} ⩽ ϕ_{2 j}$ ;
additivity (over sources of payoff): $\forall S V (S) = α_{1} V_{1} (S) + α_{2} V_{2} (S) \Rightarrow \forall j ϕ_{j} = α_{1} ϕ_{1 j} + α_{2} ϕ_{2 j}$ .

Lloyd Stowell Shapley. A value for n-person games. 1952.

The axioms are what make the division "fair". The whole payoff is distributed without remainder; players who are equally useful in any coalition get equal shares; a player who adds nothing to any coalition gets nothing; a player who is everywhere more useful in one game than in another gets no less in it; finally, if the payoff comes from several sources, the division adds up too.

Empirical estimation of the Shapley value

The exact formula requires going through all $2^{n - 1}$ coalitions, and with hundreds of features this is impossible. But the Shapley value is an expectation over a random permutation, and it can be estimated by sampling.

Definition (Empirical estimation of the Shapley value). An unbiased Monte Carlo estimate of the Shapley value: $Π$ is a random subset of permutations; for each $π \in Π$ the features $π (j)$ , $j = 1, \dots, n$ , are added to the model incrementally:

ϕ^_{j} = \frac{1}{∣Π∣} π \in Π \sum Δ (j, S_{π j}) .

What to take as the payoff $V (S)$ of the features $S \subseteq {f_{1}, \dots, f_{n}}$ :

the coefficient of determination $V (S) = R_{S}^{2}$ , with the model retrained as each feature is added;
the Shapley regression value $V (S) = f_{S} (x)$ on the object $x$ , where the model $f_{S}$ is trained only on the features from $S$ ;
the Shapley sampling value $V (S) = E_{x ~} f (x_{S}, x ~)$ , where $x = (x_{S}, x ~)$ and $E_{x ~}$ is the mean over the sample objects $x_{i} = (x_{S i}, x ~_{i})$ : $x_{S i} \approx x_{S}$ .

E. Štrumbelj, I. Kononenko. Explaining prediction models and individual predictions with feature contributions. 2014.

The choice of payoff determines what exactly is explained. If the payoff is the quality of the model $R_{S}^{2}$ , the Shapley value decomposes the quality of the model over the features: a global explanation. If the payoff is the model's answer on the object $x$ , the Shapley value decomposes that answer: an explanation of a particular prediction. The first variant needs a separate model for each coalition, trained only on its features, and that is expensive. The second variant makes do with one trained model: the absence of the features from $x ~$ is imitated by averaging over their values on sample objects that are similar to $x$ in the features $S$ .

The Shapley value for features in linear regression

For linear regression with the payoff $R_{S}^{2}$ , the Shapley value gives a way to correct the instability of the weights under multicollinearity.

Definition (The Shapley value for features in linear regression). $α = (F^{T} F)^{- 1} F^{T} y$ is the solution of the problem $∥ F α - y ∥^{2} \to min_{α}$ .

The decomposition of the coefficient of determination into net effects:

R^{2} = j = 1 \sum n α_{j} (f_{j}^{T} y) (for y^{T} y = 1, y ˉ = 0) .

The decomposition of $R^{2}$ into the Shapley values of the features, with $V (S) = R_{S}^{2}$ :

R^{2} = j = 1 \sum n ϕ_{j} .

Equating the effects, $ϕ_{j} = α_{j} (f_{j}^{T} y)$ , we get $α_{j} = ϕ_{j} / (f_{j}^{T} y)$ .

Advantages of the Shapley estimates $α_{j}$ for linear regression:

they are not affected by multicollinearity and are more stable;
the coefficients are interpretable by sign and magnitude;
they may be biased, but the bias is small.

S. Lipovetsky, M. Conklin. Analysis of regression in game theory approach. 2001.

Both sums decompose the same quantity $R^{2}$ over the features, but differently. The net effects inherit the instability of the least squares weights. The Shapley values are stable: each is the mean contribution of the feature over all coalitions, so correlated features share their common contribution between themselves instead of pulling it away from each other with opposite signs. If we require that the net effect of each feature equal its Shapley value, we obtain new regression coefficients. They no longer minimise the sum of squares exactly, that is, they have some bias, but they are stable and meaningful in sign and magnitude.

Surrogate modelling in the neighbourhood of an object

Another approach to explaining the prediction of a complex model on an object $x$ is to approximate it in the neighbourhood of $x$ by a simple interpretable model.

Definition (Surrogate modelling in the neighbourhood of an object).

$(x_{i}, y_{i})_{i = 1}^{ℓ}$ is the training sample, $L (f, y)$ the loss function;
$f (x, α)$ is an uninterpretable model trained on the sample:

$i = 1 \sum ℓ L (f (x_{i}, α), y_{i}) \to α min;$
$g_{x} (z, β)$ is an interpretable surrogate model that approximates $f$ in the neighbourhood of the object $x$ being explained:

$i = 1 \sum k w_{x i} L (g_{x} (z_{i}, β), f (z_{i}, α)) + Ω (β) \to β min;$
$(z_{i})_{i = 1}^{k} \sim π (K_{h} (z, x))$ are surrogate objects sampled from a radial distribution centred at $x$ with radius $h$ ;
$w_{x i} = K_{h} (z_{i}, x)$ are the weights of the objects in the $h$ -neighbourhood of the object $x$ ;
$K_{h} (z, x)$ is a closeness function (kernel) of radius $h$ ;
$Ω (β)$ is a regulariser, a penalty on the complexity of the model $g_{x} (z, β)$ .

The training sample for the surrogate model is not the original objects with the teacher's answers but synthesised objects $z_{i}$ with the answers of the complex model $f$ itself. The surrogate model learns to imitate $f$ , and only in the neighbourhood of $x$ : the objects are weighted by their closeness to $x$ . The regulariser prevents the surrogate model from becoming complex, otherwise its interpretability would be lost.

The LIME method

Definition (The LIME method (Local Interpretable Model-agnostic Explanations)).

g_{x} (z, β) = j = 1 \sum m β_{j} b_{j} (z) is a local linear approximation.

the object $x$ for which an explanation is required is fixed;
surrogate objects $z_{i}$ are synthesised in its neighbourhood;
the values of the main model $f (z_{i}, α)$ are computed on them;
a local approximation by the surrogate model is built;
an explanation and its visualisation are built for the object $x$ .

M. Ribeiro, S. Singh, C. Guestrin. "Why should I trust you?" Explaining the predictions of any classifier. 2016.

The method does not depend on the design of the model $f$ (it is model-agnostic): it only needs to be able to compute its answers on the synthesised objects. Globally the model can be as nonlinear as you like, but in a small neighbourhood of the object its boundary is almost straight, and a linear model approximates it well. The weights of this linear model serve as the explanation.

Definition (The LIME method: synthesising surrogate objects).

g_{x} (z, β) = j = 1 \sum m β_{j} b_{j} (z) is a local linear approximation;

the features $b_{j} (z) = [the j -th distortion of the object x is absent in the surrogate z]$ ;
synthesising a surrogate $z (b)$ : apply to $x$ all the distortions $j$ for which $b_{j} = 0$ ;
synthesising a sample of surrogates $(z_{i})_{i = 1}^{k}$ : by random $b_{j} \in {0, 1}$ .

O. Sedukhin. Model interpretation and data shift diagnostics: LIME, SHAP and Shapley Flow. 2022 (in Russian).

An important detail: the features of the surrogate model are not the original features of the object but binary indicators of "distortions". The object $x$ is spoiled by a set of $m$ predefined distortions; the binary vector $b$ says which of them are applied. For example, an image of a cat is split into fragments, and a distortion is painting a fragment grey; $b = (1, 0, 0, 1, 1, 0, 1, 1)$ means that the second, third and sixth fragments are painted over. The surrogate model explains the answer of $f$ on $x$ in terms of these distortions, which a person can understand.

Definition (The LIME method: interpretability of the surrogate model).

g_{x} (z, β) = j = 1 \sum m β_{j} b_{j} (z) is a local linear approximation.

Examples of interpretable distortions of the object $x$ :

replacing the $j$ -th feature in $x$ by a missing value, the mean value or 0;
replacing part of the object $x$ by part of another object;
dropping the $j$ -th word from the text $x$ , and so on.

Interpretability of the linear model $g_{x} (z, β)$ :

the weight $β_{j}$ equals the change in $g$ when the distortion $b_{j}$ is removed;
the number $m$ must not be too large;
there must be no multicollinearity (regularisation!).

$L (g, f) = (g - f)^{2}$ is the quadratic loss function; $K_{h} (z, x) = exp (- \frac{1}{h ^{2}} ρ^{2} (z, x))$ , where $ρ$ is the Euclidean or cosine metric.

M. Ribeiro, S. Singh, C. Guestrin. "Why should I trust you?" Explaining the predictions of any classifier. 2016.

Example (LIME: text classification (20 Newsgroups)). The features $b_{j} (z) = [the word j of the text x is present in the text z]$ ; a histogram of the weights $β_{j}$ shows the importance of the words $j$ for the original text $x$ .

The SVM-RBF classification model has 94% accuracy on test, but when distinguishing the classes "christianity" and "atheism" it considers the junk words "Posting", "Host", "Re" important. It is clear what the problem is and how to fix it (filter the words).

This example from the paper of the LIME authors shows why a developer needs explanations. By its test accuracy the model looks excellent, but the explanations reveal that it distinguishes topics by service words from the e-mail headers. In this dataset such words happen to correlate with the topic, and on new data the model will fail. Without explanations this problem cannot be seen, and once it is seen it is easy to fix: remove the headers from the texts.

Example (LIME: image classification). The features $b_{j} (z)_{j = 1}^{m}$ are segments (super-pixels) of the image $x$ ; $m = 10$ , and the features are constructed for the object $x$ being explained.

The classification model is the deep neural network Inception. The three most probable classes for a photograph of a person with a guitar and a dog: "electric guitar" ( $p = 0.32$ ), "acoustic guitar" ( $p = 0.24$ ), "labrador" ( $p = 0.21$ ). The explanation for the class "electric guitar" highlights the neck of the guitar: it is clear why the model confused "acoustic" with "electric".

The explanation of each class is the few image segments with the largest weights $β_{j}$ . For "labrador" the dog's face is highlighted, for "acoustic guitar" the body of the guitar, and for the erroneous "electric guitar" the neck, which really is similar in acoustic and electric guitars.

The Anchors method

Definition (The Anchors method: approximation by conjunctions).

g_{x} (z, β) = j \in J ⋀ b_{j} (z) are conjunction rules

formed by a small number of binary features or threshold conditions.

The rule tries to cover as large a region as possible of the objects that the model $f$ assigns to the same class as $x$ . It beats LIME in precision, coverage and quality of explanations.

M. Ribeiro, S. Singh, C. Guestrin. Anchors: high-precision model-agnostic explanations. 2018.

The surrogate model here is not a linear function but a logical rule, that is, a conjunction of several conditions. Such a rule is an "anchor": as long as the conditions hold, the model with high probability gives the same answer as on $x$ , however everything else changes. An example by the same authors is the sentiment analysis of two reviews: "This movie is not bad" (positive) and "This movie is not very good" (negative). LIME gives the word "not" a positive weight in the first review and a negative one in the second, and from the weights of individual words it is hard to understand how the model reasons. Anchors explain more clearly: ${not, bad} \to$ positive, ${not, good} \to$ negative.

The SHAP method

The SHAP method combines both ideas: the LIME surrogate model and the Shapley value.

Definition (The SHAP method (SHapley Additive exPlanations)).

g_{x} (z, β) = j = 1 \sum m β_{j} b_{j} (z) is a local linear approximation;

the features $b_{j} (z) = [the j -th distortion of the object x is absent in the surrogate z]$ ;
synthesising a surrogate $z (b)$ : apply to $x$ all the distortions $j$ for which $b_{j} = 0$ ;
the increment of $f (z, α)$ if the distortion $j$ is removed from the surrogate $z (b)$ :

$Δ (j, b) = V (b ∣_{b_{j} = 1}) - V (b ∣_{b_{j} = 0}), V (b) = f (z (b), α) .$

Three desirable properties of the local model $g_{x} (z, β)$ :

local accuracy of the approximation at the point $x$ : $\forall j b_{j} (z) = 1 \Rightarrow g_{x} (z, β) = f (x, α)$ ;
uselessness of a dummy, a feature $b_{j}$ missing in $x$ : $\forall j b_{j} (x) = 0 \Rightarrow β_{j} = 0$ ;
consistency: as the increment $Δ (j, b)$ grows, $β_{j}$ grows: $\forall j : (\forall b Δ_{1} (j, b) ⩽ Δ_{2} (j, b)) \Rightarrow β_{1 j} ⩽ β_{2 j}$ .

Here the distortions play the role of the players of a cooperative game, and the payoff of a coalition $b$ is the model's answer on the surrogate in which the distortions from $b$ have been removed. Properties 1–3 are analogues of Shapley's axioms. The first is efficiency: on the undistorted object the surrogate model reproduces the answer $f (x, α)$ exactly. It is implied here that the model's answer on a fully distorted object, $f (z (0), α)$ , is taken as the origin; otherwise a free term $β_{0} = f (z (0), α)$ is added to $g_{x}$ . The second is the "dummy" axiom, the third is consistency.

Theorem (Lundberg, Lee). The only distribution of the weights $β_{j}$ that satisfies properties 1, 2, 3 is the Shapley value:

β_{j} = b \in {0, 1}^{m} : b_{j} = 0 \sum \frac{∣ b ∣ ! ( m - ∣ b ∣ - 1 )!}{m !} Δ (j, b),

where $∣ b ∣ = {k : b_{k} = 1}$ is the number of ones in the vector $b$ .

Theorem (The Shapley Kernel method). The Shapley value $(β_{j})$ is the solution of a weighted least squares problem:

b \in {0, 1}^{m} \sum w_{b} (g_{x} (z (b), β) - f (z (b), α))^{2} \to β min,

where $w_{b}$ are the weights of the $2^{m}$ surrogates:

w_{b} = \frac{∣ b ∣ ! ( m - ∣ b ∣ - 1 )!}{m !} \cdot \frac{m - 1}{∣ b ∣} = \frac{1}{m C _{m - 2}^{∣ b ∣ - 1}} .

The second theorem is remarkable in that it reduces computing the Shapley value to a weighted linear regression, that is, exactly to the LIME problem, only with special weights for the surrogates. The weights are large for vectors $b$ with very few or very many ones: surrogates in which one distortion has been removed, or only one remains, carry the most information about the contribution of an individual distortion. For $b = 0$ and $b = 1$ the weight becomes infinite. In practice these two surrogates do not enter the sum but act as constraints: the surrogate model must reproduce the answer of $f$ on them exactly.

Definition (The Shapley Kernel method: an implementation of SHAP).

⊕ The Shapley value $(β_{j})$ is computed by a weighted linear regression.
⊕ LIME solves the same problem, but the surrogate weights $w_{b}$ are set heuristically, not optimally.
⊕ For large $2^{m}$ the vectors $b$ can be sampled from the distribution $w_{b}$ .
⊕ SHAP is better than LIME in experiments where they were compared with how experts explain the decisions of models.
⊖ The importance of features is estimated on unrealistic (out-of-distribution) surrogate objects.

Scott Lundberg, Su-In Lee. A unified approach to interpreting model predictions. 2017. E. Kumar, S. Venkatasubramanian, C. Scheidegger, S. A. Friedler. Problems with Shapley-value-based explanations as feature importance measures. 2020.

A drawback common to PDP, PFI, LIME and SHAP is evaluating the model on objects of a kind that does not occur in the data: the distorted surrogates lie outside the distribution on which the model was trained, and its answers on them can be arbitrary. The second paper in the list is devoted, among other things, to criticism of Shapley values as measures of feature importance.

Example (The SHAP method: an example of visualisation). The model of the probability of default $f (x)$ is gradient boosting.

An individual explanation for a borrower $x$ : $f (x) = 19%$ with a mean default rate of $y ˉ = 6%$ . The Shapley values are shown in colour: features with $β_{j} (x) < 0$ lower the risk estimate, those with $β_{j} (x) > 0$ raise it; the features are income, days since the last payment, the interest to be paid, the number of previous loans, age, and the number of requests to the credit bureau.

Aggregated explanations over the whole sample ${β_{j} (x_{i})}$ : on the X axis, $β_{j} (x_{i})$ ; on the Y axis, the features $j$ ; the colour of a point is the value of the feature $f_{j} (x_{i})$ ; the width of a line is proportional to the number of points.

The individual explanation shows how the estimate of 19% for the given borrower is made up from the average risk level of 6%: each feature shifts it up or down by its Shapley value. The aggregated plot is built from the Shapley values on all the objects of the sample. It shows at once both the overall importance of a feature (the horizontal spread of the points) and the direction of its influence: if the red points, large values of the feature, lie on the right, then risk grows as the feature grows.

The SAGE method

Definition (The SAGE method (Shapley Additive Global importancE)).

SHAP: what are the contributions of the features $f_{j}$ to the prediction $f (x)$ .
SAGE: how the quality of the model as a whole depends on the features $f_{j}$ .

The modification SHAP → SAGE:

$V (S) = - L (E_{x ~} f (x_{S}, x ~))$ : the losses are decomposed (LossSHAP);
$ϕ_{j} = \frac{1}{ℓ} \sum_{i = 1}^{ℓ} ϕ_{j} (x_{i})$ : the Shapley values are averaged over the sample;
$ϕ_{j} = \frac{1}{∣ X ∣} \sum_{x_{i} \in X} ϕ_{j} (x_{i})$ : or over a random subsample $X$ , if it takes too long.

Ian C. Covert, Scott Lundberg, Su-In Lee. Understanding Global Feature Contributions With Additive Importance Measures. 2020.

SHAP explains one prediction, SAGE the quality of the model as a whole. For this, the payoff of a coalition of features becomes not the model's answers but the negated losses of a model that knows only the features of the coalition (the others are averaged out). The Shapley values computed for each object are then averaged over the sample. The result is a global estimate of feature importance which, unlike PFI, takes their interactions over all coalitions into account.

Interpretation in the object space

The Shapley value for objects

The same cooperative game theory can be applied not to features but to training objects: how useful is each object for training the model?

Definition (The Shapley value for objects: incremental learning). Now the training objects play a cooperative game:

$f_{S} (x)$ is the model trained on the subsample $S \subseteq {x_{1}, \dots, x_{ℓ}}$ ;
$V (S) = - \sum_{x} L (f_{S} (x), y (x))$ on test objects $x$ (hold-out);
$Δ (i, S) = V (S \cup i) - V (S)$ is the utility of the training object $x_{i}$ ;
$ϕ_{i} = \frac{1}{∣Π∣} \sum_{π \in Π} Δ (i, S_{π i})$ is an unbiased Monte Carlo estimate.

Algorithm: $ϕ_{i} := 0$ for all $i$ ;

for all permutations $π_{t} \in Π$ , $t = 1, \dots, ∣Π∣$ :

$S := \emptyset$ ; $v_{0} := V (\emptyset)$ ;
for all $k = 1, \dots, ℓ$ :
- $i := π_{t} (k)$ ; $S := S \cup {x_{i}}$ ;
- update the model $f_{S} (x)$ by training it further on the object $x_{i}$ ;
- evaluate the model $v_{k} := V (S)$ ;
- $ϕ_{i} := \frac{t - 1}{t} ϕ_{i} + \frac{1}{t} (v_{k} - v_{k - 1})$ .

A. Ghorbani, J. Zou. Data Shapley: equitable valuation of data for machine learning. 2019.

The payoff of a coalition of objects is the quality of a model trained on these objects, measured on a held-out sample. The objects are added to the training sample in the order of a random permutation, and each is credited with how much the quality improved after it was added. The last line of the algorithm accumulates the mean over permutations: after $t$ permutations $ϕ_{i}$ equals the mean of the $t$ additions of the object $x_{i}$ . Incremental learning is essential here: going through one permutation, the model is not retrained from scratch on each subsample but is trained further on the next object.

The Gradient Shapley method

The cheapest way of further training is one step of online gradient descent.

Definition (Building Shapley estimates into online gradient descent). Gradient minimisation of an additive criterion:

i = 1 \sum ℓ L (f (x_{i}, α), y_{i}) \to α min .

The incremental learning algorithm Online Gradient Descent: $ϕ_{i} := 0$ for all $i$ ;

for all permutations $π_{t} \in Π$ , $t = 1, \dots, ∣Π∣$ :

$S := \emptyset$ ; $v_{0} := V (\emptyset)$ ; initialise $α_{0}$ ;
for all $k = 1, \dots, ℓ$ :
- $i := π_{t} (k)$ ; $S := S \cup {x_{i}}$ ;
- update the model $α_{k} := α_{k - 1} - η_{k} \nabla_{α} L (f (x_{i}, α_{k - 1}), y_{i})$ ;
- evaluate the model $v_{k} := V (S)$ ;
- $ϕ_{i} := \frac{t - 1}{t} ϕ_{i} + \frac{1}{t} (v_{k} - v_{k - 1})$ .

A. Ghorbani, J. Zou. Data Shapley: equitable valuation of data for machine learning. 2019. M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. 2003.

One pass through a permutation is one epoch of stochastic gradient descent in which the objects are presented in the order of the permutation, and the quality of the model is measured after each step. The Shapley value of an object comes almost for free, as a by-product of training, and the usefulness of an object is measured by how much its gradient step improved the model.

Interpreting objects with Shapley values

Definition (Interpreting objects with Shapley values).

a low $ϕ_{i}$ : outliers; such $x_{i}$ can be removed from the sample;
a high $ϕ_{i}$ : support, boundary objects; such $x_{i}$ are in short supply;
a more stable estimate than leave-one-out.

Experiment (the UCI BreastCancer problem):

removing the best objects from training, in decreasing order of $ϕ_{i}$ ;
removing the worst objects from training, in increasing order of $ϕ_{i}$ ;
adding objects similar to the best ones, in decreasing order of $ϕ_{i}$ ;
adding objects similar to the worst ones, in increasing order of $ϕ_{i}$ .

A. Ghorbani, J. Zou. Data Shapley: equitable valuation of data for machine learning. 2019.

Objects with low and negative Shapley values make the model worse: these are outliers and labelling errors, and they can be removed. Objects with high values are support, boundary objects; these are exactly the objects the model lacks, and new objects similar to them are worth adding to the sample. The link with active learning is direct here. The leave-one-out estimate, the change in quality when one object is excluded, is less stable: if two objects duplicate each other, excluding either of them changes nothing, and both get a zero estimate, although together they are useful. In the authors' experiments on the breast cancer problem, removing the objects with the largest $ϕ_{i}$ degrades quality faster than removing random ones, while removing the objects with the smallest $ϕ_{i}$ improves quality.

Counterfactual explanations

The last type of explanation answers not the question "why did the model decide this way" but the question "what needs to change for it to decide otherwise".

Definition (The problem of finding counterfactuals). A counterfactual $x^{'}$ is an object similar to $x$ but with a substantially different model prediction $f (x^{'}, α^{*})$ .

A credit scoring model has issued a refusal. What changes in the features would change the model's decision? (Close other loans? Move to another city? Change jobs? Change the structure of expenses?)
A model has estimated the rental value for an owner. Which factors could increase the estimate? (Better renovation? Allow pets?)

Important: find feasible changes of the features:

change the minimum number of features minimally;
choose from a set of diverse counterfactuals.

Riccardo Guidotti. Counterfactual explanations and how to find them: literature review and benchmarking. 2022.

For a person who was refused a loan, the most useful thing is not a list of feature weights but advice: what they need to do to be approved. Such advice must be feasible: changing one's age or city of birth is useless, while changing the structure of one's expenses is possible. It must be economical: change as few features as possible, and as little as possible. And it is useful to offer several different options, so that the person can choose the one that suits them.

Definition (A method for finding counterfactuals (Counterfactual explanations)). A counterfactual $x^{'}$ is an object that differs minimally from $x$ and substantially in the model's prediction $f (x^{'}, α)$ . In psychology, a mentally imagined alternative course of events.

The optimisation problem of finding counterfactuals $x^{'}$ with a given $y^{'}$ :

L (f (x^{'}, α), y^{'}) + λ ∥ x - x^{'} ∥_{1} \to x^{'} min .

The $L_{1}$ regulariser makes the solution sparse: the larger $λ$ , the more features coincide, $x_{j}^{'} = x_{j}$ :

∥ x - x^{'} ∥_{1} = j = 1 \sum n \frac{∣ x _{j} - x _{j}^{'} ∣}{MAD _{j}},

Median Absolute Deviation $MAD_{j} = med_{i} ∣ x_{ij} - M_{j} ∣$ , $M_{j} = med_{i} x_{ij}$ .

By gradually decreasing $λ$ , we fit $f (x^{'}, α) \to y^{'}$ .

S. Wachter, B. Mittelstadt, C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. 2017.

The problem looks for an object $x^{'}$ on which the model gives the required answer $y^{'}$ and which differs little from $x$ . The distance is taken in the $L_{1}$ norm, and this is essential: as in LASSO, the $L_{1}$ penalty leads to a sparse solution in which most features stay unchanged and only a few change. Each feature is normalised by its median absolute deviation, a measure of spread robust to outliers, so that changes in different features are commensurable. One starts with a large $λ$ , at which $x^{'}$ almost coincides with $x$ , and decreases it until the model's answer on $x^{'}$ becomes close enough to $y^{'}$ .

Approaches to the explainability of models

The taxonomy from the survey by Belle and Papantonis gives an overall picture. Interpretable models — linear and logistic regression, decision trees, $k$ nearest neighbours, logical algorithms, generalised additive and Bayesian models — explain themselves. Opaque models — random forests, SVM, multilayer neural networks — need explanations "after training" (post-hoc). Such explanations fall into several categories: simplification (replacing the model by rules or a tree), feature importance estimates (influence functions, sensitivity, game-theoretic methods), local explanations (linear approximation, counterfactuals) and visual explanations (dependence plots). Examples of methods are SHAP, Anchors, LIME, counterfactual examples, ICE, PDP, and rule extraction from tree ensembles (inTrees).

V. Belle, I. Papantonis. Principles and practice of explainable machine learning. 2020.

Summary

Interpretability is the transparency of the model's design, or the understandability of its result on an object.
There are not many interpretable models: linear (MVLR, LR, GAM, GLM), logical (DT, RI), metric (kNN, PW, RBF), Bayesian (NB, BN).
Explaining a decision on an object is done, as a rule, with an interpretable surrogate model.
The Shapley value estimates the contributions of "players" to the overall result from data on the success of their coalitions; the "players" are features, but the idea applies to objects too.
SHAP and SAGE are the most advanced explanation methods.

P. Linardatos, V. Papastefanopoulos, S. Kotsiantis. Explainable AI: A Review of Machine Learning Interpretability Methods. 2021. Zachary C. Lipton. The Mythos of Model Interpretability. 2018. Christoph Molnar. Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. 2019. Ribana Roscher et al. Explainable Machine Learning for Scientific Insights and Discoveries. 2020.

The abbreviations in the summary: MVLR, multivariate linear regression; LR, logistic regression; GAM and GLM, generalised additive and generalised linear models; DT, decision trees; RI, rule induction; kNN, $k$ nearest neighbours; PW, the Parzen window; RBF, radial basis function networks; NB, the naive Bayes classifier; BN, Bayesian networks.

Machine Learning 2. Lecture 12. Interpretability and Explainability

What this lecture is about

Interpretability and explainability

Goals, tasks, basic notions

Interpretable models

Feature importance in linear regression

Visual methods: partial dependence plots

Interpretation in the feature space

Permutation feature importance

The Shapley value

Empirical estimation of the Shapley value

The Shapley value for features in linear regression

Surrogate modelling in the neighbourhood of an object

The LIME method

The Anchors method

The SHAP method

The SAGE method

Interpretation in the object space

The Shapley value for objects

The Gradient Shapley method

Interpreting objects with Shapley values

Counterfactual explanations

Approaches to the explainability of models

Summary

Voron-ML-xai.pdf