# On Explaining Random Forests with SAT

Yacine Izza1 Joao Marques-Silva2 1ANITI, Univ. Toulouse, France
2IRIT, CNRS, Toulouse, France
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Random Forests (RFs) are among the most widely used Machine Learning (ML)
classifiers. Even though RFs are not interpretable, there are no dedicated
non-heuristic approaches for computing explanations of RFs. Moreover, there is
recent work on polynomial algorithms for explaining ML models, including naive
Bayes classifiers. Hence, one question is whether finding explanations of RFs
can be solved in polynomial time. This paper answers this question negatively,
by proving that deciding whether a set of literals is a PI-explanation of an
RF is $\textnormal{D}^{\textnormal{P}}$-complete. Furthermore, the paper
proposes a propositional encoding for computing explanations of RFs, thus
enabling finding PI-explanations with a SAT solver. This contrasts with
earlier work on explaining boosted trees (BTs) and neural networks (NNs),
which requires encodings based on SMT/MILP. Experimental results, obtained on
a wide range of publicly available datasets, demonstrate that the proposed
SAT-based approach scales to RFs of sizes common in practical applications.
Perhaps more importantly, the experimental results demonstrate that, for the
vast majority of examples considered, the SAT-based approach proposed in this
paper significantly outperforms existing heuristic approaches.

##  1 Introduction

The recent successes of Machine Learning (ML), and the forecast continued
growth of ML-enabled applications, including applications that impact human
beings or that are even safety critical, has raised the need for identifying
explanations for the predictions made by ML models. As a result, recent years
witnessed the rapid growth of the field of explainable Artificial Intelligence
(XAI) (see e.g. Guidotti et al. (2019); Li et al. (2018); Montavon et al.
(2018); Shih et al. (2018, 2019); Ribeiro et al. (2016, 2018); Ignatiev et al.
(2019); Ignatiev (2020); Audemard et al. (2020); Ignatiev et al. (2020);
Ignatiev and Marques-Silva (2021); Marques-Silva et al. (2021)).
Unfortunately, the most promising ML models, including neural networks or
ensembles of classifiers, due to their size and intrinsic complexity, are
generally accepted to be non-interpretable (or black-box), with the
understanding that the predictions made by such black-box models cannot be
understood by human decision makers.

A large body of work on XAI is based on heuristic approaches Ribeiro et al.
(2016); Lundberg and Lee (2017); Ribeiro et al. (2018), offering no formal
guarantees regarding computed explanations111For example, an explanation $E$,
for an input $I_{1}$ resulting in prediction $A$, can also be consistent with
input $I_{2}$ resulting in prediction $B\not=A$ Ignatiev (2020). Such _loose_
explanations inevitably raise concerns in applications where safety is
critical.. In contrast, recent work focused on non-heuristic approaches which
offer formal guarantees with respect to computed explanations Shih et al.
(2018); Ignatiev et al. (2019); Shih et al. (2019); Ignatiev (2020); Darwiche
and Hirth (2020); Audemard et al. (2020); Marques-Silva et al. (2020);
Ignatiev et al. (2020); Ignatiev and Marques-Silva (2021); Marques-Silva et
al. (2021).

Approaches to explainability can also be characterized as being model-agnostic
or model-precise222Orthogonal to the goals of the paper is the classification
of explanations as _local_ or _global_ Guidotti et al. (2019). . Model-
agnostic approaches do not require information about the ML model
representation, thus allowing the explanation of any class of ML models. In
contrast, in model-precise approaches, some representation of the concrete ML
model is reasoned about, and so these are characterized by being model-
specific. Whereas model-agnostic approaches are in general heuristic, model-
precise approaches can either be non-heuristic Shih et al. (2018); Ignatiev et
al. (2019); Shih et al. (2019); Ignatiev (2020); Darwiche and Hirth (2020);
Audemard et al. (2020); Marques-Silva et al. (2020); Ignatiev et al. (2020);
Ignatiev and Marques-Silva (2021); Marques-Silva et al. (2021) or heuristic
Zhao et al. (2019); Petkovic et al. (2018); Mollas et al. (2020). For model-
precise non-heuristic approaches different solutions have been investigated.
Shih et al. (2018) propose an approach for explaining Bayesian network
classifiers, which is based on compiling such classifiers into Ordered
Decision Diagrams representing all prime implicants of the boolean function
representing the target class predictions. These represent the so-called PI-
explanations (which we revisit in Section 2). A different approach, based on
abductive reasoning Ignatiev et al. (2019); Ignatiev (2020), exploits
automated reasoning tools (e.g. SMT, MILP, etc.) with explanations being
computed on demand. In abductive reasoning approaches, the ML model is
represented as a set of constraints and, given some target instance, a prime
implicant is computed, which represents a minimal set of feature-value pairs
that is sufficient for the prediction. Earlier work investigated encodings of
neural networks Ignatiev et al. (2019) and of boosted trees Ignatiev (2020).

This paper extends earlier work on model-precise non-heuristic explainability.
Concretely, the paper proposes a novel approach for computing PI (or
abductive) explanations (AXps) of Random Forest classifiers Breiman (2001);
Yang et al. (2020); Zhang et al. (2019); Gao and Zhou (2020); Feng and Zhou
(2018); Zhou and Feng (2017). Random Forests (RFs) represent a widely used
tree ensemble ML model, where each RF ML model is composed of a number of
decision trees (DTs). (The importance of RFs is further illustrated by recent
proposals for implementing deep learning (DL) with RFs Zhou and Feng (2017);
Zhang et al. (2019); Feng and Zhou (2018).)

In contrast with earlier work Ignatiev (2020), we show that in the case of RFs
it is possible to devise a purely propositional encoding. In turn, this
enables achieving very significant performance gains. Concretely, the
experimental results show that our approach is able to compute explanations of
realistically-sized RFs most often in a fraction of a second. The experiments
also show that our approach is on average more than one order of magnitude
faster than a state of the art model-agnostic heuristic approach Ribeiro et
al. (2018).

Recent work on model-precise non-heuristic explainability has shown that some
ML models can be explained in polynomial time Audemard et al. (2020); Marques-
Silva et al. (2020). In contrast, this paper proves that it is
$\textnormal{D}^{\textnormal{P}}$-complete to decide whether a set of literals
is a PI-explanation (AXp) of an RF, thus making it unlikely that RFs can be
explained in polynomial time.

The paper is organized as follows. Section 2 covers the preliminaries. Section
3 proves the complexity of deciding whether a set of literals is an
explanation for an RF. Section 4 proposes a propositional encoding for
computing one AXp of an RF. Section 5 presents the experimental results.
Finally, Section 6 concludes the paper.

##  2 Preliminaries

### ML Classification.

We consider a machine learning classification problem, defined by a set of
features ${\mathcal{F}}=\\{1,\ldots,m\\}$, and by a set of classes
${\mathcal{K}}=\\{c_{1},c_{2},\ldots,c_{K}\\}$. Each feature
$j\in{\mathcal{F}}$ takes values from a domain $\mathbb{D}_{i}$. (Domains may
correspond to Boolean, Categorical or Continuous data.) Thus, feature space is
defined as
$\mathbb{F}=\mathbb{D}_{1}\times{\mathbb{D}_{2}}\times\ldots\times{\mathbb{D}_{m}}$.
To refer to an arbitrary point in feature space we use the notation
$\mathbf{x}=(x_{1},\ldots,x_{m})$, whereas to refer to a specific point in
feature space we use the notation $\mathbf{v}=(v_{1},\ldots,v_{m})$, with
$v_{i}\in{\mathbb{D}_{i}}$, $i=1,\ldots,m$. An _instance_ (or example) denotes
a pair $(\mathbf{v},c)$, where $\mathbf{v}\in\mathbb{F}$ and
$c\in{\mathcal{K}}$. An ML classifier is characterized by a classification
function $\tau$ that maps the feature space $\mathbb{F}$ into the set of
classes ${\mathcal{K}}$, i.e. $\tau:\mathbb{F}\to{\mathcal{K}}$. To learn a
classifier, a set of instances
$\\{(\mathbf{v}_{1},c_{1}),\ldots,(\mathbf{v}_{k},c_{k})\\}$ is used as
training data by a learning algorithm that returns a function with a best fit
on the training data.

### Decision Tree and Random Forest Classifiers.

Decision trees rank among the most widely-used techniques ML models Breiman et
al. (1984); Quinlan (1993). Formally, a decision tree
${\mathcal{T}}=(V_{{\mathcal{T}}},E_{{\mathcal{T}}})$ is a directed acyclic
graph, where the root node has no incoming edges, and every other node has
exactly one incoming edge. The nodes of a tree are partitioned into terminal
($V_{T}$) and non-terminal ($V_{NT}$) nodes. Terminal nodes denote the leaf
nodes, and have no outgoing edges (i.e. children). Non-terminal nodes denote
the internal nodes, and have outgoing edges. Each terminal node $j\in{V_{T}}$
is associated with a class taken from ${\mathcal{K}}$. We define a map
$\kappa:V_{T}\to{\mathcal{K}}$ to represent the class associated with each
terminal node. Each non-terminal node is associated with a feature taken from
a set of features ${\mathcal{F}}$. Given a feature $j\in{{\mathcal{F}}}$
associated with a non-terminal node $l$, each outgoing edge represents a
literal of the form $x_{j}\bowtie S_{j}$, where either
$S_{j}\in\mathbb{D}_{j}$ or $S_{j}\subseteq\mathbb{D}_{j}$ 333Features are
either categorical (including boolean) or real- or integer-valued ordinal, and
$\bowtie\>\in{\\{=,\in\\}}$. (Observe that these operators allow for intervals
to be represented.). Each path in ${\mathcal{T}}$ is associated with a
consistent conjunction of literals, denoting the values assigned to the
features so as to reach the terminal node in the path. We will represent the
set of literals of some tree path $R_{k}$ by ${\mathcal{L}}(R_{k})$.

A well-known drawback of decision trees is overfitting with respect to the
training data. In contrast, tree ensembles such as Random Forests (RFs)
Breiman (2001) combine several tree-based models, which allows for improved
accuracy and ability to generalize beyond the training data. More formally, an
RF $\mathfrak{F}$ is a collection of decision trees (DTs)
$\mathfrak{F}=\\{{\mathcal{T}}_{1},{\mathcal{T}}_{2},\ldots,{\mathcal{T}}_{M}\\}$.
Each tree ${\mathcal{T}}_{i}\in{\mathfrak{F}}$ is trained on a subsample of
the training dataset so as the trees of the RF are not correlated. The
prediction function in RF works by majority vote, that is each tree votes for
a class and the most voted class is picked. (In case of ties, for simplicitly
we will pick the lexicographically smallest class.)

### Running Example.

Let us assume a simple binary classification problem for predicting whether or
not a patient has a heart disease. The class variables are: Yes and No (Yes to
classify the patient as suffering from heart disease and No to classify the
patient as without heart disease.) and a set of features in the following
order: blocked-arteries, good-blood-circulation, chest-pain, and weight, where
features 1, 2 and 3 represent Boolean variables, and feature 4 represents an
ordinal variable. Let the set of trees, shown in Figure 1, be the tree
ensemble of an RF classifier $\mathfrak{F}$ trained on the heart disease
problem and $\tau$ its classification function. There are 3 trees in the
forest and each tree has a maximum depth of 2. Assume we have an instance
$\mathbf{v}=(1,0,1,70)$, namely, blocked-arteries = 1, good-blood-circulation
= 0, chest-pain = 1, weight = 70. Hence, Trees 1 and 3 vote for Yes and Tree 2
votes for No. As the majority votes go for Yes, then the classifier will
return Yes for $\mathbf{v}$, i.e. $\tau(\mathbf{v})=\textit{Yes}$.

(a) Tree 1 (b) Tree 2

(c) Tree 3

Figure 1: Running example.

### Boolean satisfiability (SAT).

The paper assumes the notation and definitions standard in SAT Biere et al.
(2021), i.e. the decision problem for propositional logic, which is known to
be NP-complete Cook (1971). A propositional formula $\varphi$ is defined over
a finite set of Boolean variables $X=\\{x_{1},x_{2},\ldots,x_{n}\\}$. Formulas
are most often represented in _conjunctive normal form_ (CNF). A CNF formula
is a conjunction of clauses, a clause is a disjunction of literals, and a
literal is a variable ($x_{i}$) or its negation ($\neg{x_{i}}$). Whenever
convenient, a formula is viewed as a set of sets of literals. A Boolean
interpretation $\mu$ of a formula $\varphi$ is a total mapping of $X$ to
$\\{0,1\\}$ ($0$ corresponds to _False_ and $1$ corresponds to _True_).
Interpretations can be extended to literals, clauses and formulas with the
usual semantics; hence we can refer to $\mu(l)$, $\mu(\omega)$,
$\mu(\varphi)$, to denote respectively the value of a literal, clause and
formula given an interpretation. Given a formula $\varphi$, $\mu$ is a _model_
of $\varphi$ if it makes $\varphi$ _True_ , i.e. $\mu(\phi)=1$. A formula
$\varphi$ is _satisfiable_ ($\varphi\operatorname*{\nvDash}\perp$) if it
admits a model, otherwise, it is _unsatisfiable_
($\varphi\operatorname*{\vDash}\perp$). Given two formulas $\varphi$ and
$\psi$, we say that $\varphi$ entails $\psi$ (denotes
$\varphi\operatorname*{\vDash}\psi$) if all models of $\varphi$ are also
models of $\psi$. $\varphi$ and $\psi$ are equivalent (denoted
$\varphi\equiv\psi$) if $\varphi\operatorname*{\vDash}\psi$ and
$\psi\operatorname*{\vDash}\varphi$.

### Abductive explanations.

The paper uses the definition of PI-explanation Shih et al. (2018) (also
referred to as abductive explanation (AXp) in Ignatiev et al. (2019))
444Throughout the paper we will use both terms PI-explanation and abductive
explanation (AXp) interchangeably., based on prime implicants of some decision
function (related with the predicted class). Let us consider a given ML model,
computing a classification function $\tau$ on feature space $\mathbb{F}$, a
point $\mathbf{v}\in\mathbb{F}$, with prediction $c=\tau(\mathbf{v})$, with
$\mathbf{v}=(v_{1},\ldots,v_{m})$. A PI-explanation (AXp) is any minimal
subset ${\mathcal{X}}\subseteq{\mathcal{F}}$ such that:

$\forall(\mathbf{x}\in\mathbb{F}).\left[\bigwedge\nolimits_{i\in{{\mathcal{X}}}}(x_{i}=v_{i})\right]\operatorname*{\rightarrow}(\tau(\mathbf{x})=c)$
(1)

In a similar vein, we consider contrastive explanations (CXps) Miller (2019).
A formal definition of contrastive explanation is proposed in recent work
Ignatiev et al. (2020).

### Contrastive explanations.

Contrastive explanation can be defined as a minimal subset
${\mathcal{Y}}\subseteq{\mathcal{F}}$ that suffice to changing the prediction
if features of ${\mathcal{Y}}$ are allowed to take some arbitrary value from
their domain. Given $\mathbf{v}=(v_{1},\ldots,v_{m})\in\mathbb{F}$ with
$\kappa(\mathbf{v})=c$, a CXp is any minimal subset
${\mathcal{Y}}\subseteq{\mathcal{F}}$ such that,

$\exists(\mathbf{x}\in\mathbb{F}).\bigwedge\nolimits_{j\in{\mathcal{F}}\setminus{\mathcal{Y}}}(x_{j}=v_{j})\land(\kappa(\mathbf{x})\not=c)$
(2)

Building on the results of R. Reiter in model-based diagnosis Reiter (1987),
Ignatiev et al. (2020) proves a minimal hitting set (MHS) duality relation
between AXps and CXps, i.e. AXps are MHSes of CXps and vice-versa.

######  Example 1.

Consider the binary classifier $\mathfrak{F}$ of the running example. and the
instance $(\mathbf{v}=(1,0,1,70),\mathit{Yes})$. If the features good-blood-
circulation and weight are allowed to take any possible value from their
domain, and the values of the features blocked-arteries and chest-pain are
kept to their values in $\mathbf{v}$, then the prediction is still Yes. This
means that the features good-blood-circulation and weight can be deemed
irrelevant for the prediction of Yes given the other feature values in
$\mathbf{v}$. Moreover, by allowing either blocked-arteries or chest-pain to
take any value, prediction will change to No. Hence, $\\{\textit{blocked-
arteries},\textit{chest-pain}\\}$ is a subset-minimal set of features
sufficient for predicting $\tau(\mathbf{v})=\textit{Yes}$, that is a PI-
explanation (AXp). Additionally, setting the value of blocked-arteries to 0
suffices to changing the prediction of $\mathbf{v}$ (i.e.
$\tau(0,0,1,70)=\textit{No}$), thus $\\{\textit{blocked-arteries}\\}$ is a
CXp.

##  3 Complexity of AXps for RFs

Recent work identified classes of classifiers for which one AXp can be
computed in polynomial time Audemard et al. (2020); Marques-Silva et al.
(2020). These classes of classifiers include those respecting specific
criteria of the knowledge compilation map Audemard et al. (2020)555The
knowledge compilation map was first proposed in 2002 Darwiche and Marquis
(2002)., but also Naive Bayes and linear classifiers (resp. NBCs and LCs)
Marques-Silva et al. (2020). (In the case of NBCs and LCs, enumeration of AXps
was shown to be solved with polynomial delay.) One question is thus whether
there might exist a polynomial time algorithm for computing one computing AXp
of an RF. This section shows that this is unlikely to be the case, by proving
that deciding whether a set of features represents an AXp is
$\textnormal{D}^{\textnormal{P}}$-complete666The class
$\textnormal{D}^{\textnormal{P}}$ Papadimitriou (1994) is the set of languages
defined by the intersection of two languages, one in NP and one in coNP..

Let $\mathfrak{F}$ be an RF, with classification function $\tau$, and let
$\mathbf{v}\in\mathbb{F}$, with prediction
$\tau(\mathbf{v})=c\in{\mathcal{K}}$. $\tau$ is parameterized with $c$, to
obtain the boolean function $\tau_{c}$, s.t. $\tau_{c}(\mathbf{x})=1$ iff
$\tau(\mathbf{x})=c$. A set of literals $I_{\mathbf{v}}$ is associated with
each $\mathbf{v}$. Let $\rho$ be a subset of the literals associated with
$\mathbf{v}$, i.e. $\rho\subseteq{I_{\mathbf{v}}}$. Hence,

######  Theorem 1.

For a random forest $\mathfrak{F}$, given an instance $\mathbf{v}$ with
prediction $c$, deciding whether a set of literals is an AXp is
$\textnormal{D}^{\textnormal{P}}$-complete.

Proof.  Given an instance $\mathbf{v}$ and predicted class $c$, deciding
whether a set of literals $\rho$ is an AXp of an RF $\mathfrak{F}$ is clearly
in $\textnormal{D}^{\textnormal{P}}$. We need to prove that
$\rho\operatorname*{\vDash}\tau_{c}$, which is a problem in coNP. We also need
to prove that a set of literals $\rho^{\prime}$, obtained by the removal of
any single literal from $\rho$ (and there can be at most $m$ of these), is
such that $\rho\operatorname*{\nvDash}\tau_{c}$, a problem in NP. To prove
that the problem is hard for $\textnormal{D}^{\textnormal{P}}$, we reduce the
problem of computing a prime implicant of a DNF, which is known to be complete
for $\textnormal{D}^{\textnormal{P}}$ Umans et al. (2006), to the problem of
computing a PI-explanation of an RF $\mathfrak{F}$.
Consider a DNF $\phi=t_{1}\lor\cdots\lor{t_{n}}$, where each term $t_{i}$ is a
conjunction of literals defined on a set $X=\\{x_{1},\ldots,x_{m}\\}$ of
boolean variables. Given $\phi$, we construct an RF $\mathfrak{F}$, defined on
a set ${\mathcal{F}}$ of $m$ features, where each feature $i$ is associated
with an $x_{i}$ element of $X$, and where $D_{i}=\\{0,1\\}$. Moreover,
$\mathfrak{F}$ is such that $\phi(\mathbf{x})=1$ iff $\tau_{1}(\mathbf{x})=1$.
$\mathfrak{F}$ is constructed as follows.

  1. i.

Associate a decision tree (DT) ${\mathcal{T}}_{i}$ with each term $t_{i}$,
such that the assignment satisfying $t_{i}$ yields class 1, and the other
assignments yield class 0. Clearly, the size of the DT ${\mathcal{T}}_{i}$ is
linear on the size of $t_{i}$, since each literal not taking the value
specified by the term will be connected to a terminal node with prediction 0.

  2. ii.

Create $(n-1)$ additional trees, each having exactly one terminal node and no
non-terminal nodes. Moreover, associate class $1$ with the terminal node.

Next, we prove that $\phi(\mathbf{x})=1$ iff $\tau_{1}(\mathbf{x})=1$.

  1. i.

Let $\mathbf{x}$ be such that $\phi(\mathbf{x})=1$. Then, there is at least
one term $t_{j}$, such that $t_{j}(\mathbf{x})=1$. As a result, the
corresponding tree ${\mathcal{T}}_{j}$ in the RF will predict class 1. Hence,
at least $n$ trees predict class 1, and at most $n-1$ trees predict class 0.
As a result, the predicted class is 1, and so $\tau_{1}(\mathbf{x})=1$.

  2. ii.

Let $\mathbf{x}$ be such that $\tau_{1}(\mathbf{x})=1$. This means that at
least one of the trees associated with the terms $t_{i}$ must predict value 1.
Let such tree be ${\mathcal{T}}_{j}$, associated with term $t_{j}$. For this
tree to predict class 1, then $t_{j}(\mathbf{x})=1$, and so
$\phi(\mathbf{x})=1$.

Now, let $\rho$ be a conjunction of literals defined on $X$. Then, we must
have $\rho\operatorname*{\vDash}\phi$ iff
$\rho\operatorname*{\vDash}\tau_{1}$. Every model of $\rho$ is also a model of
$\phi$, and so it must also be a model of $\tau_{1}$. Conversely, every model
of $\rho$ is also a model of $\tau_{1}$, and so it must also be a model of
$\phi$. $\Box$

##  4 AXps for Random Forests

This section outlines the computation of PI-explanations (AXps) for RFs. We
first present the algorithm’s organization. The algorithm requires a logical
encoding of RFs, which are presented next.

### Computing AXps.

A minimal set of features ${\mathcal{X}}\in{\mathcal{F}}$ is an AXp if (1)
holds. Clearly, this condition holds iff the following formula is
unsatisfiable,

$\left[\bigwedge\nolimits_{i\in{{\mathcal{X}}}}(x_{i}=v_{i})\right]\land\mathsf{Enc}(\tau(\mathbf{x})\not=c)$

The previous formula has two components
$\langle{\mathcal{H}},{\mathcal{S}}\rangle$. ${\mathcal{H}}$ represents the
set of hard clauses, encoding the representation of the ML model and also
imposing a constraint on the predicted class, i.e.
$\mathsf{Enc}(\tau(\mathbf{x})\not=c)$. ${\mathcal{S}}$ represents the unit
(_soft_) clauses, each capturing a literal $(x_{i}=v_{i})$. Since the clauses
in ${\mathcal{S}}$ are _soft_ , they can be _dropped_ (thus allowing $x_{i}$
to take any value) while searching for a minimal subset of ${\mathcal{E}}$ of
${\mathcal{S}}$, such that,

$\left[\bigwedge\nolimits_{(x_{1}=v_{i})\in{\mathcal{E}}}(x_{i}=v_{i})\right]\land\mathsf{Enc}(\tau(\mathbf{x})\not=c)$

is unsatisfiable. Our goal is to find a minimal set ${\mathcal{S}}$ such that
the pair $\langle{\mathcal{H}},{\mathcal{S}}\rangle$ remains unsatisfiable
(where ${\mathcal{S}}$ can be viewed as the background knowledge against which
the clauses in ${\mathcal{S}}$ are inconsistent). This corresponds to finding
a minimal unsatisfiable subset (MUS) of
$\langle{\mathcal{H}},{\mathcal{S}}\rangle$, and so any off-the-shelve MUS
extraction algorithm can be used for computing an AXp (as noted in earlier
work Ignatiev et al. (2019)).

Clearly, adapting the descibed procedure above of computing one AXp to one
that computes a CXp is straightforward. That is, the minimal set
${\mathcal{Y}}$ of ${\mathcal{S}}$ to search is, such that,

$\left[\bigwedge\nolimits_{(x_{1}=v_{i})\in{\mathcal{S}}\setminus{\mathcal{Y}}}(x_{i}=v_{i})\right]\land\mathsf{Enc}(\tau(\mathbf{x})\not=c)$

is satisfiable. Further, hitting set duality between AXps and CXps allows to
exploit any algorithm for computing MUSes/MCSes777An MCS is a minimal set of
clauses to remove from an unsatisfiable CNF formula to recover consistency .
It is well-known that MCSes are minimal hitting sets of MUSes and vice-versa
Reiter (1987); Birnbaum and Lozinskii (2003). to enumerate both kinds of
explanations (AXps and CXps). (Recent work Ignatiev et al. (2020); Marques-
Silva et al. (2021); Ignatiev and Marques-Silva (2021) exploits the MUS/MCS
enumeration algorithm MARCO Liffiton et al. (2016) for enumerating AXps/CXps.)

We detail next how to encode an RF, while requiring some prediction not to
hold. We start with a simple encoding of an RF into an SMT formula, and then
we detail a purely propositional encoding, which enables the use of SAT
solvers.

### SMT Encoding.

Several encodings of tree ensemble models, such as Boosted Trees (BTs), have
been proposed and they are essentially based on SMT/MILP (see e.g. Chen et al.
(2019); Einziger et al. (2019); Ignatiev (2020), etc). Hence, it is natural to
follow prior work and propose a straightforward encoding of RFs in SMT.
Intuitively, the formulation of RFs into SMT formulas is as follows. We encode
every single DT of an RF as a set of implication rules. That is, a DT path
(classification rule) is interpreted as a rule of the form
$\textit{antecedent}\operatorname*{\rightarrow}\textit{consequent}$ where the
antecedent is a conjunction of predicates encoding the non-terminal nodes of
the path and the consequent is a predicate representing the class associated
with the terminal node of the path. Next, we aggregate the prediction (votes)
of the DTs and count the prediction score for each class. This can be
expressed by an arithmetic function that calculates the sum of trees
predicting the same class. Lastly, a linear inequality checks which class has
the largest score.

The implementation of the encoding above resulted in performance results
comparable to those of BTs Ignatiev (2020). However, in the case of RFs it is
possible to devise a purely propositional encoding, as detailed below.

### SAT Encoding.

Our goal is to represent the structure of an RF with a propositional formula.
This requires abstracting away what will be shown to be information used by
the RF that is unnecessary for finding an AXp. Concretely, and as shown below,
the actual values of the features used as literals in the RF need not be
considered when computing one AXp. We start by detailing how to encode the
nodes of the decision trees in an RF. This is done such that the actual values
of the features are abstracted away. Then, we present the encoding of the RF
classifier itself, including how the majority voting is represented.

To encode a terminal node of a DT, we proceed as follows. Given a set of
classes ${\mathcal{K}}=\\{c_{1},c_{2},\ldots,c_{K}\\}$, a terminal node $t$
labeled with one class of ${\mathcal{K}}$. Then, we define for each
$c_{j}\in{{\mathcal{K}}}$ a variable $l_{j}$ and represent the terminal node
$t$ with its corresponding label class $c_{j}$, i.e. $\kappa(t)=c_{j}$.

Moreover, the encoding of a non-terminal node of a DT is organized as follows.
Given a feature $j\in{{\mathcal{F}}}$ associated with a non-terminal node $l$,
with a domain $\mathbb{D}_{j}$, each outgoing edge of $l$ is represented by a
literal $l_{j}$ of the form $x_{j}\bowtie S_{j}$ s.t.
$x_{j}\in{{\mathcal{F}}}$ is the variable of feature $j$,
$S_{j}\bowtie\mathbb{D}_{j}$ and $\bowtie\>\in{\\{=,\subseteq,\in\\}}$. Hence
we distinguish three cases for encoding $x_{j}\bowtie S_{j}$. For the first
case, feature $j$ is binary, and so the literal $l_{j}$ is True if $x_{j}=1$
and False if $x_{j}=0$. For the second case, feature $j$ is categorical, and
so we introduce a Boolean variable $z_{i}$ for each value
$v_{i}\in\mathbb{D}_{j}$ s.t. $z_{i}=1$ iff $x_{j}=v_{i}$. Assume
$S_{j}=\\{v_{1},\ldots,v_{n}\\}$, then we connect $l_{j}$ to variables
$z_{i},i=1,\ldots,n$ as follows:
$l_{j}\operatorname*{\leftrightarrow}(z_{1}\vee\ldots\vee z_{n})$ or $\neg
l_{j}\operatorname*{\leftrightarrow}(z_{1}\vee\ldots\vee z_{n})$, depending on
whether the current edge is going to left or right child-node. Finally, for
the third case, feature $j$ is real-valued. Thus, $S_{j}$ is either an
interval or a union of intervals. Concretely, we consider all the splitting
thresholds of the feature $j$ existing in the RF and we generate (in order)
all the possible intervals. Each interval $I_{i}\subseteq\mathbb{D}_{j}$ is
denoted by a Boolean variable $z_{i}$. Let us assume
$S_{j}=I_{1}\cup\ldots\cup I_{n}$ and $z_{1},\ldots,z_{n}$ are variables
associated with $I_{1}\cup\ldots\cup I_{n}$, then we have
$l_{j}\operatorname*{\leftrightarrow}(z_{1}\vee\ldots\vee z_{n})$ or $\neg
l_{j}\operatorname*{\leftrightarrow}(z_{1}\vee\ldots\vee z_{n})$. Moreover,
this encoding can be reduced into a more compact set of constraints (that also
improves propagation in the SAT solver). Indeed, if the number of intervals is
large the encoding will be as well. Hence, we propose to use auxiliary
variables in the encoding. Assume $\mathbb{D}_{j}=I_{1}\cup I_{2}\cup I_{3}$,
nodes $l$ and $l^{\prime}$ s.t. $\neg
l_{j}\operatorname*{\leftrightarrow}z_{1}$, $\neg
l_{j}\operatorname*{\leftrightarrow}(z_{1}\vee z_{2}\vee z_{3})$, $\neg
l_{j}^{\prime}\operatorname*{\leftrightarrow}(z_{1}\vee z_{2})$,
$l_{j}^{\prime}\operatorname*{\leftrightarrow}z_{3}$, then this can be re-
written as: $\neg l_{j}\operatorname*{\leftrightarrow}z_{1}$,
$l_{j}\operatorname*{\leftrightarrow}(z_{2}\vee l_{j}^{\prime})$, $\neg
l_{j}^{\prime}\operatorname*{\leftrightarrow}(z_{2}\vee\neg l_{j})$,
$l_{j}^{\prime}\operatorname*{\leftrightarrow}z_{3}$.

The next step is to encode the RF classifier. Given an RF $\mathfrak{F}$
formed by a set of $M$ DTs, i.e.
$\mathfrak{F}=\\{{\mathcal{T}}_{1},{\mathcal{T}}_{2},\ldots,{\mathcal{T}}_{M}\\}$,
and $\tau$ the classification function of $\mathfrak{F}$. For every DT
${\mathcal{T}}_{i}\in\mathfrak{F}$, we encode the set of paths
${\mathcal{R}}_{i}$ of ${\mathcal{T}}_{i}$ as follows:

$\bigwedge\nolimits_{R_{k}\in{{\mathcal{R}}_{i}}}\left(\left(\bigwedge\nolimits_{l_{j}\in{\mathcal{L}}(R_{k})}l_{j}\right)\operatorname*{\rightarrow}l_{ij}\right)$
(3)

where $l_{ij}$ is a literal associated with ${\mathcal{T}}_{i}$ in which the
voted class is $c_{j}\in{{\mathcal{K}}}$.

For every DT ${\mathcal{T}}_{i}\in\mathfrak{F}$, and every path
$R_{k}\in{{\mathcal{R}}_{i}}$, we enforce the condition that exactly one
variable $l_{ij}$ is True in ${\mathcal{T}}_{i}$ 888Only one class is returned
by ${\mathcal{T}}_{i}$.. This can be expressed as999We use the well-known
cardinality networks Asín et al. (2011) for encoding all the cardinality
constraints of the proposed encoding.:

$\left(\bigvee\nolimits_{j=1}^{K}l_{ij}\right)~{}\wedge~{}\sum\nolimits_{j=1}^{K}l_{ij}\leq
1$ (4)

Finally, for capturing the majority voting used in RFs, we need to express the
constraint that the counts (of individual tree selections) for some class
$c_{k}\not=c_{j}$ have to be large enough (i.e. greater than, or greater than
or equal to) when compared to the counts for class $c_{j}$. We start by
showing how cardinality constraints can be used for expressing such
constraints. The proposed solution requires the use of $K-1$ cardinality
constraints, each comparing the counts of $c_{j}$ with the counts of some
other $c_{k}$. Afterwards, we show how to reduce to 2 the number of
cardinality constraints used.

Let $c_{j}\in{\mathcal{K}}$ be the predicted class. The index $j$ is relevant
and ranges from 1 to $K=|{\mathcal{K}}|$. Moreover, let $1\leq{k}<{j}\leq{K}$.
Class $c_{k}$ is selected over class $c_{j}$ if:

$\small\sum\nolimits_{i=1}^{M}l_{ik}>\sum\nolimits_{i=1}^{M}l_{ij}\Leftrightarrow\sum\nolimits_{i=1}^{M}l_{ik}+\sum\nolimits_{i=1}^{M}\neg{l_{ij}}\geq{M}$
(5)

Similarly, let $1\leq{j}<{k}\leq{K}$. Class $c_{k}$ is selected over class
$c_{j}$ if:

$\small\sum\nolimits_{i=1}^{M}l_{ik}>\sum\nolimits_{i=1}^{M}l_{ij}\Leftrightarrow\sum\nolimits_{i=1}^{M}l_{ik}+\sum\nolimits_{i=1}^{M}\neg{l_{ij}}\geq{M+1}$
(6)

(A simple observation is that these constraints can be optimized for the case
$|{\mathcal{K}}|=2$.)

It is possible to reduce the number of cardinality constraints as follows. Let
us represent (5) and (6), respectively, by
$\mathsf{Cmp}_{\prec}(z^{\prec}_{1},\ldots,z^{\prec}_{M})$ and
$\mathsf{Cmp}_{\succ}(z^{\succ}_{1},\ldots,z^{\succ}_{M})$. (Observe that the
encodings of these constraints differ (due to the different RHSes).) Moreover,
in (5) and (6) we replace $(z^{\prec}_{1},\ldots,z^{\prec}_{M})$ and
$(z^{\succ}_{1},\ldots,z^{\succ}_{M})$ resp. by $l_{1k},\ldots,l_{Mk}$, for
some $k$. The idea is that we will _only_ use two cardinality constraints, one
for (5) and one for (6).

Let $p_{k}=1$ iff $k$ is to be compared with $j$. In this case,
$\mathsf{Cmp}_{\bowtie}(z^{\bowtie}_{1},\ldots,z^{\bowtie}_{M})$ (where
$\bowtie$ is either $\prec$ or $\succ$) is comparing the class counts of
$c_{j}$ with the class counts of some $c_{k}$. Let us use the constraint
$p_{k}\operatorname*{\rightarrow}(z^{\bowtie}_{i}\leftrightarrow{l_{ik}})$,
with $k\in\\{1,\ldots,{K}\\}\setminus\\{j\\}$, and $1\leq{i}\leq{M}$. This
serves to allow associating the (free) variables
$(z^{\bowtie}_{1},\ldots,z^{\bowtie}_{M})$ with some set of literals
$(l_{1k},\ldots,l_{Mk})$. Moreover, we also let
$p_{0}\operatorname*{\rightarrow}(z^{\bowtie}_{i}\leftrightarrow{1})$ and
$p_{j}\operatorname*{\rightarrow}(z^{\bowtie}_{i}\leftrightarrow{1})$, i.e. we
allow $p_{0}$ and $p_{j}$ to pick _guaranteed winners_ , and such that
$\neg{p_{0}}\lor\neg{p_{j}}$. Essentially, we allow for a guaranteed winner to
be picked below $j$ or above $j$, but not both. Clearly, we must pick one $k$,
either below or above $j$, to pick a class $c_{k}$, when comparing the counts
of $c_{k}$ and $c_{j}$. We do this by picking two winners, one below $j$ and
one above $j$, and such that at most one is allowed to be a guaranteed winner
(either 0 or $j$):

$\left(\sum\nolimits_{r=0}^{j-1}p_{r}=1\right)\>\land\>\left(\sum\nolimits_{r=j}^{K}p_{r}=1\right)$

Observe that, by starting the sum at 0 and $j$, respectively, we allow the
picking of one guaranteed winner in each summation, if needed be. To
illustrate the described encoding above we consider again the running example.

######  Example 2.

Consider again the RF $\mathfrak{F}$ of the running example and the instance
$\mathbf{v}=(1,0,1,70)$, giving the prediction Yes. Let us define the Boolean
variables $x_{1},x_{2}$ and $x_{3}$ associated with the binary features
blocked-arteries, good-blood-circulation, chest-pain, resp. and variables
$w_{1}$ and $w_{2}$ representing $(\textit{weight}>75)$ and
$(\textit{weight}\leq 75)$ resp. and an auxiliary variable $w$. Also, to
represent the classes No and Yes, we associate variables denoting the classes
for each tree: $\\{l_{11},l_{12}\\}$ for ${\mathcal{T}}_{1}$,
$\\{l_{21},l_{22}\\}$ for ${\mathcal{T}}_{2}$ and $\\{l_{31},l_{32}\\}$ for
${\mathcal{T}}_{3}$. Hence, the corresponding set of encoding constraints is:
$\\{x_{1}\wedge x_{3}\operatorname*{\rightarrow}l_{12}$, $x_{1}\wedge\neg
x_{3}\operatorname*{\rightarrow}l_{11}$, $\neg
x_{1}\operatorname*{\rightarrow}l_{11}$,
$x_{2}\operatorname*{\rightarrow}l_{21}$, $\neg x_{2}\wedge
w\operatorname*{\rightarrow}l_{22}$, $\neg x_{2}\wedge\neg
w\operatorname*{\rightarrow}l_{21}$, $x_{2}\wedge
x_{1}\operatorname*{\rightarrow}l_{32}$, $x_{2}\wedge\neg
x_{1}\operatorname*{\rightarrow}l_{31}$, $\neg x_{2}\wedge
x_{3}\operatorname*{\rightarrow}l_{32}$, $\neg x_{2}\wedge\neg
x_{3}\operatorname*{\rightarrow}l_{31}$,
$w\operatorname*{\leftrightarrow}w_{1}$, $\neg
w\operatorname*{\leftrightarrow}w_{2}$, $(l_{11}+l_{21}+l_{31})\geq 2$,
$x_{1}$, $\neg x_{2}$, $x_{3}$, $w_{2}\\}$. Observe that $\\{x_{1},\neg
x_{2},x_{3},w_{2}\\}$ denotes the set of the soft constraints whereas the
remaining are the hard constraints.

##  5 Experimental Results

Dataset | (#F #C #I) | RF | CNF | SAT oracle | AXp (RFxpl) | Anchor
---|---|---|---|---|---|---
D | #N | %A | #var | #cl | MxS | MxU | #S | #U | Mx | m | avg | %w | avg | %w
ann-thyroid | $(21)$ | 3 |  $718$) | 4 | $2192$ | 98 | $17\,854$ | $29\,230$ | 0.12 | 0.15 | $2$ | $18$ | 0.36 | 0.05 | 0.13 | $96$ | 0.32 | $4$
appendicitis | $(7)$ | 2 |  $43$) | 6 | $1920$ | 90 | $5181$ | $10\,085$ | 0.02 | 0.02 | $4$ | $3$ | 0.05 | 0.01 | 0.03 | $100$ | 0.48 | $0$
banknote | $(4)$ | 2 |  $138$) | 5 | $2772$ | 97 | $8068$ | $16\,776$ | 0.01 | 0.01 | $2$ | $2$ | 0.03 | 0.02 | 0.02 | $100$ | 0.19 | $0$
biodegradation | $(41)$ | 2 |  $106$) | 5 | $4420$ | 88 | $11\,007$ | $23\,842$ | 0.31 | 1.05 | $17$ | $22$ | 2.27 | 0.04 | 0.29 | $97$ | 4.07 | $3$
ecoli | $(7)$ | 5 |  $66$) | 5 | $3860$ | 90 | $20\,081$ | $34\,335$ | 0.10 | 0.09 | $4$ | $2$ | 0.21 | 0.05 | 0.10 | $98$ | 0.38 | $2$
glass2 | $(9)$ | 2 |  $66$) | 6 | $2966$ | 90 | $7303$ | $15\,194$ | 0.04 | 0.03 | $5$ | $4$ | 0.09 | 0.02 | 0.03 | $100$ | 0.61 | $0$
heart-c | $(13)$ | 2 |  $61$) | 5 | $3910$ | 85 | $5594$ | $11\,963$ | 0.04 | 0.02 | $6$ | $7$ | 0.07 | 0.01 | 0.04 | $100$ | 0.85 | $0$
ionosphere | $(34)$ | 2 |  $71$) | 5 | $2096$ | 87 | $7174$ | $14\,406$ | 0.02 | 0.02 | $22$ | $11$ | 0.11 | 0.02 | 0.03 | $100$ | 12.43 | $0$
iris | $(4)$ | 3 |  $60$) | 6 | $1446$ | 93 | $16\,346$ | $25\,603$ | 0.02 | 0.01 | $2$ | $2$ | 0.05 | 0.02 | 0.03 | $100$ | 0.21 | $0$
karhunen | $(64)$ | 10 |  $200$) | 5 | $6198$ | 91 | $36\,708$ | $70\,224$ | 1.06 | 1.41 | $35$ | $29$ | 14.64 | 0.65 | 2.78 | $100$ | 28.15 | $0$
letter | $(16)$ | 26 |  $398$) | 8 | $44\,304$ | 82 | $28\,991$ | $68\,148$ | 1.97 | 3.31 | $8$ | $8$ | 6.91 | 0.24 | 1.61 | $70$ | 2.48 | $30$
magic | $(10)$ | 2 |  $381$) | 6 | $9840$ | 84 | $29\,530$ | $66\,776$ | 0.51 | 1.84 | $6$ | $4$ | 2.13 | 0.07 | 0.14 | $99$ | 0.91 | $1$
mofn-3-7-10 | $(10)$ | 2 |  $128$) | 6 | $8776$ | 92 | $2926$ | $8646$ | 0.00 | 0.01 | $3$ | $7$ | 0.02 | 0.01 | 0.01 | $100$ | 0.29 | $0$
new-thyroid | $(5)$ | 3 |  $43$) | 5 | $1766$ | 100 | $17\,443$ | $28\,134$ | 0.03 | 0.01 | $3$ | $2$ | 0.08 | 0.03 | 0.05 | $100$ | 0.36 | $0$
pendigits | $(16)$ | 10 |  $220$) | 6 | $12\,004$ | 95 | $30\,522$ | $59\,922$ | 2.40 | 1.32 | $10$ | $6$ | 4.11 | 0.14 | 0.94 | $96$ | 3.68 | $4$
phoneme | $(5)$ | 2 |  $540$) | 6 | $8962$ | 82 | $21\,899$ | $49\,840$ | 0.09 | 0.07 | $3$ | $2$ | 0.22 | 0.05 | 0.09 | $98$ | 0.37 | $2$
ring | $(20)$ | 2 |  $740$) | 6 | $6188$ | 89 | $19\,114$ | $42\,362$ | 0.27 | 0.44 | $11$ | $9$ | 1.25 | 0.05 | 0.25 | $92$ | 7.25 | $8$
segmentation | $(19)$ | 7 |  $42$) | 4 | $1966$ | 90 | $21\,288$ | $35\,381$ | 0.11 | 0.17 | $8$ | $10$ | 0.53 | 0.11 | 0.31 | $100$ | 4.13 | $0$
shuttle | $(9)$ | 7 |  $1160$) | 3 | $1460$ | 99 | $18\,669$ | $29\,478$ | 0.11 | 0.08 | $2$ | $7$ | 0.34 | 0.05 | 0.14 | $99$ | 0.42 | $1$
sonar | $(60)$ | 2 |  $42$) | 5 | $2614$ | 88 | $9938$ | $20\,537$ | 0.04 | 0.06 | $36$ | $24$ | 0.43 | 0.04 | 0.09 | $100$ | 23.02 | $0$
spambase | $(57)$ | 2 |  $442$) | 5 | $4614$ | 92 | $13\,055$ | $28\,284$ | 0.07 | 0.06 | $18$ | $37$ | 0.50 | 0.05 | 0.11 | $100$ | 6.18 | $0$
spectf | $(44)$ | 2 |  $54$) | 5 | $2306$ | 88 | $6707$ | $13\,449$ | 0.07 | 0.06 | $20$ | $24$ | 0.34 | 0.02 | 0.07 | $100$ | 8.12 | $0$
texture | $(40)$ | 11 |  $550$) | 5 | $5724$ | 87 | $34\,293$ | $64\,187$ | 0.79 | 0.63 | $23$ | $17$ | 3.24 | 0.19 | 0.93 | $100$ | 28.13 | $0$
threeOf9 | $(9)$ | 2 |  $103$) | 3 | $920$ | 100 | $2922$ | $4710$ | 0.00 | 0.00 | $1$ | $8$ | 0.01 | 0.00 | 0.01 | $100$ | 0.14 | $0$
twonorm | $(20)$ | 2 |  $740$) | 5 | $6266$ | 94 | $21\,198$ | $46\,901$ | 0.08 | 0.08 | $12$ | $8$ | 0.28 | 0.06 | 0.10 | $100$ | 5.73 | $0$
vowel | $(13)$ | 11 |  $198$) | 6 | $10\,176$ | 90 | $44\,523$ | $88\,696$ | 1.66 | 2.11 | $8$ | $5$ | 4.52 | 0.15 | 1.15 | $66$ | 1.67 | $34$
waveform-21 | $(21)$ | 3 |  $500$) | 5 | $6238$ | 84 | $29\,991$ | $57\,515$ | 0.68 | 0.54 | $10$ | $11$ | 2.27 | 0.09 | 0.34 | $100$ | 5.86 | $0$
waveform-40 | $(40)$ | 3 |  $500$) | 5 | $6232$ | 83 | $30\,438$ | $58\,380$ | 0.50 | 0.86 | $15$ | $25$ | 7.07 | 0.11 | 0.88 | $100$ | 11.93 | $0$
wdbc | $(30)$ | 2 |  $114$) | 4 | $2028$ | 96 | $7813$ | $15\,742$ | 0.06 | 0.02 | $12$ | $18$ | 0.13 | 0.03 | 0.05 | $100$ | 10.56 | $0$
wine-recog | $(13)$ | 3 |  $72$) | 3 | $1188$ | 97 | $17\,718$ | $28\,421$ | 0.04 | 0.04 | $5$ | $8$ | 0.13 | 0.04 | 0.07 | $100$ | 1.46 | $0$
wpbc | $(33)$ | 2 |  $78$) | 5 | $2432$ | 76 | $9078$ | $18\,675$ | 1.00 | 1.53 | $20$ | $13$ | 5.33 | 0.03 | 0.65 | $79$ | 3.91 | $21$
xd6 | $(9)$ | 2 |  $172$) | 6 | $8288$ | 100 | $2922$ | $8394$ | 0.00 | 0.00 | $3$ | $6$ | 0.02 | 0.01 | 0.01 | $100$ | 0.57 | $0$

Table 1: Performance evaluation of the RF explainability tool (RFxpl), and
comparison with Anchor. The table shows results for 32 datasets, i.e. those
for which test data accuracy is no less than 76%. Columns #F, #C and #I
report, respectively, the number of features, classes and tested instances, in
the dataset. Columns D, #N and %A show, respectively, each tree’s max. depth,
total number of nodes and test accuracy of an RF classifier. Columns #var and
#cl show the number of variables and clauses of a CNF formula encoding an RF
classifier along with any instance to analyze. Column MxS (resp. MxU) reports
the maximum runtime of a SAT call (UNSAT call, resp.) and column #S (#U,
resp.) reports the average number of SAT calls (resp. UNSAT calls) performed
to extract an AXp. Column avg (Mx and m, resp.) shows the average (max. and
min., resp.) runtime for extracting an explanation. The percentage of won
instances is given as %w.

This section assess the performance of our approach to compute PI-explanations
(AXps) for RFs and also compares the results with an heuristic explaining
model Anchor Ribeiro et al. (2018)101010Anchor computes heuristic _local_
explanations and not PI-explanations (AXp). Also, we do not consider other
tools, such as LIME Ribeiro et al. (2016) or SHAP Lundberg and Lee (2017), as
these learn a simpler ML model as an explanation and not a set of literals.
The assessment is performed on a selection of 32 publicly available datasets,
which originate from UCI Machine Learning Repository UCI (2020) and Penn
Machine Learning Benchmarks Olson et al. (2017). Benchmarks comprise binary
and multidimensional classification datasets. The number of classes in the
benchmark suite varies from 2 to 26. The number of features (resp. data
samples) varies from 4 to 64 (106 to 58000, resp.) with the average being 21.9
(resp. 5131.09). When training RF classifiers for the selected datasets, we
used 80% of the dataset instances (20% used for test data). For assessing
explanation tools, we randomly picked fractions of the dataset, depending on
the dataset size. Concretely, for datasets containing, resp., less than 200,
200–999, 1000–9999 and 10000 or more, we randomly picked, resp., 40%, 20%, 10%
and 2% of the instances to analyze. The number of trees in each RF is set to
100 while tree depth varies between 3 and 8. (Note that we have tested other
values for the number of trees ranging from 30 to 200, and we fixed it to 100
since with 100 trees RFs achieve the best train/test accuracies.) As a result,
the accuracy of the trained models varies between 76% to 100%. We use the
scikit-learn Pedregosa et al. (2011) ML tool to train RF models. Note that,
scikit-learn can only handle binary and ordinal features in the case of RFs.
Accordingly, the experiments focus on binary and continuous data and do not
include categorical features. In addition, we have overridden the implemented
RF learner in sciki-learn so that it reflects the original algorithm described
in Breiman (2001) 111111The RF model implemented by scikit-learn uses
probability estimates to predict a class, whereas in the original proposal for
RFs Breiman (2001), the prediction is based on majority vote.. Furthermore,
PySAT Ignatiev et al. (2018) is used to instrument incremental SAT oracle
calls.

The experiments are conducted on a MacBook Pro with a Dual-Core Intel Core i5
2.3GHz CPU with 8GByte RAM running macOS Catalina. Table 1 summarizes the
results of assessing the performance of our RF explainer tool (RFxpl) on the
selected datasets. (The table’s caption also describes the meaning of each
column.) As can be observed, and with three exceptions, the average running
time of RFxpl is less than 1sec. per instance. In terms of the largest running
times, there are a few outliers (this is to be expected since we are solving a
$\textnormal{D}^{\textnormal{P}}$-hard problem), and these occur when the
number of classes is large. To assess the scalability of RFxpl, we compared
RFxpl with the well-known heuristic explainer Anchor Ribeiro et al. (2018).
(Clearly, the exercise does not aim to compare the explanation accuracies of
Anchor and RFxpl, but only to assess how scalable it is in practice to solve a
$\textnormal{D}^{\textnormal{P}}$-complete explainability problem with a
propositional encoding and a SAT oracle.) Over all datasets, RFxpl outperforms
Anchor on more than 96% of the instances (i.e. 8438 out of 8746). In terms of
average running time per instance, RFxpl outperforms Anchor by more than 1
order of magnitude, concretely the average run time of Anchor is 14.22 times
larger than the average runtime of RFxpl.

##  6 Conclusion

This paper proposes a novel approach for explaining random forests. First, the
paper shows that it is $\textnormal{D}^{\textnormal{P}}$-complete to decide
whether a set of literals is a PI-explanation (AXp) for a random forest.
Second, the paper proposes a purely propositional encoding for computing PI-
explanations (AXps) of random forests. The experimental results allow
demonstrating that the proposed approach not only scales to realistically
sized random forests, but it is also significantly more efficient that a state
of the art model-agnostic heuristic approach. Given the practical interest in
RFs Zhou and Feng (2017), finding AXps represents a promising new application
area of SAT solvers.

Two extensions of the work can be envisioned. One extension is to improve
further the propositional encoding proposed in this paper, aiming at
eliminating the very few cases where heuristic approaches are more efficient.
Another extension is to exploit the proposed model (and any of its future
improvements) to explain deep random forests Zhou and Feng (2017).

### Acknowledgements.

This work is supported by the AI Interdisciplinary Institute ANITI, funded by
the French program “Investing for the Future - PIA3” under Grant agreement no
ANR-19-PI3A-0004.

## References

  * Asín et al. (2011) R. Asín, R. Nieuwenhuis, A. Oliveras, and E. Rodríguez-Carbonell.  Cardinality networks: a theoretical and empirical study.  Constraints, 16(2):195–221, 2011.
  * Audemard et al. (2020) G. Audemard, F. Koriche, and P. Marquis.  On tractable XAI queries based on compiled representations.  In KR, pages 838–849, 2020.
  * Biere et al. (2021) A. Biere, M. Heule, H. van Maaren, and T. Walsh, editors.  Handbook of Satisfiability. IOS Press, 2021.
  * Birnbaum and Lozinskii (2003) E. Birnbaum and E. L. Lozinskii.  Consistent subsets of inconsistent systems: structure and behaviour.  J. Exp. Theor. Artif. Intell., 15(1):25–46, 2003.
  * Breiman et al. (1984) L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone.  Classification and Regression Trees.  Wadsworth, 1984.
  * Breiman (2001) L. Breiman.  Random forests.  Mach. Learn., 45(1):5–32, 2001.
  * Chen et al. (2019) H. Chen, H. Zhang, S. Si, Y. Li, D. S. Boning, and C. Hsieh.  Robustness verification of tree-based models.  In NeurIPS, pages 12317–12328, 2019.
  * Cook (1971) S. A. Cook.  The complexity of theorem-proving procedures.  In STOC, pages 151–158, 1971.
  * Darwiche and Hirth (2020) A. Darwiche and A. Hirth.  On the reasons behind decisions.  In ECAI, pages 712–720, 2020.
  * Darwiche and Marquis (2002) A. Darwiche and P. Marquis.  A knowledge compilation map.  J. Artif. Intell. Res., 17:229–264, 2002.
  * Einziger et al. (2019) G. Einziger, M. Goldstein, Y. Sa’ar, and I. Segall.  Verifying robustness of gradient boosted models.  In AAAI, pages 2446–2453, 2019.
  * Feng and Zhou (2018) J. Feng and Z. Zhou.  AutoEncoder by forest.  In AAAI, pages 2967–2973, 2018.
  * Gao and Zhou (2020) W. Gao and Z. Zhou.  Towards convergence rate analysis of random forests for classification.  In NeurIPS, 2020.
  * Guidotti et al. (2019) R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi.  A survey of methods for explaining black box models.  ACM Comput. Surv., 51(5):93:1–93:42, 2019.
  * Ignatiev and Marques-Silva (2021) A. Ignatiev and J. Marques-Silva.  SAT-based rigorous explanations for decision lists.  In SAT, 2021.  In Press.
  * Ignatiev et al. (2018) A. Ignatiev, A. Morgado, and J. Marques-Silva.  PySAT: A Python toolkit for prototyping with SAT oracles.  In SAT, pages 428–437, 2018.
  * Ignatiev et al. (2019) A. Ignatiev, N. Narodytska, and J. Marques-Silva.  Abduction-based explanations for machine learning models.  In AAAI, pages 1511–1519, 2019.
  * Ignatiev et al. (2020) A. Ignatiev, N. Narodytska, N. Asher, and J. Marques-Silva.  From contrastive to abductive explanations and back again.  In AI*IA, 2020.  (Preliminary version available from https://arxiv.org/abs/2012.11067.).
  * Ignatiev (2020) A. Ignatiev.  Towards trustable explainable AI.  In IJCAI, pages 5154–5158, 2020.
  * Li et al. (2018) O. Li, H. Liu, C. Chen, and C. Rudin.  Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions.  In AAAI, pages 3530–3537, 2018.
  * Liffiton et al. (2016) M. H. Liffiton, A. Previti, A. Malik, and J. Marques-Silva.  Fast, flexible MUS enumeration.  Constraints An Int. J., 21(2):223–250, 2016.
  * Lundberg and Lee (2017) S. M. Lundberg and S. Lee.  A unified approach to interpreting model predictions.  In NeurIPS, pages 4765–4774, 2017.
  * Marques-Silva et al. (2020) J. Marques-Silva, T. Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska.  Explaining naive bayes and other linear classifiers with polynomial time and delay.  In NeurIPS, 2020.
  * Marques-Silva et al. (2021) J. Marques-Silva, T. Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska.  Explanations for monotonic classifiers.  In ICML, 2021.  In Press.
  * Miller (2019) T. Miller.  Explanation in artificial intelligence: Insights from the social sciences.  Artif. Intell., 267:1–38, 2019.
  * Mollas et al. (2020) I. Mollas, N. Bassiliades, I. P. Vlahavas, and G. Tsoumakas.  Lionforests: local interpretation of random forests.  In ECAI, volume 2659, pages 17–24, 2020.
  * Montavon et al. (2018) G. Montavon, W. Samek, and K. Müller.  Methods for interpreting and understanding deep neural networks.  Digit. Signal Process., 73:1–15, 2018.
  * Olson et al. (2017) R. S. Olson, W. La Cava, P. Orzechowski, R. J. Urbanowicz, and J. H. Moore.  Pmlb: a large benchmark suite for machine learning evaluation and comparison.  BioData Mining, 10(1):36, 2017.
  * Papadimitriou (1994) C. H. Papadimitriou.  Computational complexity.  Addison-Wesley, 1994.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * Petkovic et al. (2018) D. Petkovic, R. B. Altman, M. Wong, and A. Vigil.  Improving the explainability of random forest classifier - user centered approach.  In PSB, pages 204–215, 2018.
  * Quinlan (1993) J. R. Quinlan.  C4.5: Programs for Machine Learning.  Morgan Kaufmann, 1993.
  * Reiter (1987) R. Reiter.  A theory of diagnosis from first principles.  Artif. Intell., 32(1):57–95, 1987.
  * Ribeiro et al. (2016) M. T. Ribeiro, S. Singh, and C. Guestrin.  ”why should I trust you?”: Explaining the predictions of any classifier.  In KDD, pages 1135–1144, 2016.
  * Ribeiro et al. (2018) M. T. Ribeiro, S. Singh, and C. Guestrin.  Anchors: High-precision model-agnostic explanations.  In AAAI, pages 1527–1535, 2018.
  * Shih et al. (2018) A. Shih, A. Choi, and A. Darwiche.  A symbolic approach to explaining bayesian network classifiers.  In IJCAI, pages 5103–5111, 2018.
  * Shih et al. (2019) A. Shih, A. Choi, and A. Darwiche.  Compiling bayesian network classifiers into decision graphs.  In AAAI, pages 7966–7974, 2019.
  * UCI (2020) UCI Machine Learning Repository.  https://archive.ics.uci.edu/ml, 2020.
  * Umans et al. (2006) C. Umans, T. Villa, and A. L. Sangiovanni-Vincentelli.  Complexity of two-level logic minimization.  IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 25(7):1230–1246, 2006.
  * Yang et al. (2020) L. Yang, X. Wu, Y. Jiang, and Z. Zhou.  Multi-label learning with deep forest.  In ECAI, volume 325, pages 1634–1641, 2020.
  * Zhang et al. (2019) Y. Zhang, J. Zhou, W. Zheng, J. Feng, L. Li, Z. Liu, M. Li, Z. Zhang, C. Chen, X. Li, Y. A. Qi, and Z. Zhou.  Distributed deep forest and its application to automatic detection of cash-out fraud.  ACM Trans. Intell. Syst. Technol., 10(5):55:1–55:19, 2019.
  * Zhao et al. (2019) X. Zhao, Y. Wu, D. L. Lee, and W. Cui.  iforest: Interpreting random forests via visual analytics.  IEEE Trans. Vis. Comput. Graph., 25(1):407–416, 2019.
  * Zhou and Feng (2017) Z. Zhou and J. Feng.  Deep forest: Towards an alternative to deep neural networks.  In IJCAI, pages 3553–3559, 2017.


# Digital $k$-continuity, digital $k$-isomorphism, local $k$-isomorphism,
radius $2$-local $k$-isomorphism, and digital $k$-homotopy

Sang-Eon Han  Department of Mathematics Education, Institute of Pure and
Applied Mathematics
Jeonbuk National University, Jeonju-City Jeonbuk, 54896, Republic of Korea
e-mail<EMAIL_ADDRESS>Tel: 82-63-270-4449.

###### Abstract.

The present paper refers to the notions of digital continuity, digital
$k$-isomorphism, local $k$-isomorphism, radius $2$-local $k$-isomorphism, and
digital $k$-homotopy motivated by the Khalimsky’s version. We discuss
something incorrectly mentioned in Boxer’s papers and suggest some accurate
information.

AMS Classification: 68U05
Keywords: digital topology, digital image, digital $k$-connectivity,
$k$-adjacency, digital continuity, digital $k$-homotopy

##  1\. Essential concepts for studying digital images

The present paper will often follow the notation. ${\mathbb{N}}$ indicates the
set of positive integers, ${\mathbb{Z}}$ means the set of integers, $``$$:=$”
is used for introducing a new term and $``$$\subset$” stands for a subset as
usual. Besides, for $a,b\in{\mathbb{Z}}$,
$[a,b]_{\mathbb{Z}}:=\\{t\in{\mathbb{Z}}\,|\,a\leq t\leq b\\}$. We also
abbreviate the term $``$digital topological” as $DT$.

To study digital images from the viewpoint of digital topology, we have
considered digital $k$-connectivities for the $n$-dimensional lattice set
${\mathbb{Z}}^{n},n\in{\mathbb{N}}$. In detail, before 2004 (see [4, 5, 6]),
focusing on the $3$-dimensional real world, all papers in digital topology
dealt with only low dimensional digital image $(X,k)$, i.e.,
$X\subset{\mathbb{Z}}^{3}$ with one of the $k$-adjacency of ${\mathbb{Z}}^{3}$
[1, 25, 26, 27].

After generalizing these $k$-connectivities into those for $n$-dimensional
cases, $n\in{\mathbb{N}}$, since 2004 ([4, 5, 6]), a digital image $(X,k)$ has
often assumed to be a set $X$ in ${\mathbb{Z}}^{n}$ with one of the
$k$-adjacency relations of ${\mathbb{Z}}^{n}$ from (2.2) below. Indeed, the
$k$-adjacency relations for $X\subset{\mathbb{Z}}^{n},n\in{\mathbb{N}}$, were
initially established in [6] (see also [4, 5, 9, 13]). More precisely, for a
natural number $t$, $1\leq t\leq n$, the distinct points
$p=(p_{i})_{i\in[1,n]_{\mathbb{Z}}}$ and
$q=(q_{i})_{i\in[1,n]_{\mathbb{Z}}}\in{\mathbb{Z}}^{n}$ are $k(t,n)$-adjacent
(see the page 74 of [6]) if

$None$ $\text{at most}\,\,t\,\,\text{of their coordinates differ by}\,\,\pm
1\,\,\text{and the others~{}coincide.}$

According to this criterion, the digital $k(t,n)$-connectivities of
${\mathbb{Z}}^{n},n\in{\mathbb{N}}$, are formulated [6] (see also [13]) as
follows:

$None$
$k:=k(t,n)=\sum_{i=1}^{t}2^{i}C_{i}^{n},\text{where}\,\,C_{i}^{n}:={n!\over(n-i)!\
i!}.$

For instance, in ${\mathbb{Z}}^{4}$, $k(1,4)=8$, $k(2,4)=32$, $k(3,4)=64$, and
$k(4,4)=80$; in ${\mathbb{Z}}^{5}$, $k(1,5)=10$, $k(2,5)=50$, $k(3,5)=130$,
$k(4,5)=210$, and $k(5,5)=242$; and in ${\mathbb{Z}}^{6}$, $k(1,6)=12$,
$k(2,6)=72$, $k(3,6)=232$, $k(4,6)=472$, $k(5,6)=664$, $k(6,6)=728$ [4, 6,
13].
The notation $``$$k(t,n)$” of (2.2) indeed gives us essential information to
study digital images such as the dimension $n$ and the number $t$ associated
with the statement of (2.1). Han’s approach using $k:=k(t,n)$ can be helpful
to study more complicated cases such as digital products with a
$C$-compatible, a normal, and a pseudo-normal $k$-adjacency [6, 12, 19, 23]
and their applications.

Hereinafter, a relation set $(X,k)$ is assumed in ${\mathbb{Z}}^{n}$ with a
$k$-adjacency of (2.2), called a digital image. Namely, we now abbreviate
$``$digital image $(X,k)$” as $``$$(X,k)$” if there is no confusion.

Let us now recall a $``$digital $k$-neighborhood of the point $x_{0}$” in
$(X,k)$. For $(X,k)$ and a point $x_{0}\in X$, we have often used the notation

$None$ $N_{k}(x_{0},1):=\\{x\in X\,|\,\,x\,\,\text{is}\,\,k\text{-adjacent
to}\,\,x_{0}\\}\cup\\{x_{0}\\},$

which is called a digital $k$-neighborhood of the point $x_{0}$ in $(X,k)$.
The notion of (2.3) indeed facilitates some studies of digital images, e.g.,
digital covering spaces [6, 8, 9], digital $(k_{0},k_{1})$-homotopy [2, 3, 6,
8], digital-topological ($DT$-, for brevity) $k$-group [16, 17], and so on.

The notation of (2.3) indeed comes from the $``$digital $k$-neighborhood of
$x_{0}\in X$ with radius $\varepsilon\in{\mathbb{N}}$” in [4, 5, 6] (see (2.4)
below). More precisely, for $(X,k),X\subset{\mathbb{Z}}^{n}$ and two distinct
points $x$ and $x^{\prime}$ in $X$, a simple $k$-path from $x$ to $x^{\prime}$
with $l$ elements is said to be a sequence $(x_{i})_{i\in[0,l]_{\mathbb{Z}}}$
in $X$ such that $x_{0}=x$ and $x_{l}=x^{\prime}$ and further, $x_{i}$ and
$x_{j}$ are $k$-adjacent if and only if $|i-j|=1$ [25]. We say that a length
of the simple $k$-path, denoted by $l_{k}(x,y)$, is the number $l$ [6].

######  Definition 1.

[4] (see also [6]) For a digital image $(X,k)$ on ${\mathbb{Z}}^{n}$, the
digital $k$-neighborhood of $x_{0}\in X$ with radius $\varepsilon$ is defined
in $X$ to be the following subset of $X$

$None$ $N_{k}(x_{0},\varepsilon)=\\{x\in
X\,|\,l_{k}(x_{0},x)\leq\varepsilon\\}\cup\\{x_{0}\\},$

where $l_{k}(x_{0},x)$ is the length of a shortest simple $k$-path from
$x_{0}$ to $x$ and $\varepsilon\in{\mathbb{N}}$.

Owing to Definition 1, it is clear that $N_{k}(x_{0},1)$ of (2.3) is a special
case of $N_{k}(x_{0},\varepsilon)$ of (2.4). Note that the neighborhood
$N_{k}(x_{0},2)$ plays an important role in establishing the notions of a
radius $2$-local $(k_{1},k_{2})$-isomorphism and a radius
$2$-$(k_{1},k_{2})$-covering map which is strongly associated with the
homotopy lifting theorem [5] and is essential for calculating digital
fundamental groups of digital images $(X,k)$ [3, 6].

We say that $(Y,k)$ is $k$-connected [25] if for arbitrary distinct points
$x,y\in Y$ there is a finite sequence $(y_{i})_{i\in[0,l]_{\mathbb{Z}}}$ in
$Y$ such that $y_{0}=x$, $y_{l}=y$ and $y_{i}$ and $y_{j}$ are $k$-adjacent if
$|\,i-j\,|=1$ [25]. Besides, a singleton is assumed to be $k$-connected.

A simple closed $k$-curve (or $k$-cycle) with $l$ elements in
${\mathbb{Z}}^{n},n\geq 2$, denoted by $SC_{k}^{n,l}$ [6, 25], $l(\geq
4)\in{\mathbb{N}}$, is defined as the sequence
$(y_{i})_{i\in[0,l-1]_{\mathbb{Z}}}\subset{\mathbb{Z}}^{n}$ such that $y_{i}$
and $y_{j}$ are $k$-adjacent if and only if $|\,i-j\,|=\pm 1(mod\,l)$. Indeed,
the number $l(\geq 4)$ is very important in studying $k$-connected digital
images from the viewpoint of digital homotopy theory. The number $l$ of
$SC_{k}^{n,l}$ can be an even or an odd number. Namely, the number $l$ depends
on the dimension $n$ and the $k$-adjacencies (see Remark 1.1 below).

######  Remark 1.1.

(see (5) of [14]) The number $l$ of $SC_{k}^{n,l}$ depends on the dimension
$n\in{\mathbb{N}}\setminus\\{1\\}$ and the number
$l\in\\{2a,2a+1\\},a\in{\mathbb{N}}\setminus\\{1\\}$.

##  2\. Digital $k$-continuity, digital $k$-isomorphism, local
$k$-isomorphism, and radius $2$-local $k$-isomorphism

Rosenfeld [26] initially introduced the notion of digital $k$-continuity. More
precisely, Rosenfeld defined that a map $f:(X,k_{1})\to(X,k_{2})$ is said to
be $(k_{1},k_{2})$-continuous if the image $(f(A),k_{2})$ is $k_{2}$-connected
for each $k_{1}$-connected subset $A$ of $(X,k_{1})$, where
$X\subset{\mathbb{Z}}^{3}$. Also, Rosenfeld represented it as follows: A
function $f:(X,k_{1})\to(Y,k_{2})$ is $(k_{1},k_{2})$-continuous if and only
if two points $x$ and $x^{\prime}$ which are $k_{1}$-adjacent in $(X,k_{1})$
implies that either $f(x)=f(x^{\prime})$ or $f(x)$ is $k_{2}$-adjacent to
$f(x^{\prime})$, where $X$ and $Y$ are subsets of ${\mathbb{Z}}^{3}$. Based on
this approach, Han [6] represented the $(k_{1},k_{2})$-continuity of a map
$f:(X,k_{1})\to(Y,k_{2})$ with the following statement which has strongly used
to study digital covering spaces and pseudo-convering spaces, $DT$-$k$-group
theory [16, 17], and so forth, where $X\subset{\mathbb{Z}}^{n_{1}}$ and
$Y\subset{\mathbb{Z}}^{n_{2}}$.

######  Proposition 2.1.

[4, 6, 8] A function $g:(X,k_{1})\to(Y,k_{2})$ is $(k_{1},k_{2})$-continuous
if and only if for each point $x\in X$, $g(N_{k_{1}}(x,1))\subset
N_{k_{2}}(g(x),1)$, where $X\subset{\mathbb{Z}}^{n_{1}}$ and
$Y\subset{\mathbb{Z}}^{n_{2}}$.

Using $k$-continuous maps, we establish a digital topological category,
denoted by DTC, consisting of the following two pieces of data [8].
$\bullet$ The set of $(X,k)$ as objects,
$\bullet$ For every ordered pair of objects $(X,k_{1})$ and $(Y,k_{2})$, the
set of all $(k_{1},k_{2})$-continuous maps $f:(X,k_{1})\to(Y,k_{2})$ as
morphisms.

Based on the digital continuity, since 2005 [7], we have often used a
$(k_{1},k_{2})$-isomorphism for a map between two sets
$X\subset{\mathbb{Z}}^{n_{1}}$ and $Y\subset{\mathbb{Z}}^{n_{2}}$ in [7, 20]
instead of a $(k_{1},k_{2})$-homeomorphism for a map between two sets
$X,Y\subset{\mathbb{Z}}^{3}$ in [1], as follows:

######  Definition 2.

[1] (see also [7, 20]) Assume $(X,k_{1})$ and $(Y,k_{2})$ on
${\mathbb{Z}}^{n_{1}}$ and ${\mathbb{Z}}^{n_{2}}$, respectively. We say that a
bijection $h:(X,k_{1})\to(Y,k_{2})$ is a $(k_{1},k_{2})$-isomorphism if $h$ is
a $(k_{1},k_{2})$-continuous and the inverse map of $h$, $h^{-1}:Y\to X$, is
$(k_{2},k_{1})$-continuous. Then we denote this isomorphism by
$(X,k_{1})\approx_{(k_{1},k_{2})}(Y,k_{2})$. If $n_{1}=n_{2}$ and
$k_{1}=k_{2}$, then we call it a $k_{1}$-isomorphism.

Compared with a $(k_{1},k_{2})$-isomorphism, a local
$(k_{1},k_{2})$-isomorphism which is weaker than a $(k_{1},k_{2})$-isomorphism
was defined. The notion plays an important role in establishing a
$(k_{1},k_{2})$-covering space [5, 6] and a pseudo-$(k_{1},k_{2})$-covering
space [11, 18], $DT$-$(k_{1},k_{2})$-embedding theorem [14], and so forth.

######  Definition 3.

[4, 15] For two digital images $(X,k_{1})$ on ${\mathbb{Z}}^{n_{1}}$ and
$(Y,k_{2})$ on ${\mathbb{Z}}^{n_{2}}$, consider a map
$h:(X,k_{1})\to(Y,k_{2})$. Then the map $h$ is said to be a local (or $L$-,
for brevity) $(k_{1},k_{2})$-isomorphism if for every $x\in X$, $h$ maps
$N_{k_{1}}(x,1)$ $(k_{1},k_{2})$-isomorphically onto $N_{k_{2}}(h(x),1)$,
i.e., the restriction map $h|_{N_{k_{1}}(x,1)}:N_{k_{1}}(x,1)\to
N_{k_{2}}(h(x),1)$ is a $(k_{1},k_{2})$-isomorphism. If $n_{1}=n_{2}$ and
$k_{1}=k_{2}$, then the map $h$ is called a local (or $L$-)
$k_{1}$-isomorphism.

In view of Definition 3, we observe that a local $(k_{1},k_{2})$-isomorphism
is obviously a $(k_{1},k_{2})$-continuous map. However, the converse does not
hold. Compared with a local $(k_{1},k_{2})$-isomorphism, the following is
defined.

######  Definition 4.

[5] (Radius $2$-local $(k_{1},k_{2})$-isomorphism) Assume a map
$h:(X,k_{1})\to(Y,k_{2})$, where $X\subset{\mathbb{Z}}^{n_{1}}$ and
$Y\subset{\mathbb{Z}}^{n_{2}}$. Then we say that it is a radius $2$-local
$(k_{1},k_{2})$-isomorphism if for each point $x\in X$ the restriction $h$ to
$N_{k_{1}}(x,2)$, i.e., $h|_{N_{k_{1}}(x,2)}:N_{k_{1}}(x,2)\to
N_{k_{2}}(h(x),2)$ is a $(k_{1},k_{2})$-isomorphism. In particular, in the
case of $k:=k_{1}=k_{2}$, we call it a radius $2$-local $k$-isomorphism.

Comparing Definitions 3 and 4, we obtain the following:

######  Remark 2.2.

A radius $2$-local $(k_{1},k_{2})$-isomorphism is clearly a local
$(k_{1},k_{2})$-isomorphism. However, the converse does not hold.

######  Example 2.3.

Consider the map $p:({\mathbb{Z}},2)\to
SC_{k}^{n,l}:=(s_{i})_{i\in[0,l-1]_{\mathbb{Z}}}$ given by
$p(t)=s_{t(mod\,l)}$.
(1) In the case of $l\geq 5$, the map $p$ is a radius $2$-local
$(2,k)$-isomorphism.
(2) In the case of $l=4$, the map $p$ is not a radius $2$-local
$(2,k)$-isomorphism but an $L$-$(2,k)$-isomorphism.

A radius $2$-local $(k_{1},k_{2})$-isomorphism strongly plays an important
role in studying digital images from the viewpoint of digital homotopy theory
and digital covering theory. In detail, this notion is essential for
establishing the homotopy lifting theorem [5] which can be used to calculate
digital fundamental groups [3, 5, 6].

######  Remark 2.4.

(Utilities of radius $2$-local $(k_{1},k_{2})$-isomorphism)
$\bullet$ Establishment of the homotopy lifting theorem [5]
$\bullet$ Calculation of digital fundamental groups [3, 5, 6]

##  3\. Digital $k$-homotopy and digital $k$-homotopy equivalence

Before 2005, the notion of a digital $k$-homotopy was considered in
${\mathbb{Z}}^{3}$. In detail, the first version of a digital $k$-homotopy was
initially established by Khalimsky [24]. After that, the second version of it
was introduced by Boxer in ${\mathbb{Z}}^{3}$ [1]. After that, in
${\mathbb{Z}}^{n},n\in{\mathbb{N}}$, the third version of it was established
by Han in [5, 6]. Han’s version is called a digital $k$-homotopy relative to a
subset $A\subset X$ (see [5, 6]) and it has been used to study a $k$-homotopic
thinning of a digital image $(X,k)$ in ${\mathbb{Z}}^{n}$. For a digital image
$(X,k)$ and $A\subset X$, we often call $((X,A),k)$ a digital image pair. Let
us now recall some history of them as follows:

######  Definition 5.

[24] (Khalimsky’s version of a digital $k$-homotopy in ${\mathbb{Z}}^{3}$).
Let $(X,k_{1})$ and $(Y,k_{2})$ be digital images. Let
$f,g:(X,k_{1})\to(Y,k_{2})$ be $(k_{1},k_{2})$-continuous functions.
Suppose that there exist $m\in{\mathbb{N}}$ and a function
$H:X\times[0,m]_{\mathbb{Z}}\to Y$ such that
(1) for all $x\in X,H(x,0)=f(x)$ and $H(x,m)=g(x)$ and
(2) for all $t\in[0,m]_{\mathbb{Z}}$, the induced function $H_{t}:X\to Y$
given by $H_{t}(x)=H(x,t)$ for all $x\in X$ is $(k_{1},k_{2})$-continuous.
Then we say that $H$ is a $k$-homotopy between $f$ and $g$.

As a more rigid version than the digital $(k_{1},k_{2})$-homotopy of
Definition 5, the following was constructed. In addition, a pointed digital
image is said to be a pair $(X,x_{0})$ and $x_{0}\in X$. A pointed
$(k_{1},k_{2})$-continuous map $f:(X,x_{0})\to(Y,y_{0})$ is a
$(k_{1},k_{2})$-continuous function from $X$ to $Y$ such that $f(x_{0})=y_{0}$
from $(X,x_{0})$ to $(Y,y_{0})$ [1].

######  Definition 6.

[1] (Boxer’s version of a (pointed) digital $(k_{1},k_{2})$-homotopy in
${\mathbb{Z}}^{3}$). Let $(X,k_{1})$ and $(Y,k_{2})$ be a digital image,
respectively. Let $f,g:(X,k_{1})\to(Y,k_{2})$ be $(k_{1},k_{2})$-continuous
functions. Suppose that there exist $m\in{\mathbb{N}}$ and a function
$H:X\times[0,m]_{\mathbb{Z}}\to Y$ such that
(1)-(2): the conditions (1) and (2) of Definition 5 and further,
(3) for all $x\in X$, the induced function $H_{x}:[0,m]_{\mathbb{Z}}\to Y$
given by $H_{x}(t)=H(x,t)$ for all $t\in[0,m]_{\mathbb{Z}}$ is
$(2,k_{2})$-continuous.
Then we say that $H$ is a $(k_{1},k_{2})$-homotopy between $f$ and $g$.
A digital $(k_{1},k_{2})$-homotopy $H:X\times[0,m]_{Z}\to Y$ between $f$ and
$g$ is called a pointed digital $(k_{1},k_{2})$-homotopy between $f$ and $g$
if for all $t\in[0,m]_{Z},H(x_{0},t)=y_{0}$.

As a generalization of the Boxer’s pointed digital $(k_{1},k_{2})$-homotopy,
Han [5, 6] established the so-called $``$digital $(k_{1},k_{2})$-homotopy
relative to $A$” in [5, 6] with the expansion of the dimension from
${\mathbb{Z}}^{3}$ to ${\mathbb{Z}}^{n},n\in{\mathbb{N}}$ and $\\{x_{0}\\}$ to
$A\subset X$, as follows:

######  Definition 7.

[4, 8] (Han’s version of a digital $(k_{1},k_{2})$-homotopy relative to $A$ in
${\mathbb{Z}}^{n},n\in{\mathbb{N}}$). Let $(X,k_{1})$ and $(Y,k_{2})$ be
digital images on ${\mathbb{Z}}^{n_{1}}$ and ${\mathbb{Z}}^{n_{2}}$,
respectively. Let $f,g:(X,k_{1})\to(Y,k_{2})$ be $(k_{1},k_{2})$-continuous
functions. Suppose that there exist $m\in{\mathbb{N}}$ and a function
$H:X\times[0,m]_{\mathbb{Z}}\to Y$ such that
(1)-(3): the conditions (1)-(3) of Definition 6, and further,
(4) for all $t\in[0,m]_{\mathbb{Z}}$, assume that the induced map $H_{t}$ on
$A$ is a constant which follows the prescribed function from $A$ to $Y$. To be
precise, $H_{t}(x)=f(x)=g(x)$ for all $x\in A$ and for all
$t\in[0,m]_{\mathbb{Z}}$.
Then we call $H$ a $(k_{1},k_{2})$-homotopy relative to $A$ between $f$ and
$g$, and we say that $f$ and $g$ are $(k_{1},k_{2})$-homotopic relative to $A$
in $Y$, $f\simeq_{(k_{1},k_{2})relA}g$ in symbols.
In particular, in the case of $n_{1}=n_{2}$ and $k:=k_{1}=k_{2}$, we
abbreviate $``$$(k_{1},k_{2})$-homotopy relative to $A$” as $``$$k$-homotopy
relative to $A$” and use the notation $f\simeq_{krelA}g$.

In Definition 7, if $A=\\{x_{0}\\}\subset X$, then we observe that $H$ is a
pointed $(k_{1},k_{2})$-homotopy at $\\{x_{0}\\}$ [1]. If, for some $x_{0}\in
X$, $1_{X}$ is $k$-homotopic to the constant map in the space $x_{0}$ relative
to $\\{x_{0}\\}$, then we say that $(X,x_{0})$ is pointed $k$-contractible
[1]. For instance, $SC_{3n-1}^{n,4}$ is $(3n-1)$-contractible [1, 6, 9].

######  Remark 3.1.

Using Han’s homotopy of Definition 7, we can proceed a $k$-homotopic thinning
[9] (see Definition 9 below).

In [9], we have studied a $k$-homotopic thinning in $DTC$ by using a strong
$k$-deformation retract derived from the $k$-homotopy relative to some subset
$(A,k)\subset(X,k)$ in Definition 7.

######  Definition 8.

[9] In DTC, for a digital image pair $((X,A),k)$, $A$ is said to be a strong
$k$-deformation retract of $X$ if there is a $k$-retraction $r$ of $X$ onto
$A$ such that $F:i\circ r\simeq_{k\cdot{\it rel.}A}1_{X}$, where
$i:(A,k)\to(X,k)$ is an inclusion map. Then, a point $x\in X\setminus A$ is
called strongly $k$-deformation retractable.

######  Definition 9.

[9] In $DTC$, for a digital image $(X,k)$, a process of deleting strong
$k$-deformation retractable points from $X$ is called a $k$-homotopic
thinning.

Based on Definition 7, the notion of a digital $(k_{1},k_{2})$-homotopy
equivalence is introduced as follow:

######  Definition 10.

[21] Assume two digital images $(X,k_{1})$ on ${\mathbb{Z}}^{n_{1}}$ and
$(Y,k_{2})$ on ${\mathbb{Z}}^{n_{2}}$. Assume a $(k_{1},k_{2})$-homotopy from
$(X,k_{1})$ and $(Y,k_{2})$ such that $g\circ f\simeq_{(k_{1},k_{2}))}1_{X}$
and a $(k_{2},k_{1})$-homotopy from $(Y,k_{1})$ and $(X,k_{1})$ such that
$f\circ g\simeq_{(k_{2},k_{1}))}1_{Y}$. Then we say that $(X,k_{1})$ is
$(k_{1},k_{2})$-homotopy equivalent to $(Y,k_{2})$. In particular, in the case
of $n_{1}=n_{2}$ and $k:=k_{1}=k_{2}$, the $(k_{1},k_{2})$-homotopy
equivalence is said to be a $k$-homotopy equivalence.

Even though Boxer often claimed that the term $``$$k$-homotopy equivalence”
was introduced in [1], one can clearly observe that there is no notion (or
term) of a $k$-homotopy equivalence in [1]. The paper [1] just only stated an
equivalence relation of a homotopy of Definition 6 (see Proposition 2.8 of
[1]). As for a digital $(k_{1},k_{2})$-homotopy equivalence, Han [21]
delivered his talk on a digital $(k_{1},k_{2})$-homotopy equivalence and a
digital $k$-homotopy equivalence at the international conference which was
held in Washington in the U.S. in 2003 (see [21]). Besides, many scholars
including the professors R. Kopperman, J. D. Lawson, M. Mislove enjoyed the
talk and discussed the notion of a digital $(k_{1},k_{2})$-homotopy
equivalence and a digital $k$-homotopy equivalence there. After two years
later, in only 2005, Boxer studied the notion of a digital
$(k_{1},k_{2})$-homotopy equivalence and a digital $k$-homotopy equivalence in
his paper.

######  Remark 3.2.

Based on Khalimsky topology or an adjacency derived from the Khalilmsky
topology on ${\mathbb{Z}}^{n}$, the paper [10] studied many types of homotopy
equivalence from the viewpoint of digital topology. Besides, the paper [22]
also studied a special kind of homotopy equivalence using some adjacency
derived from the Marcus-Wyse topology.

##  4\. Further remarks

We have discussed some utilities of the notion of a radius $2$-local
$(k_{1},k_{2})$-isomorphism and referred to a history of the concept of a
digital $k$-homotopy. Based on the works [1, 2, 3, 4, 5, 6, 8, 9, 15, 18, 21,
24], we will remark on Boxer’s misconception in [2] on Han’s papers [11, 15]
and a revision of a pseudo-$(k_{1},k_{2})$-covering space. In particular,
since Boxer [2] referred to some results in [18] in an inaccurate way, we will
correct some assertions in [2] which are due to Boxer’s misunderstanding with
a next paper as a series of this topic.

Conflicts of Interest: The author declares no conflict of interest.

## References

  * [1] L. Boxer, A classical construction for the digital fundamental group, J. Math. Imaging Vis. 10 (1999) 51–62.
  * [2] L. Boxer, Variants on covering maps, arXiv:2303.001150v2 (4 May 2023) 1-8.
  * [3] L. Boxer, I. Karaca, The classification of digital covering spaces. J. Math. Imaging Vis. 32 (2008) 23–29.
  * [4] S.-E. Han, Digital $(k_{0},k_{1})$-covering map and its properties, Honam Math. J. 26 (2004) 107–117.
  * [5] S.-E. Han, Digital coverings and their applications, J. Appl. Math. Comput. 18 (2005) 487–495.
  * [6] S.-E. Han, Non-product property of the digital fundamental group, Inf. Sci. 171 (2005) 73–91.
  * [7] S.-E. Han, On the simplicial complex stemmed from a digital graph, Honam Math. J., 27 (2005) 115–129.
  * [8] S.-E. Han, Discrete Homotopy of a Closed $k$-Surface, LNCS 4040; Springer: Berlin, Germany, 2006; pp. 214–225.
  * [9] S.E. Han, The $k$-homotopic thinning and a torus-like digital image in ${\bf Z}^{n}$, J. Math. Imaging Vision 31 (2008) 1-16.
  * [10] S.-E. Han, $KD$-$(k_{0},k_{1})$-homotopy equivalence and its applications, Jour. of Korean Math. Soc. 47(8) (2010) 1031-1054.
  * [11] S.-E. Han, Unique pseudo-lifting property in digital topology, Filomat 26(4) (2012) 739–746.
  * [12] S.-E. Han, Compatible adjacency relations for digital products, Filomat 31(9) (2017) 2787-2803.
  * [13] S.-E. Han, Estimation of the complexity of a digital image from the viewpoint of fixed point theory. Appl. Math. Comput., 347 (2019) 236–248.
  * [14] S.-E. Han, The most refined axiom for a digital covering space, Mathematics 8 (1898) (2020) doi:2.3030/math811868.
  * [15] S.-E. Han, An equivalent conditions for a pseudo $(k_{0},k_{1})$-covering space, Filomat 36(15) (2022) 5093-5105.
  * [16] S.-E. Han, Digitally topological groups, Electronic Research Archive 30(6) (2022) 2356–2384.
  * [17] S.-E. Han, $DT$-$k$-group structures on digital objects and an answer to an open problem, Discrete Mathematics, Algorithms and Applications, accepted (in press) (2023) 1-30.
  * [18] S.-E. Han, Remarks on pseudocovering spaces in a digital topological setting, Filomat 38(2) (2024), (accepted and in press).
  * [19] S.-E. Han, Essential concepts of digital topology (Digital $k$-connectivities and $k$-adjacencies for digital products), arXiv: 2309.01438v1 (2023).
  * [20] S.E. Han and B.G. Park, Digital graph $(k_{0},k_{1})$-isomorphism and its applications, http://atlas-conferences.com/c/a/k/b/36.htm (2003).
  * [21] S.-E. Han, B.G. Park, Digital Graph $(k_{0},k_{1})$-Homotopy Equivalence and Its Applications, In Proceedings of the Conference on Topology and Its Applications, Washington, DC, USA, 9–12 July 2003.
  * [22] S.-E. Han, W. Yao, Homotopy based on Marcus–Wyse topology and its applications, Topol. Appl. 201 (2016) 358–371.
  * [23] J.-M. Kang, S.-E. Han, S. Lee, Digital products with $PN_{k}$-adjacencies and the almost fixed point property in $DTC_{k}^{\blacktriangle}$ , AIMS(Mathematics) 6(10) (2021) 11550-11567.
  * [24] E.D. Khalimsky, Motion, Deformation, and Homotopy in Finite Spaces, Proceedings IEEE International Conference on Systems, Man, and Cybernetics Boston, 1987, pp. 227-234.
  * [25] T.Y. Kong; A.Rosenfeld, Computer Vision, Graphics, and Imaging Processing, 48 (1989) 357-393.
  * [26] A. Rosenfeld, Digital topology, Am. Math. Mon. 86 (1979) 76–87.
  * [27] A. Rosenfeld, Continuous functions on digital pictures, Pattern Recognit. Lett. 4 (1986) 177–184.