# On Tackling Explanation Redundancy in Decision Trees

Yacine Izza<EMAIL_ADDRESS>
University of Toulouse, Toulouse, France Alexey Ignatiev
<EMAIL_ADDRESS>
Monash University, Melbourne, Australia Joao Marques-Silva joao.marques-
<EMAIL_ADDRESS>
IRIT, CNRS, Toulouse, France

###### Abstract

Decision trees (DTs) epitomize the ideal of interpretability of machine
learning (ML) models. The interpretability of decision trees motivates
explainability approaches by so-called intrinsic interpretability, and it is
at the core of recent proposals for applying interpretable ML models in high-
risk applications. The belief in DT interpretability is justified by the fact
that explanations for DT predictions are generally expected to be succinct.
Indeed, in the case of DTs, explanations correspond to DT paths. Since
decision trees are ideally shallow, and so paths contain far fewer features
than the total number of features, explanations in DTs are expected to be
succinct, and hence interpretable. This paper offers both theoretical and
experimental arguments demonstrating that, as long as interpretability of
decision trees equates with succinctness of explanations, then decision trees
ought not be deemed interpretable. The paper introduces logically rigorous
path explanations and path explanation redundancy, and proves that there exist
functions for which decision trees must exhibit paths with explanation
redundancy that is arbitrarily larger than the actual path explanation. The
paper also proves that only a very restricted class of functions can be
represented with DTs that exhibit no explanation redundancy. In addition, the
paper includes experimental results substantiating that path explanation
redundancy is observed ubiquitously in decision trees, including those
obtained using different tree learning algorithms, but also in a wide range of
publicly available decision trees. The paper also proposes polynomial-time
algorithms for eliminating path explanation redundancy, which in practice
require negligible time to compute. Thus, these algorithms serve to indirectly
attain irreducible, and so succinct, explanations for decision trees.
Furthermore, the paper includes novel results related with duality and
enumeration of explanations, based on using SAT solvers as witness-producing
NP-oracles.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Function Representation
    2. 2.2 Logic Foundations
    3. 2.3 Classification Problems
    4. 2.4 Decision Trees
    5. 2.5 Formal Explainability
    6. 2.6 Summary of Notation
  3. 3 Duality of Explanations & Path-Based Explanations
    1. 3.1 Generalized Explanations & Duality
    2. 3.2 Restricted Duality
    3. 3.3 Path Explanations
  4. 4 Path Explanation Redundancy in Decision Trees
    1. 4.1 Explanation Redundancy in Running Examples
    2. 4.2 Path Explanation Redundancy in Practice
    3. 4.3 Path Explanation Redundancy in Theory
  5. 5 Computing Path Explanations in Decision Trees
    1. 5.1 Abductive Path Explanations by Explicit Path Analysis
    2. 5.2 Abductive Path Explanations by Tree Traversal
    3. 5.3 Abductive Path Explanations by Propositional Horn Encoding
    4. 5.4 Contrastive Path Explanations
    5. 5.5 Enumeration of Path Explanations
  6. 6 Experimental Results
  7. 7 Related Work
  8. 8 Conclusions
  9. Acknowledgments

##  1 Introduction

The cognitive limits of human decision makers [131] substantiate why
succinctness is one of the key requirements of explanations of machine
learning (ML) models. Succinct explanations are generally accepted to be
easier to understand by human decision makers, but are also easier to diagnose
or debug. Decision trees (DTs) epitomize so-called interpretable machine
learning models [47, 160, 135], in part because paths in the tree (which are
possibly short, and so potentially succinct) represent explanations of
predictions.

Decision trees (DTs) find a wide range of practical uses111From an ever-
increasing range of practical uses, example references include [190, 189, 108,
179, 26, 29, 28, 69, 25, 27, 30, 32, 33, 115, 72, 34, 37, 31, 142, 145, 52,
24, 174, 171, 36, 67, 127, 35, 19]. . Moreover, DTs are the most visible
example of a collection of machine learning (ML) models that have recently
been advocated as essential for high-risk applications [160]. Decision trees
also represent explainability approaches based on intrinsic interpretability
[135]222Interpretability is generally accepted to be a subjective concept,
without a rigorous definition [113]. Similar to other works [135], this paper
relates interpretability with succinctness of the explanations provided..
Given a decision tree, some input and the resulting prediction, the
explanation associated with that prediction is the path in the decision tree
consistent with the input. This simple observation justifies in part why
decision trees have been deemed interpretable for at least two decades [47],
an observation that is widely taken for granted [71, 25, 135, 11], that
motivates many of the applications referenced above, and which explains the
interest in learning optimal decision trees, especially in recent
years333Standard references include [140, 38, 141, 23, 183, 138, 184, 80, 15,
16, 181, 2, 112, 101, 79, 182, 3, 61, 165, 144, 167, 4, 60, 128], and notably
when it is well-known that learning optimal (smallest) DTs is NP-hard [84]. It
should be noted that earlier work encompasses different optimality criteria,
some of which is tightly related with succinctness of explanations (e.g. as
measured by average path length). In contrast with earlier work, this paper
offers a different perspective. Concretely, the paper proves that paths in
decision trees can be arbitrarily larger (on the number of features) than a
logically rigorous explanation for a prediction. Furthermore, the experimental
results, obtained on a wide range of datasets and also on publicly available
DTs, demonstrate that DTs in practice naturally exhibit the same limitation,
i.e. DTs almost invariably have paths that contain more literals than what a
logically rigorous explanation requires. The experiments also demonstrate that
redundancy of literals in DT paths exists _even_ for optimal (and/or sparse)
decision trees [23, 80, 112, 161]. The main corollary of the paper’s
theoretical and experimental results is that succinctness of explanations
cannot be ensured by the paths in decision trees, and must instead be computed
with logically rigorous approaches. This corollary has significant practical
consequences, in some high-risk applications, but also in situations that are
safety-critical. For example, in a medical application [179], an explanation
that contains literals that are unnecessary, may prevent a physician from
focusing on the symptoms that are actually crucial for correct diagnosis. In
more general settings, non-succinct explanations may be beyond the grasp of
human-decision makers [131], whereas (subset-minimal) succinct explanations
may not.

Explanations, such as the ones informally sketched above, essentially
represent an answer to a “Why?” question, i.e.  _why_ is the prediction the
one obtained? Such explanations aim at succinctness by being subset-minimal
(or irreducible). These explanations are referred to as PI-explanations or
abductive explanations (AXp’s) [169, 93]. A different class of explanations
answer a “Why not?” question, i.e.  _why didn’t_ one get a prediction
different from the one obtained? Or what would be necessary to change to get a
different prediction? This sort of explanations also aim at succinctness by
being subset-minimal, and are referred to as contrastive explanations (CXp’s)
[132, 92].

This paper shows that succinctness of explanations of paths in DTs can be
achieved efficiently in practice. Concretely, the paper shows that logically
rigorous explanations, i.e. both AXp’s and CXp’s, can be computed in
polynomial time, and so in practice require negligible time to compute.
Furthermore, the paper shows that, whereas AXp’s can be arbitrarily smaller
than a path in a DT, CXp’s _cannot_. Concretely, the paper shows that, for any
prediction, a contrastive explanation corresponds exactly to the conditions
provided by one of the paths in the decision tree. Furthermore, the paper
proposes path-specific variants of both AXp’s and CXp’s, as opposed to the
instance-specific definitions studied in earlier work. Path-specific
explanations relate with the conditions (i.e. the literals) on a given path,
and so are instance-independent. In addition, the paper shows that these
variants of AXp’s and CXp’s can also be computed in polynomial time.

Compared with earlier work [98, 83], this paper offers comprehensive evidence
regarding the redundancy of path-based explanations in DTs. Concretely, the
paper proves that i) size-minimal DTs can exhibit arbitrary explanation
redundancy, ii) in practice explanation redundancy is often observed, iii) DTs
without explanation redundancy correspond to a very specific class of
classifiers represented as non-overlapping minimal disjunctive normal form
formulas, iv) (provably) optimal sparse DTs also invariably exhibit path
explanation redundancy, v) example DTs used in most textbooks and other
representative references also exhibit explanation redundancy and, finally,
vi) other types of explanations (concretely path explanations, which are
investigated in this paper) reveal important properties in terms of redundancy
of explanations. In addition, the paper builds on earlier work [98, 83]
showing that tools claiming interpretable AI solutions [23, 85] also exhibit
path explanation redundancy, and that this occurs with other well-known
decision tree learners. Therefore, our results serve to complement any state-
of-the-art approach for learning DTs, allowing the computation of path
explanations which are often shorter than DT paths. More importantly, our
results can be used to provide much-needed succinct explanations in high-risk
and safety-critical applications.

#### Main results.

The paper’s main results are organized as follows:

  1. 1.

The paper formalizes in detail the computation of explanations in decision
trees, such that decision trees are allowed to have both categorical and
ordinal features, taking values from arbitrary domains, and such that an
arbitrary number of classes is allowed;

  2. 2.

The paper introduces explanation functions (as an extension of prime implicant
explanations), and proposes conditions for monotonicity of the definition of
abductive and contrastive explanations, which in turn yields a generalized
form of minimal hitting set duality between abductive and contrastive
explanations;

  3. 3.

The paper identifies nesting properties of abductive and contrastive
explanations, which allows enumerating abductive explanations from a subset of
the features;

  4. 4.

The paper uses the two previous results to introduce path explanations and
path explanation redundancy, where path explanations are distinguished from
instance-specific explanations;

  5. 5.

The paper proves that optimal decision trees can exhibit path explanation
redundancy, and that DTs that do not exhibit path explanation redundancy must
correspond to minimal generalized decision functions (GDF) [82] represented in
disjunctive normal form (DNF). The class of functions that can be represented
with such DNF GDFs is argued to be very unlikely to be obtained in practice;

  6. 6.

The paper proposes algorithms for the computation of path explanations, as
follows:

    1. (a)

Three algorithms for computing abductive path explanations, two of which build
on earlier work [98, 83], and a novel one that relates with reasoning about
overconstrained Horn formulas;

    2. (b)

One algorithm for computing all contrastive path explanations; and

    3. (c)

One algorithm for enumerating abductive path explanations by starting from the
hypergraph of contrastive path explanations.

  7. 7.

The paper offers extensive experimental evidence, attesting to the
significance of identifying and removing explanation redundancy from decision
tree paths.

#### Organization.

The paper is organized as follows. Section 2 introduces the notation and
definitions used in the rest of the paper. Sections 3 and 4 detail the paper’s
theoretical foundations, namely duality results and path explanations for DTs.
Path explanations are significant, because these allow relating abductive and
contrastive explanations with the literals in the DT paths. Concretely,
Section 3 proposes a generalization of abductive and contrastive explanations
to explanation functions such that duality between explanations is respected.
This section also reveals a nesting property of explanations, and introduces
path explanations. Furthermore, the section shows how the two previous results
apply in the case of path explanations for DTs. Moreover, Section 4 builds on
path explanations to formalize _path explanation redundancy_ (PXR) for DTs.
First, this section proves that there exist minimum-size DTs that necessarily
exhibit PXR. Second, the section relates DTs that do not exhibit path
explanation redundancy with minimal generalized decision functions [81, 82].
In addition, this section shows that optimal sparse DTs [80] exhibit PXR, and
shows that PXR can represent in practice a much larger fraction of a path than
the explanation itself. Section 5 proposes three polynomial-time algorithms
for computing one abductive path explanation, including a novel and simple
propositional Horn encoding. This section also covers the computation of
contrastive path explanations, and the enumeration of path explanations.
Section 6 presents experimental results that confirm the paper’s main claims:
i) PXR occurs naturally, and can be found in DTs used in a vast number of
research and survey papers and textbooks published over the years; ii) PXR is
ubiquitous in DTs learned with different tree learning algorithms, and that
the time taken to compute explanations (be them abductive or contrastive) is
always negligible; iii) PXR can represent a very significant percentage of the
length of tree paths; and iv) PXR exists even in trees that are optimal (and
sparse) [184, 80, 112, 161]. Section 7 overviews related work on computing
explanations for DTs, and Section 8 concludes the paper.

##  2 Preliminaries

This section overviews the definitions and notation used in the remainder of
the paper. Section 2.1 briefly summarizes the notation for functions used in
the paper, emphasizing function parameterizations, which we will use to
represent families of functions. Section 2.2 includes a brief overview of the
logic foundations the paper builds upon. Section 2.3 introduces classification
problems and the associated notation. Section 2.4 introduces decision trees
and outlines a formalization that is vital for reasoning about DTs. Although
DTs are among the best understood ML models, a rigorous formalization is
required to reason about explanations. Afterwards, Section 2.5 overviews
formal explainability. Finally, Section 2.6 summarizes the notation introduced
in this section and used in the rest of the paper.

###  2.1 Function Representation

A function is well-known to be a mapping from one set to another. We will
allow functions to be parameterized, thus in fact defining families of related
functions, which depend on the choices of parameters. Furthermore, we will
allow functions to be parameterized on an arbitrary (and not necessarily
defined a priori) number of parameters. (Parameterization serves to represent
families of functions, with arguments which are distinguished from the other
arguments, e.g. selected features vs. points in feature space.) As an example,
$f:D\to{C}$ maps a domain $D$ into a codomain $C$. If $d\in{D}$, then $f(d)$
denotes the value of $C$ that $d\in{D}$ is mapped to. $f(d;\pi_{1},\pi_{2})$
denotes that $f$ is parameterized on some given parameters $\pi_{1}$ and
$\pi_{2}$. Moreover, $f(d;\pi,\ldots)$ denotes that $f$ is parameterized on
$\pi$ as well as on a number of additional but yet-undefined parameters. To
keep the notation as simple as possible, we will reveal parameterizations only
when relevant.

###  2.2 Logic Foundations

Definitions and notation standard in mathematical logic, concretely related
with propositional logic and decidable fragments of first-order logic, will be
used throughout the paper [40]. Propositional formulas are defined over
boolean variables taken from some set $X=\\{x_{1},x_{2},\ldots,x_{m}\\}$,
where each boolean variable takes values from $\mathbb{B}=\\{0,1\\}$. A
literal is a variable $x_{i}$ or its negation $\neg{x_{i}}$. A propositional
formula is defined inductively using literals and the standard logic operators
$\lor$ and $\land$ 444For simplicity, we restrict the set of allowed logic
operators. The inductive definition of propositional formulas above could be
extended to accommodate for universal and existential operators; it could also
be extended to accommodate for other well-known logic operators, including
$\neg$, $\operatorname*{\rightarrow}$ and $\leftrightarrow$, among others.: i)
Literals are propositional formulas; ii) If $\varphi_{1}$ and $\varphi_{2}$
are propositional formulas, then $\varphi_{1}\lor\varphi_{2}$ is a
propositional formula; and iii) If $\varphi_{1}$ and $\varphi_{2}$ are
propositional formulas, then $\varphi_{1}\land\varphi_{2}$ is a propositional
formula. A conjunctive normal form (CNF) formula $\varphi$ is a conjunction of
disjunctions of literals. A disjunction of literals is referred to as a
_clause_. A disjunctive normal form (DNF) formula is a disjunction of
conjunctions of literals. A conjunction of literals is referred to as a
_term_. A Horn formula is a CNF formula where each clause does not contain
more than one non-negated literal. We will use quantification where necessary,
with $\forall$ and $\exists$ having respectively the meaning of universal and
existential quantification of variables over their domains.

A _truth assignment_ represents a point $\mathbf{v}=(v_{1},\ldots,v_{m})$ of
$\mathbb{B}^{m}=\\{0,1\\}^{m}$, where the value assigned to each $x_{i}$ is
associated with coordinate $i$. $\mathbf{v}\operatorname*{\vDash}\varphi$ is
defined inductively on the structure of $\varphi$: i)
$\mathbf{v}\operatorname*{\vDash}(\varphi_{1}\lor\varphi_{2})$ iff
$\mathbf{v}\operatorname*{\vDash}\varphi_{1}$ or
$\mathbf{v}\operatorname*{\vDash}\varphi_{2}$; ii)
$\mathbf{v}\operatorname*{\vDash}(\varphi_{1}\land\varphi_{2})$ iff
$\mathbf{v}\operatorname*{\vDash}\varphi_{1}$ and
$\mathbf{v}\operatorname*{\vDash}\varphi_{2}$; iii)
$\mathbf{v}\operatorname*{\vDash}\neg{x_{i}}$ iff $v_{i}=0$; and iv)
$\mathbf{v}\operatorname*{\vDash}{x_{i}}$ iff $v_{i}=1$. If a truth assignment
$\mathbf{v}$ is such that $\mathbf{v}\operatorname*{\vDash}\varphi$, then
$\varphi$ is _satisfied_ by $\mathbf{v}$, and we say that $\mathbf{v}$ is a
_model_ ; otherwise $\varphi$ is _falsified_ by $\mathbf{v}$, and we write
$\mathbf{v}\operatorname*{\nvDash}\varphi$. A formula $\varphi$ is
_satisfiable_ if there exists a truth assignment that satisfies $\varphi$;
otherwise it is _unsatisfiable_ (or _overconstrained_ , or _inconsistent_). If
$\pi$ and $\kappa$ are propositional formulas, then we write
$(\pi\operatorname*{\vDash}\kappa)$ to denote that
$\forall(\mathbf{x}\in\mathbb{B}^{m}).(\mathbf{x}\operatorname*{\vDash}\pi)\operatorname*{\rightarrow}(\mathbf{x}\operatorname*{\vDash}\kappa)$.
Similarly, we write $\pi\operatorname*{\nvDash}\kappa$ to denote that
$\exists(\mathbf{x}\in\mathbb{B}^{m}).(\mathbf{x}\operatorname*{\vDash}\pi)\land(\mathbf{x}\operatorname*{\nvDash}\kappa)$.
A term $\pi$ is a _prime implicant_ of $\kappa$, if
$\pi\operatorname*{\vDash}\kappa$ and for any term $\theta$ such that
$\theta\operatorname*{\vDash}\pi\land\pi\operatorname*{\nvDash}\theta$, it
does not hold that $\theta\operatorname*{\vDash}\kappa$. Similarly, a clause
$\psi$ is a _prime implicate_ of $\kappa$, if
$\kappa\operatorname*{\vDash}\psi$ and for any clause $\gamma$ such that
$\gamma\operatorname*{\vDash}\psi\land\psi\operatorname*{\nvDash}\gamma$, it
does not hold that $\kappa\operatorname*{\vDash}\gamma$.

The definitions above can be extended to domains other than boolean domains,
by allowing the variables to take values from domains that are not necessarily
boolean, and by defining literals using appropriate relational operators [40].
Well-known examples of relational operators include those in
$\\{\leq,\geq,<,>,=,\in\\}$, among others. We can also consider functions
whose codomain is not necessarily boolean, and can also include those in logic
formulas again using suitable relational operators. Concrete examples will be
introduced later in this section when describing decision trees, but also when
introducing formal explanations. Furthermore, in a number of situations, it is
convenient to talk about formulas that consist of conjunctions of other
formulas as _sets of constraints_ , where each constraint can represent a
clause, or a more complex (propositional) formula, thus allowing set notation
to be used with conjunctions of constraints.

For an overconstrained formula, not all of its constraints can be satisfied
simultaneously. In general, overconstrained formulas are split into a set of
_hard_ constraints (i.e. ${\mathcal{H}}$) and a set of _soft_ (or _breakable_
, or weighted, or costed) constraints (i.e. ${\mathcal{B}}$), In such
settings, a number of computational problems can be defined for reasoning
about the pairs $({\mathcal{H}},{\mathcal{B}})$, including: i) finding an
assignment that maximizes the cost of satisfied soft constraints, i.e. the
maximum satisfiability (MaxSAT) problem; ii) finding subset-maximal subsets of
${\mathcal{B}}$ which, together with ${\mathcal{H}}$ are satisfiable, i.e.
finding a maximal satisfiable subset (MSS); iii) finding a subset-minimal set
of clauses ${\mathcal{C}}\subseteq{\mathcal{B}}$ which, if removed from
${\mathcal{B}}$, cause
${\mathcal{H}}\cup({\mathcal{B}}\setminus{\mathcal{C}})$ to be satisfiable,
i.e. finding a minimal correction subset (MCS); and iv) finding a subset-
minimal set of clauses ${\mathcal{U}}\subseteq{\mathcal{B}}$ which together
with ${\mathcal{H}}$ are inconsistent, i.e. finding a minimal unsatisfiable
subset (MUS). There is a comprehensive body of research on algorithms for
reasoning about overconstrained formulas [21, 120, 123, 130, 10, 110, 129,
122, 124, 125, 40].

For some problems, we will use a SAT solver as an oracle. Although a SAT
solver is used for solving a well-known NP-complete problem [54], it is also
the case that a SAT solver ought not be equated with an NP oracle [124]. This
observation is justified by the fact that SAT solvers report satisfying
assignments (or witnesses) for satisfiable formulas. Moreover, most SAT
solvers also report _summaries_ in the case of unsatisfiable formulas, where a
summary is a subset of the clauses that is itself inconsistent. As a result,
when using a SAT solver as a oracle, we are in fact considering a witness-
producing (and most often summary-providing) NP-oracle.

###  2.3 Classification Problems

The paper considers classification problems, defined on a set of features
${\mathcal{F}}=\\{1,\ldots,m\\}$, where each feature $i$ takes values from a
domain ${\mathcal{D}}_{i}$, and $m=|{\mathcal{F}}|$ denotes the number of
features. Each domain ${\mathcal{D}}_{i}$ may be categorical or ordinal.
Ordinal domains can be integer or real-valued. The set of domains is
represented by $\mathbb{D}=({\mathcal{D}}_{1},\ldots,{\mathcal{D}}_{m})$. The
union of domains is $\mathbb{U}=\cup_{i\in{\mathcal{F}}}{\mathcal{D}}_{i}$.
(For the sake of simplicity, several of the examples studied in this paper
consider ${\mathcal{D}}_{i}=\\{0,1\\}$ (i.e. binary features).) Feature space
is defined by
$\mathbb{F}={\mathcal{D}}_{1}\times{\mathcal{D}}_{2}\times\ldots\times{\mathcal{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 concrete (constant)
point in feature space we use the notation $\mathbf{v}=(v_{1},\ldots,v_{m})$,
with $v_{i}\in{D_{i}}$, $i=1,\ldots,m$. Similarly to the case of domains, and
for the sake of simplicity, most examples in the paper consider a binary
classification problem, with two classes $|{\mathcal{K}}|=2$, e.g.
${\mathcal{K}}=\\{\textbf{0},\textbf{1}\\}$,
${\mathcal{K}}=\\{\mathbf{N},\mathbf{Y}\\}$, or
${\mathcal{K}}=\\{\ominus,\oplus\\}$. However, the results in the paper apply
to any decision (or classification) tree used as a classifier. A classifier
computes a non-constant classification function $\kappa$ that maps the feature
space $\mathbb{F}$ into a set of classes, $\kappa:\mathbb{F}\to{\mathcal{K}}$.
Furthermore, a _boolean classifier_ is such that $\mathbb{F}=\\{0,1\\}^{m}$
and ${\mathcal{K}}=\\{0,1\\}$. An _instance_ ${\mathcal{I}}$ (or example)
denotes a pair ${\mathcal{I}}=(\mathbf{v},c)$, where $\mathbf{v}\in\mathbb{F}$
and $c\in{\mathcal{K}}$, such that $\kappa(\mathbf{v})=c$. To train a
classifier (in our case we are interested in DTs), we start from a set of
instances ${\mathcal{I}}_{T}=\\{{I}_{1},\ldots,{I}_{n}\\}$. Algorithms for
learning different families of classifiers can be found in standard references
[48, 149, 150, 157, 134, 162, 68, 192, 166, 5, 148, 46, 191]. There are also
algorithms that learn optimal classifiers (e.g. decision trees), and some
examples are referenced in Section 1.

In this paper, a _literal_ represents a condition on the values of a feature.
Depending on the value assigned to the feature, the literal can be satisfied
or falsified. Throughout the paper, and for consistency of notation, literals
will always be of the form $(x_{i}\in{S_{l}})$, where
$S_{l}\subseteq{\mathcal{D}}_{i}$. This literal is satisfied when feature $i$
is assigned a value from set $S_{l}$; otherwise it is falsified. For
simplicity of notation, when $|S_{l}|=1$ and $S_{l}=\\{v_{i}\\}$ , we may
instead represent a literal by $(x_{i}=v_{i})$. Moreover, the universe of
literals is
$\mathbb{L}=\\{{\mathcal{L}}\,|\,{\mathcal{L}}=(x_{i}\in{S_{l}}),i\in{\mathcal{F}},S_{l}\subseteq{\mathcal{D}}_{i}\\}$.

A point $\mathbf{v}=(v_{1},\ldots,v_{m})$ in feature space
($\mathbf{v}\in\mathbb{F}$) can also be described by a set of $m$ _literals_ ,
each of the form $(x_{i}=v_{i})$, i.e. $\\{(x_{i}=v_{i})|i=1,\ldots,m\\}$.
Alternatively, literals may be represented using set notation, i.e.
$\\{(x_{i}\in\\{v_{i}\\})\,|\,i=1,\ldots,m\\}$.

Finally, given the definitions above, the universe of _classification
problems_ is represented by the set
$\mathbb{M}=\\{{\mathcal{M}}\,|\,{\mathcal{M}}=({\mathcal{F}},\mathbb{D},\mathbb{F},{\mathcal{K}},\kappa)\\}$,
where each tuple
${\mathcal{M}}=({\mathcal{F}},\mathbb{D},\mathbb{F},{\mathcal{K}},\kappa)$
represents a concrete classification problem.

###  2.4 Decision Trees

A decision tree ${\mathcal{T}}=(V,E)$ is a directed acyclic graph having at
most one path between every pair of nodes, with
$V=\\{1,\ldots,\mathfrak{V}\\}$ and $E\subseteq{V}\times{V}$. Moreover, $V$ is
partitioned into a set of non-terminal nodes $N$ and a set of terminal nodes
$T$, i.e. $V=N\cup{T}$. When referring to the _size_ of the decision tree, we
will use $|{\mathcal{T}}|$. ${\mathcal{T}}$ has a root node,
${\textsf{root}}({\mathcal{T}})\in{V}$ characterized by having no incoming
edges, with the convention being that ${\textsf{root}}({\mathcal{T}})=1$. All
other nodes have exactly one incoming edge. Each terminal node is associated
with an element $c$ of ${\mathcal{K}}$. Concretely, we assume a function
$\varsigma$ mapping terminal nodes to one of the classes,
$\varsigma:T\to{\mathcal{K}}$. For non-terminal nodes $\sigma:N\to 2^{V}$ maps
each node $r$ to the set of child nodes of $r$. The paper considers only
univariate decision trees (i.e. each non-terminal node tests only a single
feature). (Possible alternatives include multivariate decision trees [50], but
also non-grounded decision trees [43]; these are beyond the scope of this
paper.) As a result, each non-terminal node is assigned a single feature.
Specifically, we assume a function $\phi$ mapping non-terminal nodes to one of
the features, $\phi:N\to{\mathcal{F}}$. As noted earlier, a variable $x_{i}$
is used to denote values (from ${\mathcal{D}}_{i}$) that can be assigned to
feature $i$. A feature $i$ may be associated with multiple nodes connecting
the tree’s root node to some terminal node. Each edge $(r,s)\in{E}$, with
$\phi(r)=i$, is associated with a literal, representing the values from
${\mathcal{D}}_{i}$ for which the edge is declared consistent. Concretely,
$\varepsilon:E\to\mathbb{L}$ maps each edge $(r,s)$ with a literal of the form
$x_{i}\in{S_{l}}$, with $i=\phi(r)$ and $S_{l}\subseteq{\mathcal{D}}_{i}$. As
noted earlier, literals will _always_ be of the form $(x_{i}\in{S_{l}})$, with
$S_{l}\subsetneq{\mathcal{D}}_{i}$. (We could consider a larger set of
relational operators for representing literals, e.g.
${\\{{\not\in},{=},{\not=},{<},{\leq},{\geq},>\\}}$ among others. To simplify
reasoning about decision trees, only the $\in$ relational operator will be
used; the other relational operators can be translated to the $\in$ operator.)
The definition of literals assumed in the paper allows an edge to be
consistent with multiple values, and so the DTs considered in this paper
effectively correspond to multi-edge decision trees [8]. This more generalized
definition of literals allows modeling the DTs learned by well-known tree
learning tools [178]. Nevertheless, when denoting that an edge for a node
labeled with feature $i$ is consistent only with a single value $v_{i}$, we
may simply label the edge with $v_{i}$ or with $x_{i}=v_{i}$, for the sake of
simplicity. For a given feature, two literals are inconsistent if these
represent sets of values that do not intersect.

######  Example.

The literals $(x_{1}\in\\{0\\})$ and $(x_{1}\in\\{1\\})$ are inconsistent,
because $\\{0\\}\cap\\{1\\}=\emptyset$. In contrast, the literals
$(x_{1}\in\\{1,3\\})$ and $(x_{1}\in\\{2,3,4\\})$ are consistent, because
$\\{1,3\\}\cap\\{2,3,4\\}=\\{3\\}\not=\emptyset$.

A (complete) path $R_{k}$ in a DT ${\mathcal{T}}$ represents a sequence of
nodes $\langle{r_{1}},{r_{2}},\ldots,{r_{l}}\rangle$, with
$r_{1},r_{2},\ldots,r_{l}\in{V}$, that connect the root node to one of the
terminal nodes, and such that $(r_{j},r_{j+1})\in{E}$. Hence,
$r_{1}={\textsf{root}}({\mathcal{T}})=1$ and $r_{l}\in{T}$. Furthermore, the
number of paths in a DT ${\mathcal{T}}$ is $|T|$, i.e. the number of terminal
nodes. Each path is assigned an identifier $R_{k}\in{\mathcal{R}}$, where
${\mathcal{R}}$ denotes the set of paths of ${\mathcal{T}}$. The sequence of
nodes associated with path $R_{k}\in{\mathcal{R}}$, is
${\textsf{seq}}(R_{k})=\langle{r_{1}},{r_{2}},\ldots,{r_{l}}\rangle$. For
simplicity, and with a mild abuse of notation, we also use $R_{k}$ to
represent the sequence of nodes associated with the identified $R_{k}$.

A DT (as any other classifier) computes a (non-constant) classification
function $\kappa:\mathbb{F}\to{\mathcal{K}}$. When studying explanations, we
will consider a concrete instance $(\mathbf{v},c)$, with
$c=\kappa(\mathbf{v})$, and distinguish two sets of paths, one corresponding
to paths with prediction $c$ and another corresponding to paths with a
different prediction. Thus, the set
${\mathcal{P}}=\\{P_{1},\ldots,P_{k_{1}}\\}\subseteq{\mathcal{R}}$ denotes the
paths corresponding to a prediction of $c$. Moreover, the set
${\mathcal{Q}}=\\{Q_{1},\ldots,Q_{k_{2}}\\}\subseteq{\mathcal{R}}$ denotes the
paths corresponding to a prediction in ${\mathcal{K}}\setminus\\{c\\}$.
Furthermore, given the definition of ${\mathcal{P}}$ and ${\mathcal{Q}}$, it
is the case that ${\mathcal{R}}={\mathcal{P}}\cup{\mathcal{Q}}$. When
referring to $R_{k}\in{\mathcal{R}}$, this may represent a path in
${\mathcal{P}}$ or a path in ${\mathcal{Q}}$.

Each path in a DT ${\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}\in{\mathcal{R}}$ by $\mathrm{\Lambda}(R_{k})$. Likewise,
the set of features in some tree path $R_{k}\in{\mathcal{R}}$ is represented
by $\mathrm{\Phi}(R_{k})$. Moreover, each terminal node associated with a path
is represented by $\tau(R_{k})$, $\tau:{\mathcal{R}}\to{T}$. Each path in the
tree _entails_ (meaning that it is sufficient for) the prediction associated
with the path’s terminal node. Let $c\in{\mathcal{K}}$ denote the prediction
associated with path $R_{k}$, i.e. $c=\varsigma(\tau(R_{k}))$. Then, it holds
that,

$\forall(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{(x_{i}\in{S_{l}})\in\mathrm{\Lambda}(R_{k})}(x_{i}\in{S_{l}})\right]\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$
(1)

where $\mathbf{x}=(x_{1},\ldots,x_{i},\ldots,x_{m})$, $c\in{\mathcal{K}}$, and
each $S_{l}\subseteq{\mathcal{D}}_{i}$.

######  Example.

For the example shown in Figure 1, it is the case that,

$\forall((x_{1},x_{2},x_{3})\in\\{0,1\\}^{3}).\left[(x_{1}\in\\{1\\})\land(x_{2}\in\\{1\\})\land(x_{3}\in\\{1\\})\right]\operatorname*{\rightarrow}(\kappa(c)=\textbf{1})$

Furthermore, the classification function associated with this DT can be
represented as follows, for $\mathbf{x}=(x_{1},x_{2},x_{3})$:

$\kappa(\mathbf{x})=\left\\{\begin{array}[]{ccl}1&&\textnormal{iff
$[(x_{1}\in\\{1\\})\land(x_{2}\in\\{1\\})\land(x_{3}\in\\{1\\})]\lor[(x_{1}\in\\{1\\})\land(x_{2}\in\\{0\\})]$}\\\\[3.5pt]
0&&\textnormal{iff
$[(x_{1}\in\\{0\\})]\lor[(x_{1}\in\\{1\\})\land(x_{2}\in\\{1\\})\land(x_{3}\in\\{0\\})]$}\\\
\end{array}\right.$

As discussed below, one underlying assumption is that any pair of paths in
${\mathcal{R}}$ must have at least one pair of inconsistent literals. Let
$(r_{j},r_{j+1})$ denote some edge in path $R_{k}\in{\mathcal{R}}$. Let $i$ be
the feature associated with $r_{j}$, and let
$S_{ij}\subsetneq{\mathcal{D}}_{i}$ represent the set of the literal
$(x_{i}\in{S_{ij}})$, that is associated with the edge $(r_{j},r_{j+1})$.
Given $\mathbf{v}\in\mathbb{F}$, the edge $(r_{j},r_{j+1})$ is consistent with
$\mathbf{v}$ if $v_{i}\in{S_{ij}}$; otherwise the edge is inconsistent. A
predicate ${\textsf{consistent}}(R_{k},\mathbf{v})$ is associated with each
path $R_{k}$ and each point $\mathbf{v}$ in feature space,
${\textsf{consistent}}:{\mathcal{R}}\times\mathbb{F}\to\\{0,1\\}$ (or
alternatively, ${\textsf{consistent}}\subseteq{\mathcal{R}}\times\mathbb{F}$).
The predicate consistent is defined as follows: given the path
$R_{k}\in{\mathcal{R}}$ and the point in feature space
$\mathbf{v}\in\mathbb{F}$, consistent takes value 1 if all edges of $R_{k}$
are consistent given $\mathbf{v}$; otherwise consistent takes value 0.

The paper makes the following general assumption with respect to decision
trees.

######  Assumption 1.

For a DT ${\mathcal{T}}$, it holds that:

  1. 1.

For each point $\mathbf{v}$ in feature space, there exists exactly one path
consistent with $\mathbf{v}$.

$\forall(\mathbf{x}\in\mathbb{F}).\left[\exists(R_{k}\in{\mathcal{R}}).{\textsf{consistent}}(R_{k},\mathbf{x})\land\forall(R_{l}\in{\mathcal{R}}\setminus\\{R_{k}\\}).\neg{\textsf{consistent}}(R_{l},\mathbf{x})\right]$

i.e. each point in feature space must be consistent with at least one path,
and no point in feature space can be consistent with more than one path.

  2. 2.

For each tree path $R_{k}\in{\mathcal{R}}$, there exists at least one point in
feature space that is consistent with the path:

$\forall(R_{k}\in{\mathcal{R}}).\exists(\mathbf{x}\in\mathbb{F}).{\textsf{consistent}}(R_{k},\mathbf{x})$

i.e. there can be no logically inconsistent paths in a DT.

Unless stated otherwise, for the results presented in this paper it is
presupposed that Assumption 1 holds555Assumption 1 outlines what one might
consider fairly reasonable conditions regarding the organization of decision
trees, and indeed appears to capture the intuitive notion of what a decision
tree should represent. However, and perhaps surprisingly, there are recent
examples of tree learning tools that can learn DTs with logically inconsistent
paths, e.g. [179, Fig. 4] and [80, Fig. 6b]. Fortunately, it is simple to
devise linear-time algorithms, on the size of the DT (and for domains of
constant size), for removing logically inconsistent paths. There are also
well-known examples of DTs with points in feature space inconsistent with all
the DT paths, i.e. DTs with _dead-ends_ [64, Figure 8.1]..

The following additional definitions will be considered for DTs. First, let
$\rho:{\mathcal{F}}\times{\mathcal{R}}\to 2^{\mathbb{U}}$ be such that
$\rho(i,R_{k})$ represents the set of values of feature $i$, taken from
${\mathcal{D}}_{i}$, that are consistent with path $R_{k}\in{\mathcal{R}}$.
Clearly, $\rho(i,R_{k})$ is computed by intersecting all the literals testing
the value of feature $i$:

$\rho(i,R_{k})=\bigcap_{(x_{i}\in{S_{l}})\in{\mathrm{\Lambda(R_{k})}}}S_{l}$
(2)

Observe that $\rho(i,R_{k})$ serves to aggregate literals that test the same
feature into a single set of values, each of which is consistent with path
$R_{k}$.

######  Example.

For the example shown in Figure 1, with $Q_{2}=\langle 1,3,5,6\rangle$,
$\rho(2,P_{2})=\\{1\\}$ and $\rho(3,P_{2})=\\{0\\}$.

Moreover, let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}:\mathbb{F}\times{\mathcal{R}}\to
2^{{\mathcal{F}}}$ be such that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}(\mathbf{v},Q_{l})$
represents the subset of features $i$ which takes a value (in $\mathbf{v}$)
that is inconsistent with the values of $i$ that are consistent with $Q_{l}$.
Similarly, let
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}:{\mathcal{R}}\times{\mathcal{R}}\to
2^{{\mathcal{F}}}$ be such that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{k},Q_{l})$
represents the subset of features $i$ for which each value consistent with
$P_{k}$ is inconsistent with the consistent values of $i$ that are consistent
with $Q_{l}$.

######  Example.

For the example shown in Figure 1, with $\mathbf{v}=(0,0,0,0)$, $P_{1}=\langle
1,3,4\rangle$, and $Q_{2}=\langle 1,3,5,6\rangle$, then
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}(\mathbf{v},P_{1})=\\{1\\}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{1},Q_{2})=\\{2\\}$.

#### Running examples.

Throughout the paper, a number of decision trees will be used as running
examples. These DTs are taken from existing references [148, 80, 191,
161]666The choice of examples taken from published references is deliberate,
and aims at illustrating the importance of computing path explanations for
decision trees.. For each of the running examples, and with the purpose of
simplifying the analysis, original feature domains are mapped to symbolic
(numbered) domains. Moreover, all examples of classification problems map to
two classes, which we will represent either by $\\{\textbf{0},\textbf{1}\\}$
or by $\\{\textbf{N},\textbf{Y}\\}$. Clearly, these modifications do not
change in any way the semantics of the original problems.

######  Example 1.

777In this paper, examples that are referenced from the text or by other
examples are numbered; the others are not.

Figure 1 is adapted from [148]. The original DT is learned from a given
dataset [148] using a variant of ID3 [150]. As can be observed,
$N=\\{1,3,5\\}$ and $T=\\{2,4,6,7\\}$. Given the instance
$(\mathbf{v},c)=((1,1,1),1)$, we set $P_{1}=\langle 1,3,4\rangle$,
$P_{2}=\langle 1,3,5,7\rangle$, $Q_{1}=\langle 1,2\rangle$, $Q_{2}=\langle
1,3,5,6\rangle$. Moreover, $P_{2}$ is the path consistent with the instance.
For path $P_{2}$, we have
$\mathrm{\Lambda}(P_{2})=\\{(x_{1}\in\\{1\\}),(x_{2}\in\\{1\\}),(x_{3}\in\\{1\\})\\}$.
Clearly, the literals associated with $\mathbf{v}=(1,1,1)$, i.e. $x_{1}=1$,
$x_{2}=1$ and $x_{3}=1$, are consistent with $x_{1}\in\\{1\\}$,
$x_{2}\in\\{1\\}$ and $x_{3}\in\\{1\\}$, respectively. Additional results for
this DT are summarized in Table 11 (see Table 11). ∎

BDT/.style= for tree= l=1.125cm,s sep=1.0cm, if n children=0circle, draw,
edge= my edge , if n=1 edge+=0 my edge, , , BDT [$x_{1}$,
label=[yshift=-6.875ex]1 [0, label=[yshift=-4.775ex]2, fill=tred3!20, edge
label=node[pos=0.45,left,xshift=-1.0pt] $\in\\{0\\}$] [$x_{2}$,
label=[yshift=-6.875ex]3, edge label=node[pos=0.45,right,xshift=1.0pt]
$\in\\{1\\}$ [1, label=[yshift=-4.775ex]4, fill=tgreen3!25, edge
label=node[pos=0.45,left,xshift=-1.0pt] $\in\\{0\\}$] [$x_{3}$, ,
label=[yshift=-6.875ex]5, edge label=node[pos=0.45,right,xshift=1.0pt]
$\in\\{1\\}$ [0, label=[yshift=-4.775ex]6, fill=tred3!20, edge
label=node[pos=0.45,left,xshift=-1.0pt] $\in\\{0\\}$] [1,
label=[yshift=-4.775ex]7, fill=tgreen3!25, edge
label=node[pos=0.45,right,xshift=1.0pt] $\in\\{1\\}$] ] ] ]

(a) Decision tree

Feature | ID | Var. | Domain | Coded Domain
---|---|---|---|---
Length | 1 | $x_{1}$ | $\\{\textnormal{Long},\textnormal{Short}\\}$ | $\\{0,1\\}$
Thread | 2 | $x_{2}$ | $\\{\textnormal{New},\textnormal{Follow-Up}\\}$ | $\\{0,1\\}$
Author | 3 | $x_{3}$ | $\\{\textnormal{Uknown},\textnormal{Known}\\}$ | $\\{0,1\\}$

Classes |  Coded Representation
---|---
$\\{\textnormal{Skips},\textnormal{Reads}\\}$ |  $\\{0,1\\}$

(b) Mapping of features and classes

Figure 1: Decision tree, adapted from [148, Ch. 07, Fig. 7.4]

######  Example 2.

Figure 2 is adapted from [80]. The original DT was produced with the tool OSDT
(optimal sparse decision trees) [80]. As can be observed,
$N=\\{1,2,4,5,7,8,10\\}$ and $T=\\{3,6,9,11,12,13,14,15\\}$. Given the
instance $(\mathbf{v},c)=((0,0,1,0,1),1)$, we set $P_{1}=\langle
1,2,4,7,10,15\rangle$, $P_{2}=\langle 1,2,4,7,11\rangle$, $P_{3}=\langle
1,2,5,8,13\rangle$, $P_{4}=\langle 1,2,5,9\rangle$, $P_{5}=\langle
1,3\rangle$, and then $Q_{1}=\langle 1,2,4,6\rangle$, $Q_{2}=\langle
1,2,4,7,10,14\rangle$, $Q_{3}=\langle 1,2,5,8,12\rangle$. Moreover, $P_{1}$ is
the path consistent with the instance. As can be observed,
$\mathrm{\Lambda}(P_{1})=\\{(x_{1}\in\\{0\\}),(x_{2}\in\\{0\\}),(x_{3}\in\\{1\\}),(x_{4}\in\\{0\\}),(x_{5}\in\\{1\\})\\}$,
and the literals associated with $\mathbf{v}=(0,0,1,0,1)$ are
$\\{x_{1}=0,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1\\}$, hence being pairwise
consistent. Additional results for this DT are summarized in Table 12 (see
Table 12). ∎

BDT/.style= for tree= l=1.5cm,s sep=1.15cm, if n children=0circle,
draw=black,text=black,edge= my edge , if n=1 edge+=0 my edge, , edge=thick, ,
BDT [$x_{1}$, label=[yshift=-6.875ex]1 [$x_{2}$, label=[yshift=-6.875ex]2,
edge label=node[midway,left,xshift=-0.5pt] $\in\\{0\\}$ [$x_{3}$,
label=[yshift=-6.875ex]4, edge label=node[midway,left,xshift=-2.5pt]
$\in\\{0\\}$ [0, label=[yshift=-5.0ex]6, edge
label=node[midway,left,xshift=-0.5pt] $\in\\{0\\}$, rectangle, fill=tred3!20 ]
[$x_{4}$, label=[yshift=-6.875ex]7, edge label=node[midway,right,xshift=0.5pt]
$\in\\{1\\}$ [$x_{5}$, label=[yshift=-6.875ex]10, edge
label=node[midway,left,xshift=-1.5pt] $\in\\{0\\}$ [0,
label=[yshift=-5.0ex]14, edge label=node[midway,left,xshift=-1.5pt]
$\in\\{0\\}$, rectangle, fill=tred3!20 ] [1, label=[yshift=-5.0ex]15, edge
label=node[midway,right,xshift=0.5pt] $\in\\{1\\}$, rectangle, fill=tgreen3!25
] ] [1, label=[yshift=-5.0ex]11, edge label=node[midway,right,xshift=0.5pt]
$\in\\{1\\}$, rectangle, fill=tgreen3!25 ] ] ] [$x_{4}$,
label=[yshift=-6.875ex]5, edge label=node[midway,right,xshift=1.5pt]
$\in\\{1\\}$ [$x_{5}$, label=[yshift=-6.875ex]8, edge
label=node[midway,left,xshift=-0.5pt] $\in\\{0\\}$ [0,
label=[yshift=-5.0ex]12, edge label=node[midway,left,xshift=-0.5pt]
$\in\\{0\\}$, rectangle, fill=tred3!20 ] [1, label=[yshift=-5.0ex]13, edge
label=node[midway,right,xshift=0.5pt] $\in\\{1\\}$, rectangle, fill=tgreen3!25
] ] [1, label=[yshift=-5.0ex]9, edge label=node[midway,right,xshift=0.5pt]
$\in\\{1\\}$, rectangle, fill=tgreen3!25 ] ] ] [1, label=[yshift=-5.0ex]3,
edge label=node[midway,right,xshift=0.5pt] $\in\\{1\\}$, rectangle,
fill=tgreen3!25 ] ]

(a) Decision tree

Feature in [80] |  Boolean feature
---|---
middle-middle=x |  $x_{1}$
top-left=x |  $x_{2}$
bottom-right=x |  $x_{3}$
bottom-left=x |  $x_{4}$
top-right=x |  $x_{5}$

Definitions
---
${\mathcal{F}}$ | $\\{1,2,3,4,5\\}$
${\mathcal{D}}_{1},\ldots,{\mathcal{D}}_{5}$ | $\\{0,1\\}$
${\mathcal{K}}$ | $\\{0,1\\}$

(b) Mapping of features

Figure 2: Decision tree, adapted from [80, Figure 5b], for the tic-tac-toe
dataset

######  Example 3.

Figure 3 is adapted from [191], and illustrates the application of a standard
tree learning algorithm, but where the features are categorical (and non-
binary). In this case, and for completeness, we show features 5 and 6 (resp.
sound and umbilicus), but these are not associated with any node in the DT. As
can be observed, $N=\\{1,2,3,6,11\\}$, $T=\\{4,5,7,8,9,10,12,13\\}$. Given the
instance $(\mathbf{v},c)=((1,2,1,2),\textbf{Y})$, we set $P_{1}=\langle
1,2,5\rangle$, $P_{2}=\langle 1,2,6,10\rangle$, $P_{3}=\langle
1,2,6,11,12\rangle$, $P_{4}=\\{1,3,9\\}$, and then $Q_{1}=\langle
1,2,6,11,13\rangle$, $Q_{2}=\langle 1,2,7\rangle$, $Q_{3}=\langle
1,3,8\rangle$, $Q_{4}=\langle 1,4\rangle$. Moreover, $P_{3}$ is the path
consistent with the instance. Additional results for this DT are summarized in
Table 11 (see Table 11). ∎

BDT/.style= for tree= l=1.5cm,s sep=1.5cm, if n children=0circle,
draw=black,text=black,edge= my edge , edge=thin, , BDT [$x_{1}$,
label=[yshift=-6.875ex]1, [$x_{2}$, label=[yshift=-0.625ex]2, edge
label=node[pos=0.55,above,xshift=-5.5pt] $\in\\{1\\}$ [Y,
label=[yshift=-5.125ex]5, rectangle, fill=tgreen3!25, edge
label=node[pos=0.45,left,xshift=-4pt] $\in\\{1\\}$ ] [$x_{4}$,
label=[yshift=-6.875ex]6, edge label=node[pos=0.7,right,xshift=-0.575pt]
$\in\\{2\\}$ [Y, label=[yshift=-5.125ex]10, rectangle, fill=tgreen3!25, edge
label=node[pos=0.45,left,xshift=-1.5pt] $\in\\{1,3\\}$ ] [$x_{3}$,
label=[yshift=-6.875ex]11, edge label=node[pos=0.45,right,xshift=0.25pt]
$\in\\{2\\}$ [Y, label=[yshift=-5.125ex]12, rectangle, fill=tgreen3!25, edge
label=node[pos=0.45,left,xshift=-0.5pt] $\in\\{1\\}$ ] [N,
label=[yshift=-5.125ex]13, rectangle, fill=tred3!20, edge
label=node[pos=0.45,right,xshift=0.25pt] $\in\\{2\\}$ ] ] ] [N,
label=[yshift=-5.125ex]7, rectangle, fill=tred3!20, edge
label=node[pos=0.45,right,xshift=3.0pt] $\in\\{3\\}$ ] ] [$x_{3}$,
label=[yshift=-6.875ex]3, edge label=node[pos=0.75,left,xshift=-0.5pt]
$\in\\{2\\}$ [N, label=[yshift=-5.125ex]8, rectangle, fill=tred3!20, edge
label=node[pos=0.45,left,xshift=-0.25pt] $\in\\{1\\}$ ] [Y,
label=[yshift=-5.125ex]9, rectangle, fill=tgreen3!25, edge
label=node[pos=0.45,right,xshift=0.25pt] $\in\\{2\\}$ ] ] [N,
label=[yshift=-5.125ex]4, rectangle, fill=tred3!20, edge
label=node[pos=0.55,above,xshift=4.5pt] $\in\\{3\\}$ ] ]

(a) Decision tree

Classes |  Coded Representation
---|---
$\\{\textnormal{ripe},\textnormal{unripe}\\}$ |  $\\{\textnormal{{Y}},\textnormal{{N}}\\}$

(b) Mapping of classes

Feature | ID | Var. | Domain | Coded Domain
---|---|---|---|---
Texture | 1 | $x_{1}$ | $\\{\textnormal{clear},\textnormal{clightly\leavevmode\nobreak\ blurry},\textnormal{blurry}\\}$ | $\\{1,2,3\\}$
Root | 2 | $x_{2}$ | $\\{\textnormal{curly},\textnormal{slightly\leavevmode\nobreak\ curly},\textnormal{curly}\\}$ | $\\{1,2,3\\}$
Surface | 3 | $x_{3}$ | $\\{\textnormal{hard},\textnormal{soft}\\}$ | $\\{1,2\\}$
Color | 4 | $x_{4}$ | $\\{\textnormal{green},\textnormal{dark},\textnormal{light}\\}$ | $\\{1,2,3\\}$
Sound | 5 | $x_{5}$ | $\\{\textnormal{crisp},\textnormal{muffled},\textnormal{dull}\\}$ | $\\{1,2,3\\}$
Umbilicus | 6 | $x_{6}$ | $\\{\textnormal{flat},\textnormal{slightly\leavevmode\nobreak\ hollow},\textnormal{hollow}\\}$ | $\\{1,2,3\\}$

(c) Mapping of features

Figure 3: Decision tree adapted from [191, Ch. 04, Fig. 4.3]

######  Example 4.

Figure 4 is adapted from [161], and shows a DT for the recividism dataset [7].
Features are categorical or ordinal. (Feature Priors ranges from 0 to 38, and
feature Age ranges from 18 to 96. The symbolic names $\textnormal{MxP}=38$,
$\textnormal{MnA}=18$, $\textnormal{MxA}=96$ are shown in the DT.) A
distinguishing feature of this running example is that one of the features
(Priors) is tested more than once along some of the paths. As can be observed,
$N=\\{1,3,4,6\\}$, $T=\\{2,5,7,8,9\\}$. Given the instance
$(\mathbf{v},c)=((2,20,0),\textbf{Y})$, we set $P_{1}=\langle 1,2\rangle$,
$P_{2}=\langle 1,3,4,6,8\rangle$, $P_{3}=\langle 1,3,4,7\rangle$, and then
$Q_{1}=\langle 1,3,4,6,9\rangle$, $Q_{2}=\langle 1,3,5\rangle$. Moreover,
$P_{2}$ is the path consistent with the instance. Additional results for this
DT are summarized in Table 12 (see Table 12). ∎

BDT/.style= for tree= l=1.5cm,s sep=1.5cm, if n children=0circle,
draw=black,text=black,edge= my edge , edge=thin, , BDT [$x_{1}$,
label=[yshift=-6.875ex]1, [Y, label=[yshift=-5.125ex]2, rectangle,
fill=tgreen3!25, edge label=node[pos=0.45,left,xshift=-1pt]
$\in\\{4..\textnormal{MxP}\\}$ ] [$x_{2}$, label=[yshift=-6.875ex]3, edge
label=node[pos=0.45,right,xshift=1.0pt] $\in\\{0..3\\}$ [$x_{3}$,
label=[yshift=-6.875ex]4, edge label=node[pos=0.55,left,xshift=-0.5pt]
$\in\\{\textnormal{MnA}..25\\}$ [$x_{1}$, label=[yshift=-6.875ex]6, edge
label=node[pos=0.45,left,xshift=-0.25pt] $\in\\{0\\}$ [Y,
label=[yshift=-5.125ex]8, rectangle, fill=tgreen3!25, edge
label=node[pos=0.45,left,xshift=-0.5pt] $\in\\{2,3\\}$ ] [N,
label=[yshift=-5.125ex]9, rectangle, fill=tred3!20, edge
label=node[pos=0.45,right,xshift=0.25pt] $\in\\{0,1\\}$ ] ] [Y,
label=[yshift=-5.125ex]7, rectangle, fill=tgreen3!25, edge
label=node[pos=0.45,right,xshift=0.5pt] $\in\\{1\\}$ ] ] [N,
label=[yshift=-5.125ex]5, rectangle, fill=tred3!20, edge
label=node[pos=0.55,right,xshift=0.25pt] $\in\\{26..\textnormal{MxA}\\}$ ] ] ]

(a) Decision tree

Classes |  Coded Representation
---|---
$\\{\textnormal{Yes},\textnormal{No}\\}$ |  $\\{\textnormal{{Y}},\textnormal{{N}}\\}$

(b) Mapping of classes

Feature | ID | Var. | Domain | Coded Domain
---|---|---|---|---
Priors | 1 | $x_{1}$ | $\\{0,\ldots,\textnormal{MxP}\\}$ | $\\{0,\ldots,\textnormal{MxP}\\}$
Age | 2 | $x_{2}$ | $\\{\textnormal{MnA},\ldots,\textnormal{MxA}\\}$ | $\\{\textnormal{MnA},\ldots,\textnormal{MxA}\\}$
Juvenile crimes | 3 | $x_{3}$ | $\\{0,1\\}$ | $\\{0,1\\}$

(c) Mapping of features

Figure 4: Decision tree adapted from [161, Figure 2]. According to the
dataset, $\textnormal{MnA}=18$, $\textnormal{MxA}=96$ and
$\textnormal{MxP}=38$, but the numbers are be left symbolic.

###  2.5 Formal Explainability

Formal explanation888There is an extensive body of work on non-formal XAI
approaches to XAI [1, 136, 164, 75, 163, 175, 77, 78, 153]. approaches have
been studied in a growing body of research in recent years999A sample of
references on formal explainability includes [169, 93, 170, 94, 139, 188, 14,
57, 58, 168, 152, 44, 92, 118, 98, 119, 100, 117, 83, 13, 89, 12, 55, 45, 81,
151, 114, 185, 59, 42, 9, 82, 88, 121, 74].. Concretely, this paper uses the
definition of _abductive explanation_ [93] (AXp), which corresponds to a PI-
explanation [169] in the case of boolean classifiers. AXp’s represent prime
implicants of the discrete-valued classifier function (which computes the
predicted class)101010There exist also standard references with detailed
overviews of the uses of prime implicants in the context of boolean functions
[76, 56]. Generalizations of prime implicants beyond boolean domains have been
considered before [126]. Prime implicants have also been referred to as
minimum satisfying assignments in first-order logic (FOL) [62], and have been
studied in modal and description logics [39]. . Throughout this paper we will
opt to use the acronym AXp to refer to abductive explanations.

Let us consider a given classifier, computing a classification function
$\kappa$ on feature space $\mathbb{F}$, a point $\mathbf{v}\in\mathbb{F}$,
with prediction $c=\kappa(\mathbf{v})$, and let ${\mathcal{X}}$ denote a
subset of the set of features ${\mathcal{F}}$,
${\mathcal{X}}\subseteq{\mathcal{F}}$. ${\mathcal{X}}$ is a weak AXp for the
instance $(\mathbf{v},c)$ if,

$\begin{array}[]{rcl}\operatorname*{\mathsf{WeakAXp}}({\mathcal{X}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\forall(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{i\in{\mathcal{X}}}(x_{i}=v_{i})\right]\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)\\\
\end{array}$ (3)

(We could highlight that $\operatorname*{\mathsf{WeakAXp}}$ is parameterized
on $\kappa$, $\mathbf{v}$ and $c$, but opt not to clutter the notation, and so
these dependencies will be left implicit.) Thus, given an instance
$(\mathbf{v},c)$, a (weak) AXp is a set of features which, if fixed to the
values dictated by $\mathbf{v}$, then the prediction is guaranteed to be $c$,
independently of the values assigned to the other features. ${\mathcal{X}}$ is
an AXp if, besides being a weak AXp, it is also subset-minimal, i.e.

$\begin{array}[]{rcl}\operatorname*{\mathsf{AXp}}({\mathcal{X}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\operatorname*{\mathsf{WeakAXp}}({\mathcal{X}})\land\forall({\mathcal{X}}^{\prime}\subsetneq{\mathcal{X}}).\neg\operatorname*{\mathsf{WeakAXp}}({\mathcal{X}}^{\prime})\\\
\end{array}$ (4)

An AXp can be viewed as a possible answer to a “Why?” question, i.e. why is
the classifier’s prediction $c$?

It should be plain in this work, but also in earlier work, that the
representation of AXp’s using subsets of features aims at simplicity. The
sufficient condition for the prediction is evidently the conjunction of
literals associated with the features contained in the AXp.

Similarly to the case of AXp’s, one can define (weak) contrastive explanations
(CXp’s) [132, 92]. ${\mathcal{Y}}\subseteq{\mathcal{F}}$ is a weak CXp for the
instance $(\mathbf{v},c)$ if,

$\begin{array}[]{rcl}\operatorname*{\mathsf{WeakCXp}}({\mathcal{Y}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\exists(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{i\not\in{\mathcal{Y}}}(x_{i}=v_{i})\right]\land(\kappa(\mathbf{x})\not=c)\\\
\end{array}$ (5)

(As before, for simplicity we keep the parameterization of
$\operatorname*{\mathsf{WeakCXp}}$ on $\kappa$, $\mathbf{v}$ and $c$
implicit.) Thus, given an instance $(\mathbf{v},c)$, a (weak) CXp is a set of
features which, if allowed to take any value from their domain, then there is
an assignment to the features that changes the prediction to a class other
than $c$, this while the features not in the explanation are kept to their
values (_ceteris paribus_).

Furthermore, a set ${\mathcal{Y}}\subseteq{\mathcal{F}}$ is a CXp if, besides
being a weak CXp, it is also subset-minimal, i.e.

$\begin{array}[]{rcl}\operatorname*{\mathsf{CXp}}({\mathcal{Y}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\operatorname*{\mathsf{WeakCXp}}({\mathcal{Y}})\land\forall({\mathcal{Y}}^{\prime}\subsetneq{\mathcal{Y}}).\neg\operatorname*{\mathsf{WeakCXp}}({\mathcal{Y}}^{\prime})\\\
\end{array}$ (6)

A CXp can be viewed as a possible answer to a “Why Not?” question, i.e. why
isn’t the classifier’s prediction a class other than $c$? A different
perspective for a contrastive explanation is as the answer to a _How?_
question, i.e. how to change the features so as to change the prediction. In
recent literature this alternative view has been investigated under the name
_actionable recourse_ [177, 180, 104, 103]. It should be underlined that
whereas AXp’s correspond to prime implicants of the boolean function
$(\kappa(\mathbf{x})=c)$ that are consistent with some point
$\mathbf{v}\in\mathbb{F}$, CXp are _not_ prime implicates of function
$(\kappa(\mathbf{x})=c)$. Nevertheless, the concept of _counterexample_
studied in formal explainability [93] corresponds to prime implicates of the
function $(\kappa(\mathbf{x})=c)$ (which are not restricted to be consistent
with some specific point $\mathbf{v}\in\mathbb{F}$).

One important observation is that, independently of what $\kappa$ represents,
the $\operatorname*{\mathsf{WeakAXp}}$ and $\operatorname*{\mathsf{WeakCXp}}$
predicates (respectively defined using (3) and (5)) are _monotone_
111111Clearly, from the definition of $\operatorname*{\mathsf{WeakAXp}}$
(resp. $\operatorname*{\mathsf{WeakCXp}}$), if
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})$ (resp.
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}})$) holds, then
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}}^{\prime})$ (resp.
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}}^{\prime})$) also holds for any
superset ${\mathcal{Z}}^{\prime}$ of ${\mathcal{Z}}$. If
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})$ (resp.
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}})$) does not hold, then
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}}^{\prime})$ (resp.
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}}^{\prime})$) also does not hold
for any superset ${\mathcal{Z}}^{\prime}$ of ${\mathcal{Z}}$.. This means that
the tests for minimality (i.e., respectively (4) and (6)) can be simplified
to:

$\begin{array}[]{rcl}\operatorname*{\mathsf{AXp}}({\mathcal{X}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\operatorname*{\mathsf{WeakAXp}}({\mathcal{X}})\land\forall(t\in{\mathcal{X}}).\neg\operatorname*{\mathsf{WeakAXp}}({\mathcal{X}}\setminus\\{t\\})\\\
\end{array}$ (7)

and,

$\begin{array}[]{rcl}\operatorname*{\mathsf{CXp}}({\mathcal{Y}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\operatorname*{\mathsf{WeakCXp}}({\mathcal{Y}})\land\forall(t\in{\mathcal{Y}}).\neg\operatorname*{\mathsf{WeakCXp}}({\mathcal{Y}}\setminus\\{t\\})\\\
\end{array}$ (8)

Observe that, instead of considering all possible subsets of ${\mathcal{X}}$
(resp. ${\mathcal{Y}}$), it suffices to consider the subsets obtained by
removing a single element from ${\mathcal{X}}$ (resp. ${\mathcal{Y}}$). This
observation is at the core of the algorithms proposed in recent years for
computing AXp’s and CXp’s of a growing range of families of classifiers [93,
94, 139, 118, 98, 119, 100, 117, 83, 89, 81].

######  Example 5.

For the DT in Figure 1, consider the instance $((1,1,1),1)$ (i.e. if Length is
Short, and Thread is Follow-Up, and Author is Known, then predict Reads). The
paths in ${\mathcal{P}}$ are: ${\mathcal{P}}=\\{P_{1},P_{2}\\}$, with
$P_{1}=\langle{1},3,4\rangle$ and $P_{2}=\langle{1},3,5,7\rangle$. The paths
in ${\mathcal{Q}}$ are: ${\mathcal{Q}}=\\{Q_{1},Q_{2}\\}$, with $Q_{1}=\langle
1,2\rangle$ and $Q_{2}=\langle 1,3,5,6\rangle$. Path $P_{2}$ is consistent
with the instance; all other paths are inconsistent with the instance. The
features associated with $P_{2}$ are $\mathrm{\Phi}(P_{2})=\\{1,2,3\\}$, and
the path literals associated with path $P_{2}$ are
$\Lambda(P_{2})=\\{(x_{1}\in\\{1\\}),(x_{2}\in\\{1\\}),(x_{3}\in\\{1\\})\\}$.
Nevertheless, from Figure 1, it is clear that ${\mathcal{X}}=\\{1,3\\}$ is a
weak AXp. Indeed, if feature 2 (feature variable $x_{2}$) is allowed to take
any value in its domain, then the prediction remains unchanged. Hence, it is
the case that, with $\mathbf{x}=(x_{1},x_{2},x_{3})$,
$\forall(\mathbf{x}\in\\{0,1\\}^{3}).[(x_{1})\land(x_{3})]\operatorname*{\rightarrow}\kappa(\mathbf{x})$.
Furthermore, ${\mathcal{X}}$ is minimal, since dropping either 1 or 3 from
${\mathcal{X}}$ will cause the weak AXp condition to fail.

CXp’s can be computed in a similar way. One can also observe that if either
$x_{1}$ or $x_{3}$ are allowed to take any value from their domains, then
there is an assignment that causes the prediction to change. Thus,
${\mathcal{Y}}_{1}=\\{1\\}$ or ${\mathcal{Y}}_{2}=\\{3\\}$ are CXp’s of the
given instance. ∎

Given the definitions of AXp and CXp, and building on Reiter’s seminal work
[154], recent work [92] proved the following duality between minimal hitting
sets121212Recall that a set ${\mathcal{H}}$ is a _hitting set_ of a set of
sets ${\mathcal{S}}=\\{S_{1},\ldots,S_{k}\\}$ if
${\mathcal{H}}\cap{S_{i}}\not=\emptyset$ for $i=1,\ldots,k$. ${\mathcal{H}}$
is a minimal hitting set of ${\mathcal{S}}$, if ${\mathcal{H}}$ is a hitting
set of ${\mathcal{S}}$, and there is no proper subset of ${\mathcal{H}}$ that
is also a hitting set of ${\mathcal{S}}$.:

######  Proposition 1 (Minimal hitting-set duality between AXp’s and CXp’s).

AXp’s are minimal hitting sets (MHSes) of CXp’s and vice-versa.

We refer to Proposition 1 as MHS duality between AXp’s and CXp’s. The previous
result has been used in more recent papers for enabling the enumeration of
explanations [119, 89, 83]. Furthermore, a consequence of Proposition 1 is the
following result:

######  Lemma 1.

Given a classifier function $\kappa:\mathbb{F}\to{\mathcal{K}}$, defined on a
set of features ${\mathcal{F}}$, a feature $i\in{\mathcal{F}}$ is included in
some AXp iff $i$ is included in some CXp.

Another minimal hitting-set duality result, different from Proposition 1, was
investigated in earlier work [94], and relates _global_ AXp’s (i.e. not
restricted to be consistent with a specific point $\mathbf{v}\in\mathbb{F}$)
and counterexamples (see Equation 6).

Given the above, the universe of _explanation problems_ is defined by
$\mathbb{E}_{I}=\\{{\mathcal{E}}\,|\,{\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c)),{\mathcal{M}}\in\mathbb{M},\mathbf{v}\in\mathbb{F},c\in{\mathcal{K}},c=\kappa(\mathbf{v})\\}$.
As a result, a tuple $({\mathcal{M}},(\mathbf{v},c))$ will allow us to
unambiguously represent the classification problem ${\mathcal{M}}$ for which
we will be computing AXp’s and CXp’s given the instance $(\mathbf{v},c)$.

###  2.6 Summary of Notation

The notation used throughout the paper is summarized in Table 1 (see Table 1).
(We should note that some of the notation introduced in this paper has also
been used in a number of recent works 131313See for example [93, 139, 94, 86,
118, 87, 98, 119, 100, 89, 55, 83, 121, 82, 88]..)

Symbol | Definition | Meaning
---|---|---
${\mathcal{F}}$ | $\\{1,\ldots,m\\}$ | Set of features
${\mathcal{D}}_{i}$ | – | Domain of feature $i$
$\mathbb{D}$ | $\mathbb{D}=({\mathcal{D}}_{1},\ldots,{\mathcal{D}}_{m})$ | Range of domains, ${\mathcal{D}}_{i}=\mathbb{D}(i)$
$\mathbb{U}$ | $\mathbb{U}=\cup_{i\in{\mathcal{F}}}{\mathcal{D}}_{i}$ | Union of domains
$\mathbb{F}$ | ${\mathcal{D}}_{1}\times{\mathcal{D}}_{2}\times\ldots\times{\mathcal{D}}_{m}$ | Feature space
$x_{i}$ | $x_{i}\in{\mathcal{D}}_{i}$ | Variable associated with feature $i$
${\mathcal{L}}$ | ${\mathcal{L}}=(x_{i}\in{S_{l}})$ | Literal, with $S_{l}\subsetneq{\mathcal{D}}_{i}$
$\mathbb{L}$ | $\mathbb{L}=\\{x_{i}\in{S_{l}}\\}$ | Sets of literals, $i\in{\mathcal{F}}\land{S_{l}}\subsetneq{\mathcal{D}}_{i}$
${\mathcal{K}}$ | $\\{c_{1},\ldots,c_{K}\\}$ | Set of classes
$\kappa$ | $\kappa:\mathbb{F}\to{\mathcal{K}}$ | Classification function
${\mathcal{I}}$ | ${\mathcal{I}}=(\mathbf{v},c)$ | Instance, with $\mathbf{v}\in\mathbb{F},c\in{\mathcal{K}}$
$\mathbb{M}$ | $\mathbb{M}=\\{({\mathcal{F}},\mathbb{D},\mathbb{F},{\mathcal{K}},\kappa)\\}$ | Universe of classification problems
$\mathbb{E}_{I}$ | $\mathbb{E}_{I}=\\{({\mathcal{M}},(\mathbf{v},c))\\}$ | Explanation problems, ${\mathcal{M}}\in\mathbb{M},\mathbf{v}\in\mathbb{F},c\in{\mathcal{K}}$
$\xi$ | $\xi:\mathbb{F}\to\\{0,1\\}$ | Explanation function, $\xi(\mathbf{x};{\mathcal{Z}},\ldots)$, ${\mathcal{Z}}\subseteq{\mathcal{F}}$
$\mathbb{E}_{S}$ | $\mathbb{E}_{S}=\\{({\mathcal{M}},(\xi,{\mathcal{Z}},c))\\}$ | XP problems, ${\mathcal{M}}\in\mathbb{M},{\mathcal{Z}}\subseteq\mathbb{F},c\in{\mathcal{K}}$, $\xi$: XP function
$\mathbb{E}_{P}$ | $\mathbb{E}_{P}=\\{({\mathcal{M}},R_{k})\\}$ | Path-related XP problems, ${\mathcal{M}}\in\mathbb{M},R_{k}\in{\mathcal{R}}$
${\mathcal{T}}$ | ${\mathcal{T}}=(V,E)$ | Decision tree, with nodes $V$ and edges $E$
$V$ | ${N}\cup{T}$ | Set of nodes in DT ${\mathcal{T}}$
$T$ | – | Terminal nodes
$\varsigma$ | $\varsigma:{T}\to{\mathcal{K}}$ | Class associated with each terminal node
$N$ | – | Non-terminal nodes
$\phi$ | $\phi:{N}\to{\mathcal{F}}$ | Feature associated with each non-terminal node
$\sigma$ | $\sigma:N\to 2^{V}$ | Child nodes of non-terminal node
$\varepsilon$ | $\varepsilon:{E}\to\mathbb{L}$ | Lit. $x_{i}\in{S_{l}}$ associated with edge $(r,s)$, $i=\phi(r)$
${\mathcal{R}}$ | – | Paths in DT ${\mathcal{T}}$
$R_{k}$ | $R_{k}=\langle{r_{1}},\ldots,{r_{l}}\rangle$ | Path in DT ${\mathcal{T}}$, with tree nodes $r_{1},\ldots,r_{l}$
seq | – | Sequence of tree nodes in $R_{k}\in{\mathcal{R}}$
$\tau$ | $\tau:{\mathcal{R}}\to{T}$ | Terminal node associated with path $R_{k}\in{\mathcal{R}}$
$\mathrm{\Phi}$ | $\mathrm{\Phi}:{\mathcal{R}}\to 2^{{\mathcal{F}}}$ | Features associated with path $R_{k}$ in ${\mathcal{R}}$
$\mathrm{\Lambda}$ | $\mathrm{\Lambda}:{\mathcal{R}}\to 2^{\mathbb{L}}$ | Literals associated with path $R_{k}$ in ${\mathcal{R}}$
$\rho$ | $\rho:{\mathcal{F}}\times{\mathcal{R}}\to 2^{\mathbb{U}}$ | Values of feature $i$ consistent with $R_{k}\in{\mathcal{R}}$
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}$ | ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}:\mathbb{F}\times{\mathcal{R}}\to 2^{{\mathcal{F}}}$ | Features that are inconsistent between instance and path
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}$ | ${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}:{\mathcal{R}}\times{\mathcal{R}}\to 2^{{\mathcal{F}}}$ | Features that are inconsistent between two paths
${\mathcal{H}}$ | – | hard constraints/clauses
${\mathcal{B}}$ | – | soft constraints/clauses

Table 1: Summary of the notation used throughout the paper

##  3 Duality of Explanations & Path-Based Explanations

This section builds on recent work on duality of explanations [92] (see
Section 2.5), and makes the following contributions:

  1. 1.

Explanations are generalized to explanation functions and conditions are
outlined for minimal hitting-set (MHS) duality of explanations to hold in this
more general setting.

  2. 2.

Explanations are shown to respect a nesting property, with MHS duality holding
for nested explanations.

Furthermore, the section highlights how the results above can be used for
relating the computation of explanations of a DT with specific tree paths
instead of being instance-specific.

###  3.1 Generalized Explanations & Duality

#### Explanation functions.

Besides prime implicants of discrete-valued functions, we can envision a
generalized explanation function $\xi:\mathbb{F}\to\\{0,1\\}$, and redefine
both weak AXp’s and weak CXp’s, assuming such a generalized explanation
function141414Explanation functions have been studied in earlier work on
formal explainability [188]. . However, we impose that $\xi$ be parameterized
on a selected subset ${\mathcal{Z}}$ of the features, and also on other
parameters which we may leave undefined, or instead opt to include. This
parameterization will be represented by:
$\xi(\mathbf{x};{\mathcal{Z}},\ldots)$. For example, if $\xi$ represents a
prime implicant that is sufficient for the prediction, the parameterization
(as discussed in Section 2.5) is the restriction of the conjunction of
literals to those features in ${\mathcal{Z}}$, where the literals are of the
form $x_{i}=v_{i}$ (i.e. the parameterization on ${\mathcal{Z}}$ serves to
select the coordinate values of $\mathbf{v}$ associated with the features in
${\mathcal{Z}}$). However, it is possible to consider explanation functions
that involve other types of literals. Concretely, we will allow explanation
functions to involve literals of the form $(x_{i}\in{S_{l}})$.

Earlier work on formal explainability has most often considered as the
underlying explanation function the prime implicants of discrete-valued
functions, defined on arbitrary feature spaces. Hence, given an instance
$(\mathbf{v},c)$, a possible definition of explanation function is:

$\xi(\mathbf{x};{\mathcal{Z}},\mathbf{v})=\bigwedge_{i\in{\mathcal{Z}}}(x_{i}=v_{i})$
(9)

A clear limitation of using such prime implicants as the explanation function
is that we are equating each feature with a _single_ value from its domain.
For categorical features this is not a major issue, but for ordinal features
it can be too restrictive.

In the case of DT paths, a viable explanation function is:

$\xi(\mathbf{x};{\mathcal{Z}},R_{k},\mathrm{\Lambda}(R_{k}))=\bigwedge_{i\in{\mathcal{Z}},(x_{i}\in{S_{l}})\in\mathrm{\Lambda}(R_{k})}(x_{i}\in{S_{l}})$
(10)

(For simplicity, the parameterization on $R_{k}$ could be ignored, since
$R_{k}$ is in fact a constant when computing explanations that relate with
itself.)

######  Example 6.

For the running example in Figure 4, consider the instance
$((2,25,0),\textbf{Y})$, consistent with path $P_{1}=\langle
1,3,4,6,8\rangle$. It is possible to conclude that a weak AXp is $\\{1,2\\}$.
Observe that there are three features with literals in the path, i.e.
$\\{1,2,3\\}={\mathcal{F}}$, and that changing the value of feature 3 does not
change the prediction; hence a weak AXp is $\\{1,2\\}$. Using the first
explanation function above (see (9)), one could claim that
$(x_{1}=2)\land(x_{2}=25)$ suffices for the prediction. However, using the
second explanation function above (see (10)), one would be able to claim
instead that $(x_{1}\in\\{2,3\\})\land(x_{2}\in\\{\textnormal{MnA}..25\\})$
suffices for the prediction. Clearly, the second explanation function is
markedly more informative regarding which values suffice for the prediction.
(Another extension that this paper does not investigate, is that
$(x_{1}\in\\{2..\textnormal{MxP}\\})\land(x_{2}\in\\{\textnormal{MnA}..25\\})$
would also suffice for the prediction; this is the subject of future work.)
The two explanation functions above exhibit important properties, including
duality relationships; this will be discussed later in this section.
Nevertheless, other explanation functions could be envisioned. ∎

#### Generalizing AXp’s and CXp’s.

Explanation functions serve to generalize weak AXp’s and CXp’s, as follows:

######  Definition 1 ($\operatorname*{\mathsf{WeakAXp}}$ and
$\operatorname*{\mathsf{WeakCXp}}$).

Given a classification problem
${\mathcal{M}}=({\mathcal{F}},\mathbb{D},\mathbb{F},{\mathcal{K}},\kappa)$, an
explanation problem ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$, and an
explanation function $\xi$, ${\mathcal{Z}}\subseteq{\mathcal{F}}$ is a weak
abductive explanation if,

$\begin{array}[]{lcr}\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\forall(\mathbf{x}\in\mathbb{F}).\xi(\mathbf{x};{\mathcal{Z}},\ldots)\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)\\\
\end{array}$ (11)

${\mathcal{Z}}$ is a weak contrastive explanation if,

$\begin{array}[]{lcr}\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}})&\leavevmode\nobreak\
:=\nobreak\leavevmode\nobreak\leavevmode&\exists(\mathbf{x}\in\mathbb{F}).\xi(\mathbf{x};{\mathcal{F}}\setminus{\mathcal{Z}},\ldots)\land(\kappa(\mathbf{x})\not=c)\\\
\end{array}$ (12)

For simplicity, the parameterization of $\operatorname*{\mathsf{WeakAXp}}$ and
$\operatorname*{\mathsf{WeakCXp}}$, on $\xi$, ${\mathcal{M}}$ and
${\mathcal{E}}$, $\mathbf{v}$, etc. is left implicit; this will be clear from
the context.

A consequence of the definition of $\operatorname*{\mathsf{WeakAXp}}$ and
$\operatorname*{\mathsf{WeakCXp}}$ is that we have the following immediate
result:

######  Proposition 2.

For any ${\mathcal{Z}}\subseteq{\mathcal{F}}$, it is the case that,

$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})\leftrightarrow\neg\operatorname*{\mathsf{WeakCXp}}({\mathcal{F}}\setminus{\mathcal{Z}})$

###### Proof.

$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})$ states that,

$\forall(\mathbf{x}\in\mathbb{F}).\xi(\mathbf{x};{\mathcal{Z}},\ldots)\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$

whereas,
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{F}}\setminus{\mathcal{Z}})$ states
that,

$\exists(\mathbf{x}\in\mathbb{F}).\xi(\mathbf{x};{\mathcal{Z}},\ldots)\land(\kappa(\mathbf{x})\not=c)$

which is the logical negation of
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})$. Thus, if
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})$ is true, then it must be the
case that
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{F}}\setminus{\mathcal{Z}})$ is
false, and vice-versa. ∎

We will also need to consider sets of explanations and subset-minimal
explanations. Hence, the following definitions are used:

######  Definition 2 ($\mathbb{S}_{\textnormal{waxp}}$,
$\mathbb{S}_{\textnormal{wcxp}}$, $\mathbb{A}$, $\mathbb{C}$).

Given ${\mathcal{M}}$ and ${\mathcal{E}}$, the following sets of sets are
defined:

$\begin{array}[]{l}\mathbb{S}_{\textnormal{waxp}}=\\{{\mathcal{Z}}\in{\mathcal{F}}\,|\,\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})\\}\\\\[1.5pt]
\mathbb{S}_{\textnormal{wcxp}}=\\{{\mathcal{Z}}\in{\mathcal{F}}\,|\,\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}})\\}\\\
\end{array}$ (13)

The set $\mathbb{A}$ of the subset-minimal sets of
$\mathbb{S}_{\textnormal{waxp}}$ represents the AXp’s, i.e.

$\mathbb{A}=\\{{\mathcal{Z}}\in\mathbb{S}_{\textnormal{waxp}}\,|\,\forall({\mathcal{Z}}^{\prime}\subsetneq{\mathcal{Z}}).\neg\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}}^{\prime})\\}$
(14)

The set $\mathbb{C}$ of the subset-minimal sets of
$\mathbb{S}_{\textnormal{wcxp}}$ represents the CXp’s, i.e.

$\mathbb{C}=\\{{\mathcal{Z}}\in\mathbb{S}_{\textnormal{wcxp}}\,|\,\forall({\mathcal{Z}}^{\prime}\subsetneq{\mathcal{Z}}).\neg\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}}^{\prime})\\}$
(15)

Furthermore, we are especially interested in explanation functions that
guarantee the monotonicity of $\operatorname*{\mathsf{WeakAXp}}$ and
$\operatorname*{\mathsf{WeakCXp}}$. (As noted in Section 2.5, the monotonicity
of these predicates enables devising more efficient algorithms for computing
AXp’s and CXp’s.) Taking into consideration that, from (11) and (12),
$\operatorname*{\mathsf{WeakAXp}}$ and $\operatorname*{\mathsf{WeakCXp}}$ (and
so also AXp and CXp) are defined in terms of $\xi$, then we have the following
definition:

######  Definition 3.

An explanation function $\xi$ is _monotone-inducing_ if, given $\xi$:

  1. 1.

$\operatorname*{\mathsf{WeakAXp}}(\emptyset)=0$ and
$\operatorname*{\mathsf{WeakCXp}}(\emptyset)=0$;

  2. 2.

$\operatorname*{\mathsf{WeakAXp}}({\mathcal{F}})=1$ and
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{F}})=1$;

  3. 3.

Moreover, it holds that, for ${\mathcal{A}}_{0}\subseteq{\mathcal{F}}$,

$\begin{array}[]{l}\operatorname*{\mathsf{WeakAXp}}({\mathcal{A}}_{0})\operatorname*{\rightarrow}\forall({\mathcal{A}}_{1}\supseteq{\mathcal{A}}_{0}).\operatorname*{\mathsf{WeakAXp}}({\mathcal{A}}_{1})\\\\[1.5pt]
\operatorname*{\mathsf{WeakCXp}}({\mathcal{A}}_{0})\operatorname*{\rightarrow}\forall({\mathcal{A}}_{1}\supseteq{\mathcal{A}}_{0}).\operatorname*{\mathsf{WeakCXp}}({\mathcal{A}}_{1})\\\
\end{array}$

(i.e. if ${\mathcal{A}}_{0}$ is a weak AXp (resp. weak CXp) then any of its
supersets (resp. subsets) is also a weak AXp (resp. weak CXp).)

######  Example 7.

The two explanation functions described in 6 are monotone-inducing. The fact
that the explanation function associated with path literals is monotone-
inducing will be pivotal for computing path explanations. ∎

Given the above, we can now state the main result of this section.

######  Proposition 3.

Given ${\mathcal{M}}$ and ${\mathcal{E}}$, $\xi$ is a monotone-inducing
explanation function iff each element of $\mathbb{A}$ is an MHS of the
elements of $\mathbb{C}$, and vice-versa. (This is to say that the AXp’s of
${\mathcal{E}}$ are MHSes of the CXp’s of ${\mathcal{E}}$ and vice-versa.)

###### Proof.

The proof is split into cases:

  1. i)

If $\xi$ is a monotone-inducing explanation function, then AXp’s are MHSes of
CXp’s and vice-versa.
Let ${\mathcal{A}}\in\mathbb{A}$ be an AXp. Thus, ${\mathcal{A}}$ is a subset-
minimal set such that (11) holds. We claim that ${\mathcal{A}}$ must hit every
CXp ${\mathcal{C}}$ of $\mathbb{C}$. For the sake of contradiction, let us
assume that this was not the case. Then, there would exist some
${\mathcal{C}}\in\mathbb{C}$, not hit by ${\mathcal{A}}$. As a result,
${\mathcal{F}}\setminus{\mathcal{A}}$ would necessarily contain
${\mathcal{C}}$. Since ${\mathcal{C}}$ is a CXp, then (12) would be satisfied.
But this is impossible due to Proposition 2; a contradiction.
What remains to show is that the hitting set ${\mathcal{A}}$ is subset-
minimal. Suppose it was not minimal. Then, we could create a minimal hitting
set ${\mathcal{A}}^{\prime}\subsetneq{\mathcal{A}}$, since
${\mathcal{A}}^{\prime}$ would hit all the CXp’s in $\mathbb{C}$, then
$\eqref{eq:gwcxp}$ could be falsified by
${\mathcal{F}}\setminus{\mathcal{A}}^{\prime}$. However, by Proposition 2,
then ${\mathcal{A}}^{\prime}$ would satisfy (11), and so ${\mathcal{A}}$ would
not be minimal; a contradiction.
A similar argument can be used to prove that each ${\mathcal{C}}\in\mathbb{C}$
must hit every ${\mathcal{A}}\in\mathbb{A}$.

  2. ii)

If AXp’s are MHSes of CXp’s and vice-versa, then $\xi$ is a monotone-inducing
explanation function.
This follows from the definition of monotone-inducing explanation function.∎

The result above can be related not only with recent results on the duality of
explanations [94, 92], but also with other well-known results on duality in
different areas [154, 41, 173]. Finally, $\mathbb{E}_{S}$ will be used to
denote the set of explanation problems given a classification problem
${\mathcal{M}}$, a subset ${\mathcal{Z}}$ of the features, and an explanation
function $\xi$, parameterized on ${\mathcal{Z}}$ and other parameters:
$\mathbb{E}_{S}=\\{{\mathcal{E}}\,|\,{\mathcal{E}}=({\mathcal{M}},(\xi,{\mathcal{Z}},c)),{\mathcal{M}}\in\mathbb{M},{\mathcal{Z}}\subseteq{\mathcal{F}},\xi\textnormal{\leavevmode\nobreak\
is an explanation function}\\}$.

###  3.2 Restricted Duality

This section investigates a restricted form of duality that results from AXp’s
exhibiting what can be viewed as a property of _nesting_. We consider an
explanation problem ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$ and a
monotone-inducing explanation function $\xi$. Moreover, we let
${\mathcal{Z}}\subseteq{\mathcal{F}}$, with
${\mathcal{Z}}=\\{i_{1},i_{2},\ldots,i_{M}\\}$, represent a weak AXp, i.e.

$\forall(\mathbf{x}\in\mathbb{F}).\left(\xi(\mathbf{x};{\mathcal{Z}},\ldots)\right)\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$
(16)

Furthermore, let us define
$\mathbb{F}_{{\mathcal{Z}}}={\mathcal{D}}_{i_{1}}\times{\mathcal{D}}_{i_{2}}\times\cdots\times{\mathcal{D}}_{i_{M}}$,
$\mathbb{D}_{{\mathcal{Z}}}=({\mathcal{D}}_{i_{1}},{\mathcal{D}}_{i_{2}},\ldots,{\mathcal{D}}_{i_{M}})$,
and let $\iota:Z=\\{1,\ldots,M\\}\to{\mathcal{Z}}=\\{i_{1},\ldots,i_{M}\\}$ be
a bijective function that maps coordinates 1 to $M$ into the actual features’
indices in ${\mathcal{Z}}$, i.e. $\iota(r)=i_{r}$, $r=1,\ldots,M$ 151515 With
a slight abuse of notation, we will use $\iota^{{-}1}({\mathcal{Z}})$ to
denote the set $Z=\\{1,\ldots,M\\}$. We will also use
$\iota(X)={\mathcal{Z}}\subseteq{\mathcal{Z}}$ and
$\iota^{{-}1}({\mathcal{X}})=X\subseteq{Z}$ to represent the mappings of sets
of features.. In addition, we introduce the predicate
$\textnormal{prj}_{{\mathcal{Z}}}$, such that
$\textnormal{prj}_{{\mathcal{Z}}}(\mathbf{x},\mathbf{y})$ holds when
$\mathbf{y}$ is the projection of $\mathbf{x}$ on the coordinates specified by
${\mathcal{Z}}$, i.e. $y_{j}=x_{\iota(j)}$ for all $j\in{\mathcal{Z}}$.
(Observe that $\textnormal{prj}_{{\mathcal{Z}}}$ is effectively parameterized
on $\iota$, but this is left implicit.) In the concrete case of $\mathbf{v}$,
we define $\mathbf{u}\in\mathbb{F}_{{\mathcal{Z}}}$, such that
$\textnormal{prj}_{{\mathcal{Z}}}(\mathbf{v},\mathbf{u})$ is true. Moreover,
define a binary classifier
$\kappa_{{\mathcal{Z}}}:\mathbb{F}_{{\mathcal{Z}}}\to\\{0,1\\}$, as follows:

$\kappa_{{\mathcal{Z}}}(\mathbf{y})=\left\\{\begin{array}[]{ll}1,\nobreak\leavevmode&\textnormal{if\leavevmode\nobreak\
$\forall(\mathbf{x}\in\mathbb{F}).\left[\textnormal{prj}_{{\mathcal{Z}}}(\mathbf{x},\mathbf{y})\land\xi(\mathbf{x};{\mathcal{Z}},\ldots)\right]\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$}\\\\[7.0pt]
0,\nobreak\leavevmode&\textnormal{if\leavevmode\nobreak\
$\exists(\mathbf{x}\in\mathbb{F}).\left[\textnormal{prj}_{{\mathcal{Z}}}(\mathbf{x},\mathbf{y})\land\xi(\mathbf{x};{\mathcal{Z}},\ldots)\right]\land(\kappa(\mathbf{x})\not=c)$}\\\
\end{array}\right.$ (17)

Observe that, by definition of $\kappa_{{\mathcal{Z}}}$, one can conclude that
$\kappa_{{\mathcal{Z}}}$ is independent of the features in
${\mathcal{F}}\setminus{\mathcal{Z}}$. Also note that
$\kappa_{{\mathcal{Z}}}(\mathbf{y})=1$ only if $\kappa(\mathbf{x})=c$ for all
points $\mathbf{x}\in\mathbb{F}$ which project into
$\mathbf{y}\in\mathbb{F}_{{\mathcal{Z}}}$.

Given the definition of $\kappa_{{\mathcal{Z}}}$, we can now define both a
_restricted_ classification problem
${\mathcal{M}}_{{\mathcal{Z}}}=(Z,\mathbb{D}_{{\mathcal{Z}}},\mathbb{F}_{{\mathcal{Z}}},\\{0,1\\},\kappa_{{\mathcal{Z}}})$,
and associated explanation problem
${\mathcal{E}}_{{\mathcal{Z}}}=({\mathcal{M}}_{{\mathcal{Z}}},(\mathbf{u},1))$.
Clearly, for the explanation problem ${\mathcal{E}}_{{\mathcal{Z}}}$, it must
be the case that AXp’s are the MHSes of the CXp’s and vice-versa [92].
Furthermore, it is plain that the AXp’s and CXp’s of
${\mathcal{E}}_{{\mathcal{Z}}}$ are subsets of $Z$.

######  Example 8.

Consider the DT from Figure 2, and path $P_{4}=\langle 1,2,5,9\rangle$, with
$\varsigma(\tau(9))=\textbf{1}$. Let $\mathbf{v}=(0,1,0,1)$, consistent with
$P_{4}$. It is simple to conclude that ${\mathcal{Z}}=\\{1,2,4\\}$ is a weak
AXp of $(\mathbf{v},c)$. Moreover, we let $\iota(1)=1,\iota(2)=2,\iota(3)=4$,
with $Z=\\{1,2,3\\}$. Given the above, we can define $\kappa_{{\mathcal{Z}}}$.

$y_{1}$ | $y_{2}$ | $y_{3}$ | $\kappa_{{\mathcal{Z}}}$
---|---|---|---
0 | 0 | 0,1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0,1 | 0,1 | 1

(Observe that the use of ’,’ in the rows serves solely to collapse multiple
rows into one.) We can now compute the AXp’s/CXp’s for the explanation problem
$({\mathcal{M}}_{{\mathcal{Z}}},(\mathbf{u},\textbf{1}))$, with
$\mathbf{u}=(0,1,1)$, since
$\textnormal{prj}_{{\mathcal{Z}}}((0,1,0,1),(0,1,1))$ holds.
Given the explanation problem ${\mathcal{E}}_{{\mathcal{Z}}}$, and from the
definition of $\kappa_{{\mathcal{Z}}}$ in the table above, an AXp is
$\\{2,3\\}$. Clearly, the CXp’s will be $\\{2\\}$ and $\\{3\\}$. We can now
map the AXp’s and CXp’s of ${\mathcal{E}}_{{\mathcal{Z}}}$ to the features of
${\mathcal{F}}$. For the AXp, we get a set of features $\\{2,4\\}$, which we
will later argue that it is also an AXp of ${\mathcal{E}}$. For the CXp’s, we
get $\\{2\\}$ and $\\{4\\}$, which we will shortly argue that are subsets of
CXp’s of ${\mathcal{E}}$. Further, we will later argue that these sets of
features relate with abductive and contrastive explanations associated with
path $P_{4}$. ∎

Furthermore, given the definitions above, the following additional results
also hold. Given a set ${\mathcal{Z}}$, and the resulting restricted binary
classifier $\kappa_{{\mathcal{Z}}}$, there is a one to one mapping of AXp’s
between those of ${\mathcal{E}}_{{\mathcal{Z}}}$ and those of ${\mathcal{E}}$;
however, each CXp of ${\mathcal{E}}_{{\mathcal{Z}}}$ is a subset of some CXp
of ${\mathcal{E}}$.

######  Proposition 4.

$X\subseteq{Z}=\iota^{{-}1}({\mathcal{Z}})$ is an AXp of
${\mathcal{E}}_{{\mathcal{Z}}}$ iff
${\mathcal{X}}=\iota(X)\subseteq{\mathcal{Z}}$ is an AXp of ${\mathcal{E}}$.

###### Proof.

Let $\mathbf{y}$ be a point in $\mathbb{F}_{{\mathcal{Z}}}$ consistent with
the features in $X$, and so exhibiting prediction 1. Then, by definition of
$\kappa_{{\mathcal{Z}}}$, it is the case that the prediction of $\kappa$ for
any $\mathbf{x}$, such that $\textnormal{prj}(\mathbf{x},\mathbf{y})$ holds,
must be $c$.
Similarly, let $\mathbf{x}$ be a point in $\mathbb{F}$ consistent with the
features in ${\mathcal{X}}$, and so exhibiting prediction $c$. Then, by
definition of $\kappa_{{\mathcal{Z}}}$, it is the case that the prediction of
$\kappa_{{\mathcal{Z}}}$ for $\mathbf{y}$, such that
$\textnormal{prj}(\mathbf{x},\mathbf{y})$ holds, must be $1$.
Since by hypothesis, $X$ is subset-minimal, then ${\mathcal{X}}=\iota(X)$ is
subset-minimal. ∎

######  Proposition 5.

Each CXp $Y\subseteq{Z}=\iota^{{-}1}({\mathcal{Z}})$ of
${\mathcal{E}}_{{\mathcal{Z}}}$ is such that
${\mathcal{Y}}=\iota(Y)\subseteq{\mathcal{Z}}$ is a subset of some CXp of
${\mathcal{E}}$.

###### Proof.

By definition, a CXp $Y\subseteq{Z}$ of ${\mathcal{E}}_{{\mathcal{Z}}}$ is a
subset-minimal set of features in $Z$ which, if allowed to take any value from
their domains, suffice to change the prediction. However, for ${\mathcal{E}}$
and given $\mathbf{v}$, the features in ${\mathcal{F}}\setminus{\mathcal{Z}}$
take specific fixed values, dictated by $\mathbf{v}$. Hence, some of these
features may be required to change their values for the prediction of $\kappa$
to change from $c$ to some of the class in ${\mathcal{K}}\setminus\\{c\\}$.
This follows from the definition of $\kappa_{{\mathcal{Z}}}$ in (17). As a
result, it may be necessary to add to ${\mathcal{Y}}=\iota(Y)$ additional
features from ${\mathcal{F}}\setminus{\mathcal{Z}}$ so that the prediction
changes. A minimal such set is a CXp of ${\mathcal{E}}$ and it represents a
superset of ${\mathcal{Y}}$. Furthermore, no feature in $Y$ (and so in the
resulting ${\mathcal{Y}}$) is redundant, since $Y$ is by definition a minimal
set, even if the features not in ${\mathcal{Z}}$ are allowed to change their
value. ∎

Furthermore, one additional result that is a consequence of the previous
results is that the relationships between AXp’s and CXp’s can be stated in
terms of AXp’s and CXp’s that are restricted to some _seed_ set.

######  Definition 4 (Set-restricted AXp’s/CXp’s).

Let ${\mathcal{E}}$ be an explanation problem and let
${\mathcal{Z}}\in{\mathcal{F}}$ be a weak AXp of ${\mathcal{E}}$. The
${\mathcal{Z}}$-set-restricted AXp’s are the AXp’s of
${\mathcal{E}}_{{\mathcal{Z}}}$ mapped by $\iota$ to the indices of features
in ${\mathcal{F}}$, and it is represented by $\mathbb{A}_{{\mathcal{Z}}}$. The
${\mathcal{Z}}$-set-restricted CXp’s are the CXp’s of
${\mathcal{E}}_{{\mathcal{Z}}}$ mapped by $\iota$ to the indices of features
in ${\mathcal{F}}$, and it is represented by $\mathbb{C}_{{\mathcal{Z}}}$.

Given the definition of set-restricted AXp’s/CXp’s, we have the following
result:

######  Proposition 6.

Let ${\mathcal{E}}$ be an explanation problem, and let ${\mathcal{Z}}$ be a
weak AXp for ${\mathcal{E}}$. Then,
$\mathbb{A}_{{\mathcal{Z}}}\subseteq\mathbb{A}$, i.e. each
${\mathcal{Z}}$-set-restricted AXp is also an AXp. Furthermore, for each
${\mathcal{W}}\in\mathbb{C}_{{\mathcal{Z}}}$, there exists
${\mathcal{Y}}\in\mathbb{C}$ such that ${\mathcal{W}}\subseteq{\mathcal{Y}}$.

###### Proof.

This result is a consequence of Propositions 4 and 5. ∎

Furthermore, due to MHS duality between AXp’s and CXp’s, we can compute all
the AXp’s of ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$ that are contained
in ${\mathcal{Z}}$, by hitting set dualization using the CXp’s in
$\mathbb{C}_{{\mathcal{Z}}}$.

######  Proposition 7.

Each element of $\mathbb{A}_{{\mathcal{Z}}}$ is a MHS of the elements in
$\mathbb{C}_{{\mathcal{Z}}}$ and vice-versa.

###### Proof.

This result follows from Propositions 1, 4, 5 and 6. ∎

Building on earlier results on duality of explanations [94, 92], Propositions
4, 5, 7 and 6 uncover yet another dimension of the duality of explanations.
This new dimension reveals nesting properties of AXp’s and CXp’s.

######  Corollary 1.

Let ${\mathcal{W}}\subseteq{\mathcal{Z}}\subseteq{\mathcal{F}}$. Then,

  1. 1.

The ${\mathcal{W}}$-set-restricted AXp’s are a subset of the
${\mathcal{Z}}$-set-restricted AXp’s.

  2. 2.

Each ${\mathcal{W}}$-set-restricted CXp is a subset of some
${\mathcal{Z}}$-set-restricted CXp.

  3. 3.

The ${\mathcal{W}}$(or ${\mathcal{Z}}$)-set-restricted AXp’s can be obtained
from the ${\mathcal{W}}$(or ${\mathcal{Z}}$)-set-restricted CXp’s by hitting
set dualization, and vice-versa.

######  Example 9.

Consider the running example from Figure 2, and the instance
$((0,1,1,1,1),\textbf{1})$ consistent with path $\langle 1,2,5\rangle$, and
defining an explanation problem ${\mathcal{E}}$. Consider the set of features
${\mathcal{W}}=\\{2,4\\}$. Clearly, $(x_{2}=1)\land(x_{4}=1)$ suffices for the
prediction. We can also conclude that $\\{2,4\\}$ is an AXp. Moreover,
$\\{2\\}$ and $\\{4\\}$ are ${\mathcal{W}}$-set-restricted CXp’s, and MHS
duality is observed. Now consider the set of features
${\mathcal{Z}}=\\{2,3,4,5\\}$. Clearly,
$(x_{2}=1)\land(x_{3}=1)\land(x_{4}=1)\land(x_{5}=1)$ suffices for the
prediction. In this case, careful analysis reveals that $\\{2,4\\}$ and
$\\{3,5\\}$ are ${\mathcal{Z}}$-set-restricted AXp’s of ${\mathcal{E}}$ (and
so also plain AXp’s of ${\mathcal{E}}$). As a result,$\\{2,3\\}$, $\\{2,5\\}$,
$\\{3,4\\}$, $\\{4,5\\}$ are ${\mathcal{Z}}$-set-restricted CXp’s, and again
MHS duality is observed. As can be observed, for the subset ${\mathcal{W}}$ of
${\mathcal{Z}}$, the AXp’s are a subset of the AXp’s of ${\mathcal{Z}}$, and
each CXp restricted to ${\mathcal{W}}$ is a subset of the CXp’s restricted to
${\mathcal{Z}}$.
Another observation related with this example, is that although both
$\\{2,4\\}$ and $\\{3,5\\}$ are AXp’s of the original explanation problem,
only the first one is clearly related with path $P_{4}$ of the DT. ∎

###  3.3 Path Explanations

Paths in DTs can contain literals for a subset of the features, and can be
consistent with many (possibly uncountable) points in feature space. The goal
of this section is to investigate _path explanations_ ; these represent sets
of features such that (3) holds true for _any_ instance consistent with some
given path. We will consider both abductive and contrastive path explanations,
but we will also investigate how enumeration of path explanations can be
instrumented.

We will now show how the results in Sections 3.1 and 3.2 can be used to
formalize path explanations and subsequently the concept of explanation
redundancy in DT paths. First, Section 3.1 showed how to reason in terms of
literals associated with paths and not literals associated with points in
feature space. Second, Section 3.2 showed how to analyze duality of
explanations in the case when sets of features (concretely those not tested in
a given path) are excluded from explanations.

Consider a path $R_{k}\in{\mathcal{R}}$ in a DT ${\mathcal{T}}$. We define the
following (path-based) explanation function, for
${\mathcal{Z}}\subseteq\mathrm{\Phi(R_{k})}$:

$\xi(\mathbf{x};{\mathcal{Z}},\ldots)=\left[\bigwedge_{\begin{subarray}{c}j\in{\mathcal{Z}}\\\\[1.5pt]
(x_{j}\in{S_{l}})\in\mathrm{\Lambda(R_{k})}\end{subarray}}(x_{j}\in{S_{l}})\right]$
(18)

(Observe that this explanation function was first discussed in 6.) As a
result, given the proposed explanation function $\xi$, and as outlined in
Section 3.1 we can define both weak AXp’s and CXp’s.

######  Example 10.

For the DT in Figure 2, we consider path $P_{4}=\langle 1,2,5,9\rangle$, and
so with $c=\textbf{1}$. In this case, we have that
$\mathrm{\Phi}(P_{4})=\\{1,2,4\\}$. For ${\mathcal{Z}}=\mathrm{\Phi}(P_{4})$
we get,

$\xi(\mathbf{x};{\mathcal{Z}},\ldots)=\left[(x_{1}\in\\{0\\})\land(x_{2}\in\\{1\\})\land(x_{4}\in\\{1\\})\right]\qed$

In addition, path explanations are defined using the explanation function
proposed in (18).

######  Definition 5 (Path Explanations).

A (weak) path AXp (resp. CXp) is a (weak) AXp (resp. CXp) given the
explanation function (18).

A path AXp will be denoted an _abductive path explanation_ (APXp); a path CXp
will be denoted a _contrastive path explanation_ (CPXp). An explanation
problem associated with a path in a DT is represented by the tuple
$({\mathcal{M}},R_{k})$. Moreover, to distinguish the two kinds of
explanations, those introduced in Section 2.5 will be referred to as
_instance-based_ explanations. Observe that the key difference between
instance-based and path-based explanations are the literals used in the
definition of explanation. For instance-based explanations, the literals are
obtained from the point in feature space, whereas for path-based explanations,
the literals are obtained from the conditions on features specified along the
given path.

One alternative to path explanations would be to consider instance-based AXp’s
and CXp’s, as introduced in Section 2.5, by considering some point in feature
space consistent with the given path. However, such explanations offer
information that might be too specific.

######  Example.

Consider a classification problem ${\mathcal{M}}$ with
${\mathcal{F}}=\\{1,2,3\\}$,
$\mathbb{D}=({\mathcal{D}}_{1},{\mathcal{D}}_{2},{\mathcal{D}}_{3})$, with
${\mathcal{D}}_{1}=\mathbb{R}$ and
${\mathcal{D}}_{2}={\mathcal{D}}_{3}=\mathbb{N}_{0}$. Let the classifier be
represented by a DT, with path $P_{1}=\langle 1,2,3,4\rangle$ with
$\mathrm{\Lambda}(P_{1})=\\{(x_{1}\in[\textnormal{V}_{\textnormal{min}},10]),(x_{2}\in\\{0,1,2,3,4\\}),(x_{3}\in\\{0,1\\})$,
and with $\phi(1)=3$, $\phi(2)=2$, $\phi(3)=1$, and with
$\varsigma(\tau(P_{2}))=1$. Given the instance $(\mathbf{v},c)=((0,0),1)$, let
the AXp be $\\{1,2\\}$. The information that the conjunction
$(x_{1}=0)\land(x_{2}=0)$ represents a sufficient condition for the prediction
to be 1, is clearly less instructive than the information that
$(x_{1}\in[\textnormal{V}_{\textnormal{min}},10])\land(x_{2}\in\\{0,1,2,3,4\\})$
also represents a sufficient condition for the prediction to be 1.

Moreover, from Proposition 7 one can readily conclude that path AXp’s and
CXp’s exhibit MHS duality.

######  Proposition 8.

For a DT ${\mathcal{T}}$ with set of paths ${\mathcal{R}}$, and a path
$R_{k}\in{\mathcal{R}}$, the APXp’s of $R_{k}$ are the MHSes of the CPXp’s of
$R_{k}$ and vice-versa.

###### Proof.

This result instantiates, in the case of paths in DTs, the result of
Proposition 7 for restricted duality. ∎

Given the generalized definition of weak AXp in Definition 1, it is plain
that, for $\operatorname*{\mathsf{WeakAXp}}$ defined using $\xi$,
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{Z}})=1$ and
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{Z}})=1$ for
$\mathrm{\Phi}(P_{k})\subseteq{\mathcal{Z}}\subseteq{\mathcal{F}}$, and so
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{F}})$ and
$\operatorname*{\mathsf{WeakCXp}}({\mathcal{F}})$ are true. (Observe that it
is assumed that the classifier is non-constant.) It is also clear that
$\operatorname*{\mathsf{WeakAXp}}(\emptyset)=0$ and
$\operatorname*{\mathsf{WeakCXp}}(\emptyset)=0$. Finally, one can also
conclude that if $\operatorname*{\mathsf{WeakAXp}}({\mathcal{A}}_{0})=1$, then
$\operatorname*{\mathsf{WeakAXp}}({\mathcal{A}}_{1})=1$ for
${\mathcal{A}}_{1}\supseteq{\mathcal{A}}_{0}$. The same observation holds for
weak CXp’s. As a result, by Definition 3 we can conclude that $\xi$ is
monotone-inducing. Thus, by Proposition 3, there is duality between AXp’s and
CXp’s given the explanation function $\xi$.

Despite $\xi$ representing an explanation function, we must also understand
how the explanations obtained with $\xi$ relate with the explanations for the
decision tree ${\mathcal{T}}$.

As shown next, we can relate path explanations and path explanation duality
with restricted duality.

######  Proposition 9.

Let ${\mathcal{M}}$ be the classification problem associated with DT
${\mathcal{T}}$, let ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$ denote an
explanation problem given some instance $(\mathbf{v},c)$ consistent with
$P_{k}\in{\mathcal{R}}$, and let $\xi$ be the explanation function associated
with $P_{k}$, i.e. the conjunction of the literals in
$\mathrm{\Lambda}(P_{k})$. Then,

  1. 1.

Each APXp of $P_{k}$ is an AXp for ${\mathcal{E}}$ that is contained in
$\mathrm{\Phi}(P_{k})$;

  2. 2.

Each CPXp of $P_{k}$ is a subset of some CXp for ${\mathcal{E}}$ that is
contained in $\mathrm{\Phi}(P_{k})$.

###### Proof.

This result follows from the results in Sections 3.1 and 3.2 and the results
earlier in this section. ∎

######  Example 11.

We revisit 8. Let ${\mathcal{Z}}=\mathrm{\Phi}(P_{4})=\\{1,2,4\\}$:
$\mathrm{\Lambda}(P_{4})=\\{(x_{1}\in\\{0\\}),(x_{2}\in\\{1\\}),(x_{4}\in\\{1\\})\\}$
Thus, the explanation function can be defined as follows,

$\xi(\mathbf{x};{\mathcal{Z}},\ldots)=\bigwedge_{j\in{\mathcal{Z}},(x_{j}\in{S_{l}})\in\mathrm{\Lambda}(P_{4})}(x_{j}\in{S_{l}})$

Given the definition of path explanations (and so of (generalized) AXp’s and
CXp’s), we can conclude that ${\mathcal{X}}=\\{2,4\\}$ is a path AXp for
$P_{4}$. Moreover, ${\mathcal{Y}}_{1}=\\{2\\}$ and ${\mathcal{Y}}_{2}=\\{4\\}$
are path CXp’s for $P_{4}$. It can be observed that ${\mathcal{X}}$ is an AXp
for _any_ instance $(\mathbf{v},\textbf{1})$, with $\mathbf{v}$ consistent
with $P_{4}$. However, both ${\mathcal{Y}}_{1}$ and ${\mathcal{Y}}_{2}$ are
subsets of CXp’s of possible instances $(\mathbf{v},\textbf{1})$, consistent
with $P_{4}$. For example, one can identify a CXp $\\{2,3\\}$ and also a CXp
$\\{4,5\\}$. ∎

The fact that path explanations can be related with AXp’s restricted to a
specific set of features also signifies that not all instance-based
explanations represent path explanations. This observation can be related with
the distinction between path-restricted and path-unrestricted explanations
first studied in [98].

######  Example 12.

For the running example shown in Figure 2, we analyze the abductive
explanations of path $P_{4}=\langle 1,2,5,9\rangle$. Suppose we are given the
instance is $(\mathbf{v},c)=((0,1,1,1,1),1)$. An AXp is $\\{3,5\\}$. However,
this explanation offers little insight to why the prediction is 1 for the
instances that are consistent with $P_{4}$. Using the nomenclature of earlier
work [98], whereas $\\{3,5\\}$ is a path-unrestricted explanation, $\\{2,4\\}$
is a path-restricted explanation. In this paper, we consider only path
explanations, and so $\\{2,4\\}$ is the only path AXp we are interested in
computing. ∎

Explanation | Definition | Literals used in $\bm{\xi}$ | Features containing XP
---|---|---|---
AXp, path-unrestricted | (3)(7) | Instance-based | ${\mathcal{F}}$
CXp, path-unrestricted | (5)(8) | Instance-based | ${\mathcal{F}}$
AXp, path-restricted | (3)(7) | Instance-based | $\mathrm{\Phi}(R_{k})$
CXp, path-restricted | (5)(8) | Instance-based | $\mathrm{\Phi}(R_{k})$
APXp | Definition 5 | Path-based | $\mathrm{\Phi}(R_{k})$
CPXp | Definition 5 | Path-based | $\mathrm{\Phi}(R_{k})$
Table 2: Types of explanations considered in the paper, both for some path
$R_{k}\in{\mathcal{R}}$ and for any instance $(\mathbf{v},c)$ consistent with
$R_{k}$

Table 2 summarizes the kinds of explanations considered in this paper. APXp’s
and CPXp’s are introduced in this paper and, in contrast with the other kinds
of explanations, these are defined in terms of literals obtained from a
specific DT path. Clearly, due to being instance-independent, path
explanations offer a simpler solution to represent explanations of decision
trees that only depend on the structure of the tree. Furthermore, a few
additional results are consequences of the results presented in this section.
For example, despite being based on a different semantics, there is a one-to-
one mapping between the APXp’s of $R_{k}$ and the path-restricted AXp’s of any
instance consistent with $R_{k}$. The sole difference between path-restricted
AXp’s and APXp’s is that the literals associated with APXp’s are taken from
the associated path, whereas the literals associated with path-restricted
AXp’s are obtained from a concrete instance (consistent with the path).
Finally, $\mathbb{E}_{P}$ denotes the set of explanation problems given a
classification problem ${\mathcal{M}}$, and a path $R_{k}\in{\mathcal{R}}$ in
a decision tree ${\mathcal{T}}$:
$\mathbb{E}_{P}=\\{{\mathcal{E}}\,|\,{\mathcal{E}}=({\mathcal{M}},R_{k}),{\mathcal{M}}\in\mathbb{M},R_{k}\in{\mathcal{R}}\\}$.
In the rest of the paper, ${\mathcal{M}}$ is assumed to be such that the
classification function $\kappa$ is monotone-inducing,

##  4 Path Explanation Redundancy in Decision Trees

Given the definition of path explanations in Section 3.3, we can formalize the
concept of path explanation redundancy.

######  Definition 6 (Explanation Redundant Path/Feature (XRP/XRF)).

Given a DT ${\mathcal{T}}$, with set of paths ${\mathcal{R}}$, and a path
$R_{k}\in{\mathcal{R}}$, $R_{k}$ is an _explanation-redundant path_ (or XRP)
if $\mathrm{\Phi}(R_{k})$ does not represent a path AXp. Given a path AXp
${\mathcal{X}}$ for $R_{k}$, any feature $i\in\mathrm{\Phi}(R_{k})$ that is
not included in ${\mathcal{X}}$ is a _explanation-redundant feature_ (or XRF).

Feature redundancy is relative to a given APXp. Different APXp’s can yield
different redundant features. Clearly, one can consider the enumeration of
APXp’s to identify the set of features that is never-redundant, by enumerating
all APXp’s for a given path, and discarding any of the features deemed
redundant for all of the APXp’s.

###  4.1 Explanation Redundancy in Running Examples

The following examples illustrate path explanations and explanation
redundancy.

######  Example 13.

With respect to 2, with the DT shown in Figure 2, let the target path be
$P_{1}=\langle 1,2,4,7,10,15\rangle$. (In this case there is only one point in
feature space consistent with $P_{1}$, i.e. $(0,0,1,0,1)$.) We claim that
${\mathcal{X}}=\\{3,5\\}$ is a weak APXp, and so that $P_{1}$ is explanation-
redundant. To prove the claim, we consider all the possible assignments to the
other features:

Feature | Assignments
---|---
$x_{1}$ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1
$x_{2}$ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1
$x_{4}$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1
$\kappa(x_{1},x_{2},1,x_{4},1)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1

As can be concluded, as long as $x_{3}=1$ and $x_{5}=1$, then the prediction
remains unchanged, since $\kappa(x_{1},x_{2},1,x_{4},1)$ only takes value 1,
for any assignment to $x_{1},x_{2},x_{4}$. In this case, we can observe that a
path-based explanation of size 5 can be reduced to a (weak) abductive path
explanation of size 2. Hence, there are (at least) 3 redundant features
(namely features 1, 2 and 4) out of a total of 5 features included in path
$P_{1}$. The redundant features represent 60% of the original path length. As
noted earlier, this DT was generated by the GOSDT/OSDT ((generalized scalable)
optimal sparse decision trees) tools [80, 112, 161], that specifically target
interpretability. ∎

######  Example 14.

With respect to 3, with the DT shown in Figure 3, let the target path be
$P_{3}=\langle 1,2,6,11,12\rangle$. (In this case there is only one point in
feature space consistent with $P_{3}$: $(1,2,1,2)$.) It is easy to conclude
that ${\mathcal{X}}=\\{1,2,3\\}$ is a weak APXp, and so that $P_{3}$ is
explanation-redundant. Indeed, if $x_{4}$ is allowed to take any value, then
one can observe that the prediction remains unchanged. ∎

######  Example 15.

With respect to 4, with the DT shown in Figure 4, let the target path be
$P_{2}=\langle 1,3,4,6,8\rangle$. (An example of a point in feature space
consistent with $P_{2}$ is $(2,20,0)$.) It is easy to conclude that neither
$x_{1}$ nor $x_{2}$ are allowed to take any value, whereas $x_{3}$ can be
unrestricted. Hence, ${\mathcal{X}}=\\{1,2\\}$ is a weak APXp. Since neither
$x_{1}$ nor $x_{2}$ can be dropped, then $\\{1,2\\}$ is an APXp. The literals
associated with the APXp are
$\\{(x_{1}\in\\{2\\}),(x_{2}\in\\{\textnormal{MnA}..25\\})\\}$. ∎

The examples above reveal that DTs taken from recent textbooks and papers
often exhibit path explanation redundancy. Moreover, the examples above also
show that DTs taken from papers that specifically address the learning of
optimal sparse DTs (which aim at interpretability) can exhibit path
explanation redundancy. In fact, some examples confirm that there can exist
paths in optimal sparse decision trees for which there are more redundant
features than non-redundant features. Section 4.2 offers a high-level
perspective of the experimental results, which reveal that path explanation
redundancy in DTs is indeed ubiquitous. Afterwards, Section 4.3 proves that
there are functions for which path explanation redundancy is unavoidable, even
in provably size-minimal DTs. These results and observations offer conclusive
evidence regarding the significance of filtering path explanation redundancy
from DT explanations, and further underline the critical importance of
efficient algorithms for computing explanations in DTs.

###  4.2 Path Explanation Redundancy in Practice

This section summarizes some key takeaways that can be drawn from the
experimental results (see Section 6), and which offer ample practical
justification for computing AXp’s of DTs (and so finding and filtering path
explanation redundancy).

#### Path explanation redundancy in published examples.

Table 11 (see Table 11) summarizes results on path explanation redundancy for
DTs included in representative bibliography on DTs, namely textbooks and
surveys161616A non-exhaustive list of references includes [137, 48, 150, 49,
65, 159, 38, 162, 22, 68, 192, 108, 5, 166, 106, 6, 179, 148, 187, 46, 191]..
The key observation is that path explanation redundancy is ubiquitous in most
DTs that have been used as examples in textbooks and surveys over the years,
going back to the inception of tree learning algorithms.

#### Path explanation redundancy in learned DTs.

Table 6 and Table 7 (see Table 6 and Table 7) summarize the results obtained
with two different, publicly available tree learning tools, namely
Interpretable AI (IAI) [23, 85] and ITI [178], on a large number of publicly
available datasets. IAI is a recent tool that specifically targets the
learning of _interpretable DTs_. As can be concluded from the results, for
most datasets, the DTs learned by both algorithms exhibit a significant
percentage of explanation redundant paths. Moreover, for paths that exhibit
explanation redundancy, the number of redundant literals can also be
significant.

#### Large-scale path explanation redundancy.

Table 10 (see Table 10) shows results for DTs learned on more complex datasets
(which are also publicly available). For these examples, the number of
explanation redundant features can far exceed the number of explanation
relevant features. Concretely for some examples, the number of explanation-
redundant features is more than 7 times larger than the number of features
used in an AXp.

#### Path explanation redundancy in optimal (sparse) DTs.

Table 12 (see Table 12) shows results for DTs learned with recently proposed
algorithms that specifically target the learning of optimal (and so indirectly
_interpretable_) DTs, concretely [80, 112, 161] and also [184]. As can be
observed, the _optimal_ _sparse_ DTs shown in earlier work exhibit a very
significant number of redundant paths (between 55% and 75%). For explanation-
redundant paths, the percentage of explanation-redundant features can reach
60% (as illustrated with 13 for the DT shown in Figure 2).

###  4.3 Path Explanation Redundancy in Theory

This section proves two results. First, we prove that there exist functions
for which paths in smallest-size DTs will exhibit a number of explanation-
redundant literals that grow linearly with the number of features. Second, we
prove that, for a DT to be irredundant, then it must represent a generalized
decision function [81].

#### Optimal decision trees that exhibit redundancy.

To simplify the statement of the main result, the following definitions and
assumptions are used. A dataset is consistent if for any point $\mathbf{x}$ in
feature space, contains an instance $(\mathbf{x},c)$ for at most one class
$c\in{\mathcal{K}}$. A classifier is exact if it correctly classifies any
instance in training data, and that training data is consistent. (A classifier
is perfect if it is exact and is of smallest size [87, 90].) Furthermore, we
assume that a DT learner will not branch on variables that take constant value
on all the instances in training data that are consistent with the already
chosen literals.

######  Proposition 10.

Consider the boolean function,

$f(x_{1},x_{2},\ldots,x_{m-1},x_{m})=\bigvee_{i=1}^{m}x_{i}$

Then, given any DT learning algorithm that learns an exact DT (one that
correctly classifies any point in feature space), the learned DT contains a
path with $m$ literals, for which there exists an AXp containing one single
feature.

Before proving the claim of Proposition 10, it should be observed that a more
general result could be stated, where the literals $(z_{i}=v_{i})$ for a non-
boolean feature $i$ with domain ${\mathcal{D}}_{i}$ would replace the boolean
literal $x_{i}$. However, the basic result remains unchanged, as it reveals in
theory the need for explaining decision trees.

###### Proof.

The AXp’s for function $f$ are easy to identify. For prediction 1, function
$f$ has $m$ AXp’s, namely ${\mathcal{E}}_{1,i}=\\{i\\}$ with $i=1,\ldots,m$.
For prediction 0, function $f$ has one AXp, namely
${\mathcal{E}}_{0,1}=\\{1,2,\ldots,m\\}$. Any other weak AXp will not be
subset-minimal.

Next, we show that, no matter how the DT is constructed, there will always be
at least one path that grows with $m$, and for which the size of the AXp is 1.
Since the exercise is purely conceptual, we can assume that the dataset has
size $2^{m}$, representing the truth table of function $f$. We construct a DT
as follows. At each step, we let some adversary pick any variable, among the
variables that have not yet been picked, and then show that only one option
exists to continue the construction of the DT. Let the first variable be
$x_{i_{1}}$, with $1\leq{i_{1}}\leq{m}$. For $x_{i_{1}}=1$, the prediction is
1, and so the DT must have a terminal node labeled 1. For $x_{i_{1}}=0$, the
resulting function $f_{i_{1}}$ mimics $f$, but without variable $x_{i_{1}}$.
Hence, we let again some adversary pick any variable among those not yet
chosen. (Clearly, there is no reason to pick a variable already picked, since
the function $f_{i_{1}}$ does not depend on $x_{i_{1}}$.) Let the new chosen
variable variable be $x_{i_{2}}$. The analysis for $x_{i_{2}}$ is exactly the
same as for $x_{i_{1}}$, and for $x_{i_{2}}=0$, we get a new function
$f_{i_{2}}$. After analyzing all features, the resulting DT has $m$ paths with
prediction $1$ and 1 path with prediction $0$. Thus,
${\mathcal{P}}=\\{P_{1},\ldots,P_{m}\\}$ represents the paths with prediction
1, and ${\mathcal{Q}}=\\{Q_{1}\\}$ represents the path with prediction 0.
Moreover, $P_{m}$ has length $m$, with literals
$\langle{x_{i_{1}}}=0,x_{i_{2}}=0,\ldots,x_{i_{n-1}}=0,x_{i_{m}}=1\rangle$.
(The resulting DT and path $P_{m}$ are shown in Figure 5.) For the instance
$\\{x_{i_{m}}=1\\}\cup\\{x_{i_{j}}=0,1\leq{j}\leq{m-1}\\}$, path $P_{m}$ is
consistent with the instance and it has $m$ literals. However, the AXp is
$\\{i_{m}\\}$, denoting that $x_{i_{m}}=1$ suffices for the prediction. The
analysis and conclusion is independent of the order of features chosen. ∎

$x_{i_{1}}$1$x_{i_{2}}$1$x_{i_{m-1}}$1$x_{i_{m}}$01$\in\\{1\\}$$\in\\{1\\}$$\in\\{1\\}$$\in\\{0\\}$$\in\\{0\\}$$\in\\{0\\}$$\in\\{0\\}$$\in\\{1\\}$

Figure 5: DT construction for proof of Proposition 10

Although the proof analyzed AXp’s, for the proposed function and resulting DT,
the APXp’s would be the same.

######  Corollary 2.

There are DT classifiers, defined on $m$ features, for which an instance has
an AXp of size 1, and the consistent path has length $m$, and so it can be
made larger by a factor of $m$ than the size of an AXp.

#### Decision trees without path explanation redundancy.

In this section we argue that for a DT not to exhibit redundancy then it must
correspond to an irreducible generalized decision function (GDF) [81]. A GDF
represents a multi-class classifier, with
${\mathcal{K}}=\\{c_{1},\ldots,c_{K}\\}$, where each class
$c_{j}\in{\mathcal{K}}$ is classified by a boolean function $\kappa_{j}$, such
that set of boolean functions $\kappa_{i}$ respects the following statement:

$\forall(\mathbf{x}\in\mathbb{F}).\sum_{j=1,\ldots,K}\kappa_{j}(\mathbf{x})=1$
(19)

A GDF is represented by ${\mathcal{G}}=\\{\kappa_{1},\ldots,\kappa_{K}\\}$. A
DNF GDF is a set of boolean classifier functions $\kappa_{j}$, where each
$\kappa_{j}$ is represented by a disjunctive normal form (DNF) formula. A
minimal DNF GDF is a set of boolean classifier functions where each
$\kappa_{j}$ is represented by an irredundant DNF formula $\varphi_{j}$, i.e.
no term in the DNF $\varphi_{j}$ is redundant, and no literal in any term of
the DNF $\varphi_{j}$ is redundant.

######  Lemma 2.

A minimal DNF GDF ${\mathcal{G}}$ corresponds to a function representation
where each term of each DNF for some $\kappa_{j}$ is a prime implicant of
$\kappa_{j}$.

###### Proof.

Suppose a term $t_{r}$ of the DNF representation of $\kappa_{j}$ that is not a
prime implicant of $\kappa_{j}$. Then, $t_{r}$ can be simplified to
$t^{\prime}_{r}$, such that $t^{\prime}_{r}\equiv{t_{r}}$. But then the DNF
representation of ${\mathcal{G}}$ would not be minimal; a contradiction. ∎

######  Lemma 3.

A DT does not exhibit path explanation redundancy iff the conjunction of the
literals in each path to prediction $c\in{\mathcal{K}}$ represents a prime
implicant for the boolean function $\kappa(\mathbf{x})=c$.

###### Proof.

If the conjunction of the literals in each path is a prime implicant for the
boolean function $\kappa(\mathbf{x})=c$, then no path in the DT exhibits path
explanation redundancy; otherwise some path would not represent a prime
implicant, as assumed by hypothesis.
If the DT exhibits no path path explanation redundancy, then we can represent
the function $\kappa(\mathbf{x})=c$ by a disjunction of the conjunctions of
the literals in the paths predicting $c$. Each disjunct must be irreducible;
otherwise we would be able to also reduce the explanation for some path. ∎

######  Proposition 11.

A DT ${\mathcal{T}}$ does not exhibit path explanation redundancy iff there
exists a minimal DNF GDF $g$ that is equivalent to ${\mathcal{T}}$.

###### Proof.

This result follows from Lemma 2 and Lemma 3. ∎

It should be underscored that minimal DNF GDFs represent a fairly restricted
class of decision sets (DS) [109], namely minimal DSs exhibiting no overlap
[96]. The complexity of computing a minimal DS without overlap is not known,
but it is conjectured to be hard for $\Sigma_{2}^{\textnormal{p}}$ [96].
Furthermore, it is well-known that decision trees represent a far less
expressive language than DSs [158]. Thus, most functions represented by DSs
cannot be represented by DTs that correspond to minimal DNF GDFs. As a result,
Proposition 11 offers further evidence that one should expect decision trees
to be extremely unlikely to exhibit no path explanation redundancy in
practice.

##  5 Computing Path Explanations in Decision Trees

Although the finding of formal explanations is computationally hard for a
number of ML models [93, 20, 100, 89, 13], it has been shown that for DTs, one
AXp can be computed in polynomial time [98, 83]171717Furthermore, recent work
has shown that computing a smallest size AXp is NP-hard [20].. Moreover, and
in the case of CXp’s, recent work has shown that the total number of CXp’s is
polynomial, and that their enumeration runs in polynomial time [83]. This
section refines these earlier results in several ways, proposing simpler and
more efficient algorithms. More importantly, the section specifically
considers algorithms for path explanations, as opposed to instance-based
explanations. Nevertheless, the changes for computing (path
restricted/unrestricted) AXp’s/CXp’s are straightforward.

We start by offering a simple approach supporting the rationale for
polynomial-time explainability of DTs. Afterwards, we propose a simplified
variant of an existing algorithm [98], and then detail a propositional logic
Horn encoding for the problem of computing one AXp/APXp. The proposed encoding
allows us to exploit existing algorithms for reasoning about propositional
Horn formulas.

###  5.1 Abductive Path Explanations by Explicit Path Analysis

Since our goal is to compute a path explanation, we consider a concrete path
$P_{k}$, a partition $({\mathcal{P}},{\mathcal{Q}})$ of the set of paths
${\mathcal{R}}$ in ${\mathcal{T}}$, with $P_{k}\in{\mathcal{P}}$ and with
prediction $c=\varsigma(\tau(P_{k}))$ being the same for all paths in
${\mathcal{P}}$, and with the paths in ${\mathcal{Q}}$ yielding a prediction
other than $c$. Let $F_{k}=\mathrm{\Phi}(P_{k})$, i.e. the set of features $i$
associated with the edges of $P_{k}$. (For computing a path-unrestricted AXp,
we would set $F_{k}={\mathcal{F}}$.) Recall from Section 2.4 (and Table 1)
that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}$
represent, respectively, the set of features that are inconsistent between
either a point or a path and some other path. For computing AXp’s (i.e. given
an instance) we will be interested in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}(\mathbf{v},Q_{l})$
for each $Q_{l}\in{\mathcal{Q}}$. For computing APXp’s (i.e. given a path) we
will be interested in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{k},Q_{l})$
for each $Q_{l}\in{\mathcal{Q}}$. Since the analysis is similar, we will focus
on APXp’s.

For the prediction to be guaranteed not to change, due to $Q_{l}$, at least
one feature in
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{k},Q_{l})$
must not be allowed to change value. Thus, one APXp is a (subset-)minimal
hitting set of the sets
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{k},Q_{l})$
ranging over the paths $Q_{l}$ in ${\mathcal{Q}}$. Furthermore, it is well-
known that one subset-minimal hitting set can be computed in polynomial time
[66]. For example, we can construct a set ${\mathcal{X}}$ containing the
features in
$\cup_{Q_{l}\in{\mathcal{Q}}}\,{\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{k},Q_{l})$,
and then iteratively remove one feature from ${\mathcal{X}}$ while the
resulting set ${\mathcal{X}}$ is still a hitting set of all the
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{k},Q_{l})$.
(For AXp’s, we would use a similar argument, but considering instead the sets
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}(\mathbf{v},Q_{l})$.)

######  Example 16.

Consider again the DT shown in Figure 1. For $P_{2}=\langle 1,3,5,7\rangle$,
we have that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{2},Q_{1})=\\{1\\}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{2},Q_{2})=\\{3\\}$.
Thus, the only minimal hitting set is $\\{1,3\\}$, and so this represents the
only APXp for $P_{2}$. Similarly, we could consider the instance
$(\mathbf{v},c)=((1,1,1),1)$, with
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}((1,1,1),Q_{1})=\\{1\\}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}((1,1,1),Q_{1})=\\{3\\}$,
and so also obtain an AXp $\\{1,3\\}$. Clearly, since $P_{2}$ is consistent
with $\mathbf{v}=(1,1,1,1)$, all the APXp’s of $P_{2}$ should be AXp’s of
$\mathbf{v}$. ∎

######  Example 17.

Consider again the DT shown in Figure 2. For path $P_{1}=\langle
1,2,4,7,10,15\rangle$, we have that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{1},Q_{1})=\\{3\\}$,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{1},Q_{2})=\\{5\\}$,
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{1},Q_{3})=\\{2,5\\}$.
Clearly, the only minimal hitting set is $\\{3,5\\}$ and so this represents
the only APXp for $P_{1}$. Similarly, we could consider the instance
$(\mathbf{v},c)=((0,0,1,0,1),1)$ and so we would also obtain the AXp
$\\{3,5\\}$. ∎

######  Example 18.

With respect to the DT shown in Figure 3, and for path $P_{3}=\langle
1,2,6,11,12\rangle$, we have that
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{3},Q_{1})=\\{3\\}$,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{3},Q_{2})=\\{2\\}$,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{3},Q_{3})=\\{1,3\\}$,
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(P_{3},Q_{4})=\\{1\\}$.
Clearly, the only minimal hitting set is $\\{1,2,3\\}$ and so this represents
the only APXp for path $P_{3}$. ∎

The previous examples of explanations can also be viewed as _path-restricted_
AXp’s. The following example reveals the differences to path-unrestricted
AXp’s [98].

######  Example 19.

Let us consider the example of Figure 1, and path $Q_{1}=\langle 1,2\rangle$.
In this case, we want to keep the paths $P_{1}$ and $P_{2}$ inconsistent.
Hence,
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(Q_{1},P_{1})=\\{1\\}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{P}(Q_{1},P_{3})=\\{1\\}$,
and so the only APXp is $\\{1\\}$. Let us now consider the $((0,1,0),0)$,
which is consistent with path $Q_{1}$. In this case we get
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}((0,1,0),P_{1})=\\{1,2\\}$
and
${\mathchoice{\raisebox{0.0pt}{$\displaystyle\chi$}}{\raisebox{0.0pt}{$\textstyle\chi$}}{\raisebox{0.0pt}{$\scriptstyle\chi$}}{\raisebox{0.0pt}{$\scriptscriptstyle\chi$}}}_{I}((0,1,0),P_{2})=\\{1,3\\}$,
and so the AXp’s for the instance-based explanation problem are $\\{1\\}$ and
$\\{2,3\\}$. Observe that, given the instance, one can understand the AXp
$\\{2,3\\}$. However, in terms of explaining the sufficient conditions for the
prediction to remain the same, given the values specified by the path, then it
is clear that $\\{1\\}$ represents the only explanation of interest. ∎

An apparent drawback of computing explanations with the algorithm outlined in
this section is that all DT paths must be explicitly listed, and these require
worst-case quadratic space given the number of nodes in the DT. The next
sections investigate alternative approaches, which perform better in practice.

###  5.2 Abductive Path Explanations by Tree Traversal

One approach to avoid the issue with explicit path representation is to
iteratively traverse the DT as features are removed from the AXp, and checking
whether the paths to predictions other than $c$ remain inconsistent. This
approach was first described in [98]. Here, we describe a simpler variant.

Algorithm 1 summarizes the main steps of the proposed approach for computing
an APXp for a concrete path $P_{k}$. (For computing a path-restricted AXp
given an instance, we would just identify and use the same algorithm.)

Function FindAPXp(_${\mathcal{T}},{\mathcal{F}},P_{k}$_)

1 ${\mathcal{U}}\leftarrow{\mathcal{F}}\setminus\mathrm{\Phi}(P_{k})$;

// Features $\not\in$ path also $\not\in$ APXp

2 foreach  _$i\in\mathrm{\Phi}(P_{k})$_ do

3 ${\mathcal{U}}\leftarrow{\mathcal{U}}\cup\\{i\\}$;

// Tentatively drop $i$ from APXp

4 if  _$\textnormal{{{\sc
ExistsConsistentQPath}}}(P_{k},{\mathcal{U}},\textnormal{{root}}({\mathcal{T}}))$_
then

5 ${\mathcal{U}}\leftarrow{\mathcal{U}}\setminus\\{i\\}$;

// Feature $i$ must be included in APXp

6 return _${\mathcal{F}}\setminus{\mathcal{U}}$_ ;

// Return APXp

Algorithm 1 Computing one path explanation (or path-restricted AXp)

As shown, for APXp’s (and also for path-restricted AXp’s given some instance),