# Trading Complexity for Sparsity
in Random Forest Explanations

Gilles Audemard  CRIL, Université d’Artois & CNRS, France  Steve Bellart
CRIL, Université d’Artois & CNRS, France  Louenas Bounia  CRIL, Université
d’Artois & CNRS, France  Frédéric Koriche  CRIL, Université d’Artois & CNRS,
France  Jean-Marie Lagniez  CRIL, Université d’Artois & CNRS, France  Pierre
Marquis  CRIL, Université d’Artois & CNRS, France  Institut Universitaire de
France

(email<EMAIL_ADDRESS>
###### Abstract

Random forests have long been considered as powerful model ensembles in
machine learning. By training multiple decision trees, whose diversity is
fostered through data and feature subsampling, 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: while decision trees
are often easily interpretable, the predictions made by random forests are
much more difficult to understand, as they involve a majority vote over
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 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 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. Sufficient reasons - for which the
identification problem is DP-complete - are slightly larger than majoritary
reasons that can be generated using a simple linear-time greedy algorithm, and
significantly larger than _minimal_ majoritary reasons that can be approached
using an anytime Partial MaxSAT algorithm.

##  1 Introduction

Over the past two decades, rapid progress in statistical machine learning has
led to the deployment of models endowed with remarkable predictive
capabilities. Yet, as the spectrum of applications using statistical learning
models becomes increasingly large, explanations for why a model is making
certain predictions are ever more critical. For example, in medical diagnosis,
if some model predicts that an image is malignant, then the doctor may need to
know which features in the image have led to this classification. Similarly,
in the banking sector, if some model predicts that a customer is a fraud, then
the banker might want to know why. Therefore, having explanations for why
certain predictions are made is essential for securing user confidence in
machine learning technologies [25, 26].

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 a 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 implement, with few tuning parameters.
Furthermore, they often make accurate and robust predictions in practice, even
for small data samples and high-dimensional feature spaces [6]. For these
reasons, 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].

Despite their success, random forests are much less interpretable than
decision trees. Indeed, the prediction made by a decision tree on a given data
instance can be easily interpreted by reading the unique root-to-leaf path
that covers the instance. Contrastingly, there is no such _direct reason_ in a
random forest, since the prediction is 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 a data
instance is classified as positive or negative by the model ensemble.

#### Related Work.

Explaining random forest predictions has received increasing attention in
recent years [5, 10, 19]. Notably, in the classification setting, [10, 19]
have focused on _sufficient 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 $\bm{x}$ as positive by $f$ is a _prime
implicant_ $t$ of $f$ covering $\bm{x}$. By construction, removing any feature
from a sufficient reason $t$ would question the fact that $t$ explains the way
$\bm{x}$ is classified by $f$. Interestingly, if $f$ is described by a single
decision tree, then generating a sufficient reason for any input instance
$\bm{x}$ 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 a sufficient reason is DP-complete. Despite this intractability
statement, the empirical results reported in [19] show that a MUS-based
algorithm for computing sufficient reasons proves quite efficient in practice.

In addition to “model-based” explanations investigated in [10, 19], “model-
agnostic” explanations can be applied to random forests. Notably, the LIME
method [31] extrapolates a linear threshold function $g$ from the behavior of
the random forest $f$ around an input instance $\bm{x}$. Yet, even if a 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$.

#### Contributions.

In this paper, we introduce several new notions of abductive explanations:
_direct reasons_ extend to 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 $\bm{x}$
as positive by some random forest $f$ is a prime implicant $t$ of a majority
of decision trees in $f$ that covers $\bm{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 we make an exception for the intractability of
generating sufficient reasons, which was recently established in [19].
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
$\Sigma_{2}^{p}$-complete.

Based on these results, we provide algorithms for deriving random forest
explanations, which open the way for an empirical comparison. Our experiments
made on standard benchmarks show the existence of a trade-off between the
runtime complexity of finding (possibly minimal) abductive explanations and
the sparsity of such explanations. In a nutshell, majoritary reasons and
minimal majoritary 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 generate
them are generally smaller than those obtained for sufficient reasons.
Furthermore, minimal majoritary reasons outperform minimal sufficient reasons,
since the latter are too computationally demanding. In fact, using an
_anytime_ Partial MaxSAT solver for minimizing majoritary reasons, we derive
sparse explanations which are typically much shorter than all other forms of
abductive explanations. Proofs are reported in a final appendix. Additional
empirical results are available on the web page of the EXPEKCTATION project:
http://www.cril.univ-artois.fr/expekctation/.

##  2 Preliminaries

For an integer $n$, let $[n]=\\{1,\cdots,n\\}$. By $\mathcal{F}_{n}$ we denote
the class of all Boolean functions from $\\{0,1\\}^{n}$ to $\\{0,1\\}$, and we
use $X_{n}=\\{x_{1},\cdots,x_{n}\\}$ to denote the set of input Boolean
variables. Any Boolean vector $\bm{x}\in\\{0,1\\}^{n}$ is called an
_instance_. For any function $f\in\mathcal{F}_{n}$, an instance
$\bm{x}\in\\{0,1\\}^{n}$ is called a _positive example_ of $f$ if
$f(\bm{x})=1$, and a _negative example_ otherwise.

We refer to $f$ as a propositional formula when it is described using the
Boolean connectives $\land$ (conjunction), $\lor$ (disjunction) and $\neg$
(negation), together with the constants $1$ (true) and $0$ (false). As usual,
a _literal_ $l_{i}$ is a variable $x_{i}$ or its negation $\neg x_{i}$, also
denoted $\overline{x}_{i}$. A _term_ (or _monomial_) $t$ is a conjunction of
literals, and a _clause_ $c$ is a disjunction of literals. A _DNF formula_ is
a disjunction of terms and a _CNF formula_ is a conjunction of clauses. The
set of variables occurring in a formula $f$ is denoted $\mathit{Var}(f)$. In
the rest of the paper, we shall often treat instances as terms, and terms as
sets of literals. Given an assignment $\bm{z}\in\\{0,1\\}^{n}$, the
corresponding term is defined as

$\displaystyle t_{\bm{z}}=\bigwedge_{i=1}^{n}x_{i}^{z_{i}}\mbox{ where
}x_{i}^{0}=\overline{x}_{i}\mbox{ and }x_{i}^{1}=x_{i}$

A term $t$ _covers_ an assignment $\bm{z}$ if $t\subseteq t_{\bm{z}}$. An
_implicant_ of a Boolean function $f$ is a term that implies $f$, that is, a
term $t$ such that $f(\bm{z})=1$ for every assignment $\bm{z}$ covered by $t$.
A _prime implicant_ of $f$ is an implicant $t$ of $f$ such that no proper
subset of $t$ is an implicant of $f$.

With these basic notions in hand, a (Boolean) _decision tree_ on $X_{n}$ is a
binary tree $T$, each of whose internal nodes is labeled with one of $n$ input
variables, and whose leaves are labeled $0$ or $1$. 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(\bm{x})\in\\{0,1\\}$ of $T$ on an input instance
$\bm{x}$ is given by the label of the leaf reached from the root as follows:
at each node go to the left or right child depending on whether the input
value of the corresponding variable is $0$ or $1$, respectively. A (Boolean)
_random forest_ on $X_{n}$ is an ensemble $F=\\{T_{1},\cdots,T_{m}\\}$, where
each $T_{i}$ $(i\in[m])$ is a decision tree on $X_{n}$, and such that the
value $F(\bm{x})\in\\{0,1\\}$ on an input instance $\bm{x}$ is given by

$\displaystyle F(\bm{x})=\begin{cases}1&\mbox{ if
}\frac{1}{m}\sum_{i=1}^{m}T_{i}(\bm{x})>\frac{1}{2}\\\ 0&\mbox{
otherwise.}\end{cases}$

The size of $F$ is given by $|F|=\sum_{i=1}^{m}|T_{i}|$, where $|T_{i}|$ is
the number of nodes occurring in $T_{i}$. The class of decision trees on
$X_{n}$ is denoted ${\tt DT}_{n}$, and the class of random forests with at
most $m$ decision trees (with $m\geq 1$) over ${\tt DT}_{n}$ is denoted ${\tt
RF}_{n,m}$. ${\tt RF}_{n}$ is the union of all ${\tt RF}_{n,m}$ for
$m\in\mathbb{N}$.

$x_{4}$$T_{1}$$0$$x_{2}$$1$$x_{3}$$0$$x_{1}$$0$$1$$x_{2}$$T_{2}$$x_{1}$$1$$0$$x_{4}$$0$$1$$x_{3}$$T_{3}$$x_{2}$$x_{2}$$x_{1}$$x_{4}$$0$$x_{1}$$0$$1$$0$$x_{4}$$0$$1$$0$$1$

Figure 1: A random forest $F=\\{T_{1},T_{2},T_{3}\\}$ for recognizing Cattleya
orchids. The left (resp. right) child of any decision node labelled by $x_{i}$
corresponds to the assignment of $x_{i}$ to $0$ (resp. $1$).

######  Example 1.

The random forest $F=\\{T_{1},T_{2},T_{3}\\}$ in Figure 1 is composed of three
decision trees. It separates Cattleya orchids from other orchids using the
following features: $x_{1}$: “has fragrant flowers”, $x_{2}$: “has one or two
leaves”, $x_{3}$: “has large flowers”, and $x_{4}$: “is sympodial”.

It is well-known that any decision tree $T$ can be transformed into its
negation $\neg T\in{\tt DT}_{n}$, 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 a random forest $\neg
F\in{\tt RF}_{n,m}$ equivalent to the negation of a given random forest
$F\in{\tt RF}_{n,m}$.

Another important property of decision trees is that any $T\in{\tt DT}_{n}$
can be transformed in linear time into an equivalent disjunction of terms
${\tt DNF}(T)$, where each term coincides with a $1$-path (i.e., a path from
the root to a leaf labeled with $1$), or a conjunction of clauses ${\tt
CNF}(T)$, where each clause is the negation of term describing a $0$-path.
When switching to random forests, the picture is quite different:

######  Proposition 2.

Any CNF or DNF formula can be converted in linear time into an equivalent
random forest, but there is no polynomial-space translation from RF to CNF or
to DNF.

##  3 Random Forest Explanations

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 a notion of abductive explanation111Unlike [16], 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.. Formally, given a Boolean function $f\in\mathcal{F}_{n}$ and an
instance $\bm{x}\in\\{0,1\\}^{n}$, an abductive explanation for $\bm{x}$ given
$f$ is an implicant $t$ of $f$ (resp. $\neg f$) if $f(\bm{x})=1$ (resp.
$f(\bm{x})=0$) that covers $\bm{x}$. An abductive explanation $t$ for $\bm{x}$
given $f$ always exists, since $t=t_{\bm{x}}$ is such a (trivial) explanation.
So, in the rest of this section, we shall mainly concentrate on _sparse_ forms
of abductive explanations.

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 on the case
where $\bm{x}$ is a positive example of $f$, because $\neg f$ can be computed
in linear time (by Proposition 1). Nevertheless, for the sake of clarity, we
shall consider both cases $f(\bm{x})=1$ and $f(\bm{x})=0$ in our definitions.

###  3.1 Direct Reasons

For a decision tree $T\in{\tt DT}_{n}$ and a data instance
$\bm{x}\in\\{0,1\\}^{n}$, the _direct reason_ of $\bm{x}$ given $T$ is the
term $t_{\bm{x}}^{T}$ corresponding to the unique root-to-leaf path of $T$
that covers $\bm{x}$. We can extend this simple form of abductive explanation
to random forests as follows:

######  Definition 1.

Let $F=\\{T_{1},\ldots,T_{m}\\}$ be a random forest in ${\tt RF}_{n,m}$, and
$\bm{x}\in\\{0,1\\}^{n}$ be an instance. Then, the direct reason for $\bm{x}$
given $F$ is the term $t_{\bm{x}}^{F}$ defined by

$\displaystyle t_{\bm{x}}^{F}=\begin{cases}\bigwedge_{T_{i}\in
F:T_{i}(\bm{x})=1}t_{\bm{x}}^{T_{i}}&\mbox{ if }F(\bm{x})=1\\\
\bigwedge_{T_{i}\in F:T_{i}(\bm{x})=0}t_{\bm{x}}^{T_{i}}&\mbox{ if
}F(\bm{x})=0\end{cases}$

By construction, $t_{\bm{x}}^{F}$ is an abductive explanation which can be
computed in $\mathcal{O}(|F|)$ time.

######  Example 2.

Considering Example 1 again, the instance $\bm{x}=(1,1,1,1)$ is recognized as
a Cattleya orchid, since $F(\bm{x})=1$. The direct reason for $\bm{x}$ given
$F$ is $t_{\bm{x}}^{F}=x_{1}\land x_{2}\land x_{3}\land x_{4}$. It coincides
with $t_{\bm{x}}$. Consider now the instance $\bm{x}^{\prime}=(0,1,0,0)$; it
is not recognized as a Cattleya orchid, since $F(\bm{x})=0$. The direct reason
for $\bm{x}^{\prime}$ given $F$ is
$t_{\bm{x}^{\prime}}^{F}=x_{2}\land\overline{x}_{3}\land\overline{x}_{4}$. It
is a better abductive explanation than $t_{\bm{x}^{\prime}}$ itself since it
does not contain $\overline{x}_{1}$, which is locally irrelevant.

###  3.2 Sufficient Reasons

Another valuable notion of abductive explanation is the one of sufficient
reason222Sufficient reasons are also known as prime-implicant explanations
[33]., defined for any Boolean classifier [13]. In the setting of random
forests, such explanations can be defined as follows:

######  Definition 2.

Let $F\in{\tt RF}_{n}$ be a random forest and $\bm{x}\in\\{0,1\\}^{n}$ be an
instance. A _sufficient reason_ for $\bm{x}$ given $F$ is a prime implicant
$t$ of $F$ (resp. $\neg F$) if $F(\bm{x})=1$ (resp. $F(\bm{x})=0$) that covers
$\bm{x}$.

######  Example 3.

For our running example, $x_{2}\wedge x_{3}\wedge x_{4}$ and $x_{1}\wedge
x_{4}$ are the sufficient reasons for $\bm{x}$ given $F$. $\overline{x}_{4}$
and $\overline{x}_{1}\wedge\overline{x}_{3}$ are the sufficient reasons for
$\bm{x}^{\prime}$ given $F$.

Unlike arbitrary abductive explanations, all features occurring in a
sufficient reason $t$ are _relevant_. Indeed, removing any literal from $t$
would question the fact that $t$ implies $F$. To this point, the direct reason
$t_{\bm{x}}^{F}$ for $\bm{x}$ given $F$ may contain arbitrarily many more
features than a sufficient reason for $\bm{x}$ given $F$, since this was
already shown in the case where $F$ consists in a single decision tree [18].

The problem of identifying a sufficient reason $t$ for an input instance
$\bm{x}\in\\{0,1\\}^{n}$ with respect to a given random forest $F\in{\tt
RF}_{n}$, has recently been shown DP-complete [19]. In fact, even the
apparently simple task of _checking_ whether $t$ is an implicant of $F$ is
already hard:

######  Proposition 3.

Let $F$ be a random forest in ${\tt RF}_{n}$ and $t$ be a term over $X_{n}$.
Then, deciding whether $t$ is an implicant of $F$ is coNP-complete.

The above result is in stark contrast with the computational complexity of
checking whether a term $t$ is an implicant of a decision tree $T$. This task
can be solved in polynomial time, using the fact that $T$ can be converted (in
linear time) into its clausal form ${\tt CNF}(T)$, together with the fact that
testing whether $t$ implies ${\tt CNF}(T)$ can be done in $\mathcal{O}(|T|)$
time. That mentioned, in the case of random forests, the implicant test can be
achieved via a call to a SAT oracle:

######  Proposition 4.

Let $F=\\{T_{1},\ldots,T_{m}\\}$ be a random forest of ${\tt RF}_{n,m}$, and
$t$ be a (satisfiable) term over $X_{n}$. Let $H$ be the CNF formula

$\displaystyle\\{(\overline{y}_{i}\vee c):i\in[m],c\in{\tt CNF}(\neg
T_{i})\\}\cup{\tt CNF}\left(\sum_{i=1}^{m}y_{i}>\frac{m}{2}\right)$

where $\\{y_{1},\ldots,y_{m}\\}$ are fresh variables and ${\tt
CNF}\left(\sum_{i=1}^{m}y_{i}>\frac{m}{2}\right)$ is a CNF encoding of the
cardinality contraint $\sum_{i=1}^{m}y_{i}>\frac{m}{2}$. Then, $t$ is an
implicant of $F$ if and only if $H\land t$ is unsatisfiable.

Based on such an encoding, the sufficient reasons for an instance $\bm{x}$
given a random forest $F$ can be characterized in terms of MUS (minimal
unsatisfiable subsets), as suggested in [19]. This characterization is useful
because many SAT-based algorithms for computing a MUS (or even all MUSes) of a
CNF formula have been pointed out for the past decade [2, 23, 24], and hence,
one can take advantage of them for computing sufficient reasons.

Going one step further, a natural way for improving the clarity of sufficient
reasons is to focus on those of minimal size. Specifically, given $F\in{\tt
RF}_{n}$ and $\bm{x}\in\\{0,1\\}^{n}$, a _minimal sufficient reason_ for
$\bm{x}$ with respect to $F$ is a sufficient reason for $\bm{x}$ given $F$ of
minimal size.333Minimal sufficient reasons should not to be confused with
_minimum-cardinality explanations_ [33], where the minimality condition bears
on the features set to $1$ in the data instance $\bm{x}$.

######  Example 4.

For our running example, $x_{1}\wedge x_{4}$ is the unique minimal sufficient
reason for $\bm{x}$ given $F$, and $\overline{x}_{4}$ is the unique minimal
reason for $\bm{x}^{\prime}$ given $F$.

As a by-product of the characterization of a sufficient reason in terms of MUS
[19], a minimal sufficient reason for $\bm{x}$ given $f$ can be viewed as a
_minimal_ MUS. Thus, we can exploit algorithms for computing minimal MUSes
(see e.g., [17]) in order to derive minimal sufficient reasons. However,
deriving a minimal sufficient reason is computationally harder than deriving a
sufficient reason:

######  Proposition 5.

Let $F\in{\tt RF}_{n}$, $\bm{x}\in\\{0,1\\}^{n}$, and $k\in\mathbb{N}$. Then,
deciding whether there exists a minimal sufficient reason $t$ for $\bm{x}$
given $F$ containing at most $k$ features is $\Sigma_{2}^{p}$-complete.

###  3.3 Majoritary Reasons

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 to 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.

######  Definition 3.

Let $F=\\{T_{1},\ldots,T_{m}\\}$ be a random forest in ${\tt RF}_{n,m}$ and
$\bm{x}\in\\{0,1\\}^{n}$ be an instance. Then, a _majoritary reason_ for
$\bm{x}$ given $F$ is a term $t$ covering $\bm{x}$, such that $t$ is an
implicant of at least $\lfloor\frac{m}{2}\rfloor+1$ decision trees $T_{i}$
(resp. $\neg T_{i}$) if $F(\bm{x})=1$ (resp. $F(\bm{x})=0$), and for every
$l\in t$, $t\setminus\\{l\\}$ does not satisfy this last condition.

######  Example 5.

For our running example, $\bm{x}$ has three majoritary reasons given $F$:
$x_{1}\land x_{2}\land x_{4}$, $x_{1}\land x_{3}\land x_{4}$, and $x_{2}\land
x_{3}\land x_{4}$. Those reasons are better than $t_{\bm{x}}^{F}$ in the sense
that they are shorter than this direct reason. $\bm{x}^{\prime}$ has three
majoritary reasons given $F$: $\overline{x}_{1}\land\overline{x}_{4}$,
$x_{2}\land\overline{x}_{4}$, and $\overline{x}_{1}\land
x_{2}\land\overline{x}_{3}$. Each of the two majoritary reasons $x_{1}\land
x_{2}\land x_{4}$ and $x_{1}\land x_{3}\land x_{4}$ for $\bm{x}$ given $F$
contains an irrelevant literal for the task of classifying $\bm{x}$ using $F$
since $x_{1}\land x_{4}$ is a sufficient reason for $\bm{x}$ given $F$.
Similarly, each majoritary reason for $\bm{x}^{\prime}$ given $F$ contains an
irrelevant literal for the task of classifying $\bm{x}^{\prime}$ using $F$.

As the previous example illustrates it, the notions of majoritary reasons and
of sufficient reasons do not coincide in general. Indeed, a sufficient reason
$t$ is a prime implicant (covering $\bm{x}$) of the forest $F$, while a
majoritary reason $t^{\prime}$ is an implicant (covering $\bm{x}$) of a strict
majority of decision trees in the forest $F$ satisfying the additional
condition that $t^{\prime}$ 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:

######  Proposition 6.

Let $F=\\{T_{1},\ldots,T_{m}\\}$ be a random forest of ${\tt RF}_{n,m}$ and
$\bm{x}\in\\{0,1\\}^{n}$ such that $F(\bm{x})=1$. Unless $m<3$, it can be the
case that every majoritary reason for $\bm{x}$ given $F$ contains arbitrarily
many more features than any sufficient reason for $\bm{x}$ given $F$.

What makes majoritary reasons valuable is that they are abductive and can be
generated in linear time. The evidence that any majoritary reason $t$ for
$\bm{x}$ given $F$ is an abductive explanation for $\bm{x}$ given $F$ comes
directly from the fact that if $t$ implies a majority of decision trees in
$F$, then it is an implicant of $F$ (note that the converse implication does
not hold in general).

The tractability of generating majoritary reasons lies in the fact that they
can be found using a simple greedy algorithm. For the case where
$F(\bm{x})=1$, start with $t=t_{\bm{x}}$, and iterate over the literals $l$ of
$t$ by checking whether $t$ deprived of $l$ is an implicant of at least
$\lfloor\frac{m}{2}\rfloor+1$ decision trees of $F$. If so, remove $l$ from
$t$ and proceed to the next literal. Once all literals in $t_{\bm{x}}$ have
been examined, the final term $t$ is by construction an implicant of a strict
majority of decision trees in $F$, such that removing any literal from it
would lead to a term that is no longer an implicant of this majority. So, $t$
is by construction a majoritary reason. The case where $F(\bm{x})=0$ is
similar, by simply replacing each $T_{i}$ with its negation in $F$. This
greedy algorithm runs in $\mathcal{O}(n|F|)$ time, using the fact that, on
each iteration, checking whether $t$ is an implicant of $T_{i}$ (for each
$i\in[m]$) can be done in $\mathcal{O}(|T_{i}|)$ time.

By analogy with minimal sufficient reasons, a natural way of improving the
quality of majoritary reasons is to seek for shortest ones. Let $F\in{\tt
RF}_{n}$ be a random forest and $\bm{x}\in\\{0,1\\}^{n}$ be an instance. Then,
a minimal majoritary reason for $\bm{x}$ given $F$ is a minimal-size
majoritary reason for $\bm{x}$ given $F$.

######  Example 6.

For our running example, the three majoritary reasons for $\bm{x}$ given $F$
are its minimal majoritary reasons. Contrastingly, among the majoritary
reasons for $\bm{x}^{\prime}$ given $F$, only
$\overline{x}_{1}\land\overline{x}_{4}$ and $x_{2}\land\overline{x}_{4}$ are
minimal majoritary reasons.

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:

######  Proposition 7.

Let $F\in{\tt RF}_{n}$, $\bm{x}\in\\{0,1\\}^{n}$, and $k\in\mathbb{N}$. Then,
deciding whether there exists a minimal majoritary reason $t$ for $\bm{x}$
given $F$ containing at most $k$ features is NP-complete.

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 $(C_{\mathrm{soft}},C_{\mathrm{hard}})$ where
$C_{\mathrm{soft}}$ and $C_{\mathrm{hard}}$ are (finite) sets of clauses. The
goal is to find a Boolean assignment that maximizes the number of clauses $c$
in $C_{\mathrm{soft}}$ that are satisfied, while satisfying all clauses in
$C_{\mathrm{hard}}$.

######  Proposition 8.

Let $F\in{\tt RF}_{n,m}$ and $\bm{x}\in\\{0,1\\}^{n}$ be an instance such that
$F(\bm{x})=1$. Let $(C_{\mathrm{soft}},C_{\mathrm{hard}})$ be an instance of
the Partial MaxSAT problem such that:

$\displaystyle C_{\mathrm{soft}}$ $\displaystyle=\\{\overline{x}_{i}:x_{i}\in
t_{\bm{x}}\\}\cup\\{x_{i}:\overline{x}_{i}\in t_{\bm{x}}\\}$ $\displaystyle
C_{\mathrm{hard}}$ $\displaystyle=\\{(\overline{y}_{i}\vee
c_{\mid\bm{x}}):i\in[m],c\in{\tt CNF}(T_{i})\\}\cup{\tt
CNF}\left(\sum_{i=1}^{m}y_{i}>\frac{m}{2}\right)$

where $c_{\mid\bm{x}}=c\cap t_{\bm{x}}$ is the restriction of $c$ to the
literals in $t_{\bm{x}}$, $\\{y_{1},\ldots,y_{m}\\}$ are fresh variables and
${\tt CNF}(\sum_{i=1}^{m}y_{i}>\frac{m}{2})$ is a CNF encoding of the
contraint $\sum_{i=1}^{m}y_{i}>\frac{m}{2}$. The intersection of $t_{\bm{x}}$
with $t_{\bm{z}^{*}}$, where $\bm{z}^{*}$ is an optimal solution of
$(C_{\mathrm{soft}},C_{\mathrm{hard}})$, is a minimal majoritary reason for
$\bm{x}$ given $F$.

Clearly, in the case where $F(\bm{x})=0$, it is enough to consider the same
instance of Partial MaxSAT as above, except that
$C_{\mathrm{hard}}=\\{(\overline{y}_{i}\vee c_{\mid\bm{x}}):i\in[m],c\in{\tt
CNF}(\neg T_{i})\\}\cup{\tt CNF}(\sum_{i=1}^{m}y_{i}>\frac{m}{2})$.

Thanks to this characterization result, one can leverage the numerous
algorithms that have been developed so far for Partial MaxSAT (see e.g. [1,
27, 28, 32]) in order to compute minimal majoritary reasons. We took advantage
of it to achieve some of the experiments reported in Section 4.

##  4 Experiments

#### Empirical setting.

The empirical protocol was as follows. We have considered 15 datasets, which
are standard benchmarks from the well-known repositories Kaggle
(www.kaggle.com), OpenML (www.openml.org), and UCI (archive.ics.uci.edu/ml/).
These datasets are compas,  placement, recidivism, adult, ad_data, mnist38,
mnist49, gisette, dexter, dorothea, farm-ads, higgs_boson, christine, gina,
and bank. mnist38 and mnist49 are subsets of the mnist dataset, restricted to
the instances of 3 and 8 (resp. 4 and 9) digits. 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 of trees, the depth of the
trees, the mean accuracy) can be found at http://www.cril.univ-
artois.fr/expekctation/. 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
preprocessing has taken place: these features have been binarized on-the-fly
by the random forest learning algorithm that has been used.

For every benchmark $b$, a $10$-fold cross validation process has been
achieved. Namely, a set of $10$ random forest $F_{b}$ 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 $9$ parts as the training set
for generating a 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 [30] library in his version 0.23.2. The maximal
depth of any decision tree in a forest has been bounded at 8. All other hyper-
parameters 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 is good enough. For each
benchmark $b$, each random forest $F$, and a subset of 25 instances $\bm{x}$
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 $\bm{x}$ given $F$, a sufficient reason for $\bm{x}$
given $F$, a majoritary reason $\bm{x}$ given $F$, a minimal majoritary reason
for $\bm{x}$ given $F$, and a minimal sufficient reason for $\bm{x}$ given
$F$.

For computing sufficient reasons and minimal majoritary reasons, we took
advantage of the Pysat library [15] (version 0.1.6.dev15) which provides the
implementation of the RC2 Partial MaxSAT 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 majoritary reason for the instance, we
kept a 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.

We also derived a “LIME explanation” for each instance. Such an explanation
has been generated thanks to the following approach. For any $\bm{x}$ under
consideration, one first used LIME [31] to generate an associated linear model
$\bm{w}_{\bm{x}}$ where $\bm{w}_{\bm{x}}\in\mathbb{R}^{n}$. This linear model
$\bm{w}_{\bm{x}}$ classifies any instance $\bm{x}^{\prime}$ as a positive
instance if and only if $\bm{w}_{\bm{x}}\cdot\bm{x}^{\prime}>0$. Furthermore,
$\bm{w}_{\bm{x}}$ classifies the instance to be explained $\bm{x}$ in 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 [31] in its latest version.
Interestingly, a minimal sufficient reason $t$ for $\bm{x}$ given
$\bm{w}_{\bm{x}}$ can be generated in polynomial time from $\bm{w}_{\bm{x}}$.
We call it a LIME explanation for $\bm{x}$. The computation of $t$ is as
follows. If $\bm{x}$ is classified positively by $\bm{w}_{\bm{x}}$, in order
to derive $t$, it is enough to sum in a decreasing way the positive weights
$w_{i}$ occurring in $\bm{w}_{\bm{x}}$ until this sum exceeds the sum of the
opposites of all the negative weights occurring in $\bm{w}_{\bm{x}}$. The term
$t$ composed of the variables $x_{i}$ corresponding to the positive weights
that have been selected is by construction a minimal sufficient reason for
$\bm{x}$ given $\bm{w}_{\bm{x}}$ since for every $\bm{x}^{\prime}$ covered by
$t$, the inequation $\bm{w}_{\bm{x}}\cdot\bm{x}^{\prime}>0$ necessarily holds;
indeed, it holds in the worst situation where all the variables associated
with a positive weight in $\bm{w}_{\bm{x}}$ and not belonging to $t$ are set
to $0$, whilst all the variables associated with a negative weight in
$\bm{w}_{\bm{x}}$ are set to $1$. Similarly, if $\bm{x}$ is classified
negatively by $\bm{w}_{\bm{x}}$, in order to derive $t$, it is enough to sum
in an increasing way the negative weights $w_{i}$ occurring in
$\bm{w}_{\bm{x}}$ until this sum is lower than or equal to the opposite of the
sum of all the positive weights occurring in $\bm{w}_{\bm{x}}$. This time, the
term $t$ composed of the variables $x_{i}$ corresponding to the negative
weights that have been selected is by construction a minimal sufficient reason
for $\bm{x}$ given $\bm{w}_{\bm{x}}$.

All the experiments have been conducted on a 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 and each type of explanation, except LIME
explanations.

#### Results.

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).

We report hereafter empirical results about two datasets only, namely
placement and gisette (the results obtained on the other datasets are similar
and available as at http://www.cril.univ-artois.fr/expekctation/). The
placement data set is about the placement of students in a campus. It 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 as positive when the student gets a job. The random forest that
has been generated consists of 25 trees, and its mean accuracy is 97.6%.
gisette is a 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 4 and 9. An instance is labelled as positive
whenever the picture represents a 9. The random forest that has been generated
consists of 85 trees, and its mean accuracy is 96%.

Figure 2: Empirical results for the placement dataset.

Figure 2 provides the results obtained for placement, using four plots. Each
dot represents an 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 to a minimal sufficient reason because their computation
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 a
small amount of time. In particular, it shows 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 one must keep in mind that they are not abductive
explanations in general444See also [29] that reports some experiments about
Anchor (the successor of LIME), assessing the quality of the explanations
computed using Anchor.). 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.

Figure 3 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 to 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 not terminate before the time-
out. Furthermore, 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 of the forest focuses only on a subset of most
important features (in 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.

When minimal majoritary reasons are hard to be computed (as it is the case for
gisette), an approach consists in approximating them. Interestingly, one can
take advantage of an incremental partial MaxSAT algorithm, like LMHS [32], to
do the job. Specifically, the result given in Proposition 8 provides a way to
derive abductive explanations for an instance $\bm{x}$ given a random forest
$F$ in an _anytime_ fashion. Basically, using LMHS, a Boolean assignment
$\bm{z}$ satisfying all the hard constraints of $C_{\mathrm{hard}}$ and a
given number, say $k$, of soft constraints from $C_{\mathrm{soft}}$ is looked
for ($k$ is set to 0 at start). If such an assignment is found, then one looks
for an assignment satisfying $k+1$ soft constraint, and so on, until an
optimal solution is found or a preset time bound is reached. In many cases,
the most demanding step from a 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+1$ soft constraint (and such an assignment does not exist).
By construction, every $\bm{z}$ that is generated that way is such that
$t_{\bm{x}}\cap t_{\bm{z}}$ is an implicant of $F$ that covers $\bm{x}$ (and
hence, an abductive explanation). The approximation $\bm{z}$ of a minimal
majoritary reason for $\bm{x}$ given $F$, which is obtained when the time
limit is met, can be significantly shorter than the sufficient reason for
$\bm{x}$ given $F$ that has been derived. In our experiments, we used three
time limits: 10s, 60s, 600s. As the box plot and the dedicated scatter plot
given in Figure 3 show it, the sizes of the approximations $\bm{z}$ which are
derived gently decrease with time. Interestingly, the size savings that are
achieved in comparison to sufficient reasons are significant, even for the
smallest time bound of 10s that has been considered.

Figure 3: Empirical results for the gisette dataset.

##  5 Conclusion

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. 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 may contain irrelevant features. Despite this evidence,
majoritary reasons and minimal majoritary reasons appear as valuable
alternative to 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. Minimal majoritary reasons can be
looked for when majoritary reasons are too large, but this is at the cost of
an extra computation time that can be important, and even prohibitive in some
cases. However, minimal majoritary reasons can be approximated using an
_anytime_ Partial MaxSAT algorithm. Empirically, approximations can be derived
within a small amount of time and their sizes are significantly smaller than
the ones of sufficient reasons.

## Acknowledgements

This work has benefited from the support of the AI Chair EXPEKCTATION
(ANR-19-CHIA-0005-01) of the French National Research Agency. It was also
partially supported by TAILOR, a project funded by EU Horizon 2020 research
and innovation programme under GA No 952215.

## References

  * [1] C. Ansótegui, M. L. Bonet, and J. Levy.  SAT-based MaxSAT algorithms.  Artificial Intelligence, 196:77–105, 2013.
  * [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’13), pages 309–317, 2013.
  * [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\.
  * [4] Anton Belov and João Marques-Silva.  Muser2: An efficient MUS extractor.  J. Satisf. Boolean Model. Comput., 8(3/4):123–128, 2012.
  * [5] C. Bénard, G. Biau, S. Da Veiga, and E. Scornet.  Interpretable random forests via rule extraction.  In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, AISTATS’21, pages 937–945, 2021.
  * [6] G. Biau.  Analysis of a random forests model.  Journal of Machine Learning Research, 13:1063–1095, 2012.
  * [7] A. Bogomolov, B. Lepri, J. Staiano, N. Oliver, F. Pianesi, and A. Pentland.  Once upon a crime: Towards crime prediction from demographics and mobile data.  In Proceedings of the 16th International Conference on Multimodal Interaction, ICMI’14, pages 427–434. ACM, 2014.
  * [8] L. Breiman.  Random forests.  Machine Learning, 45(1):5–32, 2001.
  * [9] X. Chen and H. Ishwaran.  Random forests for genomic data analysis.  Genomics, 99(6):323–329, 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.
  * [11] A. Criminisi and J. Shotton.  Decision Forests for Computer Vision and Medical Image Analysis.  Advances in Computer Vision and Pattern Recognition. Springer, 2013.
  * [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(11):2783–2792, 2007.
  * [13] A. Darwiche and A. Hirth.  On the reasons behind decisions.  In Proceedings of the 24th European Conference on Artificial Intelligence (ECAI’20), pages 712–720, 2020.
  * [14] A. Darwiche and P. Marquis.  A knowledge compilation map.  Journal of Artificial Intelligence Research, 17:229–264, 2002.
  * [15] A. Ignatiev, A. Morgado, and J. Marques-Silva.  PySAT: A python toolkit for prototyping with SAT oracles.  In Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing (SAT’2018), pages 428–437, 2018\.
  * [16] A. Ignatiev, N. Narodytska, and J. Marques-Silva.  Abduction-based explanations for machine learning models.  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI’19), pages 1511–1519, 2019.
  * [17] A. Ignatiev, A. Previti, M. Liffiton, and J. 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\.
  * [18] Y. Izza, A. Ignatiev, and J. Marques-Silva.  On explaining decision trees.  CoRR, abs/2010.11034, 2020.
  * [19] Y. Izza and J. Marques-Silva.  On explaining random forests with SAT.  In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI’21), 2021.
  * [20] R.M. Karp.  Reducibility among combinatorial problems, chapter Complexity of Computer Computations, pages 85–103.  Plenum Press, New York, 1972.
  * [21] J. Lang, P. Liberatore, and P. Marquis.  Propositional independence: Formula-variable independence and forgetting.  Journal of Artificial Intelligence Research, 18:391–443, 2003.
  * [22] P. Liberatore.  Redundancy in logic I: CNF propositional formulae.  Artificial Intelligence, 163(2):203–232, 2005.
  * [23] M. Liffiton, A. Previti, A. Malik, and J. Marques-Silva.  Fast, flexible MUS enumeration.  Constraints An Int. J., 21(2):223–250, 2016.
  * [24] J. Marques-Silva, M. Janota, and C. Mencía.  Minimal sets on propositional formulae. Problems and reductions.  Artificial Intelligence, 252:22–50, 2017.
  * [25] T. Miller.  Explanation in artificial intelligence: Insights from the social sciences.  Artificial Intelligence, 267:1–38, 2019.
  * [26] Ch. Molnar.  Interpretable Machine Learning - A Guide for Making Black Box Models Explainable.  Leanpub, 2019.
  * [27] A. Morgado, A. Ignatiev, and J. Marques-Silva.  MSCG: robust core-guided MaxSAT solving.  J. Satisf. Boolean Model. Comput., 9(1):129–134, 2014.
  * [28] N. Narodytska and F. Bacchus.  Maximum satisfiability using core-guided MaxSAT resolution.  In Proceedings of the 28th AAAI Conference on Artificial Intelligence, pages 2717–2723, 2014.
  * [29] N. Narodytska, A. Shrotri, K. Meel, A. Ignatiev, and J. Marques-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.
  * [30] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [31] M. T. Ribeiro, S. 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\.
  * [32] P. Saikko, J. Berg, and M. Järvisalo.  LMHS: A SAT-IP hybrid MaxSAT solver.  In Proceedings of the 19th International Conference of Theory and Applications of Satisfiability Testing (SAT’16), pages 539–546, 2016.
  * [33] A. Shih, A. Choi, and A. Darwiche.  A symbolic approach to explaining bayesian network classifiers.  In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI’18), pages 5103–5111, 2018.

## Proofs

For every $f,g\in\mathcal{F}_{n}$, we note $f\models g$ when for every
$\bm{x}\in\\{0,1\\}^{n}$, $f(\bm{x})=1$ implies that $g(\bm{x})=1$.

Proof of Proposition 1

###### Proof.

By definition, an instance $\bm{x}$ is a model of the negation of a given
random forest $F=\\{T_{1},\ldots,T_{m}\\}$ if and only if it is a model of at
most $\frac{m}{2}$ trees among those of $T$. Let us state (w.l.o.g.) that
$\bm{x}$ is a model of $T_{1},\ldots,T_{k}$ and a counter-model of
$T_{k+1},\ldots,T_{m}$, with $k\leq\frac{m}{2}$. Equivalently, we have that
$\bm{x}$ is a counter-model of $T^{\prime}_{1},\ldots,T^{\prime}_{k}$ and a
model of $T^{\prime}_{k+1},\ldots,T^{\prime}_{m}$ where each $T^{\prime}_{i}$
($i\in\\{1,\ldots,m\\}$) is a decision tree equivalent to the negation of
$T_{i}$. This precisely means that $\bm{x}$ is a model of $\neg
F=\\{T^{\prime}_{1},\ldots,T^{\prime}_{m}\\}$. Since each $T^{\prime}_{i}$
($i\in\\{1,\ldots,m\\}$) can be computed in time linear in $|T_{i}|$, the
result follows. ∎

Proof of Proposition 2

###### Proof.

Let $G=c_{1}\land\cdots\land c_{p}$ be a CNF formula with $p>0$ clauses. Each
$c_{i}$ can be transformed into a decision tree $T_{i}$ using the following
linear-time recursive algorithm. For the base cases, if $c_{i}$ is empty, then
$T_{i}=0$ and if $c_{i}$ is a tautology, then $T_{i}=1$. For the inductive
case, suppose that $c_{i}=l_{j}\lor c^{\prime}_{i}$ and let $T^{\prime}_{j}$
the decision tree encoding $c^{\prime}_{i}$. If $l_{j}=x_{j}$ (resp.
$l_{j}=\overline{x}_{j}$), then $T_{i}$ is the decision tree rooted at $x_{j}$
with right (resp. left) child labeled by the leaf $1$ (resp. $0$) and with
left (resp. right) child encoding $T^{\prime}_{j}$. Now, let
$F=\\{T_{1},\cdots,T_{p},T_{p+1},\cdots,T_{q}\\}$, where
$T_{p+1},\cdots,T_{q}$ are decision trees rooted at $0$, and $q=2p-1$. For any
input instance $\bm{x}\in\\{0,1\\}^{n}$, we have $G(\bm{x})=1$ iff
$T_{i}(\bm{x})=1$ for every $i\in[p]$. Since for any positive integer $p$, the
function

$\phi_{p}(z)=\frac{p-z}{2p-1}$

satisfies $\phi_{p}(0)>\nicefrac{{1}}{{2}}$ and
$\phi_{p}(z)<\nicefrac{{1}}{{2}}$ for $z\in[p]$, it follows that $G(\bm{x})=1$
iff $F(\bm{x})>\nicefrac{{1}}{{2}}$.

The case for DNF formulas is dual: given $G=t_{1}\lor\cdots\lor t_{p}$,
compute in linear time a CNF formula equivalent to $\neg G$, then turn it in
linear time into an equivalent random forest using the transformation above,
and finally negate in linear time the resulting random forest by taking
advantage of Proposition 1.

Since every CNF formula $G$ can be turned in linear time into an equivalent
random forest $G^{\prime}$ (as we have just proved it), the size of
$G^{\prime}$ is polynomial in the size of $G$ for a fixed polynomial
(independent of $G$). Then, exploiting Proposition 1, one can negate
$G^{\prime}$ in linear time. The resulting random forest $G^{\prime\prime}$ is
equivalent to the negation of $G$ and its size is also polynomial in the size
of $G$ for a fixed polynomial.

Finally, suppose, towards a contradiction, that a polynomial-space translation
from RF to CNF exists. If so, one could compute a CNF formula
$G^{\prime\prime\prime}$ equivalent to $G^{\prime\prime}$ and having a size
polynomial in the size of $G^{\prime\prime}$ for a fixed polynomial. Thus, the
CNF formula $G^{\prime\prime\prime}$ would have a size polynomial in the size
of $G$ for a fixed polynomial. This CNF formula could be negated in linear
time into a DNF formula $G^{\prime\prime\prime\prime}$ by applying De Morgan’s
laws. By construction, $G^{\prime\prime\prime\prime}$ would be a DNF formula
equivalent to $G$, and its size would be polynomial in the size of $G$ for a
fixed polynomial. This conflicts with the fact that there is no polynomial-
space translation from CNF to DNF, see e.g., [14]. Using duality, we prove
similarly that there is no polynomial-space translation from RF to DNF.

∎

Proof of Proposition 3

###### Proof.

  * •

Membership to coNP: we show that the complementary problem, i.e., the problem
of deciding whether a term $t$ is not an implicant of a random forest $F$, is
in NP. This is direct given the characterization of the implicants of $F$
provided by Proposition 4: it is enough to comput in time polynomial in the
size of $F$ the CNF formula $H$ given in Proposition 4, and to exploit the
fact that $t$ is not an implicant of $F$ if and only if $t\wedge H$ is
satisfiable. Finally, deciding whether $t\wedge H$ is satisfiable can be
easily achieved by a non-deterministic algorithm running in time polynomial in
the size of the input (just guess a truth assignment over the variables
occurring in $t\wedge H$ and check in polynomial time that this assignment is
a model of $t\wedge H$).

  * •

coNP-hardness: by reduction from VAL, the validity problem for DNF formulae.
Let $G=d_{1}\vee\ldots\vee d_{p}$ be a DNF formula over $X_{n}$. We can
associate with $G$ in polynomial time an equivalent random forest $F$ using
Proposition 2. Consider now the term $t=\top$. $t$ is an implicant of $F$ if
and only if $G$ is valid.

∎

Proof of Proposition 4

###### Proof.

We have $t\not\models F$ if and only if $t\wedge\neg F$ is satisfiable. From
$F$, exploiting Proposition 1 one can generate in polynomial time a random
forest $F^{\prime}=\\{\neg T_{1},\ldots,\neg T_{m}\\}$ equivalent to $\neg F$.
Each $\neg T_{i}$ is the decision tree obtained by replacing every $1$-leaf in
$T_{i}$ by a $0$-leaf, and vice-versa. We thus have $t\not\models F$ if and
only if $t\wedge F^{\prime}$ is satisfiable. Then $F^{\prime}$ can be
associated in polynomial time with the following Boolean quantified formula
$\exists Y.H$ when $Y=\\{y_{i}:i\in[m]\\}\cup A$ is a set of new variables and
$H$ is a CNF formula which is the conjunction of the clauses of

$\\{(\overline{y}_{i}\vee c):i\in[m],c\in{\tt CNF}(T^{\prime}_{i})\\}$

with a CNF encoding of the cardinality constraint

$\sum_{i=1}^{m}y_{i}>\frac{m}{2}$

using auxiliary variables in $A$. $F^{\prime}$ is equivalent to $\exists Y.H$,
therefore $t\wedge F^{\prime}$ is satisfiable if and only if $t\wedge\exists
Y.H$ is satisfiable. Since the variables of $Y$ do not occur in $t$,
$t\wedge\exists Y.H$ is equivalent to $\exists Y.(t\wedge H)$. Since $\exists
Y.(t\wedge H)$ is satisfiable if and only if $t\wedge H$ is satisfiable, we
get that $t\wedge\exists Y.H$ is satisfiable if and only if $t\wedge H$ is
satisfiable. ∎

Proof of Proposition 5

###### Proof.

  * •

Membership to $\Sigma_{2}^{p}$: if there exists a minimal reason $t$ for
$\bm{x}$ given $f$ such that $t$ contains at most $k$ features, then one can
guess $t$ using a nondeterministic algorithm running in polynomial time (the
size of $t$ is bounded by the size of $\bm{x}$), then check in polynomial time
that $t$ is a sufficient reason for $\bm{x}$ given $f$ using an NP-oracle
(this comes directly from the fact that this problem belongs to DP), and
finally check in polynomial time that the size of $t$ is upper bounded by $k$.

  * •

$\Sigma_{2}^{p}$-hardness: in [22] (Theorem 2), it is shown that the problem
of deciding whether a CNF formula $\Pi=\bigwedge_{i=1}^{p}c_{i}$ has an
irredundant equivalent subset of size at most $k$ is
$\Sigma_{2}^{p}$-complete, and that the problem is $\Sigma_{2}^{p}$-hard even
in the case when $\Pi$ is unsatisfiable. Whenever $\Pi$ is unsatisfiable, an
irredundant equivalent subset of $\Pi$ precisely is a MUS of $\Pi$ (every
clause being considered as a soft clause). Accordingly, there exists an
irredundant equivalent subset $E$ of an unsatisfiable CNF formula $\Pi$ such
$E$ is of size at most $k$ if and only if there exists a MUS
$I=\\{y_{i}:c_{i}\in E\\}$ of $S=\\{y_{i}:c_{i}\in\Pi\\}$ given
$H=\\{\overline{y}_{i}\vee c_{i}:c_{i}\in\Pi\\}$ such that $I$ is of size at
most $k$. Because of this equivalence, the problem of deciding whether $S$ has
a MUS of size at most $k$ given $H$ has the same complexity as the problem of
deciding whether $\Pi$ has an irredundant equivalent subset of size at most
$k$, so it is $\Sigma_{2}^{p}$-hard. Finally, we reduce this latter problem to
the one of deciding whether a term is a minimal reason for an instance given a
random forest. The reduction is as follows. With $(H,S)$ where $S$ is
satisfiable and $H\cup S$ is unsatisfiable (as obtained from the previous
reduction), one associates in polynomial time the pair $(\bm{x},F)$ where
$\bm{x}$ is any interpretation that extends $S$ and $F$ is a random forest
from ${\tt RF}_{n,m}$ equivalent to $\neg H$ (since $H$ is a CNF formula, a
DNF formula equivalent to $\neg H$ can be computed in linear time from $H$ and
turned in linear time into an equivalent random forest $F$ as shown by
Proposition 2). Since $H\cup S$ is unsatisfiable, we have $S\models\neg H$
showing that $\bm{x}\models F$. Now, $I$ is a MUS of $S$ given $H$ if and only
if $I\cup H$ is unsatisfiable and for every $l\in I$, $(I\setminus\\{l\\})\cup
H$ is satisfiable. Taking $t=I$, this is equivalent to state that $t\wedge\neg
F$ is unsatisfiable and for every $l\in t$, $(t\setminus\\{l\\})\wedge\neg F$
is satisfiable. Equivalently, $t\models F$ and for every $l\in t$,
$(t\setminus\\{l\\})\not\models F$, or stated otherwise $t$ is a prime
implicant of $F$. Since $t=I$ and $I\subseteq S$, we also have $S\models t$,
hence $\bm{x}\models t$. Thus $t$ is a sufficient reason for $\bm{x}$ given
$F$. Since $|I|=|t|$, a MUS $I$ of $S$ given $H$ such that $|I|\leq k$ exists
if and only if a sufficient reason $t$ for $\bm{x}$ given $F$ such that
$|t|\leq k$ exists. This completes the proof.

∎

Proof of Proposition 6

###### Proof.

Again, we focus only on the case when $F(\bm{x})=1$ (if $F(\bm{x})=0$, it is
enough to consider the random forest $\neg F$ instead of $F$).

If $F$ contains at most $2$ trees, then $F$ is equivalent to the conjunction
of its elements. In this case, testing whether a term $t$ implied by $\bm{x}$
is an implicant of $F$ boils down to testing that $t$ is an implicant of every
tree in $F$, so that the sufficient reasons for $\bm{x}$ given $F$ are
precisely the majoritary reasons for $\bm{x}$ given $F$.

As to the case $m\geq 3$, whatever $n\geq 1$, let $T$ be a decision tree
equivalent to the parity function $\oplus_{i=1}^{n}x_{i}$. Consider the random
forest $F$ containing $\lfloor\frac{m}{2}\rfloor$ copies of $T$,
$\lfloor\frac{m}{2}\rfloor$ copies of the decision tree $\neg T$, and a
decision tree reduced to a $1$-leaf. By construction, $F$ is valid. Indeed,
among the subsets of $F$ containing a strict majority of decision trees, one
can find the one containing all the $\lfloor\frac{m}{2}\rfloor$ copies of $T$
plus the $1$-leaf (their conjunction is thus equivalent to $T$) and the one
containing all the $\lfloor\frac{m}{2}\rfloor$ copies of $\neg T$ plus the
$1$-leaf (their conjunction is thus equivalent to $\neg T$). Their disjunction
is thus valid. As a consequence, whatever $\bm{x}$, we have $F(\bm{x})=1$.
Indeed, we have either $T(\bm{x})=1$ or $\neg T(\bm{x})=1$ (and obviously,
$1(\bm{x})=1$). Thus, $t_{\bm{x}}$ is an implicant of a (strict) majority of
decision trees of $F$. Now, consider any literal $l$ of $t_{\bm{x}}$. The term
$t_{\bm{x}}\setminus\\{l\\}$ is not an implicant of $T$ nor an implicant of
$\neg T$ since the implicants of the parity function $\oplus_{i=1}^{n}x_{i}$
(or of its negation) depend on every variable $x_{i}$
($i\in\\{1,\ldots,n\\}$). Therefore, $t_{\bm{x}}$ is the unique majoritary
reason for $\bm{x}$ given $F$ and it contains $n$ characteristics. But since
$F$ is valid, $\top$ is the unique sufficient reason for $\bm{x}$ given $F$. ∎

Proof of Proposition 7

###### Proof.

  * •

Membership to NP: if there exists a minimal majoritary reason $t$ for $\bm{x}$
given $F$ such that $t$ contains at most $k$ features, then one can guess $t$
using a nondeterministic algorithm running in polynomial time (the size of $t$
is bounded by the size of $\bm{x}$), then check in polynomial time whether $t$
is a sufficient reason for $\bm{x}$ given $T$ for a majority of trees $T\in
F$, and finally check in polynomial time that the size of $t$ is upper bounded
by $k$.

  * •

NP-hardness: in the following, we focus only on the case when $F(\bm{x})=1$
(if $F(\bm{x})=0$, it is enough to consider the random forest $\neg F$ instead
of $F$; this is harmless given that $\neg F$ can be computed in time linear in
the size of $F$, see Proposition 1). We assume that $m=1$, i.e., $F$ consists
of a single decision tree $T\in{\tt DT}_{n}$.

We call Minimal Sufficient Reason the problem that asks, given $T\in{\tt
DT}_{n}$, $\bm{x}\in\\{0,1\\}^{n}$ with $T(x)=1$ and $k\in\mathbb{N}$, whether
there is an implicant $t$ of $T$ of size at most $k$ that covers $\bm{x}$.

Our objective is to prove that Minimal Sufficient Reason is NP-hard. To this
end, let us first recall that a _vertex cover_ of an undirected graph
$G=(X,E)$ is a subset $V\subseteq X$ of vertices such that $\\{y,z\\}\cap
V\neq\varnothing$ for every edge $e=\\{y,z\\}$ in $E$. In the Min Vertex Cover
problem, we are given a graph $G$ together with an integer $k\in\mathbb{N}$,
and the task is to find a vertex cover $V$ of $G$ of size at most $k$. Min
Vertex Cover is a well-known NP-hard problem [20], and we now show that it can
be reduced in polynomial time to Minimal Sufficient Reason.

Suppose that we are given a graph $G=(X,E)$ and assume, without loss of
generality, that $G$ does not include isolated vertices. For any $y\in X$, let
$E_{y}=\\{e\in E:y\in e\\}$ denote the set of edges in $G$ that are adjacent
to $y$, and let $N_{y}=\\{z\in X:\\{y,z\\}\in E\\}$ denote the set of
neighbors of $y$ in $G$. By $G\setminus y$, we denote the deletion of $y$ from
$G$, obtained by removing $y$ and its adjacent edges, i.e., $G\setminus
y=(X\setminus\\{y\\},E\setminus E_{y})$. We associate with $G$ a decision tree
$T(G)$ over $X_{n}=X$ using the following recursive algorithm. If $G$ is the
empty graph (i.e. $E=\varnothing$), then return the decision tree rooted at a
$1$-leaf. Otherwise, pick a node $y\in X$ and generate a decision tree $T(G)$
such that:

    1. (1)

the root is labeled by $y$;

    2. (2)

the left child is the decision tree encoding the monomial $\bigwedge N_{y}$;

    3. (3)

the right child is the decision tree $T(G^{\prime})$ returned by calling the
algorithm on $G^{\prime}=G\setminus y$.

By construction, $T(G)$ is a complete backtrack search tree of the formula
${\tt CNF}(E)=\bigwedge\\{(y\lor z):\\{y,z\\}\in E\\}$, which implies that
$T(G)$ and ${\tt CNF}(E)$ are logically equivalent. Furthermore, $T(G)$ is a
comb-shaped tree since recursion only on the rightmost branch. In particular,
the algorithm runs in $\mathcal{O}(n|E|)$ time, since step (1) takes
$\mathcal{O}(1)$ time, step (2) takes $\mathcal{O}(n)$ time, and step (3) is
called at most $|E|$ times.

Now, with an instance $\bm{P}_{1}=(G,k)$ of Min Vertex Cover, we associate the
instance $\bm{P}_{2}=(T(G),\bm{x},k)$ of Minimal Sufficient Reason, where
$\bm{x}=(1,\cdots,1)$. Based on the above algorithm, $\bm{P}_{2}$ can be
constructed in time polynomial in the size of $\bm{P}_{1}$.

Let $V$ be a solution of $\bm{P}_{1}$. Since $V$ is a vertex cover of $G$, the
term $t_{V}=\bigwedge V$ is an implicant of the formula ${\tt CNF}(E)$. Since
$t_{V}\subseteq t_{\bm{x}}$ and $|t_{V}|\leq k$, it follows from the fact that
${\tt CNF}(E)$ and $T(G)$ are logically equivalent that $t_{V}$ is a solution
of $\bm{P}_{2}$.

Conversely, let $t$ be a solution of $\bm{P}_{2}$. Since $t$ is an implicant
of $T(G)$, it follows that $t$ is an implicant of ${\tt CNF}(E)$. This
together with the fact that $t\subseteq t_{\bm{x}}$ implies that the subset of
vertices $V\subseteq X_{n}$, satisfying $\bigwedge V=t$, is a vertex cover of
$G$. Since $|V|\leq k$, it is therefore a solution of $\bm{P}_{1}$.

∎

Proof of Proposition 8

###### Proof.

Let us first recall that the forgetting $\exists V.f$ of a set of variables
$V$ in a formula $f$ denotes a formula that is a most general consequence of
$f$ that is independent of $V$ (in the sense that it is equivalent to a
formula where no variable from $V$ occurs) [21].

Let $\bm{z}^{*}$ be any optimal solution of
$(C_{\mathrm{soft}},C_{\mathrm{hard}})$. On the one hand, $\bm{z}^{*}$ is a
model of $C_{\mathrm{hard}}$. Let $V$ be the set of variables occurring in
$C_{\mathrm{hard}}$ but not in $X_{n}$. Since $\bm{z}^{*}\models
C_{\mathrm{hard}}$, we have that $\exists V.\bm{z}^{*}\models\exists
V.C_{\mathrm{hard}}$ (see [21]). Stated otherwise, the projection $\exists
V.\bm{z}^{*}$ of $\bm{z}^{*}$ on $X_{n}$ implies the projection of
$C_{\mathrm{hard}}$ on $X_{n}$.

On the other hand, by construction, a consistent term $t$ over $X_{n}$ implies
the projection of $C_{\mathrm{hard}}$ on $X_{n}$ if and only if $t$ is an
implicant of more than $\frac{m}{2}$ decision trees of $F$. Thus, the term
$\exists V.\bm{z}^{*}$ is an implicant of more than $\frac{m}{2}$ decision
trees of $F$.

Finally, if $\bm{z}^{*}$ is an optimal solution of
$(C_{\mathrm{soft}},C_{\mathrm{hard}})$, then $\bm{z}^{*}$ satisfies a maximal
number of soft clauses from $C_{\mathrm{soft}}$. Since those soft clauses are
precisely the negations of the literals occurring in $t_{\bm{x}}$, the term
$t_{\bm{z}^{*}}\cap t_{\bm{x}}$ obtained from $\exists V.\bm{z}^{*}$ by
removing every literal that coincides with a soft clause is still an implicant
of more than $\frac{m}{2}$ decision trees of $F$. Indeed, $C_{\mathrm{hard}}$
is monotone on $X_{n}$ and the polarity of every variable of $X_{n}$ in
$C_{\mathrm{hard}}$ is the same as its polarity in $t_{\bm{x}}$. Since
$\bm{z}^{*}$ satisfies a maximal number of soft clauses, $t_{\bm{z}^{*}}\cap
t_{\bm{x}}$ contains a minimal number of literals. As $t_{\bm{z}^{*}}\cap
t_{\bm{x}}\subseteq t_{\bm{x}}$, $t_{\bm{z}^{*}}\cap t_{\bm{x}}$ is a minimal
majoritary reason for $\bm{x}$ given $F$. ∎