Robust and Stable Black Box Explanations

To construct explanations that are robust to shifts in the data distribution $p$, we first consider the general setting where we are given a set of distribution shifts that we want our explanations to be robust to; we describe a practical choice in Section 3.2. We initially focus on distributional robustness; we connect it to adversarial robustness below.

In other words, $p_{\delta}$ places probability mass on covariates that are shifted by $\delta$ compared to $p$.

For computational tractability, we assume:

Given a set of distribution shifts, our goal is to compute the best explanation that is robust to these shifts:

That is, $\hat{E}$ optimizes the worst-case loss over shifts $p_{\delta}$. Computing the worst-case over shifts $p_{\delta}$ can be intractable; instead, we use an upper bound on the objective in Eq. 3.

Proof: Note that

	$\displaystyle\max_{\delta\in\Delta}\mathbb{E}_{p_{\delta}(x)}[\ell(E(x),B^{*}(x))]$
	$\displaystyle=\max_{\delta\in\Delta}\int_{\mathcal{X}}\ell(E(x),B^{*}(x))p(x-\delta)dx$
	$\displaystyle=\max_{\delta\in\Delta}\int_{\mathcal{X}}\ell(E(x^{\prime}+\delta),B^{*}(x^{\prime}+\delta))p(x^{\prime})dx^{\prime}$
	$\displaystyle\leq\int_{\mathcal{X}}\max_{\delta\in\Delta}\ell(E(x^{\prime}+\delta),B^{*}(x^{\prime}+\delta))p(x^{\prime})dx^{\prime},$
	$\displaystyle\leq\mathbb{E}_{p(x)}\left[\max_{\delta\in\Delta}\ell(E(x+\delta),B^{*}(x+\delta))\right]\qed$

This lemma gives us a surrogate objective that we can optimize in place of the one in Eq. 3—i.e.,

$\displaystyle\hat{E}=\operatorname*{\arg\min}_{E\in\mathcal{E}}\mathbb{E}_{p(x)}\left[\max_{\delta\in\Delta}\ell(E(x+\delta),B^{*}(x+\delta))\right].$

(4)

In particular, this approach connects distributional robustness to adversarial robustness—Eq. 4 is the standard objective used to achieve adversarial robustness to input perturbations $\delta\in\Delta$ (Goodfellow et al., 2015).

Next, we propose a choice of $\Delta$ that captures distributions shifts we believe to be of importance in practical applications. We begin with a concrete setting that motivates our choice, but our choice includes shifts beyond this setting.

In particular, consider the case where $\mathcal{X}=\{0,1\}^{d}$ is a vector of indicators. Our intuition is that when examining an explanation, users often want to understand how the model predictions change when a handful of components of an input $x\in\mathcal{X}$ change.

For instance, this intuition captures the case of counterfactual explanations, where the goal is to identify a small number of covariates that can be changed to affect the outcome (Zhang et al., 2018). It also captures certain intuitions underlying fairness and causality, where we care about how the model changes when a covariate such as gender or ethnicity changes (Lakkaraju & Bastani, 2020; Rosenbaum & Rubin, 1983; Pearl, 2009). Finally, it also encompasses the shifts considered in measures of variable importance (Hastie et al., 2001)—in particular, variable importance measures how the explanation changes when a single component of the input $x$ is changed.

We can use the following choice to capture our intuition:

$\displaystyle\Delta_{1}=\{\delta\in\{-1,0,1\}^{n}\mid\|\delta\|_{0}\leq s_{0}\}$

for $s_{0}\in\mathbb{N}$. However, this set is nonconvex. We can approximate this constraint using the following set:

$\displaystyle\Delta_{2}=\{\delta\in\mathbb{R}^{n}\mid\|\delta\|_{0}\leq s_{0}\wedge\|\delta\|_{\infty}\leq 1\}.$

In particular, the constraint $\|\delta\|_{\infty}\leq 1$ ensures that $-1\leq\delta_{i}\leq 1$ for each $i\in\{1,...,n\}$. Finally, we can replace the $L_{0}$ norm with the $L_{1}$ norm:

$\displaystyle\Delta_{3}=\{\delta\in\mathbb{R}^{n}\mid\|\delta\|_{1}\leq s_{0}\wedge\|\delta\|_{\infty}\leq 1\}.$

(5)

This overapproximation is a heuristic based on the fact that the $L_{1}$ loss induces sparsity in regression (Tibshirani, 1997).

More generally, we consider a shift from $p$ to a distribution $p^{\prime}$ such that $p^{\prime}$ places probability mass on the same inputs $x$ as $p$, except a small number of components of $x$ are systematically changed by a small amount:

$\displaystyle\tilde{\Delta}(s_{0},\delta_{\text{max}})=\{\delta\in\mathbb{R}^{n}\mid\|\delta\|_{0}\leq s_{0}\wedge\|\delta\|_{\infty}\leq\delta_{\text{max}}\},$

where $s_{0}\in\mathbb{N}$ and $\delta_{\text{max}}\in\mathbb{R}$—i.e., $\delta\in\tilde{\Delta}(s_{0},\delta_{\text{max}})$ is a sparse vector whose components are not too large. However, $\tilde{\Delta}(s_{0},\delta_{\text{max}})$ is nonconvex. As above, for computational tractability, we approximate it using

$\displaystyle\Delta(s_{0},\delta_{\text{max}})=\{\delta\in\mathbb{R}^{n}\mid\|\delta\|_{1}\leq s_{0}\wedge\|\delta\|_{\infty}\leq\delta_{\text{max}}\}.$

It is easy to see that $\tilde{\Delta}(s_{0},\delta_{\text{max}})\subseteq\Delta(s_{0},\delta_{\text{max}})$, so this choice overapproximates the set of shifts. In particular, this choice $\Delta(s_{0},\delta_{\text{max}})$ is a polytope, so it satisfies Assumption 3.3. The set defined in Eq. 5 is $\Delta_{3}=\Delta(s_{0},1)$.

A particular benefit of $\Delta(s_{0},\delta_{\text{max}})$ is that the marginal dependencies of $B^{*}$ on a component $x_{i}$ of an input $x\in\mathcal{X}$ is preserved in $\hat{E}$—i.e., if we unilaterally change $x_{i}$ by a small amount, $B^{*}$ and $\hat{E}$ change in the same way. Formally:

Proof: Note that

	$\displaystyle\mathbb{E}_{p(x)}\left[\left|(\hat{E}(x+c\alpha)-\hat{E}(x))-(B^{*}(x+c\alpha)-B^{*}(x))\right|\right]$
	$\displaystyle\leq\mathbb{E}_{p(x)}\left[\left|\hat{E}(x+c\alpha)-B^{*}(x+c\alpha)\right|\right]$
	$\displaystyle\hskip 14.45377pt+\mathbb{E}_{p(x)}\left[\left|\hat{E}(x)-B^{*}(x)\right|\right]$
	$\displaystyle\leq 2\epsilon\text{ since }c\alpha\in\Delta\qed$

As shown in Section 1, this property is not satisfied by standard measures of fidelity, since an explanation with perfect fidelity (i.e., Eq. 1) may use completely different covariates from the black box.

We consider the case where $\mathcal{E}$ is the space of linear functions, or more generally, any model family that can be optimized using gradient descent. Then, we can use adversarial training to optimize Eq. 4 (Goodfellow et al., 2015; Shaham et al., 2018). The key idea behind adversarial training is to learn a model $f^{*}\in\mathcal{F}$ that is robust with respect to a worst-case set of perturbations to the input data—i.e.,

$\displaystyle f^{*}=\operatorname*{\arg\min}_{f\in\mathcal{F}}\mathbb{E}_{p(x,y)}\left[\max_{\delta\in\Delta}\ell(f(x+\delta),y)\right].$

We can straightforwardly adapt this formalism to our setting by replacing $\mathcal{F}$ with $\mathcal{E}$ and $y$ with $B^{*}(x)$. In particular, suppose that $E_{\theta}\in\mathcal{E}$ is parameterized by $\theta\in\Theta$, where $\Theta\subseteq\mathbb{R}^{d}$ and $J(\theta;x)$ is defined as follows:

$\displaystyle J(\theta;x)=\ell(E_{\theta}(x),B^{*}(x)).$

Then, Eq. 4 becomes

$\displaystyle\hat{\theta}=\operatorname*{\arg\min}_{\theta\in\Theta}\mathbb{E}_{p(x)}\left[\max_{\delta\in\Delta}J(\theta;x+\delta))\right].$

(6)

The adversarial training approach optimizes Eq. 6 by using stochastic gradient descent (Goodfellow et al., 2015; Shaham et al., 2018)—for a single sample $x\sim p(x)$, the stochastic gradient estimate of the objective in Eq. 6 is

$\displaystyle\nabla_{\theta}\max_{\delta\in\Delta}J(\theta;x+\delta)\approx\nabla_{\theta}J(\theta;x+\delta^{*}),$

where

$\displaystyle\delta^{*}=\operatorname*{\arg\max}_{\delta\in\Delta}J(\theta,x+\delta).$

(7)

To solve Eq. 7, we use the Taylor approximation

$\displaystyle J(\theta;x+\delta)\approx J(\theta;x)+\nabla_{x}J(\theta;x)^{\top}\delta.$

Using this approximation, Eq. 7 becomes

	$\displaystyle\delta^{*}$	$\displaystyle=\operatorname*{\arg\max}_{\delta\in\Delta}J(\theta,x+\delta)$
		$\displaystyle\approx\operatorname*{\arg\max}_{\delta\in\Delta}\left\{J(\theta;x)+\nabla_{x}J(\theta;x)^{\top}\delta\right\}$
		$\displaystyle=\operatorname*{\arg\max}_{\delta\in\Delta}\nabla_{x}J(\theta;x)^{\top}\delta,$		(8)

where in the last line, we dropped the term $J(\theta;x)$ since it is constant with respect to $\delta$. Since we have assumed $\Delta$ is a polytope, Eq. 8 is a linear program with free variables $\delta$.

Here, we describe how we can construct robust rule-based explanations (Lakkaraju et al., 2016; Letham et al., 2015; Lakkaraju et al., 2019b)—e.g., decision sets (Lakkaraju et al., 2016, 2019b), decision lists (Letham et al., 2015), decision trees (Quinlan, 1986). Any rule based model can be expressed as a decision set (Lakkaraju & Rudin, 2017), so we focus on these models.

Unlike explanations with continuous parameters, we can no longer use gradient descent to optimize Eq. 4. Instead, we optimize it using a sampling-based heuristic. We assume we are given a distribution $p_{0}(\delta)$ over shifts $\delta\in\Delta$. Then, we approximate the maximum in Eq. 4 using $k$ samples:

$\displaystyle\max_{\delta\in\Delta}F(\delta)\approx\max_{\delta^{j}\sim p_{0}(\delta)}F(\delta^{j}),$

where $F(\delta)$ is a general objective and $j\in\{1,...,k\}$. In particular, our optimization problem becomes

$\displaystyle\hat{E}=\operatorname*{\arg\min}_{E\in\mathcal{E}}\mathbb{E}_{p(x)}\left[\max_{\delta^{j}\sim p_{0}(\delta)}\ell(E(x+\delta^{j}),B^{*}(x+\delta^{j}))\right].\vspace{-0.3in}$

(9)

Next, a decision set

$\displaystyle E=\{(s_{1},c_{1}),(s_{2},c_{2})\cdots(s_{m},c_{m})\}\subseteq S\times C$

is a set of rules of the form $(s,c)$ where $s$ is a conjunction of predicates of the form $(\text{feature},\text{operator},\text{value})$ (e.g., age $\geq$ 45) and $c\in\mathcal{Y}$ is a label. Typically, we consider the case where $\mathcal{Y}$ is a finite set. Existing algorithms (Lakkaraju et al., 2019b, 2016) for constructing decision set explanations primarily optimize for the following three goals: (i) maximizing the coverage of $E$—i.e., for $x\in\mathcal{X}$, maximizing the probability that one of the rules $(s,c)\in E$ has a condition $s$ that is satisfied by $x$, (ii) minimizing the disagreement between $E$ and $B^{*}$—i.e., minimizing the probability that $E(x)\neq B^{*}(x)$, and (iii) minimizing the complexity of $E$—e.g., $E$ has fewer rules. In particular, these algorithms optimize the following objective:

	$\displaystyle\hat{E}=$	$\displaystyle\operatorname*{\arg\max}_{E\subseteq S\times C}\{-\text{disagree}(E)+\lambda\cdot\text{cover}(E)\}$		(10)
		$\displaystyle\text{subj. to }|E|\leq\alpha,$

where

	$\displaystyle\text{disagree}(E)$	$\displaystyle=\sum_{i=1}^{m}\mathbb{P}_{p(x)}(s_{i}(x)\rightarrow B^{*}(x)\neq c_{i})$
	$\displaystyle\text{cover}(E)$	$\displaystyle=\mathbb{P}_{p(x)}(\exists(s,c)\in E\text{ s.t. }s(x)=\text{true}).$

Here, we let $s(x)=\text{true}$ if $x$ satisfies $s$ and $s(x)=\text{false}$ otherwise. In $\text{disagree}(E)$, the event in the probability says if predicate $s_{i}$ applies to $x$, then $B^{*}(x)\neq c_{i}$.

To adapt this approach to solving Eq. 9, we modify the disagreement to take the worst-case over $\delta^{j}\sim p_{0}(\delta)$:

	$\displaystyle\text{disagree}(E)$
	$\displaystyle=\sum_{i=1}^{m}\mathbb{P}_{p(x)}\left(s_{i}(x)\rightarrow\exists\delta^{j}\sim p_{0}(\delta)~{}.~{}B^{*}(x+\delta^{j})\neq c_{i}\right).$

where $j\in\{1,...,k\}$. Here, we have used an approximation where we only check if $s_{i}$ applies to the unperturbed input $x$; this choice enables our submodularity guarantee.

Proof: To show non-monotonicity, it suffices to show that at least one term in the objective Eq. 10 is non-monotone. Every time a new rule is added, the value of disagree either remains the same or increases, since the newly added rule may potentially label new instances incorrectly, but does not decrease the number of instances already labeled incorrectly by previously chosen rules. Therefore, $\text{disagree}(A)\leq\text{disagree}(B)$ if $A\subseteq B$, so $-\text{disagree}(A)\geq-\text{disagree}(B)$, which implies disagree term is non-monotone. Thus, the entire linear combination is non-monotone.
To prove that the objective in Eq. 10 is submodular, we need to: (i) introduce a (large enough) constant $C$ into the objective function to ensure that $C-\text{disagree}(E)$ is never negative,¹¹1Note that adding such a constant does not impact the solution to the optimization problem. and (ii) prove that each of the its terms are submodular. The cover term is clearly submodular—i.e., more data points will be covered when we add a new rule to a smaller set of rules compared to a larger set. It is also easy to check that the disagree term is modular/additive (and therefore submodular). Lastly, the constraint in Eq. 10 is a cardinality constraint. ∎

Since the objective of Eqn. 10 is non-monotone and submodular with cardinality constraints (Theorem 3.7), exactly solving it is NP-Hard (Khuller et al., 1999). So, we use approximate local search algorithm (Lee et al., 2009) to optimize Eq. 10. This algorithm provides the best known theoretical guarantees for this class of problems—i.e., $(k+2+1/k+\delta)^{-1}$, where $k$ is the number of constraints ($k=1$ in our case) and $\delta>0$.

Datasets. We analyzed three real-world datasets from criminal justice, healthcare, and education domains (Lakkaraju et al., 2016). Our first dataset contains bail outcomes from two different state courts in the U.S. 1990-2009. It includes criminal history, demographic attributes, information about current offenses, and other details on 31K defendants who were released on bail. Each defendant in the dataset is labeled as either high risk or low risk depending on whether they committed new crimes when released on bail. Our second dataset contains academic performance records of about 19K students who were set to graduate high school in 2012 from two different school districts in the U.S. It includes information about grades, absence rates, suspensions, and tardiness scores from grades 6 to 8 for each of these students. Each student is assigned a class label indicating whether the student graduated high school on time. Our third dataset contains electronic health records of about 22K patients who visited hospitals in two different counties in California between 2010-2012. It includes demographic information, symptoms, current and past medical conditions, and family history of each patient. Each patient is assigned a class label which indicates whether the patient has been diagnosed with diabetes.

Distribution shifts. Each of our datasets contains two different subgroups—e.g., our bail outcomes dataset contains defendants from two different states. We randomly choose data from one of these subgroups (e.g., a particular state) to be the training data, and data from the other subgroup to be the shifted data. In particular, we apply each algorithm on the training data to construct explanations, and evaluate these explanations on the shifted data.

Our explanations. Our framework ROPE can be applied in a variety of configurations. We consider four: (i) ROPE logistic: We construct a single global logistic regression model using our framework to approximate any given black box. (ii) ROPE dset: We construct a single global decision set using our framework to approximate any given black box. (iii) ROPE logistic multi: We construct multiple local explanations. In particular, we first cluster the data into $K$ subgroups (details below), and use ROPE to fit a robust logistic regression model to approximate the given black box for each subgroup. We also compute the centroid of each subgroup to serve as a representative sample. (iv) ROPE dset multi: Similar to ROPE logistic multi, except that we fit a decision set.

Baselines. We compare our framework to the following state-of-the-art post hoc explanation techniques: (i) LIME (Ribeiro et al., 2016), (ii) SHAP (Lundberg & Lee, 2017a), and (iii) MUSE (Lakkaraju et al., 2019b). LIME and SHAP are model-agnostic, local explanation techniques that explain an individual prediction of a black box by training a linear model on data near that prediction. LIME and SHAP can be adapted to produce global explanations of any given black box using a submodular pick procedure (Ribeiro et al., 2016), which chooses a few representative points from the dataset and combines their corresponding local models to form a global explanation. In our evaluation, we use the global explanations of LIME and SHAP constructed using this technique. MUSE is a model-agnostic, global explanation technique; it provides global explanations in the form of two-level decision sets.

Parameters. In case of LIME, SHAP, ROPE logistic multi, and ROPE dset multi, there is a parameter $K$ which corresponds to the number of local explanations that need to be generated; $K$ can also be thought as the number of subgroups in the data. We use Bayesian Information Criterion (BIC) to choose $K$. For a given dataset, we use the same $K$ for all these techniques to ensure they construct explanations of the same size. For MUSE, we set all the parameters using the procedure in Lakkaraju et al. (2019b); to ensure these explanations are similar in size to the others, we fix the number of outer rules to be $K$. Finally, when using ROPE to construct rule-based explanations, there is a term $\lambda$ in our objective (Eq. 10); we fix $\lambda=5$.

Black boxes. We generate post hoc explanations of deep neural networks (DNNs), gradient boosted trees, random forests, and SVMs. Here, we present results for a 5-layer DNN; remaining results are included in the Appendix. Results presented below are representative of those for other model families.

Metrics. We use fidelity to measure performance—i.e., the fraction of inputs $x$ in the given dataset for which $\hat{E}(x)=B^{*}(x)$ (Lakkaraju et al., 2019b). Fidelity is straightforward to compute for MUSE, ROPE logistic, and ROPE dset since they construct an explanation in the form of a single interpretable model. However, the explanations constructed by LIME, SHAP, ROPE logistic multi, and ROPE dset multi consist of a collection of local models. In these cases, we need to determine which local model to use for each input $x$. By construction, each local model $\hat{E}_{i}$ is associated with a representative input $x_{i}$, for $i\in\{1,...,K\}$. Thus, we compute the distance $\|x-x_{i}\|$ for each $i$, and return $\hat{E}_{i^{*}}(x)$ where $x_{i^{*}}$ is closest to $x$.

We assess the robustness of explanations constructed using each approach on real-world datasets. In particular, we compute the fidelity of the explanations on both the training data and the shifted data, as well as the percentage change between the two. A large drop in fidelity from the training data to the shifted data indicates that the explanation is not robust. Ideally, explanations should have high fidelity on both the training data (indicating it is a good approximation of the black box model) and on the shifted data (indicating it is robust to distribution shift).

Results for all three real-world datasets are shown in Table 1. As can be seen, all the explanations constructed using our framework ROPE have a much smaller drop in fidelity (0% to 7%) compared to those generated using the baselines. These results demonstrate that our approach significantly improves robustness. MUSE explanations have the largest percentage drop (21% to 23%), likely because MUSE relies entirely on the training data. In contrast, both LIME and SHAP employ input perturbations when constructing explanations (Ribeiro et al., 2016; Lundberg & Lee, 2017b), resulting in somewhat increased robustness compared to MUSE. Nevertheless, LIME and SHAP still demonstrate a considerable drop (13% to 19%), so they are still not very robust. The reason is because these approaches do not optimize a minimax objective that encodes robustness such as ours. Thus, these results validate our approach.

In addition, Table 1 shows the actual fidelities on both training data and shifted data. As can be seen, the fidelities of ROPE logistic and ROPE dset are lower than the other approaches; these results are expected since ROPE logistic and ROPE dset only use a single logistic regression and a single decision set model, respectively, to approximate the entire black box. On the other hand, ROPE logistic multi and ROPE dset multi achieve fidelities that are equal or better than the other baselines. These results demonstrate that ROPE achieves robustness without sacrificing fidelity on the original training distribution. Thus, our approach strictly outperforms the baseline approaches.

Next, we assess how different kinds of distribution shifts impact the fidelity of explanations constructed using our framework and the baselines using synthetic data. We study the effects of three different kinds of shifts: (i) changes in the correlations between different components of the covariates, (ii) changes in the means of the covariates, and (iii) changes in the variances of the covariates.

Shifts in correlation. We first describe our study for shifted data of type (i) above. We generate a synthetic dataset with 5K samples. The covariate dimension is randomly chosen between 2 and 10. Each data point is sampled $x\sim\mathcal{N}(\mu,\Sigma)$, where $\mu_{i}=0$, $\Sigma_{ii}=1$ and $\Sigma_{ij}=\beta$, where $\beta$ is uniformly random in $[-1,1]$—i.e., the correlation between any two components of the covariates is $\beta$. The label for each data point is chosen randomly. We train a 5 layer DNN $B^{*}$ on this dataset, and construct explanations for $B^{*}$.

To generate shifted data, we generate a new dataset with the same approach as above but using a different correlation $\beta^{\prime}=\beta+\alpha$, where we vary $\alpha$. Then, we compute the percentage drop in fidelity of the explanations from the training data to each of the shifted datasets. We show results averaged over 100 runs in Figure 1 (left); the $x$-axis shows $|\alpha|$, and the $y$-axis shows the percentage drop. As can be seen, MUSE exhibits the highest drop in fidelity, followed closely by LIME and SHAP. In contrast, the ROPE explanations are substantially more robust, incurring less than a 10% drop in fidelity.

Mean shifts. For shifts of type (ii) above, we follow the same procedure, except we use $\beta=0$ for both the training and shifted datasets (i.e., uncorrelated covariates), and choose $\mu$ randomly in $[-5,5]$. To generate shifted data, we use a different $\mu^{\prime}=\mu+\alpha$. Results averaged across 100 runs are shown in Figure 1 (middle). ROPE is still the most robust, though LIME and SHAP are closer to ROPE than to MUSE. Explanations generated by MUSE are not robust even to small changes in covariate means.

Variance shifts. For shifts of type (iii) above, we follow the same procedure, except we use $\beta=0$, and choose $\Sigma_{ii}=\sigma$, where $\sigma$ is randomly chosen from $[1,10]$. To generate shifted data, we use a different $\sigma^{\prime}=\sigma+\alpha$. Results averaged across 100 runs are shown in Figure 1 (right). The results are similar to the case of mean shifts.

Here, we evaluate the correctness of the constructed explanations—i.e., how closely an explanation resembles the black box. To this end, we first train “black box” models $B^{*}\in\mathcal{E}$ that are interpretable using the training data from each of our real-world datasets. Then, we construct an explanation $\hat{E}$ for $B^{*}$ using the shifted data. If $\hat{E}$ resembles $B^{*}$ structurally, then the underlying explanation technique is generating explanations that are correct despite being constructed based on shifted data.

Logistic regression black box. We first train a logistic regression (LR) “black box” $B^{*}$, and then use LIME, SHAP, ROPE logistic, and ROPE logistic multi to construct explanations $\hat{E}$ for $B^{*}$. We define the coefficient mismatch to measure the correctness. For ROPE logistic, it is computed as $\|\hat{E}-B^{*}\|$—i.e., the $L_{2}$ distance between the weight vectors of $\hat{E}$ and $B^{*}$; smaller distances mean the explanation more closely resembles the black box. The remaining approaches construct multiple logistic regression models—one $\hat{E}_{i}$ for each representative input $x_{i}$, for $i\in\{1,...,K\}$. To measure the coefficient mismatch, we assign a weight $w_{i}$ to each $x_{i}$ that equals the fraction of inputs $x$ that are assigned to $x_{i}$ (i.e., $x_{i}$ is the closest representative). Then, we measure coefficient mismatch as $\sum_{i=1}^{K}w_{i}\cdot\|\hat{E}_{i}-B^{*}\|$.

We also consider the case where $B^{*}$ is a collection of multiple logistic regression (Multiple LR) models—one $B^{*}_{i}$ for each of the $K$ subgroups. We construct explanations using LIME, SHAP, ROPE logistic, and ROPE logistic multi, and measure the coefficient mismatch as $\sum_{i=1}^{K}w_{i}\cdot\|\hat{E}_{i}-B^{*}_{e}\|$; In case of ROPE logistic, $\hat{E}_{i}=\hat{E}$.

Results for the bail dataset are shown in Table 2. When $B^{*}$ is a single logistic regression (LR), ROPE logistic and ROPE logistic multi explanations achieve the best performance and are about 38.2% more structurally similar to $B^{*}$ than the baselines. When $B^{*}$ is multiple logistic regressions (Multiple LR), the coefficient mismatch of ROPE logistic multi is at least 38.05% lower than the baselines. We obtained similar results for the academic and health datasets.

Decision set black box. As before, we train a decision set (DS) “black box” $B^{*}$ on the real-world training data, and then construct an explanation $\hat{E}$ based on the shifted data using MUSE, ROPE dset, and ROPE dset multi. We consider two measures of correctness for ROPE dset: (i) rule match: the number $d_{r}(\hat{E},B^{*})$ of rules present in both $\hat{E}$ and $B^{*}$, and (ii) feature match: the number of features $d_{f}(\hat{E},B^{*})$ present in both $\hat{E}$ and $B^{*}$. As before, for ROPE dset multi and MUSE, we use the weighted measure $\sum_{i=1}^{K}w_{i}\cdot d(\hat{E}_{i},B^{*})$, where $d=d_{r}$ and $d=d_{f}$ for rule match and feature match respectively. Higher rule and feature matches indicate that $\hat{E}$ better resembles $B^{*}$. We also consider the case where $B^{*}$ consists of multiple decision sets (Multiple DS)—one $B^{*}_{i}$ for each of the $K$ subgroups.

On the bail dataset, ROPE dset multi has 42.3% (resp., 60.4%) higher rule match than MUSE when $B^{*}$ corresponds to DS (resp., Multiple DS), and has at least 37% higher feature match than the baselines.

Finally, we evaluate the stability of the constructed explanations—i.e., how much do the explanations change if the input data is perturbed by a small amount. To this end, we first generate a synthetic dataset $D$ with 5000 samples as described in Section 4.3. Then, we generate the perturbed dataset $D^{\prime}$ by adding a small amount of Gaussian noise to data points—i.e., $x^{\prime}=x+\epsilon$, where $\epsilon\sim\mathcal{N}(0,0.2)$.²²2We experimented with other choices of variance in the range $(0.2,1.0]$ and found similar results. We then train LR, Multiple LR, DS, and Multiple DS “black boxes” $B^{*}$, and use LIME, SHAP, ROPE logistic, ROPE logistic multi, ROPE dset, ROPE dset multi to construct explanations $\hat{E}$ for the corresponding $B^{*}$. We use the original dataset $D$ both to train each black box $B^{*}$ as well as to construct its explanation $\hat{E}$. Then, for each black box $B^{*}$, we use the perturbed dataset $D^{\prime}$ to construct an additional explanation $\hat{E}^{\prime}$. Since $D^{\prime}$ is obtained by making small changes to instances in $D$, $E$ and $E^{\prime}$ should be structurally similar if the explanation technique used to construct them generates stable explanations.

We measure structural similarity of $E$ and $E^{\prime}$—similar to the results in Table 2, we compute their coefficient mismatch in the case of LR and Multiple LR, and rule and feature match in case of DS and Multiple DS. We find that explanations $E$ and $E^{\prime}$ constructed using ROPE are 18.21% to 21.08% more structurally similar than those constructed using LIME, SHAP, or MUSE. Thus, our results demonstrate that ROPE explanations are much more stable than those constructed using baselines.