LEMON: Alternative Sampling for More Faithful Explanation Through Local Surrogate Models

Explaining artificial intelligence (XAI) is important in high-impact domains such as credit scoring, employment and housing [5, 9, 12]. In these fields, incorrect model behavior may lead to additional direct costs, opportunity costs, as well as unfavorable bias and discrimination. XAI techniques can help identify and alleviate such problems [1]. Let us consider a real-world example: recent work has shown that, for commercial face classification services, accuracy of gender classification on dark-skinned females is significantly worse than on any other group [8]. This discrepancy was conjectured to be largely due to unrepresentative training datasets and imbalanced test benchmarks. However, using explanation techniques, it was shown that the classifiers made use of makeup as a proxy for gender in a way that did not generalize to the rest of the population [20].

A common approach to explain machine learning models is to create an explanatory, or surrogate model that mimics the reference model. As the surrogate is typically simpler, it can be used to understand the complex reference model. This enables us to understand any model (i.e., model-agnostic approach) without having to alter that model (which could hurt performance). The extent to which this surrogate accurately approximates the reference model is called faithfulness (or fidelity).

There are two ways to obtain a surrogate model. The first is to globally mimic the reference model with an inherently simple surrogate model. However, due to this simplicity, the resulting surrogate can often not faithfully represent the reference model, which leads to inaccurate or incorrect explanations. Another approach is to consider only a small part of the complex reference model, and locally mimic that portion. Such surrogate models remain locally faithful to the reference model, while also being simple enough to understand. The current state-of-the-art techniques to explain individual predictions (e.g., LIME [21]) apply this approach by targeting only the part of the model that is relevant for that particular prediction. This process is illustrated in Fig. 1.

To generate such a surrogate, a simple model is trained on transfer data: a set of data points labeled by the reference model. This technique is well-known, but until recently was only applied to approximate models globally. For local explanations, samples from a constrained region are used to obtain a surrogate that is locally faithful, and simple enough to be considered interpretable [4, 21].

In this paper, we investigate transfer data sampling techniques for local surrogate models, and identify that the faithfulness of existing techniques may be impaired in high dimensionality. We explore alternative sampling techniques and introduce Local Explainable MOdel explanations using N-ball sampling (LEMON): an improved sampling technique that is more faithful and robust than the current state-of-the-art techniques by sampling directly from the desired distribution instead of reweighting samples (see Fig. 1).

The idea of using transfer data to approximate a model globally was introduced by Craven et al. [10] and Domingos [11] and it has been used for model compression [3, 7, 18, 19, 22, 24], comprehensibility [4, 6, 21, 23] and generalization [18].

The types of surrogate models used vary widely. While for local explanation, linear regression is sufficient [21], global explanation requires more expressive surrogate models, e.g., shallow neural networks [22, 24], decision trees [6, 10], and rule sets [11, 23]. Furthermore, we identified two main categories of sampling techniques for surrogate learning used in previous work:

Observation-based sampling uses the training data of the model as transfer data. When features in a dataset are correlated, certain values in feature space are less likely (or impossible) to occur compared to the correlated (or ‘sensible’) region of feature space. Observation-based sampling yields more samples in that sensible part of the feature space. However, the number of samples for transfer data is limited. Oversampling techniques like Naive Bayes Estimation (NBE) or MUNGE [7] can partially address this problem.

Which of these sampling techniques to use for surrogate learning is generally not considered thoroughly. For example, some authors make empirical claims such as “We have found that using the original training set works well” [18]. However, it is unclear what kind of benefit observation-based sampling yields compared to synthetic sampling, or how the chosen synthetic sample distribution affects the quality of explanations.

The vast majority of the reviewed papers focused on global approximations, in which the faithfulness (i.e., accuracy with respect to the reference model) of the surrogate model is compromised in order to simplify the surrogate and hence the resulting explanation, or reduce its memory footprint for model compression. The focus of this paper is on sampling for local surrogates instead. By only considering a small part of the reference model, and only locally mimicking that portion of the complex model, the surrogate remains faithful and simple. This approach is more recent and gained a lot of popularity with the introduction of the LIME explainability framework [21].

To understand sampling for local surrogates, we consider LIME [21], as it is a widely popular local explanation technique, and for its clear and accessible usage of surrogate models. The transfer data in LIME are samples that are drawn from a fixed multivariate Gaussian distribution centered on the global mean of the training data. Here, fixed means that the distribution does not depend on the data point to be explained. Next, these samples are weighted based on their proximity to the data point to be explained. The locality of the technique is a result of this weighing. Then, a linear regression surrogate model is trained on these weighted samples, and the coefficients are presented as a “feature contribution” explanation that shows how important a feature is to a prediction: a small change in a feature with a high coefficient will lead to a large change in prediction, and hence can be considered important to the model.

As a consequence of fixing the transfer data independently of the point to be explained, a notable drawback of systems such as LIME is that as the dimensionality of the data increases, the chances of obtaining samples close to the instance to be explained gets ever smaller. Hence, the robustness and faithfulness are significantly impaired for high-dimensional data. This is very similar to the known “curse-of-dimensionality” limitation of rejection sampling, in which most proposed points are not accepted as valid samples in high dimensions. In addition to faithfulness, Alvarez-Melis and Jaakkola [2] have demonstrated that using only few relevant samples (100 in their study) degrades the robustness of the explanation from LIME (i.e., very different explanations for similar inputs).

To experimentally verify this effect, we set up an experiment in which we can arbitrarily increase the dimensionality of the model without affecting other semantics of the machine learning setup. Consider the n-dimensional feature space \(\mathcal {X} \subset \mathbb {R}^n\), and two classification models representing a hyperbox (\(b(\textbf{x})\)) and hypersphere (\(s(\textbf{x})\)) respectively:classifying \(\textbf{x}\in \mathcal {X}\) as either true or false. These models are simple enough to quickly change the dimensionality of the model, while being complex enough to resemble a realistic complex classification model that cannot perfectly be represented by the local surrogate model.

We chose the input data point \(\textbf{x}= [ 1, 0, 0, ... ]\), a point on the surface of the decision boundary of the model. Next, a surrogate model is generated using LIME and four different kernel width parameters. We chose values from 0.1 to 0.4 to approximate the right side of the model only (\(x_0 > 0\)). By measuring the faithfulness of the surrogate models generated for different dimensional models, we assert whether the faithfulness is impaired in high-dimensional space.

For data point \(\textbf{x}\) and varying levels of dimensionality, we measure the faithfulness of the linear surrogate model, using the cosine similarity between the coefficient vector of the surrogate, and that of the best possible linear model in this setup: \(f(\textbf{x}) = \textbf{x}_0\), coefficients shown in Fig. 2c. Contrary to more traditional faithfulness metrics (e.g., RMSE or \(R^2\)), this approach measures the agreement between the models without the need for additional sampling.

Figure 2 shows that for models with only a modest number of dimensions (i.e., 10–20 depending on the kernel width), the faithfulness of LIME is already significantly impaired, which can result in untrustworthy and misleading explanations. In addition, the explanations are not robust as indicated by the heavy fluctuations. This happens because in high-dimensions, very few relevant samples are generated in the neighborhood of the point to be explained, and hence, the linear model is unable to approximate the behavior of the reference model. For a 15-dimensional box model, Fig. 2c shows the expected coefficients (blue) and coefficients of the linear surrogate from LIME (green). Even though only feature 0 has a substantial role for prediction, LIME incorrectly reports that many other features are relevant.

Note that LIME employs LASSO feature selection to reduce dimensionality ahead of explanation. However, this step is subject to the same limitations as outlined in this section. For simplicity, we disregard the feature selection option.

We introduce LEMON: Local Explainable MOdel explanations using N-ball sampling, which addresses the issues identified in Sect. 3. This technique samples directly from the desired distribution (defined by a distance-kernel function), instead of reweighting samples. This naturally yields data points where we need them: in the neighborhood (or region of interest) of the instance \(\textbf{x}\) to be explained.

In this section, we first revisit the first synthetic evaluation example introduced in Sect. 3. Next, to use a more realistic scenario, we compare LEMON and LIME on standardized UCI datasets and a variety of models. Source code for our experiments can be found here: https://​github.​com/​iamDecode/​lemon-evaluation.

The LIME explanation framework includes an optional preceding feature selection step (using LASSO). One could argue that feature selection ahead of the explanation technique decreases the dimensionality, enabling LIME to be more suitable in higher dimensional space than we have shown in Sect. 3. However, the feature selection algorithm still needs to consider the full feature space in order to select features, which it cannot properly do without sufficient neighboring samples: it is subject to the same limitations. Hence, in our study we have disregarded the feature selection step in LIME as it makes evaluation and comparison more difficult. However, we expect similar results when including feature selection as part of both compared algorithms.

Supporting Observation-Based Sampling. Sampling with either a uniform or Gaussian distance kernel remains a synthetic approach: new samples are drawn regardless of the distribution of the original data. Thus, the surrogate model may be fitted using out-of-distribution data. To address this limitation, we cannot simply use a custom distance kernel in Eq. (3). The distance kernel is a kernel function applied to the distance r between a sample \(\textbf{x}_i\) and the instance to be explained \(\textbf{x}\), and r does not tell us enough about the location of that sample. Instead, we propose to find all original dataset samples \(\big \{\textbf{s}\in \mathcal {X} \,\mid \, \sqrt{(\textbf{x}-\textbf{s})^2} < r_\text {max} \big \}\) within radius \(r_\text {max}\). Next, we approximate the density of these local samples with kernel density estimation (KDE) and sample points from the resulting estimated density function. This can be done by choosing a random point, and offsetting it by randomly drawn value from the KDE kernel function. This yields an alternative probability distribution on the ball of radius \(r_\text {max}\) around \(\textbf{x}\) to Eq. (3), but does not change the key idea behind LEMON.

Kernel Shape. Previous work and this paper assume that a spherical region around an instance is the best representation of a local neighborhood. However, some recent rule based techniques effectively use hyperboxes instead [23]. In addition, sampling towards the closest decision boundary may yield samples with a more salient gradient. It would be interesting to investigate what the relevance and effect is of the shape of the sampling region. Next, it would be interesting to see if we can extend our work to explain multiple instances at once by sampling from multiple distributions efficiently.

Measuring Faithfulness. We currently evaluated the explanations using faithfulness: the more closely the local surrogate model resembles the reference model, the better. However, there is no consensus on the best way to measure this. LIME itself calculates faithfulness based on the transfer data points the surrogate itself was trained on. This is problematic because, as we have shown in Sect. 3, LIME produces only few relevant samples in the neighborhood of the point to be explained. Hence, the surrogate model would be evaluated using few relevant samples, leading to misleading faithfulness scores. In our synthetic examples, we could circumvent this as the most optimal set of coefficients was known, and hence we use the cosine similarity between the most optimal coefficients and those from the local surrogate. However, in a realistic scenario, the most optimal coefficients are simply not known. For evaluating with real datasets (Sect. 5.2), we thus decided to use the RMSE between the reference and surrogate model, computed on many (50,000) newly generated samples instead of the original transfer data.

As an alternative, we have considered the coefficient of determination (\(R^2\)) as a metric for faithfulness. This metric is used internally in LIME, and shows the proportion of the variance in the response variable of a regressor that can be explained by the predictor variables. However, we noted that for some (outlier) data points in our evaluation, almost all sampled data points get roughly the same predicted outcome from the reference classifier. In such case, the variance of the predicted outcomes is (very close to) 0. Computing the \(R^2\) score with this data yields \(R^2\) values of (close to) minus infinity, severely skewing the results.

Finally, faithfulness in itself does not guarantee the best possible explanation. There are many (often subjective) desiderata to consider when evaluating explanations, which are almost impossible to formalize due to their subjective nature. Hence, we do not claim to find an optimal explanation, just one closer to the behavior of the original model.