Trading Complexity for Sparsity in Random Forest Explanations
Authors: Gilles AUDEMARD
Steve Bellart
Louenas Bounia
Frederic M Koriche
Jean-Marie Lagniez
Pierre Marquis
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Interpretability
Random Forests
Combinatorial Optimization

Abstract: Random forests have long been considered as powerful model ensembles in statistical machine learning.  By training multiple decision trees, whose diversity is fostered through bagging and subspace sampling, the resulting random forest can lead to more stable and reliable predictions than a single decision tree. This however comes at the cost of decreased interpretability: although decision trees are often easily interpretable, the predictions made by random forests are much more difficult to understand, as they involve a majority vote among hundreds of decision trees. In this paper, we examine different types of reasons that explain ``why'' an input instance is classified as positive or negative by a Boolean random forest. Notably, as an approximation of sufficient reasons (that take the form of prime implicants of the random forest), we introduce majority reasons which are prime implicants of a strict majority of decision trees. For these different abductive explanations, the tractability of the generation problem (finding one reason) and the minimization problem (finding one shortest reason) are investigated. Experiments conducted on various datasets reveal the existence of a trade-off between runtime complexity and sparsity. In a nutshell, sufficient reasons - for which the identification problem has been proved recently as DP-complete - are slightly shorter than majority reasons that can be generated using a simple polynomial-time greedy algorithm; minimal majority reasons - for which the identification problem is shown NP-complete - are significantly shorter than sufficient reasons and they can be computed using a partial MaxSAT algorithm that turns out to be quite efficient in practice. 

Trading Complexity for Sparsity in Random Forest Explanations
Anonymous Author(s)
Affiliation
Address
email
Abstract
Random forests have long been considered powerful model ensembles in ma- chine learning. By training multiple decision trees, whose diversity is fostered through data and feature subsampling, the resulting random forest lead more stable and reliable predictions than single decision tree. This however comes at the cost of decreased interpretability: while decision trees often easily interpretable, the predictions made by random forests are much more difficult to understand, they involve majority vote over hundreds of decision trees. In this paper, we examine different types of reasons that explain "why" an input instance classified positive or negative by Boolean random forest. Notably, as an alternative to sufficient reasons taking the form of prime implicants of the random forest, we introduce majoritary reasons which are prime implicants of a strict majority of decision trees. For these different abductive explanations, the tractability the generation problem (finding one reason) and the minimization problem (finding one shortest reason) are investigated. Experiments conducted on various datasets reveal the existence sparsity. Sufficient reasons for which the identification problem is DP-complete are slightly larger than majoritary reasons that can be generated using simple linear-time greedy algorithm, and significantly larger than minimal majoritary reasons that can be approached using an anytime PARTIAL MAXSAT algorithm.
2
4
6
8
10
11
12
13
14
15
trade-off between runtime complexity and
17
18
19
Introduction
20
21
Over the past two decades, rapid progress statistical machine learning has led to the deployment of models endowed with remarkable predictive capabilities. Yet, the spectrum of applications
23 using statistical learning models becomes increasingly large, explanations for why a model is making certain predictions
more critical. For example, in medical diagnosis, if some model predicts 25 that an image is malignant, then the doctor may need to know which features the image have led to this classification. Similarly, in the banking sector, if some model predicts that a customer is fraud, 27 then the banker might want to know why. Therefore, having explanations for why certain predictions made is essential for securing user confidence in machine learning technologies [21, 22].
29 This paper focuses on classifications made by random forests, a popular ensemble learning method that constructs multiple randomized decision trees during the training phase, and predicts by taking
31 majority vote over the base classifiers [8]. Since decision tree randomization is achieved by essentially coupling data subsampling (or bagging) and feature subsampling, random forests are fast and easy to
33 implement, with few tuning parameters. Furthermore, they often make accurate and robust predictions in practice, even for small data samples and high nigh-dimmnsional feature spaces [6]. For these reasons,
35 random forests have been used in various applications including, among others, computer vision [11], crime prediction [7], ecology [12], genomics [9], and medical diagnosis [3].
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 Despite their success, random forests are much less interpretable than decision trees. Indeed, the
38 prediction made by a decision tree on given data instance can be easily interpreted by reading the
39 unique root-to-leaf path that covers the instance. Contrastingly, there is no such direct reason in random forest, since the prediction derived from a majority vote over multiple decision trees. So, a key issue in random forests is to infer abductive explanations, that is, to explain in concise terms why years [5. 10, 18). Notably, in the classification setting, [10, 18] have focused on sufficien! reasons, which are abductive explanations involving only relevant features [13]. More specifically, if we view any random forest classifier as a Boolean function f. then a sufficient reason for classifying a data instance æ positive by f is a prime implicant t of f covering X. By construction, removing any feature from a sufficient reason & would question the fact that t explains the way æ is classified by f. Interestingly, if f is described by single decision tree, then generating sufficient reason for any input instance æ can be done in linear time. Yet, in the general case where f is represented by an arbitrary number of decision trees, the problem of identifying sufficient reason is -omompeete. Despite this intractability statement, the empirical results reported in [18] show that a MUS- based algorithm for computing sufficient reasons proves quite efficient in practice.
40
41
42 a data instance is classified as positive or negative by the model ensemble.
43
Related Work. Explaining random forest predictions has received increasing attention in recent
44
45
46
47
48
49
50
51
52
53
54 In addition to baaeed- explanations investigated in [10, 18], "model-agnostic" explanations can be applied to random forests. Notably, the LIME method [27] extrapolates a linear threshold function g from the behavior of the random forest I around an input instance x. Yet, even if prime implicant of the linear threshold function can be easily computed, this explanation is not guaranteed abductive since g is only an approximation of f.
55
56
58
Contributions. In this paper, we introduce several new notions of abductive explanations: direct reasons extend the case of random forests the corresponding notion defined primarily for decision trees, and majority reasons are weak forms of abductive explanations which take into account the averaging rule of random forests. Informally, a majoritary reason for classifying a instance æ as positive by some random forest f is a prime implicant of majority of decision trees in f that covers x. Thus, any sufficient reason is a majoritary reason, but the converse is not true. For these different reasons, we examine the tractability of both the generation (finding one explanation) and the minimization (finding one shortest explanation) problems. To the best of our knowledge, all complexity results related to random forest explanations are new, if make an exception for the intractability of generating sufficient reasons, which was recently established in [18]. Notably, direct reasons and majoritary reasons can be derived in time polynomial in the size of the input (the instance and the random forest used to classify it). By contrast, the identification of minimal majoritary reasons is NP-complete, and the identification of minimal sufficient reasons is Elp-compett.
60
61
62
64
66
68
69
70
71
72 Based on these results, we provide algorithms for deriving random forest explanations, which open the
73 way for an empirical comparison. Our experiments made on standard benchmarks show the existence
74 of a trade-off between the runtime complexity of finding (possibly minimal) abductive explanations and the sparsity of such explanations. In nutshell, majoritary reasons and minimal majoritary
76 reasons offer interesting compromises in comparison to, respectively, sufficient reasons and minimal sufficient reasons. Indeed, the size of majoritary reasons and the computational effort required to
78 generate them are generally smaller than those obtained for sufficient reasons. Furthermore, minimal
79 majoritary reasons outperform minimal sufficient reasons, since the latter too computationally demanding. In fact, using an anytime PARTIAL MAXSAT AT solver for minimizing majoritary reasons, we derive sparse explanations which are typically much shorter than all other forms of abductive explanations. Proofs and additional empirical results are provided as supplementary material.
80
81
82
Preliminaries
83
84 For an integer n, let [n] = (1.....n) By Fr we denote the class of all Boolean functions from (0, 1)" to {0, 1), and we use X, [=1,... , In } to denote the set of input Boolean variables. Any 86 Boolean vector & E f0,13" is called an instance. For any function f E F,, an instance x E {0, 1)"
87 is called positive example of / if fxx) = and negative example otherwise.
88 We refer to f as a propositional formula when described using the Boolean connectives A
89 (conjunction), V (disjunction) and (negation), together with the constants 1 (truc) and 0 (false). As
2

---

Ti
34
T2
J2
Ts
33
x22
333
24
FF
Figure 1: A random forest F (T,, T2, Ta for recognizing Cattleya orchids. The left (resp. right) child of any decision node labelled by corresponds to the assignment of 0 (resp. 1).
90 usual, a literal 4 is a variable r; or its negation -r,, also denoted T, A term (or monomial) is a conjunction of literals, and clause is disjunction of literals. A DNF formula is disjunction of 92 terms and CNF formula a conjunction clauses. The set of variables occurring in a formula is denoted (fr(f). In the rest of the paper, shall often treat instances terms, and terms as sets of literals. Given an assignment z E f0, 1]", the corresponding term defined as
94
12
^ at where x. and xt 24 i=1
95
term covers an assignment z if C tg. An implicant of Boolean function f is a term that implies f. that is, term such that f(z) = 1 for every assignment covered by A prime implicant of f is an implicant t of f such that no proper subset t an implicant of f-
97
98
With these basic notions in hand, (Boolean) decision tree on X,, is a binary tree T, each of whose internal nodes is labeled with one of n input variables, and whose leaves are labeled O or Every variable is supposed (w.l.o.g.) to occur at most once on any root-to-leaf path (read-once property). The value T(x) E (0, 1} of T on an input instance æ given by the label the leaf reached from the root follows: at each node go to the left or right child depending whether the input value of or 1, respectively. A (Boolean) random forest on X,, an ensemble
39
101
102
103
the corresponding variable
F
.T,,.... Jm where each T; (i E [m]] is a decision tree Xn. and such that the value F(x) [0,1] on an input instance æ is given by
105
[1
EE T((x>
F(x)
m
0
otherwise.
108
The size of F is given by |F
i= [T). where [T]] is the number of nodes occurring in T, The class of decision trees on X, is denoted DT,,, and the class of random forests with most m decision trees (with m 2 1) over DT, is denoted RF RF,,m RF,, is the union of all RF for m E N.
Σ m72
107
108
109
Example 1. The random forest F = (Ti, Ta} in Figure is composed of three decision trees. separates Cattleya orchids from other orchids using the following features: Ix: "has fragrans flowers", 22: "has one two leaves". Tz: "has large flowers". and FA: "is sympodial".
110
112
is well-known that any decision tree T can be transformed into its negation -T E DT,, by simply reverting the label of leaves. Negating a random forest can also be achieved in polynomial time: Proposition 1. There exists a linear-time algorithm that computes random forest -F E RF equivalent to the negation of a given random forest F E RF n.
113
115
116
Another important property of decision trees is that any T E DT, can be transformed in linear time into equivalent disjunction of terms DTF(T). where each term coincides with 1 1-path (i.e., path from the root to a leaf labeled with 1), or a conjunction clauses CNF(T), where each clause the negation of term describing O-path. When switching random forests, the picture is quite different: Proposition Any CNF or DNF formula can converted in linear time into an equivalent random forest, but there is no polynomial-sper space translation from RE CNE to DNE.
118
120

---

122
3
Random Forest Explanations
123
The key focus of this study is to explain why a given (Boolean) random forest classifies some incoming data instance as positive or negative. This calls for notion of abductive explanation'. Formally, given a Boolean function f E Fn and an instance a E {0. 1)", an abductive explanation for æ given is implicant of (resp. -f) if f(x) = 1 (resp. f(x) 0) that covers An abductive explanation I. for æ given f always exists, since I = l is such a (trivial) explanation. So, in the rest of this section, we shall mainly concentrate sparse forms of abductive explanations.
125
126
127
128
129
Before delving into details, it is worth mentioning that if f is represented by a random forest then, without loss of generality, we can focus the case where æ is positive example of f. because -f can be computed in linear time (by Proposition 1). Nevertheless, for the sake of clarity, we shall consider both cases f() = 1 and f(x) = 0 in our definitions.
131
133
3.1
Direct Reasons
134
For decision tree T E DT, and a data instance æ E {0, 1)"h the direct reason of given T the term tu corresponding to the unique root-to-leaf path of I"' that covers x. We can extend this simple form of abductive explanation to random forests follows:
135
136
137
Definition 1. Let F .- mm. be a random forest in RF n,m. and a: 10, be an instance.
Then, the direct reason for x given F is the term t defined by
138
(NSERAEE 2 (NTEFT ET if
FF(() =
By construction, 1o is an abductive explanation which can be computed in O(F')) time.
139
1,,1 is recognized as a Cattleya 141 orchid, since F(x) = 1. The direct reason for x given F is t = 81 A x2 A az A ag. It coincides with zz. Consider now the instance x' (0, 0. 0): it is not recognized
Example 2. Considering Example 1 again, the instance
Cattleya orchid, since F(x)= = 0. The direct reason for x' given F is to 22 ATg A34. It is a better abductive explanation
143
than t itself since it does not contain 11, which is locally irrelevant.
3.2
Sufficient Reasons
146
Another valuable notion of abductive explanation is the one of sufficient reason?. defined for any Boolean classifier [13]. In the setting of random forests, such explanations can be defined as follows:
147
148
{0, 13" be an instance. A sufficient reason for x given F is a prime implicant of F (resp. -F) if F F(x) = (resp. F(x) = 0) that covers æ. Example 3. For our running example, In A D2 A I4 and x3 A I4 are the sufficient reasons for æ given F. F. and T1 A Z2 A I' are the sufficient reasons for x' given F.
Definition 2. Let F RF, be a random forest and
149
150
152
Unlike arbitrary abductive explanations, all features occurring in a sufficient reason i are relevant. Indeed, removing any literal from i would question the fact that / implies F. To this point, the direct reason d for Φ given F may contain arbitrarily many more features than a sufficient reason for æ given F. since this was already shown in the case where F consists in a single decision tree [17].
153
154
155
156
The problem of finding a sufficient reason t for an input instance æ E {0, 13" with respect to a given random forest F RF,,, has recently been shown DP-complete [18]. In fact, even the apparently simple task of checking whether is an implicant of F is already hard:
158
159
Proposition 3. Let F be a random forest in RF, and be term over X,. Then, deciding whether t an implicant of F is coNP-complets
161
The above result is in stark contrast with the computational complexity of checking whether a term t is an implicant of decision tree T. This task can be solved in polynomial time, using the fact that
162
Unlike [15], we not require those explanations to minimal w.r.t. set inclusion, order keep the concept distinct (and actually more general) then the one of sufficient reasons.
SStfficient reasons also known prime-implicant explanations [29].

---

163 T can be converted (in linear time) into its clausal form CTF(T"), together with the fact that testing whether t implies CT) can done in ((T)) time. That mentioned, in the case of random forests, the implicant test can be achieved via a call to a SAT oracle:
184
165
186
Proposition 4. Let F = {Ti...., ...). be a random forest of n and t be a (satisfiable) term over Xn. Let H be the CNE formula
m
Vo) E CNF(-T:)) CNF
Σ
m 2
Ui
TO is a CNF encoding of the cardinality where (yi,..., ym) are fresh variables and CNF (Eih Vi 2 T Then, is an implicunt of F if and only if H A L is unsatisfiable.
188
169
contraint -x=1 y/ > m.
170
Based on such an encoding, the sufficient reasons for an instance a given random forest F can be characterized in terms of MUS (minimal unsatisfiable subsets), as suggested in [18]. This characterization is useful because many S SAT-based algorithms for computing a MUS (or even all MUSes) of a CNF formula have been pointed out for the past decade [2, 19, 20], and hence, one can take advantage of them for computing sufficient reasons.
171
172
175
174
175
Going one step further, natural way for improving the clarity of sufficient reasons is to focus on those of minimal size. Specifically, given F E RF, and æ E {0, 13", a minimal sufficient reason for with respect to F' a sufficient reason for x given F of minimal size.?
178
177
178
Example 4. For our running example, va A IA is the unique minimal sufficient reason for x given F, and F& is the unique minimal reason for x! given F.
179
180
As a by-product of the characterization of a sufficient reason in terms of MUS [18], minimal sufficient reason for a given f can be viewed as minimal MUS. Thus, we can exploit algorithms for computing minimal MUSes (see e.g., [16]) in order to derive minimal sufficient reasons. However, deriving a minimal sufficient reason computationally harder than deriving a sufficient reason:
181
182
183
Proposition 5. Let F E RF,, E 10, and k N. Then, deciding whether there exists minimal sufficient reason t for x given F containing at most l features is 22 clycooppet
185
186
3.3
Majoritary Reasons
187
Based on the above considerations, a natural question arises: does there exist a middle ground between direct reasons, which main contain many irrelevant features but are easy calculate, and sufficient reasons, which only contain relevant features but are potentially much harder to generate? Inspired by the way prime implicants can be computed when dealing with decision trees, we can reply in the affirmative using the notion of majoritary reasons, defined as follows.
188
189
190
191
192
Definition 3. Let F = (Ti...., Tm be a random forest in RF n.m and x E {0, 13"h be an instance. Then, a majoritary reason for æ given F is a term 1. covering æ, such that I is an implicant of at least +1 decision trees T; (resp. -T,) if F(x) = (resp. F(x) = 0), for every I E 1, t. (1) does not satisfy this last condition.
194
2
195
196
Example 5. For our running example, x has three majoritary reasons given F: I1 A D2 A xn.
197 In F3 A FA, and xz A 3z A I... Those reasons are better than 1. in the sense that they are shorter than this direct reason. Contrastingly, x' has four majoritary reasons given F: Ty A Fa. Z2 A Tg. I3 A Fs. and In A D2 A Ez. Each of the two majoritary reasons D2 A Fa. I3 FA show that t contains some irrelevant literals for the task of classifying x' using F.
198
199
200
In general, the notions of majoritary reasons and of sufficient reasons do not coincide. Indeed, sufficient reason is prime implicant (covering x) of the forest F, while a majoritary reason t' is an implicant (covering x) of strict majority of decision trees in the forest F satisfying the additional condition that t' is a prime implicant of at least one of these decision trees. Viewing majoritary reasons as "weak" forms of sufficient reasons, they can include irrelevant features:
202
204
205
208
Proposition 6. Let F = (Ti....,, Tm. be random forest of RF and x E {0,1)" such that F(z) 1. Unless m 3, it can be the case that every majoritary reason for x given F contains arbitrarity many more features than any sufficient reason for given F.
207
208
Minimal sufficient reasons should not to be confused with minimum cardinallla explanations [29], where the minimality condition bears on the features set I in the data instance x.
5

---

209
What makes majoritary reasons valuable is that they are abductive and can be generated in linear time. The evidence that any majoritary reason & for æ given F' is an abductive explanation for a given F comes directly from the fact that if i. implies majority of decision trees in F, then it is an implicant of F (note that the converse implication does not hold in general).
210
212
213
The tractability of generating majoritary reasons lies in the fact that they can be found using simple greedy algorithm. For the case where F(x)) 1, start with t.. and iterate over the literals of t by checking whether deprived of / is an implicant of at least [ + 1 decision trees of F. If so, remove from and proceed to the next literal. Once all literals in tw have been examined, the final term& f is by construction an implicant of a strict majority of decision trees in F, such that removing any literal from it would lead to term that is no longer an implicant of this majority. So, is by construction a majoritary reason. The case where F(x) = O is similar, by simply replacing each T; with its negation in F. This greedy algorithm runs in Onn) Fl) time, using the fact that, on each iteration, checking whether / is an implicant of Ti (for each i E [m]) can be done in ((T:i) time.
214
215
216
217
218
219
220
222
By analogy with minimal sufficient reasons, natural way of improving the quality of majoritary reasons is to seek for shortest ones. Let F E RF, be a random forest and x E {0, 1 be an instance. Then, minimal majoritary reason for given I' a minimal-size majoritary reason for x given F.
223
224
Example 6. For our running example, the three majoritary reasons for given F' are its minimal majoritary reasons. Contrastingly, among the majoritary reasons for x' given F, only T1 A Ea.
226
D2 Fs, and T3 A TA are minimal majoritary reasons.
228
Unsurprisingly, the optimization task for majoritary reasons is more demanding than the generation task. Yet, minimal majoritary reasons are easier to find than minimal sufficient reasons. Specifically:
229
230
Proposition 7. Let F E RF,, a E (0, 13", and k E N. Then, deciding whether there exists minimal majoritary reason foror a given F containing at most i features is co-copllete.
231
A common approach for handling NP-optimization problems is to rely on modern constraint solvers. From this perspective, recall that a PARTIAL MAXSAT problem consists of a pair (Ceont Chara) where Czoft and Chard are (finite) sets of clauses. The goal is to find a Boolean assignment that maximizes the number of clauses c in Csolt that are satisfied, while satisfying all clauses in Chard-
233
235
236
Proposition 8. Let F E Rmnm and x E {0,1}" be an instance such that F(x) = Let (Coff Cnara) be an instance of the PARTIAL MAXSAT problem such that:
237
Cscft = =tTe: : I4 E t U {ax : T. E t
m
Chard = {(T, V Vox): : [m],cc E CTF( U CNF
Σ
y
>
m
2
where Gl = cn tu is the restriction of c to the literals in twp. (11..... Ym are fresh variables and 238
239
CNF E Vi > my is a CNF encoding of the contraint Ex= yi > 2. The intersection of ta with
m.
240
1 where z" is an optimal solution of (Cooft; Chard), is a minimal majoritary reason for x given F.
241
Clearly, in the case where F(x)) = 0, it is enough to consider the same instance of PARTIAL MAXSAT as above, except that Chard (v. V (()) E [m], c CNF(-T.) U ( T2 y1 )
242
243
Thanks to this characterization result, one can leverage the numerous algorithms that have been developed so far for PARTIAL MAXSAT (see e.g. [1. 23, 24, 28]) in order to compute minimal majoritary reasons. We took advantage of it to achieve some of the experiments reported in Section 4.
245
Experiments
246
247
Empirical setting. The empirical protocol was as follows. We have considered 15 datasets, which are standard benchmarks from the well-known repositories Kaggle (www. www.kaaglee.omm) OpenML www.oppnnml.org. and UCI wrrchiveics.uci.edu/mi
248
249
These datasets are compas, placement, recidivism, adult, ad data, mnist38, mmist49, gisette, dexter, dorothea, farm-ads, higgs boson, christine, gina, and bank. mnist38 and mnis149 are subsets of the mnist dataset, restricted to the instances of 3 and 8 (resp. 4 and 9) digits. Due to space constraints, additional information about the datasets (especially the numbers and types of features, the number of instances), and about the random forests that have been trained (especially, the number of Boolean features used, the number
250
251
253

---

255
of trees, the depth of the trees, the mean accuracy) are reported as supplementary material. We used only datasets for binary classification, which is a very common kind of dataset. Categorical features have been treated as arbitrary numbers (the scale is nominal). As to numeric features, no data
256
257
258
preprocessing has taken place: these features have been binarized on-the-fly by the random forest
259
learning algorithm that has been used.
260
For every benchmark b, a 10-fold cross validation process has been achieved. Namely, set of 10 random forest F. have been computed and evaluated from the labelled instances of b, partitioned into 10 parts. One part was used as the test set and the remaining parts as the training set for generating random forest. The classification performance for b was measured as the mean accuracy obtained over the 10 random forests generated from b. As to the random forest learner, we have used the implementation provided by the Scikit-Learn [26] library in his version 0.23.2. The maximal of the learning algorithm have been set to their default value except the number of trees. We made some preliminary tests for tuning this parameter in order to ensure that the accuracy good enough. For
281
262
263
264
285
266
depth of any decision tree a forest has been bounded at All other hyper-parameter
267
268
each benchmark 6, each random forest F, and a subset of 25 instances æ picked up at random in the corresponding test set (leading to 250 instances per dataset) we have run the algorithms described in Section 3 for deriving the direct reason for æ given F. a sufficient reason for æ given F, majoritary reason 2 given F, a minimal majoritary reason for x given F, and a minimal sufficient reason for æ given F.
270
272
273
274
For computing sufficient reasons and minimal majoritary reasons, we took advantage of the Pysat library [14] (version 0. (.6.ev115) 15) which provides the implementation of the RC2 PARTIAL MAXS AT solver and an interface to MUSER [4]. When deriving majoritary reasons, we picked up uniformly at random 50 permutations of the literals describing the instance and tried to eliminate those literals (within the greedy algorithm) following the ordering corresponding to the permutation. As a majori- tary reason for the instance, we kept smallest reason among those that have been derived (of course, the corresponding computation time that has been measured is the cumulated time over the 50 tries). Sufficient reasons have been computed as MUSes, as explained before.
275
276
277
278
280
We also derived a "LIME explanation" for each instance. Such an explanation has been generated thanks to the following approach. For any a under consideration, one first used LIME [27] to generate an associated linear model wr where wa E RR. This linear model W classifies any instance x'' as a positive instance if and only if wr xx' > 0. Furthermore, Wa classifies the instance to be explained æ the same way as the black box model considered at start (in our case, the random forest F). We ran the LIME implementation linked to [27] in its latest version. Interestingly, a minimal sufficient reason t for æ given w,, can be generated in polynomial time from wa. We call it a LIME explanation for æ. The computation of is as follows. If x is classified positively by Wa. in order to derive I, it is enough 290 to sum in a decreasing way the positive weights w, occurring in ww until this sum exceeds the sum of the opposites of all the negative weights occurring in Ww. The term composed of the variables x; corresponding to the positive weights that have been selected is by construction a minimal sufficient reason for æ given w since for every x' covered by f, the inequation W x necessarily holds; indeed, it holds in the worst situation where all the variables associated with a positive weight in wa and not belonging to t are set to 0, whilst all the variables associated with negative weight in w. are set to 1. Similarly, if x is classified negatively by wa, in order to derive f, it is enough to sum in an increasing way the negative weights w; occurring in ww until this sum is lower than or equal to the opposite of the sum of all the posítive weights occurring in wa. This time, the term I composed the negative weights that have been selected is by construction minimal sufficient reason for æ given wz.
282
283
284
285
286
286
292
294
296
297
298
299
of the variables x; corresponding
300
All the experiments have been conducted
computer equipped with Intel(R) XEON E5-2637 CPU
@ 3.5 GHz and 128 Gib of memory. A time-out (TO) of 600s has been considered for each instance 302
303
and each type of explanation, except LIME explanations.
304
A first conclusion that can be drawn from our experiments is the intractability of computing in practice minimal sufficient reasons (this is not surprising, since this coheres with the complexity result given by Proposition 5). Indeed, we have been able to compute within the time limit of 600s a minimal reason for only 10 instances and a single dataset (compas).
Results.
306
307
308
Due to space limitations, we report hereafter empirical results about two datasets only, namely placeeent and gisette (the results obtained on the other datasets are similar and available as
7

---

Sufticent
45
Direct
Haur
mujor
that the direct reason can be quite large, that the computation of LIME explanations is usually more expensive than the ones of the other explanations, and that LIME explanations can be very short (but Stee 1eeen7
20-
10-
10
10
10
10
307
time
majentary
Sulfiient
Mojuntary
1.2
44
40
40
1.5
122
28-
2--
1.4
520
Sizn minimall
Figure 2: Empirical results for the placement dataset.
supplementary material). The placement data set about the placement of students in campus. consists of 215 labelled instances. Students are described using 13 features, related to their curricula, the type and work experience and the salary. An instance is labelled positive when the student gets job. The random forest that has been generated consists of 25 trees, and its mean accuracy 97.6%. gisette is much larger dataset, based on 5000 features and containing 7000 labelled instances. Features correspond to pixels. The problem is to separate the highly confusible digits and 9. An instance is labelled as positive whenever the picture represents has been generated consists of 85 trees, and its mean accuracy is 96%.
311
313
315
316
The random forest that
317
Figure 2 provides the results obtained for placement, using four plots. Each dot represents instance. The first plot shows the time needed to compute a reason on the x-axis, and the size of this reason on the y-axis. On this plot, no dot corresponds did not terminate before the time-out. The plot also highlights that all the other reasons have been computed within the time limit, and in general using small amount of time. In particular, it shows
319
minimal sufficient reason because their computation
321
322
323
324
325
one must keep in mind that they are not abductive explanations in general"). ) A box plot about the sizes of all the explanations is reported (the LIME ones and the direct reasons are not presented for the sake of readibility). The figure also provides two scatter plots, aiming to compare the size of majoritary reasons with the size of sufficient reasons, as well as the size of the minimal majoritary reasons with the size of sufficient reasons. These plots clearly show the benefits that can be offered by considering majoritary reasons and minimal majoritary reasons instead of sufficient reasons.
326
327
328
330
331
Figure synthesizes the results obtained for gisette, using four plots again. Three of them are of the same kind as the plots used for placement. Conclusions similar those drawn for placement can be derived for gisette, with some exceptions. First of all, this time, no dot corresponds to a minimal majoritary reason because their computation did terminate before the time-out. Furthermore,
332
333
334
335
LIME explanations are very long here. This can be explained by the fact that the computation achieved by LIME relies on a binary representation of the instance that is quite different (and possibly much larger) than the one considered in the representation of the random forest. Indeed, each decision tree the forest focuses only on subset of most important features the sense of Gini criterion) found during the learning phase. In our experiments, the size of LIME explanations was typically high for datasets based on many features.
336
337
338
340
'See also [25] that reports some experiments about ANCHOR (the successor of LIME), assessing the quality of the explanations computed using ANCHOR.

---

Sultidunt Direct Majorfa
320
Se 198377
300
1300
500
10
10:
307
107
time
Sufficiont
Mayortory
6005
374
222
333
106
324
303
229
207
280
250
majorttry
(after 100
Figure Empirical results gisette dataset.
When minimal majoritary reasons hard to be computed (as it is the case for gisette), approach consists in approximating them. Interestingly, one can take advantage of an incremental PARTIAL MAXSAT ALGORITHM, like LMHS [28], to do the job. Specifically, the result given in Proposition 8 provides a way to derive abductive explanations for an instance xc given a random forest F in an anytime fashion. Basically, using LMHS, Boolean assignment satisfying all the hard constraints of hard and a given number, say k; of soft constraints from Czoft is looked for (k is set to at start). soft constraint,
342
344
346
347 If such an assignment is found, then looks for an assignment satisfying k and so on, until an optimal solution is found or a preset time bound is reached. In many cases, the most demanding step from computational standpoint is the one for which k: is the optimal value (but one ignores it) and one looks for an assignment that satisfies k + soft constraint (and such an assignment does not exist). By construction, every z that is generated that way such that te n tz is an implicant of F' that covers (and hence, an abductive explanation). The approximation = of minimal majoritary reason for given F. which is obtained when the time limit is met, can be significantly shorter than the sufficient reason for given F that has been derived. In our experiments,
348
349
350
351
352
353
354
355
we used three time limits: 10s, 60s, 600s. As the box plot and the dedicated scatter plot given in which are derived gently decrease with time. size savings that are achieved in comparison to sufficient reasons are significant, even for the smallest time bound of 10s that has been considered.
356
Figure 3 show it, the sizes of the approximations
357
Interestingly,
5
Conclusion
380
In this paper, we have introduced, analyzed and evaluated some new notions of abductive explanations suited to random forest classifiers, namely majoritary reasons and minimal majoritary reasons.
362
Our investigation reveals the existence of a trade-off between runtime complexity and sparsity for abductive explanations. Unlike sufficient reasons, majoritary reasons and minimal majoritary reasons
363
may contain irrelevant features. Despite this evidence, majoritary reasons and minimal majoritary reasons appear as valuable alternative sufficient reasons. Indeed, majoritary reasons can be computed in polynomial time while sufficient reasons cannot (unless P = NP). In addition, most of the time in our experiments, majoritary reasons appear as slightly smaller than sufficient reasons.
385
366
367
368
Minimal majoritary reasons can be looked for when majoritary reasons are too large, but this is at
369
cost of an extra computation time that can important, and even prohibitive in some cases. However, minimal majoritary reasons can be approximated using anytime PARTIAL MAXSAT
371
algorithm. Empirically, approximations can derived within small amount of time and their sizes are significantly smaller than the ones of sufficient reasons.

---

References
373
374
[1] C. Ansótegui, M. L. Bonet, and J. Levy. SAT-based MaxSAT algorithms. Artificial Intelligence, 196:77-105, 2013.
378
[2] G. Audemard, J-M. Lagniez, and L. Simon. Improving glucose for incremental SAT solving with assumptions: Application to MUS extraction. In Proceedings of the 16th International Conference on Theory and Applications of Satisfiability Testing (SAT" pages 309-317, 2013.
377
378
379
[3] A. T. Azar, H. I. Elshazly, A. E. Hassanien, and A. M. Elkorany. A random forest classifier for 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. Boolean
382
Model. Comput., 8(3/4):123-12 128, 2012.
383
[5] C. Bénard, G. Biau, S. Da Veiga, and E. Scornet. Interpretable random forests via rule extraction.
384
In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, AIS pages 937-945, 2021.
385
386
[6]
G. Biau. Analysis of a random forests model. Journal of Machine Learning Research, 13:1063-
387
1095, 2012.
388
[7] A. Bogomolov, B. Lepri, J. Staiano, N. Oliver, Pianesi, and A. Pentland. Once upon a crime: Towards crime prediction from demographies and mobile data. In Proceedings of the 16th International Conference on Multimodal Interaction, ICMI' 14, pages 427-434, ACM, 2014.
389
390
[8] L. Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
392
[9] X. Chen and H. Ishwaran. Random forests for genomic data analysis. Genomics, 99(6):323-329
393
2012.
[10] A. Choi, A. Shih, A. Goyanka, and A. Darwiche. On symbolically encoding the behavior of random forests. In Proceedings of the 3rd Workshop on Formal Methods for ML-Enabled Autonomous Systems (FoMLAS), 2020.
395
387
[11] A. Criminisi and J. Shotton. Decision Forests for Computer Vision and Medical Image Analysis. Advances in Computer Vision and Pattern Recognition. Springer, 2013.
398
389
[12] R. Cutler, C. E. Jr. Thomas, K. H. Beard, A. Cutler, K. T. Hess, J. Gibson, and J. J. Lawler. Random forests for classification in ecology. Ecology, 88(1 ()(11)))733279) 2007.
400
401
[13] A. Darwiche and A. Hirth. On the reasons behind decisions. In Proceedings of the 24th
402
European Conference on Artificial Intelligence (ECAI'20), pages 712-720, 2020.
403
[14] A. Ignatiev, A. Morgado, and J. Marques-Silva. PySAT: A python toolkit for prototyping with SAT oracles. In Proceedings of the 2/st International Conference on Theory and Applications of Satisfiability Testing 2018)) pages 428-437, 2018.
405
406
[15] A. Ignatiev, N. Narodytska, and J. Marques-Sile Silva. Abduction-based explanations for ma- chine learning models. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI'19), pages 15 19199,, 2019.
408
409
[16] A. Ignatiev, A. Previti, M. Liffiton, and Marques-Silva, Smallest MUS extraction with minimal hitting set dualization. In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming ( (CP'15), pages 173-182, 2015.
410
411
[17] Y. Izza, A. Ignatiev, and J. Barques-Silva. On explaining decision trees. CoRR, abs/2010.11034, 2020.
413
414
[18] Y. Izza and J. Marques-Silva. On explaining random forests with SAT, In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJAA'21), page to appear, 2021.
415
416
[19] M. Liffiton, A. Previti, A. Malik, and J. Marques-Silva. Fast, flexible MUS enumeration. Constraints An Int. J., 21(2):223-250 2016.
418
[20] J. Marques-Silva, M. Janota, and C. Mencía. Minimal sets on propositional formulae. Problems
419
and reductions. Artificial Intelligence, 252:22-50, 2017.
[21] T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence, 267:1-38, 2019.
421
422
[22] Ch. Molnar. Interpretable Machine Learning- Guide for Making Black Box Models Explain-
able. Leanpub, 2019.
10

---

424
[23] A. Morgado, A. Ignatiev, and J. Marques-Silva, MSCG: robust core-guided MaxSAT solving. J. Satisf. Boolean Model. Comput., 91):119--34, 2014.
425
[24] N. Narodytska and Bacchus. Maximum satisfiability using core-guided MaxSAT resolution.
427
In Proceedings of the 28th AAAI Conference on Artificial Intelligence, pages 2717-2723, 2014.
428
[25]
N. Narodytska, A. Shrotri, K. Meel, A. Ignatiev, and J. Marques-Silvv. Silva. Assessing heuristic machine learning explanations with model counting. In Proceedings of 22nd International Conference on the Theory and Applications of Satisfiability Testing (SAT'19), pages 267-278, 2019.
430
[26] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, 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.
435
435
438
[27] M. T. Ribeiro, Singh, and C. 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. ACM, 2016.
437
438
[28] P. Saikko, J. Berg, and M. Järvisalo. LMHS: A SAT-IP hybrid MaxSAT solver. In Proceedings of the 19th International Conference Theory and Applications of Satisfiability Testing (SAT" pages 539-546, 2016.
440
[29] A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining bayesian network classifiers. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI' 18), pages 5103-5111, 2018.
443

---

Checklist
445
446
1. For all authors...
447
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
448
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
450
(c) Did you discuss any potential negative societal impacts of your work? [No] One cannot 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 to 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]
456
(b) Did you include complete proof's of all theoretical results? [Yes] As a supplementary material.
457
458
3. If you ran experiments...
459
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
460
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
482
463
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] But the results we obtained have been averaged over number of trials.
464
485
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
467
468
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
470
(b) Did you mention the license of the assets? [Yes]
471
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
The pieces of software we used are furnished as supplementary material.
(d) Did you discuss whether and how consent
obtained from people whose data you're 're using/curating? [No] This issue is irrelevant for this paper.
474
475
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] The datasets we used are anonymized and do not contain personally identifiable information or offensive content.
476
477
478
5. If you used crowdsourcing or conducted research with human subjects...
479
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [No] We did not use crowdsoureing conducted research with human subjects.
481
482
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No] We did not use crowdsourcing or conducted research with human subjects.
483
484
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No] We did not use crowdsourcing or conducted research with human subjects.
486
12


Reviews:
[{"review_id": "graX3wBlXs", "reviewer": "Reviewer_N7A7", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall comment:\nThe paper is well-written, and tackles a very interesting topic. I believe it provides an interesting approach to better understand a random forest model. However, I think that a few tree-specific questions are not addressed in the paper, and the work could benefit from clarifications and more links with related works (in the sense, aiming at deriving explanations/reasons for instance from tree-based models). \n\nComments:\n- Proposed approaches is interesting and well presented. I believe the rational behind the majority reason is sound and original.\n- It is now well-known that hyper-parameters of random forest (in particular the “max_features” randomization parameter controlling the feature subsampling) strongly impacts the way trees of the forest are built and how (and which) features are used. Disregarding the bagging, trees without feature subsampling focus on the most important features (in terms of impurity decrease) while trees with maximal feature subsampling (split features are randomly selected) will use more irrelevant features but also be able to discover all relevant features (thus all explanations/reasons). Similar questions have been addressed regarding the maximal depth of trees that could impact the size of explanations/reasons (i.e., the maximal number of relevant features that are simultaneously used to make a prediction). I think this work could benefit from considering the impact of such hyperparameters on the identified reasons, or at least better justify the choices made in the experiments (e.g., \"why limiting the tree depth to 8?\" \"Why keeping default hyperparameter values?\")  \n-  As the notion of “(irr)relevance” has been widely used in tree-based feature importance (i.e., associating each feature to an importance score) works, I think it could be useful to define the notion of relevance (or irrelevance) to clarify what is actually used here. \n- I think many links could be done with tree-based (local / per sample) feature importance methods and this work surely could benefit from a short discussion as the one made for the model agnostic method LIME. \n- I think it would be more convincing to also compare (or discuss) the explanations/reasons that have been found with the proposed approach(es) and those with LIME with more details than just a size and computational basis.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are well addressed this work should not have any negative social impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "Not relevant.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "cHOhmAH9mgr", "reviewer": "Reviewer_4ukE", "summary": "This paper is devoted to computing abductive explanations for random\nforest (RF) machine learning (ML) models. Concretely, the paper\nproposes a variant of such explanations called majoritary reasons and\nargues that this new kind of explanation is not only easier to compute\nthan computing sufficient reasons (both from the theoretical and\npractical points of view) but also that in practice they may be\nadvantageous to a user due to their often smaller size than that of\nsufficient reasons. For that, an encoding and a MaxSAT-based solution\nfor computing majoritary reasons for RF models is proposed.\n", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work studies the issue of explainability, which is arguably one\nof the most important problems in the current state of affairs in AI.\nMore importantly, this paper makes an attempt to approach this problem\nfrom the right viewpoint - namely, from the perspective of logic and\nformal reasoning, which is in clear contrast to all the \"magic\"\nheuristic methods being studied in the vast majority of works on XAI.\nFurthermore, random forests represent an important and quite widely\nused ML model, which further underscores the results reported in the\npaper.\n\nHaving said that, I feel somewhat negative about this paper as I have\na few issues with it. First, although the list of claimed\ncontributions is large, not all of them seem to be necessary in the\ncontext of the paper and the conference. As an example, Propositions 1\nand 2 look unrelated to the rest of the paper. Furthermore, I am not\nsure to what extent Proposition 2 is true because one can trivially\nencode an RF to a CNF formula in polynomial time and space using\nauxiliary variables, and the authors themselves do mention this later\nin the paper. Here, if the authors meant some concrete form of\nreduction to CNF/DNF, they should have been clear.\n\nI take Proposition 3 as a contribution even though it might be seen as\nsomewhat simple. Also, abductive and contrastive explanations are\nknown to be related with MUSes and MCSes of a logic representation of\nthe decision function, respectively. This makes Proposition 5 not\nsurprising as computing smallest size abductive explanations is in\ngeneral hard for the second level of the polynomial hierarchy, due to\nthe well-known complexity of SMUS. (Granted that the exact complexity\nof this problem in the particular case of RF models was previously not\nstudied.)\n\nThe paper requires some proof-reading as some of the examples are\nwrong. For example, {x_3=1, x_4=1} is not a sufficient reason for\nprediction F(x)=1. One can get a simple counterexample by setting\nx_1=0 and x_2=0, which makes T_2 and T_3 predict class 0 (hence, the\nmajority of trees report class 0, thus, making the RF predict 0).\nThis mistake invalidates some of the later examples, which refer to\nthis one.\n\nMy main issue with the paper is related to the main contribution,\nnamely, majoritary reasons. Concretely, I do not see why they are not\nguaranteed to be sufficient reasons. Following the definition, such a\nreason should imply that the majority of trees predict the right\nclass. By definition of RF, this means that such an explanation\nsuffices for the prediction of RF to hold, i.e. it is a sufficient\nreason for RF. (Please let me know if I am missing something.) Hence,\nI can't easily see why the following claims are correct, as well as\nif/why the MaxSAT encoding and the use a MaxSAT solver is enough to\ncompute a majoritary reason. The \"difference\" between the two types of\nexplanations is mentioned on line 204 but is not discussed at all.\nAlso, the examples fail to properly illustrate the concept.\n\nMore on examples, there is not a simple example to illustrate the\nencoding - and there must be such examples.\n\nAlso, I am not entirely convinced by the need to introduce the concept\nof direct explanations - it is straightforward that one can make the\nunion of the paths firing the prediction in each tree predicting the\nright class to derive a \"common\" reason for the prediction. Also,\nabductive explanations are typically equated to sufficient reasons,\ni.e. they are subset-minimal. Also, using the word \"minimal\" instead\nof \"minimum\"/\"smallest\" is a bit confusing when the authors refer to\nexplanations of smallest size.\n\nRegarding the experiments, I have a few comments:\n\t- what SAT solver do you use?\n\t- what configuration of a MaxSAT solver do you use?\n\t- how do you encode the cardinality constraints?\n\t- on line 287 you mention that sufficient reasons for a linear\n\t  classifier can be computed in polynomial time but fail to cite\n\t  the corresponding work.\n\t- there is no need to use LMHS (also, in what sense is it\n\t  incremental?) - you can simply use an effective incomplete\n\t  solver that over-approximates the exact solution well enough,\n\t  say Loandra.\n\nFinally, I would like to note that I failed to find a supplementary\nPDF file that would contain the proofs and/or extended discussion. The\nzip-file contains the datasets, source code and other things related\nto experimental results only. I look forward to the authors' rebuttal\nand hope that the authors will be able to convincingly comment on the\nissues I raised and/or prove me wrong.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main comments above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "GLDtJV8zTD", "reviewer": "Reviewer_ZH2P", "summary": "This paper tries to do some explanations of random forests.", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper tries to do some explanations of random forests, and proposes majoritary reasons and minimal majoritary reasons. The problem and the idea is interesting. However, there are many limitations:\n1, This paper only considers the instance with Boolean feature vector, which is the major problem. In many machine learning problems, we usually meet the problem with real-valued feature vector, such as CV and NLP applications. The paper can not be used to address real-world machine learning applications by considering boolean feature vector.\n2, Many places are unclear, such as what is \"abductive explanations\"? this notion appears many times, but no clear definition and explanation.  what is the \"prime implicant\"? still no explantion.\n3, Why trade off? why there is a trade off between complexity and sparsity, why there is a sparsity? readers are confused by the paper.\n4, the datasets are too tivial, can the paper try imagenet and NLP data sets?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1, This paper only considers the instance with Boolean feature vector, which is the major problem. In many machine learning problems, we usually meet the problem with real-valued feature vector, such as CV and NLP applications. The paper can not be used to address real-world machine learning applications by considering boolean feature vector.\n2, Many places are unclear, such as what is \"abductive explanations\"? this notion appears many times, but no clear definition and explanation.  what is the \"prime implicant\"? still no explantion.\n3, Why trade off? why there is a trade off between complexity and sparsity, why there is a sparsity? readers are confused by the paper.\n4, the datasets are too tivial, can the paper try imagenet and NLP data sets?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "0.5"}, "extra_text": {}}, {"review_id": "-ZmgOG7Fw5B", "reviewer": "Reviewer_afJi", "summary": "The paper formalizes the problem of extracting explanations from random forests, provides some clear categorizations of different types of explanations, and eventually tractable algorithms for finding not optimal but good minimal explanations.\n", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I really enjoyed reading this paper. Admittedly, the very clear formalization of the problem is probably not due to this work, and I could have known it from prior works, but I didn't. On top of that are very clear new definitions of sufficient reasons, which are expensive to find, and majoritary reasons, which are easy to find (essentially just a bottom-up greedy search). Finding minimal majoritary reasons is harder, but a polynomial solution is presented based on encoding the problem as a SAT problem.\n\nI also liked that the paper even included a comparison to a slightly adapted version of LIME.\n\nA minor comment: I, for one, did not know what a \"prime implicant\" is. It's not hard to guess, and even easier to google, but I think it wouldn't hurt to briefly mention it in the paper (I would, e.g., expect that more people in machine learning know how to convert a decision tree to DNF, which is explained in the paper, than people know what a prime implicant is).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't have any suggestions.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't have any ethical concerns with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper concerns interpretability of the decisions made by the random forest algorithm, by considering different types of reasons that would explain why an input instance is classified as positive or negative by a Boolean random forest.

The paper received a mixed set of reviews, ranging from very positive to very negative ones.

On the positive side, some reviewers praised a clear and sound formalization of extracting the explanations from random forest through the perspective of formal logic, and generally found the proposed approach interesting.

On the negative side, however, the paper was found to have a small contribution from the formal logic point of view. Also, the presentation of the main concepts results was found to be unclear, and their discussion with the existing results lacking. Furthermore, some of the results (such as Propositions 1 and 2) felt unrelated to the rest of the paper (and only used in the proofs omitted from the main text), while some other already known.

One of the reviewers did not like the fact that the paper did not test the proposed approach for large scale data sets (there was also an issue with the applicability beyond Boolean features, but I believe it was entirely clarified in the rebuttal). Also the presentation was found unclear at places.

Overall I believe the paper would require a major revision before publishing. I would advise the authors to take into account the remarks of the reviewers, especially reviewer 4ukE, while preparing such revision.

Decision: Reject