Improving Decision Sparsity

Authors: yiyang  sun
tong  wang
cynthia  rudin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:15:49

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.

Main paper: 
 introduction: 
 The notion of sparsity is a 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 in a model, or as the number of leaves in a decision tree [Murdoch et al., 2019] . Global 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 own decision, is more consequential.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 a loan application that is denied because the applicant has many delinquent payments. In that case, the decision sparsity (that is, the SEV) would be 1 because only a single factor was required to change the decision, overwhelming all possible mitigating factors. The framework of SEV thus allows us to see sparsity of models in a new light.Prior to this work, SEV had one basic definition: it 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 is 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 in a low density area where explanations are not credible. As an example, for the loan decision for a 21 year old applicant, SEV could create a counterfactual such as "Changing the applicant'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 to the features lead to an unrealistic circumstance -6-year-olds do not typically have credit. That is, the counterfactual does not represent a typical member of the opposite class.Lack of credibility is a common problem for many counterfactual explanations [Mothilal et al., 2020 , Wachter et al., 2017 , Laugel et al., 2017 , Joshi et 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 a 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 in 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 1 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, SEV 1 represents the SEV calculation with one single reference using population mean, SEV © represents the cluster-based SEV, SEV F represents the flexible-based SEV. SEV T represents the tree-based SEV The columns are four features. 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. 
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-wise explanations (iii) local sparsity optimization Models, which seek to explain and provide predictions of complex models. We further comment on these below.Instance-wise Explanations. Prior work has developed methods to explain predictions of black boxes [e.g., Guidotti et al., 2018 , Ribeiro et al., 2016 , 2018 , Lundberg and Lee, 2017 , Baehrens et 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 is on tabular data; there is a multitude of unrelated work on explanations for images [e.g., Apicella et al., 2019 Apicella et al., , 2020] ] and text [e.g., Lei et al., 2016 , Li et al., 2016 , Treviso and Martins, 2020 , Bastings et al., 2019 , Yu et al., 2019 , 2021] . More closely related are counterfactual explanations, also called inverse classification [e.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 , Laugel et al., 2017 , Pawelczyk et al., 2020] . Counterfactual explanations are typically designed to find the closest instance to a 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 a 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-based Optimization (ExpO) algorithm of Plumb et al. [2020] that used a neighborhood-fidelity regularizer to optimize the model to provide sparser post-hoc LIME explanations. Experiment in Appendix K in 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 feature, we align it to be equal to that of the reference point. The reference point is a "commons," i.e., a prototypical point of the opposite class as 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. Without loss of generality, in this paper, we are only interested in queries predicted as positive (class 1). We focus on providing a 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 i and reference x one at a time, checking at each time whether the prediction flipped. Thinking of these alignment steps as binary moves, it is convenient to represent the 2 p possible different alignment combinations as vertices on the boolean hypercube. The hypercube is defined below: Definition 3.1 (SEV hypercube). A SEV hypercube L f,i,r for a model f , an instance x i with label f (x i ) = 1, and a reference r, is a graph with 2 p vertices. Here p is the number of features in 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 variants 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 -: Definition 3.2 (SEV -). For a positively-predicted query x i (i.e., f (x i ) = 1), the Sparse Explanation Value Minus (SEV -) is the minimum number of features in the query that must be aligned to reference r to elicit a negative prediction from f . It is the length of the shortest path along the hypercube to obtain a negative prediction,SEV -(f, x i , r) := min b∈{0,1} p ∥1 -b∥ 0 s.t. L f,i,r (b) = 0.Figure 1 and Table 2 shows an example of SEV -=1 in a credit risk evaluation setting. Since p = 3, we construct a SEV hypercube with 2 3 = 8 vertices. The red vertex (1, 1, 1) corresponds to the query. The dark blue vertex at (0, 0, 0) represents the negatively-predicted 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-predicted vertex. On this hypercube, (0, 1, 1) is closest. Translating this to feature space, this means that if the query's housing situation changes from renting to the reference value "owning," it 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, 1), is called the SEV -explanation for the query, denoted by x r,expl i for reference r.Since SEV -is determined by the path on a SEV hypercube and each hypercube is determined by the reference point, the SEV -is therefore sensitive to the selection of reference points. Adjusting the reference point trades off between sparsity (according to SEV -) and closeness (measured by ℓ 2 , ℓ ∞ (see Section 6.1) or ℓ 0 (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. Moreover, the negative population may have subpopulations; e.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 x i , an individual-specific reference r i ∈ R for x i is chosen based on three criteria: it should be nearby (i.e., close), and should provide a sparse and reasonable explanation. That is, we are looking to minimize the following three objectives over placement of the reference r i :EQUATIONwith the constraint that the references obey auditability, meaning that domain experts are able to check the references manually, or construct them manually. The function SEV -(f, x i , r i ) in (2) represents the SEV -computed with the given function f , query x i , and the individual-specific reference r i for generating the hypercube. x expl,ri i is the sparse explanation for the sample x i , and P (•|X -) in the definition of credibility represents the probability density distribution of the negative population and P (x expl,ri i |X -) is the density of the negative distribution at x expl,ri i. If P (x expl,ri i |X -) is large, x expl,ri i is in a high-density region.Question: For each theoretical result, does the paper provide the full set 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 L 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 be properly referenced. 
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 to improve the credibility and sparsity of the explanations. This approach creates multiple references for the negative population. A clustering algorithm is used to group negative samples, and the resulting cluster centroids are assigned as references. A query is assigned to its closest cluster center:ri ∈ arg minr∈C ∥x i -r∥ 2where C is the collection of centroids obtained by clustering the negative samples. We refer to the SEV -produced by the grouped samples as cluster-based SEV, denoted SEV © . 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 2 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 of Bezdek et al. [1984] to constrain the predictions of the cluster centers. Details are in Appendix C. 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 ℓ 0 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.We denote SEV T 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 T . 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 a negative leaf. Theorem 4.1. With a single decision classifier DT and a positively-predicted query x i , define N i as the leaf that captures it. If N i has a sibling leaf, or any internal node in its decision path has a negatively-predicted child leaf, then SEV T is equal to 1.Figure 4 : Efficient SEV T calculation: Query (node 7 ) has SEV T =1, which goes to node 10 . The path to this node is recorded as LL at node 3 , which is along the decision path to node 7 .The second theorem states that SEV -and minimum edit distance from the query to negative leaves are equivalent. Theorem 4.2. With a single decision tree classifier DT and a positively-predicted query x i , with the set of all negatively predicted leaves as reference points, both SEV -and the ℓ 0 distance (edit distance) between the query and the SEV -explanation are minimized.The proofs of those two theorems are shown in Appendix L and M. The structure of tree models yields an extremely efficient way to calculate SEV -. We perform an important preprocessing step before any SEV - 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 it in the tree. This is described in Algorithm 2 in Appendix E. E.g., if the tree has binary splits, a path from an internal node to a leaf node might require us to go left, then right, then left. In that case, we store LRL on this internal node to record this path. Then, when a query arrives at runtime (in a positive leaf, since it has a 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 preprocessing. We traverse each of these, and the minimum distance among these is the SEV -. This is described in Algorithm 3 in Appendix E 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 1 not 2. Flip at 4Table 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 3 → 6 → 10 . That means we check 1 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 to get to the negative node, so we record the SEV T as 1 in that row. In our implementation, we simply stop when we reach an SEV T =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 SEV T =2.Note that the reference can be any point x within the leaf; if the leaf is defined by thresholds such as 3 < x 1 < 5 and x 2 > 7, then any point satisfying those conditions is a viable reference. Given a query, the algorithm flips some of its feature values to satisfy conditions of a 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, or a more meaningful value. That choice will not influence the fast calculation of SEV-T.As we mentioned in Section 3.2, the credibility objective encourages explanations to be located in high-density region of 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 is in a high-density region. Since the reference is in a highdensity region, walking towards it will eventually lead to a 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 S in each negative leaf, the SEV T explanation for query x i always satisfies credibility at least S N -, where N - is the total number of negative samples. This theorem can be easily proved because SEV -explanations generated by SEV T are always the negative leaf nodes (which are the references), and the references are located in regions with support at least S by assumption.From Section 3.2, we know that queries further from the decision boundary tend to have lower SEV -. Based on this, we introduce Flexible Reference SEV (denoted SEV F ), which moves the reference value slightly in order to achieve a lower value of the model output f (r) given a reference r, and the decision function for classification f (•), which, in turn, is likely to lead to lower SEV -. The optimization for finding the optimal reference is: r * ∈ arg min r f (r) s.t∥r -r∥ ∞ ≤ ϵ F where the arg min is over reference candidates that are near the original reference value r. The flexibility threshold ϵ F 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 F , is shown in Algorithm 1 in Appendix D. In Section 6.2, we 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. In this section, we describe how to train classifiers that optimize the average SEV -without loss in predictive performance. We propose two methods: minimizing an easy-to-optimize surrogate objective (Section 5.1) and searching for models with the smallest SEV from a "Rashomon set" of equally-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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? 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 are provided or not.• If the contribution is a 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 is 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 to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (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 to have some path to reproducing or verifying the results. 
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 et al. [2024] , we instead design the optimization objective to penalize each sample where SEV -is more than 1. Thus, we propose the loss term:ℓ SEV_All_Opt-(f ) := 1 n + n + i=1max min j=1,...,p f ((1 -e j ) ⊙ x i + e j ⊙ ri ), 0.5 , where e j is the vector with a 1 in the j th coordinate and 0's elsewhere, n + is the number of queries, and the reference point ri is specific to query x i and chosen beforehand. Intuitively, f ((1 -e j ) ⊙ x i + e j ⊙ ri ) is the function value of query x i where its feature j has been replaced with the reference's feature j. min j=1,...,p f ((1 -e j ) ⊙ x i + e j ⊙ ri ) chooses the variable to replace that most reduces the function value. If the SEV -is 1, then when this replacement is made, the point 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, f 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 at the "corners" and not difficult to optimize.To put these into an algorithm, we optimize a linear combination of different loss terms,min f ∈F ℓ BCE (f ) + C 1 ℓ SEV_All_Opt-(f ) (4)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_All_Opt-is the loss term that we have just introduced above. C 1 can be chosen using crossvalidation. We define All-Opt -as the method that optimizes (4). Our experiments show that this method is not only effective in shrinking the average SEV -but often attains the minimum possible SEV -value of 1 for most or all queries.As defined in Section 4.2, our goal is to find a model with the lowest average SEV -among classification models with the best performance.The Rashomon set [Semenova et al., 2022 , Fisher et al., 2019] is defined as the set of all models from a given class with performance approximately that of the best-performing model. The first method 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 a 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 a 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 -:min f ∈Rset 1 n + n + i=1 SEV T (f, x i ),where the Rashomon set is R set , and where we use SEV T as the SEV -for each sparse tree in the Rashomon set. Recall that Algorithms 2 and 3 show how to calculate SEV T . We call this search-based optimization as TOpt.Question: Does the paper provide open access to the data and code, with sufficient instructions to 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) 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 a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on 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. If only a 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 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Yes, we have already mentioned them in the Section F.• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiments: 
 Training Datasets To evaluate whether our proposed methods would achieve sparser, more credible and closer explanations, we present experiments on seven datasets: (i) UCI Adult Income dataset for predicting income levels [Dua and Graff, 2017] , (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 Graff, 2017] , (iv) MIMIC-III dataset for predicting patient outcomes in intensive care units [Johnson et al., 2016a,b] , (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 et al., 2023] . Additional details on data and preprocessing are in Appendix A.Training Models For SEV © , we trained four baseline binary classifiers: (i, ii) logistic regression classifiers with ℓ 1 (L1LR) and ℓ 2 (L2LR) penalties, (iii) a gradient boosting decision tree classifier (GBDT), and (iv) a 2-layer multi-layer perceptron (MLP), and tested its performance with SEV F 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 are implemented. For SEV T methods, we compared tree-based models from CART, C4.5, and GOSDT [Lin et al., 2020 , McTavish et al., 2022] with the TOpt method proposed in Section 5.2. Details on training the methods is in Appendix F.Evaluation Metrics To evaluate whether good references are selected for the queries, we evaluate sparsity and closeness (i.e., similarity of query to reference). For sparsity, we use the average number of feature changes (which is the same as ℓ 0 norm) between the query and the explanation; for closeness, we use the median ℓ ∞ norm between the generated explanation and the original query as the metric for SEV © . For tree-based models, we use only SEV T as the metric since SEV T and ℓ 0 norm are equivalent; for credibility, we need some way of estimating P (•|X) since we cannot observe it directly, so we trained a Gaussian mixture model on the negative samples of each dataset , and used the mean log-likelihood of the generated explanations as the metric for SEV © and SEV F , for TOpt, since it has already been a sparse decision tree, then we don't need to calculate the credibility.Let us show that SEV © provides improved explanations. Here, we calculated the metric for different SEV © variants, SEV © and SEV ©+F (SEV © with flexible reference), and compared to the original SEV 1 , where SEV 1 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 ℓ ∞ 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 SEV 1 . SEV © was designed to trade off SEV -for closeness, so it is surprising that it sometimes performs strictly better on both metrics, particularly for the COMPAS, Diabetes, and German Credit datasets. Figure 5 : Explanation performance under different models and metrics. We desire lower SEV -for sparsity, lower ℓ ∞ 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 SEV © 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.It is reasonable since the references are the cluster centroids for the negative samples, so the explanations are more likely to be located in the same high-density area. More detailed values for those methods and metrics are shown in Appendix H.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 in Figure 5a and 5b have already shown that with small modification of the reference, the credibility of the explanations is not affected. Figure 6a shows how SEV -and credibility change as we increase flexibility; SEV - sometimes substantially decreases while credibility is maintained. 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 [Wachter et al., 2017] , REVISE [Joshi et 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 ℓ 2 logistic regression (other information, including ℓ ∞ norms for counterfactual explanation methods, is in Appendix G). All SEV variants are in warm colors, while competitors are in 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 explanation sparsity. Importantly, sparsity is essential for human understanding [Rudin et 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 credibilityEven without optimization, our SEV -variants improve decision sparsity and/or closeness. If we are willing to 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-based SEV optimization can reduce the SEV without harming the closeness metric (ℓ ∞ ) and the credibility metrics (log-likelihood). The slashed bars represents the SEV -, ℓ ∞ and log likelihood metrics before optimization using different models, while the colored bars are the results after optimizing with All-Opt -. We have also compared our results with ExpO [Plumb et al., 2020] , which is a 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 in Appendix K. 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 it requires knowledge of the causal graph. Another limitation is that to make the explanation more credible, the threshold to stop searching the SEV hypercube is not easy to determine. Future studies could focus on on these topics. Overall, our work has the potential to enhance a 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.The datasets were divided into training and test sets using an 80-20 stratification. The numerical features were transformed by standardization to have a mean of zero and a variance of one. The categorical features, which have k different levels, were transformed into k -1 binary variables using one-hot encoding. The binary characteristics were transformed into a single dummy variable using one-hot encoding. The sizes of the datasets before and after encoding are shown in The COMPAS dataset contains information on criminal recidivism in 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 felonies/misdemeanors, and whether the current charge is a felony.The Adult data is derived from U.S. Census statistics, including information on demographics, education, employment, marital status, and financial gain/loss [Dua and Graff, 2017] . The target variable of this dataset is whether an individual's salary exceeds $50,000.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 al., 2016a,b] . The outcome of interest is determined by the binary indicator known as the "hospital expires flag," which indicates whether or not a patient died during their hospitalization. We chose the following set of variables as features: age, preiculos (pre-ICU length of stay), gcs (Glasgow Coma Scale), heartrate_min, heartrate_max, meanbp_min (min blood pressure), meanbp_max (max blood pressure), resprate_min, resprate_max, tempc_min, tempc_max, urineoutput, mechvent (whether the patient is on mechanical ventilation), and electivesurgery (whether the patient had elective surgery).The Diabetes dataset is derived from 10 years (1999) (2000) (2001) (2002) (2003) (2004) (2005) (2006) (2007) (2008) of clinical care at 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 medications, and so on. We consider whether the patient will return to the hospital within 2 years as a binary indicator.The German credit data [Dua and Graff, 2017] uses financial and demographic indicators such as checking account status, credit history, employment/marital status, etc., to predict whether an individual will default on a loan.The FICO Home Equity Line of Credit (HELOC) dataset [FICO, 2018] is used for the Explainable Machine Learning Challenge. It includes a number of financial indicators, such as the number of inquiries on a user's account, the maximum delinquency, and the number of satisfactory transactions, among others. These indicators relate to 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 a 2-year period since opening their account.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 sharing. The survey includes several factors, including, age, income, gender, ethnicity, social protection,economic protection, truth ("What is the likelihood that the above headline is true?"), familiarity ("Are you familiar with the above headline (have you seen or heard about it before?)? )"), Importance ("Assuming the headline is completely accurate, how important would you consider this news to be?"), Political Concordance ("Assuming the above headline is completely 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 to share it?").In this section, we will mainly show how sensitive SEV -is when we change the reference. Figure 8 shows an example of this, where moving the reference further away from the query (from r to the r ′ ) changes the SEV -from 2 to 1. 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 a 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 in the yellow area has an SEV - of 1 instead of 2 when the reference moves from r to r ′ . If the reference point is r, then the query needs to align the feature values along both x and y-axis to reach the SEV Explanation with reference r (recall an example of SEV -explanation in Figure 2 ) in Section 3.2, which is the same point as r. However, if the reference point is r ′ , then the query only needs to align the feature value along the x-axis to reach the SEV Explanation with SEV= 1, which is the light blue dot. Experiments have also shown that moving data points closer to the decision boundary might increase SEV -. The result on 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 -≥10). Hence, SEV -is sensitive to the reference. 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., 1984] algorithm so as to encourage negative clustering results.The original Soft K-Means (SKM) algorithm generalizes K-means clustering by assigning membership scores for multiple clusters to each point. Given a data setX = {x 1 , x 2 , • • • , x n } and Cclusters, the goal is to minimize the objective function J(U, V ), where U = [u ij ] is the membership matrix and V = {v 1 , • • • , v C } are the weighted cluster centroids. The objective is to minimize:J(U, V ) = n i=1 C j=1 u m ij ∥x i -v j ∥ 2 2 (5)where u ij is the (soft) membership score of x i in cluster j:u i,j = 1 C k=1 ∥xi-vj ∥2 ∥xi-c k ∥2 2 m-1 (6)and m > 1 is a parameter that controls the strength towards each neighboring point. When m ≈ 1, the SKM is similar to the performance of hard K-means clustering methods. When m > 1 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 a 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 ′ i for each instanceEQUATIONThe value of min{f (x i ) -0.5, 0} increases as x i is classified as positive and further away from the decision boundary. As m ′ 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 asEQUATION)We call this new objective function for encouraging negative clustering centers Score-based Soft K-Means (SSKM). In our experiments, the clustering is applied to the dataset after PaCMAP [Wang et al., 2021] , and the feature mean of all samples in a 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 ℓ 2 distance) to them in the PaCMAP embedding space for SEV © 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. It 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 10 . 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 SEV © . This section presents how the flexible-based SEV (SEV F ) has done to determine the flexible references. The key idea of finding the reference is to do a 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 1 Reference Search for Flexible SEV 1: Input: The negative samples X -, flexibility ϵ, reference r, grid size G 2: Output: Flexible reference r′ 3: Initialization: r′ ← r 4: for each feature j ∈ J , where rj is the reference value of feature j in X -do 5:q j ← quantile(X - j , rj ) {Quantile location of rj } 6:B + j ← percentile(X - j , q j + ϵ) {The upper range} 7:B - j ← percentile(X - j , q j -ϵ) {The lower range} 8: B (g) j ∼ Uniform[B - j , B + j ], g = 1, • • • , G 9: P (g) j ← f ([r 1 , • • • , B (g) j , • • • rJ ]), g = 1 • • • G {Slight changer′ j ← B (g ′ ) j{Update for flexible references} 12: end for 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 3 (Efficient SEV T Calculation) for checking all negative pathways conditions for each query and calculating the number of feature changes.Algorithm 2 Preprocessing -Information collection process for SEV T 1: Input: Decision tree DT 2: Output: DT -, a dictionary of paths to negative predictions for each internal node encoding Baseline models were fit using sklearn [Pedregosa et al., 2011] implementations in Python. The logistic regression models L1 LR and L2 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 a max depth of 3. For tree-based methods comparisons, the decision tree classifiers were fit using sklearn [Pedregosa et al., 2011] and TreeFARMS packages [Wang et al., 2022b] . Since GOSDT methods require binary input, we used the built-in threshold guessing function in GOSDT to binarize the features with set of parameters n_est=50, and max_depth=1. All the models are trained using a RTX2080Ti GPU, and with 4 core in Intel(R) Xeon(R) Gold 6226 CPU @ 2.70GHz.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 a batch size of 128, a 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 for 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, it is important to ensure that the reference has a negative prediction. If the reference is predicted as positive, then the SEV -may not exist, and a sparse explanation is no longer meaningful. Thus, we add a term to penalize the reference if it receives a positive prediction:ℓ Pos_ref (f ) := n i=1 max(f (r i ), 0.5 -θ)where θ > 0 is a margin parameter, usually θ = 0.05. This term is (0.5 -θ) as long as the reference is predicted negative. As soon as it exceeds that amount, it is penalized (increasing linearly in f (r)).To put these into an algorithm, we optimize a linear combination of different loss terms,EQUATIONTherefore, we are tuning both C 1 and C 2 to find a model with sparser explanations without performance loss through grid search. For cluster-based SEV, the cluster centers are recalculated based on the new model every 5 epochs.In this section, we provide detailed information on other kinds of counterfactual explanations generated by the CARLA package [Pawelczyk et al., 2021] on different datasets for logistic regression models. Table 6 shows the number of features changed and the ℓ ∞ 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' ℓ ∞ 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 et al. [2011] . The parameter n_components for each dataset is selected based on the clustering result mentioned in Appendix C. Here, we are using the same Gaussian Mixture Model for evaluating whether the explanation is within a high-density region. In this section, we show how SEV 1 , SEV © , SEV ©+F can increase the similarity metrics or reduce the sparsity explanations. All the models are trained and evaluated 10 times using different splits, and evaluated for their mean SEV -, mean ℓ ∞ , as well as their explanation time for each query.Table 7 shows the model performance and SEV 1 on various datasets. SEV 1 is considered as a base case for other SEV -variants to compare with. Table 7 shows that SEV 1 yields very high ℓ ∞ 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 SEV © 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 1 (reported in the parenthesis). The Mean ℓ ∞ column reports the mean ℓ ∞ and the percentage reduction compared to SEV 1 . On most datasets, SEV © increases, and ℓ ∞ 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 to the decision boundary of the model as each query is trying to find the closest (in ℓ 2 distance) negatively predicted reference point, which might provide less sparse explanations.Table 9 shows the model performance and SEV ©+F (SEV © with variable reference) on various datasets with different flexibility levels. The Mean SEV F column reports the mean SEV -for the model and the decrease in mean SEV -in percentage compared to SEV 1 (reported in the parenthesis).The Mean ℓ ∞ column reports the mean ℓ ∞ and the percentage reduction compared to SEV 1 . It is evident that with SEV F , SEV -decreases, but the ℓ ∞ 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 SEV F , and the higher the proportion, the larger decrease in SEV -the model can achieve. 0.9 ± 0.0 0.9 ± 0.0 0.87 ± 0.01 0.85 ± 0.0 1.21(2.54%) 0.58(-72.12%) -18.22(-5.62%) 1.35 ± 0.15 0.10 0.9 ± 0.0 0.9 ± 0.0 0.87 ± 0.01 0.85 ± 0.0 1.22(3.39%) 0.58(-72.12%) -18.12(-5.04%) 1.41 ± 0.14 0.20 0.9 ± 0.0 0.9 ± 0.0 0.87 ± 0.01 0.85 ± 0.0 1.22(3.39%) 0.58(-72.12%) -18.12(-5.04%) 1.43 ± 0.14In this section, we will mainly show the model performance of All-Opt © and All-Opt 1 , which are the two gradient-based optimization methods used for SEV © and SEV 1 optimization. Table 10 shows the SEV 1 , ℓ ∞ and model performance after applying All-Opt 1 methods for different models on different datasets with different levels of flexibility. It is evident that All-Opt F has provided a significant decrease in SEV, so that its values are close to 1, providing much sparser explanations without model performance loss and closeness/credibility loss in explanations. Similar findings are observed in Table 11 . In this section, we show the model performance and SEV T values for different types of tree-based models. As discussed in section 4.2, the similarity and closeness metrics in SEV T are all ℓ 0 norm, so we only need to compute the mean SEV T for each tree. Table 12 shows that most of the tree-based models can provide sparse explanations (SEV T ≤ 2), and we can also find a decision tree with the same model performance as the other tree-based models from SEV T =1 to TOpt. For the ExpO comparison experiment, we used the fidelity metrics from Plumb et al. [2020] 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: 1D 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., 2018] accurately approximates f in the neighborhood N x , which is equivalent to minimizing:ℓ fed (f, g, N x ) = E x ′ ∼Nx [g(x ′ ) -f (x ′ )] 2 .(10) The local model g's are linear models, and the N x are points sampled normally around the original query. The 1D version of Fidelity regularization requires sampling the points around each feature of x at a time, which saves time and computational complexity. Based on the above equation, we rewrite the overall objective function as:min f ∈F ℓ BCE + C F ℓ fed (11)where ℓ BCE is the Binary Cross Entropy Loss to control the accuracy of the training model, C F 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 1D Fidelity (1DFed) and Global Fidelity (Fed) regularizers. Comparing the mean SEV 1 of Table 13 with Table 7 , it is evident that with the optimization through Fed or 1DFed, the optimized models do not provide sparse explanations. In addition, it takes a long time to 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 easier to calculate. 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, it adds one to SEV -. Therefore, for the internal nodes along the SEV -path, if N i has a sibling leaf node, if we goes up to its parent node and goes the opposite direction to change the query value for counterfactual explanation, the modified instance will be directly predicted as negative, which leads to SEV -being equal to 1 in this case.Figure 11 shows an example for SEV T being exactly 1, and a case illustrating that if N does not have a sibling or any internal node in its decision path that has a negatively-predicted child leaf, SEV T should be greater than or equal to 1. In Figure 11 , 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 a specific instance. The person icon with a plus sign is N i that we would like to calculate SEV T 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 4 , it is easy to see that if we go up to node C and goes the opposite direction as the decision path for x i , then you can directly get a negative prediction.In other words, if you change the feature C in the query to make it doens't satisfy the node C 's condition, then it can be prediction as negative, which means that SEV T =1.For SEV T ≥ 1 case, if the query predidcted as positive in node 7 , since it 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 E . However, if we don't know the query x i 's value, then I am unable to know whether I need to change the condition in node E for higher SEV T . Therefore, in this case SEV T can be only guaranteed to be greater or equal to 1. • The authors are encouraged to create a separate "Limitations" section in their paper.EQUATIONEQUATION- -- -- -- SEV F 36.71 -- -- -- -- SEV © 28.02 -- -- -- -- SEV T 22.50 -- -- -- --• 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 a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text 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 fairness. • 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at 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, or 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. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Yes, we have error bars for the time execution for each methods and the GPU and CPU details in Appendix F.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 as well as estimate the total compute.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. In Table 1, what do the gray numbers represent?
2. In line 199, there are duplicate "and"s.
limitations: 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.
paper_summary: paper_summary: The authors build on top of the Sparse Explanation Value approach by
Sun et al and provide improvements in terms of closeness and
credibility.
strength_weakness: strength_weakness: 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.

Additionally, 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, which is the
setting used in the experiments, the main problem is the cost of the
change, and slightly modifying two features could be less
expensive than modifying a single one by a larger value. This should
be better discussed in the paper.
questions: questions: 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?
limitations: limitations: The approach is very incremental, and the main extension substantially
restricts the applicability of the method.

The rebuttal of the authors did shade additional light on the novelty of the contribution.
paper_summary: paper_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.
strength_weakness: strength_weakness: The method is promising but its current version is hardly scalable.
questions: 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.  

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?
limitations: limitations: The method is not scalable.

Comments: title: Thanks for your answer
Discussion
comment: Thank you for the insightful comments and willingness to raise your score! We will add those clarifications to the revised manuscript.
Thanks for your detailed feedback, I appreciate the clarifications and your arguments in favour of the novelty of the contribution, I encourage you to better clarify these aspects in the manuscript. This said, I am happy to raise my score to a borderline accept.
Dear reviewer brvf, 

As the discussion period is approaching its conclusion in two days, we would like to kindly remind you that we have addressed your comments in our rebuttal. We would greatly appreciate any additional feedback you may have before the deadline. If you have any further questions or concerns, please do not hesitate to reach out, and we will do our utmost to respond promptly.

Thank you for your time and consideration.

Best regards, 

The Authors of Submission 11304
Thanks for your answers!
Hi all, the authors have provided detailed responses to the reviews. Please read the responses, and take advantage of the reviewer-author discussion period to ask for additional clarifications if needed.

In particular, reviewer bvrF has given the lowest score due to a number of issues she/he identified with the submission. The authors addressed these issues in their response. Does the reviewer agree with the response?
I acknowledge the rebuttal. Thank you for the detailed answer.