article title title, book

# Paths in tournaments, a simple proof of Rosenfeld’s Conjecture

Charbel Bou Hanna

Lebanese University, KALMA Laboratory, Baalbek
University of Angers, LAREMA Laboratory, Angers

###### Abstract

Rosenfeld Conjectured [7] in 1972 that there exists an integer $K\geq 8$ such
that any tournament of order $n\geq K$ contains any Hamiltonian oriented path.
In 2000, Havet and Thomassé [5] proved this conjecture for any tournament with
exactly 3 exceptions. We give a simplified proof of this fact.

##  1 Introduction

A tournament $T$ is an orientation of a complete graph. The set of vertices of
$T$ is denoted by $V(T)$ and the set of arcs by $E(T)$. $v(T)$ will denote the
order of $T$, $|V(T)|$. Sometimes, we write $|T|$ instead of $v(T)$. $T$ is
said to be an $n$-tournament if $v(T)=n$.
The out-neighbour (resp. in-neighbour) of a vertex $v$ in $T$ is denoted by
$N^{+}_{T}(v)$ (resp. $N^{-}_{T}(v)$) and its out-degree (resp. in-degree) is
denoted by $d^{+}_{T}(v)$ (resp. $d^{-}_{T}(v)$). We denote by $\delta^{+}(T)$
(resp. $\delta^{-}(T)$) the minimal out-degree (resp. in-degree) and by
$\Delta^{+}(T)$ (resp. $\Delta^{-}(T)$) the maximal out-degree (resp. in-
degree). Note that $\delta^{-}(T)\leq\Delta^{+}(T)$ (resp.
$\delta^{+}(T)\leq\Delta^{-}(T)$). A tournament $T$ is said to be regular if
$d^{+}(v)=d^{-}(v)\,\forall\,v\in V(T)$. A cyclic triangle is a circuit of
length 3. We denote by $T^{+}_{4}$ a tournament composed of a circuit triangle
together with a source. A Paley tournament on 7 vertices is a tournament $T$
such that $V(T)=\\{v_{i},1\leq i\leq 7\\}$ and $(v_{i},v_{j})\in E(T)$ if and
only if $j-i\equiv 1,\,2$ or $4(mod\,7)$. We write $T^{\prime}\subseteq T$
whenever $T^{\prime}$ is a subtournament of $T$. Let $S\subseteq V(T)$, we
denote by $T[S]$ the subtournament of $T$ induced by $S$. If
$T^{\prime}\subseteq T$ and $S\subseteq V(T)$, we write
$T^{\prime}+S=T[V(T^{\prime})\cup S]$ and $T^{\prime}-S=T[V(T^{\prime})-S]$.
Let $v\in V(T)$, $d^{+}_{S}(v)=|N^{+}_{T}(v)\cap S|$ and
$d^{-}_{S}(v)=|N^{-}_{T}(v)\cap S|$. A subset $\\{x_{1},...,x_{r}\\}$ in $T$
will be denoted by $[x_{1},x_{r}]$.
Let $P=x_{1}...x_{s}$ be an oriented path, set $\widetilde{P}=x_{s}...x_{1}$.
$P$ is called an $s$-path, $x_{1}$ and $x_{s}$ are its extremities, $x_{1}$ is
the origin and $x_{s}$ is the end. The length of $P,\,l(P)$, is the number of
its arcs. $P$ is said to be directed if all of its arcs are oriented in the
same direction. A block of $P$ is a maximal (for $\subseteq$) directed subpath
of $P$. The path $P$ is said to be of type $P(b_{1},...,b_{m})$ and we write
$P=P(b_{1},...,b_{m})$, if $P$ is composed of $m$ successive blocks
$B_{1},...,B_{m}$, such that $l(B_{i})=b_{i}$. Moreover, we write
$P=P^{+}(b_{1},...,b_{m})$, if $(x_{1},x_{2})\in E(P)$. Else, we write
$P=P^{-}(b_{1},...,b_{m})$. $P$ is said to be antidirected if each block of
$P$ is of length 1.
Note that if $P=x_{1}...x_{s}=P^{+}(b_{1},...,b_{m})$ (resp.
$P^{-}(b_{1},...,b_{m})$) and
$P^{\prime}=x^{\prime}_{1}...x^{\prime}_{s}=P^{+}(b_{1},...,b_{m})$ (resp.
$P^{-}(b_{1},...,b_{m})$), then $P$ and $P^{\prime}$ are isomorphic. We write
$P\equiv P^{\prime}$. Furthermore, if we write $x_{1}...x_{s}\equiv
x^{\prime}_{1}...x^{\prime}_{s}$, then the mapping:

$f:$ | $V(P)$ | $\rightarrow$ | $V(P^{\prime})$ | is an isomorphism.
---|---|---|---|---
| $x_{i}$ | $\rightarrow$ | $f(x_{i})=x^{\prime}_{i}$ |

A path $P$, in a tournament $T$, is said to be Hamiltonian if $V(P)=V(T)$. Let
$P=x_{1}...x_{s}$ and $Q=y_{1}...y_{r}$ be 2 disjoint paths in $T$, $PQ$
denotes the path $x_{1}...x_{s}\,y_{1}...y_{r}$. In a similar way, we may
define the path $P_{1}P_{2}...P_{t}$ from $t$ pairewisely disjoint paths
$P_{1},...,P_{t}$ of $T$. Let $P=v_{1}...v_{i-1}\,v_{i}\,v_{i+1}...v_{n}$ be
an oriented path in a tournament $T$, then $P-v_{i}$ is the path
$v_{1}..v_{i-1}\,v_{i+1}...v_{n}$ in $T$.
A strong tournament is such that any two of its vertices can be joined by a
directed path. It is known that any tournament $T$ is a transitive union of
strong subtournaments (called strong components) $I_{1},\,I_{2},...,I_{t}$
that is $(v_{i},v_{j})\in E(T)\,\forall\,i<j$, $v_{i}\in I_{i}$ and $v_{j}\in
I_{j}$. We write $T=I_{1}...I_{t}$. A strong tournament is characterized by
the following property due to Camion [2].

######  Theorem 1.

$T$ is strong if and only if $T$ contains a Hamiltonian circuit.

As a consequence of the above theorem, if $T=I_{1}...I_{t}$, then $T$ contains
a directed path ending at $x$ with $V(P)=V(I_{1})\cup...\cup V(I_{i})$ for
every $x\in T_{i}$.
The complement of a digraph $D$, denoted by $\overline{D}$, is the digraph
obtained from $D$ by reversing all its arcs.

In 1971, Grünbaum [4] proved the following theorem:

######  Theorem 2.

Any tournament contains any Hamiltonian antidirected path with exactly 3
exceptions: a cyclic triangle ($T_{3}$), a regular tournament on 5 vertices
($T_{5}$) and a Paley tournament on 7 vertices ($T_{7}$).

Set $\mathcal{T}_{3,5,7}=\\{T_{3},T_{5},T_{7}\\}$. Note that if
$T\in\mathcal{T}_{3,5,7}$ contains a copy of a path $P$, then any vertex in
$T$ is an origin of a copy of $P$. Rosenfeld [7], in 1972, inspired by the
work of Grünbaum, conjectured that there exists $K\geq 8$ such that any
tournament of order $n\geq K$ contains any Hamiltonian oriented path. The case
of directed path being Rédei’s theorem [6]. Alspach, Rosenfeld [1] and
Straight [9] proved Rosenfeld’s conjecture on paths of 2 blocks. In 1973,
Forcade [3] proved Rosenfeld’s conjecture for any tournament of order $2^{n}$.
Thomason [10] was the first one to give a general answer. He proved, in 1986,
that there exists $n_{0}<2^{128}$ such that for all $n\geq n_{0}$ any
tournament of order $n$ contains any Hamiltonian oriented path. Havet and
Thomassé settled the problem by proving that the three exceptions of Grünbaum
are the only tournaments not satisfying Rosenfled’s conjecture. Havet and
Thomassé’s proof consists of giving a refinement of a key idea introduced by
Thomason saying that any set of $b_{1}+1$ vertices in an $n$-tournament
contains an origin of any $(n-1)$-path whose first block is of length $b_{1}$.
They proved that if $s^{+}(x,y)\geq b_{1}+1$, then $x$ or $y$ is an origin of
a copy of such path where $s^{+}(x,y)=|\\{z\in T$ such that $z$ can be reached
from $x$ or $y$ by a directed path$\\}|$. This new performance allowed them to
remark that proving the existence of an $(n-1)$-oriented path in any
$n$-tournament $T$ is equivalent to the existence of any Hamiltonian path $P$
in this tournament unless $(T,P)$ is one of the 69 exceptions that were
verified one by one. In this paper, we give a simple proof of the result
without treating all these exceptions.

##  2 The main result

In our proof, we are going to use the following theorem due to El-sahili and
Ghazo-Hanna [8].

######  Theorem 3.

A path lies in a tournament $T$ if and only if it lies in $\overline{T}$.

The following Lemmas will be useful in the sequel.

######  Lemma 1.

Let $T$ be a tournament then $|\\{v\in T\,/\,T-v\in\mathcal{T}_{3,5,7}\\}|\leq
2$.

###### Proof.

Suppose that $T$ contains 3 distinct vertices, $v_{1}$, $v_{2}$, $v_{3}$ such
that $T-v_{i}\in\mathcal{T}_{3,5,7}$, $1\leq i\leq 3$. We may suppose without
loss of generality that $(v_{1},v_{2})$, $(v_{2},v_{3})\in E(T)$. Since
$T-v_{1}\in\mathcal{T}_{3,5,7}$ and $T-v_{3}\in\mathcal{T}_{3,5,7}$, then
$N^{-}_{T-v_{3}}(v_{1})=N^{-}_{T-v_{1}}(v_{3})$ and
$N^{+}_{T-v_{1}}(v_{3})=N^{+}_{T-v_{3}}(v_{1})$, but $v_{2}\in
N^{+}_{T-v_{3}}(v_{1})$ and $v_{2}\notin N^{+}_{T-v_{1}}(v_{3})$, which is a
contradiction. ∎

We may deduce from this Lemma more precise conclusions. Indeed, if
$T\in\mathcal{T}_{3,5,7}$, then $\forall\,x\in T$, $\exists\,y\in N^{+}(x)$
such that $T-\\{x,y\\}\notin\mathcal{T}_{3,5,7}$.

######  Lemma 2.

(Simple Lemma) Let $n\geq 4$. Suppose that any $s$-tournament $(s<n)$ contains
any $s$-path unless if the tournament is in $\mathcal{T}_{3,5,7}$ and the path
is antidirected. Let $T$ be an $n$-tournament with a vertex $v$ such that
$d^{-}(v)=0$ and let $P=x_{1}...x_{n}$ be a non directed path. Unless
$P=P^{+}(1,2)$ and $T-v$ is a cyclic triangle, we have:

  1. 1.

$T$ contains a copy of $P$ with origin $x\neq v$.

  2. 2.

Any of the vertices of $T-v$ is an origin of a copy of $P$ if
$T-v\in\mathcal{T}_{3,5,7}$.

###### Proof.

  1. 1.

Let $j\in[2,n]$ be the minimal integer such that $d^{-}_{P}(x_{j})=0$. If
$j=n$, then $T-v$ contains a path $P^{\prime}$ such that $P^{\prime}v\equiv P$
since otherwise $P-x_{j}$ is antidirected and so $P=P^{+}(1,2)$ and
$T=T^{+}_{4}$ which is a contradiction. Otherwise, $1<j<n$. In this case,
$P-x_{j}+(x_{j-1},x_{j+1})$ or $P-x_{j}+(x_{j+1},x_{j-1})$ is not
antidirected. Suppose that $P^{\prime}=P-x_{j}+(x_{j-1},x_{j+1})$ is not
antidirected, then $T-v$ contains a path
$v_{1}\,v_{2}...v_{j-1}\,v_{j+1}...v_{n}\equiv P^{\prime}$ and so
$v_{1}...v_{j-1}\,v\,v_{j+1}...v_{n}\equiv P$ and $v_{1}\neq v$.

  2. 2.

If $T-v\in\mathcal{T}_{3,5,7}$, then we may suppose that a copy of
$P^{\prime}$ may be found in $T-v$ starting at any one of the vertices of
$T-v$.

∎

By analogy, the above lemma is valid if $d^{+}(v)=0$ with the only exception
where $P=P^{-}(1,2)$ and $T-v$ is a cyclic triangle. Using the same reasoning,
we may deduce that if $P$ contains a vertex $x_{j}$ with $1<j<n$ such that
$d^{-}_{P}(x_{j})=0$, then $T$ contains a copy of $P$ such that $v$ is not an
extremity of $P$.
We are going now to present the proof of the main result.

######  Theorem 4.

Any $n$-tournament contains any $n$-path unless the three exceptions of
Grünbaum.

###### Proof.

Let $T$ be an $n$-tournament and let $P=x_{1}..x_{n}$ be an $n$-path. If
$n\leq 4$, then any $n$-path is either directed, antidirected or of two
blocks. By theorem 3, the problem will be solved if we prove the existence of
P̂ in T̂, where P̂$\in\\{P,\overline{P}\\}$ and T̂$\in\\{T,\overline{T}\\}$.
We may suppose, without loss of generality, that
$\Delta^{+}(T)\geq\Delta^{+}(\overline{T})$. We argue by induction on $|T|\geq
5$. The case $\delta^{-}(T)=0$ can be deduced from simple lemma and Rédei’s
theorem. Set $\delta^{-}(T)=i\geq 1$ and suppose, without loss of generality,
that $(x_{i},x_{i+1})\in E(P)$, since otherwise, we use $\overline{P}$. Then
$x_{i}...x_{n}$ is of type $P^{+}(b_{1},b_{2},...,b_{r})$ for some
$b_{1},...,b_{r}\geq 1$. Let $v\in T$ such that $d^{-}(v)=\delta^{-}(T)$,
$T_{1}=T[N^{-}(v)]$ and $T_{2}=T[N^{+}(v)]$. We will treat the two cases
according to the existence of a copy of $x_{1}...x_{i}$ in $T_{1}$.

######  Case 1.

$T_{1}\not\supseteq v_{1}...v_{i}\equiv x_{1}...x_{i}$.
In this case, $x_{1}...x_{i}$ is antidirected and
$T_{1}\in\mathcal{T}_{3,5,7}$. If $b_{1}\geq 3$, let $a\in T_{2}$ such that
$T_{2}-a\supseteq v_{i+3}...v_{n}\equiv x_{i+3}...x_{n}$. Then
$T_{1}+a\supseteq v_{1}...v_{i+1}\equiv x_{1}...x_{i+1}$ such that
$v_{i+1}\neq a$. So $v_{1}...v_{i+1}\,v\,v_{i+3}...v_{n}\equiv P$.
In the case $b_{1}\leq 2$, for $\mathbf{(x_{i},x_{i-1})\in E(P)}$, suppose
that $b_{1}=1$, we discuss if $T_{2}\supseteq v_{i+2}...v_{n}\equiv
x_{i+2}...x_{n}$ or not. In the first case, suppose that there exists $x\in
T_{1}$ such that $(v_{i+2},x)\in E(T)$. By simple lemma, $T_{1}+v\supseteq
v_{1}...v_{i+1}\equiv x_{1}...x_{i+1}$ with $v_{i+1}=x$, so
$v_{1}...v_{n}\equiv P$. If $(x,v_{i+2})\in E(T)\,\forall\,x\in T_{1}$, let
$t$ be the minimal integer $(t\geq i+2)$ such that $d^{-}_{P}(x_{t})=0$. If
there exists $y\in T_{1}$ such that $T_{2}+y\supseteq w_{i+1}...w_{n}\equiv
x_{i+1}...x_{n}$ with $w_{i+1}=v_{i+2}$, then $(T_{1}-y)+v\supseteq
v_{1}...v_{i}\equiv x_{1}...x_{i}$ and so
$v_{1}...v_{i}\,w_{i+1}...w_{n}\equiv P$. Otherwise,
$N^{-}(x)\cap[v_{i+2},v_{t}]=\phi$ and $(v_{t+1},x)\in E(T)\,\forall\,x\in
T_{1}$. In this case, let $y\in T_{1}$.
$Q=(v_{t+1}\,y\,v_{t}\,v_{t-1}...v_{i+2}-v_{t})-v_{i+2}$ is a directed path.
If $t\geq i+3$, then $l(Q)=b_{2}-1$.
$T_{2}[v_{t+2},v_{n}]+\\{v_{t},v\\}\supseteq w_{t}...w_{n}\equiv
x_{t}...x_{n}$ with $w_{t}=v$ or, by simple lemma, $w_{t}=v_{t}$. In the other
hand, by simple lemma, $T_{1}+v_{i+2}\supseteq v_{1}...v_{i}\,v_{i+1}\equiv
x_{1}...x_{i+1}$ with $v_{i+1}=y$ and $v_{i}\neq v_{i+2}$, so
$v_{1}...v_{i}\,\widetilde{Q}\,w_{t}...w_{n}\equiv P$. If $t=i+2$, let $x\in
T_{1},T_{1}-x\supseteq v_{2}...v_{i}\equiv x_{2}...x_{i}$. If
$(v_{t+1},v_{t+2})\in
E(T),v_{t+1}\,v_{2}...v_{i}\,v_{t}\,x\,v\,v_{t+2}...v_{n}\equiv P$. If
$(v_{t+2},v_{t+1})\in E(T)$ and there exists $y\in T_{1}$ such that
$(v_{t+2},y)\in E(T)$, consider $(a,b)\in E(T_{1}-y)$,
$(T_{1}-\\{a,b,y\\})+v\supseteq v_{1}...v_{i-2}\equiv x_{1}...x_{i-2}$ and so
$v_{1}...v_{i-2}\,v_{t}\,a\,b\,v_{t+1}\,y\,v_{t+2}..v_{n}\equiv P$. Else, let
$z\in T_{1}$. $(T_{1}-z)+v_{t+1}\supseteq v_{1}...v_{i}\equiv x_{1}...x_{i}$
with $v_{i}\neq v_{t+1}$ and $(T[v_{t+2},v_{n}])+v\supseteq
w_{t+1}...w_{n}\equiv x_{t+1}...x_{n}$ with $w_{t+1}=v_{t+2}$ then
$v_{1}...v_{i}\,v_{t}\,z\,w_{t+1}...w_{n}\equiv P$.
In the other case, $T_{2}\not\supseteq v_{i+2}...v_{n}\equiv x_{i+2}...x_{n}$,
so $T_{2}\in\mathcal{T}_{3,5,7}$ and $x_{i+2}...x_{n}$ is antidirected. If
$b_{2}=1$, then $P$ is antidirected treated in Theorem 2. Otherwise,
$b_{2}=2$. Let $a\in T_{2}$, then $T_{1}+a\supseteq v_{1}...v_{i+1}\equiv
x_{1}...x_{i+1}$ such that $v_{i+1}\neq a$. Since $v_{i+1}\in
T_{1}\in\mathcal{T}_{3,5,7}$, then $d^{-}_{T_{2}}(v_{i+1})\geq 2$, there
exists $b\in T_{2}-a$ such that $(b,v_{i+1})\in E(T)$. If
$T_{2}-\\{a,b\\}\supseteq Q\equiv x_{i+4}...x_{n}$, then
$v_{1}...v_{i+1}\,b\,v\,Q\equiv P$. Otherwise, there exists $c\in
T_{2}-\\{a,b\\}$ such that $(c,b)\in E(T)$, then, by simple lemma,
$(T_{2}-\\{a,b\\})+v\supseteq Q\equiv x_{i+3}...x_{n}$ starting by c, then
$v_{1}...v_{i+1}\,b\,Q\equiv P$.
For $\mathbf{b_{1}=2}$, here also we study if $T_{2}\supseteq
v_{i+2}...v_{n}\equiv x_{i+2}...x_{n}$ or not. In the first case, let $x\in
N^{-}(v_{i+2})\cap T_{1}$, if any, by simple lemma, $T_{1}+v\supseteq
v_{1}...v_{i+1}\equiv x_{1}...x_{i+1}$ with $v_{i+1}=x$ and so
$v_{1}...v_{n}\equiv x_{1}...x_{n}$. If $N^{-}(v_{i+2})\cap T_{1}=\phi$, $v$
can be inserted inside $v_{i+3}...v_{n}$ to obtain a path $Q\equiv
x_{i+2}...x_{n}$ starting at $v_{i+3}$ in $(T_{2}-v_{i+2})+v$. Similarly, by
simple lemma, if $N^{-}(v_{i+3})\cap T_{1}=\phi$, we may find a copy of $P$ in
$T$, so, we may suppose in the sequel that
$d^{-}_{T_{1}}(v_{i+2})=d^{-}_{T_{1}}(v_{i+3})=0$. As above, let $t\geq i+3$
be the minimal integer such that $d^{-}_{P}(x_{t})=0$. If $t=i+3$, since
$T_{1}\in\mathcal{T}_{3,5,7}$, then $d^{+}_{T_{2}}(x)\geq 1\,\forall\,x\in
T_{1}$, since otherwise, $\Delta^{+}(\overline{T})>\Delta^{+}(T)$. If there
exists $x\in T_{1}$ and $a\in T_{2}$ such that $(x,a)\in E(T)$ and
$d^{-}_{T_{2}-v_{i+2}}(a)\geq 1$, let $b\in N^{-}_{T_{2}-v_{i+2}}(a)$. By
simple lemma, $T_{1}+v_{i+2}\supseteq v_{1}...v_{i+1}\equiv x_{1}...x_{i+1}$
with $v_{i+1}=x$. $(T_{2}-\\{a,v_{i+2}\\})+v\supseteq v_{i+3}...v_{n}\equiv
x_{i+3}...x_{n}$ with $v_{i+3}=v$ or, by simple lemma, $v_{i+3}=b$, so
$v_{1}...v_{i+1}\,a\,v_{i+3}...v_{n}\equiv P$. Otherwise, if $(v_{i+2},a)\in
E(T)$, then the problem is solved by considering $v_{1}...v_{i+1}\equiv
x_{1}...x_{i+1}$ in $T_{1}+v_{i+3}$. Otherwise, there exists $a\in T_{2}$ such
that $\forall\,x\in T_{1}$, $\forall\,y\in T_{2}-a$, we have $(x,a)$, $(y,x)$,
$(a,y)\in E(T)$. Let $y\in T_{2}-a$ such that $T_{2}-\\{a,y\\}\notin
T_{3,5,7}$. $T_{1}+y\supseteq v_{1}...v_{i+1}\equiv x_{1}...x_{i+1}$ with
$v_{i+1}\neq y$ and $T_{2}-\\{a,y\\}\supseteq v_{i+4}...v_{n}\equiv
x_{i+4}...x_{n}$ then $v_{1}...v_{i+1}\,a\,v\,v_{i+4}...v_{n}\equiv P$. If
$t>i+3$, let $x\in T_{1}$, $T_{1}-x\supseteq v_{2}...v_{i}\equiv
x_{2}...x_{i}$. If $(T_{2}-v_{i+2})+\\{v,x,v_{i}\\}\supseteq
w_{i}...w_{n}\equiv x_{i}...x_{n}$ with $w_{i}\in\\{v_{i+3},v_{i}\\}$, then
$v_{i+2}\,v_{2}...v_{i-1}\,w_{i}...w_{n}\equiv P$. Otherwise, $\forall\,x\in
T_{1}$ $N^{-}(x)\cap[v_{i+4},v_{t}]=\phi$ and $(v_{t+1},x)\in E(T)$. Let
$x,\,y\in T_{1}$ such that $(x,y)\in E(T)$ and $T_{1}-\\{x,y\\}\supseteq
v_{2}...v_{i-1}\equiv x_{2}...x_{i-1}$. As above,
$(T_{2}-\\{v_{i+2},v_{i+3}\\})+\\{y,v\\}\supseteq w_{i+2}...w_{n}\equiv
x_{i+2}...x_{n}$ with $w_{i+2}\in\\{y,v_{i+4}\\}$, so
$v_{i+2}\,v_{2}...v_{i-1}\,v_{i+3}\,x\,w_{i+2}...w_{n}\equiv P$. If
$T_{2}\not\supseteq v_{i+2}...v_{n}\equiv x_{i+2}...x_{n}$ then,
$x_{i+2}...x_{n}$ is antidirected and $T_{2}\in\mathcal{T}_{3,5,7}$. If
$|T_{2}|>|T_{1}|$, the problem is solved by considering
$\overline{\widetilde{P}}\,(b_{1}=1)$. Otherwise, $|T_{1}|=|T_{2}|$. Let $x\in
T_{1}$. $T_{2}+x\supseteq v_{i+1}...v_{n}\equiv x_{i+1}...x_{n}$ such that
$v_{i+1}\neq x$. If there exists $y\in T_{1}-x$ such that $(y,v_{i+1})\in
E(T)$, then $(T_{1}+v)-x\supseteq w_{1}..w_{i}\equiv x_{1}...x_{i}$ with
$w_{i}=y$ and so $w_{1}...w_{i}\,v_{i+1}..v_{n}\equiv P$, unless
$T_{1}-\\{x,y\\}\in\mathcal{T}_{3,5,7}$, then there exists $z\in
T_{1}-\\{x,y\\}$ such that $(y,z)\in E(T)$. By simple lemma,
$(T_{1}-\\{x,y\\})+v\supseteq w_{1}...w_{i-1}$ with $w_{i-1}=z$, and so
$w_{1}...w_{i-1}\,y\,v_{i+1}...v_{n}\equiv P$. Otherwise $T_{1}$ and $T_{2}$
are cyclic triangles. The problem is solved unless if for $u\in
T,\,T[N^{+}(u)]$, $T[N^{-}(u)]\in T_{3}$. So, if $u\in T_{1}$, then
$d^{+}_{T_{2}}(u)=1$. Else, $d^{+}_{T_{1}}(u)=2$. Set $V(T_{1})=\\{x,y,z\\}$,
then $T_{2}+x\supseteq v_{4}...v_{7}\equiv x_{4}...x_{7}$. Since
$x_{4}...x_{7}$ is antidirected, then $v_{5}=x$. Suppose, without loss of
generality that, $(y,v_{4})\in E(T)$, then $z\,v\,y\,v_{4}...v_{7}\equiv P$.
If $\mathbf{(x_{i-1},x_{i})\in E(P)}$, let $x\in T_{1}$. $T_{1}-x\supseteq
Q_{1}\equiv x_{1}...x_{i-1}$. If $T_{2}+x\supseteq v_{i+1}...v_{n}\equiv
x_{i+1}...x_{n}$ and $v_{i+1}\neq x$, $Q_{1}\,v\,v_{i+1}...v_{n}\equiv P$. If
$v_{i+1}=x$, then, by simple lemma, $T_{1}+v\supseteq v_{1}...v_{i+1}\equiv
x_{1}...x_{i+1}$ such that $v_{i+1}=x$. Then $v_{1}...v_{n}\equiv P$. If
$T_{2}+x$ contains no copy of $x_{i+1}...x_{n}$, then this path is
antdirected, so we consider $\widetilde{P}=y_{1}...y_{n}$ to remark that $P$
or $\overline{P}$ contains the arcs $(y_{i},y_{i-1})$ and $(y_{i},y_{i+1})$,
we recover a previous case.

######  Case 2.

$T_{1}\supseteq v_{1}...v_{i}\equiv x_{1}...x_{i}$.
If $b_{1}\geq 2$, then either $T_{2}\supseteq v_{i+2}...v_{n}\equiv
x_{i+2}...x_{n}$ or not. In the first case,
$v_{1}...v_{i}\,v\,v_{i+2}...v_{n}\equiv P$ and in the last case,
$T_{2}\in\mathcal{T}_{3,5,7}$ and $x_{i+2}...x_{n}$ is antidirected. If
$\exists\,x\in T_{2}$ such that $(v_{i},x)\in E(T)$, then, by simple lemma,
$T_{2}+v\supseteq v_{i+1}...v_{n}\equiv x_{i+1}...x_{n}$ with $v_{i+1}=x$.
Thus $v_{1}...v_{i}\,v_{i+1}...v_{n}\equiv P$. Otherwise, $(x,v_{i})\in
E(T)\,\forall\,x\in T_{2}$, we have $(v_{i},v_{j})\in E(T)$ whenever $j<i$,
since otherwise $\Delta^{+}(\overline{T})\geq
d^{+}_{\overline{T}}(v_{i})=d^{-}_{T}(v_{i})>|T_{2}|=d^{+}(v)=\Delta^{+}(T)$,
a contradiction. By simple lemma, $T_{2}+v_{i}$ contains a path
$v_{i+1}...v_{n}\equiv x_{i+1}...x_{n}$ with $v_{i+1}\in T_{2}$. If $i=1$,
then $v\,v_{i+1}...v_{n}\equiv P$. Otherwise, let $j<i$ be the maximal integer
such that $d^{+}_{P}(x_{j})=0$, then
$v_{1}...v_{j-1}\,v\,v_{j}...v_{i-1}\equiv x_{1}...x_{i}$. Since
$(v_{i},v_{i-1})\in E(T)$, then $\exists\,x\in T_{2}$ such that
$(v_{i-1},x)\in E(T)$. By simple lemma, we suppose that $v_{i+1}=x$ and so
$v_{1}...v_{j-1}\,v\,v_{j}...v_{i-1}$ $v_{i+1}...v_{n}\equiv P$.
Now, we will study the case $b_{1}=1$. Suppose that $N^{+}(v_{i})\cap
T_{2}\neq\phi$. Let $I_{1},\,I_{2},...I_{t}$ be the strong connected
components of $T_{2}$ such that $T_{2}=I_{1}...I_{t}$ and let
$l=max\\{j,N^{+}(v_{i})\cap I_{j}\neq\phi\\}$, $I=I_{1}\,I_{2}...I_{l}$ and
$s=|I|$. We discuss according to the value of $s$:
For the case $\mathbf{s>b_{2}}$, let $Q=u_{1}...u_{b_{2}+1}$ be a directed
path in $I$ such that $u_{b_{2}+1}\in N^{+}(v_{i})$ and let $j=i+b_{2}+2$. So
either $T_{2}-[u_{2},u_{b_{2}+1}]$ contains a path $v_{j}...v_{n}\equiv
x_{j}...x_{n}$, and in this case
$v_{1}...v_{i}\,u_{b_{2}+1}...u_{2}\,v\,v_{j}...v_{n}\equiv P$, or
$T_{2}-[u_{2},u_{b_{2}+1}]\in\mathcal{T}_{3,5,7}$ and $x_{j}...x_{n}$ is
antidirected. By simple lemma, $(T_{2}-[u_{2},u_{b_{2}+1}])+v$ contains a path
$v_{j-1}...v_{n}\equiv x_{j-1}...x_{n}$ with $v_{j-1}=u_{1}$. In this case,
$v_{1}...v_{i}\,u_{b_{2}+1}...$ $u_{2}\,v_{j-1}...v_{n}\equiv P$.
Now we will study the case $\mathbf{s=b_{2}}$. Let $Q=u_{1}...u_{b_{2}}$ be a
directed path in $I$ such that $u_{b_{2}}\in N^{+}(v_{i})$ and let
$j=i+b_{2}+2$. If $T_{2}-I\notin\mathcal{T}_{3,5,7}$ or $x_{j}...x_{n}$ is not
antidirected, then $v_{1}...v_{i}\,u_{b_{2}}...u_{1}\,v\,v_{j}...v_{n}\equiv
P$ where $T_{2}-I\supseteq v_{j}...v_{n}\equiv x_{j}...x_{n}$. Otherwise, we
will continue the proof depending on the orientation of $x_{i}\,x_{i-1}$ and
on the value of $i$. If $(x_{i-1},x_{i})\in E(P)$ or $i=1$, let $a\in
T_{2}-I$. By simple lemma, $(T_{2}-(I\cup a))+v_{i}$ contains a path
$v_{j}...v_{n}\equiv x_{j}...x_{n}$ with $v_{j}\neq v_{i}$, then
$v_{1}...v_{i-1}\,v\,a\,u_{b_{2}}...u_{1}\,v_{j}...v_{n}\equiv P$. Otherwise,
$(x_{i},x_{i-1})\in E(P)$ and $i\geq 2$. If
$N^{+}(v_{i-1})\cap(T_{2}-I)\neq\phi$, let $a\in N^{+}(v_{i-1})\cap(T_{2}-I)$.
As above $\exists\,r<i$ such that $v_{1}...v_{r-1}\,v\,v_{r}...v_{i-1}\equiv
x_{1}...x_{i}$ and by simple lemma $(T_{2}-(I\cup a))+v_{i}\supseteq
v_{j}...v_{n}\equiv x_{j}...x_{n}$ with $v_{j}\neq v_{i}$, so
$v_{1}...v_{r-1}\,v\,v_{r}...v_{i-1}\,a\,u_{b_{2}}...$
$u_{1}\,v_{j}...v_{n}\equiv P$. Otherwise, let $abc$ be a cyclic triangle in
$T_{2}-I$. Then, if $b_{2}\geq 2$,
$v_{1}...v_{i-1}\,a\,v_{i}\,b\,u_{b_{2}}...u_{3}\,v\,v_{j}...v_{n}\equiv P$
with $v_{j}...v_{n}\subseteq(T_{2}-(I\cup\\{a,b\\}))+\\{u_{1},u_{2}\\}$ such
that $v_{j}...v_{n}\equiv x_{j}...x_{n}$. If $b_{2}=b_{3}=1$,
$v_{1}...v_{i-1}\,a\,v_{i}\,b\,c\,v\,v_{j+2}...v_{n}\equiv P$ where
$v_{j+2}...v_{n}\subseteq T_{2}-\\{a,b,c\\}$. If $b_{2}=1$, $b_{3}=2$ and
$T_{2}-I\in\\{T_{5},T_{7}\\}$, choose $d\in T_{2}-\\{u_{1},a,b,c\\}$ such that
$T_{2}-\\{u_{1},a,b,c,d\\}\notin\mathcal{T}_{3,5,7}$ ($d$ exists by Lemma 1),
then $v_{1}...v_{i-1}\,d\,v_{i}\,a\,b\,c\,v$ $v_{j+3}...v_{n}\equiv P$ where
$v_{j+3}...v_{n}\subseteq T_{2}-\\{a,b,c,d\\}$.
For the remaining cases, $T_{2}=T^{+}_{4}$. The possible situations are the
following. If $|T_{1}|=2$, then a copy of $P$ is found by considering
$\overline{\widetilde{P}}$. If $|T_{1}|=3$, we have the following two cases:

$v_{1}$$v_{2}$$v_{3}$$v$$v_{4}$$v_{5}$$v_{6}$$v_{7}$ Figure 1:
$v_{5}\,v_{4}\,v\,v_{7}\,v_{6}\,v_{3}\,v_{1}\,v_{2}\equiv P$.
$v_{1}$$v_{3}$$v_{2}$$v$$v_{4}$$v_{5}$$v_{6}$$v_{7}$ Figure 2:
$v_{7}\,v_{6}\,v_{5}\,v_{2}\,v_{3}\,v\,v_{4}\,v_{1}\equiv P$.

If $|T_{1}|=4$, the problem is solved unless $T_{1}=\overline{T_{2}}$ and
$x_{1}...x_{4}\equiv x_{9}...x_{6}$.
In this case, we have:

$v_{2}$$v_{3}$$v_{4}$$v_{1}$$v$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ Figure 3:
$v_{3}\,v\,v_{2}\,v_{1}\,v_{4}\,v_{6}\,v_{7}\,v_{8}\,v_{5}\equiv P$.

Finally, $\mathbf{s\leq b_{2}-1}$. Let $u_{1}...u_{s}$ be a directed path in
$T_{2}$ such that $(v_{i},u_{s})\in E(T)$. If $s\geq 2$, then $b_{2}\geq 3$.
Let $Q$ be a directed path of length $b_{2}-s-1$ in $T_{2}-[u_{1},u_{s}]$ such
that $(T_{2}-Q)-[u_{1},u_{s}]\supseteq Q_{1}\equiv x_{i+b_{2}+2}...x_{n}$, and
let $Q_{2}$ be a Hamiltonian directed path in
$T[\\{u_{1},...,u_{s-2},u_{s}\\}]$. If $(x_{i-1},x_{i})\in E(P)$ or
$|T_{1}|=1$ then $v_{1}...v_{i-1}vu_{s}v_{i}Qu_{s-1}...u_{1}Q_{1}\equiv P$.
Otherwise, $(x_{i},x_{i-1})\in E(P)$, then $(T_{1}-v_{i})+v\supseteq
v^{\prime}_{1}...v^{\prime}_{i}\equiv x_{1}...x_{i}$ such that
$v^{\prime}_{i}=v_{i-1}$. We will insert $Q,\,v,\,v_{i},\,u_{s}$ into
$v_{1}...v_{i-1}\,u_{s-1}...u_{1}$ $Q_{1}$ to obtain a copy of $P$ according
to the arcs between $v_{i-1},\,v_{i},\,u_{s-1}$ and $u_{s}$.
$(v_{i-1},u_{s})\in E(T)$ $\Rightarrow$
$v^{\prime}_{1}...v^{\prime}_{i}\,u_{s}\,v_{i}\,Q\,u_{s-1}...u_{1}\,Q_{1}\equiv
P$. $(u_{s},v_{i-1}),$ $(u_{s-1},v_{i})\in E(T)$ $\Rightarrow$
$v_{1}...v_{i-1}\,u_{s}\,Q\,v\,v_{i}\,u_{s-1}...u_{1}\,Q_{1}\equiv P$.
$(u_{s},v_{i-1})$, $(v_{i},u_{s-1})$,$(u_{s-1},v_{i-1})\in E(T)$ $\Rightarrow$
$v_{1}...v_{i-1}\,u_{s-1}\,u_{s}\,v_{i}\,Q\,u_{s-2}...u_{1}\,v\,Q_{1}\equiv
P$. The only remainder case is $(u_{s},v_{i-1})$, $(v_{i},u_{s-1})$,
$(v_{i-1},u_{s-1})\in E(T)$. In this case,
$v^{\prime}_{1}...v^{\prime}_{i}\,u_{s-1}\,v_{i}\,Q\,Q_{2}\,Q_{1}\equiv P$.
Now, we will treat the case $s=1$ and $b_{2}\geq 2$. If $(x_{i},x_{i-1})\in
E(P)$, then $|T_{2}|\geq 3$. If $\exists\,a\in(T_{2}-u_{1})\cap
N^{-}(v_{i-1})$and $b_{2}=\Delta^{+}(T)$, let $Q$ be a Hamiltonian directed
path in $T_{2}-\\{u_{1},a\\}$, then
$v_{1}...v_{i-1}\,a\,v_{i}\,Q\,u_{1}\,v\equiv P$. if $b_{2}<\Delta^{+}(T)$,
let $Q_{1}$ be a directed path of length $b_{2}-2$ in $T_{2}-\\{a,u_{1}\\}$
then $T_{2}-(V(Q_{1})\cup\\{a\\})\supseteq Q_{2}$ such that
$v_{1}...v_{i-1}\,a\,v_{i}\,Q_{1}\,v\,Q_{2}\equiv P$. If $(T_{2}-u_{1})\cap
N^{-}(v_{i-1})=\phi$, then $(T_{1}-v_{i-1})\subseteq N^{-}(v_{i-1})\cap
N^{-}(u_{1})$ and $(u_{1},v_{i-1})\in E(T)$. Since $b_{2}\geq 2$, then
$x_{i+2}...x_{n}$ is neither of type $P^{+}(1,2)$ nor directed starting from
$x_{i+2}$. By simple lemma, $(T_{2}-u_{1})+v\supseteq v_{i+2}...v_{n}\equiv
x_{i+2}...x_{n}$ such that $v_{i+2}\neq v$. For $|T_{1}|>2$, if
$\exists\,j<i-1$ such that $(v_{j},v_{i})\in E(T)$, then since
$(T_{1}-\\{v_{i-1},v_{i},v_{j}\\})+u_{1}\supseteq Q\equiv x_{1}...x_{i-2}$, so
$Q\,v_{i-1}\,v_{j}\,v_{i}\,v_{i+2}...v_{n}\equiv P$. If $(v_{i},v_{j})\in
E(T)$ whenever $j<i$, then $T_{1}-\\{v_{1},v_{i-1}\\}\supseteq Q_{1}\equiv
x_{1}...x_{i-2}$ and $Q_{1}\,v_{i-1}\,v_{1}\equiv x_{1}...x_{i}$. Then the
problem is solved since $(v_{i},v_{1})\in E(T)$. For $|T_{1}|=2$, if
$\exists\,a\in T_{2}-u_{1}$ such that $(T_{2}-a)\supseteq
v_{i+3}...v_{n}\equiv x_{i+3}...x_{n}$ with $v_{i+3}\neq u_{1}$, then
$a\,v_{1}\,v\,v_{2}\,v_{i+3}\,v_{n}\equiv P$. Otherwise, by simple lemma,
$x_{5}...x_{n}$ is a directed path. Let $a,\,b\in T_{2}-u_{1}$ such that
$(a,b)\in E(T)$. $|T_{2}|>3$, since otherwise, $N^{+}_{T}(b)=\\{v_{2}\\}$ then
$d^{+}_{T}(b)=1$ and so $\Delta^{+}(\overline{T})>\Delta^{+}(T)$, a
contradiction. Let $Q$ be a Hamiltonian directed path in
$T_{2}-\\{a,b,u_{1}\\}$, then $v\,v_{1}\,b\,a\,u_{1}\,Q\,v_{2}\equiv P$. For
$(x_{i-1},x_{i})\in E(P)$ or $i=1$, if $T_{2}-u_{1}\supseteq Q\equiv
x_{i+3}...x_{n}$, then $v_{1}...v_{i-1}\,v\,u_{1}\,v_{i}\,Q\equiv P$.
Otherwise, $T_{2}-u_{1}\in\mathcal{T}_{3,5,7}$ and $x_{i+3}...x_{n}$ is
antidirected. If $b_{2}=3$, let $a\in T_{2}-u_{1}$, then
$T_{2}-\\{a,u_{1}\\}\supseteq Q_{1}$ such that
$v_{1}...v_{i-1}\,v\,a\,u_{1}\,v_{i}\,Q_{1}\equiv P$. Otherwise, $b_{2}=2$. If
$|T_{1}|<|T_{2}|$, then, by considering $\widetilde{P}$ or
$\overline{\widetilde{P}}$, we recover one of the previous cases. If
$|T_{1}|=|T_{2}|$, then the problem is solved unless $T_{1}$ is isomorphic to
$\overline{T_{2}}$ and $x_{1}...x_{i}\equiv x_{n}...x_{n-i+1}$. Then
$\exists\,a\in T_{1}$ such that $d^{+}_{T_{1}}(a)=0$,
$T_{1}-a\in\mathcal{T}_{3,5,7}$ and $N^{-}(a)\cap T_{2}=\\{u_{1}\\}$. Let
$bcd$ be a directed path in $T_{1}-a$ and let $b^{\prime}\in T_{2}-u_{1}$.
$(T_{1}-\\{a,b,c,d\\})+v\supseteq Q^{\prime}$ and
$T_{2}-\\{b^{\prime},u_{1}\\}\supseteq Q^{\prime\prime}$ such that
$Q^{\prime}\,u_{1}\,b\,c\,d\,b^{\prime}\,a\,Q^{\prime\prime}\equiv P$.
From now on, we may suppose that any copy $y_{1}...y_{i}$ of $x_{1}...x_{i}$
in $T_{1}$ satisfies the condition that $N^{+}(y_{i})\cap T_{2}=\phi$. Thus,
by simple lemma, we can deduce that $x_{i}...x_{1}$ is directed or is of type
$P^{+}(1,2)$ with $T_{1}-y_{i}$ is a cyclic triangle. For $i=1$, if
$x_{i+2}..x_{n}$ is not directed, then choose $a\in T_{2}$ such that
$(T_{2}-a)+v\supseteq Q$ with $a\,v_{1}\,Q\equiv P$. Otherwise, by considering
$\overline{\widetilde{P}}$, the problem is solved since $b_{1}\geq 2$. For
$i\geq 2$, let $a\in T_{2}\cap N^{-}(v_{i-1})$, then $(T_{2}-a)+v\supseteq Q$
such that $v_{1}...v_{i-1}\,a\,v_{i}\,Q\equiv P$ unless $x_{i+2}...x_{n}$ is
directed or $\in P^{+}(1,2)$ with $T_{2}-a$ is a cyclic triangle. If
$\exists\,b\in(T_{2}-a)\cap N^{+}(a)$, then, if $T_{2}-a=bcd$ and
$x_{i+2}...x_{n}=P^{+}(1,2)$, $v_{1}...v_{i-1}\,a\,b\,d\,v_{i}\,c\,v\equiv P$
or $x_{i+2}...x_{n}$ is directed and $v_{1}...v_{i-1}\,a\,b\,v\,Q\,v_{i}\equiv
P$, where $Q$ is a Hamiltonian directed path in $T_{2}-\\{a,b\\}$. If
$(T_{2}-a)\cap N^{+}(a)=\phi$, since $d^{-}_{T_{2}}(v_{i-1})=1$, then
$d^{+}_{T_{1}}(v_{i-1})=0$ and $i=2$. Thus, by considering
$\widetilde{P}=y_{1}...y_{n}$ or $\overline{\widetilde{P}}=y_{1}...y_{n}$, the
problem is solved since $\widetilde{P}$ or $\overline{\widetilde{P}}$ contains
the arcs $(y_{1},y_{2})$ and $(y_{2},y_{3})$.

∎

######  Acknowledgment.

I would like to thank Professor Amin El Sahili and Doctor Maydoun Mortada for
their following up during the preparation of this paper.

## References

  * [1] B. Alspach and M. Rosenfeld  “Realization of certain generalized paths in tournaments”  In _Discrete Math_ 34, 1981, pp. 199–20
  * [2] P. Camion  “Chemins et Circuits Hamiltoniens des Graphs Complets”  In _Comptes Rendus de l’Académie des Science_ 269, 1959, pp. 2151–2152
  * [3] R. Forcade  “Parity of Paths and Circuits in Tournaments”  In _Discrete Math_ 6, 1973, pp. 115–118
  * [4] B. Grünbaum  “Antidirected Hamiltonian Paths in Tournaments”  In _Journal of Combinational Theory_ 11, B, 1971, pp. 249–257
  * [5] F. Havet and S. Thomassé  “Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld’s Conjecture”  In _Journal of Combinational Theory_ 78, B, 2000, pp. 243–273
  * [6] L. Rédei  “Ein Kombinatorischer Satz”  In _Acta Scientiarum Mathematicarum_ 7, 1934, pp. 39–43
  * [7] M. Rosenfeld  “Antidirected Hamiltonian Paths in Tournaments”  In _Journal of Combinational Theory_ 12, B, 1972, pp. 249–257
  * [8] A. Sahili and Z. Hanna  “About the Number of Oriented Hamiltonian Paths and Cycles in Tournaments” submitted
  * [9] H.J. Straight  “The existence of certain type of semi-walks in tournaments”  In _Proceedings of the Southeastern Conference on Combinatorics, Graph Theory and Computing, Congress. Numer._ 29, 1980, pp. 901–908
  * [10] A. Thomason  “Paths and Cycles in Tournaments”  In _Transactions of the American Mathematical Society_ 296, 1986, pp. 167–180


11institutetext: School of Computing, Queen’s University, Kingston, ON K7L
2N8, Canada

# Evolutionary Approaches to Explainable Machine Learning

Ryan Zhou and Ting Hu

###### Abstract

Machine learning models are increasingly being used in critical sectors, but
their black-box nature has raised concerns about accountability and trust. The
field of explainable artificial intelligence (XAI) or explainable machine
learning (XML) has emerged in response to the need for human understanding of
these models. Evolutionary computing, as a family of powerful optimization and
learning tools, has significant potential to contribute to XAI/XML. In this
chapter, we provide a brief introduction to XAI/XML and review various
techniques in current use for explaining machine learning models. We then
focus on how evolutionary computing can be used in XAI/XML, and review some
approaches which incorporate EC techniques. We also discuss some open
challenges in XAI/XML and opportunities for future research in this field
using EC. Our aim is to demonstrate that evolutionary computing is well-suited
for addressing current problems in explainability, and to encourage further
exploration of these methods to contribute to the development of more
transparent, trustworthy and accountable machine learning models.

##  1 Introduction

As the use of machine learning models becomes increasingly widespread in
various domains, including critical sectors of society such as finance and
healthcare, there is a growing need for human understanding of such models.
Although machine learning can detect complex patterns and relationships in
data, decisions based on the predictions made by these models can have real-
world impacts on human lives. The use of machine learning models in high-
stakes applications such as medicine, job hiring, and criminal justice has
raised concerns about the fairness, transparency, and accountability of these
models. Therefore, it is essential not only to develop accurate prediction
models but also to understand and explain how these predictions are being
made.

The field of explainable artificial intelligence (XAI) or explainable machine
learning (XML) has emerged in response to this need iML_Murdoch_PNAS_19 . XAI
research aims to develop methods to explain the decisions, predictions, or
recommendations made by machine learning models in a way that is
understandable to humans. These explanations act as a foundation to build
trust and improve the robustness of a model by highlighting biases and
failures, allow researchers to better understand, validate and debug the
model, ensure compliance with regulations, and improve human-machine
interaction by giving users a better understanding of when they can rely on a
model’s decisions.

In this book chapter, we aim to provide an overview of XAI/XML and the role of
evolutionary computing (EC) in this field. In Section 2, we introduce the
concept of XML and review current techniques used in the field. In Section 3,
we will focus on evolutionary techniques for explaining machine learning
models. Specifically, we will cover data visualization, feature selection and
engineering, local and global explanations, counter-factual and adversarial
examples. We will also discuss evolutionary methods designed specifically for
explaining deep learning models, as well as evolutionary methods for assessing
the quality of explanations themselves. In Section 4, we identify some
challenges remaining in the field of XAI/XML and discuss future opportunities
for incorporating EC. Finally, Section 5 provides concluding remarks for the
chapter.

##  2 Explainable Machine Learning

Explainability and the fields of XAI/XML are concerned with extracting
insights from machine learning models in order to make them more transparent,
interpretable and understandable to humans. The goal of XAI/XML is to develop
methods that can provide clear explanations of the decision-making process and
enable humans to understand what relationships a model has learned and how the
model arrived at its conclusions.

More concretely, the types of questions we wish to answer with an explanation
include bacarditIntersectionEvolutionaryComputation2022a :

  * •

Are the patterns the model is drawing on to make its prediction the ones we
expect?

  * •

Why did the model make this prediction instead of a different one, and what
would it take to make it change its prediction?

  * •

Is the model biased and are the decisions made by the model fair?

Explanations can be provided in many forms; examples include visualizations,
numerical values, data instances, or text explanations iML_Murdoch_PNAS_19 .

###  2.1 Interpretability vs. Explainability

The terms interpretability and explainability are often used interchangeably
by researchers. However, in this chapter we distinguish between them as
referring to two different but related aspects of attempting to understand a
model liptonMythosModelInterpretability2018 ; iML_Rudin_NatML_19 .

For our purposes, interpretability refers to the level of transparency and
ease of understanding of a model’s decision-making process. An interpretable
model is one whose decisions can be traced and understood by a human, for
example, by having a simple symbolic representation. In other words, a model
is considered interpretable if its decision-making process can be understood
simply by inspecting the model. For example, small decision trees are often
considered interpretable because it is feasible for a human to follow the
exact steps leading to the prediction.

On the other hand, even if we cannot trace the exact logic, a model can still
be considered explainable if a human-understandable explanation can be
provided for what the model is doing or why a decision is made. The more
comprehensive and understandable the explanation is, the more explainable the
overall system is. Explanations can be provided for the overall patterns and
relationships learned by a model, or for the logic used to produce an
individual prediction. Some practical methods for providing explanations
include evaluating feature importance, visualizing intermediate
representations, or comparing the prediction to be explained with samples from
the training set. An explanation essentially acts as an interface between the
human and the model, attempting to approximate the behavior or decisions made
by the model in a way that is comprehensible to humans. As such, this “model
of the model” must be both an accurate proxy for the model in the areas of
interest but also be understandable itself.

These two terms, interpretability and explainability, also roughly correspond
to two paradigms for improving the understandability of a model. The first
approach, often known as “intrinsic interpretability”, “glass-box” or
“interpretability by design”, focuses on the interpretability of the model and
aims to improve it by simplifying or otherwise restricting its complexity
IML_eBook_Molnar_22 . A simple enough model allows the exact logic to be
easily followed and understood by humans, but over-reducing the model
complexity can also restrict the performance of the model. In some cases, it
might not be possible to construct a simple enough model that can still
effectively solve the problem at hand.

The second approach, known as “post-hoc” or “black-box” methods, focuses on
explainability and aims to provide explanations by analyzing the model after
it has been trained. This approach does not restrict the performance of the
model in any way, but also makes it more challenging to provide informative
explanations. These explanation methods are typically independent of the
original model and are learned after the initial model has been trained
IML_eBook_Molnar_22 . In this chapter, we will primarily focus on this
approach to understanding models. However, in some cases, an explanation for a
complex model can take the form of simpler model; in this case, it is
important to consider the interpretability of the explanation as well.

It is also worth noting that these two goals are not mutually exclusive, and
both approaches can be used to better understand a model. The overall goal of
explainability is to develop better tools to understand machine learning
models, while the goal of interpretability is to construct models that can be
understood using the tools we have.

###  2.2 Explanation Methods

There are several types of explanations, which focus on different aspects of
the modeling process (Figure 1). In this section, we will provide an overview
of various categories, and describe some examples of each. This overview is
not meant to be exhaustive, but rather to highlight the various areas where
XAI techniques can be applied. For a more intensive survey of current methods
in XAI, we direct the reader to recent reviews dwivediExplainableAIXAI2023 ;
saeedExplainableAIXAI2023  on the topic.

Figure 1: Overview of the process of building a machine learning model,
showing areas where explanations (magnifying glasses) are often applied.
Examples of methods in each category are described in Section 2. Also shown is
the intrinsic interpretability approach (cogwheel), where models are designed
to be interpretable from the start. All these methods can be used together to
form a more complete picture of a model’s behavior.

#### Explaining Data

Although this category is sometimes omitted in discussions of explainable
machine learning, it is worth mentioning as part of the overall pipeline.
Methods under this category do not necessarily explain the model itself, but
aim to explain the underlying data that a model is trained on, focusing on
understanding the data distribution and its characteristics. Techniques such
as exploratory analysis, data visualization and dimensionality reduction can
be used to gain a better understanding of the patterns in the underlying data
that the model might learn, as well as identify any potential biases. Examples
of these techniques include Principal Component Analysis (PCA)
pearsonLIIILinesPlanes1901 ; hotellingAnalysisComplexStatistical1933  and
t-Distributed Stochastic Neighbor Embedding (t-SNE)
maatenVisualizingDataUsing2008 , which reduce the dimensionality of data to
allow for easy visualization. In addition, methods such as clustering and
outlier detection can help identify patterns or anomalies in the data that may
impact the model’s performance, and can aid in feature selection and
engineering. These explanations can help identify data quality issues, biases,
and preprocessing requirements, as well as build trust.

#### Explaining Features

This approach aims to explain the dependence of a model on each feature it
uses. For example, feature importance returns a score that represents the
significance of each feature to the model. This helps to identify which
features have the greatest impact on the model’s predictions and provides
insights into how the model is making decisions. This type of explanation can
also be used to verify whether the model is behaving as expected \- for
example, by checking whether it is using the same features a human would to
solve the problem. In the case of a computer vision model, this type of
explanation can be used to determine if the features being used to classify a
particular image as a cat make sense, or if the model is using spurious
patterns in the data, such as identifying the cat based on its surroundings.
This type of explanation can also aid in optimizing models and performing
feature selection by identifying less important features.

Some models, such as decision trees and tree ensembles like random forests,
provide feature importance measures randForest_Breiman_ML_01 . For other
models, Shapley additive explanations (SHAP) SHAP_Lundberg_NeurIPS_17
attempts to provide a universal method for assessing feature importance that
can be applied to most machine learning models. This is based on the Shapley
value, a concept from cooperative game theory that assigns a value to each
player in a game based on their contribution to the overall outcome. In the
context of machine learning, the “players” are the features in the data, and
the “game” is the prediction task. The Shapley value scores each feature based
on its contribution to each prediction. The exact calculation of Shapley
values is usually computationally impractical, as it involves evaluating every
possible combination of features. However, SHAP proposes approximating these
values using sampling and regression, making the estimation of feature
importance computationally feasible. This method is widely used in the field
of XAI.

#### Explaining Model Internals

Methods in this category attempt to explain the internal function of the
model, for example, by inspecting the structure of a tree or the weights in a
neural network. These approaches can either attempt to explain the entire
model, or to understand smaller components of the model.

Explaining the full model can be done by training a secondary model which both
approximates the original model and is more interpretable. An example of this
approach was proposed by Lakkaraju et al.
lakkarajuInterpretableExplorableApproximations2017 . Their approach
approximates the behavior of the model using a small number of decision sets,
providing an interpretable proxy for the entire model. While approximating the
full model in this and similar ways is effective for smaller models, producing
accurate but interpretable proxy models becomes increasingly difficult as the
size of the model increases. For large models with sufficiently complex
behavior, the proxy model will either be a poor approximation or will itself
be so large that it becomes difficult to interpret.

This difficulty has led to the development of methods which attempt to explain
smaller sub-components of a large model. Examining sub-components can allow us
to break down the overall function in a modular way, or to identify the parts
of a model which are responsible for certain decisions. For example, one way
to explain the function of a neuron in a neural network is by finding or
constructing an input that will maximize its activation
mahendranVisualizingDeepConvolutional2016 . This produces an idealized version
of the input that the neuron activates on.

In recent years, many methods have been developed for explaining the internals
of deep learning models samekExplainingDeepNeural2021 . This is due to the
rise in popularity of such models and their inherent black-box nature and
large size, making explanations for them challenging but particularly
important. As an example of one such method, Interpretable Lens Variable
Models adelDiscoveringInterpretableRepresentations2018  train an invertible
mapping from a complex internal representation inside a neural network (the
latent space in a generative or discriminative model) to a simpler,
interpretable one. A user supplies some side information in the form of a few
examples which illustrate the properties they are interested in being
represented explicitly, such as rotation and scaling. Then, the mapping is
learned while constraining certain dimensions in the interpretable
representation to obey a linear relationship with the side information. Since
the mapping is invertible, the output of the model can also be controlled by
making changes to the interpretable representation. The authors’ experiments
showed that this method can enable the user to control these properties of the
images generated by the model in an intuitive way.

#### Explaining Predictions

This type of approach aims to explain a specific prediction made by a model.
As such, the explanation only needs to capture the behaviour of the model with
respect to the prediction in question, rather than the model as a whole.

One popular approach in this category is Local Interpretable Model-agnostic
Explanations (LIME) expPredict_Ribeiro_KDD_16 . LIME explains a prediction by
sampling a set of instances similar to the input to be explained. It obtains
predictions for each of these instances and then fits a linear model to the
sampled set of inputs and predictions. This creates a linear approximation for
the model in the local neighborhood surrounding the instance to be explained.
Although this explanation does not necessarily reflect the global behavior of
the model, it is locally faithful and allows us to understand the behavior of
the model around that point.

Counterfactual explanations are another type of explanation which provide
information through a hypothetical example in which the model would have made
a different decision. For example, “the model would have approved a loan if
your income were $5000 higher” is a counterfactual illustrating how the input
would need to be changed in order to get a different result from the model
wachterCounterfactualExplanationsOpening2017b . This type of explanation is
intuitive and can be performed on a model in a black-box manner, without any
access to a model’s internals. One advantage of counterfactual explanations is
that they can provide users with recourse, a concrete set of changes that
could be made to change the decision to a different one
karimiSurveyAlgorithmicRecourse2020 . Additionally, because they directly
operate on the model’s evaluation, they are always faithful to the model’s
true behavior. However, because they consist of single instances or data
points, they provide less insight into the model’s overall behavior compared
to a more comprehensive explanation.

Diverse Counterfactual Explanations (DiCE)
mothilalExplainingMachineLearning2020  is one common method of constructing
counterfactual predictions. The aim of this method is to produce
counterfactuals which are valid (produce a different result when fed into the
model), proximal (are similar to the input), and diverse (different from each
other). Diversity is desirable here as it increases the likelihood of finding
a useful explanation and provides a more complete picture of the model’s
behavior. DiCE generates a diverse set of counterfactual examples using a
diversity metric based on determinantal point processes
kuleszaDeterminantalPointProcesses2012 , a probabilistic model which can solve
subset selection problems under diversity constraints. This diversity
constraint forces the various examples apart, while an additional proximity
constraint forces the examples to lie close to the original input. The method
also attempts to make the counterfactual examples differ from the input in as
few features as possible (feature sparsity).

#### Other Considerations

When choosing an explanation method, there are some other factors to consider,
such as whether a method is model-specific or model-agnostic, and whether it
provides global or local explanations.

Whether an explanation is considered model-specific or model-agnostic is based
on whether the technique is restricted to certain types of models, or if it
can be applied to multiple types of models. For instance, some methods of
generating feature importance measures randForest_Breiman_ML_01  are specific
to random forests and cannot be directly used to generate feature importance
for a neural network. Conversely, some methods are designed for extracting
information from the internal representation of neural networks, and cannot be
applied to random forests. These methods are model-specific. On the other
hand, Shapley additive explanations (SHAP) can be applied to assess feature
importance for any of the commonly used machine learning models, making it
model-agnostic.

In addition, explanations can be local or global. Local explanations aim to
provide an explanation for a specific input or group of inputs, while global
explanations aim to explain the behavior of the entire model. For instance, a
global explanation technique such as partial dependence plots
EstatLearn_Hastie_01  or feature importance identifies influential features
across the entire training dataset or model. On the other hand, LIME fits its
linear model to the neighborhood of a specific prediction, making it a local
explanation as it only deals with the behavior of the model in the specific
region near the prediction. While global explanations may appear to be
preferable to local explanations, in practice explanations are always
constrained by the amount of information a human can grasp at one time. As
such, while global explanations can provide information about overall trends
in the data or model, local explanations are useful for providing more detail
about specific aspects of interest.

##  3 Evolutionary Approaches to Explainable Machine Learning

###  3.1 Why Use EC?

Evolutionary computing (EC) is an approach to automatic adaptation inspired by
the principles of biological evolution that has been successfully applied to
various fields, including optimization, learning, engineering design, and
artificial life. This approach mimics the process of natural selection,
allowing the computer to evolve and optimize solutions to complex problems by
combining and improving upon existing solutions. Common techniques within EC
include evolutionary algorithms such as genetic algorithms, genetic
programming, and evolution strategies, and swarm intelligence algorithms such
as particle swarm optimization. These techniques use iterative processes of
selection, recombination, mutation, and adaptation to improve the performance
of the models.

EC has unique strengths that make it well-suited for handing the challenges of
XAI. First of all, EC can work with symbolic representations or interpretable
models such as decision trees or rule systems. This can be used to guarantee
interpretability of the evolved representation. If EC is used to evolve an
explanation using interpretable components, the explanation will be
interpretable. To leverage this, a common approach is to evolve an
interpretable approximation of the model, in whole or in part.

Evolutionary methods are also highly flexible, being able to perform black-box
optimization, and usually being derivative-free. As a result, they can be
applied to a variety of models without requiring knowledge of the model’s
internal logic – for example, when access to a model is only available through
an API which returns only the predictions. This flexibility also enables
optimization of unusual or customized metrics without requiring in-depth
knowledge of how to optimize the metric. Additionally, the flexibility of
evolutionary methods allows them to be used to create hybrid methods with
other algorithms or to serve as meta-learning methods.

EC is advantageous for XAI as it can handle multiple objectives
simultaneously. This is important as explanations by nature require both
faithfulness to the model as well as interpretability to humans. The
population-based nature of evolutionary algorithms also enables explicit use
of diversity metrics. This allows us to explore a range of different
explanations, increasing the chances of finding a useful one.

We will now delve into current methods which employ EC for producing
explanations, and provide an overview of these approaches and their
applications. There are a number of different ways to generate explanations,
and as before, we will discuss them based on the stage in the machine learning
modeling process in which they can be applied, highlighting works of interest.
For an extensive survey on these methods, we invite the reader to explore
recent reviews bacarditIntersectionEvolutionaryComputation2022a ;
meiExplainableArtificialIntelligence2022  on the use of evolutionary methods
in XAI.

###  3.2 Explaining Data

EC can be used to explain data by means of dimensionality reduction and
visualization. One approach is GP-tSNE GPinterpVis_Lensen_ITC_21 , which
adapts the classic t-SNE maatenVisualizingDataUsing2008  algorithm to use
evolved trees to provide an interpretable mapping from the original data
points to the embedded points. Similarly, Schofield and Lensen
schofieldUsingGeneticProgramming2021  use tree-GP to produce an interpretable
mapping for Uniform Manifold Approximation and Projection (UMAP). By producing
an explicit mapping function rather than simply the embedded points, we can
not only make the process more transparent but also reuse the mapping on new
data.

In some cases, we may want to use the lower dimensional representation for
prediction as well as visualization. This is useful for interpretability as it
allows us to visualize exactly the same data representation that the model
sees. Therefore, another approach is to construct features which are both
amenable to visualization and well-suited for downstream tasks. Icke and
Rosenberg ickeMultiobjectiveGeneticProgramming2011  proposed a multi-objective
GP algorithm to optimize three objective measures desirable for constructed
features - classifiability, visual interpretability and semantic
interpretability. Similarly, Cano et al.
canoMultiobjectiveGeneticProgramming2017  developed a method using multi-
objective GP to construct features for visualization and downstream analysis,
optimizing for six classification and visualization metrics. The
classification metrics (accuracy, AUC and Cohen’s kappa rate) aim to improve
the performance of the downstream classifier, while the visualization metrics
(C-index, Davies-Bouldin index, Dunn’s index) aim to improve the clustering
and separability of the features.

###  3.3 Feature Selection and Feature Engineering

Feature selection is a common preprocessing step where a relevant subset of
features is selected from the original dataset. This is used to improve the
performance of the model, but also has benefits for interpretability by
narrowing down the features the model can draw on. As an explanation, feature
selection shares some similarities with feature importance, which identifies
the features a model is drawing on, but instead restricts the model explicitly
so it can only draw on the chosen features.

Genetic algorithms are a straightforward and effective approach to feature
selection, with a natural representation in the form of strings of 1s and 0s,
making them a popular choice for feature selection
sayedNestedGeneticAlgorithm2019 ; shaFeatureSelectionPolygenic2021 ;
xueMultiObjectiveFeatureSelection2022 . Genetic programming can also be used
for feature selection since the inclusion of features in a tree or linear
genetic program is intrinsically evolved with the program
GPinterpret_Hu_GPTP_20 ; EvoNetOA_Hu_PLOSCB_18 ; SMILE_Sha_BMCBio_21 . For an
in-depth review of genetic programming methods, we refer the reader to
xueSurveyEvolutionaryComputation2016 . Swarm intelligence methods, such as
particle swarm optimization, have been applied to feature selection as well
xueSelfadaptiveParticleSwarm2019 . For a more detailed review of these
methods, we direct the reader to nguyenSurveySwarmIntelligence2020 . In
addition to selecting features for a model, feature selection can also be used
to improve data understanding by integrating it with techniques such as
clustering hancerSurveyFeatureSelection2020 .

Feature engineering, also referred to as feature construction, is a related
approach that involves building higher-level condensed features out of basic
features. Genetic programming can be used to evolve these higher-level
features for downstream tasks such as classification and regression
lacavaLearningFeatureSpaces2020 ; GP-FE_Li_BIBM_20 ;
muharramEvolutionaryConstructiveInduction2005 ;
virgolinExplainingMachineLearning2020 . This can also help improve the
interpretability of a model, since this can reduce a large number of low-level
features to a smaller number of higher-level features which may be easier to
understand for humans. Moreover, it removes some of the modeling out of the
black-box and into a transparent step beforehand, thereby reducing the amount
of explanation needed.

These methods also share many similarities with dimensionality reduction
techniques, and in some cases can fall under both categories. Uriot et al.
uriotGeneticProgrammingRepresentations2022  compared a variety of multi-tree
GP algorithms for dimensionality reduction, as well as a tree-based
autoencoder architecture. In the multi-tree representation, each individual in
the population is a collection of trees with each tree mapping the input to
one feature in the latent dimension. In order to reconstruct the input for the
autoencoder, a multi-tree decoder is simultaneously evolved with one tree per
input dimension. Their results showed that GP-based dimensionality reduction
was on par with the conventional methods they tested (PCA, LLE, and Isomap).

###  3.4 Model Extraction

This approach, also known as a global surrogate model, aims to approximate a
black-box model with an evolved interpretable model. This idea is closely
related to knowledge distillation buciluaModelCompression2006 ;
hintonDistillingKnowledgeNeural2015  in deep learning, but rather than simply
making the model smaller we also want to make it more interpretable.

Evans et al. iMLGP_Evans_GECCO_19  propose a model extraction method using
multi-objective genetic programming to construct decision trees that
accurately represent any black-box classifier while being more interpretable.
This method aims to simultaneously maximize the ability of the tree to
reconstruct (replicate) the predictions of a black-box model and also maximize
interpretability by minimizing the complexity of the decision tree. The
reconstruction ability is measured by the weighted F1 score over cross-
validation, and the complexity of the decision tree is measured by the number
of splitting points in the tree. The overall evolutionary process uses a
modified version of NSGA-II NSGA-II_Deb_TEC_02 . In their experiments on a
range of classification problems, they found that the accuracy remained
commensurate with other model extraction methods (Bayesian rule lists,
logistic regression, and two types of decision trees) while significantly
reducing the complexity of the models produced.

###  3.5 Local Explanations

Instead of creating an interpretable model to approximate the global
performance of a black-box model, which may not be possible, these approaches
only attempt to approximate the local behaviour using an evolutionary
algorithm. Much work in this area is inspired by LIME, but enhance the
relatively simple sampling strategy and linear approximation with evolutionary
components.

Ferreira et al. GP-localExp_Ferreira_CEC_20  proposed Genetic Programming
Explainer (GPX), a GP-based method which fits a local explanation model for a
given input example. Similar to LIME, when given a sample input to be
explained, the method samples a set of neighboring data points around the
input and fits a local explanation. However, rather than a linear model, GPX
uses a GP to evolve symbolic expression trees that best capture the behavior
of the pre-trained black-box model over the neighboring data points. The
authors tested this on both classification and regression datasets and
reported that the GP captured the model’s behavior better than LIME, as the
assumption of linear local behavior was not always valid, and also
outperformed a decision tree used as an explainer for the same neighbor set.

On the other hand, Guidotti et al. guidottiLocalRuleBasedExplanations2018
proposed Local Rule-based Explanations (LORE), which applies an evolutionary
algorithm to neighborhood generation rather than evolving the explanation
itself. A genetic algorithm generates a set of points near the prediction to
be explained, which are either classified the same as or differently from the
original prediction while being nearby. A decision tree is then used to fit
the local behavior of the black-box model. The use of a genetic algorithm here
ensures a dense sampling of points in the local neighborhood which lie on both
sides of the decision boundary.

###  3.6 Counterfactuals

Another line of work is in creating counterfactuals using EC. An EA is well
suited to this task as a black-box, possibly multi-objective optimizer, as it
allows us to find counterfactuals without knowing the internal workings of the
model while also optimizing for multiple desirable criteria in the
counterfactuals.

CERTIFAI sharmaCERTIFAICommonFramework2020  generates a population of
counterfactual explanations using a model-agnostic genetic algorithm. The
initial population is generated by sampling instances which lie on the other
side of the decision boundary of the model (i.e., are classified differently
from the instance to be explained). Then, the genetic algorithm optimizes the
population to minimize the distance (for some notion of distance, depending on
the type of data) from each counterfactual instance to the input instance. The
population is then analyzed for robustness, which increases if the best
counterfactual examples found are farther away from the input, and fairness,
which is measured by comparing robustness across different values of a
particular feature.

GeCo schleichGeCoQualityCounterfactual2021  uses a genetic algorithm with
feasibility and plausibility constraints on the features, specified using the
constraint language PLAF. This allows certain counterfactuals which would be
useless to the user (e.g. counterfactuals where the user changes their gender
or decreases their age) to be ruled out. Similar to CERTIFAI, the genetic
algorithm minimizes the distance from the input instance to the counterfactual
examples, prioritizing examples on the other side of the decision boundary but
also keeping examples which are close to the decision boundary if not enough
counterfactuals are available. The fitness function does not consider how many
features are changed relative to the input instance (with a smaller number
being preferred for ease of understanding), but the algorithm is biased toward
a smaller number of changes by initializing the population with only one
feature changed.

Multi-objective counterfactuals (MOC)
dandlMultiObjectiveCounterfactualExplanations2020  explicitly use multi-
objective optimization to consider multiple desirable properties of the
explanations. MOC uses a modified version of NSGA-II to perform its search.
Among the changes are the use of mixed integer evolution strategies (MIES)
liMixedIntegerEvolution2013  to search a mixed discrete and continuous space,
and a different crowding distance sorting algorithm which prioritizes
diversity in feature space. A total of four objectives are used, optimizing
for these four desirable properties: the model output for the example should
be close to the desired output; the example should lie close in feature space
to the input to be explained; the example should not differ from the input in
too many features; and the example is plausible (likely to be drawn from the
same distribution as the real data), measured by its distance to the closest
$k$ data points.

###  3.7 Explaining Deep Learning

Thus far, the methods we have covered are general, and can be used with a
variety of models. However, with the popularity of deep learning methods, we
would be remiss not to discuss some specific methods tailored for deep
learning models. While deep learning models are large, they are also
differentiable allowing for hybrid methods combining gradient information with
evolution.

For image classification, the large number of input features (pixels) presents
a significant problem for many explanation methods. As such, it is necessary
to reduce the dimension first, for example by clustering similar pixels into
“superpixels”. Wang et al. wangMultiobjectiveGeneticAlgorithm2022  propose
using a multi-objective genetic algorithm to identify superpixels of
importance for the final prediction, and using this set of superpixels as an
explanation. The genetic algorithm uses NSGA-II to optimize for the least
number of superpixels used, while maximizing the model’s confidence in its
prediction.

Adversarial examples are closely related to counterfactuals. An adversarial
example is a counterfactual example but with the intent of creating an
incorrect prediction IML_eBook_Molnar_22 . This is done by applying a small
perturbation to an example to change its classification. Most approaches
search for examples which are as close to the original input as possible, and
perceptually similar to the input. These examples are a method to highlight
failure modes of the model as well as a potential attack vector on deep
learning models.

Su et al. suOnePixelAttack2019  propose a method of finding adversarial
examples which modify only one pixel in an image. This is in contrast to
previous methods which modify multiple pixels in the image and are more
obvious to humans. Their method uses differential evolution, where each
individual is encoded by the coordinate of the pixel to be modified and the
perturbation in RGB space. They find that in many cases one pixel is
sufficient to deceive the model.

Adversarial examples are also present in models built for other domains, such
as natural language processing. Alzantot et al.
alzantotGeneratingNaturalLanguage2018  generate adversarial examples on a
sentiment analysis model and a textual entailment model. In addition, the
examples they produce are designed to be semantically and syntactically
similar to the original input, making the attack more difficult to spot. A
genetic algorithm is used to optimize for a different target label than the
original. Mutation is done by changing words in the input to similar words as
measured by a word embedding model (GloVe), and filtering out words which do
not fit the context.

###  3.8 Assessing Explanations

Finally, rather than using EC to generate the explanations themselves, we will
discuss some ways that it can be used to assess or improve the quality of
other explanation methods.

Huang et al. huangSAFARIVersatileEfficient2022  propose two metrics to assess
the robustness of an explanation: worst-case misinterpretation discrepancy and
probabilistic interpretation robustness. Interpretation discrepancy measures
the difference between two interpretations, one before and one after
perturbation of the input. It is desirable for this value to be low for a
interpretation to be robust to perturbation. They then measure the discrepancy
in two worst cases: the largest interpretation discrepancy possible while
still being classified as the same class, and the smallest interpretation
discrepancy possible while being classified differently (adversarial example).
These values are optimized for using a GA. The other metric, probability of
misinterpretation, calculates probabilistic versions of the above: the
probability of an example having the same classification but significantly
different interpretation, and the probability of an example having a different
classification but similar interpretation. This is estimated using subset
simulation.

It is also possible to perform an adversarial attack on the explanations
themselves. Tamam et al. tamamFoilingExplanationsDeep2022  do this with
AttaXAI, a black-box approach based on evolution. AttaXAI tries to evolve an
image similar in appearance to the original input and producing the same
prediction from the model, but with an arbitrary explanation map. In their
experiments, pairs of images were selected and they showed that they were able
to generate an new image with the appearance and prediction of the first
image, but with a similar explanation map to the second.

##  4 Research Outlook

###  4.1 Challenges

One major challenge for evolutionary approaches to XAI is scalability. As data
continues to grow and machine learning models become increasingly complex, the
number of parameters and features to be optimized grows as well. As such,
methods which work well on small models and datasets may become too expensive
on larger ones. However, large models are the most opaque and most in need of
explanation, so improving the scalability of XAI methods is necessary to
ensure they can be applied to even the largest models. In particular,
producing fully interpretable global explanations which accurately capture
behavior yet are still simple enough to understand may become too challenging
as models become larger – necessitating more local explanations or a more
focused approach concentrating on explaining particular properties or
components of the model. We also see here the potential for more use of
automated approaches to explainability – for example, by using evolutionary
search to find local explanations of interest and optimize for particular
properties. This idea has been explored with counterfactual examples, but it
could be extended to other types of explanations.

Another challenge for explainability is the incorporation of domain knowledge.
This can include knowledge from subject matter experts, as well as prior
knowledge about the dataset or problem. Current approaches to XAI are broad
and aim to provide explanations which are independent of the problem setting,
or at most are model-specific rather than problem-specific. However, it can
useful to see how well a solution found by a machine learning model aligns
with current knowledge in the field to evaluate the quality of the solution,
or conversely, to identify areas where the model deviates from current
understanding. For example, a practitioner may want to see how well the gene
associations found by a genomics model aligns with the literature, as well as
which associations are novel. This domain knowledge can be provided in the
form of expert rules, constraints, or structured data such as a graph
structure or tree. Domain knowledge can also be incorporated into the model-
building process to improve interpretability, for instance by constraining the
models to focus on associations known to be plausible (e.g. by incorporating
causality) or excluding irrelevant features.

###  4.2 Opportunities

We see some additional opportunities for future work employing EC for XAI. One
promising direction in current research is the use of multiple objectives to
optimize explanations. Explainability is inherently a multi-objective problem,
requiring the explanation to both be faithful to the model as well as being
simple enough to be interpretable. EC is well-suited to explicitly optimizing
for this, and we believe introducing these ideas into current and future
explanation methods is a straightforward but effective way of improving the
quality of explanations.

Along similar lines, diversity metrics and novelty search are another unique
strength available to evolutionary algorithms which can help improve the
explanations provided. The use of quality-diversity (illumination) algorithms
can produce a range of explanations which are both accurate and present
different perspectives on the behavior of the model. For example, a quality-
diversity approach to counterfactual explanations could ensure that a range of
behaviors are showcased in the examples.

Another opportunity for EC is the incorporation of user feedback, considering
the evolution of explanations as an open-ended evolution process.
Explainability is intended for the human user, and as such explanation quality
is ultimately subjective and can only be approximated by metrics. Users may
also have their own unique preferences for what constitutes a useful
explanation. Incorporating user feedback into the evolution process can allow
better tailored explanations that continue to improve. At the same time,
better metrics for measuring the quality of an explanation are also necessary
in order to not overwhelm the user.

###  4.3 Real-world Impacts

As AI becomes increasingly integrated into real-world applications, developing
better methods for providing explanations is essential for ensuring safety and
trust across various domains. With this in mind, it is also crucial to
consider the practical effects and benefits that XAI research can have. We
would like to highlight here a few application areas where work on
evolutionary approaches to XAI can have a substantial impact.

Healthcare is a domain where the consequences of errors can be especially
high. Untrusted models may be ignored by clinicians, wasting resources and
providing no benefit. Worse, seemingly trustworthy but flawed models may cause
harm to patients. Even models with few errors may exhibit systematic biases,
such as diagnostic models underdiagnosing certain patient groups while
appearing accurate seyyed-kalantariUnderdiagnosisBiasArtificial2021 .
Explainability can help identify these systematic errors and biases arias-
duartFocusRatingXAI2022 . In the financial sector AI models are employed for
fraud detection and risk assessment. Similar systematic biases in these models
can also produce harm, for example by disproportionately denying loans to
certain groups. In addition, regulatory bodies often require explanations for
these models to ensure compliance and maintain transparency.

Explainability also holds significant potential to advance engineering and
scientific discovery. AI models are used in various engineering applications,
for example in AI-driven materials design and drug discovery, and to produce
scientific insights in fields such as genomics and astrophysics. Explanations
can offer insight into the underlying mechanisms and relationships, improving
hypothesis generation and validating domain knowledge.

Natural language processing has experienced many recent breakthroughs, with
the development and deployment of models of unprecedented size. In particular,
there is an emerging paradigm of building “foundation models”, generalist deep
learning models which are trained on a wide range of data for general
capabilities and which can be further fine-tuned for downstream tasks
bommasaniOpportunitiesRisksFoundation2021 . These models are capable of tasks
which they are not specifically trained for, but it is still unclear how they
make decisions or generate outputs. Any flaws in these foundation models may
be carried over to application-specific models built on top of them. As these
models become more pervasive and their applications expand, understanding them
and identifying their failure modes becomes increasingly important.

##  5 Conclusion

Explainable AI/ML is an emerging field with important implications for machine
learning as a whole. With the increasing use of machine learning models in
real-world applications, it’s more important than ever that we understand such
models and what they learn. Evolutionary computing is well-poised to
contribute to the field, bringing a rich toolbox of tools for performing
black-box optimization. In this chapter, we introduced various paradigms for
explaining a machine learning model and current methods of doing so. We then
discussed how evolutionary computing can fit into these paradigms and the
advantages of employing it. In particular, evolutionary computing as an
optimizer is well suited for tricky interpretability metrics which are
difficult to handle due to reasons such as non-differentiability, as well as
for population-based metrics such as diversity and for optimizing a multiple
of these metrics at the same time. We highlighted a few methods in each
category which leveraged some of these strengths, but there is still
significant room for more exploration and more advanced evolutionary
algorithms.

The field of explainable machine learning is still new, and much knowledge
remains locked away within trained models that we still do not have the means
to decipher. The use of evolutionary computing for XAI is still uncommon, but
there are many opportunities ripe for the picking and we believe that it has
the potential to play a key part in the future of XAI.

## References

  * [1] Tameem Adel, Zoubin Ghahramani, and Adrian Weller.  Discovering Interpretable Representations for Both Deep Generative and Discriminative Models.  In Proceedings of the 35th International Conference on Machine Learning, pages 50–59. PMLR, July 2018.
  * [2] Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani B. Srivastava, and Kai-Wei Chang.  Generating natural language adversarial examples.  In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun’ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018, pages 2890–2896. Association for Computational Linguistics, 2018.
  * [3] Anna Arias-Duart, Ferran Parés, Dario Garcia-Gasulla, and Victor Gimenez-Abalos.  Focus! Rating XAI methods and finding biases.  In IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2022, Padua, Italy, July 18-23, 2022, pages 1–8. IEEE, 2022\.
  * [4] Jaume Bacardit, Alexander E. I. Brownlee, Stefano Cagnoni, Giovanni Iacca, John McCall, and David Walker.  The intersection of evolutionary computation and explainable AI.  In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22, pages 1757–1762, New York, NY, USA, July 2022. Association for Computing Machinery.
  * [5] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ B. Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen Creel, Jared Quincy Davis, Dorottya Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, and et al.  On the opportunities and risks of foundation models.  CoRR, abs/2108.07258, 2021.
  * [6] Leo Breiman.  Random Forest.  Machine Learning, 45:5–32, 2001.
  * [7] Cristian Buciluǎ, Rich Caruana, and Alexandru Niculescu-Mizil.  Model compression.  In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06, pages 535–541, New York, NY, USA, August 2006. Association for Computing Machinery.
  * [8] Alberto Cano, Sebastián Ventura, and Krzysztof J. Cios.  Multi-objective genetic programming for feature extraction and data visualization.  Soft Computing, 21(8):2069–2089, April 2017.
  * [9] Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl.  Multi-Objective Counterfactual Explanations.  In Thomas Bäck, Mike Preuss, André Deutz, Hao Wang, Carola Doerr, Michael Emmerich, and Heike Trautmann, editors, Parallel Problem Solving from Nature – PPSN XVI, Lecture Notes in Computer Science, pages 448–469, Cham, 2020. Springer International Publishing.
  * [10] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002\.
  * [11] Rudresh Dwivedi, Devam Dave, Het Naik, Smiti Singhal, Rana Omer, Pankesh Patel, Bin Qian, Zhenyu Wen, Tejal Shah, Graham Morgan, and Rajiv Ranjan.  Explainable AI (XAI): Core Ideas, Techniques, and Solutions.  ACM Computing Surveys, 55(9):194:1–194:33, January 2023.
  * [12] Benjamin P. Evans, Bing Xue, and Mengjie Zhang.  What’s inside the black box? a genetic programming method for interpreting complex machine learning models.  In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 1012–1020, 2019.
  * [13] Leonardo Augusto Ferreira, Frederico Gadelha Guimarães, and Rodrigo Silva.  Applying genetic programming to improve interpretability in machine learning models.  In Proceedings of the IEEE Congress on Evolutionary Computation (CEC), pages 1–8, 2020.
  * [14] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Dino Pedreschi, Franco Turini, and Fosca Giannotti.  Local Rule-Based Explanations of Black Box Decision Systems.  CoRR, abs/1805.10820, 2018.
  * [15] Emrah Hancer, Bing Xue, and Mengjie Zhang.  A survey on feature selection approaches for clustering.  Artificial Intelligence Review, 53(6):4519–4545, 2020.
  * [16] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  The Elements of Statistical Learning.  Springer, 2001.
  * [17] Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean.  Distilling the knowledge in a neural network.  CoRR, abs/1503.02531, 2015.
  * [18] H. Hotelling.  Analysis of a complex of statistical variables into principal components.  Journal of Educational Psychology, 24:417–441, 1933.
  * [19] Ting Hu.  Can genetic programming perform explainable machine learning for bioinformatics?  In Genetic Programming Theory and Practice XVII. Springer, 2020\.
  * [20] Ting Hu, Karoliina Oksanen, Weidong Zhang, Ed Randell, Andrew Furey, Guang Sun, and Guangju Zhai.  An evolutionary learning and network approach to identifying key metabolites for osteoarthritis.  PLoS Computational Biology, 14(3):e1005986, 2018.
  * [21] Wei Huang, Xingyu Zhao, Gaojie Jin, and Xiaowei Huang.  SAFARI: Versatile and efficient evaluations for robustness of interpretability.  CoRR, abs/2208.09418, 2022.
  * [22] Ilknur Icke and Andrew Rosenberg.  Multi-objective Genetic Programming for Visual Analytics.  In Sara Silva, James A. Foster, Miguel Nicolau, Penousal Machado, and Mario Giacobini, editors, Genetic Programming, Lecture Notes in Computer Science, pages 322–334, Berlin, Heidelberg, 2011. Springer.
  * [23] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera.  A survey of algorithmic recourse: Definitions, formulations, solutions, and prospects.  CoRR, abs/2010.04050, 2020.
  * [24] Alex Kulesza and Ben Taskar.  Determinantal point processes for machine learning.  Found. Trends Mach. Learn., 5(2-3):123–286, 2012.
  * [25] William La Cava and Jason H. Moore.  Learning feature spaces for regression with genetic programming.  Genetic Programming and Evolvable Machines, 21(3):433–467, September 2020.
  * [26] Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec.  Interpretable & explorable approximations of black box models.  CoRR, abs/1707.01154, 2017.
  * [27] Andrew Lensen, Bing Xue, and Mengjie Zhang.  Genetic programming for evolving a front of interpretable models for data visualization.  IEEE Transactions on Cybernetics, 51(11):5468–5482, 2021.
  * [28] Rui Li, Michael T. M. Emmerich, Jeroen Eggermont, Thomas Bäck, M. Schütz, J. Dijkstra, and J. H. C. Reiber.  Mixed integer evolution strategies for parameter optimization.  Evolutionary Computation, 21(1):29–64, 2013.
  * [29] Zhuang Li, Jie He, Xiaotong Zhang, Huadong Fu, and JIngyan Qin.  Toward high accuracy and visualization: An interpretable feature extraction method based on genetic programming and non-overlap degree.  In Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 299–304, 2020.
  * [30] Zachary C. Lipton.  The mythos of model interpretability.  Commun. ACM, 61(10):36–43, 2018.
  * [31] Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In Proceedings of the 31st International Conference on Neural Information Processing Systems (NeurIPS), pages 4768–4777, 2017.
  * [32] Aravindh Mahendran and Andrea Vedaldi.  Visualizing Deep Convolutional Neural Networks Using Natural Pre-images.  International Journal of Computer Vision, 120(3):233–255, December 2016.
  * [33] Yi Mei, Qi Chen, Andrew Lensen, Bing Xue, and Mengjie Zhang.  Explainable Artificial Intelligence by Genetic Programming: A Survey.  IEEE Transactions on Evolutionary Computation, pages 1–1, 2022\.
  * [34] Christoph Molnar.  Interpretable Machine Learning: A Guide for Making Black Box Models Explainable.  leanpub.com, 2022.
  * [35] Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan.  Explaining machine learning classifiers through diverse counterfactual examples.  In ACM Conference on Fairness, Accountability, and Transparency, January 2020.
  * [36] M. Muharram and G.D. Smith.  Evolutionary constructive induction.  IEEE Transactions on Knowledge and Data Engineering, 17(11):1518–1528, November 2005.
  * [37] W. James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu.  Interpretable machine learning: definitions, methods, and applications.  Proceedings of the National Academy of Sciences, 116(44):22071–22080, 2019.
  * [38] Bach Hoai Nguyen, Bing Xue, and Mengjie Zhang.  A survey on swarm intelligence approaches to feature selection in data mining.  Swarm and Evolutionary Computation, 54:100663, May 2020.
  * [39] Karl Pearson.  LIII. On lines and planes of closest fit to systems of points in space.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559–572, November 1901.
  * [40] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  “Why should I trust you?”: Explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135–1144, 2016.
  * [41] Cynthia Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 1:206–215, 2019.
  * [42] Waddah Saeed and Christian Omlin.  Explainable AI (XAI): A systematic meta-survey of current challenges and future opportunities.  Knowledge-Based Systems, 263:110273, March 2023.
  * [43] Wojciech Samek, Grégoire Montavon, Sebastian Lapuschkin, Christopher J. Anders, and Klaus-Robert Müller.  Explaining deep neural networks and beyond: A review of methods and applications.  Proc. IEEE, 109(3):247–278, 2021.
  * [44] Sabah Sayed, Mohammad Nassef, Amr Badr, and Ibrahim Farag.  A Nested Genetic Algorithm for feature selection in high-dimensional cancer Microarray datasets.  Expert Systems with Applications, 121:233–243, May 2019.
  * [45] Maximilian Schleich, Zixuan Geng, Yihong Zhang, and Dan Suciu.  GeCo: Quality counterfactual explanations in real time.  Proceedings of the VLDB Endowment, 14(9):1681–1693, May 2021.
  * [46] Finn Schofield and Andrew Lensen.  Using Genetic Programming to Find Functional Mappings for UMAP Embeddings.  In 2021 IEEE Congress on Evolutionary Computation (CEC), pages 704–711, June 2021.
  * [47] Laleh Seyyed-Kalantari, Haoran Zhang, Matthew B. A. McDermott, Irene Y. Chen, and Marzyeh Ghassemi.  Underdiagnosis bias of artificial intelligence algorithms applied to chest radiographs in under-served patient populations.  Nature Medicine, 27(12):2176–2182, 2021.
  * [48] Chengyuan Sha, Miroslava Cuperlovic-Culf, and Ting Hu.  SMILE: systems metabolomics using interpretable learning and evolution.  BMC Bioinformatics, 22:284, 2021.
  * [49] Zhendong Sha, Ting Hu, and Yuanzhu Chen.  Feature Selection for Polygenic Risk Scores using Genetic Algorithm and Network Science.  In 2021 IEEE Congress on Evolutionary Computation (CEC), pages 802–808, June 2021.
  * [50] Shubham Sharma, Jette Henderson, and Joydeep Ghosh.  CERTIFAI: A Common Framework to Provide Explanations and Analyse the Fairness and Robustness of Black-box Models.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 166–172, New York NY USA, February 2020\. ACM.
  * [51] Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai.  One pixel attack for fooling deep neural networks.  IEEE Trans. Evol. Comput., 23(5):828–841, 2019.
  * [52] Snir Vitrack Tamam, Raz Lapid, and Moshe Sipper.  Foiling explanations in deep neural networks.  CoRR, abs/2211.14860, 2022.
  * [53] Thomas Uriot, Marco Virgolin, Tanja Alderliesten, and Peter A. N. Bosman.  On genetic programming representations and fitness functions for interpretable dimensionality reduction.  In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’22, pages 458–466, New York, NY, USA, July 2022. Association for Computing Machinery.
  * [54] Laurens van der Maaten and Geoffrey Hinton.  Visualizing Data using t-SNE.  Journal of Machine Learning Research, 9(86):2579–2605, 2008.
  * [55] Marco Virgolin, Tanja Alderliesten, and Peter A. N. Bosman.  On explaining machine learning models by evolving crucial and compact features.  Swarm and Evolutionary Computation, 53:100640, March 2020.
  * [56] Sandra Wachter, Brent Mittelstadt, and Chris Russell.  Counterfactual explanations without opening the black box: Automated decisions and the GDPR.  Harv. JL & Tech., 31:841, 2017.
  * [57] Bin Wang, Wenbin Pei, Bing Xue, and Mengjie Zhang.  A Multi-objective Genetic Algorithm to Evolving Local Interpretable Model-agnostic Explanations for Deep Neural Networks in Image Classification.  IEEE Transactions on Evolutionary Computation, pages 1–1, 2022\.
  * [58] Bing Xue, Mengjie Zhang, Will N. Browne, and Xin Yao.  A Survey on Evolutionary Computation Approaches to Feature Selection.  IEEE Transactions on Evolutionary Computation, 20(4):606–626, August 2016.
  * [59] Yu Xue, Yihang Tang, Xin Xu, Jiayu Liang, and Ferrante Neri.  Multi-Objective Feature Selection With Missing Data in Classification.  IEEE Transactions on Emerging Topics in Computational Intelligence, 6(2):355–364, April 2022.
  * [60] Yu Xue, Bing Xue, and Mengjie Zhang.  Self-adaptive particle swarm optimization for large-scale feature selection in classification.  ACM Trans. Knowl. Discov. Data, 13(5):50:1–50:27, 2019.