Consistent Sufficient Explanations and Minimal Local Rules for explaining the decision of any classifier or regressor
Authors: Salim I. Amoukou
Nicolas J-B. Brunel
Venue: NeurIPS 2022 Accept (2022)
Keywords: Interpretability
Trustworthy ML
Robust and Reliable ML
rule-based models
learning theory
random forests
explainable ai
consistency
tree-based models

Abstract: To explain the decision of any regression and classification model, we extend the notion of probabilistic sufficient explanations (P-SE). For each instance, this approach selects the minimal subset of features that is sufficient to yield the same prediction with high probability, while removing other features. The crux of P-SE is to compute the conditional probability of maintaining the same prediction. Therefore, we introduce an accurate and fast estimator of this probability via random Forests for any data $(\boldsymbol{X}, Y)$ and show its efficiency through a theoretical analysis of its consistency. As a consequence, we extend the P-SE to regression problems. In addition, we deal with non-discrete features, without learning the distribution of $\boldsymbol{X}$ nor having the model for making predictions. Finally, we introduce local rule-based explanations for regression/classification based on the P-SE and compare our approaches w.r.t other explainable AI methods. These methods are available as a Python Package.

Consistent Sufficient Explanations and Minimal Local Rules for explaining any classifier or regressor
Salim Amoukou
Nicolas J-B. Brunel
LaMME
LaMME
University Paris Saclay
ENSIIE, University Paris Saclay Quantmetry Paris
Stellantis Paris
Abstract
To explain the decision of any regression and classification model, we extend the notion of probabilistic sufficient explanations (P-SE). For each instance, this approach selects the minimal subset features that is sufficient to yield the same prediction with high probability, while removing other features. The crux of P- SE is to compute the conditional probability of maintaining the same prediction. Therefore, we introduce an accurate and fast estimator of this probability via random Forests for any data (X, Y) and show its efficiency through theoretical analysis of its consistency. As consequence, we extend the P-SE to regression problems. In addition, we deal with non-discrete features, without learning the distribution of X nor having the model for making predictions. Finally, we introduce local rule-based explanations for regression/classiicatioo based on the P-SE and compare approaches w.r.t other explainable Al methods. These methods are available as a Python package'.
Introduction
Many methods have been proposed explain specific predictions of machine learning models from different perspectives, such as feature attributions approaches [Lundberg and Lee, 2017, Ribeiro al., 2016), decision rules [Ribeiro et al., 2018), counterfactual examples [Wachter et al.. 2017] and logic-based [Shih et al., 2018, Darwiche and Hirth, 2020].
Among these categories, the most popular feature attributions approaches, in particular SHAP [Lundberg and Lee, 2017], which based on Shapley Values (SV) and aims at indicating the importance of each feature in the decision. One of the main reasons for SHAP's success is its scalability, nice representations of the explanations, and mathematical foundations. However, SV used in SHAP does guarantee the truthfulness of the important variables involved in given decision. Indeed, it is possible to construct simple theoretical models (defined on a partition of the feature space) for which SV cannot distinguish between local important and non-important variables (see conclusion in Amoukou et al. [2022]). Similar difficulties have also been highlighted by Ghalebikesabi et al. [2021] for SHAP and LIME [Ribeiro al., 2016]. This lack of guarantees is a major issue since the explanations may be used for high-stakes decisions. Moreover, Additive Explanations are not suitable when interactions occur in the model [Gosiewska and Biecek, 2019].
An appealing solution to the problem above is to use decision rules [Ribeiro et al., 2018] or logic- based explanations [Darwiche and Hirth, 2020, Shih et al., 2018] which gives local explanations that take into account interactions while ensuring minimality and guarantee on the outcome. However, these methods currently available in the general case (e.g., regression model, continuous
nttpp:///itthu.. http://ttthbcomooeeeee com/ imamoukou/acvo0
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

features, ...). Our objective is to extend these methods to more realistic cases by developing new consistent algorithms.
In this paper, we generalize the concept of Probabilistic Sufficient Explanations (P-SE) introduced by Wang et al. [2020]. P-SE is relaxation of logic-based explanation: it explains the classification of an example by choosing a minimal subset of features guaranteeing that, the model makes the same prediction with high probability, whatever the values of the remaining features (under the data distribution). Such a subset is called Sufficient Explanation (also known as sufficient reason or prime implicant [Shih et al., 2018, Darwiche and Hirth, 2020]).
We make several contributions. We extend the concept of Same Decision Probability (SDP) to the regression setting so that introduce a fast and efficient estimator of the SDP based on Random Forests and prove its uniform almost sure convergence. Our approach can deal with non-discrete features and does not need the estimation of the distribution of X, contrary to [Wang et al., 2020]. Our method can explain the data generating process (X, Y) directly or any learnt model (x, f(x).
extend Sufficient Explanations from classification regression. We
We introduce the probabilistic local explanatory importance which is the frequency of each feature to be in the set of all Sufficient Explanations. In particular, this indicates the diversity of the Sufficient Explanations. We introduce local rule-based explanations for classification or regression which are simultaneously minimal and sufficient. We compare our approaches w.r.t other explainable AI methods and provide a Python package that computes all our methods.
2 Motivations and Related works
The methods used to explain the local behavior of Machine Learning models can be organized into 5 groups: features attributions, decision rules, instance wise feature selection, logical reasoning approaches, data generation based or counterfactual examples. The benefits of feature attribution- based explanations, e.g., SHAP [Lundberg et al., 2020] or LIME [Ribeiro et al., 2016] is that they are easy to read, they can be applied to any model and are generally more scalable than their alternatives. On the other hand, they are sensitive to perturbations [Ignatiev et al., 2019], or can be fooled by adversarial attacks [Slack et al., 2020]. These downsides can be caused by the local perturbations used, which make them inconsistent with the data distribution.
Quite differently, instance- wise feature selection such as L2X [Chen et al., 2018) (018]ao or INVASE [Yoon et al., 2018] aims at finding the minimal subset of variables that are relevant for a given instance æ and its label y. Interactions can be captured in that way. In addition, the identification of minimal subset = S(x) is well-formalized and the objective is to find S such that 2(Y|X = x) R [(||Xs s = ats). However, these methods are not reliable because they are prone to approximation errors due to the training of several Neural Networks, and they provide no guarantees about the fidelity of the explanations [Jethani et al., 2021]. A similar approach is also developed in [Dhurandhar et al., 2018] called Pertinent Positive.
Anchors [Ribeiro et al., 2018] are local rule-based explanations that propose a solution to the reliability issue by providing an explanation with guarantees. It explains individual predictions of any classification model by finding a decision rule that reaches given accuracy for a high percentage of the neighborhood of the instance. However, the method is only available for classification, requires discrete variables, is unstable and tends to use more variables than needed.
Logical Reasoning Approaches such Sufficient Reasons [Shih et al., 2018, Darwiche and Hirth, 2020] select a minimal subset of features guaranteeing that, no matter what is observed for the remaining features, the decision will stay the same. It can be seen as an instance-wise feature selection but with guarantees of sufficiency and minimality (i.c.. no subset of the set satisfies the sufficiency condition). However, since the guarantees are deterministic, is often necessary to include many features into the explanation, making the explanation more complex and thus less intelligible. relaxation of this method is the Sufficient Explanations [Wang et al., 2020] that gives probabilistic guarantees instead of deterministic guarantees, i.e., it required that the prediction remains the same with high probability. gives a simple local explanation with guarantees while considering feature interactions and the data distribution. However, it is limited to classification with binary features and requires learning the distribution of the features. Moreover, the Sufficient Explanations are not unique, which causes sclection problem as the whole set of explanations is not interpretable.

---

In this work, we propose consistent method that efficiently finds the Sufficient Explanations of any data generating process (X, Y) or any model (X, (x)), without learning the distribution of X. In particular, we don't t need to have access to the model f. we need only the predictions, contrary to [Wang et al., 2020]. We propose local attributions that summarize the diversity of the Sufficient Explanations. In addition, we propose local sile-hased explanations for regression and classification models based on Sufficient Explanations. To the best of our knowledge, it is the first local rule-based explanations for regression.
3 Probabilistic Sufficient Explanations for Regression
Let assume have an i.d sample D,, (X*, ) such that (X,Y) P(x,)) where X E R2 and Y E R. We use uppercase letters for random variables and lowercase letters for their value assignments. For given subset S C [p). Xs (Xi)ses denotes subgroup of the features.
We define the explanations of an instance x as the minimal subsets æs. S C [p] such that given only those features, the model yiclds "almost" the same prediction y as the complete example with high probability, under the data distribution p(X). The main probabilistic reasoning tool that we use for explanations is the Same Decision Probability (SDP) [Chen et al., 2012]. For classification, it is defined as the probability that the classifier has the same output by ignoring some variables. To explain also regression models, propose the following definition of the SDP:
Definition 3.1. (Same Decision Probability of a regressor). Given an instance (a, y). the Same Decision Probability at level of the subset 5 C [1, W.r.t & = (I5, 233) is
SDPs (,) P ((Y y)² S t X .ts)
In a regression setting, the SDP gives the probability to stay close to the same prediction y at level t, when we fix X Ig or when Xg are missing. The higher is the probability. the better is the explanation powered by S. Note that for classification, the SDP is defined as SDPs (yi x) = P X s = .ss.. Although we present all the methods with the SDP for regression, they remain the same for classification, we only need to replace SDPs (1;; æ, 1) by SDPs (y) Now, we focus the minimal subset of features such that the model makes the same almost the same decision with a given (high) probability т.
Definition 3.2. (Minimal Sufficient Explanations). Given an instance (z. y). Sx(x) is a Sufficient Explanation for probability if SDPs (a) (v; xx, I) 2 x, and no subset Z of (x) satisfies SDPz (y: 2,t) 2 т. Hence, a Minimal Sufficient Explanation is a Sufficient Explanation with minimal size.
For a given instance, the Sufficient Explanation or Minimal Sufficient Explanation may not be unique [Darwiche and Hirth, 2020]. Furthermore, there may be significant differences among the Sufficient Explanations or Minimal Sufficient Explanations. We denote A-SE as the set of all Sufficient Explanations and M-SE as the set Minimal Sufficient Explanations. Thus, the number and the diversity of the explanations make the method less intelligible, as deriving one of them is not informative enough, and all of them are too complex to interpret. Therefore, we propose to compute the following local attributions that summarize the importance of each variable in A-SE/M-SE:
Definition 3.3. (Local eXplanatory Importance LXI). Given an instance (x, y) and its A-SE or M-SE. The local explanatory importance of x; how frequent æ; is chosen in the A-SE or M-SE
Contrary to classical local feature attributions like SHAP or LIME, the values of Local Explanatory Importance does not depend on the range of values of the predictions, and are interpretable by design. It corresponds to the frequency of apparition in the A-SE or M-SE, which allows reason about the relative difference between the attribution of each feature. Indeed, we can casily discriminate between the importance of variables in terms of probabilities compared to arbitrary values of SHAP LIME that depend on the model and its predictions. In our framework, a value equal to 1 means that this feature is present in all the A-SE/M-SE. Hence this feature is necessary to maintain the prediction. Moreover, the attributions of the features are sparse since they are based on the A-SE/M-SE.
Although Sufficient Explanations allow finding local relevant variables, we may want to know the logical reasons relating input and output. essence, explaining a decision means giving the reasons that highlight why the decision has been made. Therefore, we propose to extend
3

---

the Sufficient Explanations into local rules. A rule is simple IF-THEN statement, e.g., IF the conditions on the features are met, THEN make a specific prediction. Recall that given an instance a, a Sufficient Explanation is the minimal subset S C [p]. such that fixing the values Xs = 2 permits to maintain the prediction with high probability. The idea is to find the largest rectangle Ls(x)) = I (ai, bi], ai; by E IR given the indexes of the Sufficient Explanation S such that 25 (x( and Vz with 25 E Lz()), Syy z;)) 2 π.
S
Definition 3.4. (Minimal Sufficient Rule). Given an instance (æ, y). 5 a Minimal Sufficient |8| a., b.], a, b, E I. Minimal Sufficient Rule if Ls(x))
Explanation, the rectangle (x(x) argmaxL(<>) Vol(L(x)), 0g E Ls (x) and Vz, E Ls(x), SDPs (y: z,t) n.
Intuitively, the Sufficient Rule is generalization of the Sufficient Explanation. i... instead of satisfying the minimality/sfficienncy conditions of definition 3.2 if we fixed the values X s = Is. we want to satisfy these conditions all the elements of rectangle L (æ) that contains æs. We also want this rectangle to be of maximal volume such that it covers a large part of the imput space. Thus, the Sufficient Rule captures the local behavior of the model around æ while ensuring the minimality of the rule and guarantees on the outcome. Note that the volume of the rectangle L can be defined as [x)()( = P(X E L(x)) X(L(z)) with À the Lebesgue measure.
While Sufficient Rules are similar to Anchors introduced by Ribeiro et al. [2018], we emphasize two major types of differences. The first is that our framework for constructing rules can address regression problems, deal with continuous features without discretization, and do not need access to the model f. Moreover, if we have model f and instance x, Anchors search the largest rule (or rectangle) Ls(x) such that Po(f(() = Y| Xs E Ls(x)) 2 т under an instrumental distribution Q This is different from the Sufficient Rule that requires the stability of the prediction for all the observations in the rectangle i. Vxg E Lzf = Y| X = xz) 2 π. The second major difference is that the Sufficient Rule is based on the original distribution P(x,r) use conditional distribution P(Y|Xss s). At the contrary, anchors use local sampling perturbations (introducing another distribution Q). As we discuss in the next section, the effective computation of these rules is very different. Anchors use heuristic approach to find the minimal rule, which might produce suboptimal minimal rules. The Sufficient Rules satisfy a minimality principle by definition.
4 SDP, Sufficient Explanations and Sufficient Rules via Random Forest
In order to find the Sufficient Explanations Sy (x) and the corresponding Sufficient Rules Ls, (z). we need to compute the SDP for any subset S. However, the computation of the SDP is known to be computationally hard; even for simple Naive Bayes model, the computation of SDP is Na-hard [Chen et al., 2013]. Consequently, approximate criteria based on expectations instead of probabilities have been introduced by Wang et al. [2020]. They proposed to use a Probabilistic Circuit [Choi et al., 2020] to model the distribution of the features X and compute a lower bound of the SDP.
In this section, we propose a consistent estimator of the SDP for any distribution (X, Y). It is based on two ideas: Projected Forest [Bénard et al., 202 a.c] and Quantile Regression Forest [Meinshausen and Ridgeway, 2006). The Projected Forest is an adaptation of the Random Forest algorithm that estimates E|Y| |X s = s instead of E|Y = æ), and the Quantile Regression Forest uses the Random Forest algorithm to estimate the Conditional Distribution Function (CDF) P(Y S v = x).
The first step is to write the SDP as
SDPs az, f) P((Y - y) S 5 = as) Fs(y + vt x = =g) - Fs(y Vt X = as))
Equation 4.1 shows that the only challenge is to estimate the Projected (or Conditional) CDF Fs (s = xs)= = P(Y < X = æg). The variant of the original Random Forest proposed by Meinshausen and Ridgeway [2006] that estimates the CDF F(y) X = x)) P(Y I y = x) is not of interest to us because we want to estimate the Projected CDF Fs(y) X s = xs) for any S. The recent works by Bénard et al. [2021a.c] are much more relevant as they permit to estimate E| 3 = æs] from a classical Random Forest that has learned to predict E|y|x = x). The idea is extract new Forest called Projected Forest from the original Forest, which is a projection of the original Forest along the S-direction.
We propose to combine the ideas of Quantile Regression Forest and Projected Forest to estimate the Projected CDF (s( X s = æs). In addition, we prove the consistency of our estimator of the Projected CDF.

---

4.1 Random Forest and Condition Distribution Function (CDF) Forest
Random Forest (RF) is grown as an ensemble of l trees, based on random node and split point selection based on the CART algorithm [Breiman et al., 1984]. The algorithm works as follows. For each tree, an data points are drawn at random with replacement from the original data set of size n; then, at each cell of every tree, a split is chosen by maximizing the CART-criterion; finally, the construction of every tree stopped when the total number of cells the tree reaches the value b.- For each new instance æ, the prediction of the [-th tree is:
1
3,(X;:0) O:) (x1
mo. (m. D.)
(4.1)
Or, D..)
where:
O1,1 I.... k are independent random vectors, distributed as a generic random vector θ= = (0), (²2) and independent of 'D,, O contains indexes of observations that are used to build the tree, i.e. the bootstrap sample and @ indexes of splitting candidate variables in each node. 1: denotes the sequence of 0
Aa(;; θr, Dn.) is the tree cell (leaf) containing x:
N₂ (2: O,, D,.) the number of bootstrap elements that fall into A, (2:; O, D,)
( is the bootstrap component i.e. the number of times that the observation has been chosen from the original data. The trees are then averaged gives the prediction of the forest as:
1 mi. (ar, O1.k, D.) = k Σ mn. Oi, Dr, Dn)
(4.2)
The Random Forest estimator (Eq. 4.2) can also be seen adaptive neighborhood procedure [Lin and Jeon, 2006]. For every instance æ, the observations in Dn are weighted by Wn,; 1 Dn), i 1, ; n. Therefore, the prediction of Random Forests and the weights can be rewritten
(x()); (mse))
ma.((x (x, Or. Dv)) Σ (a; Oz.k, D.)Y", (x, Ozo, D.)
D.)) Σ
k (2;
Viewing Random Forest as an adaptive nearest neighbor predictor offers natural estimates of more complex quantities (Cumulative hazard function [Ishwaran et al., 2008], Treatment effect [Wager and Athey, 2017], and conditional density [Du al., 2021]). Therefore, just as E X x is approximated by weighted mean over observation of Y E[Ily X x] is approximated by the weighted mean over the observations y using the same weights wn, O1.k, Da). The approximation is
Fu|x = x, Oz.k, D.) = Σ (w; Orsk Dr) Dr)
(4.3)
To simplify notations, we omit OI...., θz. Dn and we write Fs(y|Xs = xs)) for any S.
4.2 Projected Forest and Projected CDF Forest
We describe the Projected Forest (PRF) and show how it is combined with the Quantile Regression Forest to build the estimator of the Projected CDF. The PRF algorithm has been introduced in Bénard al. [2021c,a]. The idea is project the partition of each tree of the forest the subspace spanned by the variables in S, thus we can estimate F X rather than F The computation of these partitions for each S can be computationally expensive high dimension. However, Bénard et al. [2021a] uses simple algorithm trick to derive efficiently the output of the Projected Forest without computing explicitly its partitions. Roughly, for computing the prediction of tree, the algorithm ignores the splits that use variables not contained in S. It works as follow: when an observation is dropped down the initial trees, and it encounters a split involving a variable i & S the observation is sent both to the left and right children nodes. As result, each observation falls in multiple terminal leaves of the tree. Thus, to compute the prediction of an instance Øs, we collect the set terminal leaves where it falls, and average the output Y of the training observations which belong to every terminal leaf of this collection. E x = æs) is estimated as the average outputs of the training observations in the intersection of the leaves where æg falls.
5

---

An efficient implementation of the PRF algorithm is detailed in Appendix. The associated PRF is (#s)
14, (xs) >i=1 ( where the weights are defined by
kx x N X ( (m (mg:
(w,)(
(4.4)
, D..)
where A (æss; , Dr)) is the leaf of the associated Projected 1-th tree where as falls and N((m)) (x; O1 Dr) is the number of bootstrap observations that falls in (m=) (ars; O₁ D.). There- fore, we approximate the Projected CDF Fs(y) Xs s = æ.)) = P(Y S y X s æs) as in Eq. 4.3 by using the weights of the Projected Forest defined in Eq. 4.4. The estimator of the Projected CDF is defined as: Fs X xz) Di= (
4.3 Consistency of the Projected CDF Forest
In this section, we state our main result, which is the uniform a.s. convergence of the estimator X = æs) to Fs X = æs). Meinshausen and Ridgeway [2006] showed the uniform convergence in probability of simplified version of the estimator of the CDF defined in Eq. 4.3, where the weights (a 1.k, p,,) are in fact considered to be non-random while they are indeed random variables depending on (or) Dr,- Moreover, the bootstrap was replaced by subsampling without replacement as in most studies that analyse the asymptotic properties of Random Forests [Scornet et al., 2015, Wager and Athey, 2017, Goehry, 2020J. However, Slie-Dit-ossaqee Maume- Deschamps [2020] showed the almost everywhere uniform convergence of both estimators (the simplified and the one defined Eq. 4.3) under realistic assumptions with all the randomness and bootstrap samples. We follow their works to prove the consistency of the PRF CDF Fs X = xs)) based on the following assumptions.
and
Assumption 4.1. Vx E Id, the conditional cumulative distribution function F(y|X= = x)) continu- ous.
Assumption 4.1 is necessary to get uniform convergence of the estimator.
Assumption 4.2. For E [kt. we assume that the variation of the conditional cumulative distribution function within any cell goes to O.
Vz E Rd VyE
[F(ll) - -(yl))))) $
sup AE D..)
Assumption 4.2 allows to control the approximation error of the estimator. If for all y. F(yl-) is continuous, Assumption 4.2 is satisfied provided that the diameter of the cell goes to zero. Note that the vanishing of the diameter of the cell is a necessary condition to prove the consistency of general partitioning estimator (see chapter 4 in Györfi et al. [2002]). Scornet et al. [2015] show that it is true RF where the bootstrap step is replaced by subsampling without replacement and the data come from additive regression models [Stone, 1985]. The result is also valid for all regression functions, with a slightly modified version of RF, where there are at least fraction y observations in children nodes, and the number of splitting candidate variables is set to I at each node with small probability. Under these small modifications, Lemma from Meinshausen and Ridgeway [2006] gives that the diameter of each cell vanishes.
Assumption 4.3. Let l and N,, o₁, Dr) (number of bootstrap observations in a leaf node), then there exists (n*)) with 0, and Va: Rd,, (2: O, D.,) 222 (Vv(ln(())))) with 3 > 1 a.s.
Assumption 4.3 allows us to control the estimation error and means that the cells should contain sufficiently large number of points so that averaging among the observations is effective.
To prove the consistency of the PRF CDF Fs(y) X 2s)) we only need verify the assumptions
4.1, 4.2, 4.3 on the parameters of the PRF CDF and the Projected CDF Fs(y) X s x..) P(Y < y X æs).
Assumptions 4.1 and 4.2 are satisfied for the Projected CDF and the PRF CDF's leaves. Since by definition (x=;; O₁, D.,) Ax O₁ Dn), if the variations within the cells of the RF 0f vn 2 nols(() [9(n)]
f(()) R(g(n)) < 3K 0, 3no

---

vanish (diameter goes to zero), it also vanishes in the Projected forest. In addition, if the CDF Fly|X X z) Fly X æs. X 3 2gg) is continuous, we can show by straightforward analysis of parameter-dependent integral that the Projected CDF F s = F.$) = f F F = as X3 3 = æg )p(2 ar s Jdan is also continuous. As we control the minimal number observations in the leaf of the PRF CDF by construction, Assumption 4.3 is also verified. Then, the PRF CDF satisfies also Assumption 4. 14.33 which ensures its consistency thanks to Theorem 4.4.
Theorem 4.4. Consider RF satisfying Assumptions I to 4.3. Then,
Ve E IR", sup [sl Xs = xs) - Es(ul X s æs) 4
WER
The complete proof and simulations showing the convergence of the estimator be found in Appendix.
4.4 Estimation of SDP, Sufficient Explanations and Sufficient Rules
In this section, we show how we compute the SDP, Sufficient Explanations, and Sufficient Rules using the PRF CDF estimator. We derive from the previous section the following consistent estimator of any SDPs (y: t):
SDPs = Fs + vi [xs = us) Fs(y - Vi |Xs = =s))
However, finding the A A-SE/M-SE using a greedy algorithm is computationally hard, since the number of subsets is exponential. Therefore, we propose to reduce the number of variables by focusing only on the most influential variables. We search the Sufficient Explanations in the subspace of the 10 variables frequently selected in the RF used to estimate the SDP, reducing the complexity from 2 to 210 This preselection procedure is already used in Bénard et al. [2021b.a], and it mainly based on Proposition I of Scornet et al. 1J,15,, which highlights the fact that RF naturally splits the most on influential variables. Note that the minimum number of selected variables is a hyperparameter.
To find the Sufficient Rules, we used the SDP's estimator SDPs. By using the fact that the PRF CDF is a tree-based model, and thus SDPs partitions the space like a tree or a Random Forest, we do not need to discretize the continuous space to find the largest rectangle. We only need to find the leaves compatible with the conditions of the Sufficient Rule defined in 3.4. Given a Minimal Sufficient Explanation S of an instance æ, we already a have a rectangle (s(x)) defined by the PRF CDF or SDPs that is the largest rectangle such that as E (s( and vz with æ5 e Ls(z), SDPs 2, SDDPSPPP sy: x, t) 2 π. By definition, it is the intersection of the cell of the trees where zs falls, namely nf A! (ms) (xs; O,, D.)). Thus, starting from no ((as)) (as: θ₁ D,).. which is also cell (leaf) of the Projected Forest, we can find all the neighboring leaf (rectangle) that we can merge with it to get the largest rectangle. We will see in the next section that it provides good insights about the local behaviour of the model.
How to choose the typerparameters. The main hyperparameters are: s the number of preselected variables, the minimal probability of changing the decision and i which corresponds to the radius of the ball center at the prediction in the definition 3.1 of the SDP for regression problems.
The choice of s < p is motivated by the fact that many datasets have intrinsic dimensions much lower than the ambient dimension. Our Selection criterion is based on Proposition 1 in [Scornet et al., 2015], which highlights the fact that RF naturally splits the most influential variables. However, any RF's importance measure s.t. Mean Decrease Accuracy [Breiman, 2001] or Impurity [Breiman and Cutler, 2003] can be used the RF algorithm known to adapt to the intrinsic dimension [Scornet et al., 2015, Klusowski, 2020]. Therefore, the choice of s is directly driven by the computation power available to explore the subsets. practice, we have always found coalitions S with probability above π = 0.9 with 10 for real world datasets. Otherwise, we suggest a trade-off between the maximal reachable size s and the highest probability.
We propose choosing ग = 0.9 as is an acceptable level of risk, but the user can increase/decrease this probability depending on the use case.
The most challenging hyperparameter to select is I; we recommend having an adaptive radius t(z) using the quantile of the conditional distributions Y Y|X æ, which is by-product of the
7

---

Quantile Regression Forest used for computing the SDP. For each observation, we choose the radius t(x) = lâ., (z). 91 a1 [z]] with a + Q2 a. We build then confidence interval of varying length but with constant confidence level across the dataset. This makes our approach as natural generalization of the SDP in the classification case by accounting for the uncertainty of the model to explain. In that case, the SDP and associated sufficient coalition should be read: "if X s æg is fixed, then there is a probability at least π of not changing the prediction significantly with level 1 so that Y E [0,, (x), Q1-02 (æ)] with probability л. For this reason, we suggest fixing 01 + 02 = a and π at standard level a = π = 0.9 agreeing with acceptable level of risks.
5
Experiments
We conduct three experiments in this section. The first compares the Sufficient Explanations. Suffi- cient Rules and LXI with state-of-art (SOTA) local explanations methods (SHAP, LIME, INVASE) in simple high dimensional regression model with small relevant features. Although this model is simple, SOTA (SHAP, LIME) have been shown to poorly detect the important variables of this model [Amoukou et al., 2021, Ghalebikesabi et al., 2021]. Then, we analyse the performance of the Sufficient Rules in a real world regression problem. Finally, we highlight the advantages of the Sufficient Rules in comparison with Anchors in real world classification datasets. More experiments can be found in Appendix.
To effectively compare different explanation methods, we use synthetic data since we need the ground truth. We use the following synthetic model: we have X E R", X E (0, Σ), Σ = 0.8Jp + 57p with p 100, I, the identity matrix, J, is all-ones matrix and linear predictor with switch defined as:
Y = (X1 + X2) + (Xs + X4)
(5.1)
The variables X, for i 6... 100 are noise variables. We fit a RF with sample size 10 k = 20 trees and the minimal number of samples by leaf node is set to t, = |/n x In(n) /250 for the original and the Projected Forest. The RD 99% on the test set of size 10 The RF used to compute the explanations of SHAP, LIME. The Projected Forest is also extract from the RF for the SDP approaches. We choose 0i = 0.05, dr- = 0.95 and π = 0.90. For INVASE, we use Neural Networks with 3 hidden layers for the selector model and the predictor model as in Yoon et al. [2018]. Notice that for SHAP. LIME and the SDP approaches. we used the same information (the learned RF) to retrieve the true explanation of the data. The performance of INVASE and the RF is the same, both model perfectly fit the data with a R² 99%.
SDP approaches SOTA (SHAP, LIME, INVASE) on regression. Here, we analyze the capacity of each method to discover the local important variables the model defined in Eq. 5. Indeed, Eq. 5.1 shows that if x5 I O. the model uses only the variables I1, T2 otherwise it uses the variables 23, Zzg- Thus, we try to find the top K = 3 relevant features for each sample. Note that K is not required input for SDP and INVASE, but K must be given for SHAP and LIME. We use the true positive rate (TPR) (higher is better) and false discovery rate (FDR) (lower is better) to measure the performance of the methods on discovery (i.e., discovering which features are relevant). In addition, as one of the objectives of each method is to find the minimal subset Øg that is relevant to the corresponding target y, we also compute a predictive performance metries that shows how well the projected predictor |||| X æs) selected by each method is close to the predictor on the full set of features E|Y| X 20). under the data distribution. Formally, for given subset S, we denote it
as P-MSE- = Ez
[ X = 2 - Xs = 2s))²
where Z ~ Px.
We obtain the following results for Sufficient Explanation (TPR= 99%, FDR= 2%. P-MSE- 0.02). INVASE (TPR= 99%. FDR= 87%, P-MSE- 0.006 ), SHAP (TPR= 73%. FDR= 27%. P- MSE= 0.79), and LIME (TPR= 50%, FDR= 49%, P-MSE= 5.01). We observe that the Sufficient Explanation succeeds to find the top K relevant variables and outperform the other methods by a significant margin. SHAP and LIME obtain the worst discovery rate. INVASE succeeds in finding the relevant variables, but it has a high FDR (87%), which means we cannot distinguish between the relevant and irrelevant variables since 87% of the selected variables are irrelevant. We also see that the P-MSE of INVASE is the lowest, which is not surprising as it selects all the relevant variables despite its high FDR. Indeed, this metric is not much affected by the FDR. The P-MSE of Sufficient
8

---

Explanations is also almost zero, and as above, SHAP and LIME perform worse than the other methods. In table we compare the LXI and SHAP values on 1000 observations having X5 > O. We compare the mean absolute values of SHAP and average LXI on this sub-population. Notice that on this model, these observations have a single Sufficient Explanation which the variables X3, Xa, X5- Both models give null attributions to the noise variables, but SHAP gives higher importance to the variables X1, X2 than the truly important variables X3, X4, X5. On the other hand, LXI gives non null attributions only the important variables. We refer to the Appendix for an additional comparison with SHAP in a case where there are several Sufficient Explanations.
Table 1: Global SHAP values (mean absolute) and average LXI on 1000 observations of the test set having Xs > O. Xnoises corresponds to the sum of the attributions of the noises variables (., for i == 6......00 100).
X1
X2
X3
X4
X5
X noises
3
LXI
0
1
0
SHAP
1.47
1.54
0.56
0.56
0.86
0.005
However, even if the Sufficient Explanation find effectively the top K relevant variables, it cannot provide a complete understanding of the local behavior of the regression model (the SOTA methods also), i.e., that it's the sign of Iı that matters. Thus, by extending the Sufficient Explanation into Sufficient Rule we can retrieve the complete story. We choose an observation (ax, y) such that its Sufficient Explanation found is S = X4, Xs, Xs). with æs = [-3.4, -4.41, 0.68). Although the Sufficient Explanation shows that fixing the value Es permit to maintain the prediction with high probability, the Sufficient Rule gives the additional information that we can also maintain the prediction within a small radius around y by satisfying the rule (a())) = (Xs > 0 AND - 4.45 s X4 -4.0 AND 3.67 < X3 < -3.58). The Sufficient Rule Lg(ar) catches perfectly the local behaviour of the model which says that despite the values of Ø3, 24, it's the sign of 25 that matters.
SDP approaches on real world regression. We demonstrate the performance and flexibility of the Sufficient Rules (SR) on a real world regression dataset. Since there are no ground truth explanations for real world datasets, of the SR as an indicator of the effectiveness of the explanations. Indeed, we can build a global model by combining all the Sufficient Rules found for the observations in the training set, and measure its performance on the test set. We set the output of each rule as the majority class (resp. average values) for classification (resp. regression) of the training observations that satisfy this rule. Note that some rules can overlap and an observation can satisfy multiple rules. To resolve these conflicts, we use the output of the rule with the best precision (AUC or MSE). We called this model Global-SR. We have experimented on Bike Sharing data [Kaggle, 2015] that contains 10886 records and 15 variables about historical usage patterns with weather data in order to forecast bike rental demand in the Capital Bikeshare program in Washington, D.C.
use the predictive performance and simplicity (number of variables used)
We split the data into train (75%)- test (25%) set and train a RF with k 20 trees and maximal depth = 14. It has mean absolute error MAE = 25 and R² = 94% on test set. We use the RF on the train set to generate the SR. Although the Global-SR covers 78% of the test set, we observe that it performs as well as the baseline model with MAE = 29, R² = 90% while being transparent in its decision process. Note that the rules of the SR on Bike Sharing Demand are based on 4.5 variables in average. We give examples of the learned rules: Ri (If Workingday
True and Hours [5.5, 6.5] THEN Bike rental demand Ro = {If Hours E [8.5, 9] and Year < 2011 and month 2 5 THEN Bike rental demand 192). The number of observations that satisfy these rules is 134, 133 for the rules R1, R2 respectively with mean absolute eтror M AAR 12, MAER, = 30.
20).
Anchors vs Sufficient Rules (SR). To compare our methods w.r.t to Anchors, we have to consider a classification problem. We use three popular real world datasets: Compas (n = 6167, , = 14)[Larson et al., 2016], Nhanesi (n 8593, p 17) [CDC, 1999-2022], and Employee Attrition (n = 1470,p p- 27) [Kaggle, 2017] which we split into train (75%)- test (25%) set, and train a RF with the parameters of the previous section. We use the RF to generate the local rule- explanations with Anchors and the SDP approach (Sufficient Rules) to explain the RF's predictions on the test set. We aim to evaluate the generalization of each explanation across the population. Thus, we measure the following metrics, Coverage (higher is better): what fraction of unseen instances fall
9

---

in the rule and Correctness (higher is better): average number of unseen instances that satisfy the rule and has the same output than the observation that generate the rule, Sparsity (lower is better): the mean, variance and maximal size of the rule (number of variable on which it is based).
Table 2: Results of the Correctness (Acc), Coverage (Cov), and Sparsity (Sprs) on Compas, Nhanesi, ATTRITION of the Sufficient Rules (SR) and Anchors. The vector of Sprs (mean, std, max) corresponds to the mean, variance, and the max values of the rules.
COMPAS
NHANESI
ATTRITION
Acc
Sprs
Cov
Acc
Sprs
Cov
Acc
Sprs
Cov
SR
0,95
(1.6, 0.96.
0.30
0.97
(1.3, 0.65,
0.41
0.95
(1.15, 0.90, 9)
0.76
Anchors
0.92
(1.83, 1.89, 11)
0.23
0.96
(1.8, 3.91, 16)
0.31
0.95
(0.82, 4.24, 21)
0.74
In table 2, we observe that both model have a high accuracy in all datasets, but SR consistently outperforms Anchors on all datasets.
On the other hand, Anchors uses many more features. Indeed, by sampling marginally (i.e. assuming that the features are independent) Anchors can succeed to find accurate and high coverage rule, but fact, we can observe in table that Anchors tends to give much longer
at the cost of optimality. rules. While the observed maximal size of SR is 9 in all dataset, Anchors can provide a rule of size 12 (Compas), 16 (Nhanesi). 23 (Attrition). For instance, the size distribution of Anchors on Nhanesi is represented with the following dictionary {size: count); J: {1: 704, 2 : 127, 3: 71, 4
21, 5 : 13, 10, 7 : 10, 9, 9 9, 10 : 4, 11 2, 12 4, 13 5, 14 1, 16 : 1}. and the corresponding distribution for the SR is (1: 775, 2: 145, 3 52, 4 9, 5: 12, 7 43. Note that
this is a significant back of Anchors, as simplicity of the explanations is an essential desideratum for explanation methods. We give additional experiment confirming these results in the Appendix.
Another desirable property of explanation methods is stability, i.e., nearby observations must have the same explanations. Here, we evaluate the stability of the methods w.r. input perturbations. For each observation æ, we compare rule with the rules of 50 noisy versions of x obtained by adding random Gaussian noises (0, X I) to the values of the features with 0.1. The perturbation is small enough to not change the prediction. For each dataset (Compas, Nhanesi, Attrition), we randomly perturb 100 observations in the test set (50 times), and we observe in average 10 (std=76), 6.83 (std=139), 14 (std=58) different rules for Anchors respectively, while we have 1.5 (std=0.25), 1.1 (std=1.9), 1.13 (std=0.13) for SR, resp. It shows the large instability of Anchor compared to SR. Indeed, even when e = O, Anchors gives different rules, e.g., on Compas its has 7 (std=70) different rules in average with no perturbations. Results for other values of e can be found in Appendix.
These experiments demonstrate that the SR gives more optimal rules than the one returned by Anehors. We also conduct an additional experiment in the Appendix confirming this claim in setting where we know the ground truth.
6 Conclusion
In this work, we introduce fast and consistent estimator of the Same Decision Probability and propose natural generalization of the SDP for regression problems. Thus, we introduce the first local rule-based explanations for regression. We give consistent estimates of three local explanation methods: Minimal Sufficient Explanations, Local eXplanatory Importance, and Minimal Sufficient Rules for any data. We prove that these methods considerably improve local variable detection over state-of-ther the- algorithms while ensuring minimality, sufficiency, and stability. Our generalization of SDP and Minimal Sufficient Rules are tightly related. They are linked by Random Forest, which is computationally and statistically efficient estimator of the SDP and gives the partition that is translated into interpretable rule. Therefore, our method is principally suitable for datasets where tree-based models work (e.g., tabular data). In future works, we aim at improving the interpretability and confidence of the Sufficient Rules by taking into account uncertainty estimates of their predictions.
This work has been done in collaboration between Stellantis and Laboratoire de Mathématiques et Modélisation d' f'vryy (LaMME) and was supported by the program Convention Industrielle de Formation par la Recherche (CIFRE) of the Association Nationale de la Recherche et de la Technologic (ANRT).
Acknowledgments.
10

---

References
Salim Amoukou, Nicolas JB Brunel, and Tangi Salaün. Accurate and robust shapley values for explaining predictions and focusing on local important variables. arXiv preprint arXiv:2106.03820, 2021.
Salim I. Amoukou, Tangi Salaün, and Nicolas Brunel. Accurate shapley values for explaining tree-based models. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 2448-2465. PMLR, 28- 30 Mar 2022. URL https: httpa/////ccceiig...... mlr www.mr.rr..../p..mmmmmmmmmmmm..m /ttp//v1////// www.aau22aaaaa..aaoaaaaaaa htm.l.ll222...........
Clément Bénard, Gérard Biau, Sébastien Da Veiga, and Erwan Scornet. Shaff: Fast and consistent shapley effect estimates via random forests. arXiv preprint arXiv:2 2021a.
Clément Bénard, Gérard Biau, Sébastien Veiga, and Erwan Scomet. Interpretable random forests via rule extraction. In International Conference on Artificial Intelligence and Statistics, pages 937-945. PMLR, 2021b.
Clément Bénard, Sébastien Da Veiga, and Erwan Scomet. Mda for random forests: inconsistency, and a practical solution via the sobol-mda. arXiv preprint arXiv:2 2021c
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Leo Breiman and A Cutler. Setting up, using, and understanding random forests v4. O. University of California, Department of Statistics, 2003.
Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone. Classification and regression trees. wadsworth int. Group, 37(15)2237-251, 1984.
CDC. National health and nutrition examination survey, 1999-2022. URI. https:t/ttt..t.... cdc. Bov/Ncch/Nhanes// MaanessDDefall aspx.
Jianbo Chen, Le Song, Martin Wainwright, and Michael I. Jordan. Learning explain: An informition-theerrttie perspective on model interpretation. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 882-891. PMLR, 2018. URL http://proceedings mlr .press/ v80/ ch0/chen18j html.
S. Chen, Arthur Choi, and Adnan Darwiche. The same-decision probability: A new tool for decision making. 2012.
Suming Chen, Arthur Choi, and Adnan Darwiche. An exact algorithm for computing the same- decision probability. IJCAI 13, page 2525-2533 AAAI Press, 2013. ISBN 9781577356332.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. Technical report, Technical report, 2020.
Adnan Darwiche and Auguste Hirth. On the reasons behind decisions. arXiv preprint arXiv:2002.09284, 2020.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. Advances in neural information processing systems, 31, 2018.
Qiming Du, Gérard Biau, François Petit, and Raphaël Porcher. Wasserstein random forests and appli- cations in heterogeneous treatment effects. In International Conference on Artificial Intelligence and Statistics, pages 1729-1737. PMLR, 2021.
Kevin Elie-Dit-Cosapee and Véronique Desuea-Dssehapps.. Random forest estimation of conditional distribution functions and conditional quantiles, arXiv preprint UrXiv:2006.0699) 2020.
Sahra Ghalebikesabi, Lucile Ter-Minassian, Karla Diaz-Ordaz, and Chris Holmes. On locality of local explanation models. arXiv preprint 1XXv:2100.11645 2021.

---

Benjamin Goehry. Random forests for time-dependent processes. ESAIM: Probability and Statistics, 24:801-826, 2020.
Alicja Gosiewska and P. Biecek. Do not trust additive explanations. arXiv: Learning, 2019.
László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. distribution-free theory of nouparametric regression, volume 1. Springer, 2002.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Sine Silva. On validating, repairing and refining heuristic ml explanations. arXiv preprint arXiv: 2019.
Hemant Ishwaran, Udaya B Kogalur, Eugene H Blackstone, and Michael S Lauer. Random survival forests. The annals of applied statistics, 2(3):841-860, 2008.
Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs. and Rajesh Ranganath, Have we learned explain?: How interpretability methods can learn to encode predictions in their inter- pretations. In International Conference on Artificial Intelligence and Statistics, pages 1459-1467.
PMLR, 2021.
Kaggle. Bike sharing demand, 2015.
URL https://www.kggg/
bike-sharing-dene demand.
Kaggle. Ibm hr analytics employee attrition performance, 2017. URL www kaggle com/
pavansubhasht/ www.aaaltiisaattrrtiiitit dataset.
Jason Klusowski. Sparse learning with cart. Advances in Neural Information Processing Systems, 33: 11612-11622, 2020.
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. How analyzed the compas recidivism algorithm, 2016. URL https://w/wt http:////wwwwppppbllleeee propublica. org/article how-we- analyzed cnalyzed-che-compaa. sate--coppa--reidivieeeeee
Yi Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Journal of the American Statistical Association, 101(474)5578-590, 2006.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. I. Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Informaionn Processing Systems 30, pages 4765 4774. 2017.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):56-67, 2020.
Nicolai Meinshausen and Greg Ridgeway. Quantile regression forests. Journal of Machine Learning Research, 7(6), 2006.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Erwan Scornet, Gérard Biau, and lean-Philipee Vert. Consistency of random forests. The Annals of Statistics, 43(4):1716-1741, 2015.
Andy Shih, Arthur Choi, and Adnan Darwiche. A symbolic approach to explaining bayesian network classifiers. arXiv preprint arXiv: 100.1805.03300 2018.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference AI, Ethics, and Society, pages 180-186, 2020.
12

---

Charles J. Stone. Additive Regression and Other Nonparametric Models. The Annals of Statistics, 13(2):689 705, 1985. doi: 10.1214/aos/ 176349541. URL https://doi. http:///ooo.r///////// 10. 1214/ //aos/ 1176349548.
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech., 31:841, 2017.
Stefan Wager and Susan Athey, Estimation and inference of heterogeneous treatment effects using random forests, 2017.
Eric Wang, Pasha Khosravi, and Guy Van den Broeck. Towards probabilistic sufficient explanations, In Extending Explainable Al Beyond Deep Models and Classifiers Workshop at ICML (XXAI), 2020.
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. Invase: Instance-wise variable selection using neural networks. In International Conference on Learning Representations, 2018.
[1] Alexander, J.A. & Mozer, M.C. (1995) Template-based algorithms for connectionist rule extraction. In G. Tesauro, D.S. Touretzky and T.K. Leen (eds.), Advances in Neural Information Processing Systems 7, pp. 609-616. Cambridge, MA: MIT Press.
[2] Bower, J.M. & Beeman, D. (1995) The Book of GENESIS: Exploring Realistic Neural Models with the GEneral NEural Simulation System. New York: JELLOS/Sprigge--Velaag.
[3] Hasselmo, M.F., Schnell, F. & Barkai, E. (1995) Dynamics learning and recall at excitatory recurrent synapses and cholinergic modulation in rat hippocampal region CA3. Journal of Neuroscience 15(7).5249-5262.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We present the Minimal Sufticient Explanations, the Local eXplanatory Importance (LXI), and the Sufficient Rules in Section 3. While the Sufficient Rules and LXI are new, the Sufficient Explanations are generalization of existing works so that they can also address regression problems, deal with continuous features, and are more efficient to estimate. We present all the theoretical framework in Section 4 and their complete proofs in Appendix. We provide Python package that computes our methods. Finally, we demonstrate the advantage of our methods w.r.t SOTA on real world datasets in section 6.
(b) Did you describe the limitations your work? [Yes] Yes, we remind in the conclusion that approaches are appropriate for datasets where tree-based models work. (c) Did you discuss any potential negative societal impacts of your work? [Yes] Our work is fully dedicated to the positive societal impacts. Indeed, we propose new methods that outperforms SOTA in local important feature detection. In addition, we propose new rulc-based explanation that is more faithful to the data distribution than prior works (Anchors).
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We conform to the ethics review.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state all the theoretical results in Section 4.
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proof' are in Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We provide Python package and the results https: //github. com/ sallslllla salimamoukou/ acv00.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix.
13

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cited the datasets that used.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
It can be found at htttps://githii
com/s com/sal imamoukou/ matoouuuuuucv... acv00.
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [No] Not relevant
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] Not relevant
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [No] Not Relevant
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [No] Not relevant
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [No] Not Relevant
14


Reviews:
[{"review_id": "zEa2A8_tyzk", "reviewer": "Reviewer_HAsx", "summary": "This paper focuses on the problem of explaining the model output by extending the notion of probabilistic sufficient explanations (P-SE) to regression problems and non-binary settings. To that end, the authors extend the notion of same decision probability (SDP) to regression tasks and propose an estimator for it based on ideas from projected forest and quantile regression forest. Finally, they also introduce a local-rule based explanation, namely minimal sufficient rules, by generalizing sufficient explanations.", "questions": "How does the local explanatory importance compare, for example to SHAP values, on the tasks discussed in the experiments section? I am also unsure about its value as local feature attribution in practical settings, as it requires computing the A-SE or M-SE first which is expensive. (Unless there’s an efficient algorithm to compute/estimate it, which I could not find in the paper).\n\nI would encourage the authors to also evaluate the proposed explanations on real-world benchmark datasets for regression tasks. In the synthetic model, most features are noise variables which is not what most real-world data or models would look like.\n\nTable 1: Is correctness the same as consistency described in the previous paragraph (end of page 8)?\n\nLines 359-360: typo with comma and decimal points", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(+) The paper proposes several local explanation methods to address an interesting problem of explaining regression models.\n\n(+) A fast estimator for the SDP is also a novel and significant contribution. A theoretical analysis of its convergence is provided as well.\n\n(+) The paper is overall well written, and related works are discussed clearly.\n\n(-) For empirical evaluation on regression tasks, only a toy example is considered. \n\n(-) Local explanatory importance was introduced but not discussed or evaluated further.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YxfmdfkncgW", "reviewer": "Reviewer_rsCo", "summary": "In this paper, the authors propose a framework that can find sufficient explanations for any model of the form $x,f(x)$ and don't explicitly require access to the black box model $f$. One of their key claims to is to propose the first method to provide local rule-based explanations for the regression problem. They leverage prior art on Same Decision Probability (SDP) and in order to obtain a consistent SDP estimator to obtain MSE's they build upon ideas from Quantile Regression Forests and Projected Forests. Certain heuristics are used to alleviate the computational burden which are also inspired from more recent prior art. Empirical results include comparison against rule-based methods such as Anchors, etc to indicate better performance.", "questions": "1) How would you justify choices of certain parameters/heuristics as mentioned above ?\n\n2) What notion of stability are you presenting here (line 387). There are several notions of stability within the XAI literature hence mathematical definition or citation should  be provided ? For example is it the stability defined from here (Alvarez-Melis David, Jaakkola Tommi S. On the robustness of interpretability methods -  ICML Workshop on Human Interpretability in Machine Learning. 2018.)\n\n3) I do not see any citation or comparison w.r.t Contrastive Explanations techniques (https://arxiv.org/pdf/1802.07623.pdf) ? These have been applied successfully to tabular data also and seem very relevant work to compare against? https://arxiv.org/abs/1906.00117\n\n\n", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1) Authors try to address a relatively unaddressed problem on local rule-based explanations for regression problems.\n2) Empirical results and overall writeup are coherent with the theme the authors wanted to convey.\n\n**Weakness**\n\n1) Choice on certain heuristics like choosing 10 (line 290) seem to be directly used from prior art with no justification.\n2) Limited scope of applicability to tabular datsets only", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ItTKrHNjHSr", "reviewer": "Reviewer_bHU5", "summary": "This paper proposes a method for finding important features as Consistent Sufficient Explanation.\nThe essential building block of the method is the conditional probability estimation with conditioning on arbitrary subset of the features.\nThe authors proposed using Quantile Regression Forest and Projected Forest to estimate such conditional probability.\nThe authors also proved that the estimated conditional probability converges to the true probability as the number of samples goes to infinite.\nThe experimental results show that the proposed estimator provides more accurate estimate of important features than the existing methods such as LIME, SHAP, INVASE, and Anchors.", "questions": "Are there any other possible approaches for estimating the conditional probability estimation with conditioning on arbitrary subset of the features?", "limitations": "The authors mentioned that the proposed method is suitable for tabular data.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n### Originality\nThe notion of Consistent Sufficient Explanation was proposed in a previous study.\nThe major novelty of the paper is therefore on constructing an estimator of the conditional probability with conditioning on arbitrary subset of the features.\nThis will be a topic that is less explored in the literature.\nThe proposed estimator based on Quantile Regression Forest and Projected Forest seems reasonable, particularly for tabular data.\n\n### Clarity, Quality\nBoth the notion of Consistent Sufficient Explanation and its extensions as well as the proposed estimator are described clearly.\n\n### Significance\nThe results on the experiments with synthetic data and a few real world datasets looks promising.\n\n## Weakness\n*(My comment here is rather suggestion than Weakness.)*\nIn the paper, the authors focused on the conditional probability estimation based on random forest.\nI wonder if there is any other type of approaches we can think of.\nDiscussing possible alternative approaches would be beneficial to the readers.\nOne naive approach would be to train a generative model $p(X_{-S} | X_S)$, e.g., by using neural networks [Ref1,2,3,].\nWe can then estimate the conditional probability $p(Y | X_S) = \\int p(Y | X_S, X_{-S}) p(X_{-S} | X_S) d X_{-S}$, e.g., by sampling $X_{-S}$ from the generative model.\nAlthough this is apparently computationally expensive, this can be an alternative approach when the tree-based models are not appropriate such as images.\n\n[Ref1] Variational Autoencoder with Arbitrary Conditioning\n[Ref2] ACFlow: Flow Models for Arbitrary Conditional Likelihoods\n[Ref3] Arbitrary Conditional Distributions with Energy\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4g7iexM6Zss", "reviewer": "Reviewer_aVcg", "summary": "The paper proposes LXI, a feature importance metric, and Minimal Sufficient Rule, a generalization of Minimal  Sufficient Explanation. \n - A Minimal Sufficient Explanation (M-SE) of an instance in a model is the instance's smallest subset of features such that, w/ high probability, the model's prediction using the subset is close to the prediction when using all features.\n - LXI defines the important features of an instance in a model to be the subset of features that frequently appears in the instance's M-SE. \n - A Minimal Sufficient Rule of an instance in a model is the maximal bounding box around a subset of the instance's feature values such that every M-SE to the instance is also a SE to every point inside the box.\n\nThe paper proposed to construct a Minimal Sufficient Rule using projected forest and quantile regression forest. ", "questions": "I'd appreciate if the authors can confirm or reject my understanding of the various definitions in my summary. ", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Given my understanding of the definition of Minimal Sufficient Rule, I don't think I can make assertive judgment about the paper: As noted in the paper and the Anchor paper, a \"rule\" is a set of if-then predicates. How can a set of bounding boxes be interpreted as such?\n\nThe main contribution of the paper, the construction of a Minimal Sufficient Rule, is explained in only 10 lines (line 294-304). Perhaps a longer explanation together with some examples can help me better understand the the paper.\n\nWhat is the purpose of LXI? It seems disconnected to the rest of the paper. As a feature importance metric, it is not compared to other feature importance metric in the literature, nor is it used in the proposed method. \n\nThe paper claims to \"introduce\" Minimal Sufficient Explanations, but this is not true. It has been extensively studied in some of the references, e.g. Wang et al 2021. Perhaps this paper is the first to extend the definition to regression?", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept