# Delivering Inflated Explanations

Yacine Izza1 Alexey Ignatiev2 Peter Stuckey2 Joao Marques-Silva3 1CREATE,
National University of Singapore, Singapore
2Monash University, Melbourne, Australia
3IRIT, CNRS, Toulouse, France
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In the quest for Explainable Artificial Intelligence (XAI) one of the
questions that frequently arises given a decision made by an AI system is,
“why was the decision made in this way?” Formal approaches to explainability
build a formal model of the AI system and use this to reason about the
properties of the system. Given a set of feature values for an instance to be
explained, and a resulting decision, a formal _abductive explanation_ is a set
of features, such that if they take the given value will always lead to the
same decision. This explanation is useful, it shows that only some features
were used in making the final decision. But it is narrow, it only shows that
if the selected features take their given values the decision is unchanged.
Its possible that some features may change values and still lead to the same
decision. In this paper we formally define _inflated explanations_ which is a
set of features, and for each feature of set of values (always including the
value of the instance being explained), such that the decision will remain
unchanged. Inflated explanations are more informative than abductive
explanations since e.g they allow us to see if the exact value of a feature is
important, or it could be any nearby value. Overall they allow us to better
understand the role of each feature in the decision. We show that we can
compute inflated explanations for not that much greater cost than abductive
explanations, and that we can extend duality results for abductive
explanations also to inflated explanations.

##  1 Introduction

The purpose of eXplainable AI (XAI) is to help human decision makers in
understanding the decisions made by AI systems. It is generally accepted that
XAI is fundamental to deliver trustworthy AI Ignatiev (2020); Marques-Silva
and Ignatiev (2022). In addition, explainability is also at the core of recent
proposals for the verification of Artificial Intelligence (AI) systems Seshia
et al. (2022). Nevertheless, most of the work on XAI offers no formal
guarantees of rigor (and so will be referred to as non-formal XAI in this
paper). Examples of non-formal XAI include model-agnostic methods Ribeiro et
al. (2016); Lundberg and Lee (2017); Ribeiro et al. (2018), heuristic learning
of saliency maps (and their variants) Bach et al. (2015); Samek and Müller
(2019); Samek et al. (2019, 2021), but also proposals of intrinsic
interpretability Rudin (2019); Molnar (2020); Rudin et al. (2022). In recent
years, comprehensive evidence has been gathered that attests to to the lack of
rigor of these (non-formal) XAI approaches Ignatiev (2020); Izza et al.
(2022).

The alternative to non-formal explainability is _formal XAI_. Formal XAI
proposes definitions of explanations, and algorithms for their computation,
that ensure the rigor of computed explanations Shih et al. (2018); Ignatiev et
al. (2019); Marques-Silva and Ignatiev (2022). Despite its promise, formal XAI
also exhibits a number of important limitations, which include lack of
scalability for some ML models, and the computation of explanations which
human decision makers may fail to relate with. This paper targets mechanisms
for improving the clarity of computed explanations.

An abductive explanation Shih et al. (2018); Ignatiev et al. (2019) is a
subset-minimal set of features which correspond to a rule of the form: if a
conjunction of literals is true, then the prediction is the expected one. The
literals associated with that rule are of the form $x_{i}=v_{i}$, i.e. a
feature is tested for a concrete value in its domain. For categorical features
with large domains, and more importantly for real-value features, specifying a
literal that tests a single value will provide little insight. For example, in
the case of an ordinal feature, stating that the height of a patient is 1.825m
is less insightful that stating that the height of a patient is between 1.75m
and 1.84m. Similarly, in the case of a categorical feature, an explanation
that indicates that the vehicle color is one of
$\\{\textnormal{Red},\textnormal{Blue},\textnormal{Green},\textnormal{Silver}\\}$
(e.g. with colors $\\{\textnormal{Black},\textnormal{White}\\}$ excluded), is
more insightful that stating that the color must be Blue. For an explanations
involving several features, the use of more expressive literals will allow a
human decision maker to relate the explanation with several different
instances.

This paper proposes _inflated explanations_. In an inflated explanation the
literals of the form $x_{i}=v_{i}$ are replaced by literals of the form
$x_{i}\in\mathbb{E}_{i}$, where $\mathbb{E}_{i}$ is a subset of the feature’s
domain. Furthermore, each $\mathbb{E}_{i}$ is maximally large, i.e. no proper
superset of $\mathbb{E}_{i}$ guarantees sufficiency for the prediction.
Inflated explanations can be related with previous works Choi et al. (2020);
Izza et al. (2022); Ji and Darwiche (2023), but also with earlier work on
minimum satisfying assignments Dillig et al. (2012). For example, recent work
Izza et al. (2022) proposed algorithms for computing explanations in the case
of decision trees that report path explanations, where the literals are taken
from a concrete tree path; however, no algorithm for inflating explanations is
described. In contrast, our contribution is to propose algorithms for
transforming abductive explanations into inflated (abductive) explanations,
and such that these algorithms are shown to be efficient in practice.
Furthermore, we prove that contrastive explanations can also be inflated, and
that there exist different minimal hitting set duality Ignatiev et al. (2020)
relationships between inflated explanations. The duality results regarding
contrastive explanations attest to the robustness of minimal hitting set
duality in explainability. The experimental results illustrate that in
practice features can in general be inflated, with some inflated to almost
their original domain.

The paper is organized as follows. Section 2 introduces the notation and
definitions used throughout. This section also motivates the importance of
inflating explanations. Section 3 defines inflated abductive explanations, and
details algorithms for their computation. Different algorithms are devised for
categorical and ordinal features. Moreover, Section 4 proposes two definitions
for inflated contrastive explanations and demonstrates that minimal hitting
set duality with respect to inflated abductive explanations in both cases.
Section 5 demonstrates the practical interest of inflated explanations.
Section 6 concludes the paper.

##  2 Preliminaries

##### Classification problems.

We consider a classification problem, characterized by a set of features
${\mathcal{F}}=\\{1,\ldots,m\\}$, and by a set of classes
${\mathcal{K}}=\\{c_{1},\ldots,c_{K}\\}$. Each feature $j\in{\mathcal{F}}$ is
characterized by a domain $\mathbb{D}_{j}$. As a result, feature space is
defined as
$\mathbb{F}={\mathbb{D}_{1}}\times{\mathbb{D}_{2}}\times\ldots\times{\mathbb{D}_{m}}$.
A specific point in feature space represented by
$\mathbf{v}=(v_{1},\ldots,v_{m})$ denotes an _instance_ (or an _example_).
Also, we use $\mathbf{x}=(x_{1},\ldots,x_{m})$ to denote an arbitrary point in
feature space. In general, when referring to the value of a feature
$j\in{\mathcal{F}}$, we will use a variable $x_{j}$, with $x_{j}$ taking
values from $\mathbb{D}_{j}$. We consider two types of features
$j\in{\mathcal{F}}$: _categorical features_ where $\mathbb{D}_{j}$ is a finite
unordered set, and _ordinal features_ where $\mathbb{D}_{j}$ is a possibly
infinite ordered set. For ordinal (real-valued) features $j$ we use range
notation $[\lambda(j),\mu(j)]$ to indicate the set of values
$\\{d~{}|~{}d\in\mathbb{D}_{j},\lambda(j)\leq d\leq\mu(j)\\}$, and
$[\lambda(j),\mu(j))$ to indicate the (half-open) set of values
$\\{d~{}|~{}d\in\mathbb{D}_{j},\lambda(j)\leq d<\mu(j)\\}$. A classifier
implements a _total classification function_
$\kappa:\mathbb{F}\to{\mathcal{K}}$. For technical reasons, we also require
$\kappa$ not to be a constant function, i.e. there exists at least two points
in feature space with differing predictions.

Given the above, we represent a classifier ${\mathcal{M}}$ by a tuple
${\mathcal{M}}=({\mathcal{F}},\mathbb{F},{\mathcal{K}},\kappa)$. Moreover, and
given a concrete instance $(\mathbf{v},c)$, an explanation problem is
represented by a tuple $({\mathcal{M}},(\mathbf{v},c))$.

Throughout the paper, we consider the following families of classifiers:
monotonic classifiers, decision lists and tree ensembles. These families of
classifiers are well-known, and have been investigated in the context of
logic-based explainability Marques-Silva et al. (2021); Ignatiev and Marques-
Silva (2021); Ignatiev (2020).

##### Running examples.

The monotonic classifier of Example 1 will be used throughout the paper.

######  Example 1 (Running example – ordinal features).

We consider a monotonic classifier defined on ordinal features, adapted from
(Marques-Silva et al., 2021, Example 1). The classifier serves for predicting
student grades. It is assumed that the classifier has learned the following
formula (after being trained with grades of students from different cohorts):

$\begin{array}[]{rcl}S&=&\max\left[0.3\times{Q}+0.6\times{X}+0.1\times{H},R\right]\\\\[2.0pt]
M&=&\textnormal{ite}(S\geq 9,A,\textnormal{ite}(S\geq
7,B,\textnormal{ite}(S\geq 5,C,\\\\[1.5pt] &&\textnormal{ite}(S\geq
4,D,\textnormal{ite}(S\geq 2,E,F)))))\\\ \end{array}$

The features represent the different components of assessment, namely $S$,
$Q$, $X$, $H$ and $R$ denote, respectively, the final score, the marks on the
quiz, the exam, the homework, and the mark of an optional research project.
Each mark ranges from 0 to 10. (For the optional mark $R$, the final mark is 0
if the student opts out.) The final score is the largest of the two marks, as
shown above. The student’s final grade $M$ is defined using an ite (if-then-
else) operator, and ranges from $A$ to $F$. Features $Q$, $X$, $H$ and $R$ are
respectively numbered 1, 2, 3 and 4, and so ${\mathcal{F}}=\\{1,2,3,4\\}$.
Each feature takes values from $[0,10]$, i.e. $\lambda(i)=0$ and $\mu(i)=10$.
The set of classes is ${\mathcal{K}}=\\{A,B,C,D,E,F\\}$, with
${F}\prec{E}\prec{D}\prec{C}\prec{B}\prec{A}$. Clearly, the complete
classifier (that given the different marks computes a final grade) is
monotonic. Moreover, and in contrast with Marques-Silva et al. (2021), we will
we consider the following point in feature space representing a student
$s_{1}$, $(Q,X,H,R)=(5,10,5,8)$, with a predicted grade of $B$, i.e.
$\kappa(5,10,5,8)=B$, given that $S=8$. Moreover, and unless stated otherwise,
the order in which features are analyzed throughout the paper will be $\langle
1,2,3,4\rangle$.

The decision list of Example 2 will also be used throughout the paper.

######  Example 2 (Running example – categorical features).

We also consider a decision list with categorical features. The classification
problem is to assess risk accident, given two features, age segment
(represented by variable $A$), and car color (represented by variable $C$).
Let ${\mathcal{F}}=\\{1,2\\}$, ${\mathcal{K}}=\\{0,1\\}$
$\mathbb{D}_{1}=\\{\textnormal{Adult},\textnormal{Young~{}Adult},\textnormal{Senior}\\}$
(but where we use Junior instead of Young Adult)
$\mathbb{D}_{2}=\\{\textnormal{Red},\textnormal{Blue},\textnormal{Green},\textnormal{Silver},\textnormal{Black},\textnormal{White}\\}$.
Let the decision list be,

$\begin{array}[]{llcc}\textnormal{IF}&A=\textnormal{Adult}&\textnormal{THEN}&\kappa(\mathbf{x})=0\\\
\textnormal{ELSE
IF}&C=\textnormal{Red}&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{ELSE
IF}&C=\textnormal{Blue}&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{ELSE
IF}&C=\textnormal{Green}&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{ELSE
IF}&C=\textnormal{Black}&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{ELSE}&&&\kappa(\mathbf{x})=0\\\ \end{array}$

Moreover, we consider the instance
$(\mathbf{v},c)=((\textnormal{Junior},\textnormal{Red}),1)$, i.e. a young
adult with a red colored car represents a risk of accident.

##### Logic-based explainability.

Two types of formal explanations have been studied: abductive Shih et al.
(2018); Ignatiev et al. (2019) and contrastive Miller (2019); Ignatiev et al.
(2020). Abductive explanations broadly answer a Why question, i.e.  _Why the
prediction?_ , whereas contrastive explanations broadly answer a Why Not
question, i.e.  _Why not some other prediction?_.

Given an explanation problem, an abductive explanation (AXp) is a subset-
minimal set of features ${\mathcal{X}}\subseteq{\mathcal{F}}$ which, if
assigned the values dictated by the instance $(\mathbf{v},c)$, are sufficient
for the prediction. This is stated as follows, for a chosen set
${\mathcal{X}}$:

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

Monotonicity of entailment implies that there exist algorithms for computing a
subset-minimal set ${\mathcal{X}}\subseteq{\mathcal{F}}$ that are polynomial
on the time to decide (1) Marques-Silva and Ignatiev (2022).

An AXp ${\mathcal{X}}$ can be interpreted as a logic rule, of the form:

$\textnormal{IF}~{}~{}\left[\bigwedge_{i\in{\mathcal{X}}}(x_{i}=v_{i})\right]~{}~{}\textnormal{THEN}~{}~{}[\kappa(\mathbf{x})=c]$
(2)

Moreover, and given an explanation problem, a contrastive explanation (CXp) is
a subset-minimal set of features ${\mathcal{Y}}\subseteq{\mathcal{F}}$ which,
if the features in ${\mathcal{F}}\setminus{\mathcal{Y}}$ are assigned the
values dictated by the instance $(\mathbf{v},c)$, then there is an assignment
to the features in ${\mathcal{Y}}$ that changes the prediction. This is stated
as follows, for a chosen set ${\mathcal{Y}}\subseteq{\mathcal{F}}$:

$\exists(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{i\in{\mathcal{X}}\setminus{\mathcal{Y}}}(x_{i}=v_{i})\right]\land(\kappa(\mathbf{x})\not=c)$
(3)

Similarly to the case of AXp’s, monotonicity of entailment ensures that there
exist algorithms for computing a subset-minimal set
${\mathcal{Y}}\subseteq{\mathcal{F}}$ that are polynomial on the time to
decide (3) Marques-Silva and Ignatiev (2022).

Following standard notation Marques-Silva and Ignatiev (2022), we use the
predicate $\mathsf{WAXp}$ (resp. $\mathsf{WCXp}$) to hold true for any set
${\mathcal{X}}\subseteq{\mathcal{F}}$ for which (1) (resp. (3)) holds, and the
predicate $\mathsf{AXp}$ (resp. $\mathsf{CXp}$) to hold true for any subset-
minimal (or irreducible) set ${\mathcal{X}}\subseteq{\mathcal{F}}$ for which
(1) (resp. (3)) holds.

AXp’s and CXp’s respect a minimal-hitting set (MHS) duality relationship
Ignatiev et al. (2020). Concretely, each AXp is an MHS of the CXp’s and each
CXp is an MHS of the AXp’s. MHS duality is a stepping stone for the
enumeration of explanations.

######  Example 3.

For the monotonic classifier of Example 1, and instance $((5,10,5,8),B)$, we
can use existing algorithms Marques-Silva et al. (2021); Cooper and Marques-
Silva (2021, 2023), for computing one AXp. We use the proposed order for
analyzing features: $\langle 1,2,3,4\rangle$. we conclude that $Q$ must be
included in the AXp, since increasing the value of $Q$ to 10 would change the
prediciton. In contrast, given the value of $R$, and because we have fixed
$Q$, then both $X$ and $H$ are dropped from the AXp. Moreover, we conclude
that $R$ must be included in the AXp; otherwise, we would be able to change
the prediction to $A$ by increasing $R$. As a result, the computed AXp is
${\mathcal{X}}=\\{1,4\\}$. (For a different order of the features, a different
AXp would be obtained.) With this AXp, we associate the following rule:

$\textnormal{IF}~{}[{Q}=5\land{R}=8]~{}\textnormal{THEN}~{}[\kappa(\mathbf{x})=B]$

######  Example 4.

For the decision list running example (see Example 2), and given the instance
$(\mathbf{v},c)=((\textnormal{Junior},\textnormal{Red}),1)$, an AXp is
$\\{1,2\\}$, meaning that,

$\textnormal{IF}~{}~{}A=\textnormal{Junior}\land
C=\textnormal{Red}~{}~{}\textnormal{THEN}~{}~{}\kappa(\mathbf{x})=1$

where $\mathbf{x}=(A,C)$.

Logic-based explainability is covered in a number of recent works.
Explainability queries are studied in Audemard et al. (2020, 2021); Huang et
al. (2021); Audemard et al. (2022). Probabilistic explanations are
investigated in Wäldchen et al. (2021); Arenas et al. (2022). There exist
proposals to account for constraints on the inputs Gorji and Rubin (2022). A
distinction between constrastive and counterfactual explanations is studied in
Liu and Lorini (2023). Additional recent works include Boumazouza et al.
(2020); Malfa et al. (2021); Boumazouza et al. (2021); Liu and Lorini (2022);
Darwiche and Hirth (2023); Amgoud (2023); Bassan and Katz (2023). In addition,
there exist recent surveys summarizing the progress observed in formal XAI
Marques-Silva and Ignatiev (2022); Marques-Silva (2022).

##### Motivating examples & related work

For the two running examples, let us anticipate what we expect to obtain with
inflated explanations.

######  Example 5 (Explanations with more expressive literals – ordinal
features.).

For the monotonic classifier of Example 1, and instance $((5,10,5,7),B)$, one
AXp is ${\mathcal{X}}=\\{1,4\\}$. Our goal is to identify more general
literals than the equality relational operator. Similarly to recent work Izza
et al. (2022), we use the set-membership ($\in$) operator. The purpose of the
paper is to propose approaches for obtaining more expressive rules using the
$\in$ operator. As a result, instead of the rule from Example 3, a more
expressive rule would be,

$\textnormal{IF}~{}[{Q}\in[0,6.6]\land{R}\in[7,8.8]]~{}\textnormal{THEN}~{}[\kappa(\mathbf{x})=B]$

(Depending on how the domains are expanded, larger intervals could be
obtained. Later in the paper, we explain how the above values were obtained.)
Clearly, the modified rule is more informative, about the marks that yield a
grade of B, than the rule shown in Example 3.

######  Example 6 (Explanations with more expressive literals – categorical
features.).

For the decision list of Example 2, and instance
$((\textnormal{Junior},\textnormal{Red}),1)$, the only AXp is
${\mathcal{X}}=\\{1,2\\}$. The purpose of this paper is to identify more
general literals. For this example, instead of the rule from Example 4, a more
expressive rule would be,

$\textnormal{IF}~{}A\>{\in}\>\\{\textnormal{Junior},\textnormal{Senior}\\}\land
C\>{\in}\>\\{\textnormal{Red},\textnormal{Blue},\textnormal{Green}\\}~{}\textnormal{THEN}~{}\kappa(\mathbf{x})=1$

As in the previous example, the modified rule is more informative than the
rule shown in Example 4.

The use of generalized explanation literals is formalized in earlier work
Amgoud (2021); Amgoud and Ben-Naim (2022); Amgoud (2023). Initial approaches
for computing explanations with more expressive literals include Choi et al.
(2020); Izza et al. (2022); Ji and Darwiche (2023).

##  3 Inflated Abductive Explanations

In order to account for more expressive literals in the definition of
abductive explanations, we consider an extended definition of AXp.

###  3.1 Definition

Given an AXp ${\mathcal{X}}\subseteq{\mathcal{F}}$, an inflated abductive
explanation (iAXp) is a tuple $({\mathcal{X}},\mathbb{X})$, with
${\mathcal{X}}\subseteq{\mathcal{F}}$ is an AXp of the explanation problem
${\mathcal{E}}$, and $\mathbb{X}$ is a set of pairs $(j,\mathbb{E}_{j})$, one
for each $j\in{\mathcal{X}}$, such that the following logic statement holds
true,

$\forall(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{j\in{\mathcal{X}}}(x_{j}\in\mathbb{E}_{j})\right]\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$
(4)

where $v_{j}\in\mathbb{E}_{j},\forall j\in{\mathcal{X}}$, and where
$\mathbb{E}_{j}$ is a maximal set such that (4) holds. (Concretely, for any
$j\in{\mathcal{X}}$, and for any
$\mathbb{I}_{j}\subseteq\mathbb{D}_{j}\setminus\mathbb{E}_{j}$, it is the case
that (4) does not hold when $\mathbb{E}_{j}$ is replaced with
$\mathbb{E}_{j}\cup\mathbb{I}_{j}$.) Clearly, (4) is a stronger statement than
Equation (3), assuming at least one $\mathbb{E}_{j}\supset\\{v_{j}\\}$.

After computing one AXp ${\mathcal{X}}$, it is the case that either
$\mathbb{E}_{j}=\\{v_{j}\\}$ (for a categorical feature) or
$\mathbb{E}_{j}=[v_{j},v_{j}]$ (for an ordinal feature). Our purpose is to
find ways of augmenting $\mathbb{E}_{j}$ maximally.

######  Example 7.

For the monotonic classifier of Example 1, and the proposed inflated AXp of
Example 5, for feature 1, we can conclude that we get
$\mathbb{E}_{1}=[3.4,6.6]$.

Observe that the decision to start from an AXp aims at practical efficiency.
Algorithm 1 could be adapted to start from the set of features ${\mathcal{F}}$
instead of ${\mathcal{X}}$. Any feature for which the expansion includes its
domain is removed from the AXp. The set of inflated features for which the
inflation did not yield their domain represents one AXp.

###  3.2 Computation of Inflated Explanations

Algorithm 1 summarizes the algorithm for inflating a given AXp. As shown, the
algorithm picks some order for the features in the AXp ${\mathcal{X}}$. The
features not included in the AXp ${\mathcal{X}}$ will not be analyzed, i.e. we
are only interested in inflating features that are not already inflated.

Input: ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$, AXp
${\mathcal{X}}\subseteq{\mathcal{F}}$, Precision $\delta$

1:function $\mathsf{InflateAXp}$(${\mathcal{E}},{\mathcal{X}}$)

2: $\mathbb{X}\leftarrow\emptyset$ $\triangleright$ $\mathbb{X}$: Sets
composing inflated explanation

3: $\iota\leftarrow\mathsf{PickSomeOrder}({\mathcal{X}})$

4: for all $j\in\iota$ do

5: if $\mathsf{Categorical}(j)$ then

6: $\mathbb{E}_{j}\leftarrow\\{v_{j}\\}$

7:
$\mathbb{E}_{j}\leftarrow\mathsf{InflateCategorical}(j,\mathbb{E}_{j},{\mathcal{E}},{\mathcal{X}})$

8: else

9: $\mathsf{inf}(j)=\mathsf{sup}(j)=v_{j}$

10: $\mathbb{E}_{j}\equiv[\mathsf{inf}(j),\mathsf{sup}(j)]$ $\triangleright$
$\mathbb{E}_{j}$ changes w/ $\mathsf{inf}(j)$,$\mathsf{sup}(j)$

11:
$\mathbb{E}_{j}\leftarrow\mathsf{InflateOrdinal}(j,\mathbb{E}_{j},{\mathcal{E}},{\mathcal{X}},\delta)$

12: $\mathbb{X}\leftarrow\mathbb{X}\cup\\{(j,\mathbb{E}_{j}\\})$

13: return $({\mathcal{X}},\mathbb{X})$

Algorithm 1 Computing inflated explanations

The procedure to inflate the values associated with a feature
$i\in{\mathcal{X}}$ depends on the type of the feature. In the next sections,
we detail how categorical and ordinal features can be inflated.

####  3.2.1 Categorical Features

Algorithm 2 summarizes the algorithm for a given categorical feature
$j\in{\mathcal{X}}$. Given an initial $\mathbb{E}_{j}$, we traverse all the
values in the domain of the feature, with the exception of the values in
$\mathbb{E}_{j}$. For each value, we check whether inflating $\mathbb{E}_{j}$
with that value maintains the sufficiency of prediction, i.e. Equation 4 still
holds. If sufficiency of prediction still holds, then the value is kept, and
the algorithm most to another value. Otherwise, the value is removed from
$\mathbb{E}_{j}$, and another value will be considered.

Input: Feature $j$, $\mathbb{E}_{j}$,
${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$, and AXp
${\mathcal{X}}\subseteq{\mathcal{F}}$

1:function
$\mathsf{InflateCategorical}$($j,\mathbb{E}_{j},{\mathcal{E}},{\mathcal{X}}$)

2: $\mathbb{R}_{j}\leftarrow\mathbb{D}_{j}\setminus\mathbb{E}_{j}$
$\triangleright$ $\mathbb{R}_{j}$: what remains of $\mathbb{D}_{j}$

3: $\eta\leftarrow\mathsf{PickSomeOrder}(\mathbb{R}_{j})$

4: for all $u_{ji}\in\eta$ do

5: $\mathbb{E}_{j}\leftarrow\mathbb{E}_{j}\cup\\{u_{ji}\\}$ $\triangleright$
Expand $\mathbb{E}_{j}$, conditionally

6: if (4) does not hold then

7: $\mathbb{E}_{j}\leftarrow\mathbb{E}_{j}\setminus\\{u_{ji}\\}$
$\triangleright$ Revert expansion of $\mathbb{E}_{j}$

8: return $\mathbb{E}_{j}$

Algorithm 2 Inflate categorical feature

######  Example 8.

For the decision list of Example 2, and the instance
$(\mathbf{v},c)=((\textnormal{Junior},\textnormal{Red}),1)$, from Example 4,
we know that (the only) AXp is $\\{1,2\\}$. Let us pick the order of features
$\iota=(1,2)$. For feature 1, the order of values is (for example)
$(\textnormal{Adult},\textnormal{Senior})$, and initially
$\mathbb{E}_{1}=\\{\textnormal{Junior}\\}$. Clearly, we cannot consider the
value Adult for feature 1, as this would change the prediction. In contrast,
the value Senior can be added to $\mathbb{E}_{1}$. With respect to feature 2,
the order of values is (for example)
$(\textnormal{Blue},\textnormal{Green},\textnormal{Silver},\textnormal{Black},\textnormal{White})$,
and initially $\mathbb{E}_{2}=\\{\textnormal{Red}\\}$. Clearly, by inspection
of the decision list, we can conclude that, for a non-Adult, any of the colors
Red, Blue, Green and Black will yield prediction 1. Hence, $\mathbb{E}_{2}$
can be inflated from $\\{\textnormal{Red}\\}$ to
$\\{\textnormal{Red},\textnormal{Blue},\textnormal{Green},\textnormal{Black}\\}$,
as these values do not change the sufficiency for the prediction. As a result,
the inflated explanation denotes the rule,

IF $\displaystyle
A\>{\in}\>\\{\textnormal{Junior},\textnormal{Senior}\\}\land$ $\displaystyle
C\>{\in}\>\\{\textnormal{Red},\textnormal{Blue},\textnormal{Green},\textnormal{Black}\\}~{}\textnormal{THEN}~{}\kappa(\mathbf{x})=1$

Hence, from the decision list, and given the list, it becomes clear that a
driver does not pose a risk of accident if he/she is an Adult, or otherwise
drive a car colored Silver or White.

####  3.2.2 Ordinal Features

Input: Feat. $j$, $\mathbb{E}_{j}$,
${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$, AXp
${\mathcal{X}}\subseteq{\mathcal{F}}$, Precision $\delta$

1:function
$\mathsf{InflateOrdinal}$($j,\mathbb{E}_{j},{\mathcal{E}},{\mathcal{X}},\delta$)

2: if $\mathsf{UnconstrainedSup}(j,{\mathcal{E}},{\mathcal{X}})$ then

3: $\mathsf{sup}(j)\leftarrow\mu(j)$

4: if $\mu(j)={+}\infty$ then

5: $\mathbb{E}_{j}\equiv[\mathsf{inf}(j),{+}\infty)$

6: else

7:
$\mathsf{sup}(j)\leftarrow\mathsf{ExpandSup}(j,{\mathcal{E}},{\mathcal{X}},\delta)$

8: if $\mathsf{UnconstrainedInf}(j,{\mathcal{E}},{\mathcal{X}})$ then

9: $\mathsf{inf}(j)\leftarrow\lambda(j)$

10: if $\lambda(j)={-}\infty$ then

11: $\mathbb{E}_{j}\equiv({-}\infty,\mathsf{sup}(j)]$

12: else

13:
$\mathsf{inf}(j)\leftarrow\mathsf{ExpandInf}(j,{\mathcal{E}},{\mathcal{X}},\delta)$

14: return $\mathbb{E}_{j}$

Algorithm 3 Inflate ordinal feature

Algorithm 3 summarizes the algorithm for inflating a given ordinal feature
$j\in{\mathcal{X}}$. With the purpose of assessing the largest and smallest
possible values for feature $j$, we initially check whether the geature can
take its upper bound $\mu(j)$ (or can be unbounded when $\mu(j)={+}\infty$),
and later check whether the feature can take its lower bound. (Evidently, no
feature $j$ in ${\mathcal{X}}$ can be allowed to take any value between its
lower and upper bounds; since the feature $j$ is included in the AXp, then it
cannot be allowed to take any value in its domain.) If the feature is
unconstrained for either its largest or smallest value, then $\mathbb{E}_{j}$
is updated accordingly (with the case of ${+}\infty$/${-}\infty$ being handled
differently). Otherwise, we seek to inflate $\mathbb{E}_{j}$, either by
increasing values or by decreasing values. The search for increasing values is
illustrated by Algorithm 4, and the search for decreasing values is
illustrated by Algorithm 5. For simplicity, the algorithms implement a
(simple) linear search, using only the value of precision $\delta$ for
approximating the solution. If $\delta$ is small this is inefficient. A simple
improvement consists in using two positive values, $\beta$ and $\delta$, where
(the larger) $\beta$ is used for a rough approximation of the solution, and
(the smaller) $\delta$ is then used to refine the coarser approximation
obtained with $\beta$. Moreover, assuming the upper (or lower) bound is
finite, then standard binary search can be used. If the upper (or lower) bound
is infinite, and not constrained, then one can use exponential (binary)
search111Exponential binary search is a common algorithm for finding a value
when the domain is unbounded Bentley and Yao (1976), which is guaranteed to
terminate if one knows that the target value exists, and given some value of
precision. , with a subsequent binary search step to zoom in on the largest
(or smallest) value of the feature’s values that guarantee sufficiency for the
prediction.

Input: Feature $j$, ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$, AXp
${\mathcal{X}}\subseteq{\mathcal{F}}$, Precision $\delta$

1:function $\mathsf{expandSup}$($j,{\mathcal{E}},{\mathcal{X}},\delta$)

2: while true do

3: $\mathsf{sup}(j)\leftarrow\mathsf{sup}(j)+\delta$

4: if (4) does not hold then

5: $\mathsf{sup}(j)\leftarrow\mathsf{sup}(j)-\delta$

6: return $\mathsf{sup}(j)$

Algorithm 4 Expanding the supremum with linear search

Input: Feature $j$, ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$, AXp
${\mathcal{X}}\subseteq{\mathcal{F}}$, Precision $\delta$

1:function $\mathsf{expandInf}$($j,{\mathcal{E}},{\mathcal{X}},\delta$)

2: while true do

3: $\mathsf{inf}(j)\leftarrow\mathsf{inf}(j)-\delta$

4: if (4) does not hold then

5: $\mathsf{inf}(j)\leftarrow\mathsf{inf}(j)+\delta$

6: return $\mathsf{inf}(j)$

Algorithm 5 Expanding the infimum with linear search

######  Example 9.

For the example monotonic classifier (see Example 1), with instance
$((5,10,5,8),B)$, the computed AXp is $\\{1,2,4\\}$. Let $\delta=0.2$. We
illustrate the execution of Algorithm 3,

in the concrete case where we increase the maximum value that $Q$ (i.e.
feature 1) can take such that the prediction does not change. Since the
classifier is monotonically increasing, we can fix $H$ to 10\. The value of
$X$ is set to 10 and $R$ is set to 8. Clearly, $Q$ cannot take value 10;
otherwise the prediction would become $A$. By iteratively increasing the
largest possible value for $Q$, with increments of $\delta$ (see Algorithm 4),
we conclude that $Q$ can increase up to 6.6 while ensuring that the prediction
does not change to $A$. If $Q$ were assigned value 6.8 (the next $\delta$
increment), the prediction would change to $A$. In terms of the smallest value
that can be assigned to $Q$, we assign $H$ to 0. In this case, we conclude
that $Q$ can take the (lower bound) value of 0, because $R=8$. Hence, feature
$Q$ can take values in the range $[0,6.6]$. Finally, in the case of $R$, its
value cannot get to 9, since otherwise the prediction would become $A$. Hence,
the value of $R$ before considering 9 is 8.8 (see Example 5). In terms of the
smallest possible value for $R$, it is clear that its value cannot be less
than 7, as this would serve to change the prediction. Hence, feature $R$ can
take values in the range $[7,8.8]$. Given the above, the rule associated with
the inflated AXp is:

$\textnormal{IF}~{}[{Q}\in[0,6.6]\land{R}\in[7,8.8]]~{}\textnormal{THEN}~{}[\kappa(\mathbf{x})=B]$

####  3.2.3 Ordinal Features and Tree-based models

Tree-based machine learning models such as decision trees, random forest, and
boosted trees allow a simpler treatment of ordinal features $j$ since the
trees will only compare to a finite set of feature values
$V_{j}\subset\mathbb{D}_{j}$, we assume with comparison $x_{j}\geq d,d\in
V_{j}$. Let $[d_{1},\ldots,d_{m}]$ be the $V_{j}$ is sorted order. We can
construct disjoint intervals, given by $I_{1}=[\min(\mathbb{D}_{j}),d_{1})$,
$I_{2}=[d_{1},d_{2})$, …, $I_{m+1}=[d_{m},\max(\mathbb{D}_{j})]$. By
construction no two values in any interval can be treated differently by the
tree-base model, hence we can use these intervals as a finite categorical
representation of the feature $j$.

###  3.3 Complexity of Inflated Explanations

As can be concluded from the algorithms described in the previous section,
sufficiency for prediction is checked using Equation 4, which mimics the
oracle call for finding the AXp. Nevertheless, inflated explanations require a
number of calls to Equation 4 that grows with the number of values in the
features domains (for categorical features), or the computed supremum (or the
infimum) divided by $\delta$, for categorical features when linear search is
used. (The analysis for (unbounded) binary search is beyond the goals of the
paper.)

##  4 Inflated Contrastive Explanations & Duality

This section investigates the differences that must be accounted for in the
case of contrastive explanations.

###  4.1 Plain Inflated CXp’s & MHS Duality

In contrast with AXp’s, in the case of CXp’s inflation takes place in the
features _not_ in the explanation, i.e. in the features whose value remains
fixed.

As with AXp’s, we propose a modification to the definition of CXp, as follows:

$\exists(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{j\in{\mathcal{F}}\setminus{\mathcal{Y}}}(x_{j}\in\mathbb{E}_{j})\right]\land(\kappa(\mathbf{x})\not=c)$
(5)

Minimal hitting set duality between inflated AXp’s and inflated CXp’s is
immediate and follows from the duality result relating AXp’s and CXp’s
Ignatiev et al. (2020). To motivate the argument, let us define the following
sets:

$\displaystyle\mathbb{A}({\mathcal{E}})$
$\displaystyle=\\{{\mathcal{X}}\subseteq{\mathcal{F}}\,|\,\mathsf{AXp}({\mathcal{X}})\\}$
(6) $\displaystyle\mathbb{C}({\mathcal{E}})$
$\displaystyle=\\{{\mathcal{X}}\subseteq{\mathcal{F}}\,|\,\mathsf{CXp}({\mathcal{Y}})\\}$
(7)

Given the discussion above, the following result follows:

######  Proposition 1.

$\mathbb{A}({\mathcal{E}})$ and $\mathbb{C}({\mathcal{E}})$ remain unchanged
for inflated explanations.

Given Proposition 1 and from earlier work Ignatiev et al. (2020), it follows
that inflated AXp’s and minimal hitting sets of the set of CXp’s and vice-
versa.

Nevertheless, and in contrast with (4), (5) is a weaker definition that the
original definition of CXp. The next section proposes a stronger definition of
CXp.

###  4.2 Generalized CXp’s & Extended Duality

Due to the use of sets $\mathbb{E}_{j}\subset\mathbb{D}_{j}$ instead of
concrete feature-values $v_{j}\in\mathbb{D}_{j}$, the straightforward
definition of inflated contrastive explanations above provides a weaker
explanation, than the uninflated definition (3). Nevertheless, it allows us to
establish a simple minimal hitting set duality between inflated AXp’s and
inflated CXp’s by building directly on Ignatiev et al. (2020). In particular,
each inflated CXp is a minimal hitting set of all the inflated AXp’s and vice
versa, in the sense that given the set of all inflated AXp’s (resp. inflated
CXp’s), an uninflated CXp (resp. uninflated AXp) can be constructed by this
duality and then inflated afterwards. Note that this _set-wise_ duality
requires us to first reconstruct uninflated “versions” of the dual
explanations and only then inflate them. We can define a stronger form of
inflated contrastive explanation as follows, which will enable us to construct
inflated CXp’s (resp. inflated AXp’s) directly from inflated AXp’s (resp.
inflated CXp’s). Namely, given an instance $(\mathbf{v},c)$ and an inflated
CXp is a pair $({\mathcal{Y}},\mathbb{Y})$ s.t $\mathbb{Y}$ is a set of pairs
$(j,\mathbb{G}_{j})$ for each feature $j\in{\mathcal{Y}}$, such that the
following holds:

$\exists(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{j\in{\mathcal{F}}\setminus{\mathcal{Y}}}(x_{j}=v_{j})\land\bigwedge_{j\in{\mathcal{Y}}}(x_{j}\in\mathbb{G}_{j})\right]\land(\kappa(\mathbf{x})\not=c)$
(8)

Note that we can assume $v_{j}\not\in\mathbb{G}_{j},j\in{\mathcal{Y}}$ since
otherwise we could eliminate $j$ from ${\mathcal{Y}}$ and have a tighter
contrastive explanation. Also, observe that in contrast to (3), Equation (8)
considers each of the features $j\in{\mathcal{Y}}$ to belong to some set
$\mathbb{G}_{j}\subset\mathbb{D}_{j}$ rather than assuming them to be free.

The algorithms proposed in Section 3 can be adapted for inflating CXp’s by
checking whether (8) holds instead of (4). An immediate observation here is
that these algorithms would need to be updated such that given a feature
$j\in{\mathcal{Y}}$, we need to _shrink_ the set of allowed values starting
from $\mathbb{D}_{j}$ rather than inflating it starting from $\\{v_{j}\\}$,
which was the case for inflated AXp’s.

In order to facilitate the duality relationship between inflated AXp’s and
inflated CXp’s, observe that given an instance $(\mathbf{v},c)$, an inflated
AXp $({\mathcal{X}},\mathbb{X})$, as defined in (4), can be equivalently
reformulated as follows:

$\forall(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{j\in{\mathcal{X}}}(x_{j}\in\mathbb{E}_{j})\wedge\bigwedge_{j\in{\mathcal{F}}\setminus{\mathcal{X}}}x_{j}\in\mathbb{D}_{j}\right]\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$
(9)

In other words, simply let $\mathbb{E}_{j}=\mathbb{D}_{j}$ for all
$j\not\in{\mathcal{X}}$. Similarly, given an instance $(\mathbf{v},c)$, an
inflated CXp $({\mathcal{Y}},\mathbb{Y})$, s.t. $\mathbb{Y}$ is a set of pairs
$(j,\mathbb{G}_{j})$, can be reformulated such as the following holds:

$\exists(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{j\in{\mathcal{F}}\setminus{\mathcal{Y}}}(x_{j}\in\\{v_{j}\\})\land\bigwedge_{j\in{\mathcal{Y}}}(x_{j}\in\mathbb{G}_{j})\right]\land(\kappa(\mathbf{x})\not=c)$
(10)

In other words, $\mathbb{G}_{j}=\\{v_{j}\\}$ for all $j\not\in{\mathcal{Y}}$.

######  Proposition 2.

Given an explanation problem ${\mathcal{E}}$, let
$\mathbb{A}^{\prime}({\mathcal{E}})$ denote the set of all iAXps
$({\mathcal{X}},\mathbb{X})$ while $\mathbb{C}^{\prime}({\mathcal{E}})$ denote
the set of all iCXps $({\mathcal{Y}},\mathbb{Y})$. Then each iAXp
$({\mathcal{X}},\mathbb{X})\in\mathbb{A}^{\prime}({\mathcal{E}})$ minimally
“hits” each iCXp
$({\mathcal{Y}},\mathbb{Y})\in\mathbb{C}^{\prime}({\mathcal{E}})$ s.t. if
feature $j\in{\mathcal{F}}$ is selected to “hit” iAXp
$({\mathcal{X}},\mathbb{X})$ then
$\mathbb{G}_{j}\cap\mathbb{E}_{j}=\emptyset$, and vice versa.

###### Proof.

Suppose given an iAXp $({\mathcal{X}},\mathbb{X})$ and a iCXp
$({\mathcal{Y}},\mathbb{Y})$, feature $j\in{\mathcal{F}}$ is selected to hit
the CXp such that $\mathbb{G}_{j}\cap\mathbb{E}_{j}\neq\emptyset$. Then we
have a contradiction. Indeed, we can extract an instance
$\mathbf{v^{\prime}}=(v^{\prime}_{1},\ldots,v^{\prime}_{m})$ s.t.
$v_{j}^{\prime}\in\mathbb{G}_{j}\cap\mathbb{E}_{j}$ satisfying Equation (10),
with class $\kappa(\mathbf{v^{\prime}})\neq c$, which by definition (9)
violates the iAXp condition since
$v^{\prime}_{j}\in\mathbb{G}_{j}\cap\mathbb{E}_{j}$. ∎

Given the above proposition, we can construct inflated CXp’s from inflated
AXp’s as follows. Given a complete set $\mathbb{A}^{\prime}({\mathcal{E}})$ of
inflated AXp’s, we select one feature $\theta({\mathcal{X}})\in{\mathcal{X}}$
in the features for explanation $({\mathcal{X}},\mathbb{X})$ and construct an
inflated CXp defined by subset of features
${\mathcal{Y}}=\\{\theta({\mathcal{X}})~{}|~{}({\mathcal{X}},\mathbb{X})\in\mathbb{A}^{\prime}({\mathcal{E}})\\}$
and
$\mathbb{G}_{j}=\bigcap_{({\mathcal{X,\mathbb{X}}})\in\mathbb{A}^{\prime}({\mathcal{E}}),\theta({\mathcal{X}})=j}(\mathbb{D}_{j}\setminus\mathbb{E}_{j}^{\mathcal{X}})$.
Similarly, given a complete set $\mathbb{C}^{\prime}({\mathcal{E}})$ of
inflated CXp’s, we can construct an inflated AXp, by selecting one feature
$\phi({\mathcal{Y}})\in{\mathcal{Y}}$ from each CXp
$({\mathcal{Y}},\mathbb{Y})$, and defining
${\mathcal{X}}=\\{\phi({\mathcal{Y}})~{}|~{}{\mathcal{Y}}\in\mathbb{C}^{\prime}({\mathcal{E}})\\}$
and
$\mathbb{E}_{j}=\bigcap_{({\mathcal{Y,\mathbb{Y}}})\in\mathbb{C}^{\prime}({\mathcal{E}}),\phi({\mathcal{Y}})=j}(\mathbb{D}_{j}\setminus\mathbb{G}_{j}^{\mathcal{Y}})$.
Note that the key difficulty here is to organize efficient _minimal_ selection
of features used to “hit” the given set of explanations (either
$\mathbb{A}^{\prime}({\mathcal{E}})$ or $\mathbb{C}^{\prime}({\mathcal{E}})$).
In various settings of minimal hitting set duality Ignatiev et al. (2020),
this is typically done by invoking a modern mixed-integer linear programming
(MILP) or maximum satisfiability (MaxSAT) solver. Similar ideas can be applied
in this case as well.

##  5 Experiments

Dataset | (m, K) | RF | AXp | Inflated AXp
---|---|---|---|---
D |  #N |  %A |  Len  |  Time  |  m  |  M  |  avg  |  Time
adult | $(12$ | $2)$ | $8$ | $21526$ | $76$ | $5.6$ | $0.19$ | $0$ | $26$ | $7.0$ | $0.40$
ann-thyroid | $(21$ | $3)$ | $4$ | $2192$ | $96$ | $1.7$ | $0.20$ | $6$ | $129$ | $15.8$ | $0.41$
appendicitis | $(7$ | $2)$ | $6$ | $1920$ | $90$ | $3.7$ | $0.05$ | $13$ | $140$ | $54.2$ | $0.33$
banknote | $(4$ | $2)$ | $5$ | $2772$ | $98$ | $2.2$ | $0.05$ | $16$ | $351$ | $156.6$ | $0.22$
biodegradation | $(41$ | $2)$ | $5$ | $4420$ | $88$ | $16.7$ | $0.33$ | $47$ | $611$ | $273.1$ | $6.46$
ecoli | $(7$ | $5)$ | $5$ | $3860$ | $90$ | $3.6$ | $0.20$ | $48$ | $242$ | $128.4$ | $1.39$
german | $(21$ | $2)$ | $8$ | $13332$ | $74$ | $12.3$ | $0.36$ | $7$ | $435$ | $149.0$ | $4.20$
glass2 | $(9$ | $2)$ | $6$ | $2966$ | $84$ | $4.6$ | $0.07$ | $6$ | $263$ | $92.9$ | $0.41$
heart-c | $(13$ | $2)$ | $5$ | $3910$ | $83$ | $5.5$ | $0.07$ | $9$ | $207$ | $89.1$ | $0.23$
ionosphere | $(34$ | $2)$ | $5$ | $2096$ | $85$ | $21.5$ | $0.06$ | $16$ | $352$ | $193.5$ | $0.27$
iris | $(4$ | $3)$ | $6$ | $1446$ | $93$ | $2.2$ | $0.11$ | $14$ | $48$ | $20.7$ | $0.15$
karhunen | $(64$ | $10)$ | $5$ | $6198$ | $92$ | $34.8$ | $3.07$ | $215$ | $650$ | $392.4$ | $17.14$
lending | $(9$ | $2)$ | $5$ | $5370$ | $75$ | $2.2$ | $0.10$ | $0$ | $6$ | $1.7$ | $0.14$
magic | $(10$ | $2)$ | $6$ | $9840$ | $85$ | $6.3$ | $0.25$ | $81$ | $2041$ | $831.7$ | $6.84$
mofn-3-7-10 | $(10$ | $2)$ | $6$ | $8776$ | $91$ | $3.0$ | $0.06$ | $0$ | $0$ | $0.0$ | $0.06$
mushroom | $(22$ | $2)$ | $4$ | $1930$ | $97$ | $9.2$ | $0.07$ | $1$ | $42$ | $14.5$ | $0.15$
new-thyroid | $(5$ | $3)$ | $5$ | $1766$ | $100$ | $2.9$ | $0.12$ | $9$ | $108$ | $60.2$ | $0.40$
pendigits | $(16$ | $10)$ | $6$ | $12004$ | $96$ | $9.8$ | $1.07$ | $89$ | $569$ | $281.0$ | $12.50$
phoneme | $(5$ | $2)$ | $6$ | $8962$ | $83$ | $3.0$ | $0.18$ | $151$ | $1765$ | $582.5$ | $2.62$
promoters | $(57$ | $2)$ | $3$ | $1214$ | $90$ | $25.0$ | $0.05$ | $13$ | $38$ | $23.0$ | $0.12$
recidivism | $(15$ | $2)$ | $10$ | $75204$ | $61$ | $7.9$ | $0.48$ | $0$ | $6$ | $2.2$ | $0.53$
ring | $(20$ | $2)$ | $6$ | $6188$ | $90$ | $9.6$ | $0.35$ | $14$ | $1639$ | $720.5$ | $1.35$
segmentation | $(19$ | $7)$ | $4$ | $1966$ | $90$ | $8.1$ | $0.39$ | $19$ | $149$ | $59.7$ | $1.99$
shuttle | $(9$ | $7)$ | $3$ | $1460$ | $99$ | $2.3$ | $0.22$ | $7$ | $50$ | $19.8$ | $0.42$
sonar | $(60$ | $2)$ | $5$ | $2614$ | $88$ | $35.9$ | $0.11$ | $152$ | $327$ | $242.8$ | $4.10$
soybean | $(35$ | $18)$ | $5$ | $4460$ | $87$ | $15.6$ | $2.05$ | $4$ | $35$ | $13.1$ | $3.39$
spambase | $(57$ | $2)$ | $5$ | $4614$ | $92$ | $18.9$ | $0.15$ | $57$ | $516$ | $211.6$ | $0.94$
spectf | $(44$ | $2)$ | $5$ | $2306$ | $87$ | $19.7$ | $0.10$ | $11$ | $221$ | $108.9$ | $2.11$
texture | $(40$ | $11)$ | $5$ | $5724$ | $89$ | $22.8$ | $1.06$ | $70$ | $834$ | $338.4$ | $13.19$
threeOf9 | $(9$ | $2)$ | $3$ | $920$ | $100$ | $1.0$ | $0.02$ | $0$ | $0$ | $0.0$ | $0.02$
twonorm | $(20$ | $2)$ | $3$ | $1500$ | $92$ | $10.4$ | $0.05$ | $17$ | $248$ | $99.2$ | $0.15$
vowel | $(13$ | $11)$ | $6$ | $10176$ | $91$ | $7.7$ | $1.28$ | $70$ | $862$ | $401.5$ | $28.05$
waveform-21 | $(21$ | $3)$ | $5$ | $6238$ | $84$ | $9.6$ | $0.50$ | $81$ | $1026$ | $373.6$ | $6.28$
waveform-40 | $(40$ | $3)$ | $5$ | $6232$ | $84$ | $14.5$ | $0.90$ | $73$ | $975$ | $365.0$ | $8.21$
wdbc | $(30$ | $2)$ | $4$ | $2028$ | $94$ | $11.9$ | $0.08$ | $56$ | $274$ | $119.8$ | $0.45$
wine-recog | $(13$ | $3)$ | $3$ | $1188$ | $97$ | $4.5$ | $0.15$ | $10$ | $112$ | $39.0$ | $0.35$
wpbc | $(33$ | $2)$ | $5$ | $2432$ | $76$ | $19.9$ | $0.80$ | $89$ | $429$ | $211.2$ | $144.48$
xd6 | $(9$ | $2)$ | $6$ | $8288$ | $100$ | $3.0$ | $0.07$ | $0$ | $0$ | $0.0$ | $0.06$

Table 1: Detailed performance evaluation of delivering inflated AXp’s for RFs.
The table shows results for 38 datasets, which contain categorical and ordinal
data. Columns m and K report, respectively, the number of features and classes
in the dataset. Columns D, #N and %A show, respectively, each tree’s max.
depth, total number of nodes and test accuracy of an RF classifier. Column Len
reports the average explanation length (i.e. average number of features
contained in the explanations). Column Time shows the average runtime for
extracting an explanation. Column avg (resp. m and M) reports the average
number of values/intervals (for categorical /continuous domain) computed in
the expansion of $\mathbb{E}_{j}$ for the inflated AXp.

This section presents a summary of empirical assessment of computing inflated
abductive explanations for the case study of RF classifiers trained on some of
the widely studied datasets.

##### Experimental setup.

The experiments are conducted on a MacBook Pro with a Dual-Core Intel Core i5
2.3GHz CPU with 8GByte RAM running macOS Ventura. The results reported do not
impose any time or memory limit.

##### Benchmarks.

The assessment is performed on a selection of 38 publicly available datasets,
which originate from UCI Machine Learning Repository UCI (2020) and Penn
Machine Learning Benchmarks Olson et al. (2017). The benchmarks comprise
binary and multidimensional classification datasets and include ordinal and
categorical datasets. (Categorical features are encoded into OHE data and
handled as a group of attributes representing their original features when
computing the explanations.) The number of classes in the benchmark suite
varies from 2 to 18. The number of features varies from 4 to 64 with the
average being 22.5 (resp. 5131.09). When training RF classifiers for the
selected datasets, we used 80% of the dataset instances (20% used for test
data). For assessing explanation tools, we randomly picked fractions of the
dataset, depending on the dataset size. The scikit-learn toolkit Pedregosa and
et al. (2011) was used to train the models. The number of trees in each
learned model is set to 100, while tree depth varies between 3 and 10. As a
result, the accuracy of the trained models varies between 61% to 100%.
Besides, our formal explainers are set to compute a single AXp and then apply
the inflation method, per data instance from the selected set of instances and
200 samples are randomly to be tested for each dataset.

##### Prototypes implementation.

We developed a reasoner for RFs as Python script222The Python code is publicly
available on https://github.com/yizza91/RFxpl. The script implements the SAT-
based encoding of RFs proposed in Izza and Marques-Silva (2021), and the
outlined algorithms (Algorithms 1, 2, 3, 4 and 5) in order to compute inflated
AXp’s. Also, the prototype can serve to compute first an AXp, if this one was
not provided in the inputs, and then generate an inflated explanation.
Furthermore, PySAT Ignatiev et al. (2018) is used to generate the CNF formulas
and cardinality constraints in a clausal form to encode the classifier.
Afterwards, PySAT is used to instrument incremental calls to the Glucose3
Audemard and Simon (2018) SAT solver when computing explanations.

##### Results.

Table 1 summarizes the results of computing inflated AXp’s for RFs on the
selected datasets. As can be observed from the results, and with three
exceptions, our method succeeds in expanding all individual set
$\mathbb{E}_{i}$ of features involved in the AXp. Moreover, we observe that
for 20 out of 38 datasets, the average increase in sub-domain $\mathbb{E}_{i}$
varies between 100 and 720, and for 13 over 38 datasets this number varies
between 13 to 99. In terms of performance, the results clearly demonstrate
that our approach scales to (realistically) large data and large tree
ensembles considered in the assessment. It is plain to see that for most
datasets the proposed method takes a few seconds on average to deliver an
inflated AXp, thus the average (resp. minimum and maximum) runtime for all
datasets is 7.11 seconds (resp. 0.02 and 144.48 seconds). Even though a few
outliers were observed in continuous data where the number of splits
(intervals) generated by the trees is fairly large, this does not contrast the
effectiveness of our technique since the largest running time that could be
registered is less than 2.30 minutes. As results, our extensive evaluation
performed on a large range of real world data and RFs of large sizes, allows
us to conclude that our solution is effective in practice to produce more
expressive explanations than standard AXp’s and more importantly in a short
time.

##  6 Conclusions

One limitation of logic-based explanations, either abductive or contrastive
explanations, is that these are based on fairly restricted literals, of the
form $x_{i}=v_{i}$. This paper formalizes the concept of _inflated
explanation_ , which can be considered either in the case of abductive or
contrastive explanations. Furthermore, the paper proposes algorithms for the
rigorous computation of inflated explanations, and demonstrates the existence
of minimal hitting set duality between inflated abductive and inflated
contrastive explanations. The experimental results validate the practical
interest of computing inflated explanations.

## References

  * Amgoud and Ben-Naim (2022) Leila Amgoud and Jonathan Ben-Naim.  Axiomatic foundations of explainability.  In IJCAI, pages 636–642, 2022.
  * Amgoud (2021) Leila Amgoud.  Non-monotonic explanation functions.  In ECSQARU, pages 19–31, 2021.
  * Amgoud (2023) Leila Amgoud.  Explaining black-box classifiers: Properties and functions.  Int. J. Approx. Reason., 155:40–65, 2023.
  * Arenas et al. (2022) Marcelo Arenas, Pablo Barceló, Miguel Romero, and Bernardo Subercaseaux.  On computing probabilistic explanations for decision trees.  In NeurIPS, 2022.
  * Audemard and Simon (2018) Gilles Audemard and Laurent Simon.  On the glucose SAT solver.  Int. J. Artif. Intell. Tools, 27(1):1840001:1–1840001:25, 2018\.
  * Audemard et al. (2020) Gilles Audemard, Frédéric Koriche, and Pierre Marquis.  On tractable XAI queries based on compiled representations.  In KR, pages 838–849, 2020.
  * Audemard et al. (2021) Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis.  On the computational intelligibility of boolean classifiers.  In KR, pages 74–86, 2021.
  * Audemard et al. (2022) Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis.  On the explanatory power of boolean decision trees.  Data Knowl. Eng., 142:102088, 2022.
  * Bach et al. (2015) Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek.  On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.  PloS one, 10(7):e0130140, 2015.
  * Bassan and Katz (2023) Shahaf Bassan and Guy Katz.  Towards formal XAI: formally approximate minimal explanations of neural networks.  In TACAS, pages 187–207, 2023.
  * Bentley and Yao (1976) Jon Louis Bentley and Andrew Chi-Chih Yao.  An almost optimal algorithm for unbounded searching.  Inf. Process. Lett., 5(3):82–87, 1976.
  * Boumazouza et al. (2020) Ryma Boumazouza, Fahima Cheikh Alili, Bertrand Mazure, and Karim Tabia.  A symbolic approach for counterfactual explanations.  In SUM, pages 270–277, 2020.
  * Boumazouza et al. (2021) Ryma Boumazouza, Fahima Cheikh Alili, Bertrand Mazure, and Karim Tabia.  ASTERYX: A model-agnostic sat-based approach for symbolic and score-based explanations.  In CIKM, pages 120–129, 2021.
  * Choi et al. (2020) Arthur Choi, Andy Shih, Anchal Goyanka, and Adnan Darwiche.  On symbolically encoding the behavior of random forests.  CoRR, abs/2007.01493, 2020.
  * Cooper and Marques-Silva (2021) Martin C. Cooper and Joao Marques-Silva.  On the tractability of explaining decisions of classifiers.  In CP, pages 21:1–21:18, 2021.
  * Cooper and Marques-Silva (2023) Martin C. Cooper and Joao Marques-Silva.  Tractability of explaining classifier decisions.  Artif. Intell., 316:103841, 2023.
  * Darwiche and Hirth (2023) Adnan Darwiche and Auguste Hirth.  On the (complete) reasons behind decisions.  J. Log. Lang. Inf., 32(1):63–88, 2023.
  * Dillig et al. (2012) Isil Dillig, Thomas Dillig, Kenneth L. McMillan, and Alex Aiken.  Minimum satisfying assignments for SMT.  In CAV, pages 394–409, 2012.
  * Gorji and Rubin (2022) Niku Gorji and Sasha Rubin.  Sufficient reasons for classifier decisions in the presence of domain constraints.  In AAAI, February 2022.
  * Huang et al. (2021) Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, and João Marques-Silva.  On efficiently explaining graph-based classifiers.  In KR, pages 356–367, 2021.
  * Ignatiev and Marques-Silva (2021) Alexey Ignatiev and Joao Marques-Silva.  SAT-based rigorous explanations for decision lists.  In SAT, pages 251–269, 2021.
  * Ignatiev et al. (2018) Alexey Ignatiev, António Morgado, and Joao Marques-Silva.  PySAT: A python toolkit for prototyping with SAT oracles.  In SAT, pages 428–437, 2018.
  * Ignatiev et al. (2019) Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva.  Abduction-based explanations for machine learning models.  In AAAI, pages 1511–1519, 2019.
  * Ignatiev et al. (2020) Alexey Ignatiev, Nina Narodytska, Nicholas Asher, and Joao Marques-Silva.  From contrastive to abductive explanations and back again.  In AIxIA, pages 335–355, 2020.
  * Ignatiev (2020) Alexey Ignatiev.  Towards trustable explainable AI.  In IJCAI, pages 5154–5158, 2020.
  * Izza and Marques-Silva (2021) Yacine Izza and Joao Marques-Silva.  On explaining random forests with SAT.  In IJCAI, pages 2584–2591, 2021.
  * Izza et al. (2022) Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva.  On tackling explanation redundancy in decision trees.  J. Artif. Intell. Res., 75:261–321, 2022.
  * Ji and Darwiche (2023) Chunxi Ji and Adnan Darwiche.  A new class of explanations for classifiers with non-binary features.  CoRR, abs/2304.14760, 2023.
  * Liu and Lorini (2022) Xinghan Liu and Emiliano Lorini.  A logic of ”black box” classifier systems.  In WoLLIC, pages 158–174, 2022.
  * Liu and Lorini (2023) Xinghan Liu and Emiliano Lorini.  A unified logical framework for explanations in classifier systems.  J. Log. Comput., 33(2):485–515, 2023.
  * Lundberg and Lee (2017) Scott M. Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In NeurIPS, pages 4765–4774, 2017.
  * Malfa et al. (2021) Emanuele La Malfa, Rhiannon Michelmore, Agnieszka M. Zbrzezny, Nicola Paoletti, and Marta Kwiatkowska.  On guaranteed optimal robust explanations for NLP models.  In IJCAI, pages 2658–2665, 2021.
  * Marques-Silva and Ignatiev (2022) Joao Marques-Silva and Alexey Ignatiev.  Delivering trustworthy AI through formal XAI.  In AAAI, pages 12342–12350, 2022.
  * Marques-Silva et al. (2021) Joao Marques-Silva, Thomas Gerspacher, Martin C. Cooper, Alexey Ignatiev, and Nina Narodytska.  Explanations for monotonic classifiers.  In ICML, pages 7469–7479, 2021.
  * Marques-Silva (2022) João Marques-Silva.  Logic-based explainability in machine learning.  CoRR, abs/2211.00541, 2022.
  * Miller (2019) Tim Miller.  Explanation in artificial intelligence: Insights from the social sciences.  Artif. Intell., 267:1–38, 2019.
  * Molnar (2020) Christoph Molnar.  Interpretable Machine Learning.  Leanpub, 2020.  http://tiny.cc/6c76tz.
  * Olson et al. (2017) Randal S. Olson, William La Cava, Patryk Orzechowski, Ryan J. Urbanowicz, and Jason H. Moore.  PMLB: a large benchmark suite for machine learning evaluation and comparison.  BioData Mining, 10(1):36, 2017.
  * Pedregosa and et al. (2011) Fabian Pedregosa and et al.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * Ribeiro et al. (2016) Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin.  ”why should I trust you?”: Explaining the predictions of any classifier.  In KDD, pages 1135–1144, 2016.
  * Ribeiro et al. (2018) Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin.  Anchors: High-precision model-agnostic explanations.  In AAAI, pages 1527–1535, 2018.
  * Rudin et al. (2022) Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong.  Interpretable machine learning: Fundamental principles and 10 grand challenges.  Statistics Surveys, 16:1–85, 2022.
  * Rudin (2019) Cynthia Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 1(5):206–215, 2019.
  * Samek and Müller (2019) Wojciech Samek and Klaus-Robert Müller.  Towards explainable artificial intelligence.  In Samek et al. Samek et al. (2019), pages 5–22.
  * Samek et al. (2019) Wojciech Samek, Grégoire Montavon, Andrea Vedaldi, Lars Kai Hansen, and Klaus-Robert Müller, editors.  Explainable AI: Interpreting, Explaining and Visualizing Deep Learning.  Springer, 2019.
  * Samek et al. (2021) 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.
  * Seshia et al. (2022) Sanjit A. Seshia, Dorsa Sadigh, and S. Shankar Sastry.  Toward verified artificial intelligence.  Commun. ACM, 65(7):46–55, 2022.
  * Shih et al. (2018) Andy Shih, Arthur Choi, and Adnan Darwiche.  A symbolic approach to explaining bayesian network classifiers.  In IJCAI, pages 5103–5111, 2018.
  * UCI (2020) UCI Machine Learning Repository.  https://archive.ics.uci.edu/ml, 2020.
  * Wäldchen et al. (2021) Stephan Wäldchen, Jan MacDonald, Sascha Hauch, and Gitta Kutyniok.  The computational complexity of understanding binary classifier decisions.  J. Artif. Intell. Res., 70:351–387, 2021.


# Pig aggression classification using CNN, Transformers and Recurrent Networks

Junior Silva Souza<EMAIL_ADDRESS>Eduardo Bedin<EMAIL_ADDRESS>Gabriel Toshio Hirokawa Higa<EMAIL_ADDRESS>Newton Loebens
<EMAIL_ADDRESS>Hemerson Pistori<EMAIL_ADDRESS>
###### Abstract

The development of techniques that can be used to analyze and detect animal
behavior is a crucial activity for the livestock sector, as it is possible to
monitor the stress and animal welfare and contributes to decision making in
the farm. Thus, the development of applications can assist breeders in making
decisions to improve production performance and reduce costs, once the animal
behavior is analyzed by humans and this can lead to susceptible errors and
time consumption. Aggressiveness in pigs is an example of behavior that is
studied to reduce its impact through animal classification and identification.
However, this process is laborious and susceptible to errors, which can be
reduced through automation by visually classifying videos captured in
controlled environment. The captured videos can be used for training and, as a
result, for classification through computer vision and artificial
intelligence, employing neural network techniques. The main techniques
utilized in this study are variants of transformers: STAM, TimeSformer, and
ViViT, as well as techniques using convolutions, such as ResNet3D2,
Resnet(2+1)D, and CnnLstm. These techniques were employed for pig video
classification with the objective of identifying aggressive and non-aggressive
behaviors. In this work, various techniques were compared to analyze the
contribution of using transformers, in addition to the effectiveness of the
convolution technique in video classification. The performance was evaluated
using accuracy, precision, and recall. The TimerSformer technique showed the
best results in video classification, with median accuracy of 0.729.

###### keywords:

aggressiveness , Video Classification , Transformers , Convolutional

††journal: Computers and Electronics in Agriculture

##  1 Introduction

The increasing worldwide demand for protein in the last years has led pig
farms to expand. This expansion has been financed by companies that aim at
large scale production to supply the market. In the context of livestock
farming, abnormal animal behavior stemming from stress factors due to the
environment is one factor that can indicate issues and must be noticed in
order to maintain high production levels [19]. Some of the behaviors that
require attention are aggressiveness, feeding and mounting. Animal behavior
monitoring is usually done manually, and require not only technical knowledge,
but also experience. It is, therefore, a highly error-prone task [1]. Given
the many difficulties involved in this task, the application of technological
solutions to monitor animal behavior has been increasing in recent years [27].

The development of deep learning-based computer vision techniques in the last
decade has opened new possibilities for automating tasks related to many kinds
of problems, including classification, detection and object tracking. Most
relevantly, of course, it has also opened new possibilities for the
development of applications aimed at, for example, tracking animals in groups,
such as in the work of Xu et al. [36]. In swine farming, cameras can be used
to capture images or videos, which can then be processed in order to identify
abnormalities [24].

There are important differences between images and videos, as regards the data
and information captured. By using videos, it is possible to obtain
information about events that occur over a period of time (as opposed to
events occurring in a given instant), which can indicate desirable or
undesirable behavioral characteristics in swines that occurs in short time
span. Among the undesirable behaviors, aggressiveness is one that cannot be
easily identified by image analysis alone. In such cases, analyzing videos can
yield better results by providing temporal information [35].

The fundamental idea of this paper, therefore, is that aggressive behavior can
be identified using both spacial information (extracted from individual
frames) and temporal information (extracted from sequences of frames), that
is, aggressive behavior can be classified through automated video analysis
with neural networks. With this hypothesis in mind, this work evaluates video
classification techniques applied to the task. More specifically, it evaluates
models based on transformers for video processing: Visual Vision Transformer
(ViViT), Space Time Attention Model (STAM) and TimeSformer, along with a
Convolutional Neural Network (CNN) with Recurrent Neural Network (RNN),
ResNet3D and Resnet(2+1)D.

The contribution of this work lies in the creation of a dataset containing
videos depicting both aggressive and non-aggressive behaviors, collected
within a local commercial breeding environment. Additionally, it proposes the
automated classification of aggressive behavior, specifically those occurring
in commercial breeding contexts, utilizing computer vision techniques such as
convolution, recurrence and transformers for video classification. In this
manner, a comparative analysis of the performance of these techniques is
conducted, with objective of determined which among them yields superior
results.

##  2 Related Works

The application of deep learning techniques to solve computer vision problems
has allowed the development of high performance techniques for tasks such as
image and video classification, semantic segmentation and object detection.
The application of these new technologies to animal monitoring has already
been the subject of several studies. Some works, such as those by Hansen et
al. [13] and Shigang et al. [29] have noticed the possibility of using images
of pig faces to monitor variables such as welfare and mood, and also as an
auxiliary management tool in general. Going beyond their field, computer
vision techniques have also influenced researches such as that by Liao et al.
[21], that proposes the TransformerCNN model to monitor pigs by processing
their vocal sounds. Hu et al. [15] studied the application of feature pyramid
networks (FPNs) to segment individual pigs. When behavior is specifically
concerned, there are also important works. Kim et al. [18] proposed a system
to recognize feeding behavior using object detection networks, such as YoloV3.
Zhang et al. [39] proposed an algorithm to detect drinking, urination and
mounting behavior in real-time, by processing images generated in a pig pen.
In these cases, the primary focus was on still images. Videos were used as a
way of producing singular images more efficiently, which is a common practice,
since the cameras can be left hanging over the pig pen, or attached to
something, and configured to take videos from which individual frames can be
sampled as pictures.

On the other hand, Zhang et al. [38] used convolutional neural networks to
process videos, in order to identify five behaviors of interest: sleeping,
mounting, lying down, feeding and walking. The proposed approach used optical
flow techniques to extract movement information, and convolutions were applied
in parallel on RGB video frames. The detection and monitoring of animals was
also analyzed by Fernández-Carrión et al. [10], who performed identification
and monitoring by using CNN and Kalman filter for tracking and analyzing boars
afflicted with African swine fever. In this last case, the deep learning
techniques were used as part of another research aiming at proving the point
that this sickness can be identified early by monitoring the movement of the
animals. Another relevant case where deep learning was used within a research
is the work by Chen et al. [6], where the interaction of animals with
enrichment objects was analyzed as a way of reducing aggressive behavior.
Finally,Wang et al. [34] applied a CNN with Long Short-Term Memory (LSTM) to
classify videos of piglets according to their postures. The authors utilized
PCA to select frames, reducing their numbers and facilitating network
training. As stated above, many works use videos to capture still images, and
process still images for information. For many problems, single images are
enough for classification using neural networks. However, these works show
that behavior monitoring can benefit from the extraction of deeper spatial and
temporal information from sequential image data.

There are recent developments in the field of computer vision that may prove
useful for animal behavior monitoring, and have not yet been properly
evaluated. Above all, these are represented by the family of transformer-based
architectures, whose central component is their attention mechanism. The use
of attention in image and video classification allow the implementation of
techniques aimed at highlighting important features present in the data, along
with their relationship [33], [7]. Dosovitskiy et al. [9] proposed to apply
attention concepts to (still) image processing. Then, Li et al. [20] proposed
to expand their application to video processing. Given the current state of
arts, in this work, we present a video dataset with videos of aggressive
behaviors of pigs. Furthermore, it includes an evaluation of transformer-
based, recurrent, and convolutional neural techniques for video
classification, specifically applied to identify instances of aggressive
behavior.”

##  3 Materials and Methods

###  3.1 Video dataset

For this research, a video dataset was collected in a private property in the
state of Mato Grosso do Sul, Brazil. The dataset includes videos of pigs that
were raised as livestock and were between 60 to 180 days old at time of
capture. The images were collected in period from March until July of 2022,
when the mean temperature was 28℃. The videos were captured mostly during the
early morning hours, between 08h00 to 10h00, and the late afternoon hours,
between 13h00 to 16h00, when the animals were more active.

The dataset consists of 421 video clips, of which 143 were annotated as
“Aggressive” and 278 were annotated as “Not Aggressive”. The videos were
captured from a height of 2.6 meters and a distance of 5 meters from each
enclosure, utilizing a fixed diagonal camera position. The camera device used
was a Motorola e(6i) configured to capture frames with a height of 2340 pixels
and a width of 4160 pixels, using the RGB color space at a rate of 30 frames
per second, in recording periods of 39 minutes for each video, which were used
to obtain the clips.

To obtain the dataset, it was necessary to perform a processing of edition
111The editing process was performed using the python programming language and
the OpenCV package. on each video recording. The videos were cut into clips at
the moments when the animals exhibited behavior considered aggressive, as well
as moments when they did not display aggression but were in close proximity.
In Figure 1 we can observe an example of an input video recording composed of
70,200 frames (39 minutes at 30 frames per second), where the manual
classification (aggression or nonaggression) was performed. Furthermore, it is
possible to observe that the image presents a blue tone due to the barn fence
on the side of the enclosure where the animals are housed. This is done to
provide both light and ventilation during the day, a practice adopted by many
local shelters.

Figure 1: In this image, we can visualize the process of classification from
an input video, where clips are obtained.

In Figure 2, We can see an example of three frames that depict two pigs in an
aggressive moment from a clip. The animals involved, pig 1 and pig 2, display
an initial aggression, attempting to bite each other. This is a brief moment
that occurs within a short time interval.

Figure 2: The image shows three sequential frames depicting two instances of
aggression. We can observe more highlighted details in frame three, located on
the right, where the animals are attempting to bite.

The animal behavior, considered non-aggressive, can be observed in Figure 3,
where we can see animals in standing up and animals lying down in normal
conditions.

Figure 3: Image depicting three frames illustrating non-aggressive animal
behavior.

###  3.2 Video preprocessing

Video compression was employed to reduce the number of frames to be processed
by eliminating redundant information from the clips. In the work of Liu et al.
[22], the reduction of frames was analyzed to determine the minimum and
sufficient amount of frames needed for training and classification. This
processing allowed for a reduction of processing during the training.

The reduction of clip frames was accomplished at a 4:1 ratio. As a result,
each sequence of 40 frames was condensed to 10 frames. Besides the
compression, each frame of video was also resized to 400 pixels of height and
400 pixels in width.

###  3.3 Deep Learning

This paper compares the performance of deep neural networks applied to video
classification, including convolutional neural networks (CNNs), recurrent
neural networks (RNNs), and transformers-based neural networks. Convolutional
neural networks, either combined with or without recurrent neural networks,
are considered as alternative approaches for video classification, as
demonstrated in previous works such as Patil et al. [26] and Singh et al.
[30].

To perform the classification of videos using convolutional neural networks,
architectures have been proposed in Tran et al. [32] that utilize the
mechanism of “skip connection ”to handle the problem of vanishing gradients
which can reduce the magnitude of the updates of neurons in training. In order
to work with spacial and temporal information, two architectures have been
developed: ResNet3D and Resnet(2+1)D also referring to as ResNet21D in this
work. ResNet3D performs convolutions in three dimensions to extract both
temporal and spacial information from video frames. On the other hand, the
ResNet(2+1)D architecture performs 2D convolutions followed by 1D
convolutions, extracting spacial and temporal information, respectively.

The use of recurrent neural networks (RNNs) in combination with convolutional
neural networks (CNNs) was also proposed in this work. The network used was
ResNet. The CNN was utilized for extracting features from videos, which
represent spatial information. Meanwhile, the RNN was employed for
classification and extraction of information from frames, representing
temporal information [14].

Transformers are implementations of attention mechanisms developed initially
in the field of natural language processing. They have since been adapted for
use in computer vision in tasks such as image and video classification,
detection and segmentation[5].

In natural language processing, each word is represented in the form of
tokens. However, in computer vision, an image is divided in small parts called
patches, which are used as tokens, and are them used for image classification
using ViT (Vision Transformers).

The ViT introduces the construction of a neural network that uses
transformers, as an adaptation that does not use convolutions [9, 11]. The
tokens are extracted from an image and passed to a transformer encoder which
corresponds to one block of the transformer. One of the differentials of the
transformer is its attention mechanism, specifically the dot product attention
presented in the encoder. The encoders are responsible for extracting
information, which is used by a multilayer perceptron that is responsible for
classification.

The ViViT architecture is an application of ViT in video and image
classification problems. In this architecture, each video is treated as a
sequence of images from which important spatial and temporal information are
extracted for classification purposes. As videos are composed of sequential
images (frames), relevant information can be extracted at each frame change.
Furthermore, each frame in the video can be analyzed by ViT, which extracts
spatial information that is used to extract temporal information. The
architecture ViViT has two stages of application using ViT: The first stage is
applied to each frame from the video and the second stage is applied to the
results from the first stage [3].

The STAM architecture is similar to ViViT. This architecture applies ViT to
extract spatial and temporal information, which gives more efficient
processing while prioritizing the extraction of spatial information before
capturing temporal information. In STAM, 16 frames are selected per video for
processing, as described in [28].

The TimeSformer (Time-Space Transformer) architecture divides each frame of
the video into patches with a size of 16x16, which can be changed to other
sizes such as 32x32, 64x64. This architecture uses ViT to extract spatial and
temporal information from the obtained patches. During processing, only the
patches with more information are selected. The quantity and location of
patches can vary during the processing, which involves the execution of
multiple ViT models. This processing allows the model to focus on the most
important parts of each frame to achieve video classification [4].

###  3.4 Experimental Setup

To conduct the experiments, the dataset was used with a 5-fold cross-
validation [23]. In each run, 20% of the training images were used for
validation. The frames of the videos were resized to $(64,64)$ pixels due to
the limitations of the runtime environment, which used the NVIDIA TITAN Xp
with 12 GB of memory, supporting execution with sizes no larger than that. For
the transformer modules, 32 patches were extracted from each frame. This
initial value is used in works such as [31]. Each architecture was tested with
the following learning rates: 0.0001 and 0.0003, values utilized in different
works, such as that of Islam et al. [16], as well as that of Nasirahmadi et
al. [25]. In this work, the neural networks were optimized with Adam, which
yielded good results in works such as that of Desai [8] and Almadani et al.
[2].

The training was performed for 20 epochs, with batches of size 8, following
the approach by Zhou et al. [40]. The weights were randomly initialized, and
the transfer learning technique was not utilized due to the specific
characteristics of the application domain. At the end of the training phase,
four classification metrics were calculated for the test folds, and the mean
values were obtained for the following metrics: accuracy, precision, recall,
and F-score. Then, these results were evaluated through an ANOVA hypothesis
test, with a significance threshold of 5%. The Scott-Knott clustering test was
used post-hoc, when the ANOVA results were significant.

##  4 Results

The Tables 1, 2, 3, and 4 show the values of accuracy, precision, recall, and
F-score, respectively, using techniques for video classification, analyzed
with one-way ANOVA. The Table columns show the name of the techniques, as well
as the mean, median, and standard deviation (SD) values.

Accuracy metric
---
Technique | Median | Mean (SD)
ViViT | 0.694 | 0.698 (0.056)
STAM | 0.659 | 0.665 (0.016)
TimeSformer | 0.729 |  0.764 (0.083)
CnnLstm | 0.699 | 0.724 (0.092)
Resnet3D | 0.724 | 0.750 (0.107)
Resnet21D | 0.718 | 0.757 (0.111)
Table 1: The results are presented for all techniques using the accuracy
metric. Precision metric
---
Technique (group) | Median | Mean (SD)
ViViT (a) | 0.594 | 0.580 (0.111)
STAM (b) | 0.167 | 0.300 (0.358)
TimeSformer (a) | 0.681 |  0.716 (0.125)
CnnLstm (a) | 0.576 | 0.614 (0.142)
Resnet3D (a) | 0.613 | 0.670 (0.197)
Resnet21D (a) | 0.600 | 0.653 (0.183)
Table 2: The results are presented for all techniques using the precision
metric. Recall metric
---
Technique (group) | Median | Mean (SD)
ViViT (a) | 0.358 | 0.381 (0.129)
STAM (b) | 0.017 | 0.035 (0.046)
TimeSformer (a) | 0.483 | 0.499 (0.207)
CnnLstm (a) | 0.397 | 0.480 (0.189)
Resnet3D (a) | 0.534 | 0.531 (0.187)
Resnet21D (a) | 0.677 |  0.613 (0.225)
Table 3: The results are presented for all techniques using the recall metric.
F-score metric
---
Technique (group) | Median | Mean (SD)
ViViT (a) | 0.426 | 0.454 (0.125)
STAM (b) | 0.031 | 0.062 (0.082)
TimeSformer (a) | 0.544 | 0.573 (0.178)
CnnLstm (a) | 0.465 | 0.532 (0.168)
Resnet3D (a) | 0.555 | 0.585 (0.185)
Resnet21D (a) | 0.602 |  0.621 (0.193)
Table 4: The results are presented for all techniques using the F-score
metric.

The TimeSformer technique presented the best performance in the accuracy and
precision metrics, with values of 0.729 and 0.764 for their respective medians
and means. However, the Resnet21D technique outperformed TimeSformer in the
recall metric.

The ANOVA results were marginally significant for the techniques in all four
metrics, with p-values of $0.0771$, $0.000449$, $1.2\times 10^{-8}$, and
$4.9\times 10^{-10}$ for accuracy, precision, recall, and F-score,
respectively. These values were analyzed and indicate statistically
significant differences between almost all analyzed techniques, except for
accuracy when considering a significance level of 5%. Subsequent post-hoc
analysis using the Scott-Knott clustering test revealed that TimesFormer
outperformed the other techniques in precision metrics, despite being
clustered together with ViViT, Resnet3D, Resnet21D and CnnLstm. STAM achieved
the worst performance in all metrics.

The significant differences between the techniques can be analyzed using the
precision metric, which yielded a p-value of $0.000009$. These values indicate
strong statistical differences among the adopted techniques. Furthermore, when
comparing the learning rate, the precision and recall metrics also showed
significant differences, with p-values of $0.049393$ and $0.01480$,
respectively.

Considering the metrics of precision and a learning rate of $0.0001$, the
technique that showed the best result is TimeSformer, which is a variant of
transformer model.

We can visualize in Table 5 six video clips were used, with each clips
displaying three frames as an illustrative example. The GT (Ground Truth)
column represents the actual outcomes, while the DL (Deep Learning) column
reflects the results from TimeSformer classification technique. The clips
identified as ’a’ and ’b’ were correctly classified as ’NA’ (Non-Aggressive),
whereas the clips ’c’ and ’d’ were accurately classified as ’A’ (Aggressive).
Additionally, in Table 5, we can observe the clips ’e’ and ’f’, which,
although categorized as ’NA’ and ’A’, respectively, in the GT column, were not
classified correctly.

Frames | Results
---|---
| GT | DL
(a)  | NA | NA
(b)  | NA | NA
(c)  | A | A
(d)  | A | A
(e)  | NA | A
(f)  | A | NA
Table 5: Accurate and inaccurate classification of videos along with their
corresponding labels. Taking into account NA (Non-aggressive), A (Aggressive),
GT (Ground Truth), and DL (Deep Learning techniques).

The confusion matrix was obtained for the TimeSformer technique in the testing
dataset, as shown in Figure 4. We can observe an average accuracy rate of 73%
in the classification, where there are more videos classified as non-
aggressive.

Figure 4: The confusion matrix was obtained from the testing set using the
TimeSformer technique.

##  5 Discussion

Video classification requires the extraction of temporal and spatial
information that can be explored by techniques using sequences of frames
(videos). In this research, we propose the use of variants of transformers for
video classification. Although the transformer technique has been applied in
works involving videos, such as [37], and has shown better results when using
datasets with videos of gastrointestinal diseases. The use of transformers in
computer vision poses a challenge, transformers rely on extensive datasets to
yield improved results, necessitating high-quality images and substantial
processing power [17].

The reduction of the number of processed frames is an interesting strategy
adopted to improve processing efficiency and reduce redundant information.
However, it can affect the model’s generalization capacity. In the case of
STAM, which was configured to process 16 frames per video, it did not result
in better precision, recall and F-score. This may be due to the fact that the
behavior of interest is not always clearly presented in the initial frames of
the analyzed videos.

In the case of ViViT, which is another variant of transformer-based models, it
did not show better results compared by the analyzed metrics. This could be
attributed to differences in architecture and the way ViViT processes and
extracts information from frames. On the other hand, TimeSformer emerged as a
better option, particularly in terms of precision. Its approach of selecting
relevant patches from each frame allows for reducing redundant information and
focusing on the most important characteristics for classification. This
strategy of patch selection proves advantageous for the classification task
and leads to superior results, especially in terms of precision.

Although the use of CnnLstm with recurrent neural networks has shown better
results in previous works, such as [12], this technique did not demonstrate
the best performance in this project. This can be attributed to the fact that
the analyzed videos consist of series of frames that require the processing of
long sequences, which becomes a bottleneck for an LSTM-based to approach.

However, it is important emphasize that the other techniques that exclusively
used convolution, such as Resnet3D and Resnet21D, achieved better results
compared to the CNN-LSTM approach. This indicates that combining LSTM with
convolution does not yield significant improvements in this specific context.

##  6 Conclusion

This work proposed the use of deep learning techniques, including
transformers, convolutional neural networks, and recurrent layers to classify
aggressive behavior in pigs. To accomplish this, a video dataset was created
for training and validating the employed techniques.

The techniques were evaluated using accuracy, precision, recall, and F-measure
metrics, which demonstrated that the TimeSformer technique achieved the best
results in video classification across all metrics. While variants of
transformers have been utilized in numerous works involving video
classification, the TimeSformer technique outperformed them with the dataset
created and used in this study, particularly in terms of precision.

## References

  * Alameer et al. [2020] Alameer, A., Kyriazakis, I., Dalton, H. A., Miller, A. L., Bacardit, J., 2020. Automatic recognition of feeding and foraging behaviour in pigs using deep learning. biosystems engineering 197, 91–104.
  * Almadani et al. [2022] Almadani, A., Shivdeo, A., Agu, E., Kpodonu, J., 2022. Deep video action recognition models for assessing cardiac function from echocardiograms. In: 2022 IEEE International Conference on Big Data (Big Data). pp. 5189–5199.
  * Arnab et al. [2021] Arnab, A., Dehghani, M., Heigold, G., Sun, C., Lučić, M., Schmid, C., October 2021. Vivit: A video vision transformer. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). pp. 6836–6846.
  * Bertasius et al. [2021] Bertasius, G., Wang, H., Torresani, L., 2021. Is space-time attention all you need for video understanding?
URL https://arxiv.org/abs/2102.05095

  * Bi et al. [2021] Bi, J., Zhu, Z., Meng, Q., 2021. Transformer in computer vision. In: 2021 IEEE International Conference on Computer Science, Electronic Information Engineering and Intelligent Control Technology (CEI). pp. 178–188.
  * Chen et al. [2020] Chen, C., Zhu, W., Oczak, M., Maschat, K., Baumgartner, J., Larsen, M. L. V., Norton, T., 2020. A computer vision approach for recognition of the engagement of pigs with different enrichment objects. Computers and Electronics in Agriculture 175, 105580.
  * Dai et al. [2021] Dai, X., Chen, Y., Xiao, B., Chen, D., Liu, M., Yuan, L., Zhang, L., 2021. Dynamic head: Unifying object detection heads with attentions. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 7373–7382.
  * Desai [2020] Desai, C., 2020. Comparative analysis of optimizers in deep neural networks. International Journal of Innovative Science and Research Technology 5 (10), 959–962.
  * Dosovitskiy et al. [2020] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al., 2020\. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929.
  * Fernández-Carrión et al. [2020] Fernández-Carrión, E., Barasona, J. Á., Sánchez, Á., Jurado, C., Cadenas-Fernández, E., Sánchez-Vizcaíno, J. M., 2020\. Computer vision applied to detect lethargy through animal motion monitoring: a trial on african swine fever in wild boar. Animals 10 (12), 2241\.
  * Fu [2022] Fu, Z., 2022. Vision transformer: Vit and its derivatives.
URL https://arxiv.org/abs/2205.11239

  * Han et al. [2023] Han, J., Siegford, J., Colbry, D., Lesiyon, R., Bosgraaf, A., Chen, C., Norton, T., Steibel, J. P., 2023. Evaluation of computer vision for detecting agonistic behavior of pigs in a single-space feeding stall through blocked cross-validation strategies. Computers and Electronics in Agriculture 204, 107520\.
  * Hansen et al. [2021] Hansen, M. F., Baxter, E. M., Rutherford, K. M., Futro, A., Smith, M. L., Smith, L. N., 2021. Towards facial expression recognition for on-farm welfare assessment in pigs. Agriculture 11 (9), 847.
  * Harris et al. [2023] Harris, C., Finn, K. R., Kieseler, M.-L., Maechler, M. R., Tse, P. U., 2023. Deepaction: a matlab toolbox for automated classification of animal behavior in video. Scientific Reports 13 (1), 2688.
  * Hu et al. [2021] Hu, Z., Yang, H., Lou, T., 2021. Dual attention-guided feature pyramid network for instance segmentation of group pigs. Computers and Electronics in Agriculture 186, 106140.
  * Islam et al. [2020] Islam, M. M., Tasnim, N., Baek, J.-H., 2020. Human gender classification using transfer learning via pareto frontier cnn networks. Inventions 5 (2), 16.
  * Khan et al. [2022] Khan, S., Naseer, M., Hayat, M., Zamir, S. W., Khan, F. S., Shah, M., 2022. Transformers in vision: A survey. ACM computing surveys 54 (10s), 1–41.
  * Kim et al. [2021] Kim, M., Choi, Y., Lee, J.-n., Sa, S., Cho, H.-c., 2021. A deep learning-based approach for feeding behavior recognition of weanling pigs. Journal of Animal Science and Technology 63 (6), 1453–1463.
URL https://doi.org/10.5187/jast.2021.e127

  * Lassaletta et al. [2019] Lassaletta, L., Estellés, F., Beusen, A. H., Bouwman, L., Calvet, S., Van Grinsven, H. J., Doelman, J. C., Stehfest, E., Uwizeye, A., Westhoek, H., 2019\. Future global pig production systems according to the shared socioeconomic pathways. Science of the Total Environment 665, 739–751.
  * Li et al. [2021] Li, Y., Wu, C.-Y., Fan, H., Mangalam, K., Xiong, B., Malik, J., Feichtenhofer, C., 2021. Mvitv2: Improved multiscale vision transformers for classification and detection.
URL https://arxiv.org/abs/2112.01526

  * Liao et al. [2022] Liao, J., Li, H., Feng, A., Wu, X., Luo, Y., Duan, X., Ni, M., Li, J., 2022. Domestic pig sound classification based on transformercnn. Applied Intelligence, 1–17.
  * Liu et al. [2020] Liu, D., Oczak, M., Maschat, K., Baumgartner, J., Pletzer, B., He, D., Norton, T., 2020. A computer vision-based method for spatial-temporal action recognition of tail-biting behaviour in group-housed pigs. Biosystems Engineering 195, 27–41.
  * Liu et al. [2019] Liu, W., Luo, W., Li, Z., Zhao, P., Gao, S., et al., 2019. Margin learning embedded prediction for video anomaly detection with a few anomalies. In: IJCAI. pp. 3023–3030.
  * Ma et al. [2022] Ma, S., Zhang, Q., Li, T., Song, H., 2022. Basic motion behavior recognition of single dairy cow based on improved rexnet 3d network. Computers and Electronics in Agriculture 194, 106772.
  * Nasirahmadi et al. [2019] Nasirahmadi, A., Sturm, B., Edwards, S., Jeppsson, K.-H., Olsson, A.-C., Müller, S., Hensel, O., 2019. Deep learning and machine vision approaches for posture detection of individual pigs. Sensors 19 (17).
URL https://www.mdpi.com/1424-8220/19/17/3738

  * Patil et al. [2021] Patil, P., Pawar, V., Pawar, Y., Pisal, S., 2021. Video content classification using deep learning. arXiv preprint arXiv:2111.13813.
  * Shao et al. [2021] Shao, H., Pu, J., Mu, J., 2021. Pig-posture recognition based on computer vision: Dataset and exploration. Animals 11 (5), 1295.
  * Sharir et al. [2021] Sharir, G., Noy, A., Zelnik-Manor, L., 2021. An image is worth 16x16 words, what is a video worth?
URL https://arxiv.org/abs/2103.13915

  * Shigang et al. [2021] Shigang, W., Jian, W., Meimei, C., Jinyang, W., 2021. A pig face recognition method for distinguishing features. In: 2021 IEEE Asia-Pacific Conference on Image Processing, Electronics and Computers (IPEC). IEEE, pp. 972–976.
  * Singh et al. [2022] Singh, D. K., Ansari, M. A., Pallawi, S., 2022. Computer vision based visual activity classification through deep learning approaches. In: 2022 IEEE Region 10 Symposium (TENSYMP). pp. 1–5.
  * Strudel et al. [2021] Strudel, R., Garcia, R., Laptev, I., Schmid, C., October 2021. Segmenter: Transformer for semantic segmentation. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). pp. 7262–7272.
  * Tran et al. [2018] Tran, D., Wang, H., Torresani, L., Ray, J., LeCun, Y., Paluri, M., 2018. A closer look at spatiotemporal convolutions for action recognition. In: Proceedings of the IEEE conference on Computer Vision and Pattern Recognition. pp. 6450–6459.
  * Vaswani et al. [2017] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., Polosukhin, I., 2017. Attention is all you need. Advances in neural information processing systems 30.
  * Wang et al. [2021] Wang, M., Larsen, M., Bayer, F., Maschat, K., Baumgartner, J., Rault, J.-L., Norton, T., et al., 2021. A pca-based frame selection method for applying cnn and lstm to classify postural behaviour in sows. Computers and Electronics in Agriculture 189, 106351.
  * Wang et al. [2022] Wang, M., Larsen, M. L., Liu, D., Winters, J. F., Rault, J.-L., Norton, T., 2022\. Towards re-identification for long-term tracking of group housed pigs. Biosystems Engineering 222, 71–81.
  * Xu et al. [2022] Xu, J., Zhou, S., Xu, A., Ye, J., Zhao, A., 2022. Automatic scoring of postures in grouped pigs using depth image and cnn-svm. Computers and Electronics in Agriculture 194, 106746.
  * Zhang et al. [2023] Zhang, C., Ding, A., Fu, Z., Ni, J., Chen, Q., Xiong, Z., Liu, B., Cao, Y., Chen, S., Liu, X., 2023. Deep learning for gastric location classification: An analysis of location boundaries and improvements through attention and contrastive learning. Smart Health 28, 100394.
URL https://www.sciencedirect.com/science/article/pii/S2352648323000223

  * Zhang et al. [2020] Zhang, K., Li, D., Huang, J., Chen, Y., 2020. Automated video behavior recognition of pigs using two-stream convolutional networks. Sensors 20 (4), 1085\.
  * Zhang et al. [2019] Zhang, Y., Cai, J., Xiao, D., Li, Z., Xiong, B., 2019. Real-time sow behavior detection based on deep learning. Computers and Electronics in Agriculture 163, 104884.
URL https://www.sciencedirect.com/science/article/pii/S0168169919300080

  * Zhou et al. [2023] Zhou, W., Zhu, Y., Lei, J., Yang, R., Yu, L., 2023. Lsnet: Lightweight spatial boosting network for detecting salient objects in rgb-thermal images. IEEE Transactions on Image Processing 32, 1329–1340.