Local Explainability#

LIME (Local Interpretable Model-Agnostic Explanation)#

LIME (Local Interpretable Model-Agnostic Explanation; [Ribeiro2016]) is a model agnostic explanation tool. It does so by creating a surrogate interpretable model, such as a Lasso or decision tree, to explain how the original model makes predictions for a given input sample.

The process is straightforward:

Create a simulated dataset by randomly perturbing the input sample with noises (as \(x\)), and then evaluate the output of the original model on these perturbed samples (as \(y\)).
An interpretable model (Lasso in our case) is fitted on this simulated data, with weights assigned to each perturbed sample based on its proximity to the original input sample.

The Modeva implementation of LIME is based on the LIME package. For binary classification problems, it uses predict_proba as the response.

SHAP (SHapley Additive exPlanations)#

SHAP (Shapley Additive Explanations; [Lundberg2017], [Lundberg2018]) is a machine learning tool that can explain the output of any model by computing the contribution of each feature to the final prediction. The concept of SHAP can be explained with a sports analogy. Suppose you have just won a soccer game and want to distribute a winner’s bonus fairly among the team members. You know that the five players who scored the goals played a significant role in the victory, but you also recognize that the team could not have won without the contributions of other players. To determine the individual value of each player, you need to consider their contribution in the context of the entire team. This is where Shapley values come in - they help to quantify the contribution of each player to the team’s success.

The Shapley value explanation method possesses several attractive properties, such as local accuracy, missingness, and consistency. It decomposes the prediction into a linear combination of feature contributions, as illustrated below.

\[\begin{align} g\left(z^{\prime}\right)=\phi_0+\sum_{j=1}^p \phi_j z_j^{\prime}, \tag{1} \end{align}\]

where \(g\) is the explanation method, \(p\) is the number of features, and \(z^{\prime} \in \{0, 1\}^p\) is the coalition vector that indicates the on or off state of each feature. The Shapley value of the \(j\)-th feature is denoted as \(\phi_{j}\), which can be estimated using various approaches. In Modeva, the Shapley values are computed based on the shap Python package, which offers several methods for estimating Shapley values. The following sections will introduce these estimation algorithms in detail. In particular, we use the shap.Explainer if the estimator is supported by the shap Python package. Otherwise, we will use the exact solution if the number of features is less than or equal to 15, and otherwise KernelSHAP.

Exact Solution#

The exact solution is obtained using the Shapley value formula, which requires evaluating all possible coalitions of features with and without the \(i\)-th feature.

\[\begin{align} \phi_{i}= \sum_{S \subseteq \{1, \ldots, p\} \backslash \{ i \}} \frac{|S|!(p-|S|-1)!}{p!}(val(S \cup \{i\}) - val(S)). \tag{2} \end{align}\]

where \(val\) is the value function that returns the prediction of each coalition. The marginal contribution of feature \(i\) to the coalition \(S\) is calculated as the difference between the value of the coalition with the addition of feature \(i\) and the value of the original coalition, i.e., \(val(S \cup \{i\}) - val(S)\). The term \(\frac{|S|!(p-|S|-1)!}{p!}\) is a normalization factor. When the number of features is small, this exact estimation approach is acceptable. However, as the number of features increases, the exact solution may become problematic.

It’s worth noting that the value function \(val\) takes the feature coalition \(S\) as input. However, in machine learning models, the prediction is not solely based on the feature coalition but on the entire feature vector. Therefore, we need to specify how removing a feature from the feature vector affects the prediction. Two common approaches are available, both of which depend on a pre-defined background distribution instead of merely replacing the “missing” features with a fixed value.

The former conditions the set of features in the coalition and uses the remaining features to estimate the missing features, but it can be challenging to obtain the conditional expectation in practice. The latter approach breaks the dependency among features and intervenes directly on the missing features of the sample being explained, using corresponding features from the background sample. This approach is used in the KernelSHAP algorithm.

Conditional expectation: This approach conditions the set of features in the coalition and uses the remaining features to estimate the missing features. However, obtaining the conditional expectation can be challenging in practice.
Interventional conditional expectation (the option used in Modeva): This approach breaks the dependency among features and intervenes directly on the missing features of the sample being explained, using corresponding features from the background sample.

KernelSHAP#

KernelSHAP is a kernel-based approach for estimating Shapley values that are inspired by local surrogate models. It is particularly useful for computing Shapley values with a large number of features. Given an instance \(x\), KernelSHAP estimates the contributions of each feature using the following steps:

Randomly sample coalitions and compute the output of these simulated coalitions.
Calculate the weight of each feature in the coalition using the SHAP Kernel (see the details in the reference [Lundberg2017]).
Fit a weighted linear model to the sampled coalitions.
Return the Shapley values which are the coefficients of the linear model.

KernelSHAP ignores feature dependence. Sampling from the marginal distribution means ignoring the dependence structure between features, which may result in an estimation that puts too much weight on unlikely instances. Moreover, KernelSHAP is not guaranteed to be consistent with the exact solution, and it also requires a lot of computation time. In practice, we usually do downsampling to reduce the computation time (by default 500 in Modeva).

LinearSHAP and TreeSHAP#

In addition to exact solution and KernelSHAP, the shap package also provides specific estimation algorithms for certain models, e.g., LinearSHAP and TreeSHAP. The following paragraphs will introduce these algorithms in detail. However, most of the built-in models in Modeva do not benefit from these algorithms for the moment, and we instead use the exact solution or KernelSHAP.

LinearSHAP computes the SHAP values for a linear model and can account for the correlations among the input features.

Conditional expectation: Accounts for the correlation of features, and a subsample of data is used to estimate a transformation that can then be applied to explain any prediction of the model.
Interventional conditional expectation (default): Assumes features are independent, and the SHAP values for a linear model are \((x - \bar{x})\) multiplied by the coefficients.

TreeSHAP is a model-specific algorithm designed for tree-based models. In decision trees, each leaf node explicitly defines a feature interaction, allowing interactions not present in the tree structure to be ignored and reducing the number of coalitions. This reduction in coalitions greatly reduces computation time for tree-based models. TreeSHAP offers two ways to compute Shapley values:

Path-dependent tree explainer, which approximates interventional conditional expectation based on the number of training samples that went down paths in the tree.
Interventional tree explainer (the default), which computes interventional conditional expectation exactly, but is a bit slower than the path-dependent method.