RL-LIM: REINFORCEMENT LEARNING-BASED LOCALLY INTERPRETABLE MODELING
Year: 2019

Abstract:
Understanding black-box machine learning models is important towards their widespread adoption. However, developing globally interpretable models that explain the behavior of the entire model is challenging. An alternative approach is to explain black-box models through explaining individual prediction using a locally interpretable model. In this paper, we propose a novel method for locally interpretable modeling – Reinforcement Learning-based Locally Interpretable Modeling (RL-LIM). RL-LIM employs reinforcement learning to select a small number of samples and distill the black-box model prediction into a low-capacity locally interpretable model. Training is guided with a reward that is obtained directly by measuring agreement of the predictions from the locally interpretable model with the black-box model. RL-LIM near-matches the overall prediction performance of black-box models while yielding human-like interpretability, and significantly outperforms state of the art locally interpretable models in terms of overall prediction performance and fidelity.

heading: 1 INTRODUCTION
text: Artificial Intelligence (AI) is advancing at a rapid pace, particularly with recent advances in deep neural networks and ensemble methods (Goodfellow et al., 2016; He et al., 2016; Chen & Guestrin, 2016; Ke et al., 2017). This progress has been fueled by ‘black-box’ machine learning models where the decision making is controlled by complex non-linear interactions between many parameters that are difficult for humans to understand and interpret. However, in many real-world applications AI systems are not only expected to perform well but are also required to be interpretable: doctors need to understand why a particular treatment is recommended, and financial institutions need to understand why a loan was declined. Use cases of model interpretability vary across applications: it can provide trust to users by showing rationales behind decisions, enable detection of systematic failure cases, and provide actionable feedback for improving models (Rudin, 2018).
Many studies have suggested a trade-off between performance and interpretability (Virág & Nyitrai, 2014; Johansson et al., 2011). This is correct in that globally interpretable models, which attempt to explain the entire model behavior, typically yield considerably worse performance than ‘blackbox’ models (Lipton, 2016). To go beyond the performance limitations of globally interpretable models, another promising direction is locally interpretable models, which instead of explaining the entire model explain a single prediction (Ribeiro et al., 2016). Methodologically, while a globally interpretable model fits a single inherently interpretable model (such as a linear model or a shallow decision tree) to the entire training set, locally interpretable models aim to fit an inherently interpretable model locally, i.e. for each instance individually, by distilling knowledge from a high performance black-box model. Such locally interpretable models are very useful for real-world AI deployments to provide succinct and human-like explanations to users. They can be used to identify systematic failure cases (e.g. by seeking common trends in input dependence for failure cases), detect biases (e.g. by quantifying feature importance for a particular variable), and provide actionable feedback to improve a model (e.g. understand failure cases and what training data to collect).
To be useful in practice, locally interpretable models need to maximize two objectives: (i) the overall prediction performance (how well it predicts compared to the ground truth labels) – for the model to be accurate, and (ii) fidelity (how well it approximates the ‘black-box’ model predictions) – to ensure the model is reliably approximating the black-box model’s predictions in the neighborhood
of interest (Plumb et al., 2019; Lakkaraju et al., 2019). To this end, a few methods have recently been proposed for locally interpretable modeling: Local Interpretable Model-agnostic Explanations (LIME) (Ribeiro et al., 2016), Supervised Local modeling methods (SILO) (Bloniarz et al., 2016), and Model Agnostic Supervised Local Explanations (MAPLE) (Plumb et al., 2018). LIME in particular has gained notable popularity and has been deployed in many applications due to its simplicity. However, the overall prediction performance and fidelity metrics are not reaching desired levels in many cases (Alvarez-Melis & Jaakkola, 2018; Zhang et al., 2019; Ribeiro et al., 2018; Lakkaraju et al., 2017). Indeed, as we show in our experiments, there are frequent cases where existing locally interpretable models even underperform commonly low-performing globally interpretable models.
One of the fundamental challenges to fit a locally interpretable model is the representational capacity difference while applying distillation. Black-box machine learning models, such as deep neural networks or ensemble models, have much larger representational capacity than locally interpretable models. This can result in underfitting with conventional distillation techniques, leading to suboptimal performance (Hinton et al., 2015; Wang et al., 2019). We address this fundamental challenge by proposing a novel Reinforcement Learning-based method to fit Locally Interpretable Models which we call RL-LIM. RL-LIM efficiently utilizes the small representational capacity of locally interpretable models by training with a small number of samples that are determined to have the highest value contribution to the fitting of a locally interpretable model. In order to select these highest-value instances, we train instance-wise weight estimators (modeled with deep neural networks) using a reinforcement signal that quantifies the fidelity metric (i.e. how well does the model approximate the black-box model predictions). The contributions of this paper can be summarized as:
1. We introduce the first method that tackles interpretability through data-weighted training, and show that reinforcement learning is highly effective for end-to-end training of such a model. 2. We show that distillation of a black-box model into a low-capacity interpretable model can be significantly improved by fitting with a small subset of relevant samples that is controlled efficiently by our method. 3. On various classification and regression datasets, we demonstrate that RL-LIM significantly outperforms alternative models (LIME, SILO and MAPLE) in overall prediction performance and fidelity metrics – in most cases, the overall performance of locally interpretable models obtained by RL-LIM is very similar to complex black-box models.

heading: 2 RELATED WORK
text: Locally interpretable models: There are various approaches to interpret black-box models – (Gilpin et al., 2018) provides a good overview. One approach is to directly decompose the prediction into feature attributions by considering what-if cases. Shapley values (Štrumbelj & Kononenko, 2014) and their computationally-efficient variants (Lundberg & Lee, 2017) are commonly-used methods in this category. Other notable methods are based on activation differences, e.g. DeepLIFT (Shrikumar et al., 2017), or saliency maps using the gradient flows, e.g. CAM (Zhou et al., 2016) and Grad-CAM (Selvaraju et al., 2017). In this paper, we focus on the direction of locally interpretable modeling – distilling a black-box model into an interpretable model for each input instance.
Locally Interpretable Model-agnostic Explanation (LIME) (Ribeiro et al., 2016) is the most popular method for locally interpretable modeling. LIME is based on modifying a data instance by tweaking the feature values and then learning from the impact of the modifications on the output. A fundamental challenge for LIME is the need for a meaningful distance metric to determine neighborhoods, as simple metrics like Euclidean distance may yield poor fidelity in some cases and the estimation can be highly-sensitive to normalization (Alvarez-Melis & Jaakkola, 2018) especially with categorical variables. Supervised Local modeling methods (SILO) (Bloniarz et al., 2016)) aims to improve LIME by determining the neighborhoods for each instance using ad-hoc tree-based ensemble methods. Model Agnostic Supervised Local Explanations (MAPLE) (Plumb et al., 2018) furthers adds a method for feature selection on top of SILO – it utilizes ad-hoc tree-based ensemble methods to determine the weights of training instances for each target instance and uses the weights to optimize a locally interpretable model. However, SILO and MAPLE still have shortcomings because the tree-based ensemble methods are optimized independently from the locally interpretable model – lack of joint optimization results in suboptimal fidelity for the locally interpretable model. Overall, to construct a locally interpretable model, a key problem is how to select the optimal training
instances for each testing instance, because the selected training instances mostly determine the constructed locally interpretable model. The number of possibilities for training instance selection is extremely large (exponential in the number of training instances). LIME heuristically utilizes Euclidean distances, whereas SILO and MAPLE use ad-hoc tree-based ensemble methods. Our proposed method, RL-LIM, takes a very different perspective: to properly and efficiently explore the large possible solution space, RL-LIM utilizes reinforcement learning to find the optimal policy that selects the training instances that maximize the fidelity of the locally interpretable model.
Data-weighted training: Optimal weighing of training data is a paramount problem in machine learning. By upweighting valuable instances and downweighting the low quality or problematic instances, better performance can be obtained in certain learning scenarios, such as imbalanced or noisy labels (Jiang et al., 2018). One approach for data weighting is utilizing Influence Functions (Koh & Liang, 2017), that are based on oracle access to gradients and Hessian-vector products. Jointly-trained student-teacher methods constitute another approach (Jiang et al., 2018; Bengio et al., 2009) to learn a data-driven curriculum. Using the feedback from the teacher network, training instance-wise weights are learned for the student model. Aligned with our motivations, meta learning is considered for data weighting in Ren et al. (2018). Their proposed method utilizes gradient descent-based meta learning, guided by a small validation set, to maximize the target performance.
In this work we consider data-weighted training for a novel purpose: interpretability. Unlike gradient descent-based meta learning, our approach uses reinforcement learning to integrate the reward directly with the fidelity metric. Aforementioned works estimate the same ranking of training instances for the entire dataset. Instead, our method yields an instance-wise ranking of training data points, different for each testing instance. This enables efficient distillation of a black-box model prediction into a locally interpretable model.

heading: 3 REINFORCEMENT LEARNING-BASED MODELING
text: We consider a training dataset D = {(xi, yi), i = 1, ..., N} ∼ P for training of a black-box model f , where xi ∈ X is the feature vector in a d-dimensional feature space X and yi ∈ Y is the corresponding label in a label space Y . We also assume that there exists a probe dataset Dp = {(xpj , y p j ), j = 1, ...,M} ∼ P where M is the number of probe instances. The probe dataset is used to evaluate the model performance to guide meta-learning as in Ren et al. (2018). If there is no explicit probe dataset, we can randomly partition a subset of the training dataset as the probe dataset and the remainder as the training dataset. RL-LIM is composed of three models:
1. Black-box model f : X → Y – any machine learning model that needs to be explained (e.g. a deep neural network or a decision tree-based ensemble model),
2. Locally interpretable model gθ : X → Y – an inherently interpretable model by design (e.g. a linear model or a shallow decision tree),
3. Instance-wise weight estimation model hφ : X × X × Y → [0, 1] – a function that outputs the instance-wise weights to fit the locally interpretable model. It uses concatenation of a probe feature, a training feature, and a corresponding black-box model prediction on the training feature as its inputs. It can be a complex machine learning model – e.g. here a deep neural network.
Our objective is to construct an accurate locally interpretable model gθ such that the predictions made by it are similar to the predictions of the given black-box model f∗ – i.e. the locally interpretable model has high fidelity. We use a loss function, L : Y × Y → R to quantify the fidelity of the locally interpretable model (e.g. mean absolute error, lower the better). In RL-LIM, the three necessary components of an RL framework are as follows: the state is the vector of input features, the action is the selection vector, and the reward is the fidelity which depends on the input features and the selection vector. The instance-wise weight estimator model is the agent that outputs the actions based on the state (input features). The environment is comprised of the input feature generating process, as well as the black-box model for the target task.
The representational capacity difference between the black-box model and the locally interpretable model is the bottleneck we aim to address. Ideally, to avoid underfitting, locally interpretable models should be learned with a minimal number of training instances that are most effective in capturing the model behavior. We propose an instance-wise weight estimation model hφ to estimate the probabil-
ities of training instances that should be used for fitting the locally interpretable model. Integrating with the accurate locally interpretable modeling goal, we propose the following objective:
min hφ
Exp∼PX [ L(f∗(xp), g∗θ(xp)(x p)) ] + λExp,x∼PX [ hφ(xp, x, f∗(x)) ] s.t. g∗θ(xp) = argmingθ Ex∼PX [ hφ(xp, x, f∗(x))× Lg(f∗(x), gθ(x))
] (1) where λ ≥ 0 is a hyper-parameter that controls the number of training instances used to fit the locally interpretable model (we study the impact of performance on λ in Section 4.2), and hφ(xp, x, f∗(x)) represents the instance-wise weight for each training pair (x, f∗(x)) for the probe data xp. Lg is the loss function to fit the locally interpretable model, for which we use the mean squared error between predicted values for regression and logits for classification. φ and θ are the trainable parameters, whereas f∗ (the pre-trained black-box model) is fixed.
The first term in the objective function Exp∼PX [ L(f∗(xp), g∗θ(xp)(x p)) ]
represents the local prediction differences between black-box model and locally interpretable model (referred to as fidelity metric). The second term in the objective function Exp,x∼PX [ hφ(xp, x, f∗(x)) ] represents the expected number of selected training points to fit the locally interpretable model. Lastly, the constraint ensures that the locally interpretable model is derived from weighted loss function, where weights are the output of the instance-wise weight estimator hφ. Our formulation does not assume any constraint on gθ – it could be any inherently interpretable model suitable for the data type of interest. Next, we describe how Eq. (1) can be efficiently addressed with reinforcement learning.

heading: 3.1 TRAINING AND INFERENCE
text: The RL-LIM method, shown in Fig. 1, can be thought of as encompassing 5 stages:
• Stage 0 – Black-box model training: This stage is the preliminary stage for RL-LIM. Given the training set D, the black-box model f is trained to minimize a loss function (Lf ) (e.g. mean squared error for regression or cross-entropy for classification), i.e., f∗ = argminf 1 N ∑N i=1 Lf (f(xi), yi). If the pre-trained black-box model is already saved, we can
skip this stage and retrieve the given pre-trained black-box model to f∗.
• Stage 1 – Auxiliary dataset construction: Using the pre-trained black-box model f∗, we create auxiliary training and probe datasets, as D̂ = {(xi, ŷi), i = 1, ..., N} (where ŷi = f∗(xi)) and D̂p = {(xpj , ŷ p j ), j = 1, ...,M} (where ŷ p j = f
∗(xpj )), respectively. These auxiliary datasets (D̂, D̂p) are used for instance-wise weight estimation models and locally interpretable model training.
• Stage 2 – Interpretable baseline training: To improve the stability of the instance-wise weight estimator training, a baseline model is observed to be beneficial. As the baseline model gb : X → Y , we use a globally interpretable model (such as a linear model or shallow decision tree) optimized to replicate the predictions of the black-box model: g∗b = argming 1 N ∑N i=1 L(g(xi), ŷi).
• Stage 3 – Instance-wise weight estimator training: We train an instance-wise weight estimator using the auxiliary datasets (D̂, D̂p). To encourage exploration, we consider probabilistic selection, with a sampler block that is based on the output of the instance-wise weight estimator – hφ(xpj , xi, ŷi) represents the probability that (xi, ŷi) is selected to train locally interpretable model for the probe instance xpj . Let the binary vector c(x p j ) ∈ {0, 1}N represent the selection opera-
tion, such that (xi, ŷi) is selected for training locally interpretable model for xpj when ci(x p j ) = 1. Correspondingly, ρφ(xp) is the probability mass function for c(xpj ) given hφ(·):
ρφ(xpj , c(x p j )) = N∏ i=1 [ hφ(xpj , xi, f ∗(xi))ci(x p j ) · (1− hφ(xpj , xi, f ∗(xi)))1−ci(x p j ) ]
As the original form of the optimization problem in Eq. (1) is intractable due to the expectation operations, we employ approximations:
– The sample mean is used as an approximation of the first term of the objective function as 1 M ∑M j=1 L(f∗(x p j ), g ∗ θ(xpj ) (xpj ))). – The second term of the objective, which represents the average selection probability, is approximated as the number of selected instances (divided by N ) to have ||c(xpj )||1 = 1 N ∑N i=1 |ci(x p j )|. – The constraint term is approximated using the sample mean of the training loss as g∗ θ(xpj ) =
argmingθ 1 N ∑N i=1 [ ci(xpj ) · Lg(f∗(xi), gθ(xi)) ] .
The sampler block yields a non-differential objective, and we cannot train the instance-wise weight estimator using conventional gradient descent-based optimization. There are approximations such as training in expectation (Raffel et al., 2017) or Gumbel-softmax (Jang et al., 2016). Instead, motivated by its many successful applications (Ranzato et al., 2015; Zaremba & Sutskever, 2015; Zhang & Lapata, 2017), we use REINFORCE algorithm (Williams, 1992) such that the selection action is rewarded by the performance of its impact. The loss function for the instance-wise weight estimator l(φ) is expressed as:
l(φ) = Expj∼PX [ Ec(xpj )∼ρφ(xpj ,·) [ L(f∗(xpj ), g ∗ θ(xpj ) (xpj ))) + λ||c(x p j )||1 ]] To apply the REINFORCE algorithm, we directly compute the gradient∇φ l̂(φ) as:
∇φ l̂(φ) = Expj∼PX [ Ec(xpj )∼ρφ(xpj ,·) [ L(f∗(xpj ), g ∗ θ(xpj ) (xpj ))) + λ||c(x p j )||1 ] ∇φ log ρφ(xpj , c(x p j )) ]
Using the gradient∇φ l̂(φ), we employ the following steps iteratively to update the parameters of the instance-wise weight estimator φ:
1. Estimate instance-wise weights wi(xpj ) = hφ(x p j , xi, ŷi) and instance-wise selection vector
ci(xpj ) ∼ Ber(wi(x p j )) for each training and probe instance in a mini-batch.
2. Optimize the locally interpretable model with the selection vector for each probe instance:
g∗θ(xpj ) = argmin
gθ N∑ i=1 [ ci(xpj ) · Lg(f ∗(xi), gθ(xi)) ]
3. Update the instance-wise weight estimation model parameter φ:
φ← φ− α M M∑ j=1 [ L(f∗(xpj ), g ∗ θ(xpj ) (xpj ))− Lb(x p j ) + λ||c(x p j )||1 ] · ∇φ log ρφ(xpj , c(x p j ))
where α > 0 is a learning rate and Lb(xpj ) = L(f∗(x p j ), g ∗ b (x p j )) is the baseline loss against which
we benchmark the performance improvement. We repeat the steps above until convergence. • Stage 4 – Interpretable inference: Unlike when training, we use a fixed instance-wise weight
estimator (without the sampler and interpretable baseline) and merely fit the locally interpretable model at inference. Given the test instance xt, we obtain the selection probabilities from the instance-wise weight estimator, and using these as the weights, we fit the locally interpretable model via weighted optimization. The outputs of the trained interpretable model are the instancewise predictions and the corresponding explanations (e.g., local dynamics of the black-box model predictions at xt given by the coefficients of the fitted linear model).

heading: 3.2 COMPUTATIONAL COST
text: In this subsection, we analyze the computational cost of RL-LIM for training and inference. As a representative and commonly used example, we assume linear regression as the locally interpretable model, which has a computational complexity of O(d2N) + O(d3) to fit, where d is the number of features and N is the number of training instances. When N >> d (which is often the case in practice), the training computational complexity is approximated as O(d2N) (Tan, 2018). Training: Given a pre-trained black-box model, Stage 1 involves running inferenceN times and the total complexity depends on the complexity of the black-box model. Unless the black-box model is very complex, the computational complexity of Stage 1 becomes much smaller than Stage 3. Stage 2 has negligible computational overhead. At Stage 3, we iteratively train the instance-wise weight estimator and fit the locally interpretable model from scratch using weighted optimization. Therefore, the computational complexity is O(d2NNI) where NI is the number of iterations in Stage 3 (typically NI < 10, 000 until convergence). Thus, the training complexity scales roughly linearly with the number of training instances.
Interpretable inference: To infer with the locally interpretable model, we need to fit the locally interpretable model after obtaining the instance-wise weights from the trained instance-wise weight estimator. Thus, for each testing instance, the computational complexity is O(d2N).1
For instance, on a single NVIDIA V100 GPU, on Facebook Comment dataset (consisting∼ 600,000 samples), RL-LIM yields a training time of less than 5 hours (including Stage 1, 2 and 3) and an interpretable inference time of less than 10 seconds per a testing instance. On the other hand, LIME results in much longer interpretable inference time (around 30 seconds per a testing instance) due to acquiring a large number of black-box model predictions for the inputs perturbations, whereas SILO and MAPLE are similar to RL-LIM.

heading: 4 EXPERIMENTS
text: We compare RL-LIM to multiple benchmarks on 3 synthetic datasets and 5 UCI public datasets.
Datasets: The 3 public datasets for regression problems are: (1) Blog Feedback, (2) Facebook Comment, (3) News Popularity; the other 2 public datasets for classification problems are: (4) Adult Income, (5) Weather. Details of the data descriptions can be found in the hyper-links of each dataset (colored in blue). Data statistics can be found in Table 3 in Appendix A. In this section, we mainly focus on the tabular datasets because the local dynamics are more important and useful to explain for them; however, RL-LIM method can be generalized to other data types in a straightforward way.
1A subset of the training dataset can be used to reduce complexity (with decreased fidelity).
Black-box models: We focus on approximating black-box models that are shown to yield competitive performance on the target tasks: 3 tree-based ensemble methods (1) XGBoost (Chen & Guestrin, 2016), (2) LightGBM (Ke et al., 2017), (3) Random Forests (RF) (Breiman, 2001); and deep neural networks (4) Multi-layer Perceptron (MLP). Also, we use (5) Ridge Regression (RR) and (6) Regression Tree (RT) (for regression) and (7) Logistic Regression (LR) and (8) Decision Tree (DT) (for classification) as globally interpretable models to benchmark.2 We focus on two types of locally interpretable models: (1) Ridge regression, (2) Shallow regression tree (with a max depth of 3). We report the performance with ridge regression for regression and with shallow regression tree for classification in this section. The results of the other two combinations (with ridge regression for classification and with shallow regression tree for regression) are described in Appendix E.
Comparisons to previous work: We compare the performance of RL-LIM with three competing methods: (1) Local Interpretable Model-agnostic Explanations (LIME) (Ribeiro et al., 2016), (2) Supervised Local modeling methods (SILO) (Bloniarz et al., 2016), (3) Model Agnostic Supervised Local Explanations (MAPLE) (Plumb et al., 2018).
Performance metrics: To evaluate the performance of locally interpretable models using real-world datasets, we quantify the overall prediction performance and its fidelity. We assume a disjoint testing dataset Dt = {(xtk, ytk)}Lk=1 for evaluation. For the overall prediction performance, we compare the predictions of the locally interpretable models with the ground-truth labels. We use Mean Absolute Error (MAE) for regression and Average Precision Recall (APR) for classification. For fidelity, we compare the outputs (predicted values for regression and logits for classification) of the locally interpretable models and of the black-box model. We consider two metrics: R2 score (Legates & McCabe, 1999) and Local MAE (LMAE). The details of the metrics are described in Appendix C.
Implementation details: We implement instance-wise weight estimator using a multi-layer perceptron with tanh activation. The number of hidden units and layers are optimized by the crossvalidation. In most cases, 5-layer perceptron with 100 hidden units performs reasonably-well across all datasets. All features are normalized to be between zero and one, using standard minmax scaler. Categorical variables are transformed using one-hot encoding.

heading: 4.1 EXPERIMENTS ON SYNTHETIC DATASETS – RECOVERING LOCAL DYNAMICS
text: On real-world datasets it is challenging to directly evaluate the explanation quality of the locally interpretable models due to the absence of ground-truth explanations. Thus we initially focus on synthetic datasets (with known ground-truth explanations) to directly evaluate how well the locally interpretable models can recover the underlying local dynamics. We construct three synthetic datasets such that the 11-dimensional input features X are sampled from N (0, I) and Y are:
1. Syn1: Y = X1 + 2X2 if X10 < 0 and Y = X3 + 2X4 if X10 ≥ 0 2. Syn2: Y = X1 + 2X2 if X10 + eX11 < 1 and Y = X3 + 2X4 if X10 + eX11 ≥ 1 3. Syn3: Y = X1 + 2X2 if X10 +X311 < 0 and Y = X3 + 2X4 if X10 +X 3 11 ≥ 0
All three datasets have different local dynamics in different input regimes. We directly use the ground truth function as the black-box model and focus on how well locally interpretable modeling can capture the local dynamics. We evaluate the performance of capturing local dynamics using Absolute Weight Difference (AWD): AWD = ||w − ŵ||, where w is the ground truth coefficients to generate Y and ŵ is the derived coefficient from the locally interpretable models. We use the estimated coefficients of the ridge regression as the derived local dynamics (ŵ).
As shown in Fig. 2, RL-LIM significantly outperforms other benchmarks in discovering the local dynamics on all three datasets and in different regimes. RL-LIM can actively learn the linear and non-linear decision boundaries for the local dynamics. Note that LIME completely fails to recover the local dynamics as it uses the Euclidean distance uniformly for all features and cannot distinguish the special properties of the features that alter the local dynamics. SILO and MAPLE only use the predictions to discover the local dynamics; thus, it is hard to discover the decision boundary that depends on the other variables which are independent to the predictions. Fig. 5 in Appendix D shows the learning curves of RL-LIM demonstrating the efficiency of reinforcement learning.
2We use python packages (including Sklearn and Tensorflow) to implement those predictive models and the details can be found in the hyper-links (colored in blue) of each model and Appendix B.

heading: 4.2 THE EFFECT OF THE NUMBER OF SELECTED SAMPLES ON FIDELITY
text: In RL-LIM, optimal distillation is enabled by using a small subset of training instances to fit the low-capacity locally interpretable model. The number of selected instances is controlled by λ in our method – if λ is high/low, RL-LIM penalizes more/less on the number of selected instances; thus, less/more instances are selected to construct the locally interpretable model.
We analyze the efficacy of λ in controlling the likelihood of selection and the dependency of fidelity on λ. We expect that if we select a too small/large number of training instances, the locally interpretable model will overfit/underfit which negatively affects the fidelity in both cases. Fig. 3 shows that there is a clear relationship between λ and the local fidelity. If λ is too large, RL-LIM selects too small number of instances; thus, the fitted locally interpretable model is less accurate (due to overfitting). On the other hand, if λ is too small, RL-LIM selects too large number of instances and deteriorates fidelity (due to underfitting). To achieve the optimal λ, we conduct cross-validation experiments and select λ which achieves the best validation fidelity (e.g. λ = 0.5 in Syn2). Fig. 3 shows the average selection probability of the training instances for each λ. As λ increases, the average selection probabilities monotonically decrease due to the higher penalty on the number of selected training instances. Note that even using a small portion of training instances, RL-LIM can accurately distill the predictions of black-box models into locally interpretable models which is crucial to understand and interpret the predictions using the most relevant training instances.

heading: 4.3 EXPERIMENTS ON REAL DATASETS – OVERALL PERFORMANCE AND FIDELITY
text: On multiple real datasets, we evaluate the overall prediction performance and fidelity. For the regression and classification problems, we use ridge regression and shallow regression trees as the locally interpretable model. More results can be found in Appendix E.
As can be seen in Table 1, the performance of globally interpretable ridge regression (trained on the entire dataset from the scratch) is much worse than other complex non-linear models, implying that modeling non-linear relationships between the features and the labels is important towards high prediction performance. For other locally interpretable modeling methods (LIME, SILO, MAPLE), the performance is far worse than the original black-box model, showing that they fail at efficiently
distilling the non-linear black-box models. In some cases (especially on the Facebook dataset), the performance of the benchmarks is even worse than the performance of global ridge regression (highlighted in red), questioning the value of using these locally interpretable models instead of globally interpretable ridge regression.
In contrast, RL-LIM achieves similar overall prediction performance to the black-box models and significantly outperforms global ridge regression. Table 1 also compares the fidelity in terms of R2 score for regression using ridge regression as the locally interpretable model (LMAE results can be found in Appendix E.3). We observe that R2 scores for some cases (especially on Facebook dataset and LIME) are negative which represent that the outputs of the locally interpretable models are even worse than the constant mean value estimator. On the other hand, RL-LIM achieves higher and positive R2 values consistently for all datasets and black-box models than other benchmarks.
Table 2 shows a similar analysis for classification using shallow regression trees (with max depth of 3) as the locally interpretable model (Regression trees are used to model logit outputs for classification.). The overall prediction performance of four black-box models are significantly better than the globally interpretable decision tree which demonstrates the superior fitting by complex black-box models. Among the locally interpretable models, RL-LIM achieves the best APR and R2 score for most cases, underlining its strength in distilling the predictions of the black-box model accurately. In some cases, the benchmarks (especially for LIME) achieve lower overall prediction performance than the globally interpretable decision tree (highlighted in red). The overall prediction performance and fidelity metrics of all locally interpretable models seem better for classification problems than regression problems. We expect that the predictions of black-box models are mostly highly confident, i.e. located near 0 or 1; thus, locally interpretable models can easily distill the predictions of the black-box models for classification than regression.

heading: 4.4 QUALITATIVE ANALYSES – INTERPRETATIONS OF RL-LIM ON ADULT INCOME DATASET
text: In this subsection, we qualitatively analyze the local explanations provided by RL-LIM on the Adult Income dataset. Although RL-LIM is able to provide local explanations for each individual separately, we analyze its explanations in subgroup granularity for better visualization and understanding. Fig. 4 represents the feature importance (derived by RL-LIM as the local explanations) for
five subgroups in predicting the annual income using XGBoost as the black-box model. We use ridge regression as the locally interpretable model and the absolute value of fitted coefficients as the estimated feature importance. As can be observed in Fig. 4, for age subgroups, capital gain seems much more important for mature people (older than 25) than young people (younger than 25). For education subgroups, capital gain/loss, occupation, and native countries are more critical for highly-educated people (Doctorate, Prof-school, and Masters graduates) than the others. We do not discover notable biases of black-box models for gender, marital status, and race subgroups.

heading: 5 CONCLUSIONS
text: We propose a novel method for locally interpretable modeling of pre-trained black-box models. Our proposed method employs reinforcement learning to select a small number of valuable instances and use them to train a low-capacity locally interpretable model. The selection mechanism is guided with a reward obtained from the similarity of predictions of the locally interpretable model and the blackbox model. Our approach near-matches the performance of black-box models and significantly outperforms alternative techniques in terms of overall prediction performance and fidelity metrics consistently across various datasets and black-box models.

heading: A DATA STATISTICS

heading: B HYPER-PARAMETERS OF THE PREDICTIVE MODELS
text: In this paper, we use 8 different predictive models. For each predictive model, the corresponding hyper-parameters used in the experiments are as follows:
• XGBoost: booster - gbtree, max depth - 6, learning rate - 0.3, number of estimators - 1000, max depth - 6, reg alpha - 0
• LightGBM: booster - gbdt, max depth - None, learning rate - 0.1, number of estimators - 1000, min data in leaf - 20
• Random Forests: number of estimators - 1000, criterion - gini, max depth - None, warm start - False
• Multi-layer Perceptron: Number of layers - 4, hidden units - [feature dimensions, feature dimensions/2, feature dimensions/4, feature dimensions/8], activation function - relu, early stoping - True with patient 10, batch size - 256, maximum number of epochs - 200, optimizer - Adam
• Ridge Regression: alpha - 1 • Regression Tree: max depth - 3, criterion - gini • Logistic Regression: solver - lbfgs, no regularization • Decision Tree: max depth - 3, criterion - gini
We follow the default settings for the other hyper-parameters that are not mentioned here.

heading: C PERFORMANCE METRICS
text: • Mean Absolute Error (MAE):
MAE = E(xt,yt)∼P ||g∗θ(xt)(x t)− yt)||1 '
1
L L∑ k=1 ||g∗θ(xtk)(x t k)− ytk||1,
• Local MAE (LMAE):
LMAE = Ext∼PX ||g∗θ(xt)(x t)− f∗(xt)||1 '
1
L L∑ k=1 ||g∗θ(xtk)(x t k)− f∗(xtk))||1,
• R2 score (Legates & McCabe, 1999):
R2 = 1− Ext∼PX ||f∗(xt)− g∗θ(xt)(x t)||22 Ext∼PX ||f∗(xt)− Ex̂t∼PX [f∗(x̂ t)]||22 ' 1−
1 L ∑L k=1 ||f∗(xtk)− g∗θ(xtk)(x t k)||22
1 L ∑L k=1 ||f∗(xtk)− 1 L ∑L k=1[f ∗(xtk)]||22 .
If R2 = 1, the predictions of the locally interpretable model perfectly match the predictions of the black-box model. On the other hand, if R2 = 0, the locally interpretable model performs as similar as the constant mean value estimator. If R2 < 0, the locally interpretable model performs worse than the constant mean value estimator.

heading: D LEARNING CURVES OF RL-LIM

heading: E ADDITIONAL RESULTS
text: E.1 REGRESSION WITH SHALLOW REGRESSION TREE AS THE LOCALLY INTERPRETABLE MODEL
E.2 CLASSIFICATION WITH RIDGE REGRESSION AS THE LOCALLY INTERPRETABLE MODEL
E.3 REGRESSION WITH RIDGE REGRESSION AS THE LOCALLY INTERPRETABLE MODEL - FIDELITY ANALYSIS IN TERMS OF LOCAL MAE (LMAE)
E.4 COMPARISON TO DIFFERENTIABLE WEIGHTING BASELINES
In this subsection, we additionally compare RL-LIM to two baselines that have differentiable objective for weighting: (1) straight-through estimator (STE) (Bengio et al., 2013), (2) Learning to Reweight (L2R) (Ren et al., 2018). The experimental setup is the same with the synthetic experiments in Section 4.1 and the performance metric is Average Weight Difference (AWD). As can be seen from Table 8, the first approach, STE, converges fast but to a suboptimal AWD, whereas L2R overfits to the fidelity metric and cannot guide weighting of the training samples properly, eventually yielding poor AWD.
The sampler block in RL-LIM makes the optimization problem of the RL-LIM non-differentiable. The main motivation of using the sampler in RL-LIM is to encourage exploration in order to systematically explore the extremely large action space. When we utilize straight-through estimator to make the entire process differentiable, the model converges faster but to a suboptimal solution due to the under-exploration of the action space.
The main difference between L2R and RL-LIM is that L2R learns weights of the training samples that are the same across all validation and testing samples; on the other hand, RL-LIM uses a single instance-wise weight estimator model to learn different weights of the training samples for each probe samples. If we apply L2R to this framework, we need to separately apply L2R for each probe sample. Therefore, there would be a high likelihood of overfitting to the probe dataset because it would only use one validation sample to learn the weights of the training samples.
E.5 SAMPLE COMPLEXITY ANALYSIS
In this subsection, we report the sample complexity analysis results of RL-LIM, comparing to: (1) randomly selected subsamples (Random), (2) STE-based weighting (STE). We vary the number of training samples (from 200 to 2000) and compute the AWD on three synthetic datasets.
As can be seen in Fig. 6, with randomly selected subsamples, it only works well when we have an extremely small number of training samples due to a smaller chance of overfitting. For STE-based model, it converges fast; thus, it works better with smaller training samples; however, for larger training samples, it performs worse than RL-LIM due to under-exploration of the action space.

heading: F ANALYSIS OF INSTANCE-WISE WEIGHTS DISTRIBUTIONS
text: In this section, we analyze the instance-wise weights of training samples visualizing the distributions of the instance-wise weights of training samples for the entire probe samples, and the dependence of the average instance-wise weights of training samples on the distance from the probe sample.
As can be seen in Fig. 7 (a)-(c), the instance-wise weights have quite skewed distribution. Some samples (e.g. with average instance-wise weights above 0.5) are much more critical to interpreting the probe sample than many others (e.g. average instance-wise weights below 0.1)
In Fig. 7 (d), there is a clear trend that the samples near the probe sample have higher average instance-wise weights, which shows that RL-LIM learns the meaningful distance metrics to measure the relevance while interpreting the probe samples. This trend is consistent across all three synthetic datasets.

Review summaries:
This paper studies the problem of interpreting predictions of blackbox models. In particular, they study local interpretable models, which are used to study interpretability at the level of one or a few data points. A key challenge is that in order for local models to be interpretable, they need to be simple in form and therefore lower in capacity (i.e. linear); thus, if they are trained on entire datasets they will underfit.