Regularizing Black-box Models for Improved Interpretability
Year: 2019

Abstract:
Most of the work on interpretable machine learning has focused on designing either inherently interpretable models, which typically trade-off accuracy for interpretability, or post-hoc explanation systems, which lack guarantees about their explanation quality. We explore an alternative to these approaches by directly regularizing a black-box model for interpretability at training time. Our approach explicitly connects three key aspects of interpretable machine learning: (i) the model’s inherent interpretability, (ii) the explanation system used at test time, and (iii) the metrics that measure explanation quality. Our regularization results in substantial improvement in terms of the explanation fidelity and stability metrics across a range of datasets and black-box explanation systems while slightly improving accuracy. Finally, we justify theoretically that the benefits of our regularization generalize to unseen points.

heading: 1 Introduction
text: Complex learning-based systems are increasingly shaping our daily lives, and, in order to monitor and understand these systems, we require clear explanations of model behavior. While model interpretability has many definitions and is often largely application specific (Lipton, 2016), local explanations are a popular and powerful tool (Ribeiro et al., 2016). Recent work on local interpretability in machine learning ranges from proposals of new models that are interpretable by-design (e.g., Wang and Rudin, 2015; Caruana et al., 2015) to model-agnostic post-hoc algorithms for interpreting complex, black-box predictors such as ensembles and deep neural networks (e.g., Ribeiro et al., 2016; Lei et al., 2016; Lundberg and Lee, 2017; Selvaraju et al., 2017; Kim et al., 2018). Despite the variety of technical approaches, the underlying goal of all of these works is to develop an interpretable predictive system that produces two outputs: a prediction and its underlying explanation.
Both interpretability by-design and post-hoc explanation strategies have limitations. On one hand, the by-design approaches are restricted to working with model families that provide inherent interpretability, potentially at the cost of accuracy. On the other hand, by performing two disjoint steps, there is no guarantee that post-hoc explainers applied to an arbitrary model will produce explanations of suitable quality. Moreover, recent approaches that claim to overcome this apparent trade-off between prediction accuracy and explanation quality are in fact by-design proposals that impose certain constraints on the underlying model families they consider (e.g., Al-Shedivat et al., 2017; Plumb et al., 2018; AlvarezMelis and Jaakkola, 2018a). In this work, we propose a novel alternative strategy called Explanation-based Optimization (ExpO) that aims to address both of these shortcomings by adding an interpretability regularizer to the loss function of an arbitrary predictive model. We illustrate how ExpO can influence the interpretability and accuracy of a model in Figure 1 (left).
Illustration. Consider a situation where Bob’s loan application is denied by a machine learning system; see the toy illustration in Figure 1 (right). Here, a good local explanation can help Bob understand how to improve his application in order to get the loan. Unfortunately, a standard model, a multi-layer perceptron trained with SGD, is not very interpretable because it has many abrupt changes. Indeed, we can quantitatively measure the local interpretability
of the model using the standard fidelity (Ribeiro et al., 2016; Plumb et al., 2018) and stability (Alvarez-Melis and Jaakkola, 2018a) explanation metrics. To make the learned model more amenable to local explanation, ExpO augments the objective function with fidelity- or stability-based regularizers, effectively controlling the degree of local explainability.
The specific contributions of our work are as follows:
1. Interpretability regularizers. We introduce two interpretability regularizers associated with the fidelity and stability explanation metrics. The first, ExpO-Fidelity, is designed for semantic features and explainers that directly make predictions, such as those in Ribeiro et al. (2016); Lundberg and Lee (2017); Plumb et al. (2018). The second, ExpO-Stability, is tailored for non-semantic features (e.g., pixels) and explainers that identify features that are influential on a prediction, such as saliency maps (Simonyan et al., 2013). Both regularizers are differentiable and can be used to augment the objective function of an arbitrary model. In Section 3.1, we discuss how they differ from the classical approaches for local approximation and function smoothing.
2. Generalizable explanation quality. We analyze the properties of the explanation quality metrics and show that the benefits of our regularization generalize to unseen points. Specifically, we derive a bound on the gap between the fidelity of explanations on training and held out points and connect it with the local variance of the learned model.
Empirical results. We evaluate models trained with and without our regularizers on a variety of regression and classification tasks with semantic and image features.1 Empirically, they slightly improve predictive performance across the nine datasets we consider (seven UCI regression tasks, a medical classification task, and MNIST). From an interpretability perspective, our results demonstrate significant improvement in terms of explanation quality as measured by the fidelity and stability metrics. In particular, our regularizers improved explanation fidelity by at least 25% on the UCI datasets and on the medical classification task while stability on MNIST was improved by orders of magnitude. Additionally, we found, qualitatively, that our regularizers produce models with simpler and more comprehensible explanations. In summary, black-box explanation systems work better on models trained with ExpO and, as an additional benefit, those models tend to be more accurate.

heading: 2 Background and Related Work
text: Consider a supervised learning problem, where our goal is to estimate a model, f : X 7→ Y, f ∈ F , that maps input feature vectors, x ∈ X , to targets, y ∈ Y, and is trained using data, {xi, yi}Ni=1. If the class of functions used for modeling the data is complex, we can
1 The code for our regularizers and all experiments is at: https://github.com/ForReview11235/CodeForICLR2020
understand the behavior of f in some neighborhood, Nx ∈ P [X ] (where P [X ] is the space of probability distributions over X ), by generating a local explanation. We denote algorithms that produce explanations (i.e., explainers) as e : X × F 7→ E , where E is the set of possible explanations. The choice of E generally depends on whether or not X consists of semantic features, and will be defined more precisely next.

heading: 2.1 Semantic Features
text: We call features semantic if people can reason about them and understand what it means when their values change (e.g., a person’s income, the concentration of a chemical, etc.). Consequently, local explanations try to predict how the model’s output would change if the input was perturbed (Ribeiro et al., 2016; Lundberg and Lee, 2017; Plumb et al., 2018). Thus, we can define the output space of the explainer as Es := {g ∈ G | g : X 7→ Y}, where G is a class of interpretable (typically linear) functions.
Fidelity metric. When the explainer’s output space is Es, the explanation is defined as a function g : X 7→ Y, and it is natural to evaluate how accurately g models f in a neighborhood Nx (Ribeiro et al., 2016; Plumb et al., 2018):
F (f, g,Nx) := Ex′∼Nx [(g(x′)− f(x′)) 2 ], (1)
which we refer to as the neighborhood-fidelity (NF) metric. This metric is sometimes evaluated with Nx as a point mass on x and we call this version the point-fidelity (PF) metric. While Plumb et al. (2018) argued that point-fidelity can be misleading because it does not measure generalization of e(x, f) across Nx, it has been used for evaluation in the prior work (Ribeiro et al., 2016; Lundberg and Lee, 2017; Ribeiro et al., 2018) and we report it in our experiments along with the neighborhood-fidelity for completeness.
Black-box explanation systems. Various explainers have been proposed to generate local explanations of the form g : X 7→ Y, typically assuming that g is linear. In particular, LIME (Ribeiro et al., 2016), one of the most popular black-box explanation systems2, solves the following optimization problem:
e(x, f) := arg min g∈Es F (f, g,Nx) + Ω(g), (2)
where Ω(e) stands for an additive regularizer that encourages certain desirable properties of the explanations (e.g., sparsity). LIME’s objective function is closely related to the fidelity metric and subsequently to our proposed ExpO-Fidelity regularizer. Consequently, we expect our regularizer to improve the quality of LIME-generated explanations. Our experimental results in Section 4.1 corroborate this hypothesis.
Along with LIME, we consider another black-box explanation tool, called MAPLE (Plumb et al., 2018). It differs substantially from LIME in that its neighborhood function is learned from the data rather than specified as a parameter. In our experiments, we evaluate the quality of MAPLE-generated local explanations for models regularized via ExpO-Fidelity, but do not use MAPLE’s learned neighborhood function to define ExpO-Fidelity. We view this as a good test case to see how optimizing the fidelity metric for one neighborhood generalizes to another one (see Section 3 for a more detailed discussion of this point). In Section 4.1, we see that regularizing for LIME neighborhoods improves MAPLE’s explanation quality.

heading: 2.2 Non-Semantic Features
text: Non-semantic features lack an inherent interpretation, with images being a canonical example. When X consists of non-semantic inputs, we cannot assign meaning to the difference between x and x′, hence it does not make sense to explain the difference between the predictions f(x) and f(x′). As a result, fidelity is not an appropriate explanation metric. Instead, in this
2SHAP (Lundberg and Lee, 2017) is another popular method that proposes a theoreticallymotivated neighborhood sampling function, but requires explanations to be linear models that act on binary features. This requirement is too limiting in our case.
context, local explanations try to identify which parts of the input are particularly influential on a prediction (Sundararajan et al., 2017). Consequently, we consider explanations of the form Ens := Rd, where d is the number of features in X .
Stability metric and saliency maps. When the explainer’s output space is Ens, the explanation is a vector in Rd, and cannot be directly compared to the underlying model itself, as in the case of the fidelity metric. Instead, the focus in this setting is on the degree to which the explanation changes between points in a local neighborhood, which we measure using the stability metric (Alvarez-Melis and Jaakkola, 2018a):
S(f, e,Nx) := Ex′∼Nx [||e(x, f)− e(x′, f)||22] (3) Various explainers (Sundararajan et al., 2017; Zeiler and Fergus, 2014; Shrikumar et al., 2016; Smilkov et al., 2017; Adebayo et al., 2018) have been proposed to generate local explanations in Ens, with saliency maps (Simonyan et al., 2013) being the approach that we consider in this work. Saliency maps assign importance weights to image pixels based on the magnitude of the gradient of the predicted class with respect to the corresponding pixels.
Recent work on model interpretability emphasizes that more stable explanations tend to be more trustworthy (Alvarez-Melis and Jaakkola, 2018a; Ghorbani et al., 2017; Alvarez-Melis and Jaakkola, 2018b). Note that the stability metric can also be considered in the context of semantic features in addition to the fidelity metric.

heading: 2.3 Related Methods
text: A few recently proposed approaches to model interpretability are closely related to our work. First, self-explaining neural networks (SENN) (Alvarez-Melis and Jaakkola, 2018a) (a variation of contextual explanation networks (Al-Shedivat et al., 2017)) is an interpretable by-design approach that additionally (indirectly) optimizes their models to produce stable explanations. Second, “Right For The Right Reasons” (RTFR) (Ross et al., 2017) selectively penalizes gradients of the output with respect to certain input features at some points to discourage their use by the model. Finally, a work concurrent with ours (Lee et al., 2019), which expanded on (Lee et al., 2018), proposed to regularize models of structured data to encourage explainability in a way that is similar to ExpO but differs substantially in how the the target explanation for the regularizer is defined and in how the final objective function is optimized.
From a technical standpoint, SENN and RTFR both assume that the local explanation is close to the first order Taylor approximation of the model at that point. In Section 3.1, we demonstrate how Taylor approximations are often quite different from and more difficult to use than the neighborhood-based local explanations that we use in ExpO. Further, SENN’s regularizer requires the neural network to have a very particular structure and, therefore, unlike ExpO, cannot by applied to an arbitrary model. While RTFR’s regularization can be used with arbitrary models, it is not directly related to a measure of explanation quality and is defined using specific domain knowledge; on the other hand, ExpO aims to directly improve quality of explanations with respect to a specific metric and does not require domain knowledge. In the Appendix A.1, we compare ExpO to simple l1 and l2 regularization since other baselines are either model specific or require domain knowledge. We found that they do not significantly impact model interpretability.

heading: 3 Explanation Optimization
text: Running black-box explainers on arbitrary models does not guarantee the quality of the resulting explanations. To address this, we define regularizers that can be added to the loss function and used to train an arbitrary model f . Specifically, we want to solve the following optimization problem:
f̂ := arg min f∈F
1
N N∑ i=1 (L(f, xi, yi) + γR(f,N regxi )) (4)
where L(f, xi, yi) is a standard predictive loss (e.g., squared error for regression or crossentropy for classification), R(f,N regxi ) is a regularizer that encourages explainability of f in the neighborhood of xi, and γ > 0 controls the regularization strength. Because our regularizers are differentiable, we can solve Equation 4 using any standard gradient-based algorithm; in our case, SGD with Adam.
Algorithm 1 ExpO-Fidelity input fθ, x, N reg x , m
1: Sample: x′1, . . . , x ′ m ∼ N reg x 2: Compute predictions: ŷj(θ) = fθ(x ′ j) for j = 1, . . . ,m 3: Produce a linear explanation:
βx(θ) = argminβ m∑ j=1 (ŷj(θ)−β>x′j) 2
output 1m ∑m j=1(ŷj(θ)− βx(θ) >x′j) 2
Algorithm 2 ExpO-Stability input fθ, x, N reg x , m
1: Sample: x′1, . . . , x ′ m ∼ N reg x 2: Compute predictions: ŷj(θ) = fθ(x ′ j), for j = 1, . . . ,m
output 1m ∑m j=1(ŷj(θ)− fθ(x)) 2
We define R(f,N regx ) based on either the neighborhoodfidelity, Eq. (1), or the neighborhood-stability, Eq. (3). In order to compute these metrics exactly, we would need to run an explainer algorithm, e; this may be nondifferentiable or too computationally expensive to use as a regularizer. Thus, for ExpO-Fidelity, we approximate e using a local linear model fit on points sampled from Nregx (Algorithm 1). For ExpO-Stability, we simply require that the model’s output not change too much across Nregx (Algorithm 2).3
Choosing the neighborhood. Defining a good regularization neighborhood, requires considering the following. On one hand, we would like N regx to be similar to Nx, as used in Eq. 1 or Eq. 3, so that the neighborhoods used for regularization and for evaluation match. On the other hand, we also would like N regx to be consistent with the ‘local neighborhood’ defined by e internally, which may differ from Nx. For LIME, this is not a problem since the internal definition of the ‘local neighborhood’ is a hyperparameter that we can set. However for MAPLE, the ‘local neighborhood’ is learned from the data, and hence the regularization and explanation neighborhoods may differ. Ultimately, we left resolving this tension to future work.
Computational cost. Algorithm 1 could be prohibitively expensive since the number of samples, m, from Nregx , has to be proportional to the dimension of x, d, resulting in O(d
3) evaluations of f to compute the regularizer at x. So we also test a randomized version of Algorithm 1, ExpO-1D-Fidelity, that randomly selects one dimension of x to perturb according to Nregx and penalizes the error of a local linear model along that dimension. This breaks the dependence of the computational cost of the regularizer on d and allows us to compute each gradient step with a O(1) increase in the number of evaluations of f .

heading: 3.1 Understanding the Properties of ExpO
text: The goal of this section is to compare the behavior of local linear explanations and our regularizers to some existing theoretical function approximations and measures of variance to help develop an intuitive understanding of ExpO. First, we compare neighborhood-based local linear explanations to first order Taylor approximations to show that they can have fundamentally very different behaviors. Second, we compare ExpO-Fidelity to the Lipchitz Constant (LC) and Total Variation (TV) of the learned function.
Local explanations vs. Taylor approximations. A natural question to ask is, Why should we sample from Nx in order to locally approximate f when there are easier and theoretically motivated approximations? One possible way to do this is via the Taylor approximation (Alvarez-Melis and Jaakkola, 2018a). The downside of a Taylor approximationbased approach is that such an approximation cannot readily be adjusted to different neighborhood scales and its fidelity and stability strictly depend on the learned function. This can be seen in Figure 2 (left) where the Taylor approximations at two nearby points are both radically different and not faithful to the model outside of an small neighborhood.
Fidelity regularization and the model’s LC or TV. From a theoretical perspective, our regularizer is similar to controlling the Lipschitz Constant or Total Variation of f across Nx after removing the part of f explained by e(x, f). From an interpretability perspective, there is nothing inherently wrong with having a large LC or TV, which is demonstrated in
3A similar procedure was explored previously in (Zheng et al., 2016) for adversarial robustness.
Figure 2 (right). However, once we take into account what can be explained by e(x, f), then upper bounding any one of ExpO-Fidelity, the LC, or the TV will upper bound the others.

heading: 3.2 Generalization of Local Linear Explanations
text: To conclude our analysis, we study the quality of local linear explanations in terms of generalization. Note that ExpO regularization encourages learning models that are explainable in the neighborhoods of each training point. However, how would this property generalize to unseen points? We answer this question by providing a generalization bound in terms of neighborhood-fidelity metric for local linear explanations (see Appendix A.2 for derivations).
Proposition 1 Let the neighborhood sampling function Nx be characterized by some parameter σ ( e.g., the effective radius of a neighborhood) and the variance of the trained model f(x) across all such neighborhoods be bounded by some constant C(σ) > 0. Then, the following bound holds with at least 1− δ probability:
E [r(f, x)] ≤ 1 n n∑ i=1 r(f, xi) +
√ C2(σ) log 1δ
2n (5)
Remark 2 The obtained bound tells us that explainable models with smaller local variances across the neighborhoods are likely to have explanations of higher fidelity on the held out points. This further motivates the approximation we used in Algorithm 2.
4 Experimental Results
In our first set of experiments, we demonstrate the effectiveness of ExpO-Fidelity and ExpO-1D-Fidelity on datasets with semantic features using seven regression problems from the UCI collection (Dheeru and Karra Taniskidou, 2017) as well as an in-hospital mortality classification problem. Dataset statistics are in Table 1. Our second experiment demonstrates the effectiveness of ExpO-Stability for creating saliency maps (Simonyan et al., 2013) on MNIST (LeCun, 1998). We found that a model trained with our regularizers is more interpretable than a model trained without them because black-box explainers pro-
duce quantitatively better explanations for them; further, they are often more accurate. Finally, we demonstrate qualitatively that the explanations for the regularized model tend to be simpler.

heading: 4.1 Neighborhood-Fidelity Regularization
text: We compare models trained with our regularizers to models trained without them. We report accuracy and three interpretability metrics: Point-Fidelity (PF), Neighborhood-Fidelity (NF), and Stability (S). The interpretability metrics are evaluated for two black-box explanation systems: LIME and MAPLE. Consequently, the “MAPLE-PF” label corresponds to the Point-Fidelity Metric for explanations produced by MAPLE.
Experimental setup. All of the inputs to the model were standardized to have mean zero and variance one (including the response variable for regression problems). The network architectures and hyper-parameters were chosen using a simple grid search. For the final results, we set Nx to be N (x, σ) with σ = 0.1 and Nregx to be N (x, σ) with σ = 0.5. In the Appendix A.3, we discuss how these values were chosen.
UCI regression experiments. The effects of ExpO-Fidelity and ExpO-1D-Fidelity on model accuracy and interpretability are in Table 3. ExpO-Fidelity frequently improved the interpretability metrics by over 50%, with the smallest improvements being around 25%. Further, it lowered the prediction error on the ‘communities’, ‘day’, and ‘MSD’ datasets, which lets us conclude that it has a small positive effect on accuracy as well. ExpO-1D-Fidelity generally had a similar effect on the interpretability metrics.
We ran experiments on the ‘MSD’ dataset4 to understand the scalability of ExpO to larger tasks. On this dataset, evaluating the interpretability metrics using MAPLE was fairly slow, and hence we only evaluate them using LIME on the first 1000 testing points. Both ExpO-Fidelity and ExpO-1D-Fidelity improved LIME’s interpretability metrics by at least 50% and both improved the model accuracy.
Medical classification experiments. The ‘support2’ dataset5 is used for in-hospital mortality prediction. Because the output layer of our models is the softmax over logits for two classes, we run each explanation system on each of the individual logits. Table 4 presents the results. We observe that ExpO-Fidelity improved the interpretability metrics by 50% or more. ExpO-1D-Fidelity slightly decreased accuracy and improved the interpretability metrics by at least 25%.
A qualitative example on the UCI ‘housing’ dataset. While we have demonstrated quantitatively that black-box explainers produce better explanations for ExpO-regularized models, here we qualitatively analyze the changes in the explanations. More examples, that show similar effects, are available in the Appendix A.4.
Consider the UCI ‘housing’ dataset, a regression problem to predict housing prices in the Boston area. After sampling a random point x, we use LIME to generate a local linear explanation at this point for a model trained without regularization (“unregularized
explanation”) and for a model trained with ExpO-1D-Fidelity (“regularized explanation”). The unregularized and regularized explanations are shown in Table 2.
Quantitatively, using ExpO-1D-Fidelity decreased the LIME-NF metric from 1.15 to 0.02; i.e. ExpO produced a model that is much more accurately modeled by the explanation around x. Note that the regularized explanation has fewer significant coefficient (those with absolute value greater than 0.1), and hence it is simpler as the effect is attributed to fewer features.
4The task is to predict release year of song from a set of acoustic features, treated as a regression problem as in Bloniarz et al. (2016)
5http://biostat.mc.vanderbilt.edu/wiki/Main/SupportDesc.

heading: 4.2 Stability Regularization
text: For this experiment, we compared a normally trained convolutional neural network on MNIST to one trained using ExpO-Stability. Then, we evaluated the quality of saliency map explanations for these models. Both Nx and N reg x where defined as Unif(x− 0.05, x+ 0.05). Both the normally trained model and model traiend with ExpO-Stability achieved the same accuracy of 99%. This demonstrates one of the practical differences between SENN and ExpO: SENN places strict structural constraints on the network and subsequently lowers the testing accuracy to roughly 97%. Quantitatively, training the model with ExpO-Stability decreased the stability metric from 6.94 to 0.0008. Qualitatively, training the model with ExpO-Stability made the resulting saliency maps look much better by focusing them on the presence or absence of certain pen strokes (Figure 3).

heading: 5 Conclusion
text: In this work, we have introduced the novel idea of directly regularizing arbitrary models to be more interpretable with respect to a general metric. We contrasted our regularizers to classical approaches for function approximation and smoothing and provided a generalization bound for them. We demonstrated, across a variety of problem settings and explainers, that our regularizers slightly improve model accuracy and improve the interpretability metrics by somewhere from 25% to orders of magnitude. We believe that potential future work may focus on three areas: (1) exploring alternative neighborhood functions, Nregx , that match those used by other black-box explanation systems, (2) exploring how to regularize for non-local interpretability metrics, and finally (3) exploring the interaction between the regularizers and the optimization process, e.g., progressively changing the importance of the regularization during training or using the regularization as an additional training step.

heading: A Appendix
text: A.1 Comparison of EXPO to Baseline Methods
Although there are related methods to ExpO, none are necessarily appropriate to act as a baseline for comparison:
• SENN (Alvarez-Melis and Jaakkola, 2018a) requires that the model has a specific structure. ExpO makes no assumptions about the model’s structure.
• RTFR (Ross et al., 2017) requires that we have the domain knowledge to specify that “Feature ‘i’ should not be relevant to the prediction for point ‘x’ ”. ExpO does not require this or any other domain knowledge.
• Finally, the regularizers defined by (Lee et al., 2019) are designed for structured data types. ExpO is designed to work with semantic features or images, so there isn’t a common experiment that we could run.
As a result, we consider two standard regularization techniques: l2 and l1 regularization. These regularizers may make the network smoother or simpler (due to sparser weights), which may make it more amenable to local explanation. The results of this experiment are in Table 5; notice that neither of these regularizers had a significant effect on the interpretability metrics compared to ExpO.
A.2 Details on the Generalization of Local Linear Explanations
Here, we provide a derivation of the bound (5) on the explanation fidelity. First, we assume that local linear explanations, βx, are obtained by solving the ordinary least squares regression problem (as given in Algorithm 1):
βx = [ X ′X ′> ]−1 X ′f(X ′), (6)
where each column of X ′ denotes a sample from the neighborhood Nx and f(X ′) is a column-vector of the corresponding function values. The expected fidelity of the explanation βx can be computed analytically:
r(f, x) = ENx [ f(x′)2 ] − ENx [f(x′)x′] > ENx [ [x′x′>] ]−1 ENx [f(x′)x′] (7) where expectation ENx [·] is taken with respect to x′ over the neighborhood Nx. Note the equality in (7) is the expected value of the squared residual between f(x) and the
optimal local linear explanation, which is upper-bounded by the variance of the model in the corresponding neighborhood:
0 ≤ r(f, x) ≤ ENx [ f(x′)2 ] − ENx [f(x′)] 2 = VarNx [f(x ′)] (8)
For instance, if f(x) is L-Lipschitz and the neighborhood Nx is defined a uniform distribution within a σ-ball centered at x, then the variance of f(x) within the neighborhood can be further bounded by 4L2σ2, hence r(f, x) ≤ 4L2σ2. For the explanations to generalize, we would like to make sure that the gap between the average fidelity on the training set and the expected fidelity is small with high probability. More formally, the following inequality should hold:
P ( E [r(f, x)]− 1
n n∑ i=1 r(f, xi) > ε
) < δn(ε) (9)
The following is a restatement of Proposition 1 with a short proof.
Proposition 3 Let the neighborhood sampling function Nx be characterized by some parameter σ ( e.g., the effective radius of a neighborhood) and the variance of the trained model f(x) across all such neighborhoods be bounded by some constant C(σ) > 0. Then, the following bound holds with at least 1− δ probability:
E [r(f, x)] ≤ 1 n n∑ i=1 r(f, xi) +
√ C2(σ) log 1δ
2n
Proof. By assumption, the variance of the model f(x) is bounded in each local neighborhood specified by Nx. Then (7) implies that each residual is bounded as 0 ≤ r(f, x) ≤ C(σ). Applying Hoeffding’s inequality, we get:
P ( E [r(f, x)]− 1
n n∑ i=1 r(f, xi) > ε
) < exp {−2nε2 C2(σ) } Inverting the inequality gives us the bound.
A.3 Choosing σ for Nx and N reg x
In Figure 4, we see that the choice of σ for Nx was not critical (the value of LIME-NF only increased slightly with σ) and that this choice of σ for Nregx produced slightly more accurate and interpretable models.
A.4 More Examples of EXPO’s Effects
Here, we demonstrate the effects of ExpO-Fidelity on more examples from the UCI ‘housing’ dataset (Table 6). Observe that the same general trends hold true:
• The regularized explanation more accurately reflects the model (LIME-NF metric) • The regularized explanation generally considers fewer features to be relevant. Again,
a feature is ‘significant’ if its absolute values is 0.1 or greater.
• Neither model appears to be heavily influenced by CRIM or INDUS. The regularized model generally relies more on LSTAT and less on DIS, RAD, and TAX to make its predictions.
The same comparison for examples from the UCI ‘winequality-red’ are in Table 7. We can see that the regularized model depends more on “volatile acidity” and less on “sulphates” while usually agreeing about the effect of “alcohol”. Further, it is better explained by those explanations than the unregularized model.

Review summaries:
The paper considers the problem of training black box models for improved interpretability, and  proposes to penalize black-box models at training time using two regularizers that correspond to fidelity and stability explanation metrics. As computing the regularizers exactly is computationally intensive they propose two approximating algorithm. In addition, as the one for fidelity is still prohibitive, a randomized variant is proposed. Connections are established between the regularizers and the model's Lipschitz constant or total variation. A generalization bound is presented for local linear explanations. The proposed approach is evaluated on a variety of datasets.