Trading Complexity for Sparsity in Random Forest Explanations
Year: 2021

Abstract:
Random forests have long been considered as powerful model ensembles in ma1 chine learning. By training multiple decision trees, whose diversity is fostered 2 through data and feature subsampling, the resulting random forest can lead to 3 more stable and reliable predictions than a single decision tree. This however 4 comes at the cost of decreased interpretability: while decision trees are often easily 5 interpretable, the predictions made by random forests are much more difficult to 6 understand, as they involve a majority vote over hundreds of decision trees. In 7 this paper, we examine different types of reasons that explain “why” an input 8 instance is classified as positive or negative by a Boolean random forest. Notably, 9 as an alternative to sufficient reasons taking the form of prime implicants of the 10 random forest, we introduce majoritary reasons which are prime implicants of a 11 strict majority of decision trees. For these different abductive explanations, the 12 tractability of the generation problem (finding one reason) and the minimization 13 problem (finding one shortest reason) are investigated. Experiments conducted on 14 various datasets reveal the existence of a trade-off between runtime complexity and 15 sparsity. Sufficient reasons for which the identification problem is DP-complete 16 are slightly larger than majoritary reasons that can be generated using a simple 17 linear-time greedy algorithm, and significantly larger than minimal majoritary 18 reasons that can be approached using an anytime PARTIAL MAXSAT algorithm. 19

Random forests have long been considered as powerful model ensembles in ma-1 chine learning. By training multiple decision trees, whose diversity is fostered2 through data and feature subsampling, the resulting random forest can lead to3 more stable and reliable predictions than a single decision tree. This however4 comes at the cost of decreased interpretability: while decision trees are often easily5 interpretable, the predictions made by random forests are much more difficult to6 understand, as they involve a majority vote over hundreds of decision trees. In7 this paper, we examine different types of reasons that explain “why” an input8 instance is classified as positive or negative by a Boolean random forest. Notably,9 as an alternative to sufficient reasons taking the form of prime implicants of the10 random forest, we introduce majoritary reasons which are prime implicants of a11 strict majority of decision trees. For these different abductive explanations, the12 tractability of the generation problem (finding one reason) and the minimization13 problem (finding one shortest reason) are investigated. Experiments conducted on14 various datasets reveal the existence of a trade-off between runtime complexity and15 sparsity. Sufficient reasons - for which the identification problem is DP-complete16 - are slightly larger than majoritary reasons that can be generated using a simple17 linear-time greedy algorithm, and significantly larger than minimal majoritary18 reasons that can be approached using an anytime PARTIAL MAXSAT algorithm.19
1 Introduction20
Over the past two decades, rapid progress in statistical machine learning has led to the deployment21 of models endowed with remarkable predictive capabilities. Yet, as the spectrum of applications22 using statistical learning models becomes increasingly large, explanations for why a model is making23 certain predictions are ever more critical. For example, in medical diagnosis, if some model predicts24 that an image is malignant, then the doctor may need to know which features in the image have led to25 this classification. Similarly, in the banking sector, if some model predicts that a customer is a fraud,26 then the banker might want to know why. Therefore, having explanations for why certain predictions27 are made is essential for securing user confidence in machine learning technologies [21, 22].28
This paper focuses on classifications made by random forests, a popular ensemble learning method29 that constructs multiple randomized decision trees during the training phase, and predicts by taking a30 majority vote over the base classifiers [8]. Since decision tree randomization is achieved by essentially31 coupling data subsampling (or bagging) and feature subsampling, random forests are fast and easy to32 implement, with few tuning parameters. Furthermore, they often make accurate and robust predictions33 in practice, even for small data samples and high-dimensional feature spaces [6]. For these reasons,34 random forests have been used in various applications including, among others, computer vision [11],35 crime prediction [7], ecology [12], genomics [9], and medical diagnosis [3].36
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Despite their success, random forests are much less interpretable than decision trees. Indeed, the37 prediction made by a decision tree on a given data instance can be easily interpreted by reading the38 unique root-to-leaf path that covers the instance. Contrastingly, there is no such direct reason in a39 random forest, since the prediction is derived from a majority vote over multiple decision trees. So, a40 key issue in random forests is to infer abductive explanations, that is, to explain in concise terms why41 a data instance is classified as positive or negative by the model ensemble.42
Related Work. Explaining random forest predictions has received increasing attention in recent43 years [5, 10, 18]. Notably, in the classification setting, [10, 18] have focused on sufficient reasons,44 which are abductive explanations involving only relevant features [13]. More specifically, if we view45 any random forest classifier as a Boolean function f , then a sufficient reason for classifying a data46 instance x as positive by f is a prime implicant t of f covering x. By construction, removing any47 feature from a sufficient reason t would question the fact that t explains the way x is classified by f .48 Interestingly, if f is described by a single decision tree, then generating a sufficient reason for any49 input instance x can be done in linear time. Yet, in the general case where f is represented by an50 arbitrary number of decision trees, the problem of identifying a sufficient reason is DP-complete.51 Despite this intractability statement, the empirical results reported in [18] show that a MUS-based52 algorithm for computing sufficient reasons proves quite efficient in practice.53
In addition to “model-based” explanations investigated in [10, 18], “model-agnostic” explanations54 can be applied to random forests. Notably, the LIME method [27] extrapolates a linear threshold55 function g from the behavior of the random forest f around an input instance x. Yet, even if a prime56 implicant of the linear threshold function can be easily computed, this explanation is not guaranteed57 abductive since g is only an approximation of f .58
Contributions. In this paper, we introduce several new notions of abductive explanations: direct59 reasons extend to the case of random forests the corresponding notion defined primarily for decision60 trees, and majority reasons are weak forms of abductive explanations which take into account the61 averaging rule of random forests. Informally, a majoritary reason for classifying a instance x as62 positive by some random forest f is a prime implicant t of a majority of decision trees in f that63 covers x. Thus, any sufficient reason is a majoritary reason, but the converse is not true. For these64 different reasons, we examine the tractability of both the generation (finding one explanation) and65 the minimization (finding one shortest explanation) problems. To the best of our knowledge, all66 complexity results related to random forest explanations are new, if we make an exception for the67 intractability of generating sufficient reasons, which was recently established in [18]. Notably, direct68 reasons and majoritary reasons can be derived in time polynomial in the size of the input (the instance69 and the random forest used to classify it). By contrast, the identification of minimal majoritary70 reasons is NP-complete, and the identification of minimal sufficient reasons is Σp2-complete.71
Based on these results, we provide algorithms for deriving random forest explanations, which open the72 way for an empirical comparison. Our experiments made on standard benchmarks show the existence73 of a trade-off between the runtime complexity of finding (possibly minimal) abductive explanations74 and the sparsity of such explanations. In a nutshell, majoritary reasons and minimal majoritary75 reasons offer interesting compromises in comparison to, respectively, sufficient reasons and minimal76 sufficient reasons. Indeed, the size of majoritary reasons and the computational effort required to77 generate them are generally smaller than those obtained for sufficient reasons. Furthermore, minimal78 majoritary reasons outperform minimal sufficient reasons, since the latter are too computationally79 demanding. In fact, using an anytime PARTIAL MAXSAT solver for minimizing majoritary reasons,80 we derive sparse explanations which are typically much shorter than all other forms of abductive81 explanations. Proofs and additional empirical results are provided as supplementary material.82
2 Preliminaries83
For an integer n, let [n] = {1, · · · , n}. By Fn we denote the class of all Boolean functions from84 {0, 1}n to {0, 1}, and we use Xn = {x1, · · · , xn} to denote the set of input Boolean variables. Any85 Boolean vector x ∈ {0, 1}n is called an instance. For any function f ∈ Fn, an instance x ∈ {0, 1}n86 is called a positive example of f if f(x) = 1, and a negative example otherwise.87
We refer to f as a propositional formula when it is described using the Boolean connectives ∧88 (conjunction), ∨ (disjunction) and ¬ (negation), together with the constants 1 (true) and 0 (false). As89
usual, a literal li is a variable xi or its negation ¬xi, also denoted xi. A term (or monomial) t is a90 conjunction of literals, and a clause c is a disjunction of literals. A DNF formula is a disjunction of91 terms and a CNF formula is a conjunction of clauses. The set of variables occurring in a formula f is92 denoted Var(f). In the rest of the paper, we shall often treat instances as terms, and terms as sets of93 literals. Given an assignment z ∈ {0, 1}n, the corresponding term is defined as94
tz = n∧ i=1 xzii where x 0 i = xi and x 1 i = xi
A term t covers an assignment z if t ⊆ tz . An implicant of a Boolean function f is a term that95 implies f , that is, a term t such that f(z) = 1 for every assignment z covered by t. A prime implicant96 of f is an implicant t of f such that no proper subset of t is an implicant of f .97
With these basic notions in hand, a (Boolean) decision tree on Xn is a binary tree T , each of whose98 internal nodes is labeled with one of n input variables, and whose leaves are labeled 0 or 1. Every99 variable is supposed (w.l.o.g.) to occur at most once on any root-to-leaf path (read-once property).100 The value T (x) ∈ {0, 1} of T on an input instance x is given by the label of the leaf reached from101 the root as follows: at each node go to the left or right child depending on whether the input value of102 the corresponding variable is 0 or 1, respectively. A (Boolean) random forest on Xn is an ensemble103 F = {T1, · · · , Tm}, where each Ti (i ∈ [m]) is a decision tree on Xn, and such that the value104 F (x) ∈ {0, 1} on an input instance x is given by105
F (x) =
{ 1 if 1m ∑m i=1 Ti(x) > 1 2
0 otherwise. The size of F is given by |F | = ∑m
i=1 |Ti|, where |Ti| is the number of nodes occurring in Ti. The106 class of decision trees on Xn is denoted DTn, and the class of random forests with at most m decision107 trees (with m ≥ 1) over DTn is denoted RFn,m. RFn is the union of all RFn,m for m ∈ N.108 Example 1. The random forest F = {T1, T2, T3} in Figure 1 is composed of three decision trees.109 It separates Cattleya orchids from other orchids using the following features: x1: “has fragrant110 flowers”, x2: “has one or two leaves”, x3: “has large flowers”, and x4: “is sympodial”.111
It is well-known that any decision tree T can be transformed into its negation ¬T ∈ DTn, by simply112 reverting the label of leaves. Negating a random forest can also be achieved in polynomial time:113 Proposition 1. There exists a linear-time algorithm that computes a random forest ¬F ∈ RFn,m114 equivalent to the negation of a given random forest F ∈ RFn,m.115
Another important property of decision trees is that any T ∈ DTn can be transformed in linear time116 into an equivalent disjunction of terms DNF(T ), where each term coincides with a 1-path (i.e., a path117 from the root to a leaf labeled with 1), or a conjunction of clauses CNF(T ), where each clause is the118 negation of term describing a 0-path. When switching to random forests, the picture is quite different:119 Proposition 2. Any CNF or DNF formula can be converted in linear time into an equivalent random120 forest, but there is no polynomial-space translation from RF to CNF or to DNF.121
3 Random Forest Explanations122
The key focus of this study is to explain why a given (Boolean) random forest classifies some incoming123 data instance as positive or negative. This calls for a notion of abductive explanation1. Formally,124 given a Boolean function f ∈ Fn and an instance x ∈ {0, 1}n, an abductive explanation for x125 given f is an implicant t of f (resp. ¬f ) if f(x) = 1 (resp. f(x) = 0) that covers x. An abductive126 explanation t for x given f always exists, since t = tx is such a (trivial) explanation. So, in the rest127 of this section, we shall mainly concentrate on sparse forms of abductive explanations.128
Before delving into details, it is worth mentioning that if f is represented by a random forest then,129 without loss of generality, we can focus on the case where x is a positive example of f , because ¬f130 can be computed in linear time (by Proposition 1). Nevertheless, for the sake of clarity, we shall131 consider both cases f(x) = 1 and f(x) = 0 in our definitions.132
3.1 Direct Reasons133
For a decision tree T ∈ DTn and a data instance x ∈ {0, 1}n, the direct reason of x given T is the134 term tTx corresponding to the unique root-to-leaf path of T that covers x. We can extend this simple135 form of abductive explanation to random forests as follows:136 Definition 1. Let F = {T1, . . . , Tm} be a random forest in RFn,m, and x ∈ {0, 1}n be an instance.137 Then, the direct reason for x given F is the term tFx defined by138
tFx =
{∧ Ti∈F :Ti(x)=1 t Ti x if F (x) = 1∧
Ti∈F :Ti(x)=0 t Ti x if F (x) = 0
By construction, tFx is an abductive explanation which can be computed in O(|F |) time.139 Example 2. Considering Example 1 again, the instance x = (1, 1, 1, 1) is recognized as a Cattleya140 orchid, since F (x) = 1. The direct reason for x given F is tFx = x1 ∧ x2 ∧ x3 ∧ x4. It coincides141 with tx. Consider now the instance x′ = (0, 1, 0, 0); it is not recognized as a Cattleya orchid, since142 F (x) = 0. The direct reason for x′ given F is tFx′ = x2∧x3∧x4. It is a better abductive explanation143 than tx′ itself since it does not contain x1, which is locally irrelevant.144
3.2 Sufficient Reasons145
Another valuable notion of abductive explanation is the one of sufficient reason2, defined for any146 Boolean classifier [13]. In the setting of random forests, such explanations can be defined as follows:147 Definition 2. Let F ∈ RFn be a random forest and x ∈ {0, 1}n be an instance. A sufficient reason148 for x given F is a prime implicant t of F (resp. ¬F ) if F (x) = 1 (resp. F (x) = 0) that covers x.149 Example 3. For our running example, x1 ∧ x2 ∧ x4 and x3 ∧ x4 are the sufficient reasons for x150 given F . x4 and x1 ∧ x2 ∧ x3 are the sufficient reasons for x′ given F .151
Unlike arbitrary abductive explanations, all features occurring in a sufficient reason t are relevant.152 Indeed, removing any literal from t would question the fact that t implies F . To this point, the direct153 reason tFx for x given F may contain arbitrarily many more features than a sufficient reason for x154 given F , since this was already shown in the case where F consists in a single decision tree [17].155
The problem of finding a sufficient reason t for an input instance x ∈ {0, 1}n with respect to a given156 random forest F ∈ RFn, has recently been shown DP-complete [18]. In fact, even the apparently157 simple task of checking whether t is an implicant of F is already hard:158 Proposition 3. Let F be a random forest in RFn and t be a term over Xn. Then, deciding whether t159 is an implicant of F is coNP-complete.160
The above result is in stark contrast with the computational complexity of checking whether a term t161 is an implicant of a decision tree T . This task can be solved in polynomial time, using the fact that162
1Unlike [15], we do not require those explanations to be minimal w.r.t. set inclusion, in order to keep the concept distinct (and actually more general) then the one of sufficient reasons.
2Sufficient reasons are also known as prime-implicant explanations [29].
T can be converted (in linear time) into its clausal form CNF(T ), together with the fact that testing163 whether t implies CNF(T ) can be done inO(|T |) time. That mentioned, in the case of random forests,164 the implicant test can be achieved via a call to a SAT oracle:165 Proposition 4. Let F = {T1, . . . , Tm} be a random forest of RFn,m, and t be a (satisfiable) term166 over Xn. Let H be the CNF formula167
{(yi ∨ c) : i ∈ [m], c ∈ CNF(¬Ti)} ∪ CNF ( m∑ i=1 yi > m 2 ) where {y1, . . . , ym} are fresh variables and CNF (∑m i=1 yi > m 2 ) is a CNF encoding of the cardinality168
contraint ∑m
i=1 yi > m 2 . Then, t is an implicant of F if and only if H ∧ t is unsatisfiable.169
Based on such an encoding, the sufficient reasons for an instance x given a random forest F can170 be characterized in terms of MUS (minimal unsatisfiable subsets), as suggested in [18]. This171 characterization is useful because many SAT-based algorithms for computing a MUS (or even all172 MUSes) of a CNF formula have been pointed out for the past decade [2, 19, 20], and hence, one can173 take advantage of them for computing sufficient reasons.174
Going one step further, a natural way for improving the clarity of sufficient reasons is to focus on175 those of minimal size. Specifically, given F ∈ RFn and x ∈ {0, 1}n, a minimal sufficient reason for176 x with respect to F is a sufficient reason for x given F of minimal size.3177 Example 4. For our running example, x3 ∧ x4 is the unique minimal sufficient reason for x given F ,178 and x4 is the unique minimal reason for x′ given F .179
As a by-product of the characterization of a sufficient reason in terms of MUS [18], a minimal180 sufficient reason for x given f can be viewed as a minimal MUS. Thus, we can exploit algorithms for181 computing minimal MUSes (see e.g., [16]) in order to derive minimal sufficient reasons. However,182 deriving a minimal sufficient reason is computationally harder than deriving a sufficient reason:183 Proposition 5. Let F ∈ RFn, x ∈ {0, 1}n, and k ∈ N. Then, deciding whether there exists a184 minimal sufficient reason t for x given F containing at most k features is Σp2-complete.185
3.3 Majoritary Reasons186
Based on the above considerations, a natural question arises: does there exist a middle ground187 between direct reasons, which main contain many irrelevant features but are easy to calculate, and188 sufficient reasons, which only contain relevant features but are potentially much harder to generate?189 Inspired by the way prime implicants can be computed when dealing with decision trees, we can190 reply in the affirmative using the notion of majoritary reasons, defined as follows.191 Definition 3. Let F = {T1, . . . , Tm} be a random forest in RFn,m and x ∈ {0, 1}n be an instance.192 Then, a majoritary reason for x given F is a term t covering x, such that t is an implicant of at least193 bm2 c + 1 decision trees Ti (resp. ¬Ti) if F (x) = 1 (resp. F (x) = 0), and for every l ∈ t, t \ {l}194 does not satisfy this last condition.195 Example 5. For our running example, x has three majoritary reasons given F : x1 ∧ x2 ∧ x4,196 x1 ∧ x3 ∧ x4, and x2 ∧ x3 ∧ x4. Those reasons are better than tFx in the sense that they are shorter197 than this direct reason. Contrastingly, x′ has four majoritary reasons given F : x1 ∧ x4, x2 ∧ x4,198 x3 ∧ x4, and x1 ∧ x2 ∧ x3. Each of the two majoritary reasons x2 ∧ x4, x3 ∧ x4 show that tFx′199 contains some irrelevant literals for the task of classifying x′ using F .200
In general, the notions of majoritary reasons and of sufficient reasons do not coincide. Indeed, a201 sufficient reason t is a prime implicant (covering x) of the forest F , while a majoritary reason t′ is an202 implicant (covering x) of a strict majority of decision trees in the forest F satisfying the additional203 condition that t′ is a prime implicant of at least one of these decision trees. Viewing majoritary204 reasons as “weak” forms of sufficient reasons, they can include irrelevant features:205 Proposition 6. Let F = {T1, . . . , Tm} be a random forest of RFn,m and x ∈ {0, 1}n such that206 F (x) = 1. Unless m < 3, it can be the case that every majoritary reason for x given F contains207 arbitrarily many more features than any sufficient reason for x given F .208
3Minimal sufficient reasons should not to be confused with minimum-cardinality explanations [29], where the minimality condition bears on the features set to 1 in the data instance x.
What makes majoritary reasons valuable is that they are abductive and can be generated in linear time.209 The evidence that any majoritary reason t for x given F is an abductive explanation for x given F210 comes directly from the fact that if t implies a majority of decision trees in F , then it is an implicant211 of F (note that the converse implication does not hold in general).212
The tractability of generating majoritary reasons lies in the fact that they can be found using a simple213 greedy algorithm. For the case where F (x) = 1, start with t = tx, and iterate over the literals l of t214 by checking whether t deprived of l is an implicant of at least bm2 c + 1 decision trees of F . If so,215 remove l from t and proceed to the next literal. Once all literals in tx have been examined, the final216 term t is by construction an implicant of a strict majority of decision trees in F , such that removing217 any literal from it would lead to a term that is no longer an implicant of this majority. So, t is by218 construction a majoritary reason. The case where F (x) = 0 is similar, by simply replacing each219 Ti with its negation in F . This greedy algorithm runs in O(n|F |) time, using the fact that, on each220 iteration, checking whether t is an implicant of Ti (for each i ∈ [m]) can be done in O(|Ti|) time.221 By analogy with minimal sufficient reasons, a natural way of improving the quality of majoritary222 reasons is to seek for shortest ones. Let F ∈ RFn be a random forest and x ∈ {0, 1}n be an instance.223 Then, a minimal majoritary reason for x given F is a minimal-size majoritary reason for x given F .224 Example 6. For our running example, the three majoritary reasons for x given F are its minimal225 majoritary reasons. Contrastingly, among the majoritary reasons for x′ given F , only x1 ∧ x4,226 x2 ∧ x4, and x3 ∧ x4 are minimal majoritary reasons.227
Unsurprisingly, the optimization task for majoritary reasons is more demanding than the generation228 task. Yet, minimal majoritary reasons are easier to find than minimal sufficient reasons. Specifically:229 Proposition 7. Let F ∈ RFn, x ∈ {0, 1}n, and k ∈ N. Then, deciding whether there exists a230 minimal majoritary reason t for x given F containing at most k features is NP-complete.231
A common approach for handling NP-optimization problems is to rely on modern constraint solvers.232 From this perspective, recall that a PARTIAL MAXSAT problem consists of a pair (Csoft, Chard)233 where Csoft and Chard are (finite) sets of clauses. The goal is to find a Boolean assignment that234 maximizes the number of clauses c in Csoft that are satisfied, while satisfying all clauses in Chard.235 Proposition 8. Let F ∈ RFn,m and x ∈ {0, 1}n be an instance such that F (x) = 1. Let236 (Csoft, Chard) be an instance of the PARTIAL MAXSAT problem such that:237
Csoft = {xi : xi ∈ tx} ∪ {xi : xi ∈ tx}
Chard = {(yi ∨ c|x) : i ∈ [m], c ∈ CNF(Ti)} ∪ CNF ( m∑ i=1 yi > m 2 ) where c|x = c ∩ tx is the restriction of c to the literals in tx, {y1, . . . , ym} are fresh variables and238 CNF( ∑m i=1 yi > m 2 ) is a CNF encoding of the contraint ∑m i=1 yi > m 2 . The intersection of tx with239 tz∗ , where z∗ is an optimal solution of (Csoft, Chard), is a minimal majoritary reason for x given F .240
Clearly, in the case where F (x) = 0, it is enough to consider the same instance of PARTIAL MAXSAT241 as above, except that Chard = {(yi ∨ c|x) : i ∈ [m], c ∈ CNF(¬Ti)} ∪ CNF( ∑m i=1 yi > m 2 ).242
Thanks to this characterization result, one can leverage the numerous algorithms that have been243 developed so far for PARTIAL MAXSAT (see e.g. [1, 23, 24, 28]) in order to compute minimal244 majoritary reasons. We took advantage of it to achieve some of the experiments reported in Section 4.245
4 Experiments246
Empirical setting. The empirical protocol was as follows. We have considered 15 datasets, which247 are standard benchmarks from the well-known repositories Kaggle (www.kaggle.com), OpenML248 (www.openml.org), and UCI (archive.ics.uci.edu/ml/). These datasets are compas, placement,249 recidivism, adult, ad_data, mnist38, mnist49, gisette, dexter, dorothea, farm-ads, higgs_boson,250 christine, gina, and bank. mnist38 and mnist49 are subsets of the mnist dataset, restricted to the251 instances of 3 and 8 (resp. 4 and 9) digits. Due to space constraints, additional information about252 the datasets (especially the numbers and types of features, the number of instances), and about the253 random forests that have been trained (especially, the number of Boolean features used, the number254
of trees, the depth of the trees, the mean accuracy) are reported as a supplementary material. We255 used only datasets for binary classification, which is a very common kind of dataset. Categorical256 features have been treated as arbitrary numbers (the scale is nominal). As to numeric features, no data257 preprocessing has taken place: these features have been binarized on-the-fly by the random forest258 learning algorithm that has been used.259
For every benchmark b, a 10-fold cross validation process has been achieved. Namely, a set of 10260 random forest Fb have been computed and evaluated from the labelled instances of b, partitioned261 into 10 parts. One part was used as the test set and the remaining 9 parts as the training set for262 generating a random forest. The classification performance for b was measured as the mean accuracy263 obtained over the 10 random forests generated from b. As to the random forest learner, we have used264 the implementation provided by the Scikit-Learn [26] library in his version 0.23.2. The maximal265 depth of any decision tree in a forest has been bounded at 8. All other hyper-parameters of the266 learning algorithm have been set to their default value except the number of trees. We made some267 preliminary tests for tuning this parameter in order to ensure that the accuracy is good enough. For268 each benchmark b, each random forest F , and a subset of 25 instances x picked up at random in the269 corresponding test set (leading to 250 instances per dataset) we have run the algorithms described in270 Section 3 for deriving the direct reason for x given F , a sufficient reason for x given F , a majoritary271 reason x given F , a minimal majoritary reason for x given F , and a minimal sufficient reason for x272 given F .273
For computing sufficient reasons and minimal majoritary reasons, we took advantage of the Pysat274 library [14] (version 0.1.6.dev15) which provides the implementation of the RC2 PARTIAL MAXSAT275 solver and an interface to MUSER [4]. When deriving majoritary reasons, we picked up uniformly at276 random 50 permutations of the literals describing the instance and tried to eliminate those literals277 (within the greedy algorithm) following the ordering corresponding to the permutation. As a majori-278 tary reason for the instance, we kept a smallest reason among those that have been derived (of course,279 the corresponding computation time that has been measured is the cumulated time over the 50 tries).280 Sufficient reasons have been computed as MUSes, as explained before.281
We also derived a “LIME explanation” for each instance. Such an explanation has been generated282 thanks to the following approach. For any x under consideration, one first used LIME [27] to generate283 an associated linear model wx where wx ∈ Rn. This linear model wx classifies any instance x′ as a284 positive instance if and only if wx ·x′ > 0. Furthermore, wx classifies the instance to be explained x285 in the same way as the black box model considered at start (in our case, the random forest F ). We ran286 the LIME implementation linked to [27] in its latest version. Interestingly, a minimal sufficient reason287 t for x given wx can be generated in polynomial time from wx. We call it a LIME explanation for x.288 The computation of t is as follows. If x is classified positively by wx, in order to derive t, it is enough289 to sum in a decreasing way the positive weights wi occurring in wx until this sum exceeds the sum290 of the opposites of all the negative weights occurring in wx. The term t composed of the variables xi291 corresponding to the positive weights that have been selected is by construction a minimal sufficient292 reason for x given wx since for every x′ covered by t, the inequation wx · x′ > 0 necessarily holds;293 indeed, it holds in the worst situation where all the variables associated with a positive weight in wx294 and not belonging to t are set to 0, whilst all the variables associated with a negative weight in wx295 are set to 1. Similarly, if x is classified negatively by wx, in order to derive t, it is enough to sum in296 an increasing way the negative weights wi occurring in wx until this sum is lower than or equal to297 the opposite of the sum of all the positive weights occurring in wx. This time, the term t composed298 of the variables xi corresponding to the negative weights that have been selected is by construction a299 minimal sufficient reason for x given wx.300
All the experiments have been conducted on a computer equipped with Intel(R) XEON E5-2637 CPU301 @ 3.5 GHz and 128 Gib of memory. A time-out (TO) of 600s has been considered for each instance302 and each type of explanation, except LIME explanations.303
Results. A first conclusion that can be drawn from our experiments is the intractability of computing304 in practice minimal sufficient reasons (this is not surprising, since this coheres with the complexity305 result given by Proposition 5). Indeed, we have been able to compute within the time limit of 600s a306 minimal reason for only 10 instances and a single dataset (compas).307
Due to space limitations, we report hereafter empirical results about two datasets only, namely308 placement and gisette (the results obtained on the other datasets are similar and available as a309
supplementary material). The placement data set is about the placement of students in a campus. It310 consists of 215 labelled instances. Students are described using 13 features, related to their curricula,311 the type and work experience and the salary. An instance is labelled as positive when the student312 gets a job. The random forest that has been generated consists of 25 trees, and its mean accuracy313 is 97.6%. gisette is a much larger dataset, based on 5000 features and containing 7000 labelled314 instances. Features correspond to pixels. The problem is to separate the highly confusible digits 4315 and 9. An instance is labelled as positive whenever the picture represents a 9. The random forest that316 has been generated consists of 85 trees, and its mean accuracy is 96%.317
Figure 2 provides the results obtained for placement, using four plots. Each dot represents an instance.318 The first plot shows the time needed to compute a reason on the x-axis, and the size of this reason on319 the y-axis. On this plot, no dot corresponds to a minimal sufficient reason because their computation320 did not terminate before the time-out. The plot also highlights that all the other reasons have been321 computed within the time limit, and in general using a small amount of time. In particular, it shows322 that the direct reason can be quite large, that the computation of LIME explanations is usually more323 expensive than the ones of the other explanations, and that LIME explanations can be very short (but324 one must keep in mind that they are not abductive explanations in general4). A box plot about the325 sizes of all the explanations is reported (the LIME ones and the direct reasons are not presented for326 the sake of readibility). The figure also provides two scatter plots, aiming to compare the size of327 majoritary reasons with the size of sufficient reasons, as well as the size of the minimal majoritary328 reasons with the size of sufficient reasons. These plots clearly show the benefits that can be offered329 by considering majoritary reasons and minimal majoritary reasons instead of sufficient reasons.330
Figure 3 synthesizes the results obtained for gisette, using four plots again. Three of them are of the331 same kind as the plots used for placement. Conclusions similar to those drawn for placement can332 be derived for gisette, with some exceptions. First of all, this time, no dot corresponds to a minimal333 majoritary reason because their computation did not terminate before the time-out. Furthermore,334 LIME explanations are very long here. This can be explained by the fact that the computation335 achieved by LIME relies on a binary representation of the instance that is quite different (and possibly336 much larger) than the one considered in the representation of the random forest. Indeed, each decision337 tree of the forest focuses only on a subset of most important features (in the sense of Gini criterion)338 found during the learning phase. In our experiments, the size of LIME explanations was typically339 high for datasets based on many features.340
4See also [25] that reports some experiments about ANCHOR (the successor of LIME), assessing the quality of the explanations computed using ANCHOR.
When minimal majoritary reasons are hard to be computed (as it is the case for gisette), an approach341 consists in approximating them. Interestingly, one can take advantage of an incremental PARTIAL342 MAXSAT ALGORITHM, like LMHS [28], to do the job. Specifically, the result given in Proposition343 8 provides a way to derive abductive explanations for an instance x given a random forest F in an344 anytime fashion. Basically, using LMHS, a Boolean assignment z satisfying all the hard constraints of345 Chard and a given number, say k, of soft constraints from Csoft is looked for (k is set to 0 at start).346 If such an assignment is found, then one looks for an assignment satisfying k + 1 soft constraint,347 and so on, until an optimal solution is found or a preset time bound is reached. In many cases, the348 most demanding step from a computational standpoint is the one for which k is the optimal value349 (but one ignores it) and one looks for an assignment that satisfies k + 1 soft constraint (and such an350 assignment does not exist). By construction, every z that is generated that way is such that tx ∩ tz351 is an implicant of F that covers x (and hence, an abductive explanation). The approximation z of352 a minimal majoritary reason for x given F , which is obtained when the time limit is met, can be353 significantly shorter than the sufficient reason for x given F that has been derived. In our experiments,354 we used three time limits: 10s, 60s, 600s. As the box plot and the dedicated scatter plot given in355 Figure 3 show it, the sizes of the approximations z which are derived gently decrease with time.356 Interestingly, the size savings that are achieved in comparison to sufficient reasons are significant,357 even for the smallest time bound of 10s that has been considered.358
5 Conclusion359
In this paper, we have introduced, analyzed and evaluated some new notions of abductive explanations360 suited to random forest classifiers, namely majoritary reasons and minimal majoritary reasons.361 Our investigation reveals the existence of a trade-off between runtime complexity and sparsity for362 abductive explanations. Unlike sufficient reasons, majoritary reasons and minimal majoritary reasons363 may contain irrelevant features. Despite this evidence, majoritary reasons and minimal majoritary364 reasons appear as valuable alternative to sufficient reasons. Indeed, majoritary reasons can be365 computed in polynomial time while sufficient reasons cannot (unless P = NP). In addition, most of366 the time in our experiments, majoritary reasons appear as slightly smaller than sufficient reasons.367 Minimal majoritary reasons can be looked for when majoritary reasons are too large, but this is at368 the cost of an extra computation time that can be important, and even prohibitive in some cases.369 However, minimal majoritary reasons can be approximated using an anytime PARTIAL MAXSAT370 algorithm. Empirically, approximations can be derived within a small amount of time and their sizes371 are significantly smaller than the ones of sufficient reasons.372
References373
[1] C. Ansótegui, M. L. Bonet, and J. Levy. SAT-based MaxSAT algorithms. Artificial Intelligence,374 196:77–105, 2013.375
[2] G. Audemard, J-M. Lagniez, and L. Simon. Improving glucose for incremental SAT solving376 with assumptions: Application to MUS extraction. In Proceedings of the 16th International377 Conference on Theory and Applications of Satisfiability Testing (SAT’13), pages 309–317, 2013.378
[3] A. T. Azar, H. I. Elshazly, A. E. Hassanien, and A. M. Elkorany. A random forest classifier for379 lymph diseases. Computer Methods and Programs in Biomedicine, 113(2):465–473, 2014.380
[4] Anton Belov and João Marques-Silva. Muser2: An efficient MUS extractor. J. Satisf. Boolean381 Model. Comput., 8(3/4):123–128, 2012.382
[5] C. Bénard, G. Biau, S. Da Veiga, and E. Scornet. Interpretable random forests via rule extraction.383 In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics,384 AISTATS’21, pages 937–945, 2021.385
[6] G. Biau. Analysis of a random forests model. Journal of Machine Learning Research, 13:1063–386 1095, 2012.387
[7] A. Bogomolov, B. Lepri, J. Staiano, N. Oliver, F. Pianesi, and A. Pentland. Once upon a crime:388 Towards crime prediction from demographics and mobile data. In Proceedings of the 16th389 International Conference on Multimodal Interaction, ICMI’14, pages 427–434. ACM, 2014.390
[8] L. Breiman. Random forests. Machine Learning, 45(1):5–32, 2001.391 [9] X. Chen and H. Ishwaran. Random forests for genomic data analysis. Genomics, 99(6):323–329,392 2012.393 [10] A. Choi, A. Shih, A. Goyanka, and A. Darwiche. On symbolically encoding the behavior394 of random forests. In Proceedings of the 3rd Workshop on Formal Methods for ML-Enabled395 Autonomous Systems (FoMLAS), 2020.396
[11] A. Criminisi and J. Shotton. Decision Forests for Computer Vision and Medical Image Analysis.397 Advances in Computer Vision and Pattern Recognition. Springer, 2013.398
[12] R. Cutler, C. E. Jr. Thomas, K. H. Beard, A. Cutler, K. T. Hess, J. Gibson, and J. J. Lawler.399 Random forests for classification in ecology. Ecology, 88(11):2783–2792, 2007.400
[13] A. Darwiche and A. Hirth. On the reasons behind decisions. In Proceedings of the 24th401 European Conference on Artificial Intelligence (ECAI’20), pages 712–720, 2020.402
[14] A. Ignatiev, A. Morgado, and J. Marques-Silva. PySAT: A python toolkit for prototyping with403 SAT oracles. In Proceedings of the 21st International Conference on Theory and Applications404 of Satisfiability Testing (SAT’2018), pages 428–437, 2018.405
[15] A. Ignatiev, N. Narodytska, and J. Marques-Silva. Abduction-based explanations for ma-406 chine learning models. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence407 (AAAI’19), pages 1511–1519, 2019.408
[16] A. Ignatiev, A. Previti, M. Liffiton, and J. Marques-Silva. Smallest MUS extraction with minimal409 hitting set dualization. In Proceedings of the 21st International Conference on Principles and410 Practice of Constraint Programming (CP’15), pages 173–182, 2015.411
[17] Y. Izza, A. Ignatiev, and J. Marques-Silva. On explaining decision trees. CoRR, abs/2010.11034,412 2020.413
[18] Y. Izza and J. Marques-Silva. On explaining random forests with SAT. In Proceedings of the414 30th International Joint Conference on Artificial Intelligence (IJCAI’21), page to appear, 2021.415
[19] M. Liffiton, A. Previti, A. Malik, and J. Marques-Silva. Fast, flexible MUS enumeration.416 Constraints An Int. J., 21(2):223–250, 2016.417
[20] J. Marques-Silva, M. Janota, and C. Mencía. Minimal sets on propositional formulae. Problems418 and reductions. Artificial Intelligence, 252:22–50, 2017.419
[21] T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial420 Intelligence, 267:1–38, 2019.421
[22] Ch. Molnar. Interpretable Machine Learning - A Guide for Making Black Box Models Explain-422 able. Leanpub, 2019.423
[23] A. Morgado, A. Ignatiev, and J. Marques-Silva. MSCG: robust core-guided MaxSAT solving. J.424 Satisf. Boolean Model. Comput., 9(1):129–134, 2014.425
[24] N. Narodytska and F. Bacchus. Maximum satisfiability using core-guided MaxSAT resolution.426 In Proceedings of the 28th AAAI Conference on Artificial Intelligence, pages 2717–2723, 2014.427
[25] N. Narodytska, A. Shrotri, K. Meel, A. Ignatiev, and J. Marques-Silva. Assessing heuristic428 machine learning explanations with model counting. In Proceedings of 22nd International429 Conference on the Theory and Applications of Satisfiability Testing (SAT’19), pages 267–278,430 2019.431
[26] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,432 P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher,433 M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine434 Learning Research, 12:2825–2830, 2011.435
[27] M. T. Ribeiro, S. Singh, and C. Guestrin. "why should I trust you?": Explaining the predictions436 of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on437 Knowledge Discovery and Data Mining, pages 1135–1144. ACM, 2016.438
[28] P. Saikko, J. Berg, and M. Järvisalo. LMHS: A SAT-IP hybrid MaxSAT solver. In Proceedings of439 the 19th International Conference of Theory and Applications of Satisfiability Testing (SAT’16),440 pages 539–546, 2016.441
[29] A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining bayesian network442 classifiers. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial443 Intelligence (IJCAI’18), pages 5103–5111, 2018.444
Checklist445
1. For all authors...446 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s447 contributions and scope? [Yes]448 (b) Did you describe the limitations of your work? [Yes]449 (c) Did you discuss any potential negative societal impacts of your work? [No] One cannot450 expect any negative impact (the paper is about explaining predictions).451 (d) Have you read the ethics review guidelines and ensured that your paper conforms to452 them? [Yes]453 2. If you are including theoretical results...454
(a) Did you state the full set of assumptions of all theoretical results? [Yes]455 (b) Did you include complete proofs of all theoretical results? [Yes] As a supplementary456 material.457 3. If you ran experiments...458
(a) Did you include the code, data, and instructions needed to reproduce the main experi-459 mental results (either in the supplemental material or as a URL)? [Yes]460
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they461 were chosen)? [Yes]462
(c) Did you report error bars (e.g., with respect to the random seed after running experi-463 ments multiple times)? [No] But the results we obtained have been averaged over a464 number of trials.465
(d) Did you include the total amount of compute and the type of resources used (e.g., type466 of GPUs, internal cluster, or cloud provider)? [Yes]467
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...468 (a) If your work uses existing assets, did you cite the creators? [Yes]469 (b) Did you mention the license of the assets? [Yes]470 (c) Did you include any new assets either in the supplemental material or as a URL? [Yes]471 The pieces of software we used are furnished as a supplementary material.472 (d) Did you discuss whether and how consent was obtained from people whose data you’re473 using/curating? [No] This issue is irrelevant for this paper.474 (e) Did you discuss whether the data you are using/curating contains personally identifiable475 information or offensive content? [No] The datasets we used are anonymized and do476 not contain personally identifiable information or offensive content.477
5. If you used crowdsourcing or conducted research with human subjects...478 (a) Did you include the full text of instructions given to participants and screenshots, if479 applicable? [No] We did not use crowdsourcing or conducted research with human480 subjects.481
(b) Did you describe any potential participant risks, with links to Institutional Review482 Board (IRB) approvals, if applicable? [No] We did not use crowdsourcing or conducted483 research with human subjects.484
(c) Did you include the estimated hourly wage paid to participants and the total amount485 spent on participant compensation? [No] We did not use crowdsourcing or conducted486 research with human subjects.487

Review summaries:
This work aims at providing a way of deriving explanations/reasons (in terms of features) from Boolean random forest (i.e., performing binary classification). They present three kinds of explanations (and the “minimal” variant for two of them): a direct reason is the most obvious one and directly comes from the interpretation of a single decision tree, a sufficient reason is one that is common to all trees, and a majority reason that is one related to the majority vote prediction and is appropriated for random forest models. Computational complexity is discussed for all approaches. 

This paper is devoted to computing abductive explanations for random forest (RF) machine learning (ML) models. Concretely, the paper proposes a variant of such explanations called majoritary reasons and argues that this new kind of explanation is not only easier to compute than computing sufficient reasons (both from the theoretical and practical points of view) but also that in practice they may be advantageous to a user due to their often smaller size than that of sufficient reasons. For that, an encoding and a MaxSAT-based solution for computing majoritary reasons for RF models is proposed.