# Consistent Sufficient Explanations and Minimal Local Rules for explaining
any classifier or regressor

Salim I. Amoukou
LaMME
University Paris Saclay
Stellantis Paris
&Nicolas J-B. Brunel
LaMME
ENSIIE, University Paris Saclay
Quantmetry 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 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
package111https://github.com/salimamoukou/acv00.

##  1 Introduction

Many methods have been proposed to explain specific predictions of machine
learning models from different perspectives, such as feature attributions
approaches (Lundberg and Lee, 2017; Ribeiro et 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 are feature attributions approaches,
in particular SHAP (Lundberg and Lee, 2017), which is 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 not guarantee the truthfulness of the important variables
involved in a 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 et 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
are not currently available in the general case (e.g., regression model,
continuous 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 a 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 a 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 we can extend Sufficient
Explanations from classification to regression. We 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 $\boldsymbol{X}$, contrary
to (Wang et al., 2020). Our method can explain the data generating process
$(\boldsymbol{X},Y)$ directly or any learnt model
$(\boldsymbol{X},f(\boldsymbol{X}))$.
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) or INVASE (Yoon et al., 2018) aims at finding the minimal subset of
variables that are relevant for a given instance $\boldsymbol{x}$ and its
label $y$. Interactions can be captured in that way. In addition, the
identification of a minimal subset $S=S(\boldsymbol{x})$ is well-formalized
and the objective is to find $S$ such that
$\mathcal{L}(Y|\boldsymbol{X}=\boldsymbol{x})\approx\mathcal{L}(Y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$.
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 a 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 as 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.e., no subset of the set satisfies
the sufficiency condition). However, since the guarantees are deterministic,
it is often necessary to include many features into the explanation, making
the explanation more complex and thus less intelligible. A 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. It 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 a selection problem as the whole set of explanations is not
interpretable.

In this work, we propose a consistent method that efficiently finds the
Sufficient Explanations of any data generating process $(\boldsymbol{X},Y)$ or
any model $(\boldsymbol{X},f(\boldsymbol{X}))$, without learning the
distribution of $\boldsymbol{X}$. In particular, we don’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 rule-based 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 we have an i.i.d sample
$\mathcal{D}_{n}={(\boldsymbol{X}^{i},Y^{i})_{i=1,\dots,n}}$ such that
$(\boldsymbol{X},Y)\sim P_{(\boldsymbol{X},Y)}$ where
$\boldsymbol{X}\in\mathbb{R}^{p}$ and $Y\in\mathbb{R}$. We use uppercase
letters for random variables and lowercase letters for their value
assignments. For a given subset $S\subset[p]$,
$\boldsymbol{X}_{S}=(X_{i})_{i\in S}$ denotes a subgroup of the features.

We define the explanations of an instance $\boldsymbol{x}$ as the minimal
subsets $\boldsymbol{x}_{S},S\subset[p]$ such that given only those features,
the model yields "almost" the same prediction $y$ as on the complete example
with high probability, under the data distribution $p(\boldsymbol{X})$. The
main probabilistic reasoning tool that we use for our 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, we propose the following
definition of the SDP:

######  Definition 3.1.

(Same Decision Probability of a regressor). Given an instance
$(\boldsymbol{x},y)$, the Same Decision Probability at level $t$ of the subset
$S\subset\left\llbracket 1,p\right\rrbracket$, w.r.t
$\boldsymbol{x}=\left(\boldsymbol{x}_{S},\boldsymbol{x}_{\bar{S}}\right)$ is

$\small SDP_{S}\left(y;\boldsymbol{x},t\right)=P\left((Y-y)^{2}\leq
t\left|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}\right.\right).$

In a regression setting, the SDP gives the probability to stay close to the
same prediction $y$ at level $t$, when we fix
$\boldsymbol{X}_{S}=\boldsymbol{x}_{S}$ or when $\boldsymbol{X}_{\bar{S}}$ are
missing. The higher is the probability, the better is the explanation powered
by $S$. Note that for classification, the SDP is defined as
$SDP_{S}\left(y;\boldsymbol{x}\right)=P\left(Y=y\left|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}\right.\right)$.
Although we present all the methods with the SDP for regression, they remain
the same for classification, we only need to replace
$SDP_{S}\left(y;\boldsymbol{x},t\right)$ by
$SDP_{S}\left(y;\boldsymbol{x}\right)$. Now, we focus on the minimal subset of
features such that the model makes the same or almost the same decision with a
given (high) probability $\pi$.

######  Definition 3.2.

(Minimal Sufficient Explanations). Given an instance $(\boldsymbol{x},y)$,
$S_{\pi}(\boldsymbol{x})$ is a Sufficient Explanation for probability $\pi$,
if $SDP_{S_{\pi}(\boldsymbol{x})}\left(y;\boldsymbol{x},t\right)\geq\pi$, and
no subset $Z$ of $S_{\pi}(\boldsymbol{x})$ satisfies
$SDP_{Z}\left(y;\boldsymbol{x},t\right)\geq\pi$. 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 of 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 $(\boldsymbol{x},y)$
and its A-SE or M-SE. The local explanatory importance of $\boldsymbol{x}_{i}$
is how frequent $\boldsymbol{x}_{i}$ 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 to reason about the relative
difference between the attribution of each feature. Indeed, we can easily
discriminate between the importance of variables in terms of probabilities
compared to arbitrary values of SHAP or 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. In essence,
explaining a decision means giving the reasons that highlight why the decision
has been made. Therefore, we propose to extend the Sufficient Explanations
into local rules. A rule is a simple IF-THEN statement, e.g., IF the
conditions on the features are met, THEN make a specific prediction. Recall
that given an instance $\boldsymbol{x}$, a Sufficient Explanation is the
minimal subset $S\subset[p]$, such that fixing the values
$\boldsymbol{X}_{S}=\boldsymbol{x}_{S}$ permits to maintain the prediction
with high probability. The idea is to find the largest rectangle
$L_{S}(\boldsymbol{x})=\prod_{i=1}^{|S|}[a_{i},b_{i}],a_{i},b_{i}\in\mathbb{R}$
given the indexes of the Sufficient Explanation $S$ such that
$\boldsymbol{x}_{S}\in L_{S}(\boldsymbol{x})$ and $\forall\boldsymbol{z}\text{
with }\boldsymbol{z}_{S}\in L_{S}(\boldsymbol{x})$,
$SDP_{S}(y;\boldsymbol{z};t)\geq\pi$.

######  Definition 3.4.

(Minimal Sufficient Rule). Given an instance $(\boldsymbol{x},y)$, $S$ a
Minimal Sufficient Explanation, the rectangle
$L_{S}(\boldsymbol{x})=\prod_{i=1}^{|S|}[a_{i},b_{i}],a_{i},b_{i}\in\mathbb{R}$
is a Minimal Sufficient Rule if
$L_{S}(\boldsymbol{x})=\operatorname*{argmax}_{L(\boldsymbol{x})}\;Vol(L(\boldsymbol{x}))$,
$\boldsymbol{x}_{S}\in L_{S}(\boldsymbol{x})$ and
$\forall\boldsymbol{z},\boldsymbol{z}_{S}\in L_{S}(\boldsymbol{x})$,
$SDP_{S}\left(y;\boldsymbol{z},t\right)\geq\pi$.

Intuitively, the Sufficient Rule is a generalization of the Sufficient
Explanation, i.e., instead of satisfying the minimality/sufficiency conditions
of definition 3.2 if we fixed the values
$\boldsymbol{X}_{S}=\boldsymbol{x}_{S}$, we want to satisfy these conditions
on all the elements of a rectangle $L_{S}(\boldsymbol{x})$ that contains
$\boldsymbol{x}_{S}$. We also want this rectangle to be of maximal volume such
that it covers a large part of the input space. Thus, the Sufficient Rule
captures the local behavior of the model around $\boldsymbol{x}$ while
ensuring the minimality of the rule and guarantees on the outcome. Note that
the volume of the rectangle $L$ can be defined as
$Vol(L(\boldsymbol{x}))=P(\boldsymbol{X}\in L(\boldsymbol{x}))$ or
$\lambda(L(\boldsymbol{x}))$, with $\lambda$ 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 a model $f$ and an instance $\boldsymbol{x}$,
Anchors search the largest rule (or rectangle) $L_{S}(\boldsymbol{x})$ such
that $P_{Q}(f(\boldsymbol{x})=Y|\;\boldsymbol{X}_{S}\in
L_{S}(\boldsymbol{x}))\geq\pi$ 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.e
$\forall\boldsymbol{x}_{S}\in
L_{S}(\boldsymbol{x}),P(f(\boldsymbol{x})=Y|\;\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\geq\pi$.
The second major difference is that the Sufficient Rule is based on the
original distribution $P_{(\boldsymbol{X},Y)}$ as we use conditional
distribution $P(Y|\boldsymbol{X}_{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 a 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 $S_{\pi}(\boldsymbol{x})$ and the
corresponding Sufficient Rules $L_{S_{\pi}}(\boldsymbol{x})$, 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 NP-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 $\boldsymbol{X}$ and
compute a lower bound of the SDP.

In this section, we propose a consistent estimator of the SDP for any
distribution $(\boldsymbol{X},Y)$. It is based on two ideas: Projected Forest
(Bénard et al., 2021a, c) and Quantile Regression Forest (Meinshausen and
Ridgeway, 2006). The Projected Forest is an adaptation of the Random Forest
algorithm that estimates $E[Y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}]$ instead
of $E[Y|\boldsymbol{X}=\boldsymbol{x}]$, and the Quantile Regression Forest
uses the Random Forest algorithm to estimate the Conditional Distribution
Function (CDF) $P(Y\leq y|\boldsymbol{X}=\boldsymbol{x})$. The first step is
to write the SDP as

$\displaystyle\small SDP_{S}(y;\boldsymbol{x},t)$
$\displaystyle=P((Y-y)^{2}\leq
t|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=F_{S}(y+\sqrt{t}\;|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-F_{S}(y-\sqrt{t}\;|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}).$

Equation 4 shows that the only challenge is to estimate the Projected (or
Conditional) CDF $F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=P(Y\leq
y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$. The variant of the original Random
Forest proposed by Meinshausen and Ridgeway (2006) that estimates the CDF
$F(y|\boldsymbol{X}=\boldsymbol{x})=P(Y\leq y|\boldsymbol{X}=\boldsymbol{x})$
is not of interest to us because we want to estimate the Projected CDF
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ for any $S$. The recent works
by Bénard et al. (2021a, c) are much more relevant as they permit to estimate
$E[Y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}]$ from a classical Random Forest
that has learned to predict $E[Y|\boldsymbol{X}=\boldsymbol{x}]$. The idea is
to extract a 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
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$. In addition, we prove the
consistency of our estimator of the Projected CDF.

###  4.1 Random Forest and Condition Distribution Function (CDF) Forest

A Random Forest (RF) is grown as an ensemble of $k$ 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, $a_{n}$ 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 is stopped when the total
number of cells in the tree reaches the value $t_{n}$. For each new instance
$\boldsymbol{x}$, the prediction of the $l$-th tree is:

$\displaystyle\small
m_{n}(\boldsymbol{x},\Theta_{l},\mathcal{D}_{n})\small=\sum_{i=1}^{n}\frac{B_{n}(\boldsymbol{X}^{i};\Theta_{l})\;\mathds{1}_{X^{i}\in
A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}}{N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}Y^{i}$
(4.1)

where:

  * •

$\Theta_{l},l=1,\dots,k$ are independent random vectors, distributed as a
generic random vector $\Theta=(\Theta^{1},\Theta^{2})$ and independent of
$\mathcal{D}_{n}$. $\Theta^{1}$ contains indexes of observations that are used
to build the tree, i.e. the bootstrap sample and $\Theta^{2}$ indexes of
splitting candidate variables in each node. $\Theta_{1:k}$ denotes the
sequence of $\Theta_{l}$’s.

  * •

$A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$ is the tree cell (leaf)
containing $\boldsymbol{x}$

  * •

$N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$ is the number of bootstrap
elements that fall into $A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$

  * •

$B_{n}(\boldsymbol{X}^{i};\Theta_{l})$ 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 to gives the prediction of the forest as:

$\displaystyle\small
m_{k,n}(\boldsymbol{x},\Theta_{1:k},\mathcal{D}_{n})=\frac{1}{k}\sum_{l=1}^{k}m_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$
(4.2)

The Random Forest estimator (Eq. 4.2) can also be seen as an adaptive
neighborhood procedure (Lin and Jeon, 2006). For every instance
$\boldsymbol{x}$, the observations in $\mathcal{D}_{n}$ are weighted by
$w_{n,i}(\boldsymbol{x};\Theta_{1:k},\mathcal{D}_{n})$, $i=1,\dots,n$.
Therefore, the prediction of Random Forests and the weights can be rewritten
as

$\small
m_{k,n}(\boldsymbol{x},\Theta_{1:k},\mathcal{D}_{n})=\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x};\Theta_{1:k},\mathcal{D}_{n})Y^{i},\quad
w_{n,i}(\boldsymbol{x};\Theta_{1:k},\mathcal{D}_{n})=\sum_{l=1}^{k}\frac{B_{n}(X^{i};\Theta_{l})\;\mathds{1}_{X^{i}\in
A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}}{k\times
N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}$

Viewing a 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 et al., 2021)). Therefore, just as
$E[Y|\boldsymbol{X}=\boldsymbol{x}]$ is approximated by a weighted mean over
observation of $Y^{i}$, $E[\mathds{1}_{Y\leq
y}|\boldsymbol{X}=\boldsymbol{x}]$ is approximated by the weighted mean over
the observations of $\mathds{1}_{Y^{i}\leq y}$ using the same weights
$w_{n,i}(\boldsymbol{x};\Theta_{1:k},\mathcal{D}_{n})$. The approximation is

$\small\widehat{F}(y|\boldsymbol{X}=\boldsymbol{x},\Theta_{1:k},\mathcal{D}_{n})=\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x};\Theta_{1:k},\mathcal{D}_{n})\mathds{1}_{Y^{i}\leq
y}$ (4.3)

To simplify notations, we omit $\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n}$
and we write $\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ 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 et al. (2021c, a). The idea is to
project the partition of each tree of the forest on the subspace spanned by
the variables in $S$, thus we can estimate $E[Y|\boldsymbol{X}_{S}]$ rather
than $E[Y|\boldsymbol{X}]$. The computation of these partitions for each $S$
can be computationally expensive in high dimension. However, Bénard et al.
(2021a) uses a simple algorithm trick to derive efficiently the output of the
Projected Forest without computing explicitly its partitions. Roughly, for
computing the prediction of a tree, the algorithm ignores the splits that use
variables not contained in $S$. It works as follow: when an observation is
dropped down in the initial trees, and it encounters a split involving a
variable $i\notin S$ , the observation is sent both to the left and right
children nodes. As a result, each observation falls in multiple terminal
leaves of the tree. Thus, to compute the prediction of an instance
$\boldsymbol{x}_{S}$, we collect the set of terminal leaves where it falls,
and average the output $Y^{i}$ of the training observations which belong to
every terminal leaf of this collection.
$E[Y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}]$ is estimated as the average
outputs of the training observations in the intersection of the leaves where
$\boldsymbol{x}_{S}$ falls.

An efficient implementation of the PRF algorithm is detailed in Appendix. The
associated PRF is $\small
m_{k,n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S})=\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})Y^{i}$
where the weights are defined by

$\small
w_{n,i}(\boldsymbol{x}_{S})=\small\sum_{l=1}^{k}\frac{B_{n}(X^{i};\Theta_{l})\;\mathds{1}_{X^{i}\in
A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})}}{k\times
N_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})},$
(4.4)

where
$A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$
is the leaf of the associated Projected $l$-th tree where $\boldsymbol{x}_{S}$
falls and
$N_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$ is
the number of bootstrap observations that falls in
$A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$.
Therefore, we approximate the Projected CDF
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=P(Y\leq
y|\boldsymbol{X}_{S}=\boldsymbol{x}_{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:
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{Y^{i}\leq
y}$.

###  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
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ to
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$. Meinshausen and Ridgeway
(2006) showed the uniform convergence in probability of a simplified version
of the estimator of the CDF defined in Eq. 4.3, where the weights
$w_{n,i}(\boldsymbol{x}_{S};\Theta_{1:k},\mathcal{D}_{n})$ are in fact
considered to be non-random while they are indeed random variables depending
on $(\Theta_{l})_{l=1,\dots,k}$, $\mathcal{D}_{n}$. 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, 2020). However, Elie-Dit-Cosaque and Maume-
Deschamps (2020) showed the almost everywhere uniform convergence of both
estimators (the simplified and the one defined in 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
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ based on the
following assumptions.

######  Assumption 4.1.

$\forall x\in\mathbb{R}^{d}$, the conditional cumulative distribution function
$F(y|X=x)$ is continuous.

Assumption 4.1 is necessary to get uniform convergence of the estimator.

######  Assumption 4.2.

For $l\in[k]$, we assume that the variation of the conditional cumulative
distribution function within any cell goes to $0$.

$\forall x\in\mathbb{R}^{d},\forall y\in\mathbb{R},\sup_{\boldsymbol{z}\in
A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}|F(y|\boldsymbol{\boldsymbol{z}})-F(y|\boldsymbol{x})|\overset{a.s}{\to}0$

Assumption 4.2 allows to control the approximation error of the estimator. If
for all $y$, $F(y|.)$ 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 in 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 a fraction
$\gamma$ observations in children nodes, and the number of splitting candidate
variables is set to 1 at each node with a small probability. Under these small
modifications, Lemma 2 from Meinshausen and Ridgeway (2006) gives that the
diameter of each cell vanishes.

######  Assumption 4.3.

Let $k$ and $N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$ (number of
bootstrap observations in a leaf node), then there exists
$k=\mathcal{O}(n^{\alpha})$, with $\alpha>0$, and
$\forall\boldsymbol{x}\in\mathbb{R}^{d}$,
$N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})=\Omega(\sqrt{n}(ln(n))^{\beta})$222$f(n)=\Omega(g(n))\iff\exists
k>0,\exists n_{0}>0|\;\forall n\geq n_{0}|f(n)|\geq|g(n)|$ , with $\beta>1$
a.s.

Assumption 4.3 allows us to control the estimation error and means that the
cells should contain a sufficiently large number of points so that averaging
among the observations is effective.

To prove the consistency of the PRF CDF
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$, we only need to
verify the assumptions 4.1, 4.2, 4.3 on the parameters of the PRF CDF and the
Projected CDF $F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=P(Y\leq
y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$.

Assumptions 4.1 and 4.2 are satisfied for the Projected CDF and the PRF CDF’s
leaves. Since by definition
$A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})\subset
A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$, if the variations within
the cells of the RF vanish (diameter goes to zero), it also vanishes in the
Projected forest. In addition, if the CDF
$F(y|\boldsymbol{X}=\boldsymbol{x})=F(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\boldsymbol{X}_{\bar{S}}=\boldsymbol{x}_{\bar{S}})$
is continuous, we can show by a straightforward analysis of parameter-
dependent integral that the Projected CDF
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=\int
F(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\boldsymbol{X}_{\bar{S}}=\boldsymbol{x}_{\bar{S}})p(\boldsymbol{x}_{\bar{S}}|\boldsymbol{x}_{S})d\boldsymbol{x}_{\bar{S}}$
is also continuous. As we control the minimal number of observations in the
leaf of the PRF CDF by construction, Assumption 4.3 is also verified. Then,
the PRF CDF satisfies also Assumption 4.1-4.3 which ensures its consistency
thanks to Theorem 4.4.

######  Theorem 4.4.

Consider a RF satisfying Assumptions 4.1 to 4.3. Then,

$\displaystyle\small\forall\boldsymbol{x}\in\mathbb{R}^{d},\sup_{y\in\mathbb{R}}|\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|\overset{a.s}{\to}0$

The complete proof and simulations showing the convergence of the estimator
can 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
$SDP_{S}\left(y;\boldsymbol{x},t\right)$:

$\displaystyle\small\widehat{SDP}_{S}$
$\displaystyle\small=\widehat{F}_{S}(y+\sqrt{t}\;|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-\widehat{F}_{S}(y-\sqrt{t}\;|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$

However, finding the 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 $s=10$
variables frequently selected in the RF used to estimate the SDP, reducing the
complexity from $2^{p}$ to $2^{10}$. This preselection procedure is already
used in Bénard et al. (2021b, a), and it is mainly based on Proposition 1 of
Scornet et al. (2015), which highlights the fact that RF naturally splits the
most on influential variables. Note that the minimum number of selected
variables $s$ is a hyperparameter.

To find the Sufficient Rules, we used the SDP’s estimator $\widehat{SDP}_{S}$.
By using the fact that the PRF CDF is a tree-based model, and thus
$\widehat{SDP}_{S}$ 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
$\boldsymbol{x}$, we already a have a rectangle $L_{S}(\boldsymbol{x})$
defined by the PRF CDF or $\widehat{SDP}_{S}$ that is the largest rectangle
such that $\boldsymbol{x}_{S}\in L_{S}(\boldsymbol{x})$ and
$\forall\boldsymbol{z}\text{ with }\boldsymbol{z}_{S}\in
L_{S}(\boldsymbol{x}),\widehat{SDP}_{S}(y;\boldsymbol{z},t)=\widehat{SDP}_{S}(y;\boldsymbol{x},t)\geq\pi$.
By definition, it is the intersection of the cell of the trees where
$\boldsymbol{x}_{S}$ falls, namely
$\cap_{l=1}^{k}A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$.
Thus, starting from
$\cap_{l=1}^{k}A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$,
which is also a 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 hyperparameters.

The main hyperparameters are: $s$ the number of preselected variables, $\pi$
the minimal probability of changing the decision and $t$ 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\ll 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 on influential
variables. However, any RF’s importance measure s.t. Mean Decrease Accuracy
(Breiman, 2001) or Impurity (Breiman and Cutler, 2003) can be used as the RF
algorithm is 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. In practice, we have
always found coalitions $S$ with a probability above $\pi=0.9$ with $s=10$ for
real world datasets. Otherwise, we suggest a trade-off between the maximal
reachable size $s$ and the highest probability.

We propose choosing $\pi=0.9$ as it 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 $t$; we recommend having an
adaptive radius $t(x)$ using the quantile of the conditional distributions
$Y|\boldsymbol{X}=\boldsymbol{x}$, which is a by-product of the Quantile
Regression Forest used for computing the SDP. For each observation, we choose
the radius
$t(\boldsymbol{x})=[\hat{q}_{\alpha_{1}}(\boldsymbol{x}),\hat{q}_{1-\alpha_{2}}(\boldsymbol{x})]$
with $\alpha_{1}+\alpha_{2}=\alpha$. We build then a confidence interval of
varying length but with constant confidence level across the dataset. This
makes our approach as a 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
$\boldsymbol{X}_{S}=\boldsymbol{x}_{S}$ is fixed, then there is a probability
at least $\pi$ of not changing the prediction significantly with level
$1-\alpha$, or so that
$Y\in[\hat{q}_{\alpha_{1}}(\boldsymbol{x}),\hat{q}_{1-\alpha_{2}}(\boldsymbol{x})]$
with probability $\pi$. For this reason, we suggest fixing
$\alpha_{1}+\alpha_{2}=\alpha$ and $\pi$ at standard level $1-\alpha=\pi=0.9$
agreeing with acceptable level of risks.

##  5 Experiments

We conduct three experiments in this section. The first compares the
Sufficient Explanations, Sufficient Rules and LXI with state-of-art (SOTA)
local explanations methods (SHAP, LIME, INVASE) in a 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
$\boldsymbol{X}\in\mathbb{R}^{p}$, $\boldsymbol{X}\in\mathcal{N}(0,\Sigma)$,
$\Sigma=0.8J_{p}+5I_{p}$ with $p=100$, $I_{p}$ is the identity matrix, $J_{p}$
is all-ones matrix and a linear predictor with switch defined as:

$\displaystyle\small Y=(X_{1}+X_{2})\mathds{1}_{X_{5}\leq
0}+(X_{3}+X_{4})\mathds{1}_{X_{5}>0}.$ (5.1)

The variables $X_{i}$ for $i=6\dots 100$ are noise variables. We fit a RF with
a sample size $n=10^{4}$, $k=20$ trees and the minimal number of samples by
leaf node is set to $t_{n}=\lfloor\sqrt{n}\times\ln(n)^{1.5}/250\rfloor$ for
the original and the Projected Forest. The $R^{2}=99\%$ on the test set of
size $10^{4}$. The RF is used to compute the explanations of SHAP, LIME. The
Projected Forest is also extract from the RF for the SDP approaches. We choose
$\alpha_{1}=0.05,\alpha_{2}=0.95$ and $\pi=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^{2}=99\%$.

#### SDP approaches vs SOTA (SHAP, LIME, INVASE) on regression.

Here, we analyze the capacity of each method to discover the local important
variables of the model defined in Eq. 5.1. Indeed, Eq. 5.1 shows that if
$x_{5}\leq 0$, the model uses only the variables $x_{1},x_{2}$ otherwise it
uses the variables $x_{3},x_{4}$. Thus, we try to find the top $K=3$ relevant
features for each sample. Note that $K$ is not a 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 $\boldsymbol{x}_{S}$ that is relevant to the
corresponding target $y$, we also compute a predictive performance metrics
that shows how well the projected predictor
$E[Y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S}]$ selected by each method is close
to the predictor on the full set of features
$E[Y|\boldsymbol{X}=\boldsymbol{x}]$, under the data distribution. Formally,
for a given subset $S$, we denote it as
$\small\text{P-MSE}=E_{Z}\left[\Big{(}E[Y|\boldsymbol{X}=\boldsymbol{Z}]-E[Y|\boldsymbol{X}_{S}=\boldsymbol{Z}_{S}]\Big{)}^{2}\right]$
where $\boldsymbol{Z}\sim P_{\boldsymbol{X}}$.

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 Explanations is also almost zero, and as
above, SHAP and LIME perform worse than the other methods. In table 1, we
compare the LXI and SHAP values on 1000 observations having $X_{5}>0$. 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 is the variables $X_{3},X_{4},X_{5}$. Both models
give null attributions to the noise variables, but SHAP gives higher
importance to the variables $X_{1},X_{2}$ than the truly important variables
$X_{3},X_{4},X_{5}$. On the other hand, LXI gives non null attributions only
on 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 $X_{5}>0$. $X_{noises}$ corresponds to the sum of the attributions of the noises variables ($X_{i}$ for $i=6\dots 100$). | $X_{1}$ | $X_{2}$ | $X_{3}$ | $X_{4}$ | $X_{5}$ | $X_{noises}$
---|---|---|---|---|---|---
LXI | 0 | 0 | 1 | 1 | 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 $x_{5}$ that matters. Thus, by extending the Sufficient Explanation
into Sufficient Rule we can retrieve the complete story. We choose an
observation $(\boldsymbol{x},y)$ such that its Sufficient Explanation found is
$S=[X_{3},X_{4},X_{5}]$, with $\boldsymbol{x}_{S}=[-3.64,-4.41,0.68]$.
Although the Sufficient Explanation shows that fixing the value
$\boldsymbol{x}_{S}$ 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 $\small
L_{S}(\boldsymbol{x})=\\{X_{5}>0\;\text{AND}\;-4.45\leq
X_{4}\leq-4.06\;\text{AND}\;-3.67\leq X_{3}\leq-3.58\\}$. The Sufficient Rule
$L_{S}(\boldsymbol{x})$ catches perfectly the local behaviour of the model
which says that despite the values of $x_{3},x_{4}$, it’s the sign of $x_{5}$
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, we use the predictive performance and simplicity
(number of variables used) 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 we
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.

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^{2}=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^{2}=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: $R_{1}=\\{\texttt{If Workingday = True and Hours $\in$ [5.5,
6.5] THEN Bike rental demand = 20}\\}$, $R_{2}=\\{$If Hours $\in$ [8.5, 9] and
Year $\leq$ 2011 and month $\geq$ 5 THEN Bike rental demand = 192$\\}$. The
number of observations that satisfy these rules is $134$, $133$ for the rules
$R_{1}$, $R_{2}$ respectively with a mean absolute error
${MAE}_{R_{1}}=12,{MAE}_{R_{2}}=30$.

#### 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,p=14)$(Larson et al., 2016), Nhanesi $(n=8593,p=17)$ (CDC,
1999-2022), and Employee Attrition $(n=1470,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-
based 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 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, 7) | 0.30 | 0.97 | (1.3, 0.65, 7) | 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 at the cost of
optimality. In fact, we can observe in table 2 that Anchors tends to give much
longer 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 $\\{\textbf{size}:count\\}$:
$\\{\textbf{1}:704,\;\textbf{2}:127,\;\textbf{3}:71,\;\textbf{4}:21,\;\textbf{5}:13,\;\textbf{6}:10,\;\textbf{7}:10,\;\textbf{8}:9,\;\textbf{9}:9,\;\textbf{10}:4,\;\textbf{11}:2,\;\textbf{12}:4,\;\textbf{13}:5,\;\textbf{14}:1,\;\textbf{16}:1\\}$,
and the corresponding distribution for the SR is
$\\{\textbf{1}:775,\;\textbf{2}:145,\;\textbf{3}:52,\;\textbf{4}:9,\;\textbf{5}:12,\;\textbf{7}:4\\}$.
Note that this is a significant drawback of Anchors, as simplicity of the
explanations is an essential desideratum for explanation methods. We give an
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.t input perturbations. For each observation
$\boldsymbol{x}$, we compare its rule with the rules of 50 noisy versions of
$\boldsymbol{x}$ obtained by adding random Gaussian noises
$\mathcal{N}(0,\epsilon\times I)$ to the values of the features with
$\epsilon=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 $\epsilon=0$, 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 $\epsilon$ can be found in Appendix.

These experiments demonstrate that the SR gives more optimal rules than the
one returned by Anchors. We also conduct an additional experiment in the
Appendix confirming this claim in a setting where we know the ground truth.

##  6 Conclusion

In this work, we introduce a fast and consistent estimator of the Same
Decision Probability and propose a 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-the-art
algorithms while ensuring minimality, sufficiency, and stability. Our
generalization of SDP and Minimal Sufficient Rules are tightly related. They
are linked by a Random Forest, which is a computationally and statistically
efficient estimator of the SDP and gives the partition that is translated into
an 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.

#### Acknowledgments.

This work has been done in collaboration between Stellantis and Laboratoire de
Mathématiques et Modélisation d’Évry (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 Technologie (ANRT).

## References

  * Amoukou et al. (2021) Salim I 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.
  * Amoukou et al. (2022) 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://proceedings.mlr.press/v151/amoukou22a.html.
  * Arenal-Gutiérrez et al. (1996) Eusebio Arenal-Gutiérrez, Carlos Matrán, and Juan Antonio Cuesta-Albertos.  Unconditional glivenko-cantelli-type theorems and weak laws of large numbers for bootstrap.  _Statistics & Probability Letters_, 26:365–375, 1996\.
  * Bénard et al. (2021a) 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:2105.11724_ , 2021a.
  * Bénard et al. (2021b) Clément Bénard, Gérard Biau, Sébastien Veiga, and Erwan Scornet.  Interpretable random forests via rule extraction.  In _International Conference on Artificial Intelligence and Statistics_ , pages 937–945. PMLR, 2021b.
  * Bénard et al. (2021c) Clément Bénard, Sébastien Da Veiga, and Erwan Scornet.  Mda for random forests: inconsistency, and a practical solution via the sobol-mda.  _arXiv preprint arXiv:2102.13347_ , 2021c.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine learning_ , 45(1):5–32, 2001.
  * Breiman and Cutler (2003) Leo Breiman and A Cutler.  Setting up, using, and understanding random forests v4. 0.  _University of California, Department of Statistics_ , 2003.
  * Breiman et al. (1984) Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone.  Classification and regression trees. wadsworth int.  _Group_ , 37(15):237–251, 1984.
  * CDC (1999-2022) CDC.  National health and nutrition examination survey, 1999-2022.  URL https://wwwn.cdc.gov/Nchs/Nhanes/Default.aspx.
  * Chen et al. (2018) Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan.  Learning to explain: An information-theoretic 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/chen18j.html.
  * Chen et al. (2012) Suming Chen, Arthur Choi, and Adnan Darwiche.  The same-decision probability: A new tool for decision making.  In _Proceedings of the Sixth European Workshop on Probabilistic Graphical Models_ , pages 51–58. Citeseer, 2012.
  * Chen et al. (2013) Suming Chen, Arthur Choi, and Adnan Darwiche.  An exact algorithm for computing the same-decision probability.  In _Twenty-Third International Joint Conference on Artificial Intelligence_ , IJCAI ’13, page 2525–2531. AAAI Press, 2013.  ISBN 9781577356332.
  * Choi et al. (2020) YooJung Choi, Antonio Vergari, and Guy Van den Broeck.  Probabilistic circuits: A unifying framework for tractable probabilistic models.  Technical report, Technical report, 2020.
  * Darwiche and Hirth (2020) Adnan Darwiche and Auguste Hirth.  On the reasons behind decisions.  _arXiv preprint arXiv:2002.09284_ , 2020.
  * Dhurandhar et al. (2018) 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.
  * Du et al. (2021) Qiming Du, Gérard Biau, François Petit, and Raphaël Porcher.  Wasserstein random forests and applications in heterogeneous treatment effects.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1729–1737. PMLR, 2021.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Elie-Dit-Cosaque and Maume-Deschamps (2020) Kevin Elie-Dit-Cosaque and Véronique Maume-Deschamps.  Random forest estimation of conditional distribution functions and conditional quantiles.  _arXiv preprint arXiv:2006.06998_ , 2020.
  * Ghalebikesabi et al. (2021) Sahra Ghalebikesabi, Lucile Ter-Minassian, Karla Diaz-Ordaz, and Chris Holmes.  On locality of local explanation models.  _arXiv preprint arXiv:2106.14648_ , 2021.
  * Goehry (2020) Benjamin Goehry.  Random forests for time-dependent processes.  _ESAIM: Probability and Statistics_ , 24:801–826, 2020\.
  * Gosiewska and Biecek (2019) Alicja Gosiewska and P. Biecek.  Do not trust additive explanations.  _arXiv: Learning_ , 2019.
  * Györfi et al. (2002) László Györfi, Michael Kohler, Adam Krzyżak, and Harro Walk.  _A distribution-free theory of nonparametric regression_ , volume 1.  Springer, 2002.
  * Ignatiev et al. (2019) Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva.  On validating, repairing and refining heuristic ml explanations.  _arXiv preprint arXiv:1907.02509_ , 2019.
  * Ishwaran et al. (2008) 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.
  * Jethani et al. (2021) Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs, and Rajesh Ranganath.  Have we learned to explain?: How interpretability methods can learn to encode predictions in their interpretations.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1459–1467. PMLR, 2021.
  * Kaggle (2015) Kaggle.  Bike sharing demand, 2015.  URL https://www.kaggle.com/c/bike-sharing-demand.
  * Kaggle (2016) Kaggle.  Pima indians diabetes database, 2016.  URL https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database.
  * Kaggle (2017) Kaggle.  Ibm hr analytics employee attrition performance, 2017.  URL www.kaggle.com/pavansubhasht/%****␣neurips_2022.bbl␣Line␣200␣****ibm-hr-analytics-attrition-dataset.
  * Klusowski (2020) Jason Klusowski.  Sparse learning with cart.  _Advances in Neural Information Processing Systems_ , 33:11612–11622, 2020.
  * Larson et al. (2016) Jeff Larson, Surya Mattu, Lauren Kirchner, , and Julia Angwin.  How we analyzed the compas recidivism algorithm, 2016.  URL https://www.propublica.org/article/how-we-analyzed-the-compas-recidivism-algorithm.
  * Lin and Jeon (2006) Yi Lin and Yongho Jeon.  Random forests and adaptive nearest neighbors.  _Journal of the American Statistical Association_ , 101(474):578–590, 2006.
  * Lundberg and Lee (2017) Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  _Advances in neural information processing systems_ , 30, 2017.
  * Lundberg et al. (2020) Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M 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\.
  * Meinshausen and Ridgeway (2006) Nicolai Meinshausen and Greg Ridgeway.  Quantile regression forests.  _Journal of Machine Learning Research_ , 7(6), 2006.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Ribeiro et al. (2016) 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.
  * Ribeiro et al. (2018) 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.
  * Scornet et al. (2015) Erwan Scornet, Gérard Biau, and Jean-Philippe Vert.  Consistency of random forests.  _The Annals of Statistics_ , 43(4):1716–1741, 2015.
  * Shih et al. (2018) Andy Shih, Arthur Choi, and Adnan Darwiche.  A symbolic approach to explaining bayesian network classifiers.  _arXiv preprint arXiv:1805.03364_ , 2018.
  * Singh et al. (2021) Chandan Singh, Keyan Nasseri, Yan Shuo Tan, Tiffany Tang, and Bin Yu.  imodels: a python package for fitting interpretable models.  _Journal of Open Source Software_ , 6(61):3192, 2021.
  * Slack et al. (2020) 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 on AI, Ethics, and Society_ , pages 180–186, 2020.
  * Stone (1985) Charles J. Stone.  Additive Regression and Other Nonparametric Models.  _The Annals of Statistics_ , 13(2):689 – 705, 1985.  doi: 10.1214/aos/1176349548.  URL https://doi.org/10.1214/aos/1176349548.
  * Vapnik and Chervonenkis (2015) Vladimir N Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  In _Measures of complexity_ , pages 11–30. Springer, 2015.
  * Wachter et al. (2017) 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.
  * Wager and Athey (2017) Stefan Wager and Susan Athey.  Estimation and inference of heterogeneous treatment effects using random forests, 2017.
  * Wang et al. (2020) Eric Wang, Pasha Khosravi, and Guy Van den Broeck.  Towards probabilistic sufficient explanations.  In _Extending Explainable AI Beyond Deep Models and Classifiers Workshop at ICML (XXAI)_ , 2020.
  * Yoon et al. (2018) Jinsung Yoon, James Jordon, and Mihaela van der Schaar.  Invase: Instance-wise variable selection using neural networks.  In _International Conference on Learning Representations_ , 2018.

Appendix

###### Contents

  1. 1 Introduction
  2. 2 Motivations and Related works
  3. 3 Probabilistic Sufficient Explanations for Regression
  4. 4 SDP, Sufficient Explanations and Sufficient Rules via Random Forest
    1. 4.1 Random Forest and Condition Distribution Function (CDF) Forest
    2. 4.2 Projected Forest and Projected CDF Forest
    3. 4.3 Consistency of the Projected CDF Forest
    4. 4.4 Estimation of SDP, Sufficient Explanations and Sufficient Rules
  5. 5 Experiments
  6. 6 Conclusion
  7. A Proofs
    1. A.1 Main assumptions
    2. A.2 Proof of theorem 4.4
  8. B Empirical evaluations of the estimator $\widehat{F}_{S}$
  9. C Additional experiments
    1. C.1 Local rules of Anchors and Sufficient Rules with ground truth explanations
    2. C.2 Shapley values and Local eXplanatory importance (LXI) on LUCAS dataset
    3. C.3 Stability of Anchors and Sufficient Rules
  10. D From Sufficient Rules to Global Interpretable model
  11. E Projected Forest CDF algorithm

##  Appendix A Proofs

In this section, we prove our main result, Theorem 4.4, which is the uniform
a.s. consistency of the PRF CDF
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ to the projected
CDF $F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$.

###  A.1 Main assumptions

######  Assumption A.1.

$\forall x\in\mathbb{R}^{d}$, the conditional cumulative distribution function
$F(y|X=x)$ is continuous.

Assumption A.1 is necessary to get uniform convergence of the estimator.

######  Assumption A.2.

For $l\in[k]$, we assume that the variation of the conditional cumulative
distribution function within any cell goes to $0$.

$\forall x\in\mathbb{R}^{d},\forall y\in\mathbb{R},\sup_{\boldsymbol{z}\in
A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}|F(y|\boldsymbol{\boldsymbol{z}})-F(y|\boldsymbol{x})|\overset{a.s}{\to}0$

Assumption A.2 allows to control the approximation error of the estimator. If
for all $y$, $F(y|.)$ is continuous, Assumption A.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 in 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 a fraction
$\gamma$ observations in children nodes, and the number of splitting candidate
variables is set to 1 at each node with a small probability. Under these small
modifications, Lemma 2 from Meinshausen and Ridgeway [2006] gives that the
diameter of each cell vanishes.

######  Assumption A.3.

Let $k$ and $N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$ (number of
boostrap observations in a leaf node), then there exists
$k=\mathcal{O}(n^{\alpha})$, with $\alpha>0$, and
$\forall\boldsymbol{x}\in\mathbb{R}^{d}$,
$N_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})=\Omega(\sqrt{n}(ln(n))^{\beta})$333$f(n)=\Omega(g(n))\iff\exists
k>0,\exists n_{0}>0|\;\forall n\geq n_{0}|f(n)|\geq|g(n)|$ , with $\beta>1$
a.s.

Assumption A.3 allows us to control the estimation error and means that the
cells should contain a sufficiently large number of points so that averaging
among the observations is effective.

To prove the consistency of the PRF CDF
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$, we only need to
verify the assumptions A.1, A.2, A.3 on the parameters of the PRF CDF and the
Projected CDF $F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=P(Y\leq
y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$.

Assumptions A.1 and A.2 are satisfied for the Projected CDF and the PRF CDF’s
leaves. Since by definition
$A_{n}^{(\boldsymbol{x}_{S})}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})\subset
A_{n}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})$, if the variations within
the cells of the RF vanish, it also vanishes in the projected forest. In
addition, if the CDF
$F(y|\boldsymbol{X}=\boldsymbol{x})=F(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\boldsymbol{X}_{\bar{S}}=\boldsymbol{x}_{\bar{S}})$
is continuous, we can show by a straightforward analysis of parameter-
dependent integral that the Projected CDF
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})=\int
F(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\boldsymbol{X}_{\bar{S}}=\boldsymbol{x}_{\bar{S}})p(\boldsymbol{x}_{\bar{S}}|\boldsymbol{x}_{S})d\boldsymbol{x}_{\bar{S}}$
is also continuous. Since we control the minimal number of observations in the
leaf of the Projected Forest by construction, Assumption A.3 is also verified.
Then, the PRF CDF satisfies also Assumption A.1-A.3 which ensures its
consistency thanks to Theorem 4.4.

###  A.2 Proof of theorem 4.4

######  Theorem A.4.

Consider a random forest which satisfies Assumtions A.1 to A.3. Then,

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\quad\sup_{y\in\mathbb{R}}|\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|\overset{a.s}{\to}0$
(A.1)

The main idea is to use a second independent sample
$\mathcal{D}_{n}^{\diamond}$. Let assume we have a honest forest [Wager and
Athey, 2017] of the Projected CDF Forest
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n})$,
which is a random forest that grows using $\mathcal{D}_{n}$ but use another
sample $\mathcal{D}_{n}^{\diamond}$ (independent of $\mathcal{D}_{n}$ and
$\Theta$) to estimate the weights and the prediction. The projected CDF honest
Forest is defined as:

$F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})=\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S};\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})\mathds{1}_{Y^{\diamond
i}\leq y}$

where

$w_{n,i}^{\diamond}(\boldsymbol{x}_{S};\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})=\frac{1}{k}\sum_{l=1}^{k}\frac{\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})}}{N_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})},$

and
$N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))=N_{n}^{(S)}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})$
is the number of observation of
$\mathcal{D}_{n}^{\diamond}=\\{(X_{1}^{\diamond},Y_{1}^{\diamond})\dots,(X_{n}^{\diamond},Y_{n}^{\diamond})\\}$
that fall in $A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$. To
ease the notations, we do not write
$\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond}$ if
not necessary e.g. we write
$F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ instead of
$F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})$.

Therefore, we have $\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
y\in\mathbb{R}$,

$\small|\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|\leq|\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|+|F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|$

The convergence of the two right-hand terms is handled separately into the
following Proposition A.5 and Lemma A.1.

######  Proposition A.5.

Consider a random forest which satisfies Assumtions A.1 to A.3. Then,

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
y\in\mathbb{R},\quad
F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$
(A.2)

Proposition A.5 shows that the Projected CDF honest Forest is consistent and
Lemma A.1 shows that the honest and the non-honest forest are close.

######  Lemma A.1.

Consider a random forest which satisfies Assumtions A.1 to A.3. Then,

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
y\in\mathbb{R},\quad|F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n})-\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n}|\overset{a.s}{\to}0$
(A.3)

Hence, according to Proposition A.5 and Lemma A.1, we get

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
y\in\mathbb{R},\quad\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n})\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$
(A.4)

To have the almost sure uniform convergence relative to y of the Projected CDF
honest forest, we use Dini’s second theorem. Indeed, $\\{Y^{\diamond i}\leq
y\\}=\\{U_{i}\leq F_{S}(y|X^{\diamond i}_{S})\\}$, where $U_{i},i=1,\dots,n$
are i.i.d uniform random variables. Let
$s_{i}=F_{S}(y|\boldsymbol{X}_{S}=X^{\diamond i}_{S})=F_{S}(y|X^{\diamond
i}_{S})$ and $s=F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$, we have

$\displaystyle\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n})$
$\displaystyle=\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{U_{i}\leq
s_{i}\\}}$
$\displaystyle=\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}\leq
s\\}},$

where $\tilde{U}_{i}\sim\mathcal{U}(s_{i},s_{i}+1),i=1,\dots,n$ are
independent uniform variable. Then, A.4 is equivalent to:

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
s\in[0,1],\quad\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}\leq
s\\}}\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}s$ (A.5)

A.5 states that, $\forall s\in[0,1],\exists
N_{s}\subset\Omega,\mathbb{P}(N_{s})=0$ such that

$\displaystyle\forall\omega\in
N_{s}^{\mathrm{c}},\quad\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
s\\}}\underset{n\to+\infty}{\overset{}{\longrightarrow}}s.$ (A.6)

Thus, we need to find a set $N$ that does not depend on $s$ which satisfies
A.6 to get the uniform convergence with Dini’s second theorem. To that aim, we
will use the density of $\mathbb{Q}$ in $\mathbb{R}$ as in the proof of the
Glivenko-Cantelli theorem.

Since the countable union of null set is a null set, $\exists
N\subset\Omega,\mathbb{P}(N)=0$ such that

$\displaystyle\forall s\in[0,1]\cap\mathbb{Q},\;\forall\omega\in
N^{\mathrm{c}},\quad\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
s\\}}\underset{n\to+\infty}{\overset{}{\longrightarrow}}s$ (A.7)

A.7 is also true $\forall s\in[0,1]$. Indeed, let $s\in[0,1],\epsilon>0,w\in
N,\exists p,q\in\mathbb{Q}$ such that $s-\epsilon\leq p\leq s\leq q\leq
s+\epsilon$, since
$s\rightarrow\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(w)\leq
s\\}}$ is increasing, we have:

$\displaystyle\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
p\\}}\leq\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
s\\}}\leq\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
q\\}}$ (A.8)

Thus,

$\displaystyle
s-\epsilon\leq\liminf\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
s\\}}\leq\limsup\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(\omega)\leq
s\\}}\leq s+\epsilon$ (A.9)

So we have shown that $\exists N\subset\Omega,\mathbb{P}(N)=0,\forall\omega\in
N^{\mathrm{c}}$

  * •

$s\rightarrow\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(w)\leq
s\\}}$ is increasing for all $n\in\mathbb{N}^{\star}$

  * •

$\forall
s\in[0,1],\quad\sum_{i=1}^{n}w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{\tilde{U}_{i}(w)\leq
s\\}}\underset{n\to+\infty}{\overset{}{\longrightarrow}}s$ and $s\rightarrow
s$ is continuous

Then the Dini’s second theorem states that we have the almost sure uniform
convergence proving Theorem 4.4. Now, we turn to the proof of Proposition A.5
and Lemma A.1. To that aim, we need the following lemma based on Vapnik-
Chervonenkis classes.

######  Lemma A.2.

Consider $\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond},$ two independent
datasets of independent n samples of $(\boldsymbol{X},Y)$. Build a tree using
$\mathcal{D}_{n}$ with bootstrap and bagging procedure driven by $\Theta$. As
before, $N(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))$ is the number of
bootstrap observations of $\mathcal{D}_{n}$ that fall into
$A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$ and
$N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))$ is the number of
observations of $\mathcal{D}_{n}^{\diamond}$ that fall into
$A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})$. Then:

$\displaystyle\forall\epsilon>0,\quad\mathbb{P}\left(\left\lvert
N(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))-N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))\right\rvert>\epsilon\right)\leq
24(n+1)^{2|S|}e^{-\epsilon^{2}/288n}$ (A.10)

See the proof in [Elie-Dit-Cosaque and Maume-Deschamps, 2020], Lemma 5.3.

Proof of proposition A.5.

We want to show that:

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
y\in\mathbb{R},\quad
F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},\mathcal{D}_{n}^{\diamond})\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|$

Let $x\in\mathbb{R}^{d},y\in\mathbb{R}$, we have:

$\displaystyle\left\lvert
F_{S}^{\diamond}(y|\boldsymbol{x}_{S})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\right\rvert$
$\displaystyle\leq\left\lvert\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\Big{(}\mathds{1}_{\\{Y^{\diamond
i}\leq y\\}}-F_{S}(y|\boldsymbol{X}_{S}^{\diamond i})\Big{)}\right\rvert$
$\displaystyle+\left\lvert\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\Big{(}F_{S}(y|\boldsymbol{X}_{S}^{\diamond
i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\Big{)}\right\rvert$

We define
$W_{n}=\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\Big{(}\mathds{1}_{\\{Y^{\diamond
i}\leq y\\}}-F_{S}(y|\boldsymbol{X}_{S}^{\diamond i})\Big{)}=$ and
$V_{n}=\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\Big{(}F_{S}(y|\boldsymbol{X}_{S}^{\diamond
i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\Big{)}$ and treat each term
separately.

Let prove that
$|W_{n}|\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}0$. We can
rewrite $W_{n}$ as
$W_{n}=\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})H^{\diamond}_{i}$
where $H^{\diamond}_{i}$ is bounded by $1$ and $E[H^{\diamond}_{i}|X^{\diamond
i}_{S}]=0$. Then,

$\displaystyle P(W_{n}>\epsilon)$ $\displaystyle\leq
e^{-t\epsilon}\;\mathbb{E}[e^{tW_{n}}]$ $\displaystyle\leq
e^{-t\epsilon}\;\mathbb{E}\left[\prod_{i=1}^{n}\mathbb{E}\left[e^{tw_{n,i}^{\diamond}(\boldsymbol{x}_{S})H^{\diamond
i}}|\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},X^{\diamond,i}_{S},\dots,X^{\diamond,n}_{S}\right]\right]$
$\displaystyle\leq
e^{-t\epsilon}\;\mathbb{E}\left[\prod_{i=1}^{n}e^{\frac{t^{2}}{2}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})^{2}}\right]$

The last inequality comes from the fact that
$w_{n,i}^{\diamond}(\boldsymbol{x}_{S})$ is a constant given
$\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n},X^{\diamond,i}_{S},\dots,X^{\diamond,n}_{S}$,
and as $H^{\diamond i}$ is bounded by 1 with $E[H^{\diamond}_{i}|X^{\diamond
i}_{S}]=0$, we used the following inequality: If $|X|\leq 1$ a.s and
$\mathbb{E}[X]=0$, then
$\mathbb{E}[e^{tX}]\leq\mathbb{E}[e^{\frac{t^{2}}{2}}]$.

By using Assumption A.2, item 2., let $K>0$ be such that $\forall l\in[k]$,
$N(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))\geq\frac{K\sqrt{n}\ln(n)^{\beta}}{2}$
a.s., then we have
$\Gamma(l)=\\{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))\leq\frac{K\sqrt{n}\ln(n)^{\beta}}{2}\\}\subset\\{|N(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))-N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))|\geq\frac{K\sqrt{n}\ln(n)^{\beta}}{2}\\}$.
Thus, using Lemma A.2, we have that $\mathbb{P}(\Gamma(l))\leq
24(n+1)^{2|S|}\exp(-\frac{-K^{2}(\ln(n)^{2\beta})}{1152})$.

We have

$\displaystyle\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})^{2}$
$\displaystyle=\sum_{i=1}^{n}\frac{w_{n,i}^{\diamond}(\boldsymbol{x}_{S})}{k}\left(\sum_{l=1}^{k}\frac{\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l}))}(\mathds{1}_{\\{\Gamma(l)\\}}+\mathds{1}_{\\{\Gamma(l)^{c}\\}})\right)$
$\displaystyle\leq\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\left(\frac{2}{K\sqrt{n}\ln(n)^{\beta}}+\frac{1}{k}\sum_{l=1}^{k}\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S};\Theta_{l},\mathcal{D}_{n})}\mathds{1}_{\\{\Gamma(l)\\}}\right)$

So that,

$\displaystyle P(W_{n}>\epsilon)$
$\displaystyle\leq\exp(-t\epsilon+\frac{t^{2}}{K\sqrt{n}\ln(n)^{\beta}})\mathbb{E}\left[\exp\left(\frac{t^{2}}{2}\mathds{1}_{\cup_{l=1}^{k}\Gamma(l)}\right)\right]$
$\displaystyle\leq\exp(-t\epsilon+\frac{t^{2}}{K\sqrt{n}\ln(n)^{\beta}})\times\left(1+e^{\frac{t^{2}}{2}}\sum_{l=1}^{k}\mathbb{P}(\Gamma(l))\right)$
$\displaystyle\leq\exp(-t\epsilon+\frac{t^{2}}{K\sqrt{n}\ln(n)^{\beta}})\times\left(1+24k(n+1)^{2|S|}\exp\left({\frac{t^{2}}{2}-\frac{K^{2}\ln(n)^{2\beta}}{1152}}\right)\right)$

Taking $t^{2}=\frac{K^{2}\ln(n)^{2\beta}}{576}$ leads to

$\displaystyle P(W_{n}>\epsilon)$
$\displaystyle\leq(1+24k(n+1)^{2|S|})\exp\left({\frac{K\ln(n)^{\beta}}{576\sqrt{n}}-\frac{\epsilon
K\ln(n)^{\beta}}{24}}\right)$

We obtain the same bound for
$\mathbb{P}(W_{n}\leq-\epsilon)=\mathbb{P}(-W_{n}>\epsilon)$, then by using
Assumption A.2, item 1., $k=\mathcal{O}(n^{\alpha})$ so that the right term is
finite, we conclude by Borel cantelli that $|W_{n}|$ goes to 0 a.s.

Finally, we show that
$V_{n}\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}0$.

$\displaystyle|V_{n}|$
$\displaystyle=\left|\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\Big{(}F_{S}(y|\boldsymbol{X}_{S}^{\diamond
i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\Big{)}\right|$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\frac{\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\left|\Big{(}F_{S}(y|\boldsymbol{X}_{S}^{\diamond
i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\Big{)}\right|$
$\displaystyle\leq\sum_{l=1}^{k}\left(\sum_{i=1}^{n}\frac{\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\left|F_{S}(y|\boldsymbol{X}_{S}^{\diamond
i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\right|\right)$
$\displaystyle\leq\sum_{l=1}^{k}\left(\sum_{i=1}^{n}\frac{\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\sup_{\boldsymbol{z}\in
A_{n}^{(S)}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}\left|F_{S}(y|\boldsymbol{X}_{S}=z_{S})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\right|\right)$
$\displaystyle\leq\sum_{l=1}^{k}\sup_{\boldsymbol{z}\in
A_{n}^{(S)}(\boldsymbol{x};\Theta_{l},\mathcal{D}_{n})}\left|F_{S}(y|\boldsymbol{X}_{S}=z_{S})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})\right|$

By assumption A.1 i.e that variation of the Projected CDF within the cell of
the Projected Tree vanishes, we conclude that
$|V_{n}|\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}0$ ending the
proof of Proposition A.5.

Proof of Lemma A.1.

We want to show that:

$\displaystyle\forall\boldsymbol{x}\in\mathbb{R}^{d},\forall
y\in\mathbb{R}\quad|F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n})-\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S},\Theta_{1},\dots,\Theta_{k},\mathcal{D}_{n}|\overset{a.s}{\to}0.$

We have

$\displaystyle|F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|=|\sum_{i=1}^{n}w_{n,i}^{\diamond}(\boldsymbol{x}_{S})\mathds{1}_{\\{Y^{\diamond
i}\leq y\\}}-w_{n,i}(\boldsymbol{x}_{S})\mathds{1}_{\\{Y^{i}\leq y\\}}|$
$\displaystyle=\left|\sum_{i=1}^{n}\frac{1}{k}\sum_{l=1}^{k}\frac{\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\mathds{1}_{\\{Y^{\diamond
i}\leq
y\\}}-\frac{1}{k}\sum_{l=1}^{k}\frac{B_{n}(X^{i};\Theta_{l})\mathds{1}_{X^{i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}}{N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\mathds{1}_{\\{Y^{i}\leq
y\\}}\right|$
$\displaystyle=\left|\frac{1}{k}\sum_{l=1}^{k}\left(\frac{\sum_{i=1}^{n}\mathds{1}_{X^{\diamond
i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}\mathds{1}_{\\{Y^{\diamond
i}\leq
y\\}}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}-\frac{\sum_{i=1}^{n}B_{n}(X^{i};\Theta_{l})\mathds{1}_{X^{i}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n})}\mathds{1}_{\\{Y^{i}\leq
y\\}}}{N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\right)\right|$

As in [Arenal-Gutiérrez et al., 1996], we replace the boostrap component with
$Z^{1},\dots,Z^{n}$ which are distributed as $Z=(Z_{1},Z_{2})$ that has
uniform distribution over
$\mathcal{D}_{n}=\\{(\boldsymbol{X}^{1},Y^{1}),\dots,(\boldsymbol{X}^{n},Y^{n})\\}$
conditionally to $\mathcal{D}_{n}$.

$\displaystyle|F_{S}^{\diamond}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})-\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})|$
$\displaystyle=\left|\frac{1}{k}\sum_{l=1}^{k}\left(\frac{\sum_{i=1}^{n}\mathds{1}_{\\{X^{\diamond
i}\in A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Y^{\diamond
i}\leq
y\\}}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}-\frac{\sum_{i=1}^{n}\mathds{1}_{\\{Z^{i}_{1}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Z^{i}_{2}\leq
y\\}}}{N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\right)\right|$
$\displaystyle\leq\frac{1}{k}\sum_{l=1}^{k}\left|\frac{\sum_{i=1}^{n}\mathds{1}_{\\{X^{\diamond
i}\in A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Y^{\diamond
i}\leq
y\\}}}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}-\frac{\sum_{i=1}^{n}\mathds{1}_{\\{Z^{i}_{1}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Z^{i}_{2}\leq
y\\}}}{N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\right|$
$\displaystyle\overset{\mathrm{def}}{=}\frac{1}{k}\sum_{l=1}^{k}|G_{l}|$

We have,

$\displaystyle|G_{l}|\leq|G_{l}^{1}|+|G_{l}^{2}|$

with

$\displaystyle G_{l}^{1}=\frac{\left|\sum_{i=1}^{n}\mathds{1}_{\\{X^{\diamond
i}\in A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Y^{\diamond
i}\leq y\\}}-\sum_{i=1}^{n}\mathds{1}_{\\{Z^{i}_{1}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Z^{i}_{2}\leq
y\\}}\right|}{N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}\text{and}$
$\displaystyle G_{l}^{2}=\frac{\left|\sum_{i=1}^{n}\mathds{1}_{\\{X^{\diamond
i}\in A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Y^{\diamond
i}\leq y\\}}-\sum_{i=1}^{n}\mathds{1}_{\\{Z^{i}_{1}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Z^{i}_{2}\leq
y\\}}\right|}{N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}.$

Therefore, A.1 is equivalent to show that $\forall
l\in[k],\;|G_{l}^{1}|,|G_{l}^{2}|\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}0$.

Let $\epsilon>0$, by using Assumption A.2, item 2. i.e $\exists
K>0,N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))\geq
K\sqrt{n}\ln(n)^{\beta}$, we have,

$\displaystyle\mathbb{P}(|G_{l}^{1}|>\epsilon)$
$\displaystyle=\mathbb{P}\left[\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{X^{\diamond
i}\in A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Y^{\diamond
i}\leq y\\}}-\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{Z^{i}_{1}\in
A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l},\mathcal{D}_{n}),\;Z^{i}_{2}\leq
y\\}}\right|>\frac{\epsilon
N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}{n}\right]$
$\displaystyle\leq\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{\diamond
i},Y^{\diamond i})\in A}-\mathbb{P}\left((\boldsymbol{X},Y)\in
A\right)\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]$
$\displaystyle+\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}-\mathbb{P}\left((\boldsymbol{X},Y)\in
A\right)\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]$
$\displaystyle+\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]$
$\displaystyle\leq
2\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}-\mathbb{P}\left((\boldsymbol{X},Y)\in
A\right)\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]$
$\displaystyle+\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]$

where
$\mathcal{B}=\Big{\\{}\prod_{i=1}^{|S|}[a_{i},b_{i}]\times[-\infty,y]:a_{i},b_{i}\in\bar{\mathbb{R}}\Big{\\}}$.
The first term are handled thanks to a direct application of the Theorem 2 in
[Vapnik and Chervonenkis, 2015] that bounds the difference between the
frequencies of events to their probabilities over an entire class
$\mathcal{B}$. Therefore,

$\displaystyle\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}-\mathbb{P}\left((\boldsymbol{X},Y)\in
A\right)\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]\leq
8(n+1)^{2|S|+1}\exp(-\frac{K^{2}\epsilon^{2}\ln(n)^{2\beta}}{288})$

To handle the last term, we apply the Theorem 2 in [Vapnik and Chervonenkis,
2015] under the conditional distribution given $\mathcal{D}_{n}$,

$\displaystyle\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\;\Big{|}\mathcal{D}_{n}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\mathbb{P}\left((\boldsymbol{Z_{1}},Z_{2})\in
A\;|D_{n}\right)\right|>\frac{\epsilon\;K\sqrt{n}\ln(n)^{\beta}}{3n}\;\Big{|}\mathcal{D}_{n}\right]\right]$
$\displaystyle\leq
8(n+1)^{2|S|+1}\exp(-\frac{K^{2}\epsilon^{2}\ln(n)^{2\beta}}{288})$

Finally, we get the overall upper bound,

$\displaystyle\mathbb{P}(|G_{l}^{1}|>\epsilon)\leq
24(n+1)^{2|S|+1}\exp(-\frac{\epsilon^{2}\ln(n)^{2}\beta}{288})$

By Borel-Cantelli, we conclude that
$|G_{l}^{1}|\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}0$.

Now, we treat the term $|G_{l}^{2}|$. The main difference with $|G_{l}^{1}|$
is that $N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))$ was replaced by
$N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))$. The proof remains
the same as above, we just have to show how to deal with
$N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))$ for each term. For
example,

$\displaystyle\small\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}{3n}\right]$
$\displaystyle\small=\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}{3n},\;\exists
l\in[k],|N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))-N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))|>\lambda\right]$
$\displaystyle\small+\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}{3n},\;\forall
l\in[k],|N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))-N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))|\leq\lambda\right]$
$\displaystyle\small\leq
k\;\mathbb{P}\left(|N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))-N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))|>\lambda\right)$
$\displaystyle+\small\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;(N(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))-\lambda)}{3n}\right]$

By using Lemma A.2 for the first term, and Assumption A.2, item 2. with
$\lambda=2K\sqrt{n}\ln(n)^{\beta}$, we have

$\displaystyle\mathbb{P}\left[\sup_{A\in\mathcal{B}}\left|\frac{1}{n}\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{Z}^{i}_{1},\boldsymbol{Z}^{i}_{2})\in
A}-\sum_{i=1}^{n}\mathds{1}_{\\{(\boldsymbol{X}^{i},Y^{i})\in
A}\right|>\frac{\epsilon\;N^{\diamond}(A_{n}^{(S)}(\boldsymbol{x}_{S},\Theta_{l}))}{3n}\right]$
$\displaystyle\leq
k\;24(n+1)^{2|S|}e^{-\epsilon^{2}/288n}+24(n+1)^{2|S|+1}\exp(-\frac{K^{2}\epsilon^{2}\ln(n)^{2\beta}}{288})$

Since $k=\mathcal{O}(n^{\alpha})$ by Assumption A.2, item 1., the right hand
is summable, then we conclude that
$|G_{l}^{2}|\underset{n\to+\infty}{\overset{a.s}{\longrightarrow}}0$.

This conclude the proof of Lemma A.1, thus the proof of Theorem 4.4.

##  Appendix B Empirical evaluations of the estimator $\widehat{F}_{S}$

In order to compare the PRF CDF
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ and
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$, we use a Monte Carlo
estimator to effectively compute
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$. We use the synthetic dataset
of Section 5: $\boldsymbol{X}\in\mathbb{R}^{p}$,
$\boldsymbol{X}\in\mathcal{N}(0,\Sigma)$, $\Sigma=0.8J_{p}+5I_{p}$ with
$p=100$, $I_{p}$ is the identity matrix, $J_{p}$ is all-ones matrix and a
linear predictor with switch defined as:

$\displaystyle\small Y=(X_{1}+X_{2})\mathds{1}_{X_{5}\leq
0}+(X_{3}+X_{4})\mathds{1}_{X_{5}>0}.$ (B.1)

The variables $X_{i}$ for $i=6\dots 100$ are noise variables. We fit a RF with
a sample size $n=10^{4}$, $k=20$ trees and the minimal number of samples by
leaf node is set to $t_{n}=\lfloor\sqrt{n}\times\ln(n)^{1.5}/250\rfloor$ for
the original and the Projected Forest.

We chose a randomly chosen point $\boldsymbol{x}_{S}=[-0.13,1.29,-1.31]$ with
$S=[1,2,5]$ from the test set. The experiment is replicated 100 times. Figure
1 shows that the estimator works well for almost all points $y\in\mathbb{R}$.

Figure 1: Comparison of
$\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ and
$F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$ with $S=[1,2,5]$ and
$\boldsymbol{x}_{S}=[-0.13,1.29,-1.31]$

We also compute two global metrics. For a given $S$, we compute the average
Kolmogorov-Smirnov
$MKS=\frac{1}{n}\sum_{i=1}^{n}\sup_{y\in\mathbb{R}}|\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S,i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S,i})|$
and the average mean absolute deviation
$MAD=\frac{1}{n}\sum_{i=1}^{n}\int_{\mathbb{R}}|\widehat{F}_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S,i})-F_{S}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S,i})|dy$.

We have MAD = 0.008 and the MKS=0.26 on all the observations with
$S=[1,2,3,5]$ showing the estimator’s efficiency. We also compute them with
small $S=[0,4]$, it works even better with MAD=$0.068$, MKS=$0.0098$.

##  Appendix C Additional experiments

###  C.1 Local rules of Anchors and Sufficient Rules with ground truth
explanations

In this section, we compare Anchors and Sufficient Rules in a synthetic
dataset where there are strong dependencies between the important features. In
this case, we can evaluate their capacity of providing the ground truth
minimal rules since we know the distribution of the data. We use the moon
dataset $(X_{1},X_{2},Y)\in\mathbb{R}^{2}\times\\{0,1\\}$, see figure 2, and
we add gaussian features $\boldsymbol{Z}\in\mathbb{R}^{100}$ with the
$\mu,\Sigma$ of the previous section such that the final data is
$(X_{1},X_{2},\boldsymbol{Z},Y)$. In addition, if $Z_{1}>0$, we flip the label
$Y$ of the observations.
We train a RF with the parameters of the previous section. It has AUC=$99\%$
on the test set ($10^{4}$ observations). We use Anchors with threshold
$\tau=0.95$, tolerance $\delta=0.05$, and the Minimal Sufficient Rules with
$\pi=0.95$ to explain 1000 observations of the test set. We observe that, on
average Anchors tend to give much longer rules. The mean size for Sufficient
Rules is 2, and for Anchors it is 10. In addition, the Minimal Sufficient
Explanations detect local relevant variables more accurately. It has
FDR=$3\%$, TPR=$100\%$ and Anchors has FDR=$48\%$, TPR=$80\%$. Finally, we
observe qualitatively the rules on a given example $\boldsymbol{x}$ (black
star in figure 2). We also test the stability of the explanations by comparing
the rules of $\boldsymbol{x}$ and $\boldsymbol{\tilde{x}}$ a nearby
observation such that $\max_{i\in\\{1,2\\}}|x_{i}-\tilde{x}_{i}|\leq 0.05$
(yellow star in figure 2). The rules given by Anchors for
$\boldsymbol{x},\tilde{\boldsymbol{x}}$ are $\small
L_{\text{Anchors}}(\boldsymbol{x})=\\{X_{1}>-0.03\;\text{AND}\;Z_{1}>0.01\;\text{AND}\;Z_{9}>-1.66\;\text{AND}\;Z_{44}>1.66\;\text{AND}\;Z_{32}\leq-1.57\\}$
and $\small
L_{\text{Anchors}}(\boldsymbol{\tilde{x}})=\\{X_{1}>1.04\;\text{AND}\;X_{2}\leq-0.20\;\text{AND}\;Z_{1}>0.01\;\text{AND}\;Z_{28}>0.01\;\text{AND}\;Z_{45}\leq-1.57\\}$.
We find that the rules are very different, showing instability. Moreover, we
also note that Anchors is very sensitive to random seed. However, the SDP
approach gives the same explanations for
$\boldsymbol{x},\tilde{\boldsymbol{x}}$. The observations have two Minimal
Sufficient Explanations $S^{\star}_{1}=[x_{1},z_{1}]$,
$S^{\star}_{2}=[x_{2},z_{1}]$. Thus, they have two Sufficient Rules, we can
observe them given the axis $X_{1},X_{2}$ in figure 2. We notice that the
rules found are very relevant for explaining these instances’ predictions.
Nevertheless, the vertical rule could be a little more to the left. We think
this inaccuracy comes from the estimation of the RF, which is not perfect.

Figure 2: Explanations of $\boldsymbol{x}$, $\tilde{\boldsymbol{x}}$ by the
two Sufficient Rules, the horizontal/vertical rectangle is associate with
$S^{\star}_{1}=[x_{1},z_{1}],S^{\star}_{2}=[x_{2},z_{1}]$ respectively. The
background samples are the observations with $z_{1}>0$.

As these observations have multiple explanations, we provide an additional
insight about the important variables by computing their Local eXplanatory
Importances (LXI). The LXI of $\boldsymbol{x},\boldsymbol{\tilde{x}}$ are
$\big{[}\boldsymbol{x}_{1}=0.5,\boldsymbol{x}_{2}=0.5,\boldsymbol{z}_{1}=1,\boldsymbol{z_{2}}=0,\dots,\boldsymbol{z}_{100}=0\big{]}$.
It shows that the variables $\\{Z_{i}\\}_{i\in\llbracket 2,100\rrbracket}$ are
irrelevant for these observations. The relevant variables are
$X_{1},X_{2},Z_{1}$ and especially $Z_{1}$ is the most important. It is a
necessary feature as it appears in every Sufficient Explanations.

#### Comparison of SHAP values and LXI on Moon Data:

In figure 3, we compare the SHAP values and LXI of an observation with
$Z_{1}>0$ (the green star). We observe that the LXI gives non-null values only
on the active variable $(X_{2},Z_{1})$, while the SV gives non-null values
also on noise variables. Moreover, SV gives a non-negligible value to the
feature $X_{1}$ that is not necessary for this prediction. Indeed, by
analyzing figure 2, we observe that whatever the value of $X_{1}$, if we fix
$X_{2}$ and the sign of $Z_{1}$, the prediction will not change.

(a) LXI

(b) SHAP values

Figure 3: LXI and SHAP values of the green star

We also compute the mean importance score across the population in figure 4.
For the SV, we take the mean absolute values as it may have negative
contributions. The three important values that come out for both methods are
$X_{1},X_{2},Z_{1}$. However, as in the local case, SV assign values to the
noise variables.

(a) Mean LXI

(b) Mean absolute SHAP

Figure 4: Comparison of Mean LXI and Mean absolute SHAP

###  C.2 Shapley values and Local eXplanatory importance (LXI) on LUCAS
dataset

In this section, we want to highlight a case where the LXI permit to
drastically simplify the different explanations. We use a semi-synthetic
dataset LUCAS (LUng CAncer Simple set), a dataset generated by causal Bayesian
networks with 12 binary variables. The causal graph is drawn in figure 6 and
the probability table in figure 6 .

Figure 5: Bayesian network that represents the causal relationships between
variables

Figure 6: Probabilities table used to generate Data

In figure 7, we observe the different explanations of an observation chosen
randomly, its features values are
$\big{\\{}\textbf{Smoking}={\color[rgb]{0,0,1}True},\;\textbf{Yellow
Fingers}={\color[rgb]{0,0,1}True},\;\textbf{Anxiety}={\color[rgb]{1,0,0}False},\;\textbf{Peer
Pressure}={\color[rgb]{1,0,0}False},\;\textbf{Genetic}={\color[rgb]{1,0,0}False},\;\textbf{Attention
Disorder}={\color[rgb]{0,0,1}True},\;\textbf{Born an Even
Day}={\color[rgb]{1,0,0}False},\;\textbf{Car
Accident}={\color[rgb]{0,0,1}True},\;\textbf{Fatigue}={\color[rgb]{0,0,1}True},\;\textbf{Allergy}={\color[rgb]{1,0,0}False},\;\textbf{Coughing}={\color[rgb]{0,0,1}True}\big{\\}}$
and its label is True. We see in the left of figure 7 that it has many
Sufficient Explanations. Therefore, as seen in the right of Figure 7, the LXI
permit to synthesize all the different explanations in a single feature
contributions that exhibits the local importance of the variables. Each value
corresponds to the frequency of apparition of the corresponding feature in the
set of all the sufficient explanations.

Figure 7: Screenshot of a web-App showing the Sufficient Explanations and LXI
of an observation chosen randomly

At the bottom of figure 7, we observe the rule associated with the first
Sufficient Explanation which is
$\big{\\{}\textbf{Smoking}={\color[rgb]{0,0,1}True},\;\textbf{Coughing}={\color[rgb]{0,0,1}True}\big{\\}}$.
Note that this rule is very powerful, because it has a coverage of $46\%$ and
an accuracy of $93\%$.

#### Comparison of SHAP values and LXI on LUCAS:

We can also compare the SHAP values and LXI on this dataset. In figure 8, we
observe that it is the value of Coughing that is really important for this
observation. Indeed it appears in several Sufficient Explanations ($80\%$). On
the other side, in figure 9, SHAP associates values to many more variables,
and it is difficult to discriminate between the important values. It is
difficult to deduce from the values of Smoking, Coughing, Fatigue, Allergy
which is the most important variable with SHAP values.

Figure 8: Sufficient Explanations and Local Explanatory Importance Figure 9:
SHAP values

###  C.3 Stability of Anchors and Sufficient Rules

Here, we run the last experiment of Section 5 on the stability of the local
rules (Anchors, Sufficient Explanations) with different parameters. It
consists of evaluating the stability of the methods w.r.t to input
perturbations. For a given observation $\boldsymbol{x}$, we compare the rule
of each method with the rules obtained for 50 noisy versions of
$\boldsymbol{x}$ by adding random Gaussian noises
$\mathcal{N}(0,\epsilon\times I)$ to the values of the features with different
$\epsilon=0.01,0.001$.

Figure 10: Size distribution of Anchors (left) and Sufficient Rules (right)
when $\epsilon=0.001$ Figure 11: Size distribution of Anchors (left) and
Sufficient Rules (right) when $\epsilon=0.01$

##  Appendix D From Sufficient Rules to Global Interpretable model

In this section, we investigate the capacity of transforming the Sufficient
Rules explanations as a competitive global model. Indeed, we can build a
global model by combining all the Sufficient Rules found for the observations
in the training 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 (accuracy or $R^{2}$). We have
experimented on 2 real-world datasets: Diabetes [Kaggle, 2016] contains
diagnostic measurements and aims to predict whether or not a patient has
diabetes, Breast Cancer Wisconsin (BCW) [Dua and Graff, 2017] consists of
predicting if a tumor is benign or not using the characteristic of the cell
nuclei. Thus, we perform comparisons between the global model induced by the
Sufficient Rules (G-SR) and SOTA global rule-based models as baseline. We use
the package imodel [Singh et al., 2021] (resp. scikit-learn [Pedregosa et al.,
2011]) for RuleFit, Skoped Rule (SkR) (resp. Decision Tree (DT), Random Forest
(RF)). In table 3, we observe that the G-SR performs as well as the best
baseline models while being transparent in its decision process. These
experiments increase the trustworthiness of our explanations because we derive
an interpretable (by-design) global model without paying a trade-off with
performance. As a by-product, SR can be used as a new way of building glass-
box models, but this line of research is beyond the scope of the current work.

Table 3: Accuracy of the different models on Diabetes and Breast Cancer Wisconsin dataset (BCW). For G-SR, we add the coverage of the model on the test-set in brackets. Data set | G-SR | RuleFit | SkR | DT | RF
---|---|---|---|---|---
Diabetes | 0.98 (81%) | 0.76 | 0.71 | 0.90 | 0.92
BCW | 0.95 (92%) | 0.95 | 0.93 | 0.95 | 0.96

These experiment permit to enforce the trust in the explanations given by our
methods and open new avenues to build a glass-box model with the SR.

##  Appendix E Projected Forest CDF algorithm

1: Inputs : A random forest fit with $\mathcal{D}_{n}$, a query point
$\boldsymbol{x}_{S}$, $y$, min_nodes_size

2: Output : $\widehat{F}(y|\boldsymbol{X}_{S}=\boldsymbol{x}_{S})$

3: for all trees in the forest do

4: initialize nodes_level as a list of nodes containing only the root node;

5: initialize nodes_child as an empty list of child nodes;

6: initialize samples as the list of observation indices of the full training
data of the tree;

7: for all levels in the tree do

8: for all nodes in nodes_level: do

9: if the node splits on a variable in $S$ then

10: compute whether $\boldsymbol{x}_{S}$ falls in the left or right child
node;

11: append the child node to nodes_child;

12: set samples_child as the observations in samples which satisfy the split;

13: else

14: append both the left and right children nodes to nodes_child;

15: set samples = samples_child;

16: end if

17: if the size of samples_child is lower than min_node_size then

18: break the loop through the tree levels;

19: else

20: set samples = samples_child;

21: end if

22: end for

23: set nodes_level = nodes_child;

24: end for

25: compute the tree prediction as the average of $\mathds{1}_{Y_{i}\leq y}$
for all $i$ in samples;

26: end for

27: return average the prediction of all trees;

Algorithm 1 Projected Forest CDF: $\widehat{F}_{S}$