Improving Decision Sparsity
Authors: Yiyang Sun
Tong Wang
Cynthia Rudin
Venue: NeurIPS 2024 poster (2024)
Keywords: sparse explanation
decision sparsity
Primary area: interpretability_and_explainability

Abstract: Sparsity is a central aspect of interpretability in machine learning. Typically, sparsity is measured in terms of the size of a model globally, such as the number of variables it uses. However, this notion of sparsity is not particularly relevant for decision making; someone subjected to a decision does not care about variables that do not contribute to the decision. In this work, we dramatically expand a notion of *decision sparsity* called the *Sparse Explanation Value* (SEV) so that its explanations are more meaningful. SEV considers movement along a hypercube towards a reference point. By allowing flexibility in that reference and by considering how distances along the hypercube translate to distances in feature space, we can derive sparser and more meaningful explanations for various types of function classes. We present cluster-based SEV and its variant tree-based SEV, introduce a method that improves credibility of explanations, and propose algorithms that optimize decision sparsity in machine learning models.

Improving Decision Sparsity
Yiyang Sun Duke University
Tong Wang Yale University
Cynthia Rudin Duke University
Abstract
Sparsity is central aspect of interpretability in machine learning. Typically, sparsity is measured in terms of the size of a model globally, such as the number of variables uses. However, this notion of sparsity is not particularly relevant for decision making; someone subjected to a decision does not care about variables that do not contribute to the decision. In this work, we dramatically expand notion of decision sparsity called the Sparse Explanation Value (SEV) so that its explanations are more meaningful. SEV considers movement along hypercube towards a reference point. By allowing flexibility in that reference and by considering how distances along the hypercube translate to distances in feature space, we can derive sparser and more meaningful explanations for various types of function classes. We present cluster-based SEV and its variant tree-based SEV, introduce method that improves credibility of explanations, and propose algorithms that optimize decision sparsity machine learning models.
Introduction
The notion of sparsity is major focus of interpretability in machine learning and statistical modeling [Tibshirani] 1996 Rudin et al. 2022]. Typically, sparsity is measured globally, such as the number of variables a model, or as the number of leaves sparsity is relevant in many situations, but it is less relevant for individuals subject to the model's decisions. Individuals care less about, and often do not even have access to, the global model. For them, local sparsity, or decision sparsity, meaning the amount of information critical to their decision, is more consequential.
decision tree [Murdoch et al., 2019]. Global
An important notion of decision sparsity has been established in the work of Sun et al. 2024 which defined the Sparse Explanation Value (SEV), in the context of binary classification, as the number of factors that need to be changed to a reference feature value in order to change the decision. In contrast to SEV, counterfactual explanations tend not to be sparse since they require small changes to many variables in order to reach the decision boundary (Sun et al., 2024]. Instead, SEV provides sparse explanations: consider loan application that denied because the applicant has many delinquent payments. In that case, the decision sparsity (that is, the SEV) would be I because only single factor was required to change the decision, overwhelming all possible mitigating factors. The framework of SEV thus allows us see sparsity of models in a new light.
Prior to this work, SEV had one basic definition: is the minimal number of features we need to set to their reference values to flip the sign of the prediction. The reference values are typically defined as the mean of the instances in the opposite class. This calculation easy to understand, but somewhat limiting because the reference could be far in feature space from the point being explained and the explanation could land a low density area where explanations are not credible. As an example, for the loan decision for 21 year old applicant, SEV could create counterfactual such as "Changing the applicant's s 3-year credit history to 15 years would change the decision." " While this counterfactual is valid, faithful, and sparse, it is not close because the distance between the query point and the counterfactual is so large (3 years to 15 years). In addition, this explanation is not credible because the proposed changes the features lead to unrealistic circumstance 6-year-olds do not typically have credit. That is, the counterfactual does not represent a typical member of the opposite class.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Lack of credibility is common problem for many counterfactual explanations [Mothilal et al. 2020 Wachter et al. 2017 Laugel et al., 2017 Joshi al. 2019]. Therefore, in this work, we propose to augment the SEV framework by adding two practical considerations, closeness of the reference point to the query, and credibility of the explanation, while also optimizing decision sparsity.
We propose three ways to create close, sparse and credible explanations. The first way is to create multiple possibilities for the reference, one at the center of each cluster of points (Section[4.1) Having a finite set of references keeps the references auditable, meaning that domain expert can manually check the references prior to generating any explanations. By creating references spread throughout the opposite class, queries can be assigned to closer references than before. Second, we allow the references to be flexible, where their position can be shifted slightly from a central location order to reduce the SEV (Section 4.4). The third way pertains to decision tree classifiers, where a reference point is placed on each opposite-class leaf, and an efficient shortest-path algorithm is used to find the nearest reference (Section 4.2). Table shows a query at the top, and some SEV calculations from our methods below, showing feature values that were changed within the explanation.
Table 1: An example for a query in the FICO Dataset with different kinds of explanations, SEVI represents the SEV calculation with one single reference using population mean, SEV represents the cluster-based SEV, SEV represents the flexible-based SEV. SEVT represents the tree-based SEV The columns are four features.
EXTERNAL
NUMSATISS
NETFRACTION
PERCENTTRADES NEVERDELQ
NUMPEATURE CHANGED
RISKESTIMATE
FACTORYTRADES
REVOLVINGBURDEN
Query
69.00
10.00
117.01
90
SEVI
72.65
21.47
22.39
90
SEVE
78.00
10.00
9.00
90
SEY 81.00
26.00
12.00
90
SEVT 69.00
10.00
117.01
100
In addition to developing methods for calculating SEV, we propose two algorithms to optimize a machine learning model to reduce the number of points that have high SEV without sacrificing predictive performance in Section 5) one based on gradient optimization, and the other based on search. The search algorithm is exact. It uses an exhaustive enumeration of the set of accurate models to find one with (provably) optimal SEV.
Our notions of decision sparsity are general and can be used for any model type, including neural networks and boosted decision trees. Decision sparsity can benefit any application where individuals are subject to decisions made from predictive models these are cases where decision sparsity is more important than global sparsity from the individual perspectives.
2 Related Work
The concept of SEV revolves around finding models that are simple, in that the explanations for their predictions are sparse, while recognizing that different predictions can be simple in different ways (i.e., involving different features). In this way, it relates to (i) instance-wis explanations (iii) local sparsity optimization Models, which seek to explain and provide predictions of complex models. We further comment these below.
instacc-wwise Explanations. Prior work has developed methods explain predictions of black boxes [e.g.. Guidotti et al.) 2018 Ribeiro et al. 2016 2018 Lundberg and Leel [017]] Baehrens) al. 2010 for individual instances. These explanations are designed to estimate importance of features, are not necessarily faithful to the model, and are not associated with sparsity in decisions, so they are fairly distant from the purpose of the present work. Our work on tabular data; there
is multitude of unrelated work on explanations for images leigellpicellaa et al., 2019 2020 and
text [e.g.. Lei et al. [0166] [i et al., [016)] (Trvvioo and Martins [020 BBsttngs al. [019 Yu et al.
2019 2021]. More closely related are counterfactual explanations, also called inverse classification
le.g.. Mothilal et al.
2020 Wachter et al. 2017 Lash et al. 2017 Sharma et al., 2024 Virgolin
and Fracaros 2023
Guidotti et al. 2019 Poyiadzi et al. 2020 Russell 2019 Boreiko et al. 2022 Pawelczyk al.) 2020). Counterfactual explanations are typically designed to
Laugel et al. 2017
find the closest instance to query point with the opposite prediction, without considering sparsity of

---

the explanation. However. extensive experiments Delaney et al. 2023 indicate that these "closest counterfactuals" tend to be unnatural for humans because the decision boundary is typically in region where humans have no intuition for why a point belongs to one class or the other. For SEV, on the other hand, reference values represent the population commons, so they are intuitive. Thus, SEV has two advantages over standard counterfactuals: its references are meaningful because they represent population commons, and its explanations are sparse.
Local Sparsity Optimization Models While there are numerous prior works on developing post-hoc explanations, limited attention has been paid to developing models that provide sparse explanations. We are aware of only one work on this, namely the Explanation-basee Optimization (ExpO) algorithm Plumb et al. [0200] that used neighborhood-fidee
regularizer to optimize the model to provide sparser post-hoc LIME explanations. Experiment in Appendix K our paper shows that ExpO is both slower and provides less sparse predictions than our algorithms.
Preliminaries and Motivation
The Sparse Explanation Value (SEV) is defined to measure the sparsity of individual predictions of binary classifiers. The point we are creating an explanation for is called the query. The SEV is the smallest set of feature changes from the query to a reference that can flip the prediction of the model. When we make a change to the query's 's feature, we align it to be equal to that of the reference point. The reference point is "commons," i..., prototypical point of the opposite class the query. In this section, we will focus on the basic definition of SEV, the selection criteria for the references, as well as three reference selection methods.
3.1 Recap of Sparse Explanation Values
We define SEV following Sunn et al. [2024]. For a specific binary classification dataset {æ; 1/ J= i= with each æ; E RP,
(0.1.1)
(1.1.1)
and the outcome of interest is y/: E 10, (This can be
(..0.))
(1.0.1)
extended to multi-class classification by providing counter- factuals for every other class than the query's 's class.) We predict the outcome using a classifier f X
{0,
(0.1.0)
Without loss of generality, in this paper, we are only interested in queries predicted as positive (class 1). We focus providing sparse explanation from the query to a reference that serves as a population commons, denoted r. Human studies [Delaney et al.) 2023) have shown that contrasting an instance with prototypical instances from another class provides more intuitive explanations than comparing it with instances from the same class. Thus, we define our references in the opposite class (negative class in this paper). To calculate SEV, we will align (i.e., equate) features from query x; and reference E one at a time, checking at each time whether the prediction flipped. Thinking of these alignment steps binary moves, it is convenient to represent the 2" possible different alignment combinations as vertices on the boolean hypercube. The hypercube is defined below:
(1,1.0)
(0,0.0)
(1,0,0)
Figure 1: SEV Hypercube
Definition 3.1 (SEV hypereube). A SEV hypereube Ljr,r for model f. an instance x, with label f(x,) = 1. and a reference r, is a graph with 2" vertices. Here is the number of features in æ, and b, E {0, 1 is Boolean vector that represents each vertex. Vertices u and are adjacent when their Boolean vectors differ in one bit, lbb,, bulloo = 1. O's in b, indicate the corresponding features are aligned, i.e., set to the feature values of the reference r, while I's indicate the true feature value of instance i. Thus, the actual feature values represented by the vertex is 2. b. @ Oz; + (1-b,) where O the Hadamard product. The score of vertex is f (ax also denoted as Cys.r(
The SEV hypercube definition can also be extended from a hypercube to a Boolean lattice as they have the same geometric structure. There are two vari- ants of the Sparse Explanation Value: one gradually aligns the query to the reference (SEV-), and the other gradually aligns the reference to the query (SEV+). In this paper, we focus on SEV-:
Table 2: Calculation process for SEV =
TYPE
HOUSING LOAN EDUCATION Y (RISK)
(1111) query SEV- Explanation
Rent > 10k High School
High
(0,1,1)
Owning > 10k High School
Low
(0,0,0) reference
Owning
<5k Master
Low
3

---

Definition 3.2 (SEV-). For positively predeictdd query (i.e., f(x;) = 1), the Sparse Explanation Value Minus (SEV)) the minimum number of features the query that must be aligned to reference to elicit negative prediction from f. It is the length of the shortest path along the hypercube to obtain a negative prediction,
SEV (f, r)
min Be (0.1))
11 --bllo s.t. (b,rr(b= =0.
Figure I and Table shows an example of SEV in credit risk evaluation setting. Since p 3, we construct a SEV hypercube with 2 = 8 vertices. The red vertex (1, corresponds to the query. The dark blue vertex at (0, O, 0) represents the prrediice reference value. The orange vertices are predicted to be positive, and the light blue vertices are predicted to be negative. To compute SEV-, we start at (1, 1, 1) and find the shortest path to a negatively-predicte
vertex. On this hypercube, (0, 1, 1) is closest. Translating this to feature space, this means that if the query's s housing situation changes from renting to the reference value "owning," would be predicted as negative. This means that SEV is equal to 1 in this case. The feature vector corresponding to this closest vertex (0, 1), is called the SEV- explanation for the query, denoted by a; reference r.
r.expl for
3.2 Motivation of Our Work: Sensitivity to Reference Points
Since SEV- is determined by the path on SEV hypercube and each hypercube is determined by the reference point, the SEV is therefore sensitive to the selection reference points. Adjusting the reference point trades off between sparsity (according to SEV and closeness (measured by lz. (see Section 6.I or & (see Section 6..4) distance between the query and its assigned reference point). Note that this trade-off exists because SEV tends to be small when the reference is far from the query. More detailed explanations, visualizations, and experiments are shown in Appendix B
Selecting References. The reference must represent the commons, meaning the negative population, and the generated explanations should represents the negative populations as well. Morcover, the negative population may have subpopulations: c.g., Diabetes patients may have higher blood glucose levels, while hypertension patients have higher blood pressure. To have meaningful coverage of the negative population, in this work, we consider multiple references, placed within the various subpopulations. This allows each point in the positive population to be closer to a reference. Let R denote possible placements of references. For query I,, individual-specific reference r; R for æ; is chosen based on three criteria: it should be nearby (i.e., close), and should provide sparse and reasonable explanation. That is, are looking to minimize the following three objectives over placement of the reference r;:
| R (Closeness)
SEV (f, -P(x; -(2xpphri1 (Negated Credibility),
(Sparsity)
(2)
(3)
with the constraint that the references obey auditability, meaning that domain experts are able to check the references manually, construct them manually. The function (fV x; r;) in (2) represents the SEV computed with the given function f. query 2;, and the individual-specific reference r; for generating the hypercube. expl.rr is the sparse explanation for the sample H;, and P(- in the definition of credibility represents the probability density distribution of the negative population and P( ((ppppl.rr X-) is the density of the negative distribution at x; x. expl.r: is in high-density region.
expl.r: P(a expl.rr (X-) ) is large,
4 Meaningful and Credible SEV
We now describe cluster-based SEV, which improves closeness at the expense of SEV, and its variant, tree-based SEV, which improves all three objectives and computational efficiency. We also present methods improve the credibility and sparsity of the explanations.
4.1 Cluster-based SEV: Improving Closeness

---

This approach creates multiple references for the nega- tive population. A clustering algorithm used to group negative samples, and the resulting cluster centroids are assigned as references. A query is assigned to its closest cluster center:
2000
Queries
1000
0
-100
2000
T: arg min | ll2
3300
PEC
4000
where C is the collection of centroids obtained by clustering the negative samples. We refer to the SEV- produced by the grouped samples cluster-based SEV, denoted SEVO. Figure 2 illustrates the calculation of SEV for two examples located in two different centroids. A red dot represents a query, while a blue dot represents a reference. For each instance. it selects the closest centroid and considers the SEV hypercube, where each cyan point represents a negatively predicted vertex and each pink point represents a positively predicted vertex. We deduce by following the red lines that the SEVê for the two queries are and 1, respectively. The cluster centroids should serve as a cover for the negative class. To ensure that the cluster centroids have negative predictions, we use the soft clustering method Bezdek et al. [9844 to constrain the predictions of the cluster centers. Details are in Appendix C
x
References
Figure 2: Cluster-based SEV
4.2 Tree-based SEV: SEVE Variant with Useful Properties and Computational Benefits
Tree-based SEV is a special case of cluster-based SEV, where we consider each negative leaf as a reference candidate, and find the sparsest explanation (path along the tree) to the nearest reference. Here, SEV and tu distance (i.e., edit distance) are equivalent. That is, we find the minimum number of features to change in order to achieve a negative prediction.
Iniemal rode
N
Negotive Node
BLLK
Negative Paahs lidoo No Nogatise Iush Below
6
We denote SEVT as the SEV- calculated based on this process. Here, we assume that trees have no trivial splits where all child leaves make the same prediction. If so, we would collapse those leaves before calculating the SEV". The first theorem below refers to decision paths that have negatively predicted child leaves. This is where taking one different choice at an internal split leads to negative leaf.
Figure 3: SEVT Preprocessing
Theorem 4.1. With a single decision classifier DT and a positively-predicets query I, define N as the leaf that captures it. If N; has a sibling leaf. any internal node in its decision path has negatively -preiccced child leaf. then SEVT is equal to
Nagatii (RLLIKIU
The second theorem states that SEV- and minimum edit distance from the query to negative leaves are equiv- alent.
Elspettmiian
Nogutiva Nade
Positive Nods
(RLM))
Negative
Feature Changed
Theorem 4.2. With single decision tree classifier DT and a cesttively-predictes query V; with the set of all negatively predicted leaves as reference points. both SEV and the En distance (edit distance) between the query and the SEV- explanation minimized.
Obesit
Chanit
Figure 4: Efficient SEVT calculation: Query (node ① has SE which goes to node 10). The path to this node is
The proofs of those two theorems are shown in Ap- pendix D and M The structure of tree models yields an extremely efficient way to calculate SEV-. We per- form an important preprocessing step before any SEV-
recorded as LL at node 3 which is along the decision path to node
calculations are done, which will make SEV- easier to calculate for all queries at runtime. At each internal node, we record all paths to negative leaves anywhere below in the tree. This is described in Algorithm in Appendix E E.g., if the tree has binary splits, path from an internal node to a leaf node might require us to go left, then right, then left. that case, we store LRL on this internal node to record this path. Then, when a query arrives at runtime (in positive leaf, since it has positive prediction), we traverse directly up its decision path all the way to the root node. For all internal nodes in the decision path, we observe distances to each negative leaf, which were stored during
5

---

preprocessing. We traverse each of these, and the minimum distance among these is the SEV-. This described in Algorithmmjin Appendix EE and illustrated in Figure 4 Note that we actually would traverse to each negative node because some internal decisions might not need to be changed along the path. In the example in Figure
4 we change the split at node 3 and use the value that the query already has for the split at node 6) landing in node (10, so SEV is not 2.
Table Illustration of SEVT calculation.
# CHANGED CONDITION
HYPER- TENSION
HYPER- LIPIDEMIA
HAVE STROKE
ACTION
DIABETES
OBESITY
(SEV)
Instance
Check
No
Yes
No
Yes
Yes 7
+3) 7 node (&
Flip at
Check L.L.
No
Yes
Yes
No 10
1
node 3
3 0-0610
Flip 3 (Unchanged)
Flip at node
Check LR
Yes
No
No (
2
1
5
Flip L
Flip at
2
Check LLR
Yes
Yes
No Flip at
No
2
4 9
Flip ( (Unchanged)
Table 3 walks through the calculation again, using the names of the features (hypertension, diabetes, etc.). On the first action line, the decision path to the query is ( That means check ! and (3) for negative paths, yielding path LL. We flip node (3) (change Hyperlipidemia to 'yes') and follow the LL path. We do not change Obesity get to the negative node, so we record the SEV" as in that row. In our implementation, we simply stop when we reach an SEVT=1 solution, but we will continue in order to illustrate how the calculation works. We go up to node 1 and repeat the process for the LR and LLR paths. Those both have SEVT=2.
Note that the reference can be any point within the leaf; if the leaf is defined by thresholds such as 3 < 21 < 5 and 222 > 7, then any point satisfying those conditions a viable reference. Given a query, the algorithm flips some of its feature values to satisfy conditions of leaf with the opposite prediction. Since any point in the leaf is a viable reference, we could choose the median/mean values of points in the leaf as the references, fast calculation of SEV-T.
more meaningful value. That choice will not influence the
4.3 Improving Credibility for All SEV Calculations
As we mentioned in Section 3.2. the credibility objective encourages explanations to be located in high-density region the negative population. Previous SEV definitions focus on sparsity and closeness objectives, but did not consider credibility. It is possible to increase credibility easily while constructing an explanation: if the explanation veers out of the high-density region, we continue walking along the SEV hypercube during SEV calculations. Specifically, we continue moving towards the reference until the vertex in a high-density region. Since the reference is in a high- density region, walking towards it will eventually lead to high-density point. The tree-based SEV explanations automatically satisfy high credibility:
Theorem 4.3. With a single sparse decision tree classifier DT with support at least in each negative leaf. the SEY" explanation for query x; always satisfies credibility at least S. where N the total number of negative samples.
This theorem can be easily proved because SEV- explanations generated by SEVT are always the negative leaf nodes (which are the references), and the references are located in regions with support at least S by assumption.
4.4 Flexible Reference SEV: Improving Sparsity
From Section 3.2 we know that queries further from the decision boundary tend have lower SEV-. Based on this, we introduce Flexible Reference SEV (denoted SEV*), which moves the

---

reference value slightly in order to achieve lower value of the model output f()) given a reference r, and the decision function for classification f(-). which, in turn, likely to lead lower SEV
The optimization for finding the optimal reference is: r" E arg min, f(r) s.tl|r lox S & where the arg min is over reference candidates that are near the original reference value P. The flexibility threshold OF represents the flexibility allowed for moving the reference within a ball. We limit flexibility so the explanation stays meaningful. Since it is impractical to explore all potential combinations of feature-value candidates, we address this problem by marginalizing. Specifically, we optimize the reference over each feature independently. The detailed algorithm for calculating Flexible Reference SEV, denoted SEV", is shown in Algorithm| | in Appendix D In Section 6.2 show that moving the reference slightly can sometimes reduce the SEV, improving sparsity.
5 Optimizing Models for SEV
Above, we showed how to calculate SEV- for a fixed model. this section, we describe how to train classifiers that optimize the average SEV- without loss in predictive performance. We propose two methods: minimizing an aasy-oo-ppiimize surrogate objective (Section [.T] and searching for models with the smallest SEV from "Rashomon set" of qqually-good models (Section 5.2). In what follows, we assume that SEV was calculated prior to optimization, that reference points were assigned to each query, and that these assignments do not change throughout the calculation.
5.1 Gradient-based SEV Optimization
Since we want to minimize expected test SEV the most obvious approach would be to choose our model f to minimize average training SEV However, since SEV calculations are not differentiable and they are combinatorial in the number of features and data points, this would be intractable. Following Sun al. [2024), we instead design the optimization objective penalize each sample where SEV is more than 1. Thus, we propose the loss term:
(SEV_AIL OIL (f)
n Σ max min
min (11-eej f(1-)))oz 0.5)
where e, is the vector with in the jth coordinate and O's elsewhere, n+ is the number of queries, and the reference point r; is specific to query x, and chosen beforehand. Intuitively, f(11 e,) O + e, O F:) is the function value of query æ; where its feature j has been replaced with the reference's feature j. miny=1....pp f(11 -e,) @ æ; + ej O.; chooses the variable to replace then when this replacement is made, the point
that most reduces the function value. If the SEV now is on the negative side of the decision boundary and f is less than 0.5, in which case the max chooses 0.5. If SEV- is more than 1, then after replacement, will still predict positive and be more than 0.5, in which case, its value will contribute to the loss. This loss is differentiable with respect to model parameters except the "corners" and not difficult to optimize.
To put these into an algorithm, we optimize a linear combination of different loss terms,
min LCC (f) + C1LSEVAAILOp--0 (f) JEF
where bCE is the Binary Cross Entropy Loss to control the accuracy of the training model and F is a class of classification models that estimate the probability of belonging to the positive class. (SEV (SEV_AIL_ON Apr- is the loss term that we have just introduced above. C₁ can be chosen using cross- validation. We define All-Opt method is not only effective shrinking the average SEV but often attains the minimum possible SEV- value of for most or all queries.
the method that optimizes (4) Our experiments show that this
5.2 Search-based SEV Optimization
As defined in Section 4.2 our goal is to find model with the lowest average SEV- among classifica- tion models with the best performance.
The Rashomon set [Semenova al. 2022 Fisher et al. 2019 defined as the set of all models from given class with performance approximately that of the best-performing model. The first method
7

---

that stores the entire Rashomon set of any nontrivial function class is called TreeFARMS [Xin et al. 2022], which stores all good sparse decision trees in data structure. TreeFARMS allows us to optimize multiple objectives over the space of sparse trees easily by enumeration of the Rashomon set to find all accurate models, and loop through the Rashomon set to optimize secondary objectives. We use TreeFARMS and search through the Rashomon set for a model with the lowest average SEV-
n Σ SEV (f.x;) JER
min
TE
where the Rashomon set Ryet and where we use SEVT as the SEV- for each sparse tree in the Rashomon set. Recall that Algorithms 2 and 3 show how to calculate SEVT. We call this search-based optimization as TOpt.
6 Experiments
Training Datasets To evaluate whether our proposed methods would achieve sparser, more credible
and closer explanations, we present experiments seven datasets: (i) UCI Adult Income dataset
for predicting income levels [Dua and Grafi (017). (ii) FICO Home Equity Line of Credit Dataset
for assessing credit risk, used for the Explainable Machine Learning Challenge (FICO 2018). (iii)
UCI German Credit dataset for determining creditworthiness [Dua and Grafi 2017]. (iv) MIMIC-III
dataset for predicting patient outcomes intensive care units [Johnson et al. 2016a bj. (v) COMPAS
dataset (Jeff' Larson and Angwin 2016 Wang et al., 2022a] for predicting recidivism, (vi) Diabetes
dataset (Strack et al.
[ [2014] for predicting whether patients will be re-admitted within two years, and
(vii) Headline dataset for predicting whether the headline is likely to be shared by readers [Chen
ct al.
2023 Additional details on data and preprocessing are in Appendix [A]
Training Models For SEVR, trained four baseline binary classifiers: (i. ii) logistic regression classifiers with & (L.ILR) and f2 (I.2IR) penalties, (iii) gradient boosting decision tree classifier (GBDT), and (iv) a 2-layer multi-layer perceptron (MLP), and tested its performance with SEVF added, and the credibility rules added. In addition, we trained All-Opt variants of these models in which the SEV penalties described in the previous sections implemented. For SEVT methods, compared tree- models from CART, C4.5, and GOSDT (Lin et al., 2020 McTaviih et al. 2022 with the TOpt method proposed in Section 5.2 Details on training the methods is in Appendix F
Evaluation Metries To evaluate whether good references are selected for the queries, evaluate sparsity and closeness (i.c., similarity of query to reference). For sparsity, we use the average number of feature changes (which is the same as lu norm) between the query and the explanation; for closeness, we use the median foo norm between the generated explanation and the original query as the metric for SEV". For tree-based models, to norm are equivalent; for credibility, we need some way of estimating P(- since we cannot observe it directly, so trained Gaussian mixture model the negative samples of each dataset, and used the mean log-likelihood of the generated explanations as the metric for SEV and SEVF, for TOpt, since it has already been sparse decision tree, then we don't 't need to calculate the credibility.
query only SEV" as the metric since SEV" and
6.1 Cluster-based SEV shows improvement in credibility and closeness
Let us show that SEVe provides improved explanations. Here, we calculated the metric for different SEV variants, SEV and SEV (SEV (SEV with flexible reference), and compared to the original SEV1, where SEV' is defined as the SEV- calculation with single reference generated by the mean value of each numerical feature and mode value of each categorical feature of the negative population, as done in the original SEV paper [Sun et al. 2024 under various datasets and models.
Figure 5a shows the relationship between spasity and variants, the scatter plot between mean SEV- and mean loo for each explanation generated by different variants. We find that SEV improves closeness, which was expected since the references were designed to be closer to the queries. Interestingly, SEV sometimes has lower decision sparsity than SEV1, SEVe was designed to trade off SEV- for closeness, so it surprising that sometimes performs strictly better on both metries, particularly for the COMPAS, Diabetes, and German Credit datasets.
8

---

COMPAS
Dlabebes
Aduit
COMPAS
Pabetes
RCD
25
20
-
Headlin
525 1.44
Genman
13 Headline
10
us3 MVVIC
3000
-10
20)
1.00
Mean
Moas
SEV
SEV
Mean
Mean
(a) Sparsity (SEV-) and Closeness (Lxa)
(b) Sparsity (SEV)) and Credibility log-likelihood)
Figure 5: Explanation performance under different models and metrics. We desire lower SEV for sparsity, lower Lo for closeness and higher log likelihood for credibility (shaded regions)
Interestingly. we also find that even though we do not optimize credibility for our model, Figure 5b shows that SEVe improves credibility, particularly for the Adult, German, and Diabetes datasets by plotting the relationship between mean SEV and mean log-likelihood of the generated explanations. is reasonable since the references are the cluster centroids for the negative samples, so the expla- nations more likely to be located in the same high-densit area. More detailed values for those methods and metrics are shown in Appendix H
6.2 Flexible Reference SEV can improve sparsity without losing credibility
In Section 4.4 we proposed the flexible reference method for sparsifying SEV explanations, which moves the reference slightly away from the decision boundary. The blue points Tigure5aalnn (bb have already shown that with small modification of the reference, the credibility of the explanations not affected. Figure 6a shows how SEV- and credibility change as we increase flexibility; SEV- sometimes substantially decreases while credibility is maintained.
Models
Adutt
Dinbbet
0.025
GBOT
log Belhoos
1001
SEV change rate
0.000
0.75
1ce"
-1087
1350
-0.025
0.50
MLP
-12e1
0.050
llailhod
0.25
Datasets
Adult
Carman
Headline
MIIIC
-0.100
0.00
MIMC
bood
Ice*
-0.125
COMPAS
-100"
-.50
Diebetes
SEVL
Rexibiiity
Rexibiliyy
FICO
feature changed
25
fastuure changed
feature changed
(a) SEV /Credibility change rate for varying flexibility (b) Median Log likelihood and of features changed
Figure (a) Sparsity and Credibility a function of the change of flexibility level (0 to 5% (96110%/0%%) under different models and datasets (b) The median bog-likelihood and number of features within different counterfactual explanations. Points the upper left corner are desired.
6.3 SEV provides the sparsest explanation compared to other counterfactual explanations
Recall that SEV- flips features of the query to values of the population commons. This can be viewed as a type of counterfactual explanation, though typically, counterfactual explanations aim to find the minimal distance from one class to another. In this experiment, we compare the sparsity of SEV- calculations to that of baseline methods from the literature on counterfactual explanations, namely Watcher WWachter et al. 2017], REVISE [Joshi al. 2019). Growing Sphere (Laugel et al. 2017)) and DiCE Mothilal et al. 2020].
Figure 6b shows sparsity and credibility performance of all counterfactual explanation methods on different datasets under & logistic regression (other information, including Eor norms for counterfac- tual explanation methods, is in Appendix G All SEV variants are in warm colors, while competitors are cool colors. SEV- methods have the sparest explanations, followed by DICE. (A comparison of SEV- to DiCE is provided by Sun et al. (2024)) .) We point out that this comparison was made on

---

methods that were not designed to optimize explamation sparsity. Importantly sparsity is essential for human understanding [Rudin al., 2022]. Moreover, it has been shown that SEV (especially SEV*) would have more credible explanations than competitors, while explanations remain sparse.
6.4
All-Opt" and TOpt optimize SEV -preserving model performance, explanation closeness and eredibility
Even without optimization, our SEV variants improve decision sparsity and/or closeness. If we are willing retrain the prediction model as discussed in Section 5 we can improve these metrics further, creating accurate models with higher decision sparsity. Figure 7a shows that gradient-baa SEV optimization can reduce the SEV without harming the closeness metric (foa) and the credibility metrics bog-likelihood). The slashed bars represents the SEV for and log likelihood metrics before optimization using different models, while the colored bars are the results after optimizing with - We have also compared our results with ExpO [Plumb et al. 2020), which is optimization method that maximizes the mean neighborhood fidelity of the queries, but we have found that explanations are not sparse, and it requires long training times; the detailed results are shown Appendix
0.0
TRAIN AcC
TEST ACC
MEAN SEVT
Whelmood
CART
0.71 0.01
0.71
0.03
SEV-1 optimized
C4.5
0.71 0.01
0.71 + 0.01
1.13 0.05
UR
SEV C Optimized
GOSDT
0.70
0.70 0.01
1.08 0.02
TOpt
0.70
0.70
1.00 0.00
(a) All-Opt
Performance
(b) SEV"
performance on different tree-based models
Figure 7: (a) SEV- and foo before and after All-Opt on the FICO Dataset. Slashed bars are before, solid color is after. (b) All tree-based models with similar accuracy have low SEVT.
For the Tree-based SEV, we have applied the efficient computation procedure to different kinds of tree-based models, and compared them with the search-based optimization method (TOpt) for trees in Section The search-based algorithm works perfectly in finding good model without performance loss. It achieves perfect average SEV score of 1.00.
Conclusion
Decision sparsity can be more useful than global model sparsity for individuals, as individuals care less about, and often do not even have access to, the global model. We presented approaches to achieving high decision sparsity, closeness and credibility, while being faithful to the model. One limitation of our method is that causal relationships may exist among features, invalidating certain transitions across the SEV hypercube. This can be addressed by searching across vertices that do not satisfy the causal relationship, though requires knowledge of the causal graph. Another limitation is that to make the explanation more credible, the threshold to stop searching the SEV hypercube not easy determine. Future studies could focus on on these topies. Overall, our work has the potential to enhance wide range of applications, including but not limited to loan approvals and employment hiring processes. Improved SEV translates directly into explanations that simply make more sense to those subjected to the decisions of models.
Acknowledgement
We acknowledge funding from the National Science Foundation under grants DGE-2022040 and CMMI-2323978.
10

---

References
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society (Series B), 1996.
Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistics Surveys, 16(none):1 - 85, 2022.
W James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi- and Bin Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences, ((6(44):2207-222086 2019.
Yiyang Sun, Zhi Chen, Vittorio Orlandi, Tong Wang, and Cynthia Rudin. Sparse and faithful explanations without sparse models. In Proceedings of Artificial Intelligence and Statistics (AISTATS), 2024.
Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pages 607-617, 2020.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law & Technology, 31: 841, 2017.
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. Inverse classification for comparison-biee based interpretability in machine learning. arXiv preprint arXiv:1712.08444 08443,, 2017.
Shalmali Joshi, Oluwasanmi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep Ghosh. Towards realistic individual recourse and actionable explanations in black-box decision making systems. arXiv preprint arXiv: /ee.//9979.99. 2019.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Pedreschi Dino. A survey of methods for explaining black box models. ACM Computing Surveys, 51(5), 2018.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, 2016.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin, Anchors: High-precision model-agnostic explanations. In Proceedings of the 32nd AAAI Conference Artificial Intelligence, 2018.
Scott M Lundberg and Su-In Lee. Unified Approach to Interpreting Model Predictions. In Advances in Neural Information Processing Systems, pages 4765-4774, 2017.
David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus- Robert Müller. How to explain individual classification decisions. Journal of Machine Learning Research, 11:1 11:1803-1831, aug 2010.
Andrea Apicella, Francesco Isgrò, Roberto Prevete, and Guglielmo Tamburrini. Contrastive explana- tions to classification systems using sparse dictionaries. In Image Analysis and Processing-ICIAP 2019 20th International Conference, Trento, Italy, September 9-13, 2019, Proceedings, Part 20, pages 207-218. Springer, 2019.
A. Apicella, F. Isgrò, R. Prevete, and G. Tamburrini. Middle-level features for the explanation of classification systems by sparse dictionary methods. International Journal of Neural Systems, 30 2050:405 July 2020.
Tao Lei, Regina Barzilay, and Tommi Jaakkola. Rationalizing neural predictions. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 107-117, 2016.

---

Jiwei Li, Will Monroe, and Dan Jurafsky. Understanding neural networks through representation crasure. arXiv preprint 112.v:161..08220, 2016.
Marcos Treviso and André FT Martins. The explanation game: Towards prediction explainability through sparse communication. In Proceedings of the Third Blackbox NLP Workshop Analyzing and Interpreting Neural Networks for NLP, pages 107-118, 2020.
Jasmijn Bastings, Wilker Aziz, and Ivan Titov, Interpretable neural predictions with differentiable binary variables. arXiv preprint arXiv:1905.08100 2019.
Mo Yu, Shiyu Chang, Yang Zhang, and Tommi S Jaakkola. Rethinking cooperative rationalization: Introspective extraction and complement control. arXiv preprint arXiv:1910.13299 2019.
Mo Yu, Yang Zhang, Shiyu Chang, and Tommi Jaakkola. Understanding interlocking dynamics of cooperative rationalization. Advances in Neural Information Processing Systems, 14:22222-12835 2021.
Michael T Lash, Qihang Lin, Nick Street, Jennifer G Robinson, and Jeffrey Ohlmann. Generalized inverse classification. In Proceedings of the 2017 SIAM International Conference on Data Mining, pages 162-170. SIAM, 2017.
Shubham Sharma, Alan Gee, Jette Henderson, and Joydeep Ghosh. Faster-ce: fast, sparse, transparent, and robust counterfactual explanations. In IFIP International Conference on Artificial Intelligence Applications and Innovations, pages 183-196. Springer, 2024.
Marco Virgolin and Saverio Fracaros. On the robustness of sparse counterfactual explanations to adverse perturbations. Artificial Intelligence, 316: 2023.
Riccardo Guidotti, Anna Monreale, Fosca Giannotti, Dino Pedreschi, Salvatore Ruggieri, and Franco Turini. Factual and counterfactual explanations for black box decision making. IEEE Intelligens Systems, 34(6):14-22 2019.
Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguez, Tijl De Bie, and Peter Flach. FACE: Feasible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, page 344-350. Association for Computing Machinery, 2020.
Chris Russell. Efficient search for diverse coherent explanations. Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 20-28, 2019.
Valentyn Boreiko, Maximilian Augustin, Francesco Croce, Philipp Berens, and Matthias Hein. Sparse visual counterfactual explanations in image space. In Pattern Recognition: 44th DAGM German Conference, DAGM GCPR 2022, pages 133-148, 2022.
Martin Pawelezyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counterfactual explanations for tabular data. In Proceedings of the Web Conference 2020, pages 3126-3132, 2020.
Eoin Delaney, Arjun Pakrashi, Derek Greene, and Mark T Keane. Counterfactual explanations for misclassified images: How human and machine explanations differ. Artificial Intelligence, 324: 103995, 2023.
Gregory Plumb, Maruan Al-Shedivat, Ángel Alexander Cabrera, Adam Perer, Eric Xing, and Ameet Talwalkar. Regularizing black-box models for improved interpretability. Advances in Neural Information Processing Systems, 33: 13:10066-10536 2020.
James C Bezdek, Robert Ehrlich, and William Full. Fem: The fuzzy c-means clustering algorithm. Computers & Geosciences, 10(2-3):191-200 1984.
Lesia Semenova, Cynthia Rudin, and Ronald Parr. On the existence of simpler machine learning mod- cls. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1827-1858, 2022.
Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models are wrong, but many are useful: Learning a variable's s importance by studying an entire class of prediction models simultaneously. Journal of Machine Learning Research, 20(177):1-81 2019.
12

---

Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, and Cynthia Rudin. Exploring the whole rashomon set of sparse decision trees. Advances Neural Information Processing Systems, 35:14071-14084, 2022.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL BttLLatttt//rchee...eee
edu/ml
FICO. Explainable machine learning challenge, 2018. URL URL.attsss//ommmiiyyy........
explainable--ann -ea-iaaabeemmmmmieeeeeee -eato-eeee-aeeee--aaa---------
A. Johnson, Pollard, and R. Mark. MIMIC-III clinical database. htttps///byssoonet.or
content/miiiciit// 2016a.
Alistair E. W. Johnson, Tom J. Pollard, Lu Shen, Li wei H. Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G. Mark. MIMIC-III, a freely accessible critical care database. Scientific Data, 3(1), May 2016b.
I Lauren Kirchner Jeff Larson, Surya Mattu and Julia Angwin. How we analyzed the COMPAS recidivism algorithm. ProPublica, 2016.
Caroline Wang, Bin Han, Bhrij Patel, and Cynthia Rudin. In Pursuit of Interpretable, Fair and Accurate Machine Learning for Criminal Recidivism Prediction. Journal of Quantitative Criminology, pages 1-63, 2022a.
Beata Strack, Jonathan P. DeShazo, Chris Gennings, Juan L. Olmo, Sebastian Ventura, Krzysztof J. Cios, and John N. Clore. Impact of HbAlc measurement hospital readmission rates: Analysis of 70, 000 clinical database patient records. BioMed Research International, 2014:1-11, 2014.
Xi Chen, Gordon Pennycook, and David Rand. What makes news sharable social media? Journal of Quantitative Description: Digital Media, 3, 2023.
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pages 6150 61600 PMLR, 2020.
Hayden McTavvih, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast sparse decision tree optimization via reference ensembles. In Proceedings of the AAAI conference on Artificial Intelligence, volume 36, pages 9604-96011 9613, 2022.
Chudi Zhong. Zhi Chen, Jiachang Liu, Margo Seltzer, and Cynthia Rudin. Exploring and interacting with the set of good sparse generalized additive models. Advances in Neural Information Processing Systems, 36, 2024.
Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimen- sion reduction tools work: An empirical approach to deciphering t-sne, umap, trimap, and pacmap for data visualization. Journal of Machine Learning Research, 22(201):1-73, 2021.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn; Machine learning Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Zijie J Wang, Chudi Zhong, Rui Xin, Takuya Takagi, Zhi Chen, Duen Horng Chau, Cynthia Rudin, and Margo Seltzer. Timbertrek: Exploring and curating sparse decision trees with interactive visualization. In 2022 IEEE Visualization and Visual Analytics (VIS), pages 60 64. IEEE, 2022b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Martin Pawelczyk, Sascha Bielawski, Johannes van den Heuvel, Tobias Richter, and Gjergji Kasneci. CARLA: A python library to benchmark algorithmic recourse and counterfactual explanation algorithms. arXiv preprini
2021.
Gregory Plumb, Denali Molitor, and Ameet S Talwalkar. Model agnostic supervised local explana- tions. Advances in Neural Information Processing Systems, 31, 2018.
13

---

A Data Description and Preprocessing
The datasets were divided into training and test using 80-20 stratification. The numerical features were transformed by standardization to have mean of zero and a variance of one. The categorical features, which have different levels, transformed into k binary variables using one-hot encoding. The binary characteristics were transformed into single dummy variable using one-hot encoding. The sizes of the datasets before and after encoding are shown Table 4
PRE-ENCODED FEATURES
POST-ENCODED FEATURES
OBSERVATIONS
COMPAS
6,907
Adult
32,561
14
107
MIMIC-III
48,786
14
Diabetes
101,766
33
101
German Credit
1,000
59
FICO
10,459
23
23
Headlines
41,752
12
17
Table 4: Training Dataset Sizes
Below provide more details for each dataset.
COMPAS
The COMPAS dataset contains information on criminal recidivism Broward County, Florida [Jeff Larson and Angwin 2016). The goal of this dataset is to predict the likelihood of recidivism within a two-year period, taking into account the following variables: gender, age, prior convictions, number of juvenile celonies/misdeemeannn. and whether the current charge is felony.
Adult
The Adult data is derived from U.S. Census statistics, including information on demographies, education, employment, marital status, and financial gain/loss (Dua and Graff 2017). The target variable of this dataset whether an individual's salary exceeds $50,000.
MIMIC-III
MIMIC-III is a comprehensive database that stores a variety of medical data related to the experience of patients in the Intensive Care Unit (ICU) at Beth Israel Deaconess Medical Center [Johnson et 2016a The outcome of interest is determined by the binary indicator known as the "hospital expires flag," which indicates whether not patient died during their hospitalization. We chose the following set of variables as features: age, prei culos (pre-ICU length of stay), ges (Glasgow Coma Scale), heartrate_ __min, heartrate_max meanbp_min (min blood pressure), meanbp_ _mx (max blood pressure), resprate piniatteeenn,,,,eeee resprate, ___a__ma______________a__ tempe_min, _mmi,,nnn, tempo_ma _ax, urineoutput, mechvent (whether the patient on mechanical ventilation), and electivesurger (whether the patient had elective surgery).
Diabetes
The Diabetes dataset is derived from years (1999-2008) of clinical care 130 hospitals and integrated delivery networks in the United States (Dua and Graff 2017). It consists of more than 50 characteristics that describe patient and hospital outcomes. The dataset includes variables such as race, gender, age, admission type, time spent in hospital, specialty of admitting physician, number of lab tests performed, number of medication and so on. We con- sider whether the patient will return the hospital within 2 years binary indicator.
14

---

German Credit
The German credit data (Dua and Grafi 2017 uses financial and demographic indicators such as checking account status, credit history, employmen//mariaal status, etc., to predict whether an individual will default on loan.
FICO
The FICO Home Equity Line of Credit (HELOC) dataset (FICO) 2018 is used for the Explainable Machine Learning Challenge. It includes number of financial indicators, such the number of inquiries on a user's account, the maximum delinquency, and the number of satisfactory transactions, among others. These indicators relate different individuals who have applied for credit. The target variable is whether a consumer has been 90 or more days delinquent at any time within 2-year period since opening their account.
Headlines
The News Headline dataset [Zhong et al. 2024] is a survey data aimed at discovering what kind of news content is shared and what factors are significantly associated with news shar- ing. The survey includes several factors, including, age, income, gender, ethnicity, social protection.economii protection, truth ("What is the likelihood that the above headline is true?"), f familiarity ("Are you familiar with the above headline (have you seen or heard about before?)? )²), Importance ("Assuming the headline is completely accurate, how important would you consider this news to be?"), Political tical Concordance ("Assuming the above headline is com- pletely accurate, how favorable would you consider it to be for Democrats versus Republicans?"), The goal of this data set is to predict Sharing ("If you were to see the above article on social media, how likely would you be share it?"").
15

---

B Sensitivity of the reference points
In this section, we will mainly show how sensitive SEV is when we change the reference. Figure shows an example of this, where moving the reference further away from the query (from to the r') changes the SEV- from 2 to In this figure, the dark blue axes represent the feature values of different reference values, while the black dashed line represents the decision boundary of linear classifier. Areas with different colors represent data points with different SEV-. When the reference moves further from the decision boundary (from r to r'). the corresponding areas for SEV- will move away from the decision boundary. For example, the star located the yellow area has an SEV- of I instead of 2 when the reference moves from to r'. If the reference point is then the query needs to align the feature values along both x and y-axis to reach the SEV Explanation with reference (recall example of SEV- explanation in Figure in Section 3.2 which is the same point However, if the reference point is r', then the query only needs to align the feature value along the x-axis reach the SEV Explanation with SEV= 1, which is the light blue dot.
PESEY
SEV-22 SEV-
Path to decision
SEV Explanation with reference r'
F: SEV =1 r:: SEV =1
Decision Boundary
Path decision
SEV Explanation with reference
reference r
reference r'
Figure 8: SEV distribution
Experiments have also shown that moving data points closer to the decision boundary might increase
SEV The result the Explainable ML Challenge loan decision data (FICO 2018 shown in Table 5 demonstrates that altering the reference point may increase the average SEV (from 3 to 5), but also introduces "unexplainable" samples (meaning SEV- 210). Hence, SEV- is sensitive to the reference.
Table 5: SEV change by moving reference point 7 moving closer to the decision boundary
% OF SAMPLES
REFERENCE POINT
MEAN SEV
SEV
SEV
SEV
MODEL
23
26 6
> 10
L2LR
F
2.76
2.82
0
0
F
4.95
89.23
32.3
LILR
F
2.46
1.00
0
0
F
4.57
56.87
21.27
0
16

---

C Detailed Description for Score-based Soft K-Means
As we have discussed in Section 4.1 SEV needs to have negatively predicted reference points. Therefore, when clustering the negative population, it is necessary to avoid positively predicted cluster centers. However, for most of the existing clustering methods, it is hard to "penalize" the positive predicted clusters, or their assigned samples. Therefore, we have modified the soft K-Means [Bezdek et al. [984] algorithm so to encourage negative clustering results.
The original Soft K-Means (SKM) algorithm generalizes K-means clustering by assigning mem- bership scores for multiple clusters to each point. Given a data set X {01, 22, , Fna and C clusters, the goal is to minimize the objective function [U, V), where U = [Uy]] is the membership matrix and V (Vi,... ]c are the weighted cluster centroids. The objective is to minimize:
π J(U,
= ΣΣ
My
m
v, 11
(5)
i= 5=1
where Myy is the (soft) membership score of at; in cluster j:
(6)
-=1
and m > 1 is a parameter that controls the strength towards each neighboring point. When m Re 1, the SKM is similar to the performance of hard K-means clustering methods. When m for point i, it is considered to be associated with multiple clusters instead of one distinct cluster. The higher the value of m, the more a point is considered to be part of multiple clusters, thereby reducing the distinctness of each cluster and creating more integrated and interconnected clustering arrangement. To avoid the cluster group being predicted positively, we have given higher m for those positive samples. Therefore, if the samples are predicted as positive, it reduces the possibility that those positively predicted samples to group as a cluster, which we can replace m as m² for each instance a; as
(7) The value of min(f((x.) - 0.5,0} increases as æ; is classified as positive and further away from the decision boundary. As mn increases, the negatively predicted samples are more associated with one distinct cluster, while the positively predicted samples are associated with multiple clusters with smaller weight. This makes the cluster centers less likely to be influenced by positively predicted points. Thus, we can rewrite the objective of the soft K-Means algorithm can be modified as
m = 2m min (f(x.) - 0.5,0) 1.
J'U,V)) ΣΣ
(8)
We call this new objective function for encouraging negative clustering centers Score-based Soft K-Mcan (SSKM). In our experiments, the clustering is applied to the dataset after PaCMAP [Wang ct al.] 2021]. and the feature mean of all samples in cluster is considered as the cluster center of this cluster, which is eventually used as a reference point. The queries are assigned to reference points that are closest (based on & distance) to them in the PaCMAP embedding space for SEVE calculation. The reason why we would like to first embed the dataset is that the dimension of the datasets might be too high for direct clustering, and PaCMAP provides an embedding that preserves both local and global structure. Figure 9 shows the probability of the negative predicted instances, as well as the clustering results using different kinds of clustering methods. The red points and stars represent the positively predicted instances and cluster centers, while the blue ones are the negatively predicted instances and cluster centers. is evident from the Figure that that SKM is more likely to introduce positively predicted cluster centers, compared to SSKM.
When we calculate SEV in the experiments, all clustering parameters are tuned and fixed. For the rest of the datasets, the embedding using PaCMAP, and their clustering results for the negative population with their cluster centers, are shown in Figure TO The regions with different colors represent different clusters, the blue stars in the graphs are cluster centers, and the gray points within the graphs are positive queries. All those cluster centers can be constrained to be predicted as negative by tuning the hyperparameter for Score-based Soft K-Means. Note that if one of the cluster centers cannot be constrained to be predicted as negative even with high m, then it is reasonable to remove this cluster center when calculating S
17

---

probabiity querry
Clastering
Score Clusteiing
05
Figure The clustering results for FICO dataset. (Left) The probability distribution for the negatively labeled queries; (Middle) The clustering result for Original Soft K-Means Clustering; (Right) The clustering result for Score-based K-Means Clustering The red stars represent the positively predicted cluster centers, and the blue stars the negatively predicted cluster centers
COMPASO
CENDATIG CINCOS
MIVIC BIS CINsee
HOSSERD MANC CINsOe
Figure 10: Clustering Results for different datasets.
18

---

D Detailed Algorithm for Flexible-based SEV
This section presents how the flexible-based SEV (SEV") has done determine the flexible refer- ences. The key idea of finding the reference is to do grid search through each of the features in the training dataset based on the original reference, and find the feature values that has the minimum model outcome.
Algorithm Reference Search for Flexible SEV
1: Input: The negative samples X-, flexibility e, reference i,, grid size G
2: Output: Flexible reference F'
Initialization: 7' <-7 -
4: for each feature j E J, where rj is the reference value of feature j in X do [Quantile location of r
5: 4j + (xantile(Xx.700
6: BJ percentile (X, Qg +c) (The upper range]
7:
BJ + percentile (X, -) (The lower range)
8:
B Uniform| 13 1. = ,,
pla) + I(Fr,.... } ... f-]),g=111 G (Slight change to feature j for prediction)
9:
g' + arg min, p(9) (Find minimum model outcome)
10:
FJ B (Update for flexible references)
11:
12: end for
19

---

E Detailed Algorithms for Tree-based SEV
This section presents how the tree-based SEV is calculated through two main procedure: Algorithm
2 (Preprocessing) for collecting all negative pathways and assigning them to each internal nodes and Algorithm (Efficient SEV" Calculation) for checking all negative pathways conditions for each query and calculating the number of feature changes.
Algorithm 2 Preprocessing Information collection process for SEVT
1: Input: Decision tree DT'
2: Output: DT a dictionary of paths to negative predictions for each internal node encoding
3: nodes <- [DT.root]
4: begative_part + [
5: (Negative path collection procedure)
6: while nodes not empty do
7: [node, path] <- nodes.pop()
8: if node is negative leaf then
negative_ gegative__athhee aathh.append/path) 10: else if node is an internal node or root node then
9:
(A jdd the child nodes and the path to the node list nodes. appeee [node. weood.left.prr path+ "L"]) "R"])
12:
nodes. appent night..gght.pp...
14: else
Continue (if the leaf is positive, ignore it]
16: end if
end while
18: (Assign Negative Pathways to root or internal nodes)
19: DT + dict()
20: for each path in negative_ patt do
21: for 1,. ......athheegg.. do
22:
(Add the negative decision path for internal nodes)
23:
curr_ __ndnddd= + negative =
24:
{curr_ node is the encoded internal node, and negative path[i:] is negative decision path
below this node)
25: DT DT- (errccrr__odde anpendinegative_pallff
26: end for
27: end for
20

---

Algorithm 3 Efficient SEVT Calculation Negative Pathways Check
Input: DT: decision tree, D decision with paths negative predictions, query value
Di, DP; list of internal nodes representing decision process for æ; path;; the encoded DP;
2: Output: SEVT
3: INITIALIZATION: SEVT <- 0
4: decision Deccisio_pathhaoe + encoded( xx,)
5: (encoded(DTT. x;) is function to get the string representation of the query æ; node node for DT, e.g. "LR"."LL" mentioned in section 4.2)
6: for each internal node node in DP, do
7: if node has a sibling leaf node and is predicted as negative then
8: SEVT + (Based Theoerem 4.1
9: Break {SEVT=1 =1 is the smallest SEVT, no further calculation needed)
end if
11: encoded peccoded_ndee-eee encoded(D,, node) (Get the string representation of node)
12:
Legative_pathle +- DT (encodee _ndde] (Get the negative pathways encoded_node have) for each path in negative_ do
13:
{If the negative goes the same direction the decision path, we don't need calculate this path again)
[path[0] is the first character in path) if decision parceencocccddddeeeeeeeaeeee (parh) then Continue
16:
18:
end if
temp_sev
20:
[Go over the condition in the path)
[Check if query x; satisfies, it doesn't satisfies the condition, then femp_sev should add 1)
22:
for condition each path do if æ; doesn't satisfy condition AND æ; hasn't issn't been changed yet then temp_serr-eee sert-temp_see sev +1 end if end for
23:
24:
25:
26:
27:
SEVT< +- min(temp_sev SEVT (Update SEVT to be the samller one
28:
SEVT = then
29:
Break (SEVT=1 is the smallest SEYT, further calculation needed)
30:
end
31:
end for
32:
end for
21

---

F Model training and parameter selection
2011 implementations in Python. The logistic regression models L1 LR and L. LR were fit using regularization parameter C' = 0.01. The 2-layer MLP used ReLU activation and consisted of two fully-connected layers with 128 nodes each. It was trained with early stopping. The gradient-boosted classifier used 200 trees with max depth of 3. For tree-based methods comparisons, the decision tree classifiers were fit using sklearn [Pedregosa et al. (011] and TreeFARMS packages [Wang et al.) 2022b]. Since GOSDT methods require binary input, we used the built-in threshold guessing function in GOSDT binarize the features with set of parameters n_ est=500 and faax_deph=1.. All the models are trained using RTX2080Ti GPU, and with core in Intel(R) (Ron(R) Gold 6226 CPU @ 2.70GHz.
Bascline models were fit using sklearn Pedregoss
In order to test the performance of All-Opt all models mentioned above were trained by adding the SEV losses from Section [5 to the standard loss term (BCELoss). For GBDT, the training goal is to reweigh the trees from the baseline GBDT model. The resulting loss was minimized via gradient descent in PyTorch [Paszke et al., 2019). with batch size of 128, learning rate of 0.1, and the Adam optimizer. To maintain high accuracy. the first 80 training epochs are warm-up epochs optimizing just Binary Cross Entropy Loss classification (BCELoss). The next 20 epochs add the All-Opt terms and the baseline positive penalty term to encourage low SEV values. Moreover, during the optimization process,
important ensure that the reference has a negative prediction. the reference is predicted as positive, then the SEV- may not exist, and sparse explanation is no longer meaningful. Thus, we add a term to penalize the reference it receives positive prediction:
Poo
Σ max(f
8)
where 0 is margin parameter, usually 0 0.05. This term is (0.5 0) as long the reference is predicted negative. As soon as it exceeds that amount, it is penalized (inereasing linearly in ff)). To put these into an algorithm, optimize a linear combination of different loss terms,
min (fC + C1 Ci (f) + C26ros JEF
Therefore, we are tuning both C₁ and C2 to find model with sparser explanations without perfor- mance loss through grid search. For cluster-based SEV, the cluster centers are recalculated based on the new model every epochs.
22

---

G The sparsity and meaningful performance of different counterfactual explanation methods
In this section, we provide detailed information other kinds of counterfactual explanations generated by the CARLA package (aawelzyyk al. 202T] on different datasets for logistic regression models. Table 6 shows the number of features changed and the fo for different counterfactual explanations. These counterfactual explanations tend to provide less sparse explanations than other SEV variants shown in Section 6.3 For the & calculations, we consider only the numerical features, since the categorical features' too norm does not provide meaningful explanations. Moreover, we have calculated the average log-likelihood of the explanations using the Gaussian Mixture Model in scikit-learn/ Pedregosa al. [) The parameter n_ componeents for each dataset selected based on the clustering result mentioned in Appendix [ Here, we using the same Gaussian Mixture Model for evaluating whether the explanation is within a high-density region.
Table 6: Explanation performance in different counterfactual explanations
COUNTIRFACTUAL
MEDIAN
DATASET
MEAN txc
# FEATURES CHANGE
EXPLANATIONS
LOG-LIKELIHOOD
Adult
Growing Sphere
1.07 + 0.01
14++
345.03 + 34.19
DICE
0.78 0.02
0.12
-24752. 121752.12-2 452.47
REVISE
6.12
12.14 0.75
345.03 + 32.84
Watcher
0.01
6.00 0.00
345.12 34.19
SEV'
22.62 0.01
1.18
-24752. 452.47
SEV
0.00
0.02
156.88 59.67
COMPAS
Growing Sphere
0.001
0.000
10.47 1 0.00
DiCE
1.38
3,20
-6,68 = 0.02
REVISE
1.02
5.54 1: 0.63
-188 +: 0.21
Watcher
0.01
5.00 0.00
10.48 1 0.03
SEVI
2.31
1.22+
14.65 0.32
SEY
2.00
1.19+0.00 0.02
14.41 + 0.05
Diabetes
Growing Sphere
0.01
33.00 0.00
320.41 21.47
DiCE
0.12
2.76 0.15
74296.98
REVISE
0.80
15.84 0.02
320.41 + 16.73
Watcher
0.01
12 0.00
320.41 + 21.34
SEV1
2.10
1.63 1 0.01
309.56 1 15.32
SEV
2.112
1,28 1 0.02
320.71 +: 14.79
FICO
Growing Sphere
0.01+0001
23 0.00
10.93 + 0.42
DiCE
1.11
3.27100.17
20.11 0.3
REVISE
0.10
0.00
10.94 1
Watcher
0.01
23
10.94
SEV
1.00
2.76 1 0.02
20.11 1 0.32
SEV
1.001
2,21 1. 0.022
19.32 0.21
German Credit
Growing Sphere
0.01 1.002
20 0.00
52,20 0.02
DiCE
6.08
2,76 0.23
53908.77 78 3667 84
REVISE
0.16
7.65 + 0.12
-73492.06 492.45
Watcher
0.00
6.00 0.00
52.23 0.04
SEVI
0.08
1.51 + 0.02
-124914.32 792.52
SEY
3.2
1.17 0.02
50.21 + 0.32
Headline
Growing Sphere
0.01
1.00
-4.56 0.02
DiCE
0.02
2.79 + 0.14
-12.84 0.42
REVISE
1.81
15.93 0.24
-6.98 + 0.12
Watcher
0.01
12 0.00 0.00
-4.56 +: 0.02
SEV'
2.50
1.98 + 0.01
1.52 + 0.12
SEV
2.94
1.62 0.02 0.02
0.89 + 0.26
MIMIC
Growing Sphere
0.01 0.001
0.00
24.52 1 0.02
DiCE
1.34+00.2
6.47 + 0.24
26.55 - 0.02
REVISE
12
24.52 1
Watcher
0.01000000
12 0.00
24.52
SEVI
4.53 +53++0..9
1.18 + 0.02
20.11 +
SEV
1.98 1 0.133
1.19 0.02
-99332 0.15
23

---

H Detailed SEV for all datasets
In this section, we show how SEVI, SEV", SEV can increase the similarity metries reduce the sparsity explanations. All the models are trained and evaluated 10 times using different splits, and evaluated for their mean SEV", mean Lx. as well as their explanation time for each query.
Table 7 shows the model performance and SEV' on various datasets. SEV! is considered as a base case for other SEV- variants to compare with. Table shows that SEV1 yields very high Eo for each model, indicating a large distance between the query and reference, which implies low closeness according to Section 3.2
Table 8 shows the model performance and SEVO on different datasets. Similarly, The Mean SEV column reports the mean SEV for the model and the decrease in mean SEV in percentage compared to SEV! (reported in the parenthesis). The Mean Lo column reports the mean &oo and the percentage reduction compared to SEV!. On most datasets, SEVe increases, and fo decreases, which means that the model is providing both sparser and more meaningful explanations. For some datasets like Adult and MIMIC, the SEV increases, since the cluster-based reference points might be closer the decision boundary of the model as each query is trying to find the closest (in & distance) negatively predicted reference point, which might provide less sparse explanations.
Table 9 shows the model performance and SEV*+ r (SEV with variable reference) on various datasets with different flexibility levels. The Mean SEV* column reports the mean SEV for the model and the decrease in mean SEV in percentage compared to SEV' (reported in the parenthesis). The Mcan fo column reports the mean & and the percentage reduction compared to SEV'. It is evident that with SEV SEV decreases, but the lo norm will increase due to the flexibility of the features mentioned in section 4.4 The "flexibility used" column shows the proportion of queries using the flexible reference instead of the original one for calculating SEVE and the higher the proportion, the larger decrease in SEV- the model can achieve.
Table 7: The SEV' under different models
TRAIN ACCURALY
TEST
EXPLANATION TIME/10" ())
AVTRAGE
DATASET
MUDEL
ACCURACY
SEV
LIKELIHOOD
GBDT
0.3
0.0
18:28
07437.86 2718.7
LIIR
0.85 0.0
0.0
0.0-0.0
1.14-000 0.01
24.2
0.26 0.01
44735 07 1393
L2LR
0.85 4: 0.0
0.85 0.0
0.0
0.9 0.0
1.18 2.0
22.02 2: 2:27
0.16 0.01
-9220 12 1157.19
MLP
0.87
0.0
0.86 0.0
0.93 1 0.0
0.92 0.0
1,27-000 0.06
21.73
1:3.7
0.62 0.17
-67000 48 5500.26
CUMPAS
GEDT
0.7
1.00
IJIT
= D.11
01.7
2: 1.00
U.Y2
1:01
L10=000
1304 1:00
1.18 2 0.12
8.16 = U:Y
LIIR
0.68 + 0.0
0.67 = 0.01
0.75 + 0.0
0.72 - 0.01
1.25
175500.0 0.02
2.31 + 0.07
0.12 = 0.0
5.00 0.00
L2LR
0.0
0.67
0.73
0.72 0.01
1,26
0.09
0.01
5.19 1.0
MLPP
1.30=000
0.32
Diabetes
0.85
0LE83
1.30
0:00
264.7
230674
EII.R
0.62 0.0
0.62
0.66
0.66
0.0
1.62
0.01
2.6 0.00
106.63
79.70
20534
L2LR
0.62 11 0.0
0.62 0.0
0.96 1. 0.0
0.66
0.0
1.63
0.01
2.7 0.00
117.63
79.76
191117 45 1091 15
MLP
0.65 = 11.01
01664 = 0.0
0.71 01111
0.69
0.0
1.69
0.13
2.67 +0000
136.33
140.47
700066
2008 02
FICO
GBDT
0.71 0.0
0.7 = 0.0
0.78 1: 0.0
0.77 = 0.01
3.58
0.12
1.81 1:000
692.85
30.77
71113 1 8.02
LILR
(1.71 IIDII
I.. = 0.0
0.78 2: 0.0
0.77 = 1.01
2.47
0.11
1.81 0.07
100.83 = 30.77
S1.1 1 7.41
L2LR
0.72 1. 0.0
0.71 0.01
0.78 1
0.78 0.01
2.76
0.12
1.93 1.00
481.75
136.53
52.09 1
MLP
1.011
0.22
12.06
GBDT
0.77
0.10
1.87::0.00
75811
LILR
0.75
0.75
0.01
0.79
0.05
0.40
61237
L2LR
0.78 0.01
0.76
0,83 0.01
0.79
0.04
0.15-
3.08 0.42
1.34 0.96
1111946.21
5916.8
MLP
0.81 = 11.14
0.76 B000
0.87 01.14
0.78
- 1.004
1.6
0.19
2.60 +.045
7.68
6,00
119657 JNN 16828.67
Hondlnee
GRDT
0.52 0.0
0.81 - 0.0
U. 0
0.80
7 0.0
1.82
2.36
0002
16.25
2.46
905 340-2
LILR
(178 1: 0.D
IL78 1: 0.0
0.85 1 0.0
(185
0.0
1.92
0.01
2.51 1 0.02
6.73
1 0.38
-558 81 1. 287 68
L2LR
(1.88 0.0
I.78 0.0
0.86 + 0.0
0.80
0::0=1000 0.0
1.98
20:--000 0.01
2.5 0.02
9.21 0.49
555.96 + 286. 1G
MLP
0.53 0.01
0.81 0.0
0.01
0.89
0 0.0
2.03 0.03
2.31 0.07
26.25 2.45
-103.37 1. 316,22 6.22
MINIC
U.33
LILR
0.0
0.8 0.0
0.49
19.70
L2LR
0.I1
0,8 D.01
1.16
4.34 0.52
-19.60 0.49
MLPP
0.9
0.0 0.0
0.87 0.01
0.85 0.0
1.18 0.03
2.06 0.35
0.70 0.10
-17.25 1:255.1000 0.84
24

---

Table 8: The SEVO under different models
AVERAGE SBV
MEDIAN 120
DATASET
MODEL
ADCURACY
ADCURACY
AUC
AUC
TIME (10 ?)
LIKELIHOOD
Adult
GBDT
0.88 0.0
0.57 =:
0.93 a 0.0
0.93 1: 0.0
1.39113.01%)
2.41(-86.82%)
2.22 0.84
22974.51 5166000009))
0.85
0.9
2.05-91.538)
L2LR
0.85 0.0
0.85 =
0.9
1.34(13356%)
2.86(-87.364)
0.38 0.12
21033.54(57, 333%
MIPP
0.87 0.0
0.86 +
0.33++0.4
0.92 D.0
62622.5666)
0.100-76.258
1.18 0.53
23421, (760)995)
COMPAS
(52(-21:6318)
LILK
0:08
0.0
0.72
1.199-4.8%)
1.756-24.2498
0.01
5308 64%)
L2LR
0.68 1: 0.0
0.87 1: 0.02
0.73 0.0
0.72 0.01
1,22(-3.17%)
2.06(-14.288)
0.09 1: 0.01
5.98(15.22 32%)
MLP
0.69
0.74 0.01
1.31-3.7%)
1.82(-20.887
0.03
9.12(40.5286
LILR
0.62 0.0
0.62 O.D
0.66 0.0
0.66 B.Q
1.22(-24.68)
2.31(-11.88%)
2.1 0.4
3461 2799)
L2LR
0.62 0.0
0.02 =
0.66 0.0
0.60::0000
1,281-21
2.310-14.448)
3.8 1.26
14461 36024 3698)
72/83
FICO
GBDT
0.77 2:
0.72
0:0
2:
2.020-12.528)
23.31 8.88
50 522
LILR
0.71 1: 0.0
0.7 +: 0.0
0.78 0.0
0.77 1: 0.0
L.791-27.539
1.96).738))
3.11 1.02
77 53.45344665
13.0%)
0.81
2.15X-20.379
1.78-6.918)
Genman
GBDT
D:01
0.76 0:02
U.3U
U.77 0.03
1:226122.396
(73(-1299)
28478. 1.578866022
Credit
LILR
0.75 0.01
0.75
0.8 0.01
0.77 0.01
1.07-22077%%
1.2(-37,968)
0.05
23091 73163. 73163.1258
MLP
0.04
0.78 0.03
0.87 1 0.04
0.78 0.04
L.241-22.5%)
2.54)-3.58%)
0.24
10045. 69666.593
Headline
GBDT
U.82 = 0.00
U.S1 = 11.0
0.3 0.0
U.80
1,701-3.993
(118(-7.778)
0.36 0.4
0.78
0.78
0.85
1.62(-18.1889
2.9117
1.46
5000592000 19%
MLP
0.83 0:00
0.81 0.0
0.91 + 0.01
0.89
L67(-17.7%)
1999-16.089)
3,05 0.48
1956.8/0.005
MIMIC
GEDT
0.31
0.0
0.37 0.0.
0.85 6.0
1.1(2344)
01.722)
18.1.04.0%)
L2LR
0.89 0.0
0.89 =
+ 0.0
0.8 0.0
1.192.599%)
1.98/-54.389)
0.19 0.03
MLP
0.9 0:9 0.0
0.3 0.0
0.87 + 0.01
0.80 D.0
1.2364224))
1.66)71.18%)
0.33 0.07
-16,77(2.785)
25

---

Table 9: SEV2+F under different models
FLEX- IBILITY
TRAIN ACCURACY
TEST ACCURACY
TRAIN AUC
TEST
AVERAGE
MEDIAN
AVERAGE LoG-
EXPLANATION
DATASET
MODEr
AUC
SEY
LIKEL EROOD
10MF(10-S))
Aduli
GBDT
0.05
0.88 1.00
0.57 1: 0.0
6:93 1:0.
0.93 1:0.0
1.565.695)
0.95(-9488%
217733 14622.1198
3.98 1: 0.45
0,10
1:00
0.0
0.58
0.53 4:0.
1.2954.88%
0.956-94.855
0.32
0.20
0.0
0.57
0.0
0.53 +00
1.294488%)
0.96(-94.55%)
1761116900
363++ 0.29
01/
0:85 #:00
0385
10:0
0::0000
0.55
01901-96.199)
10 0.01
0.10
0.85 1:00
0:85 0.0
0.0
0.9
1.1K4. 39%)
0.961-96 (396)
-201 64 SOX 859)
0.04
0.20
0.85 4.00
4: 0.0
0.0 0.00
0.5 4. 0.0
1.19%4399%
0.971 95.99959
301253 002265.0032 19%)
0.91 4: 0.04
12LR
000
0.85 +000
0085 0.3
0.3 +000
015 + 0.0
2.371-9900695
20ROOS S1E (SSN
1:20 0.15
0.10
0.65 1.00
0,85
1 0.0
0.0 0.0
0.9 1 0.0
2. 2.41--9.5590
201294 58.839
1.64 1. 0.18
0.20
0:85++000
0.85 + 0.0
0.9+-000
0.9+-000
1.90118699
2.400-88 99%)
21087 A5 3999)
1.50 +: 0.16
MLP
1:000
CIN 0.0
2.01
3.766-87 54.55
29444 070.500000000000 963
1.00
0.63 1.000
0.92 1.00
3.39))
46466 83%
2,88
COMPAS GEDT
0115
U.D7 =
0.72
1:44-225
0.10
0.7
0.67 + 0.01
0.77
0.72 + 0.01
1.19934889)
1, 1,4622 8488)
9.11(1.788)
0.06
0.20
0.7
+ 0.0
0.67 + 0.01
0.77 + 4.0
0.72 + 0.01
1.12(-2619)
1.36- 99.99)
8.97(10.0668)
0,68 + 0.04
LILR
0.05
0.68 1:00
0.67 0.01
0.73 1.0.0
0.72 1 0.00
1.144-8.899 8%)
6 87%)
0.29 1 0:02
0.10
0.08 100
0.67 +: 0.011
0.77 0.0
0.72 4: 0.01
3.8%%
32.9%)
5.85914.90%)
0.29 2: 0.01
0.20
0.68 +000
0.67 + 0.01
0.73 +000
0.72 + 0.01
1.346-8.8%)
1. 16- (5.09)008)
5.8715.3208 33.33)
0.28 + 0.01
12CR
0005
0:68 1.0
0.67 0.00
0.71000
0.72 0:001
1:1707.119)
20.3355
0.01
1.00
0.67 0.0.
0.73
1.176-7.1499
6.27220.11)
0.27 0:01
0.30
0.08 1.00
0.67 4: 0.91
0.73 1.00
0.72 0.01
6.35%)
30 29%)
6,28220662
0.01
000
0.000
0.07 0.01
0.0
1:2-111199)
LOT-27 5995)
8
0:30+ (X007
0.10
0.60
1 0.01
0.67 1: 0.01
0.74 1.000
0.72 1 0.01
1.2%)
1866-28.260 28.26%
8. 19:26 19%)
0.41 0.06
0.20
0.00
+ 000
0.67
+ 0.00
0.74 0:00
0.72 # 0.01
1 1.2%%)
L.62129.550 29.5788)
28.822.8818)
0.42 +: 0.07
Iiabenes GRITT
0.05
0.65 +.0
0.64 0:0
0.7 +.00
0.7 +.000
1.371-1 66%)
1.16 87%)
4521 061-92 (455)
5ind + 8.00
0.10
0.60 +.00
0UG4 + 0.0
0.7
0.7 + 0.0
1 1.394-2 16%)
1399
5006 821-8000000000 898)
58.20 + 7.45
0.30
0.65 1.00
0.64 1 0.0
0.0100
0..100
1.33--2889) 88%)
161 48 (8.23)
-5258 281 21.1%)
54.67 1.
DICK
11250
0.10
0.62
0,62-
+.00
93%)
1.31-11.118)
70%%
0.20
0.62 1.00
0.0
0.66
0.66 100
90%)
2.311-1 11 11.5%
S482 02%)
12L
0.05
0.02 1.00
0,22 1: 0.
0.66 1.00
0.00 1.00
4673)
2-31--194433
23017
7.06 1
0.10
0.02 1:00
0,022 4: 0.0
0.06 1: 0.0
0.06 0.00
1.244 46%)
16,4488
-90477 (18447.64222.998
2: 0.99
0.20
0.62 +00
0U62 0.0
0.66 +.0
( +00
1.244-23
46%)
2.311-144459
44001 23121 86%)
7 0.64
MLP
0.05
0.65 0.00
0.63 0:0
0.71 1:00
0:68 1:00
1410113590
L7M5-35:5551
10:11 20:15
0.10
0.65
+ a.0
0,33 I.0
0.71 0.00
0.08 0.0
1 1.436-3..5%
85726358828)
01889 47033 84%6
38.03 27.613
0.30
0.66 + 0.00
0.63 + 0.0
0.71 +000
0.68 +.0
1.99-14 14 725)
1.796-39499)
17723 7564 7364
90.72 19:28
RIC
GBDT
13
0.10
0.77
0.72
0.65
0.79
2.00k
50.83%
162
0.30
0.77 +00
0.72 0.011
0.85 0.0
0.77 à 0.01
2009 42 1888
01866-11388 38%)
163.04 43.56
0.05
+000
0.0
0.78
0.77 0.00
1 (18)
6245669
20.55 6.18
0.10
0.71 1.000
0.7 0.0
0.78 1.00
0.77 1 10.01
1 9X 24.7%)
77 18(3889))
34. 15 7.9
0.20
0.71 1.000
0.7 1.0.0
0.78 1.00
0.77 1.000
864 24.79)
457%)
-79-02-
12:00 1. 1.443
0105
0.72 1:00
0:01
0.78 000
0.77
4 0:01
16
280.3 1000
0.10
0.72 +.00
0.71 +-0.01
0.78 +.00
0.77 + +0001
2.280 7 7.09%)
1. 7.70-72258)
57. (1610.88%)
503 19 + 98 72
0.20
0.72 1.00
0.71 0.001
0.78 1000
1001
18 55%)
1,00)
-57 221122000000 59%
905.85 1 97
MLP
0.74
217CK
1098%))
20002
0.71 0.01
2.18 74%)
1.0669229))
17.85(129888)
135.6
0.20
0.74+ 0.0
0.71 0.01
0.81
0.78 0.0
2.18 748)
1,7166.668
78.07(13
156008 70.96
German
GBDT
0.05
0.56
0.01
0.75 0.02
0.90 0.0
0.77 1.05
1226
2.91399)
0.25 3:54
Credit
0.10
0.96
+ 0.00
0.75
+ 0L002
0.99 + 0.0
0.77 + 0.03
1.28(-12.988)
1.M-3.7498
3125300058.7999
GST 3.85
0.20
0.96 + +.000
0.75 + 0.02
0.99 +0000
0.77 + +.003
1
12.999)))
1912 1992.149
36387 77452 498)
7.78 4.46
LILR
0.05
0.76
1 0101
0.75 0.02
U.S 0.00
0.75 1 0.04
1.00-20.775
2 17.15)
2117700/6119995
0.75 0.33
0.10
0.75 1 0.01
0.75 1. 0.02
0.6 1 0.01
0.77 1 0.00
0l 20.0%)
2.01 179611999))
22680 186-61.360
0.79 0.38
0.20
0.002
20.7%)
1.12-13478
25845 271-922--900000 (9.6666
0.17
1
0.04
0.05
0.6++000
1 525)
3.062
10001 3565
0.10
0.76
0.01
0.76 0.05
0.63 0.01
0.79 1.01
1.18/ 25%)
1.00-16288
01228 76x64 0666
0.20
0.77
+ 0.01
0.76 0.033
0.83
0.79 + 0.04
1.17 52%)
71136.1064 15%6)
0188
MLP
0.05
0.81 :: 0.04
0.76 1: 0.05
0.87 0.00
0.78 1: 0.00
256-001 88%)
2.5((4446)
34661 3199)
2.90 1/42
0.10
0.81
+ 0.05
0.76 + 0.05
0.87 +0004
0.78 + +.004
1.233-23 13%)
2.58)4
16854 11660 70%)
3.04 1.67
0.20
0.81
1 0.01
0.76 1 0.03
0.87 0.04
0.78 1 1..01
1
2 3.35%
11223 18465 5298)
2,55 1. 1.47
Headlnne GBDT
011
0.32 2000
USI
2 MM
UAU 0:0
US9 0M
1,7444495
Dor 13961
22.78 3 55.05
0.10
0.00
0.81 + 0.0
0.9
0.89 0.0
1.7166045)
432 266-9.29)
20.85 + 7.71
0.20
1.00
0.0
0.9.00
1.00
15 15.93)
2.291 5.538)
543.55 37.49%)
2.41
LILR
1.00
0.78
0.85
0.55 100
2S417.19
981 355%
0.10
0.78 +00
0.78 0.0
0.85
0.85 0.0
19554-192288
29407.118)
4.16 0.17
0.30
0.78
+00
01788 + 0.0
0.65 0.0
0.65 +.0
1476-3 448)
29K17
71-3 38%)
2.54 0.12
L2CR
000
0.78 1.00
U.78 0.3
0.50 1.00
USS5 1.00
1.300 19.730
188517888)
506 83000
4.1 0.22
0.10
0.78 +000
0.76 + 0.0
B.8G + 0.0
DU65 +0000
1 1---19 199%)
204(1668)
571.971-3
5 0.22
0.20
0.78 1.00
0.78 1: 0.0
0.65 1.00
0.55 1:0.0
54-24 249)
2 2561766)
3:22 1 0.13
MLF
01A
0.83 (1))
(UST + 0.0
0:91 1-000
0:30 F-00
-17 15- 198)
7.02 1.55
0.10
0.83 1 0.01
0.81 0.0
0.91 0.01
0.89 1.0
1.84
19.215)
14.728)7
-OL 41 22.518)
7.47 2.25
0.20
0.0
+.0
1.52-26 11%)
2.06 10.8-1088226)
+ 0.79
MIMIC
GBDT
0.05
0.00
0.00:0.0
0.67
1.0.
1.212.54 (49))
0.591-59
0.066-0745)
0.10
1.00
0.9
0.87 0.00
0.55 1.0
1.212.544)
62.56-22.566
0.85%)
0.20
0.91
1000
0.9 0.00
0.87 1.000
0.85 1.000
1.212.544%
67.9767.97%
5600528))
3,30 0.43
LILR
011
0.30
200
U.S 2.0
U.S 2:00
1.11-15.59)
U.75 2 U.RG
0.10
0.80 +.00
0.89 +: 0.0
0.8 +.0.0
0.6 4 1.0
1.152.61%)
1.56-74.611)
-21 21-466-.77%
0.77 0:07
0.20
0.89 1.00
0.89 4: 0.0
0.8 0.0
0.5 1 0.0
L18(2.11)
L116
-21 (5.-66.777)
0.79 1 0:08
12ER
0118
0:39 $000
00:0++100
0.3 1:00
0.8 + (11
L1911999
L.16-7199)
21 311-718-7751
0126 + 0.11
0.10
0.69 1.00
0.89 1 0.0
0.6 0.00
0.6 0.0
L.102.59%)
L.16673.58)
-21 21.11-8.95)
0.84 1. 0.09
+.00
0.0
1.192.590 119)
1.156-33.58)
-21-451-926699
0.55
0.580 72.128)
3.62%)
0.10
0.9
+
0.87
0.55 0.00
399%)
-18.12-550449)
0.20
0.9
0.9 0.0
0.87 1
0.55 1.0.0
1.22(.399%
0.58(-72.12%)
-18.12633004))
1 1: 0.14
26

---

I All-Opt variants performance
In this section, we will mainly show the model performance of All-Opt and All-Opt', which are the two gradient-based optimization methods used for SEV and SEV' optimization. Table shows shoows the SEV?, So and model performance after applying All-Opt' methods for different models on different datasets with different levels of flexibility. It is evident that All-Opt has provided a significant decrease in SEV, so that its values are close to I, providing much sparser explanations without model performance loss and closeness/credibility loss in explanations. Similar findings are observed in Table III
Table 10: The model performance for All-Opt!
TEST
MEAN
MEAN LIKELLIRRDO
DATASET
MODEL
ACCURACY
ACCURACY
AUC
Esc
TIME(S)
Adal
CBDY
0.87 0.00
0.84 0.02
0.53 0.00
0.90
0.01
1,00 0.00
5.07
1.033
2010
-9851 SO 4201
LR
0.84
+ 0.00
0.84 = 0.01
0.50 +: 0.02
0.89
0.00
1.03 = 0.00
3.21
4.002
61=1
TUS0S O6 + 10678,32
MLP
0.96
+ 0.01
0.85 + 0.01
0.01
+ 0.02
0.01
0 0.01
1.00
+ 0.00
0.52
+
62
59049 77 9632. 16
COMPAS
GRDT
0.70+ 00001
0.08 0.01
0.71 0.001
0.71+ 0.01
L.11 0.01
1:00
0:00
204
10.4400330
LR
0.68
0.01
0.68 0.02
0.74
11 0.01
0.75
0.02
1,00 1 0.00
2.13 0.01
9.17 1.02
0.002
0.74
0.012
0.72
0.11
16
Diabetes
GBDT
0.01
0.01
0.62
0.01
0:334
10648
724
14033
0.82
0.04
0.04 0.65
0.53
0.01
1.07 0.00
217
40100000
10453
MLP
0.62
0.01
0.01
0.65
1 0.00
0.64
0.02
1.07
1.000
2.50
0.03
318 5
18013 3894.36
FICO
GBDY
0.70
0.02
0.70
0.02
0..7
1: 0.01
0.17
1 0.02
1.10
0.10
0.84
0:012
804 =: 235
10 4:4.32
LR
0.70
2 0,02
0.70
1: 0.02
0.77
a: 0.01
0.77 0.02
1.10
1 0.10
1.91
1 0.333
19 1
-20:32 0.18
MLP
0.72 1 0.01
0.72
0.01
0.78
1 0.02
0.78.L 0.01
1,28 0.00
1.29 0:21
28
-26 04 0.43
0.31
10=1
Credit
0.01
0.82
0.022
L 0.00
1.39
ML.P
0.82 0.01
0.73 0.03
0.93
0.02
0.75
1,00 + 0.00
0.08
859166.0 13728-233
Hendline
GBIYT
0.302 0.00
1.76 0.02
0:30 0000
0.89 0.00
KJN = 0.02
2.45 0:007
2732
4:37
1.R
0.77
+ 0.01
0.78 +: 0.01
0.96-11 + 0.01
0.85 +: 0.01
1.00 + 0.00
2.77
4:0.0 0:444
78 =
-2:39 + 0.1.1
MLP
0.76 2: 0,002
0.77 2 0.08
0.87
+: 0.012
(186 0,02
L8B 1 0.00
2.78
2 0.13
102
-2.57 4 0,89
MIME
GBDT
0..01
0.88 0,01
0.54 1 0.01
0.82 1722110 0.02
1,06 0.04
3.86 0.02
2709
102
-16.36 1.051
LR
0.01
0.00
87
ML.P
3.87
Table 11: The model performance for All-Opt
TRAIN
TRAIN AUC
TEST AUC
MEAN SEV
DATASET
MODEL
ACCURACY
ACCURACY
Ex0
LOG-LIKELIOOO
Adult
GBDT
0.90 1: 0.00
0.83 1: 0.01
0.89 1 0.01
0.89 1 0.01
1.14 0.03
1.87
0.03
289.07 1: 52.79
LR
0.81
= 0.00
0.81
0.91 : 0.01
0.90
1.01 = 0.01
299.01 + 17.21
MLP
0.83 1: 0.01
1.84::0.00
0.92 1 0.01
0.91 0.00
1.00 1 0.00
2.37
0.19
297.14 1. 32.
COMPAS
GBBDT
0.08 1 0.01
0.68
+ 0.01
0.72 1 0.01
0.74 0.02
1,02 : 0.02
1.34
0.47
10.25 1 2.14
LR
0.68 1: 0.01
0.68
0.01
0.72 1 0.01
0.74 0.02
1.00 1 0.00
2.49
0.21
8.67 1.32
MLP
0.67 = 0.01
0.67
0.02
0.71 + 0.01
0.72 0.01
1,05 = 0.05
1.92
= 0.05
7.22 0.56
Diabeles
GBDTT
0.62 1 0.01
0.62
0.02
0.66 1 0.01
0.66 0.02
1.05 1 0.00
1.99
1 0.01
5231.53 :: 489.52
LR
0.62 = 0.01
0.62
0.02
0.66 : 0.01
0.66 0.02
1.05 = 0.00
2.89
0.46
59937 66 638.77
MLP
0.62
0.01
0.62
0.01
0.67 + 0.01
0.67 0.67=00.0
1.05 -
0.001
-5217.30 497.75
FICO
GBDT
0.70
0.01
0,70
0.00
0.78 : 0.01
0.78 078:000 0.01
1.48 = 0.09
0.90 0.01
-35,09 = 6.79
LR
0.70 1: 0.01
0.70
0.00
0.78 1 0.01
0.78 1 0.01
1.41 1 0.05
1.60
1 0.27
-1.66 J: 7.01
MLP
0.70
0.01
0.69
0.11
0.79 + 0.02
0.78 = 0.02
1.28 = 0.19
1.23 0.05
-18.47 8.98
German
GIDDT
0.75
1 0.01
0.76
0.D1
0.82 1 0.01
0.80 0.01
1.00
0.00
1.00
1 0.00
11777731
21351011
Credit
LR
0.75
0.01
0.76
0.01
0.82 + 0.01
0.80
1 0.01
1.00 = 0.00
1.00 0.00
150700.6 = 772-123
MLP
0.02 0.86
0.79
0.01
0.92 + 0.01
0.80
1.00
0.00
1.00 1.00
-30917.9 86 653-1.23
Headline
GBDT
0.78
0.02
0.79
0.01
0.85 - 0.01
0.85
0.01
1.26 = 0.03
-1.72 0.01
-120
LR
0.78 1 0.02
0.79
0.01
0.85 1 0.01
0.85 1.001
1.29 1 0.30
2.93 0.02
-2.93 1:28
MLP
0.78
0.02
0.78
0.03
0.81 + 0.01
0.81
1.15 = 0.12
1.69 0.16
-2.87 1151
MIMIC
GIDDT
0.30 1 0.01
0.89
0.D1
0.80 1 0.00
0.80 0.00
1.05
1 0.05
1.00
-21.0 2.45
LR
0.90
= 0.01
0.89
0.01
0.80 : 0.00
0.80
0.00
1.00
0 0.00
0.000
-28.74
MLP
0. 0.89=1 = 0.01
0.89 0.01
0.84 = 0.01
0.81 1 0.00
1.01 = 0.01
0.00
-29.35 - 0.36
27

---

J SEVT in tree-based models
In this section, we show the model performance and SEV" values for different types of tree-based models. As discussed in section 4.2 the similarity and closeness metrics in SEVT are all &o norm, so we only need compute the mean SEVT for each tree. Table 12 shows that most of the tree-based models can provide sparse explanations (SEVT < 2), and we can also find a decision tree with the same model performance as the other tree-based models from SEV"=1 to TOpt.
Table 12: The model performance with different tree-based methods
DATASET
METHODS
TRAIN AcC
TEST Acc
MEAN SEVT
Adult
CART
0.84 + 0.01
0.84 0.01
1.11 + 0.01
C4.5
0.85 + 0.01
0.84
1.10 0.02
GOSDT
0.01
0.01
1.08 1 0.01
Topt
0.82
0.00
1.00
COMPAS
CART
0.68
0.60
1.02
C4.5
0.00
0.65
1.02
GOSDT
0.02
0.65
1.12
Тopt
0.67
1.00
Diabetes
CART
0.63 0.01
0.00
1.00
C4.5
0.63 + 0.01
0.63 0.01
1.00
GOSDT
0.61 0.01
0.60 0.01
0.00
Topt
0.62
0.63
1.00
FICO
CART
0.01
0.71 0.01
1.10 0.03
C4.5
0.71 0.01
0.05
GOSDT
0.00
0.09
1.80
Topt
0.00
0.01
+.00
German
CART
0.00
0.70
1.00 1.00:000
Credit
C4.5
0.01
0.00
1.00 + 0.00
GOSDT
0.00
0.01
1.00 0.00
Topt
0.01
0.70
1.00 0.00
Headline
CART
0.08
0.00
1.27 0.01
C4.5
0.01
0.70
1.16 + 0.02
GOSDT
0.00
0.02
1.09 0.02
Topt
0.00
0.00
1.00
MIMIC
CART
0.89:.001
0.01
1.00
C4.5
0.89 0.01
0.89
1.00
GOSDT
0.89 + 0.01
0.09
+.00
Topt
0.89 + 0.01
0.09
1.00 +.00
28

---

K The SEVI results after ExpO optimization
For the ExpO comparison experiment, we used the fidelity metrics from Plumb al. [2220] as the penalty term for regularizing the original model. Then we evaluated the optimized model with SEV-. We used two kinds of fidelity metrics as the regularization term: ID fidelity and 1D fidelity. Both of these two penalty terms aim to optimize the model f such that the local model g [Ribeiro et al. 2016, Plumb et al. (0118) accurately approximates f in the neighborhood Nz. which is equivalent to minimizing:
(10) The local model g's are linear models, and the N₂ are points sampled normally around the original query. The ID version of Fidelity regularization requires sampling the points around each feature of æ at a time, which saves time and computational complexity. Based on the above equation, we rewrite the overall objective function as:
(ea 9, N₂)= R (a(2²) - (ax')
min BCE + Cylie JEF
(11)
where BCE the Binary Cross Entropy Loss control the accuracy the training model, OF is the strength of the fidelity term, and the training process is the same All-Opt optimization, which we used 80 epochs for basic training process, 20 epochs for regularization.
In this section, we show the SEV- and training time for ExpO regularizer in LR and MLP models with ID Fidelity (IDFed) and Global Fidelity (Fed) regularizers. Comparing the mean SEV1 of Table 13 with Table 7 it is evident that with the optimization through Fed or IDFed, the optimized models do provide sparse explanations. In addition, it takes a long time calculate Fed and 1DFed since the regularizer's complexity is determined by the number of queries, features, as well as the points samples around the queries. For SEV the complexity is determined only by the number of queries and the number of features, so it is much casier to calculate.
Table 13: Model performance, SEV' and training time of LR and MLPs after ExpO with different datasets
TRAIN ACCURACY
TEST ACCURACY
TRAIN AUC
TEST AUC
MEAN SEV'
TRAINING TIME(S)
DATASET
MODEL
REGULARIZER
Adult
LR
Fed
0.85 + 0.01
0.84 0.01
0.90 + 0.01
0.89
0.01
1.23 + 0.02
1350 + 162
IDFed
0.84 : 0.02
0.84 0.01
0.90 0.01
0.90
1 0.02
1.7 0.02
510 = 23
MI.P
Fed
0.85
0.83 0.02
0.89
0.01
1580
IDFed
0.85 0.01
0.83 0.02
0.90 + 0.01
0.89
0.01
1.27 = 0.02
686 = 23
COMPAS LR
Fed
0.67 = 0.02
0.66 2 0.01
0.72 1 0.02
0.72 2 0.02
1.22 = 0.04
58 10
IDFed
0.65
0.65
0.01
0.72 0.02
0.02
MLP
Fed
0.68 = 0.02
0.66 0.01
0.74 + 0.02
0.72 0.01
1.28 = 0.03
125 = 14
IDFed
0.68 0.02
0.66 0.02
0.72 + 0.02
0.71 + 0.01
1.28
128 - 15
Diabetes
LR
0.63 0.02
0.62 0.01
0.02
0.60 0.01
3625
DDeed
0.63 = 0.02
0.62 0.01
0.60 + 0.02
0.60 0.01
1.46 = 0.01
1842 - 245
MLP
Fed
0.63 0.02
0.02-0000 0.01
0.60 + 0.02
0.00 1 0.01
1.52 0.01
4372 = 316
IDFed
0.63
0.62 0.01
0.60
2032
FICO
LR
Fed
0.71 0.01
0.71 0.01
0.78 + 0.02
0.78 0.01
2.76 + 0.12
150 +
IDFed
0.71 + 0.02
0.71 0.01
0.77 + 0.01
0.78 1 0.01
2.76 0.21
150 = 14
MLP
Fed
0.72
0.01
0.78
2.67 =
210
IDFed
0.72 0.02
0.71 = 0.01
0.78 + 0.02
0.77 + 0.02
2.80 0.35
195 14
German Credit
LR
Fed
0.78 = 0.02
0.76 0.01
0.82 1 0.02
0.80 1 0.01
L.65 = 0.12
28 -
IDFed
0.77
0.73 0.02
0.76
1.76 0.02
MLP
Fed
0.75 = 0.02
0.72 0.02
0.82 + 0.01
0.78 0.02
1.70 = 0.03
33 =
IDFed
0.70 0.00
0.70
0.72 + 0.02
0.73 2 0.01
1.0 0.03
20 - 0
Headline
ER
0.77
0.77 0.001
0.85
0.85 0200
680
IDFed
0.77 = 0.01
0.77
0.84 0.01
0.85 :: 0.01
1.87 = 0.02
562 - 32
MLP
Fed
0.77 1: 0.02
0.78
0.85 0.02
0.85 0.03
1.77 1 0.04
762 = 56
DDed
0.77 0.02
0.001
0.84 0.02
0.85 0.01
1.87 0.04
852
MIMIC
LR
Fed
0.89 + 0.02
0.89
0.77 4 0.01
0.77
0.01
1.18 = 0.02
712 = 42
DDFed
0.89 0.02
0.88
0.78 +
0.77 1 0.02
L17
646 = 42
MLP
0.88 - 0.00
0.80
0.78 4 0.00
0.77 +:77:000 0.01
1.15
960
IDFed
0.88 0.00
0.88
0.78 0.01
0.78 0.01
1.06
873 =
29

---

L Proof of Theorem 4.1
Theorem L.1. With single decision classifier DT and a positively-predicee query xy define N; as the leaf that captures it. If N; has a sibling leaf. or any internal node in its decision path has preeiiccce child leaf. then SEVT is equal to
SEV- is defined as the number of features that need to change within the given classification tree. If you have switched a particular node from one path to another, adds one to SEV-. Therefore, for the internal nodes along the SEV path, if N; has sibling leaf node, if we goes up to its parent node and goes the opposite direction change the query value for counterfactual explanation.
modified instance will be directly predicted negative, which leads to SEV being equal to 1 in this case.
Figure shows an example for SEVT being exactly I, and case illustrating that if N does not have child leaf, SEVT
sibling or any internal node in its decision path that has a should greater than or equal to In Figure [T] the left trees are the full decision trees, where the blue nodes are the negatively predicted leaf nodes and the red ones are positively predicted. The red arrows graph represents the decision path for specific instance. The person icon with plus sign is N; that we would like to calculate SEV" on. The right tree is the subtree of the left tree. The person icon with a minus is the query and the blue arrows indicate a decision pathway for SEV Explanation.
If the query is predicted as positive in node ④ it is easy to see that if we go up to node C and goes the opposite direction as the decision path for æt, then you can directly get negative prediction. In other words, if you change the feature C in the query to make it doens'i I satisfy the node O's condition, then can be prediction as negative, which means that SEVT=1.
For SEVT> 1 case, the query predidcted as positive in node 7 since does not have a sibling leaf node, then if it goes to its parent node (D) and goes the opposite direction, then it would reach node D.. However, if we don't I know the query æ; 's value, then am unable to know whether I need change the condition in node LL) for higher SEV". Therefore, in this case SEV? can be only guaranteed to be greater or equal to I.
Decision Tree
SEV Explanation
SEVT=1
SEVI 21
E
Figure 11: Example of SEVT=1 in Theorem 4.1
30

---

M Proof of Theorem 4.2
Theorem M.1. With a single decision tree classifier DT and positivllypredicted query æ, with the set of all negatively predicted leaves as reference points, both SEV- and the Eo distance (edit distance) between the query and the SEV explanation is minimized.
Proof (Optimality of Explanation Path):
The definition for SEV is the minimum number of features that is needed for a positively predicted query z; to aligned with the reference point in order to be predicted as negative. For tree-based classifiers, the decisions are made in the leaf nodes. Since we have set of all the negatively predicted leaves as the reference points, then the tu distance (edit distance) between the query and the SEV explanation is equivalent to the minimum to distance between the query and the negatively predicted leaf nodes. Each node can be considered satisfied. If query would like be predicted negative in a specific node, then needs change some of the feature values in the query so as to be predicted as negative, and the number of changed feature is SEVT. Therefore, SEV and the tn distance are the same in this theorem.
list of rules of conditions that needs to be
Next, we would like to show that if one of the negatively predicted leaf nodes is not considered reference point, then SEV- is minimized. It is really easy to give counterexample: if we have a decision tree shown in Figure 12 with white nodes as root/internal nodes, blue nodes as negatively predicted node, and the red ones as positively predicted. Suppose we have query predicted as positive, with feature values {A False, B False, C: False), ). and only regard node ① as the reference point, then both feature A and should change to True, in order do negative prediction. in other words, if only node ! is the reference point, then SEV-=2, However, based on Theorem 4.1 since node 4 has sibling leaf predicted as negative, then the SEV is not minimized.
F
B
F
Reference
Figure 12: counterexample with fewer reference point
Lastly, would like show that with all the negative leaf nodes considered reference points if an new reference points added, the SEV- cannot be further minimized. Since we know that the reference points should be predicted as negative, so the newly aded reference should still belongs to one of the existing negative predicted leaf node, so SEV- cannot be further minimized.
To sum up, we have proved that with the set of all negatively predicted leaves as reference points, both SEV- and the to distance (edit distance) between the query and the SEV explanation is minimized.
31

---

N Some extra examples for different kinds of SEV metrics
Table 14: Different SEV Variants Explanations in MIMIC datasets
PREICULOS
GCS
HEARTRATE MAX MEANBP_MP
RESPRATE_ MIN
TEMPC MIN URINEOUTPUT
Query
43806.28
10.00
91.00
29.00
9.00
34.50
162.98
SEVI
2215.88
SEV
2213.88
SEV
8739.30
SEV
595.48
Query
0.51
15.00
105.00
21.00
20.00
32.28
7.98
59.35
SEYP
59.35
SEVe
$6.95
36.11
SEVE
595.48
Query
1.34
5.00
139.00
33.00
11.00
35.56
247.98
SEVI
13.89
SEYP
13.89
SEYe
9.24
105.96
59.24
SEVT
595.48
Query
11.00
199.00
14.00
22.00
37.06
387.98
SEVI
102.57
SEYP
102.57
SEVe
107.58
SEVT
595.48
Query
142
13.00
134.00
28.00
28.00
34.72
4.98
SEVI
102.57
12.22
SEVP
102.57
12.22
SEY
97.70
12.68
SEYT
595.48
32

---

Table 15: Different SEV Variants Explanations COMPAS datasets
AGE
JUV FEL_ COUNT
JUV MISD COUNT JUVENILE CRIMES
PRIORS COUNT
Query
50.00
0.00
0.00
0.00
11.00
SEVI
2.21
SEVF
2.21
SEV
4.63
SEVT
2.50
Query 23.00
1.00
0.00
1.00
5.00
SEVI
36.71
2.21
SEVF
36.71
2.21
SEV
26.69
0.11
0.18
0.54
2.13
SEVT
2.50
Query
21.00
0.00
2.00
3.00
3.00
SEV1
0.12
SEVF
0.12
SEV
26.69
0.54
SEVT
33.50
Query
23.00
0.00
1.00
1.00
4.00
SEV1
36.71
SEVF
36.71
SEV
26.69
2.13
SEVT
23.00
2.50
Query
21.00
0.00
0.00
0.00
1.00
SEVI
36.71
SEVF
36.71
SEV
28.02
SEVT
22.50
33

---

NETIRACTION
REVOLVING
$4.00 44,00
112.01
22.26
9.00
8.85
6.00
95.01
22.26
9,00
30.36
45.00 .0
NUMINQ LAST6
1.00
0.00
0.00
10.00
0.56
1.18
0.00
NUMINO LAST6M
1.00
0.00
0.00
10.00
0.60
1.22
0.00
MAXDELQ2 PUBLICREC
LAST 2M
4,00
3.00
0.00
2.00
5.36
5.10
0.00
5.36
5.36
5.10
Table 16: Different SEV Variants Explanations FICO datasets
NUMTRADESOM
EVER2 DEROGPUBRESS
Missing 0.51
0.00
0.00
1.00
1.00
1.00
NUMTRADES
DEROGPUBREs
60EVER2
Missing Missing
Missing
Missing 0.82
0,00
2,00
..00
2.00
0.00
1.00
NUM SATISFACTORY
55.00
8:00
21.10
16.00
18,00
23.67
16.00
AVERAGE MINFLE
58,00 00
79.00
81.00
58.00
82.32
85,80
125.00 00
MSINCE MOSTRECEN TRADEOPH:
8.00
32.00
9,20
11.80
17.00
12.00
8.60
11.00
OLDEST TRADE-PEN
MSINCE
Missing
150.99
197.00
125.99
218.29
280.01
EXTERNAL RISK ES LSSMAATE TIMATE
60.00
72.21
SEVE 72.21
70.82
74.50
60,00
SEV 72.21
74.50
60.00
72.21
72.21
SEVF 74.50
Query 59.00
72.21
SEVO 70.82
SEVT 74.50
69.00
74.50
Query
SEV
SEVO
SEVF
Query
SEVE
SEV
SEVF
Query
SEV
SEVE
SEVO
SEV
SEVE
Query
SEV
SEV
SEV
SEVT
34

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our motivation and claims made within the abstract. We have provided experimental and theoretical results for cluster-based SEV, and its variants, and propose algorithm for improving the decision sparsity.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should elearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we have discuss the limitation of the work in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
35

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex: system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have provided the theorem mostly for the tree-based SEV in the Section 4.2. and the corresponding proofs are shown in Appendix and Appendix M
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Yes, all the experiment details are mentioned in the Appendix F The detailed training process for the comparison with ExpO is shown in Appendix K
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
36

---

If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, we have provided the code for training, and evaluation in the Experiment folder, and the script for running in Script folder.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ mnips.cc/public.//
pwt.huooommisiiooooococcc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
37

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Yes, we have already mentioned them in the Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, all the training data has been run for 10 times, which is mentioned in Section F and all the results are calculated for error bars.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, have error bars for the time execution for each methods and the GPU and CPU details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
38

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Yes, the paper conforms, in every respect, with the NeurIPS Code of Ethics
https: http::///euripccceoee httpp/pp.....poooooc////eseeeaaa
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, we have mentioned the social impact in the conclusion. Our method has impact in that it provides sparser explanations for those subjected decisions made by models, including in finance and criminal justice.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper doesn't release models that have the potential to cause harm like image generators language models.
39

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Yes, have well cited the packages.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssithcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper provides code.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
40

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
41


Reviews:
[{"review_id": "bTsGAFKa7f", "reviewer": "Reviewer_PbJJ", "summary": "This paper proposes several ways to create closer, sparser, and more credible explanations for the SEV, along with two optimizing models. The results of the experiments on various datasets support the paper's claims.", "questions": "1. In Table 1, what do the gray numbers represent?\n2. In line 199, there are duplicate \"and\"s.", "limitations": "I'm concerned about the depth of the tree if the model applies to large-scale data. In section A, the number of observations is up to 100K. If we encounter a much larger data set, the complexity of the model would exponentially increase with the depth of the tree. That's why I'm interested in time analysis.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Before reading this paper, I was unfamiliar with the sparse decision field. However, this paper is well-written and enjoyable to read.\n2. I think this paper is quite creative by simultaneously considering closeness, sparsity, and credibility.\n3. The comprehensive experiments address most of the claims they proposed in the introduction section.", "weaknesses": "It could be better to provide the complexity analysis and the analysis of time expenditure for different variants of SEV. For example, the computational benefits of using tree-based SEV.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! See below for our response to your questions.\n\n> In Table 1, what do the gray numbers represent?\n\nThank you for pointing out the missing explanation for the gray numbers. The gray numbers in Table 1 represent the query feature values that haven’t been changed, while the black numbers are the sparse explanations that have been made in order to make the prediction flipped. You can observe that the gray feature values are the same as the query feature values. In SEV, we can only use the changed features as the explanations, which is the same approach as DiCE.\n\n> In line 199, there are duplicate \"and\"s.\n\nThanks for pointing out the typo! We have already corrected the typo in our paper.\n\n> It could be better to provide the complexity analysis and the analysis of time expenditure for different variants of SEV. For example, the computational benefits of using tree-based SEV. I'm concerned about the depth of the tree if the model applies to large-scale data. In section A, the number of observations is up to 100K. If we encounter a much larger data set, the complexity of the model would exponentially increase with the depth of the tree. That's why I'm interested in time analysis.\n\nThanks for your question about the time complexity for tree-based SEV. The time complexity of tree-based SEV calculation is based on the structure of the tree instead of simply the depth of the tree. The worst case for an tree-based SEV calculation is $O(n)$, where n is the number of nodes in the decision tree. The worst case does not scale as the number of data points. Moreover, $\\text{SEV}^T$ will be stopped early when the query has a sibling leaf node with negative prediction (shown in theorem 4.1), or the query already finds an explanation with $\\text{SEV}^T$ = 1 during the search (see Line 28-29 in Algorithm 3). Therefore, the calculation of $\\text{SEV}^T$ remains fast with the growth of observations.\n\nThank you so much once again for your review!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O0QJ9EzD0G", "reviewer": "Reviewer_bvrF", "summary": "The authors build on top of the Sparse Explanation Value approach by\nSun et al and provide improvements in terms of closeness and\ncredibility.", "questions": "How can you turn a DT leaf into a reference point when dealing with\ncontinuous features? what is the actual value of the continuous\nvariables in the leaf?", "limitations": "The approach is very incremental, and the main extension substantially\nrestricts the applicability of the method.\n\nThe rebuttal of the authors did shade additional light on the novelty of the contribution.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Sensible problem, well presented solution.", "weaknesses": "The main limitation I can see in the work is its very incremental nature with respect to the approach by Syn et al.: going from one negative reference point to a set by clustering negatives (cluster-based SEV) is a trivial extension, while tree-based SEV only works if the underlying model is (or can be approximated as) a decision tree, substantially restricting the applicability of the approach.\n\nAdditionally, the superiority of sparsity with respect to distance in\nterms of acceptability for humans is intuitive but not always\nguaranteed. When dealing with recourse, for instance, which is the\nsetting used in the experiments, the main problem is the cost of the\nchange, and slightly modifying two features could be less\nexpensive than modifying a single one by a larger value. This should\nbe better discussed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! See below for our response to your questions and concerns.\n\n> The work is its very incremental nature with respect to the approach by Sun et al. cluster-based SEV is a trivial extension, while tree-based SEV only works if the underlying model is a decision tree, substantially restricting the applicability of the approach.\n\nIn terms of your question about the contribution of our paper, we understand that some of the ideas seem trivial (going from one negative reference to a set), and that you think the extension to decision trees is not broadly useful because it applies only to trees. Indeed the idea of going from one reference to many is easy. Working out how to do it, and to add credibility to the computation, is not. In terms of trees, there are many papers at NeurIPS each year that are *only* focused on decision trees! Trees are some of the most popular algorithms for interpretable machine learning, since the 1960’s. The fact that we have a substantially better way to define and compute SEV for trees is important for a lot of applications! Previous studies have also taken tree-based models for separate discussion. For instance, there exists a lot of papers discussing about fast shap values computation in tree-based models, also known as treeSHAP.\n\nWhile it’s tempting to believe ideas are incremental in retrospect, they are often not obvious until after seeing them. Many of our ideas are not obvious at all, for instance looping through all good sparse decision trees to find one that optimizes SEV + accuracy, which makes what would have been a practically impossible computation now take seconds. Many important ideas in ML seem obvious in retrospect, e.g., placing skip connections in neural networks. If you glance through the orals in NeurIPS from last year, they are almost all variations on existing topics. Our paper is only the second paper on SEV, which is a new notion of sparsity, and it generalizes the definition and works out how to optimize it and make its computations credible.\n\nWe have actually made a lot of improvements and generalizations with respect to the original SEV paper after generalizing the framework of SEV to make it support instance-wise reference selection. \n- We proposed cluster-based SEV and its variants in order to handle the two objectives of instance-wise selection: the flexible reference solves the issue of higher SEVs (cluster SEVs are larger than standard SEVs), and the credibility approach enables the explanations to be located in a high density region. The credibility setup is definitely not obvious.\n- For tree-based models, we introduced SEV-T which directly uses negative leaf nodes as the reference points, and introduced a fast calculation procedure for SEV-. That fast procedure is definitely not obvious and is comparable to content within an algorithms course. The bound on credibility in SEV- in Theorem 4.3 isn’t obvious either - tree-based SEV- computations are always sufficiently credible.\n- We generalized the original gradient-based methods and introduced new search-based methods specifically for tree-based models in order to optimize the specific model type to have low SEV. The methods for optimizing SEV are not obvious, particularly Sec 5.2 where we optimize SEV by scanning all good trees using the new Rashomon set algorithms and finding the one with the best SEV. (In contrast, think about how many papers optimize some combination of $ell_1$ loss with accuracy, or optimize neural networks using some variation of gradient descent!) \n\n> The superiority of sparsity with respect to distance in terms of acceptability for humans is intuitive but not always guaranteed. When dealing with recourse, for instance, slightly modifying two features could be less expensive than modifying a single one by a larger value.\n\nRemember that SEV is not recourse, it is a measure of sparsity only. That said, it’s possible to change the metric to a recourse metric if desired. We did use multiple distance metrics. In our experiments we also used the $L_\\infty$ metric to evaluate the cost of change, which would handle the case you mentioned - when we care about how much we change the features. Table 6 in Appendix G provides the mean $L_\\infty$ for each explanation. Based on Table 6, SEV-C achieves better sparsity, relatively low $L_\\infty$ change (compared to DiCE under the same sparsity level), and meaningfulness (high median log likelihood) *simultaneously,* while for the other methods except DiCE, they use almost all features in their explanations, which is not only too complex to interpret, but also is not actionable in practice, and would yield worse recourse scores. This is not the case of modifying two features instead of one: it is modifying all instead of one. So already we would be better in terms of most recourse loss functions. It is possible to specialize the computation to a particular recourse loss, but that’s not our goal here, we’re concerned with sparsity of the explanation, not other costs. We will put a note for future work by others.\n\n> How can you turn a DT leaf into a reference point when dealing with continuous features? What is the actual value of the continuous variables in the leaf?\n\nInterestingly, the reference can be any point x within the leaf. So if the leaf is defined by $x_1>5$ and $x_3>0$, then any point with those conditions is a viable reference. For a query, the algorithm needs to flip its feature values to satisfy those of the leaf conditions to make an opposite prediction. \n\nSince you can choose any point in the leaf as a reference value, you could choose the median/mean values of points in the leaf. That choice won’t influence the fast calculation of SEV-T, so the user can choose any actual value inside the leaf that they believe is most meaningful as the leaf’s reference.\n\nThank you so much once again for your review!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zoDpVj0DZB", "reviewer": "Reviewer_xH4u", "summary": "The paper extends the notion of decision sparsity called the sparse explanation value (SEV). Cluster-based and tree-based SEV are introduced, as well as some algorithms to optimise the decision sparsity are considered. The core of the paper -- SEV -- is defined as the number of factors that need to be changed to a reference values in order to change the decision.", "questions": "Line 85: \"humans have no intuition for why a point belongs to one class or the other\". I cannot completely agree with the statement, and it would be helpful to provide some examples. For me, on the contrary, medical doctors have often an intuition how to classify a patient, however, they do not always know how to explain their intuition.  \n\nHow the sparse explanation for the sample x (mentioned on line 171) is formally defined? Is the number of features of x (original) and x (sparse) different?", "limitations": "The method is not scalable.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem considered is important for real (e.g., medical, criminology applications). The example (Table 2) is very helpful to understand the problem. The approach is mathematically sound and in general well-described.", "weaknesses": "The method is promising but its current version is hardly scalable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! See below for our response to your questions and concerns.\n\n> Line 85: \"humans have no intuition for why a point belongs to one class or the other\". I cannot completely agree with the statement, and it would be helpful to provide some examples. For me, on the contrary, medical doctors often have an intuition how to classify a patient, however, they do not always know how to explain their intuition.\n\nThere’s a good example from Figure 3 in the paper of Keane [1] where he shows images on either side of the decision boundary that look visibly identical (we have provided the figure in the attached pdf file). There’s just no intuition why the point belongs to one class or another. We agree with you that for some decisions that, particularly where there are discrete variables, the decision boundary could be clearer. We’ll adjust the wording of that sentence. However, even for medical decisions by doctors, it’s not also clear how to diagnose someone, which is why AI can be helpful. (We have multiple projects on exactly this topic.)\n\n[1] Delaney, Eoin, et al. \"Counterfactual explanations for misclassified images: How human and machine explanations differ.\" Artificial Intelligence 324 (2023): 103995.\n\n> How the sparse explanation for the sample x (mentioned on line 171) is formally defined? Is the number of features of x (original) and x (sparse) different?\n\nThe number of features of the original query x and the sparse explanation x are the same. The sparse explanation for a specific query is defined as a p-dimensional vector that has changed the smallest number of features from its query value to the reference value to flip the prediction, while the other features remain unchanged. Four  examples are shown in Table 1. The explanations (lower rows) are the same size as the Query (top row). The gray colored values are the unchanged query values, while the black ones are changed. This is the same type of definition as other counterfactual explanation methods.\n\n> The current version is hardly scalable.\n\nSEV measures decision sparsity, so it is calculated for each point separately, therefore in practice, when we provide an SEV for one loan applicant at a time, the calculation is very fast for that applicant (fraction of a second to a few seconds, more detailed calculation time is shown in Table 7-9 in Appendix H). If you want to calculate SEV for all points at once for a huge dataset, like in the experiments of our paper, it can be computed in parallel for each point. \n\nIf you want to compute it for each point and for a large number of features, we could apply the gradient-based method from our paper first in order to reduce the mean SEV of the model to be close to 1 without sacrificing the model performance. This could speed up SEV calculation for all points.\n\nThank you so much once again for your review!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all reviewers. The following pdf goes with the response for Reviewer xH4u.

Meta-review: The authors present enhancements on the Sparse Explanation Value (SEV) framework, proposing cluster-based and tree-based variants that improve the explanations provided.  The contributions of this work are significant from a technical and practical point of view.  After the author feedback, all reviewers recommended accepting the paper.
Decision: Accept (poster)