Lecture 8: Local explanations

Interpretability

• In this lecture we shift the perspective and we wish to understand what a predictor \(\hat m_n(x)\) is actually doing.

Interpretability

Interpretability in this lecture:

• Regression: \(Y_i=m(X_i)+\varepsilon_i\)
  • \(X\qquad \rightarrow \qquad \widehat m (X) \qquad \rightarrow \qquad m (X)\) or \(Y|X\)
• For now interpretability is understanding the relationship between \(X\) and \(\widehat m (X)\)
  • This is different to understanding the relationship between \(X\) and \(Y\).

• Current machine learning algorithms are often highly flexible and can deal with interaction, non-linearity, sparsity and variable selection; but they are not interpretable.

Interpretability Local explanations

• Fix a value \(x_0 \in \mathbb R^p\).

• A local approximation at \(x_0\) of the function \(\hat m_n\) is given by

\[\begin{align}\label{eq:shap} \hat m_n\left(x_0\right)=\phi_{0}+\sum_{k=1}^{p} \phi_k(x_0), \end{align} \]

• \(\phi_0,\phi_1(x_0),\dots,\phi_p(x_0)\) are constants.

• Note: the right hand-side is not identified.

• Local explanations add constraints such that \(\phi_k(x_0)\) is uniquely identified and best reflects the local contribution of feature \(k\) to \(\hat m_n\left(x_0\right)\).

Interpretability Local explanations: Shapley values

Interpretability Local explanations: Shapley values

Interpretability Local explanations: SHAP values

• Note that we will slightly abuse notation by ignoring ordering in the input of the functions below.

• Lundberg and Lee (2017) proposed to use Shapley values with value function \[ v_x(S)=\mathbb E[ \hat m_n(X_S,X_{-S})| X_S=x_S] = \int \hat m_n(x_1,\dots,x_p) p_{X_{-S}|X_S}(x_{-S}|x_S) \mathrm dx_{-S} \] for model explanation. And called it SHAP (SHapley Additive exPlanations).

• To simplify calculations, Lundberg and Lee (2017) proposed to calculate \[ v_x(S)= \mathbb E[\hat m_n(x_S,X_{-S})]= \int \hat m_n(x_1,\dots,x_p) p_{X_{-S}}(x_{-S}) \mathrm dx_{-S} \]

• Janzing, Minorics, and Blöbaum (2020) argue that the latter value function should actually be the preffered value function. Chen et al. (2020) coin it interventional SHAP (and the original SHAP above observational SHAP).

• In the next slide, we give an example why interventional SHAP values might be preferred compared to observational SHAP values.

Interpretability Local explanations: SHAP values

Interpretability Local explanations: SHAP values

• We conclude, that if one uses observational SHAP for model explanation, then the contribution of a feature is a combination of its own contribution and the contribution of features it is correlated with.

• We will later see that observational SHAP has one further issue: One may need to extrapolate in order to calculate it.

Interpretability Local explanations: SHAP values: Estimation

• How do we calculate/estimate Shapley values?

• Remember, Shapley values are: \[ \begin{align} \phi_{k}(x_0)&=\frac{1}{p !} \sum_{\pi \in \Pi_p} \Delta_{v_{x_0}}\left(k, \{\pi(1),\dots,\pi(\pi^{-1}(k)-1)\}\right)\\ &=\frac 1 {p!}\sum_{S: S \subseteq \{1,\dots,p\} \setminus\{k\}} {|S| !(p -|S|-1) !}\Delta_{v_{x_0}}(k, S), \end{align} \]

• To calculate Shapley values exact, one would (a) need to know the value function and (b) need to evaluate \(p!\) or (second equation) \(2^p\) summands. For large \(p\) that may be infeasible.

Interpretability Local explanations: SHAP values: Estimation

• Problem: many samples needed to get accurate approximation. Hence, slow.

Interpretability Local explanations: SHAP values: Estimation: Kernel SHAP

• Charnes et al. (1988) discussed that Shapley values can be re-written as the solution of the following constraint minimisation problem:

\[ (\phi(x_0))_{0,\dots,p} = \arg\min_{(\phi_k)_{k=0,\dots,p}} \sum_{S: S\subseteq\{1,\dots,p\}} \mu(S) \left(v_{x_0}(S)- \left [\phi_0 + \sum_{k \in S} \phi_k\right]\right)^2, \] \[ \mu(S) =\frac{p-1} {\binom{p}{|S|} |S| (p-|S|)}. \]

• Note that \(\mu(\emptyset)=\mu(\{1,\dots,p\})=\infty\) and so the minimisation is not well defined.
  • The infinite weight practically enforces \(\phi_0=v_{x_0}(\emptyset)\), \(\sum_{k=0}^p \phi_k=v_{x_0}(\{1,\dots,p\})\)
  • One can hence, exclude the two sets \((\emptyset, \{1,\dots,p\})\) from the minimisation and add the two constraints, \(\phi_0=v_{x_0}(\emptyset)\), \(\sum_{k=0}^p \phi_k =v_{x_0}(\{1,\dots,p\})\), to the minimisation.
• This is a quadratic programming problem (good), but estimating \(v_{x_0}(S)\) for all \(2^p\) subsets might economically not be feasible.

Interpretability Local explanations: SHAP values: Estimation: Kernel SHAP

• Introduced in Lundberg and Lee (2017), Covert and Lee (2021) give a detailed explanation on how Kernel SHAP is implemented.
  • Instead of estimating \(v_{x_0}(S)\) for all \(2^p\) subsets they only evaluate \(m\) subsets.
  • The \(m\) subsets are drawn from the set of all subsets of \(\{1,\dots,p\}\) minus the empty set and the full set, where the probability of drawing set \(S\) is proportional to \(\mu(S)\)
• Hence the final minimisation reads \[\begin{align} \min_{(\phi_k)_{k=1,\dots,p}} \frac 1 m \sum_{i=1}^m \left(v_{x_0}(S_i)- \left [v_{x_0}(\emptyset)+ \sum_{k \in S_i} \phi_k\right]\right)^2, \\ \text{subject to} \sum_{k=1}^p \phi_k =v_{x_0}(\{1,\dots,p\})-v_{x_0}(\emptyset), \end{align} \] where \(S_i\) is the subset from draw \(i\).

Interpretability Local explanations: SHAP values: Estimation: Kernel SHAP

In practice, this is often then solved by reformulating the minimization as a least squares linear regression problem: \[ \begin{aligned} \textrm{argmin}_{\phi \in \mathbb R^{p}} \sum_{i=1}^m\left((\nu(S_i) - \nu(\emptyset) )-M_i\phi \right)^2, \end{aligned} \] subject to \(\sum_{k=1}^p \phi_k = \nu(I_p) - \nu(\emptyset)\) and where \(M_i\) is the \(i\)th row of the matrix \(M\) with \(m\) rows \(p\) columns that binary encodes \(S_i\): \(M_{ij}= \mathbb 1(j\in S_i)\), \(j=1,\dots,p\).

• The value function used in Kernel SHAP is interventional SHAP, i.e., \(v_{x_0}(S)=\mathbb E[\hat m_n(x_S,X_{-S})]\).

Interpretability Local explanations: SHAP values: TreeSHAP

• Lundberg and Lee (2017) propose a method to estimate interventional SHAP that is fast.

• It is specific for tree based algorithms.

• The algorithm is called TreeSHAP and it makes use of the binary tree structures that leads to a partitioning of the feature space.

  • For calculating \(\mathbb E[\hat m_n(x_S,X_{-S})]\), TreeSHAP recursively follows the decision path for \(x_0\) if the split feature is in \(S\), and takes the weighted average of both branches if the split feature is not in \(S\).
  • For efficient calculation, TreeSHAP does not go down the tree for every \(S\) separately but only once and while doing so keeps track of all possible \(S\).

Interpretability Local explanations: SHAP values: TreeSHAP

• Unfortunately TreeSHAP does not correspond to an empirical version of Interventional SHAP.

• In fact, two trees leading to the estimator can have different TreeSHAP values if their paths are different. In other words TreeHAP is path-specific which is an undesirable property.