2022

# A Nested Genetic Algorithm for Explaining Classification Data Sets with
Decision Rules

Paul-Amaury Matt1<EMAIL_ADDRESS>Rosina Ziegler1
<EMAIL_ADDRESS>Danilo Brajovic1
<EMAIL_ADDRESS>Marco Roth1<EMAIL_ADDRESS>Marco F. Huber1,2<EMAIL_ADDRESS>1Department of Cyber Cognitive
Intelligence (CCI), Fraunhofer Institute for Manufacturing Engineering and
Automation IPA, Nobelstrasse 12, 70569 Stuttgart, Germany

2Institute of Industrial Manufacturing and Management IFF, University of
Stuttgart, Allmandring 35, 70560 Stuttgart, Germany

###### Abstract

Our goal in this paper is to automatically extract a set of decision rules
(rule set) that best explains a classification data set. First, a large set of
decision rules is extracted from a set of decision trees trained on the data
set. The rule set should be concise, accurate, have a maximum coverage and
minimum number of inconsistencies. This problem can be formalized as a
modified version of the weighted budgeted maximum coverage problem, known to
be NP-hard. To solve the combinatorial optimization problem efficiently, we
introduce a nested genetic algorithm which we then use to derive explanations
for ten public data sets.

###### keywords:

classification, decision rule, rule extraction, genetic algorithm, Quadratic
Unconstrained Binary Optimization

##  1 Introduction

In 1959, Arthur Samuel, a pioneer in the field of Artificial Intelligence
defined the term _Machine Learning_ samuel1959some  as the “field of study
that gives computers the ability to learn without being explicitly
programmed”. In the field of Machine Learning, an important technique called
_Deep Learning_ allows “computational models that are composed of multiple
processing layers to learn representations of data with multiple levels of
abstraction” lecun2015deep . In recent years, many accurate decision support
systems based on Deep Learning have been constructed as _black boxes_
guidotti2018survey , that is as systems that hide their internal logic to the
user.

Thus, the purpose of an _Explainable Artificial Intelligence_
molnar2020interpretable ; samek2019explainable ; xu2019explainable ;
burkart2021survey  system is to make its behavior more intelligible to humans
by providing explanations gunning2019xai . A popular approach to addressing
the problem of opacity of black-box machine learning models is the use of
_post-hoc_ explainability methods: these methods approximate the logic of
underlying machine learning models with the aim of explaining their internal
workings, so that the user can understand them vale2022explainable .

Unfortunately, these methods provide explanations that are not faithful to
what the black-box model computes and can be misleading rudin2019stop . A
recent and highly cited perspective rudin2019stop  highlighted the need for
_white box_ models (i.e. models explainable by nature) for high stakes
decisions in Healthcare and Criminal Justice. Other application domains of
Artificial Intelligence where white box models are deemed to be important are
Banking, Bioinformatics, Automotive, Marketing, Politics, Agriculture, Defense
and Recommender Systems burkart2021survey . Examples of white box models are
linear regression, decision trees, mixtures of decision trees vasic2019moet
and rule sets wang2017bayesian .

In this article, we focus on an important Machine Learning task, namely
_classification_. Formally, classification refers to a predictive modeling
problem where a class label is predicted for a given example of input data.
For instance, given the length and width in centimeters of the petals and
sepals of an iris flower, we want to determine if the flower is from the
setosa, versicolour or virginica species. The Iris data
set111https://archive.ics.uci.edu/ml/datasets/iris contains 150 instances of
flowers, with 50 instances for each of these 3 species. Using this data set,
we could build classifiers using classification models such as decision trees,
random forests, support vector machines and neural networks. But amongst
these, only a sufficiently small decision tree would yield an “explainable”
solution. Let us for instance consider the decision tree shown in Figure 1
that has been obtained with Python’s scikit-learn222https://scikit-
learn.org/stable/modules/tree.html.

Figure 1: Decision tree trained on the Iris data set.

The decision tree can be transformed into a set of decision rules or so-called
_rule set_ in the following way. Every path starting at the root node and
ending at one of the leaf nodes is turned into a decision rule. A _decision
rule_ is an IF-THEN statement consisting of a conjunction of conditions
followed by a conclusion in the form of a class prediction:
_IF_ condition-1 _AND_ … _AND_ condition-n _THEN_ CLASS=y
The internal nodes and branches followed along the path make up the conditions
and the leaf node’s majority class makes up the predicted class. Decision
rules follow a general structure: IF all the conditions are met THEN make a
certain prediction. Decision rules are probably the most interpretable
prediction models. Their IF-THEN structure semantically resembles natural
language and the way we think, provided that the conditions are built from
intelligible features of the input data and that the explanation is
sufficiently concise. In the example of Figure 1, there are 9 leaf nodes and
thus also 9 decision rules that can be extracted from the decision tree. See
Figure 2.

    IF petal length<=2.45 THEN CLASS=setosa
    IF petal length>2.45 AND petal width<=1.75 AND petal length<=4.95 AND petal width<=1.65 THEN CLASS=versicolor
    IF petal length>2.45 AND petal width<=1.75 AND petal length<=4.95 AND petal width>1.65 THEN CLASS=virginica
    IF petal length>2.45 AND petal width<=1.75 AND petal length>4.95 AND petal width<=1.55 THEN CLASS=virginica
    IF petal length>2.45 AND petal width<=1.75 AND petal length>4.95 AND petal width>1.55 AND sepal length<=6.95
    THEN CLASS=versicolor
    IF petal length>2.45 AND petal width<=1.75 AND petal length>4.95 AND petal width>1.55 AND sepal length>6.95
    THEN CLASS=virginica
    IF petal length>2.45 AND petal width>1.75 AND petal length<=4.85 AND sepal length<=5.95 THEN CLASS=versicolor
    IF petal length>2.45 AND petal width>1.75 AND petal length<=4.85 AND sepal length>5.95 THEN CLASS=versicolor
    IF petal length>2.45 AND petal width>1.75 AND petal length>4.85 THEN CLASS=virginica

Figure 2: Decision rules derived from the decision tree in Figure 1.

In the example, the decision rules give a prediction for all instances of the
data set and all predictions made are correct. In general, the decision rules
obtained from a decision tree never conflict, because for any data input there
can by only one decision rule that applies. However, the decision rules
obtained from a decision tree may lead to prediction errors.

The complexity or _length_ of a decision rule can be simply defined by its
number of conditions. Here, the simplest rule is the first one and has a
length of 1. The most complex rules (fifth and sixth rules) have a length
equal to the depth of the decision tree, which is 5. The sum of the lengths of
all decision rules can be used as a measure of the complexity of the
explanation for the data set. In our example, the explanation has a complexity
of 34.

Is there a simpler explanation of the Iris data set? To check if that is the
case, we could start by training several decision trees on the data set, for
instance by training a random forest or by using a decision tree algorithm
with different hyper-parameter combinations, varying for example the maximum
tree depth or information criterion. Each tree would yield its own set of
decision rules and we would obtain explanations that differ in terms of
complexity. But the simpler the explanation, the larger the number of
prediction errors would potentially be. So we would have to set a maximum
number of prediction errors as constraint to answer the question in a
meaningful way.

An even more general idea would be to gather all the decision rules from all
the trees generated and to select rules from that large set. A set of decision
rules selected in this way may not necessarily predict all instances, unlike
those obtained from decision trees. One should also expect to encounter
conflicts between the rules, but this more general method would allow us to
find simpler explanations and reduce the number of classification errors.

Several areas of Artificial Intelligence may benefit from an automated
procedure for explaining a data set with decision rules, such as 1) Data
Science, where one essentially seeks to derive insights from data, 2)
Knowledge Representation, where one may be interested in automatically
extracting from data some knowledge expressed in a logical form, 3) Formal
Specification, as one may replace the classes of the data set by the predicted
classes of a black-box model and by extracting rules get a specification of
the behaviour of the model, and finally 4) Explainable Artificial
Intelligence, where one seeks to build models that are “transparent”, i.e.
that can be explained.

The remainder of the article is organised as follows. In Section 2, we discuss
existing approaches for rule extraction and other related works. In Section 3,
we examine how a set of candidate decision rules may be generated. Section 4
formalizes the problem of finding an optimal explanation as a budgeted maximum
coverage problem khuller1999budgeted , known to be NP-hard. A _genetic
algorithm_ (GA) is an iterative search, optimization and adaptive machine
learning technique premised on the principles of natural selection. Genetic
algorithms are capable of finding solutions to NP-hard problems
panchal2015solving . In Section 5, we introduce a nested genetic algorithm for
solving the rule selection problem, whereby the inner genetic algorithms are
necessary for facilitating the search in the constrained search space and
enable the evolutionary process. In Section 6, we then test the performance of
the algorithm on several simple classification data sets from the UCI Machine
Learning Repository and compare its performance with adaptations of the
methods exposed in Section 2 and conclude in Section 8.

In the remainder of the paper, we denote $(X,Y)$ the classification data set,
where $X=x_{1},\dotsc,x_{N}$ are $N$ vectors of dimension $d$ and
$Y=y_{1},\dotsc,y_{N}$ are labels that belong to a finite set of classes $C$.
We denote $R_{1},\dotsc,R_{M}$ the decision rules generated and $M$ their
number.

##  2 Related Work

This section reviews some of the main approaches existing for rule extraction
from an ensemble of decision trees. The approaches exposed in this section aim
at increasing the explainability of the ensemble and its predictive accuracy.
Recall that strictly speaking, a rule set does not constitute an ensemble per
se. But, a rule set allows to build a classifier once we specify a voting
mechanism to elect a winning class. Most often, the output class of the
ensemble is determined by weighted majority voting and the accuracy of the
ensemble classifier can then be defined as the fraction of observations
correctly classified. Our approach differs from the existing works discussed
here-after, since a) we do not explicitly seek to maximize _accuracy_
(fraction of correctly classified data) but rather the _coverage_ (fraction of
data classified unambiguously by the rules) of the solution, and b) these
approaches do not impose any hard constraints on the level of complexity of
the explanation nor on the number of classification errors.

###  2.1 ForEx++

The ForEx++ algorithm AdnanIslam2017forex  starts with the set of rules
obtained from a decision forest and removes identical rules. For each class,
it computes three sets of rules: 1) the set of rules with accuracy above
average, 2) the set of rules with coverage above average and 3) the set of
rules with length below average. The intersection of these three sets is then
computed for each class. Finally, the algorithm returns the union over all
classes of these intersections. The rules extracted by this method are
comparatively more accurate, general and concise than others. Some drawbacks
of the method are that the rules may not be very diverse (similar rules may be
selected for each class) and they may not cover the entire data set.

###  2.2 RF+HC Method

The RF+HC algorithm gras2015rfhc  is a rule extraction method to extract
comprehensible rules from a random forest. The algorithm consists of four
parts. First, the rules are generated. Then, a score is computed for each rule
according to

$\mathrm{ruleScore}=\frac{cc-ic}{cc+ic}+\frac{cc}{ic+k}+\frac{cc}{rl}$

where $cc$ is the number of observations that are covered and correctly
classified by the rule, $ic$ is the number of incorrectly classified
observations that are covered by the rule, $rl$ is the rule length and $k$ is
a positive constant (set to $k=4$ by the authors). This scoring function
ensures the retention of rules with the highest levels of classification
accuracy and the highest levels of coverage, along with prioritizing concise
rules. In this “hill climbing” approach (HC), the rule set contains initially
all rules. Rules are then iteratively removed from the set. In each iteration,
a rule is probabilistically selected on the basis of its score (meaning that a
rule with low score has greater chance to be selected than a rule with high
score). If the removal of the selected rule increases the overall accuracy,
then the change is retained. The removal process terminates when all rules
have been considered. Since the outcome is random, the process is repeated
several times and the rule set that achieves the highest accuracy is returned
by the algorithm.

###  2.3 IRFRE

The Improved Random Forest based Rule Extraction (IRFRE) method wang2020irfre
derives accurate and interpretable classification rules from a decision tree
ensemble. Decision rules are extracted from a Random Forest and then selected
using a multi-objective genetic algorithm fonseca1993multiobjective . An
initial population is randomly generated, where each individual’s chromosome
is coded as a binary string $r_{1}\dotsc r_{M}$ of length $M$ (the number of
rules generated) and $r_{i}=1$ if rule $R_{i}$ is selected and $r_{i}=0$
otherwise. For every generation, the accuracy and interpretability of each
individual (rule set) are calculated. The interpretability of the classifier
is defined as a linear combination of the average length of the rules, the
number of rules and their coverage. The rank of each individual is determined
and a randomized mating process takes place, in which individuals with lowest
rank are selected with highest probability. Each pair of individuals gives
birth to two children after uniform crossover and bitflip mutation. The best
individuals amongst parents and children of the current generation are
selected for the next generation. When the maximum number of generation is
reached, the algorithm stops. This yields a final population and its Pareto
optimal solutions are returned.

###  2.4 Other Related Works

Heuristic methods are traditionally used to quickly produce decision trees
with reasonably high accuracy. A commonly criticised point, however, is that
the resulting trees may not be the best representation of the data in terms of
accuracy and size. izza2020explaining ; izza2022tackling  show that in some
settings decision trees can hardly be deemed interpretable, with paths being
arbitrarily larger than a minimal set of features that entails the prediction
(i.e., a so-called _PI-explanation_).

This motivated the development of optimal classification tree algorithms that
globally optimise the decision tree in contrast to heuristic methods that
perform a sequence of locally optimal decisions. verhaeghe2020learning
introduced an approach to learn decision trees using constraint programming
that allows to limit the size of the decision trees while maintaining a good
classification accuracy. alos2021learning  offers a combinatorial optimization
approach based on Maximum Satisfiability technology to compute Minimum Pure
Decision Trees for the sake of interpretability. These decision trees can
outperform on average the decision tree classifiers generated with Python’s
scikit-learn in terms of accuracy. demirovic2022murtree  provides a novel
algorithm for learning optimal classification trees based on dynamic
programming and search that supports constraints on the depth of the tree and
number of nodes.

lakkaraju2016interpretable  formalizes decision set learning through an
objective function that simultaneously optimizes for accuracy, conciseness,
and meaningfulness of the rules. Their approach learns short, accurate and
non-overlapping rules that cover the whole feature space and pay attention to
small but important classes. Their experiments show that interpretable
decision sets are as accurate at classification as state-of-the-art machine
learning techniques. Moreover, interpretable decision sets are three times
smaller than models learned by competing approaches. wang2017bayesian  present
a machine learing algorithm for building probabilistic models for
classification that are comprised of a small number of short rules in
disjunctive normal form, which have the advantage of being interpretable to
human experts.

##  3 Generation of Decision Rules

In this section, we briefly review how decision rules can be generated and
specify how we do this in our implementation. In general, we may distinguish
six steps for generating a set of decision rules from decision trees:

  1. 1.

Choice of a decision tree algorithm. We may choose amongst several decision
tree algorithms such as ID3, C4.5, C5.0 or CART. We use the Python package
scikit-learn which implements an optimised version of the CART algorithm. Note
however that this algorithm does not support categorical variables, so the
categorical variables of the data set need to be one-hot encoded before using
the algorithm.

  2. 2.

Data preparation. Prepare the data so that the chosen training algorithm can
run without error. For instance, we may have to remove entries with missing
values or fill the missing values by applying an imputation technique.
Transform each categorical variable into several binary variables by one-hot
encoding, if the chosen algorithm cannot handle categorical variables.
Optionally, split randomly the available data into a training and a testing
set if the user’s ultimate goal is to build a classifier from the rule set.

  3. 3.

Choice of hyper-parameter values. Choose one or several combinations of values
for the hyper-parameters of the algorithm. In our implementation, the hyper-
parameter combinations are shown in Table 1.

  4. 4.

Train trees or random forests. For each hyper-parameter combination, train a
tree on the whole data set / training set, or train a random forest, whereby
each tree of the forest is trained on a random sub-sample of the data. We
train decision trees rather than random forests to minimize the number of
rules generated.

  5. 5.

Transformation into rules. Each path from the root node to a leaf node of a
decision tree is transformed into a decision rule. The internal nodes and
branches followed along the path path yield the conditions of the decision
rule and the majority class of the leaf node yields the predicted class.

  6. 6.

Simplification. We then simplify redundant conditions within a decision rule.
For instance, two conditions on the same feature $k$ such as $x^{k}\geq\alpha$
and $x^{k}\geq\beta$ simplify as one condition $x^{k}\geq\max(\alpha,\beta)$.
Remove rules that are redundant (identical) or empirically equivalent, i.e.
that yield the same predictions on the data set. The reader interested in a
more advanced method for rule simplification may refer to izza2020explaining .

Table 1: Hyper-parameters used for the CART algorithm. Hyper-parameter
---
Name |  Definition |  Range of values
criterion |  The function to measure the quality of a split. Supported criteria are “gini” for the Gini impurity and “entropy” for the information gain. |  {”gini”, ”entropy”}
splitter |  The strategy used to choose the split at each node. Supported strategies are “best” to choose the best split and “random” to choose the best random split. |  {”best”, ”random”}
max_depth |  The maximum depth of the tree. |  integer
max_features |  The number of features to consider when looking for the best split. If “sqrt”, then max_features=$\sqrt{d}$. If “log2”, then max_features=$\log_{2}(d)$. |  {”sqrt”, ”log2”}

It is also possible to generate decision rules by _rule mining_
wang2017bayesian . For categorical attributes, consider both positive
associations (e.g. $x_{j}=\mathrm{blue}$) and negative associations
($x_{j}\neq\mathrm{green}$). For each numerical attribute, create a set of
binary variables by comparing it with a set of thresholds (usually quantiles)
and add their negation as separate attributes. Then mine for frequent rules
within the sets of observations pertaining to the different classes, using
some frequent rule-mining method such as the FP-growth algorithm
borgelt2005implementation . The number of rules may be reduced by imposing a
maximum length of rules, a minimum support or a minimum information gain.

##  4 Formulation of the Optimisation Problem

Let us now formalize the problem of selecting an optimal rule set for
explaining a classification data set. Intuitively, the selected rules should
achieve several objectives. Firstly, we would like the rule set to predict a
class for a maximum number of instances in the data set. Secondly, the number
of conflicts between the rules should be minimized. Thirdly, the total
complexity of the rules shall not exceed a given complexity fixed by the user.
Finally, the total number of classification errors should not exceed a given
number of classification errors. We may consequently formulate the optimal
rule selection problem as a modified budgeted maximum coverage problem
khuller1999budgeted :

$\displaystyle\texttt{maximise
}\sum_{j=1}^{N}e_{j}-\frac{\epsilon}{2}\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{i^{\prime}=1}^{M}\alpha_{i,i^{\prime},j}\cdot
r_{i}\cdot r_{i^{\prime}}$ $\displaystyle\texttt{subject to
}L(r)=\sum_{i=1}^{M}L(R_{i})\cdot r_{i}\leq B_{c}$ $\displaystyle
E(r)=\sum_{i=1}^{M}E(R_{i})\cdot r_{i}\leq B_{e}$ $\displaystyle\forall
j\in\\{1,\dotsc,N\\}:\quad e_{j}\leq\sum_{i\in S_{j}}r_{i}$
$\displaystyle\forall i\in\\{1,\dotsc,M\\}:\quad r_{i}\in\\{0,1\\}$
$\displaystyle\forall j\in\\{1,\dotsc,N\\}:\quad e_{j}\in\\{0,1\\}$

where the decision variables and parameters are defined as follows:

  * •

$e_{j}$ is a binary variable equal to $1$ if and only if data input $x_{j}$ is
covered by at least one of the selected rules

  * •

$r_{i}$ is a binary variable equal to $1$ if and only if the decision rule
$R_{i}$ is selected

  * •

the binary coefficient $\alpha_{i,i^{\prime},j}$ is equal to $1$ if and only
if $R_{i}$ and $R_{i^{\prime}}$ cover $x_{j}$ but lead to different
predictions (conflict)

  * •

$\epsilon\geq 0$ is the penalty for every conflict between a pair of selected
rules

  * •

$S_{j}$ is the set of indices of rules that cover $x_{j}$

  * •

$L(R_{i})$ is the length of $R_{i}$

  * •

$E(R_{i})$ is the number of observations incorrectly classified by $R_{i}$

  * •

$B_{c}\geq 0$ is the budget for the total complexity of the rule set

  * •

$B_{e}\geq 0$ is the budget for the total number of classification errors
333In practice, the user may determine the error budget by setting a fraction
of error, multiplying the fraction by $N$ and rounding the result to the
closest integer.

The problem’s objective function is quadratic and the inequality constraints
are linear with respect to the decision variables $r_{i}$ and $e_{j}$. This
combinatorial optimization problem involves $M+N$ binary variables, where $M$
is the number of generated rules and $N$ is the number of data instances. It
is fortunately possible to reduce the problem to $M$ variables. Indeed, every
variable $e_{j}$ should be maximized, whilst satisfying $e_{j}\leq 1$ and
$e_{j}\leq\sum_{i\in S_{j}}r_{i}$. So, for an optimal solution $r$, this
implies $e_{j}=1$ if $\sum_{i\in S_{j}}r_{i}\geq 1$ and $e_{j}=0$ otherwise.
We thus introduce the functions $e_{j}^{*}:\\{0,1\\}^{M}\rightarrow\\{0,1\\}$
for all $j\in\\{1,\dotsc,N\\}$:

$e_{j}^{*}(r)=\begin{cases}1&\text{if }\sum_{i\in S_{j}}r_{i}\geq 1\\\
0&\text{otherwise}\end{cases}$

We may now get rid the $N$ variables $e_{j}$, thus ending up with an
equivalent problem that requires only $M$ variables:

$\displaystyle\texttt{maximise
}f^{*}(r)=\sum_{j=1}^{N}e_{j}^{*}(r)-\frac{\epsilon}{2}\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{i^{\prime}=1}^{M}\alpha_{i,i^{\prime},j}\cdot
r_{i}\cdot r_{i^{\prime}}$ $\displaystyle\texttt{subject to
}L(r)=\sum_{i=1}^{M}L(R_{i})\cdot r_{i}\leq B_{c}$ $\displaystyle
E(r)=\sum_{i=1}^{M}E(R_{i})\cdot r_{i}\leq B_{e}$ $\displaystyle\forall
i\in\\{1,\dotsc,M\\}:\quad r_{i}\in\\{0,1\\}$

Note that the objective function is not quadratic anymore. In the remainder of
the article, we refer to the value of objective function $f^{*}(r)$ simply as
coverage, the fraction $f^{*}(r)/N$ as coverage score, $L(r)$ is refered to as
complexity of the rule set and $E(r)$ as the number of classification errors.

##  5 Nested Genetic Algorithm

To solve the problem above, we develop a nested genetic algorithm. Our
algorithm uses ideas stemming from some of the classical approaches for rule
extraction presented in Section 2, viz. the RF+HC and IRFRE methods. Since
these two methods were created in a different context, we start this section
by adapting them to fit our problem. We then introduce a genetic algorithm to
solve the budgeted maximum coverage problem. The adapted RF+HC method is used
to compute part of the initial population. We then modify the classical
genetic algorithm and enhance it using two “inner” genetic algorithms nested
in the first or “outer” algorithm. The modified IRFRE method will mainly be
used to demonstrate experimentally that the inner genetic algorithms are
necessary to enable the evolutionary process (crossover and genetic mutations)
when searching for solutions in the constrained space.

###  5.1 Adaptations of Existing Rule Extraction Methods

In this subsection, we adapt three classical rule extraction methods to the
budgeted maximum coverage problem.

####  5.1.1 ForEx++

The original ForEx++ Algorithm 1 can be used without any modification for rule
selection in our setting.

Algorithm 1 ForEx++

1:for each class $c$ in $C$ do

2: let $\mathcal{I}_{c}$ be the intersection of the sets of the rules with 1)
accuracy above average, 2) coverage above average and 3) length below average

3:end for

4:$\mathcal{U}\leftarrow\bigcup_{c\in C}\mathcal{I}_{c}$

5:return $\mathcal{U}$

####  5.1.2 RF+HC

The RF+HC method can easily be adapted to our budgeted maximum coverage
problem. We start by initializing the variable representing the set of
selected rules as the empty set, then iteratively add rules. In each
iteration, we randomly pick a rule that has not been picked yet and add the
rule to the set if it does not violate any budget constraint and increases the
coverage of the set. Rules with a high score must be prioritized, so we select
rules using a probability distribution proportional to the rule score
distribution. Once all rules have been selected and examined, the iterative
procedure stops. The result of each run is stored and eventually compared with
the results obtained out of a total of $n_{\mathrm{trials}}$ runs. Since all
solutions obtained satisfy the budget constraints, we simply return as unique
solution the set that represents the best explanation, i.e. the rule set with
highest coverage. See Algorithm 2.

Algorithm 2 Adaptation of RF+HC

1:compute the ruleScore of each rule:  $\mathrm{ruleScore}=\frac{cc-
ic}{cc+ic}+\frac{cc}{ic+4}+\frac{cc}{rl}$

2:initialize the best feasible solution found $\mathcal{X}_{\mathrm{best}}$
and its coverage $f^{*}(\mathcal{X}_{\mathrm{best}})$:
$\mathcal{X}_{\mathrm{best}}\leftarrow\\{\\}$, $f^{*}_{\mathrm{max}}\leftarrow
0$

3:for trial from $1$ to $n_{\mathrm{trials}}$ do

4: initialize $\mathcal{X}$ as the empty set

5: initialize $\mathcal{R}$ as the set of all generated rules

6: while $\mathcal{R}$ is not empty do

7: select randomly a rule $R$ from $\mathcal{R}$ according to the probability
distribution $P:\mathcal{R}\rightarrow[0,1]$ defined as
$P(R)=\frac{\mathrm{ruleScore}(R)}{\sum_{R^{\prime}\in\mathcal{R}}\mathrm{ruleScore}(R^{\prime})}$

8: if adding $R$ to $\mathcal{X}$ increases $f^{*}(\mathcal{X})$ without
violating the complexity and error budget constraints then

9: add $R$ to $\mathcal{X}$

10: end if

11: remove $R$ from $\mathcal{R}$

12: end while

13: if $f^{*}(\mathcal{X})>f^{*}_{\mathrm{max}}$ then do
$f^{*}_{\mathrm{max}}\leftarrow f^{*}(\mathcal{X})$ and
$\mathcal{X}_{\mathrm{best}}\leftarrow\mathcal{X}$

14:end for

15:return $\mathcal{X}_{\mathrm{best}},f^{*}_{\mathrm{max}}$

####  5.1.3 IRFRE

The IRFRE method can also be adapted to our problem. An initial population is
created by randomly generating bit strings of length $M$ and filtering the
corresponding rule sets that fulfil the budget constraints. A multi-objective
genetic algorithm involving three objective functions is then applied. The
objectives are the coverage, the complexity and number of classification
errors of the rule set. The fitness function used is based on the rank of the
individuals with respect to the objectives. For the reproduction mechanism,
each pair of individuals selected gives birth to two children after uniform
crossover and random bitflip mutation, but only children that satisfy the
constraints are added to the population. The $n_{\mathrm{max-population}}$
fittest individual amongst the individuals are selected for the next
generation, where $n_{\mathrm{max-population}}$ is the maximum population size
allowed. The evolutionary process is repeated over $n_{\mathrm{generations}}$
and the algorithm finally returns the individual with highest coverage. See
Algorithm 3.

Algorithm 3 Adaptation of IRFRE

1:generate initial population of random binary strings with length $M$ that
fulfil the budget constraints

2:for generation from $1$ to $n_{\mathrm{generations}}$ do

3: calculate for each individual the coverage $f^{*}(r)$, the complexity
$L(r)$ and number of classification errors $E(r)$

4: compute the rank of each individual with respect to the 3 objectives

5: select pairs of individuals randomly based on their rank

6: mate the selected pairs of individuals, each pair gives birth to two
children after uniform crossover and random bitflip mutation, add the children
to the population if they fulfil the budget constraints

7: select the $n_{\mathrm{max-population}}$ fittest individuals for the next
generation

8:end for

9:return the individual $r$ with highest coverage $f^{*}(r)$ in the final
population

###  5.2 Genetic Algorithm

Solving the problem does not require a multi-objective genetic algorithm and
its rank-based fitness function and can be solved using a standard (single-
objective) genetic algorithm goldberg1989genetic  with some slight
modifications to account for the constraints. We encode the variable $r$ as a
bit string $r_{1}r_{2}\dotsc r_{M}$ of length $M$ or “chromosome”. The
encoding means that if $r_{i}=1$, then the $i$-th rule $R_{i}$ is selected for
the set of rules, where the set of rules
$\mathcal{R}=\\{R_{1},\dotsc,R_{M}\\}$ is generated as described in Section 3.

The fitness function to maximize is the coverage

$f^{*}(r)=\sum_{j=1}^{N}e_{j}^{*}(r)-\frac{\epsilon}{2}\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{i^{\prime}=1}^{M}\alpha_{i,i^{\prime},j}\cdot
r_{i}\cdot r_{i^{\prime}}$

where $e_{j}^{*}(r)=1$ when there is a rule selected which explains $x_{j}$,
and $e_{j}^{*}(r)=0$ otherwise. Remark that
$e_{j}^{*}(r)=\mathrm{sign}(e_{j,\bullet}^{\mathrm{T}}r)$, where

  * •

$\mathrm{sign}$ is the sign function defined as $\mathrm{sign}(z)=1$ if $z>0$
and $\mathrm{sign}(z)=0$ otherwise,

  * •

$e_{j,\bullet}$ is the vector in $\mathbb{R}^{M}$ with $i$-th component
$e_{j,i}=1$ if $x_{j}$ is explained by $R_{i}$ and $e_{j,i}=0$ otherwise.

Observe also that the triple sum

$\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{i^{\prime}=1}^{M}\alpha_{i,i^{\prime},j}\cdot
r_{i}\cdot r_{i^{\prime}}=r^{\mathrm{T}}{{\mathbf{Q}}}^{\alpha}r$

is a quadratic function, where ${{\mathbf{Q}}}^{\alpha}$ is the $M\times M$
square matrix with integer coefficients $\
{{\mathbf{Q}}}^{\alpha}_{i,i^{\prime}}=\sum_{j=1}^{N}\alpha_{i,i^{\prime},j}$.
Introducing the binary $M\times M$ matrix ${{\mathbf{E}}}$ with coefficients
$e_{j,i}$ equal to $1$ if and only if $x_{j}$ is explained by $R_{i}$, we can
rewrite the fitness function in matrix notation as

$f^{*}(r)=1^{\mathrm{T}}\mathrm{sign}({{\mathbf{E}}})-\frac{\epsilon}{2}\cdot
r^{\mathrm{T}}{{\mathbf{Q}}}^{\alpha}r$ (1)

where the sign function is applied component-wise. The matrix notation allows
an efficient implementation using a matrix calculus library such as Python’s
Numpy.

The crossover mechanism used can be any of the usual ones for genetic
algorithms goldberg1989genetic , namely:

  * •

1-point crossover: an integer position on both parents’ chromosomes is picked
randomly and designated a ‘crossover point’. Bits to the right of that point
are swapped between the two parent chromosomes.

  * •

2-point crossover: two crossover points are picked randomly from the parent
chromosomes. The bits in between the two points are swapped between the parent
chromosomes.

  * •

Uniform crossover: each bit is chosen from either parent with equal
probability $0.5$.

The crossover and mutation operations take place classically as well.

The standard genetic algorithm would not account for the budget constraints.
So, at every step of the genetic algorithm, we have to make sure that all
individuals satisfy them. This implies removing from the initial population
all the individuals that violate a constraint. If after crossover the
resulting chromosome does not satisfy a budget constraint, then the operation
is restarted until that is the case. This repetition is also necessary when
applying random mutations to the chromosomes obtained by crossover. The
genetic algorithm used is shown in Algorithm 4.

Algorithm 4 Standard Genetic algorithm

1:create a random initial population that fulfils the constraints

2:for $t$ from $1$ to $n_{\mathrm{generations}}$ do

3: evaluate the fitness $f^{*}(r)$ of each individual $r$

4: let $n$ be the current size of the population, draw $n/2$ pairs of distinct
individuals with probability
$p(r)=\frac{f^{*}(r)}{\sum_{r^{\prime}}f^{*}(r^{\prime})}$ proportional to the
fitness of each individual (an individual may belong to several pairs)

5: generate 2 children per pair by crossover (repeat until each child
satisfies the constraints)

6: apply a mutation to the children (repeat until each child satisfies the
constraints)

7: evaluate the fitness of the children

8: add all the children to the current population

9: select only the fittest $n_{\mathrm{max-population}}$ individuals

10:end for

11:return the individual with the highest fitness

###  5.3 Inner Genetic Algorithms

The genetic algorithm Algorithm 4 requires a) to generate a random population
that fulfils the constraints and b) to generate mutations that keep the
constraints satisfied. We will see that these two mathematical problems are in
fact NP-hard and will thus introduce two additional genetic algorithms to
solve them and nest them inside our outer genetic algorithm. In the overall
algorithm, we will first pre-compute the initial population and set of
mutations using the inner genetic algorithms. Moreover, the mutations will be
applied sequentially on the chromosomes resulting from crossover instead of
just once. Finally, the genetic algorithm will be equipped with an early
stopping policy. The Algorithm 4 modified in this way will be referred to as
_outer_ genetic algorithm.

####  5.3.1 Computation of the Initial Population

For the initial population, we need to find chromosomes that fulfil the two
budget constraints. This is mathematically equivalent to finding binary
vectors $x$ of dimension $M$ that are solutions of the integer system of two
linear inequalities

${{\mathbf{A}}}x\leq b~{},$

where ${{\mathbf{A}}}$ is the integer matrix of size $2\times M$

${{\mathbf{A}}}=\begin{bmatrix}L(R_{1})\dotsc L(R_{M})\\\ E(R_{1})\dotsc
E(R_{M})\end{bmatrix}$

and $b=(B_{c},B_{e})^{\mathrm{T}}$ is the 2-dimensional budget vector. To
obtain solutions, we pick several integer vectors $\beta$ such that
$0\leq\beta\leq b$ and for each $\beta$, we search for exact as well as
approximate solutions of ${{\mathbf{A}}}x=\beta$. All exact solutions,
together with the approximate solutions to ${{\mathbf{A}}}x=\beta$ that also
satisfy ${{\mathbf{A}}}x\leq b$ are then kept as solution of the system and
used to form the initial population of the standard genetic algorithm.

Exact and approximate solutions to ${{\mathbf{A}}}x=\beta$ can be obtained by
minimizing the squared norm of the difference between ${{\mathbf{A}}}x$ and
$\beta$

$\lVert{{\mathbf{A}}}x-\beta\rVert^{2}=({{\mathbf{A}}}x-\beta)^{\mathrm{T}}({{\mathbf{A}}}x-\beta)=x^{\mathrm{T}}({{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}})x-2\beta^{\mathrm{T}}{{\mathbf{A}}}x+\mathrm{cst}~{},$

where $\mathrm{cst}$ is a constant term independent of $x$. Since $x$ is a
binary vector, this is equivalent to the Quadratic Unconstrained Binary
Optimization (QUBO) problem

$\min x^{\mathrm{T}}{{\mathbf{Q}}}_{B}x~{},x\in\\{0,1\\}^{M}$

where ${{\mathbf{Q}}}_{B}$ is the square integer matrix
${{\mathbf{Q}}}_{B}={{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}}-2\mathrm{diag}[\beta^{\mathrm{T}}{{\mathbf{A}}}]$
of size $M\times M$. A sample of $n$ solutions to the QUBOs can be sampled
using a simple genetic algorithm as shown in Algorithm 5. The matrices
${{\mathbf{Q}}}_{B}$ of these QUBOs are of size $M\times M$, where $M$ can in
practice be quite large. This issue can be easily circumvented by generating
small random subsets of $m\leq M$ dimensions and solving the QUBO in the sub-
spaces only. The solutions obtained can be transformed into bit-strings of
length $M$ by adding zeros in the positions of the remaining dimensions. The
union of all solutions obtained in this way constitutes a sample of solutions
of the original QUBO. Our first inner algorithm for generating an initial
population is shown in Algorithm 6.

Algorithm 5 Solves $\min x^{\mathrm{T}}{{\mathbf{Q}}}x~{},x\in\\{0,1\\}^{M}$
by genetic algorithm

1:create $n$ random bit-strings $x$ of length $M$

2:for $t$ from $1$ to $n_{\mathrm{generations}}$ do

3: evaluate the fitness $f(x)=x^{\mathrm{T}}{{\mathbf{Q}}}x$ of each
individual $x$

4: draw $n/2$ pairs of distinct individuals with probability
$p(x)=\frac{f(x)}{\sum_{x^{\prime}}f(x^{\prime})}$ proportional to the fitness
of each individual (an individual may belong to several pairs)

5: generate 2 children per pair by crossover

6: apply a random mutation to the children

7: evaluate the fitness of the children

8: add all the children to the current population

9: select only the fittest $n$ individuals

10:end for

11:return the $n$ individuals of the last generation

Algorithm 6 Solves ${{\mathbf{A}}}x\leq b$ for $x\in\\{0,1\\}^{M}$

1:INPUTS: ${{\mathbf{A}}}\in\mathbb{N}^{M\times 2}$, $b\in\mathbb{N}^{2}$, set
$\mathcal{B}\subseteq\\{\beta\in\mathbb{N}^{2}|0\leq\beta\leq b\\}$

2:OUTPUT: sample of solutions

3:compute the $M\times M$ matrix
${{\mathbf{Q}}}_{I}={{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}}$

4:for $\beta\in\mathcal{B}$ do

5: compute the $M\times M$ matrix
${{\mathbf{Q}}}_{B}={{\mathbf{Q}}}_{I}-2\mathrm{diag}[\beta^{\mathrm{T}}A]$

6: sample solutions of the QUBO $\min x^{\mathrm{T}}{{\mathbf{Q}}}_{B}x$,
$x\in\\{0,1\\}^{M}$ by using Algorithm 5 in parallel on small sub-spaces of
$\\{0,1\\}^{M}$

7: store in $S$ all sampled $x$ that satisfy ${{\mathbf{A}}}x\leq b$

8:end for

9:remove duplicate solutions from $S$

10:return sample of unique solutions

####  5.3.2 Computation of the Set of Mutations

We represent a mutation $m$ by a vector in $\\{-1,0,+1\\}^{M}$ that can
suppress, leave unchanged or activate genes. A chromosome $x$ mutates under
some mutation $m$ into a new chromosome $x\oplus m$ as

$(x\oplus m)_{i}\triangleq\mathrm{clip}(x_{i}+m_{i},0,1)$

where $\mathrm{clip}$ is the clipping function defined as
$\mathrm{clip}(z,a,b)=z$ if $a\leq z\leq b$, $\mathrm{clip}(z,a,b)=a$ if $z<a$
and $\mathrm{clip}(z,a,b)=b$ if $z>b$. Given a solution $x$ of the system
${{\mathbf{A}}}x\leq b$, we want to find mutations $m$ such that $x\oplus m$
is still a solution of the system, i.e. ${{\mathbf{A}}}(x\oplus m)\leq b$. It
is easy to check that $x\oplus m=x+m^{\prime}$ where $m^{\prime}$ is the
vector in $\\{-1,0,+1\\}^{M}$ defined as $m^{\prime}_{i}=+1$ if $x_{i}=0$ and
$m_{i}=1$, $m^{\prime}_{i}=-1$ if $x_{i}=1$ and $m_{i}=-1$, and
$m^{\prime}_{i}=0$ otherwise. For such a vector $m^{\prime}$, we have $x\oplus
m=x\oplus m^{\prime}=x+m^{\prime}$ and consequently

${{\mathbf{A}}}(x\oplus m)={{\mathbf{A}}}(x\oplus
m^{\prime})={{\mathbf{A}}}x+{{\mathbf{A}}}m^{\prime}$

If $m^{\prime}$ is also such that ${{\mathbf{A}}}m^{\prime}\approx 0$, then
${{\mathbf{A}}}(x\oplus m)\approx{{\mathbf{A}}}x$, so there is a chance that
$x\oplus m^{\prime}$ still satisfies the inequality system
${{\mathbf{A}}}(x\oplus m^{\prime})\leq b$. In summary, we can obtain good
candidates for the mutations by finding elements of the approximate kernel of
the integer matrix ${{\mathbf{A}}}$ in $\\{-1,0,+1\\}^{M}$.

We can solve ${{\mathbf{A}}}x\approx 0$ for $x\in\\{-1,0,+1\\}^{M}$ using
again a genetic algorithm. Since each component $x_{i}\in\\{-1,0,+1\\}$ of the
variable $x$ may take three possible values, its encoding requires a minimum
of two binary variables. We thus encode each $x_{i}$ over two binary variables
$b_{i,1}$ and $b_{i,2}$ by writing $x_{i}=-1+b_{i,1}+2b_{i,2}$. It is easy to
check that the encoding is such that $(b_{i,1},b_{i,2})$ is mapped as follows:
$(0,0)\mapsto-1,(1,0)\mapsto 0$ and $(0,1)\mapsto+1$. Our linear encoding can
be also written in matrix form:

$x=L+{{\mathbf{E}}}X=L+(I_{M}\otimes[1,2])X=\begin{bmatrix}-1\\\ -1\\\
\vdots\\\ -1\end{bmatrix}+\begin{bmatrix}1&2&0&0&0&\dotsc&0\\\
0&0&1&2&0&\dotsc&0\\\ \vdots&\\\
0&\dotsc&&&0&1&2\end{bmatrix}\begin{bmatrix}b_{1,1}\\\ b_{1,2}\\\ b_{2,1}\\\
b_{2,2}\\\ \vdots\\\ b_{M,1}\\\ b_{M,2}\end{bmatrix}$

where $L$ is the $M$-dimensional vector $-1=[-1,\dotsc,-1]$, $X$ is the
encoding binary vector of dimension $2M$ obtained by staking all encoding bits
$b_{i,1}$ and $b_{i,2}$, $\otimes$ is the Kronecker product and
${{\mathbf{E}}}={{\mathbf{I}}}_{M}\otimes[1,2]$ is the $M\times(2M)$ encoder
matrix and ${{\mathbf{I}}}_{M}$ the identity matrix of dimension $M$.

Exact and approximate solutions to ${{\mathbf{A}}}x=0$ can be obtained by
minimizing the squared norm of ${{\mathbf{A}}}x$

$\lVert{{\mathbf{A}}}x\rVert^{2}=({{\mathbf{A}}}(L+{{\mathbf{E}}}X))^{\mathrm{T}}{{\mathbf{A}}}(L+{{\mathbf{E}}}X)=X^{\mathrm{T}}{{\mathbf{E}}}^{\mathrm{T}}{{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}}{{\mathbf{E}}}X+2L^{\mathrm{T}}{{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}}{{\mathbf{E}}}X+\mathrm{cst}~{}.$

Since $X$ is a binary vector this is equivalent to the QUBO problem

$\min X^{\mathrm{T}}{{\mathbf{Q}}}_{B}X,X\in\\{0,1\\}^{2M}~{},$

where ${{\mathbf{Q}}}_{B}$ is the $2M\times 2M$ square matrix
${{\mathbf{Q}}}_{B}={{\mathbf{E}}}^{\mathrm{T}}Q_{I}{{\mathbf{E}}}+2\mathrm{diag}[L^{\mathrm{T}}{{\mathbf{Q}}}_{I}{{\mathbf{E}}}]$
and as previously
${{\mathbf{Q}}}_{I}={{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}}$. Additional
approximate kernel elements can be obtained by closing the sampled approximate
kernel under the multiplication by $-1$. Indeed, if ${{\mathbf{A}}}x\approx
0$, then ${{\mathbf{A}}}(-x)\approx 0$. The approximate kernel of $A$ is
computed using Algorithm 7.

Algorithm 7 Solves ${{\mathbf{A}}}x\approx 0$ for $x\in\\{-1,0,+1\\}^{M}$

1:INPUTS: ${{\mathbf{A}}}\in\mathbb{N}^{2\times M}$

2:OUTPUT: sample of solutions from the approximate kernel of ${{\mathbf{A}}}$

3:compute the $M\times M$ matrix
${{\mathbf{Q}}}_{I}={{\mathbf{A}}}^{\mathrm{T}}{{\mathbf{A}}}$

4:compute the $M\times(2M)$ encoder matrix:
${{\mathbf{E}}}={{\mathbf{I}}}_{M}\otimes[1,2]$

5:compute the $2M\times 2M$ matrix
${{\mathbf{Q}}}_{B}={{\mathbf{E}}}^{\mathrm{T}}{{\mathbf{Q}}}_{I}{{\mathbf{E}}}+2\mathrm{diag}[L^{\mathrm{T}}{{\mathbf{Q}}}_{I}{{\mathbf{E}}}]$

6:sample solutions of the QUBO $\min X^{\mathrm{T}}{{\mathbf{Q}}}_{B}X$,
$X\in\\{0,1\\}^{2M}$ using Algorithm 5

7:decode optimal and approximate binary vectors $X$ using
$x=L+{{\mathbf{E}}}X\in\mathbb{Z}^{M}$

8:store in $S$ all such $x$ that satisfy $-1\leq x\leq 1$

9:close $S$ under multiplication by $-1$

10:remove duplicate solutions from $S$

11:return $S$

####  5.3.3 Super-mutations

In the standard genetic algorithm (Algorithm 4), a random mutation is applied
to a chromosome $x$ such that the mutated chromosome fulfils the budget
constraints. The mutated chromosome $r$ does not necessarily have a higher
fitness. Mutations are applied differently in the case of the nested genetic
algorithm. Since the mutations $m$ pre-generated using the inner genetic
algorithm Algorithm 7 have a higher chance of preserving the feasibility of
the solution $r$, we can impose that $m$ increases the fitness, i.e.
$f^{*}(r\oplus m)>f^{*}(r)$. We may refer to such mutations as _augmenting_
mutations. And instead of applying a single mutation after each crossover, we
may apply a sequence $m_{1},\dotsc,m_{n}$ of augmenting mutations such that

$f^{*}(r)<f^{*}(r\oplus m_{1})<f^{*}(r\oplus m_{1}\oplus
m_{2})<\dotsc<f^{*}(r\oplus m_{1}\oplus\dotsc\oplus m_{n})$

and stop applying mutations whenever the pre-generated mutations cannot
augment the fitness value anymore. We introduce the concept of _super-
mutation_ to denote a maximal sequence of augmenting mutations. Super-
mutations can be seen as an augmentation procedure or hill-climbing method
applied to each chromosome obtained by crossover.

####  5.3.4 Early Stopping Policy

The classical genetic algorithm is run for a predetermined number of
generations. In the nested genetic algorithm, super-mutations are used and
cause the genetic _diversity_ (population size when redundant chromosomes are
removed) to shrink rapidly. Indeed, all chromosomes obtained by crossover are
subject to super-mutations, and we observe experimentally that they converge
to a smaller number of local maxima (top of the hills). Thus, the genetic
diversity decreases quickly to $1$, which means that all individuals become
genetically identical to one individual that we may call the “dominating
mutant”. This can be easily detected without comparing the individuals’
chromosome, but by checking that their fitness value is the same for all
individuals. After this point, the crossover operation results in identical
offspring and mutations cannot further improve the fitness value anymore. We
thus stop the nested genetic algorithm as soon as i) the minimum and maximum
fitness values in the population are equal, ii) the pre-specified number of
generations is reached or iii) we find an individual with maximal fitness
score of $100\%$. The nested genetic algorithm finally obtained is provided
for clarity in Algorithm 8. We refer to the nested genetic algorithm as
_Quadratic Genetic Algorithm_ , abbreviated as “QGA” due to its double use of
Quadratic Unconstrained Binary Optimization (QUBO) models.

Algorithm 8 Quadratic Genetic Algorithm

1:create an initial population that fulfils the constraints using the inner
genetic algorithm Algorithm 6

2:compute a set of mutations using the inner genetic algorithm Algorithm 7

3:for $t$ from $1$ to $n_{\mathrm{generations}}$ do

4: evaluate the fitness $f^{*}(r)$ of each individual $r$

5: let $n$ be the current size of the population, draw $n/2$ pairs of distinct
individuals with probability
$p(r)=\frac{f^{*}(r)}{\sum_{r^{\prime}}f^{*}(r^{\prime})}$ proportional to the
fitness of each individual (an individual may belong to several pairs)

6: generate 2 children per pair by crossover (repeat until each child
satisfies the constraints)

7: apply a mutation to the children (repeat until each child satisfies the
constraints)

8: repeat for each child the previous step until there is no mutation that can
strictly increase its fitness (super mutation)

9: add all the children to the current population

10: select only the fittest $n_{\mathrm{max-population}}$ individuals

11: exit the for loop if the minimum and maximum fitness values in the
population are equal or if we the maximum fitness score is $100\%$

12:end for

13:return the individual with the highest fitness

##  6 Experiments

In this section, we describe how the data sets have been selected, the setting
used for generating decision rules, how the budget constraints are fixed,
summarise performance results and plot the evolution of the fitness value in
the quadratic genetic algorithm.

###  6.1 Data Sets

To evaluate the nested genetic algorithm, we compare its performance with
other approaches on public data sets from the UCI Machine Learning repository
Dua:2019 . The data sets used must be classification data sets available in
tabular form. Since we want the data sets to be explained using sufficiently
simple decision rules, we filter for data sets from the repository with a
sufficiently small number of attributes (16). As the number of rules required
for an explanation increases with the number of classes, we also limit
ourselves to data sets with a small number of classes (8). To keep the
computation time reasonable, we picked data sets with less than 1,500
instances. From the remaining data sets available, we chose those that could
directly be imported without pre-processing work. The left hand side of Table
2 shows the data sets used for the experiments and their respective number
number of instances, attributes and classes.

Table 2: Data sets and setting used in experiments. data set | Instances | Attributes | Classes | Depth | Trees | Rules
---|---|---|---|---|---|---
Iris | 150 | 4 | 3 | 3 | 24 | 64
Wine | 178 | 13 | 3 | 5 | 48 | 285
Zoo | 101 | 16 | 7 | 5 | 48 | 236
Breast cancer | 699 | 10 | 2 | 5 | 48 | 310
Banknote | 1372 | 4 | 2 | 5 | 48 | 285
Hayes-Roth | 160 | 5 | 3 | 8 | 84 | 1015
Mammographic mass | 961 | 5 | 2 | 7 | 72 | 1247
Blood transfusion | 748 | 5 | 3 | 8 | 84 | 825
Ecoli | 336 | 7 | 8 | 6 | 60 | 587
Tic-tac-toe | 958 | 9 | 2 | 10 | 108 | 5575

###  6.2 Setting used for Generating Decision Rules

For each data set, we train several decision trees using the CART algorithm
implemented in Python’s scikit-learn. The hyper-parameter combinations used
for the CART algorithm are those that have been exposed in Table 1. The
maximum depth for the trees trained ranges from 1 to the number indicated in
the column “Depth” of Table 2. This number was adjusted manually depending on
the intrinsic complexity of each data set. For each hyper-parameter
combination, one tree is trained and the total number of decision trees
trained for each data set is shown is the column “Trees”. All trees are
transformed into decision rules, which are simplified whenever possible by
merging conditions on the same features. Decision rules that are redundant in
the sense of yielding the same predictions on the data set were removed. The
final number of decision rules obtained is indicated in the last column
“Rules” and is comprised between $M=64$ and $M=5575$.

###  6.3 Choice of the Complexity and Error Budgets

For each data set, we compute the complexity of the set of decision rules
obtained from each decision tree. We call _best tree_ , the tree that achieves
the minimum complexity after simplification of the rules. For this set of
decision rules, the coverage score is guaranteed to be $100\%$. Let then
$c^{*}$ and $e^{*}$ be the complexity and number of classification errors of
the rule set obtained with the best tree. To make the problem challenging, we
then set the complexity budget $B_{c}$ strictly below $c^{*}$ and the error
budget below $e^{*}$: $B_{c}<c^{*}$ and $B_{e}\leq e^{*}$. The budgets chosen
for each data set are indicated after the slash character in the columns
“Complexity” and “Errors” of Table 3.

###  6.4 Performance Results

For each data set, we evaluate the performance of four algorithms, namely the
adaptations of RF+HC and IRFRE, an improvement of the adapted version of IRFRE
called IRFRE RF+HC whereby all the results of RF+HC are added to the initial
population of the multi-objective genetic algorithm and the nested genetic
algorithm (QGA). For each run of these algorithms, we measure the complexity
and number of classification errors of the rule set, the computation time and
the coverage score. Since the outcomes are all random, we average the
measurements over 30 runs. The results are shown in Table 3 and Figure 3 and
can be interpreted as follows.

Table 3: Averaged results obtained over 30 runs. Data set | Algorithm | Complexity | Errors | Time | Coverage %
---|---|---|---|---|---
Iris | RF+HC | 4.0 / 4 | 3.0 / 5 | 3.3s |  91.0($\pm$4.7)
| IRFRE | 3.6 / 4 | 2.2 / 5 | 9.2s |  56.4($\pm$9.1)
| IRFRE RF+HC | 4.0 / 4 | 3.0 / 5 | 18.0s |  91.0($\pm$4.7)
| QGA | 4.0 / 4 | 2.1 / 5 | 72.5s |  93.8($\pm$0.9)
Wine | RF+HC | 8.0 / 8 | 7.5 / 9 | 6.0s |  90.8($\pm$2.5)
| IRFRE | 6.9 / 8 | 5.4 / 9 | 12.4s |  66.7($\pm$8.9)
| IRFRE RF+HC | 8.0 / 8 | 7.5 / 9 | 22.2s |  90.8($\pm$2.5)
| QGA | 7.7 / 8 | 8.1 / 9 | 90.8s |  94.9($\pm$1.0)
Zoo | RF+HC | 17.3 / 18 | 7.9 / 8 | 2.1s |  96.2($\pm$1.5)
| IRFRE | 7.8 / 18 | 5.2 / 8 | 9.5s |  61.5($\pm$4.3)
| IRFRE RF+HC | 17.3 / 18 | 7.9 / 8 | 19.1s |  96.2($\pm$1.5)
| QGA | 17.1 / 18 | 7.8 / 8 | 82.6s |  98.2($\pm$1.3)
Breast cancer | RF+HC | 19.5 / 20 | 29.7 / 30 | 18.6s |  96.6($\pm$0.8)
| IRFRE | 12.3 / 20 | 23.7 / 30 | 46.0s |  89.0($\pm$1.9)
| IRFRE RF+HC | 19.5 / 20 | 29.7 / 30 | 83.7s |  96.6($\pm$0.8)
| QGA | 18.5 / 20 | 28.6 / 30 | 117.1s |  98.3($\pm$0.3)
Banknote | RF+HC | 22.6 / 23 | 34.1 / 35 | 24.3s |  96.3($\pm$1.2)
| IRFRE | 11.0 / 23 | 21.5 / 35 | 51.4s |  64.9($\pm$6.9)
| IRFRE RF+HC | 22.6 / 23 | 34.1 / 35 | 90.9s |  96.3($\pm$1.2)
| QGA | 22.6 / 23 | 31.7 / 35 | 111.9s |  98.5($\pm$0.3)
Hayes-Roth | RF+HC | 73.4 / 74 | 13.9 / 14 | 15.7s |  89.2($\pm$2.7)
| IRFRE | 39.9 / 74 | 12.5 / 14 | 23.8s |  46.7($\pm$4.4)
| IRFRE RF+HC | 73.4 / 74 | 13.9 / 14 | 36.8s |  89.2($\pm$2.7)
| QGA | 69.5 / 74 | 13.8 / 14 | 136.2s |  98.0($\pm$1.4)
Mammographic mass | RF+HC | 89.2 / 90 | 150.0 / 150 | 347.3s |  94.9($\pm$2.0)
| IRFRE | 46.6 / 90 | 136.1 / 150 | 453.7s |  81.9($\pm$4.2)
| IRFRE RF+HC | 89.2 / 90 | 150.0 / 150 | 601.5s |  94.9($\pm$2.0)
| QGA | 84.6 / 90 | 148.7 / 150 | 690.9s |  97.3($\pm$1.5)
Blood transfusion | RF+HC | 96.4 / 100 | 150.0 / 150 | 231.6s |  97.9($\pm$0.6)
| IRFRE | 40.1 / 100 | 141.4 / 150 | 340.4s |  84.4($\pm$2.8)
| IRFRE RF+HC | 96.4 / 100 | 150.0 / 150 | 480.3s |  97.9($\pm$0.6)
| QGA (simulator) | 96.9 / 100 | 149.4 / 150 | 298.0s |  99.1($\pm$0.3)
Ecoli | RF+HC | 107.5 / 113 | 31.0 / 31 | 26.4s |  96.1($\pm$1.1)
| IRFRE | 24.4 / 113 | 24.8 / 31 | 42.3s |  66.0($\pm$3.6)
| IRFRE RF+HC | 107.5 / 113 | 31.0 / 31 | 67.3s |  96.1($\pm$1.1)
| QGA | 106.3 / 113 | 30.4 / 31 | 183.2s |  98.3($\pm$0.7)
Tic-tac-toe | RF+HC | 96.3 / 150 | 70.0 / 70 | 29.0s |  78.4($\pm$0.8)
| IRFRE | 14.4 / 150 | 62.8 / 70 | 48.9s |  39.5($\pm$2.5)
| IRFRE RF+HC | 96.3 / 150 | 70.0 / 70 | 80.8s |  78.4($\pm$0.8)
| QGA | 112.9 / 150 | 69.5 / 70 | 113.4s |  82.3($\pm$1.4)

(a)  (b)  (c)  (d)  (e)  (f)  (g)  (h)  (i)  (j)

Figure 3: Performance of the selection algorithms.From left to right: RF+HC
(pink), IRFRE (blue), IRFRE RF+HC (green) and QGA (orange).

The RF+HC method is fast and achieves in all cases a high coverage score. The
IRFRE method yields feasible solutions but low coverage scores. The IRFRE
RF+HC method is significantly better than IRFRE in terms of coverage score,
but no better than RF+HC. This happens because the evolutionary process of the
multi-objective genetic algorithm does not work as expected. Indeed, the
chromosomes resulting from crossover and random mutations are rarely feasible
solutions, and when they are, they do not offer any improvement of the fitness
value. Thus, both in IRFRE and IRFRE RF+HC, the population remains unchanged
after each generation. This issue is resolved by our nested genetic algorithm,
which is able to improve on the RF+HC solutions injected in the initial
population and allows to reach averaged coverage scores comprised between $90$
and $98.6\%$. The inner genetic algorithms offer better sampling of the
solutions of the inequality system ${{\mathbf{A}}}x\leq b$ and approximate
kernel ${{\mathbf{A}}}x\approx 0$, resulting in higher coverage scores whilst
reducing the computation time.

###  6.5 Fitness Evolution in the QGA

For each of the data sets, we show in Figure 4 the evolution of the fitness
score of the population in each generation. For each population and
generation, we keep track of the minimum, average and maximum fitness of
individuals in the population. All curves show an increase over time until
termination (when the maximum number of generations is reached, when the
minimum and maximum fitness are equal or when the maximum fitness score has
reached $100\%$).

(a) Iris (b) Wine (c) Zoo (d) Breast Cancer Wisconsin (e) Banknote
Authentication (f) Hayes-Roth (g) Mammographic Mass (h) Blood Transfusion (i)
Ecoli (j) Tic-tac-toe

Figure 4: Evolution of the fitness score with the quadratic genetic algorithm.

##  7 Explanations of the Data Sets

In Appendix A, we introduce each data set and show the rule set with highest
coverage score obtained out of the 30 runs of the nested genetic algorithm
QGA.

##  8 Conclusion

Our goal was to explain classification data sets. We have formulated the
problem of selecting an optimal rule set as a budgeted maximum coverage
problem. This problem is chalenging, because it involves searching over
exponentially many possible sets of rules. We have designed a nested genetic
algorithm baptised Quadratic Genetic Algorithm to solve the problem and have
used the RF+HC method to efficiently compute an initial population, which has
then been expanded using an inner genetic algorithm. More importantly, a
second inner genetic algorithm has allowed us to find mutations that enable
the evolutionary process. We have achieved high coverage scores even with a
budget for complexity and errors lower than what the best decision tree
requires. We have provided explanations for 10 public classification data sets
and demonstrated that the genetic algorithm offered a scalable approach to
this problem.

## References

  *   * (1) Samuel, A.: Some studies in machine learning using the game of checkers. Reprinted in EA Feigenbaum & J. Feldman (Eds.)(1963). Computers and thought. McGraw-Hill (1959)
  * (2) LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. nature 521(7553), 436–444 (2015)
  * (3) Guidotti, R., Monreale, A., Ruggieri, S., Turini, F., Giannotti, F., Pedreschi, D.: A survey of methods for explaining black box models. ACM computing surveys (CSUR) 51(5), 1–42 (2018)
  * (4) Molnar, C.: Interpretable machine learning. Lulu. com (2020)
  * (5) Samek, W., Montavon, G., Vedaldi, A., Hansen, L.K., Müller, K.-R.: Explainable AI: interpreting, explaining and visualizing deep learning. Springer (2019)
  * (6) Xu, F., Uszkoreit, H., Du, Y., Fan, W., Zhao, D., Zhu, J.: Explainable ai: A brief survey on history, research areas, approaches and challenges. In: CCF International Conference on Natural Language Processing and Chinese Computing, pp. 563–574 (2019). Springer
  * (7) Burkart, N., Huber, M.F.: A survey on the explainability of supervised machine learning. Journal of Artificial Intelligence Research 70, 245–317 (2021)
  * (8) Gunning, D., Stefik, M., Choi, J., Miller, T., Stumpf, S., Yang, G.-Z.: Xai—explainable artificial intelligence. Science robotics 4(37), 7120 (2019)
  * (9) Vale, D., El-Sharif, A., Ali, M.: Explainable artificial intelligence (xai) post-hoc explainability methods: Risks and limitations in non-discrimination law. AI and Ethics, 1–12 (2022)
  * (10) Rudin, C.: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence 1(5), 206–215 (2019)
  * (11) Vasic, M., Petrovic, A., Wang, K., Nikolic, M., Singh, R., Khurshid, S.: Moët: Interpretable and verifiable reinforcement learning via mixture of expert trees (2019)
  * (12) Wang, T., Rudin, C., Doshi-Velez, F., Liu, Y., Klampfl, E., MacNeille, P.: A bayesian framework for learning rule sets for interpretable classification. The Journal of Machine Learning Research 18(1), 2357–2393 (2017)
  * (13) Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Information processing letters 70(1), 39–45 (1999)
  * (14) Panchal, G., Panchal, D.: Solving NP hard problems using genetic algorithm. Transportation 106, 6–2 (2015)
  * (15) Adnan, N., Islam, Z.: Forex++: A new framework for knowledge discovery from decision forests. Australasian Journal of Information Systems 21 (2017). https://doi.org/10.3127/ajis.v21i0.1539
  * (16) Mashayekhi, M., Gras, R.: Rule extraction from random forest: the rf+hc methods. In: Barbosa, D., Milios, E. (eds.) Advances in Artificial Intelligence, pp. 223–237. Springer, Cham (2015)
  * (17) Wang, S., Wang, Y., Wang, D., Yin, Y., Wang, Y., Jin, Y.: An improved random forest-based rule extraction method for breast cancer diagnosis. Applied Soft Computing 86, 105941 (2020). https://doi.org/10.1016/j.asoc.2019.105941
  * (18) Fonseca, C.M., Fleming, P.J.: Multiobjective genetic algorithms. In: IEE Colloquium on Genetic Algorithms for Control Systems Engineering, pp. 6–1 (1993). Iet
  * (19) Izza, Y., Ignatiev, A., Marques-Silva, J.: On explaining decision trees. arXiv preprint arXiv:2010.11034 (2020)
  * (20) Izza, Y., Ignatiev, A., Marques-Silva, J.: On tackling explanation redundancy in decision trees. arXiv preprint arXiv:2205.09971 (2022)
  * (21) Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., Schaus, P.: Learning optimal decision trees using constraint programming. Constraints 25(3), 226–250 (2020)
  * (22) Alos, J., Ansotegui, C., Torres, E.: Learning optimal decision trees using maxsat. arXiv preprint arXiv:2110.13854 (2021)
  * (23) Demirović, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., Stuckey, P.J.: Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research 23(26), 1–47 (2022)
  * (24) Lakkaraju, H., Bach, S.H., Leskovec, J.: Interpretable decision sets: A joint framework for description and prediction. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1675–1684 (2016)
  * (25) Borgelt, C.: An implementation of the FP-growth algorithm. In: Proceedings of the 1st International Workshop on Open Source Data Mining: Frequent Pattern Mining Implementations, pp. 1–5 (2005)
  * (26) Goldberg, D.E.: Genetic algorithms in search, optimization, and machine learning. addison. Reading (1989)
  * (27) Dua, D., Graff, C.: UCI Machine Learning Repository (2017). http://archive.ics.uci.edu/ml
  * (28) Hayes-Roth, B., Hayes-Roth, F.: Concept learning and the recognition and classification of exemplars. Journal of Verbal Learning and Verbal Behavior 16(3), 321–338 (1977)

##  Appendix A Explanation of the Data Sets

####  A.0.1 Iris Data Set

This is perhaps the best known data set to be found in the pattern recognition
literature. The data set contains 3 classes of 50 instances each, where each
class refers to a type of iris plant: setosa, versicolor or virginica. There
are 4 continuous attributes:

  * •

sepal length in cm

  * •

sepal width in cm

  * •

petal length in cm

  * •

petal width in cm

The data set can be found here444https://archive.ics.uci.edu/ml/datasets/iris.
The explanation is printed in Figure 5. It is composed of 3 rules and has a
complexity of 4, $94\%$ coverage and 2 classification errors.

    IF petal length <= 2.45 THEN CLASS=Iris-setosa
    IF petal width > 0.8 AND petal length <= 4.75 THEN CLASS=Iris-versicolor
    IF petal width > 1.75 THEN CLASS=Iris-virginica

Figure 5: Explanation of the Iris data set.

####  A.0.2 Wine Data Set

These data are the results of a chemical analysis of 178 wines grown in the
same region in Italy but derived from 3 different cultivars. The analysis
determined the quantities of 12 constituents found in each of the three types
of wines. The 12 attributes are:

  * •

Malic acid

  * •

Ash

  * •

Alcalinity of ash

  * •

Magnesium

  * •

Total phenols

  * •

Flavanoids

  * •

Nonflavanoid phenols

  * •

Proanthocyanins

  * •

Color intensity

  * •

Hue

  * •

OD280/OD315 of diluted wines

  * •

Proline

The class is an integer that represents the cultivar. The data set can be
found here555https://archive.ics.uci.edu/ml/datasets/wine. The explanation is
printed in Figure 6. It is composed of 3 rules, has a complexity of 8, a
coverage of $96.1\%$ and $8$ classification errors.

    IF hue > 0.785 AND color intensity > 3.46 AND flavanoids > 2.11 THEN CLASS=1
    IF color intensity > 3.82 AND flavanoids <= 1.58 AND alcalinity > 17.15 THEN CLASS=3
    IF color intensity <= 3.82 AND OD280/OD135 <= 3.73 THEN CLASS=2

Figure 6: Explanation of the Wine data set.

####  A.0.3 Zoo Data Set

This is a simple data set containing 101 animals split in 7 classes. Here is a
breakdown of the animals in each class:

  1. 1.

Aardvark, antelope, bear, boar, buffalo, calf, cavy, cheetah, deer, dolphin,
elephant, fruitbat, giraffe, girl, goat, gorilla, hamster, hare, leopard,
lion, lynx, mink, mole, mongoose, opossum, oryx, platypus, polecat, pony,
porpoise, puma, pussycat, raccoon, reindeer, seal, sealion, squirrel, vampire,
vole, wallaby, wolf

  2. 2.

Chicken, crow, dove, duck, flamingo, gull, hawk, kiwi, lark, ostrich,
parakeet, penguin, pheasant, rhea, skimmer, skua, sparrow, swan, vulture, wren

  3. 3.

Pitviper, seasnake, slowworm, tortoise, tuatara

  4. 4.

Bass, carp, catfish, chub, dogfish, haddock, herring, pike, piranha, seahorse,
sole, stingray, tuna

  5. 5.

Frog, newt, toad

  6. 6.

Flea, gnat, honeybee, housefly, ladybird, moth, termite, wasp

  7. 7.

Clam, crab, crayfish, lobster, octopus, scorpion, seawasp, slug, starfish,
worm

The 17 attributes are:

  * •

hair: Boolean

  * •

feathers: Boolean

  * •

eggs: Boolean

  * •

milk: Boolean

  * •

airborne: Boolean

  * •

aquatic: Boolean

  * •

predator: Boolean

  * •

toothed: Boolean

  * •

backbone: Boolean

  * •

breathes: Boolean

  * •

venomous: Boolean

  * •

fins: Boolean

  * •

legs: 0, 2, 4, 6, 8

  * •

tail: Boolean

  * •

domestic: Boolean

  * •

catsize: Boolean

The data set is described and can be downloaded
here666https://archive.ics.uci.edu/ml/datasets/zoo. The explanation is printed
in Figure 7. It is composed of 7 rules, has a complexity of 18, a coverage of
100% and 8 classification errors.

    IF milk <= 0.5 AND feathers > 0.5 THEN CLASS=2
    IF milk > 0.5 THEN CLASS=1
    IF hair > 0.5 AND milk <= 0.5 THEN CLASS=6
    IF milk <= 0.032 AND fins <= 0.764 AND breathes > 0.205 AND toothed > 0.563 THEN CLASS=5
    IF breathes <= 0.371 AND backbone <= 0.101 THEN CLASS=7
    IF toothed > 0.5 AND hair <= 0.5 AND breathes <= 0.5 THEN CLASS=4
    IF milk <= 0.5 AND feathers <= 0.5 AND toothed <= 0.5 AND breathes > 0.5 THEN CLASS=6

Figure 7: Explanation of the Zoo data set.

####  A.0.4 Breast Cancer Wisconsin (Original) Data Set

This data set is composed of 699 clinical exams of cells (cytology) used for
breast cancer diagnosis. The 9 attributes are the following cytological
characteristics:

  * •

Clump Thickness: 1 - 10

  * •

Uniformity of Cell Size: 1 - 10

  * •

Uniformity of Cell Shape: 1 - 10

  * •

Marginal Adhesion: 1 - 10

  * •

Single Epithelial Cell Size: 1 - 10

  * •

Bare Nuclei: 1 - 10

  * •

Bland Chromatin: 1 - 10

  * •

Normal Nucleoli: 1 - 10

  * •

Mitoses: 1 - 10

The 2 classes are 2=“benign” and 4=“malignant”.

The data set is described and can be downloaded
here777https://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+(original).
The explanation is printed in Figure 8. The explanation is composed of 8
rules, has a complexity of 16, a coverage of $98.9\%$ and 28 classification
errors.

    IF bland chromatin <= 3.5 AND clump thickness <= 6.5 THEN CLASS=2
    IF bland chromatin > 7.5 THEN CLASS=4
    IF clump thickness > 6.409 THEN CLASS=4
    IF clump thickness <= 4.612 AND adhesion <= 1.843 THEN CLASS=2
    IF bland chromatin > 3.5 AND uniformity cell size > 4.5 THEN CLASS=4
    IF bland chromatin > 3.5 AND clump thickness > 4.5 AND uniformity cell size <= 4.5 THEN CLASS=4
    IF bland chromatin > 3.5 AND bare nuclei_10 > 0.5 THEN CLASS=4
    IF uniformity cell shape <= 2.5 AND bland chromatin > 3.5 AND bare nuclei_1 > 0.5 THEN CLASS=2

Figure 8: Explanation of the Breast cancer Wisconsin data set.

####  A.0.5 Banknote Authentication Data Set

Data were extracted from images that were taken from 1372 genuine and forged
banknote-like specimens. For digitization, an industrial camera usually used
for print inspection was used. The final images have 400x400 pixels. Due to
the object lens and distance to the investigated object gray-scale pictures
with a resolution of about 660 dpi were gained. Wavelet Transform tool were
used to extract features from images. The 4 attributes are:

  * •

variance of Wavelet Transformed image (continuous)

  * •

skewness of Wavelet Transformed image (continuous)

  * •

curtosis of Wavelet Transformed image (continuous)

  * •

entropy of image (continuous)

The class is a Boolean describing if the banknotes are authentic or not. The
data set is described and can be downloaded
here888https://archive.ics.uci.edu/ml/datasets/banknote+authentication. The
explanation is printed in Figure 9. The explanation is composed of $10$ rules,
has a complexity of $23$, a coverage of $99.6\%$ and $33$ errors.

    IF skewness > 5.21 AND variance > -3.368 THEN CLASS=0
    IF skewness > 5.161 AND variance > -3.368 THEN CLASS=0
    IF skewness <= 5.161 AND variance > 0.32 AND curtosis <= -1.44 THEN CLASS=1
    IF skewness <= 5.161 AND variance > 0.32 AND curtosis > -1.44 THEN CLASS=0
    IF curtosis > 2.448 AND variance <= 0.323 AND skewness <= 0.667 THEN CLASS=1
    IF curtosis > 2.448 AND variance <= 0.323 AND skewness > 0.667 THEN CLASS=0
    IF curtosis > 2.448 AND variance > 0.323 THEN CLASS=0
    IF variance <= -4.417 THEN CLASS=1
    IF variance <= 0.32 AND skewness <= 5.865 AND curtosis <= 6.219 THEN CLASS=1
    IF variance > 6.079 THEN CLASS=0

Figure 9: Explanation of the Banknote authentication data set.

####  A.0.6 Hayes-Roth Data Set

This data set contains 160 instances split into 3 classes. It has 3
attributes.

  * •

age: categorical values ranging between 1 and 4 (30, 40, 50, 60 years old)

  * •

educational level: categorical values ranging between 1 and 4 (junior high,
high school, trade school, college)

  * •

marital status: categorical values ranging between 1 and 4 (single, married,
divorced, widowed)

The class is an integer between 1 and 3 representing the membership of
individuals that belong to Club 1, Club 2 or neither. The data set
hayes1977concept  is described and can be downloaded
here999https://archive.ics.uci.edu/ml/datasets/Hayes-Roth. The explanation is
printed in Figure 10. The explanation is composed of $17$ rules, has a
complexity of $67$, a coverage of $100\%$ and $14$ classification errors.

    IF educational level > 3.5 THEN CLASS=3
    IF age > 3.5 THEN CLASS=3
    IF age <= 3.5 AND educational level > 3.5 THEN CLASS=3
    IF age <= 3.5 AND marital status > 3.5 THEN CLASS=3
    IF age <= 3.5 AND educational level <= 3.5 AND marital status <= 3.5 AND marital status > 1.5 AND age > 1.5 THEN CLASS=2
    IF age <= 3.5 AND educational level <= 3.5 AND marital status <= 3.5 AND educational level <= 1.5 AND marital status <= 1.5
    THEN CLASS=1
    IF age <= 1.5 AND educational level <= 3.5 AND marital status <= 3.5 AND educational level <= 1.5 AND marital status > 1.5
    THEN CLASS=1
    IF marital status > 3.5 THEN CLASS=3
    IF marital status <= 3.5 AND name > 117.5 AND educational level > 2.5 THEN CLASS=1
    IF name <= 88.5 AND marital status <= 3.5 AND marital status <= 1.5 AND name > 82.0 AND educational level <= 3.0 THEN CLASS=2
    IF marital status <= 1.618 AND educational level > 2.35 AND hobby > 1.1 AND educational level <= 3.077 AND name <= 106.44
    THEN CLASS=1
    IF marital status > 2.123 AND age <= 1.397 AND hobby <= 2.969 AND marital status <= 3.321 AND name > 69.613 THEN CLASS=1
    IF educational level <= 2.541 AND age <= 3.204 AND marital status <= 1.071 AND educational level > 1.123 AND age <= 1.31
    THEN CLASS=1
    IF educational level <= 2.541 AND age <= 3.204 AND marital status <= 1.071 AND educational level > 1.123 AND age > 1.31
    THEN CLASS=2
    IF age <= 2.571 AND marital status <= 2.178 AND marital status <= 1.484 AND age > 1.34 AND name <= 99.674 AND
    educational level <= 3.926 AND educational level <= 1.61 THEN CLASS=1
    IF educational level <= 3.5 AND age <= 3.5 AND name > 117.5 AND marital status > 3.5 THEN CLASS=3
    IF age <= 1.5 AND marital status <= 3.5 AND marital status > 1.5 AND educational level <= 3.5 AND educational level > 1.5 AND
    name <= 117.5 THEN CLASS=2

Figure 10: Explanation of the Hayes-Roth data set.

####  A.0.7 Mammographic Mass Data Set

Mammography is the most effective method for breast cancer screening available
today. However, the low positive predictive value of breast biopsy resulting
from mammogram interpretation leads to approximately 70% of unnecessary
biopsies with benign outcomes. To reduce the high number of unnecessary breast
biopsies, several computer-aided diagnosis (CAD) systems have been proposed in
the last years. These systems help physicians in their decision to perform a
breast biopsy on a suspicious lesion seen in a mammogram or to perform a short
term follow-up examination instead. This data set can be used to predict the
severity (benign or malignant) of a mammographic mass lesion from BI-RADS
attributes and the patient’s age. It contains a BI-RADS assessment, the
patient’s age and three BI-RADS attributes together with the ground truth (the
severity field) for 516 benign and 445 malignant masses that have been
identified on full field digital mammograms collected at the Institute of
Radiology of the University Erlangen-Nuremberg between 2003 and 2006. Each
instance has an associated BI-RADS assessment ranging from 1 (definitely
benign) to 5 (highly suggestive of malignancy) assigned in a double-review
process by physicians. Assuming that all cases with BI-RADS assessments
greater or equal a given value (varying from 1 to 5), are malignant and the
other cases benign, sensitivities and associated specificities can be
calculated. These can be an indication of how well a CAD system performs
compared to the radiologists.

The 5 attributes used are:

  * •

BI-RADS assessment: 1 to 5 (ordinal, non-predictive!)

  * •

Age: patient’s age in years (integer)

  * •

Shape: mass shape: round=1 oval=2 lobular=3 irregular=4 (categorical)

  * •

Margin: mass margin: circumscribed=1 microlobulated=2 obscured=3 ill-defined=4
spiculated=5 (categorical)

  * •

Density: mass density high=1 iso=2 low=3 fat-containing=4 (ordinal)

The class indicates the severity: benign=0 or malignant=1. The data set is
described and can be downloaded
here101010http://archive.ics.uci.edu/ml/datasets/mammographic+mass. The
explanation is printed in Figure 11. It is composed of 16 decision rules, has
a complexity of 71, a coverage of $99.69\%$ and 150 classification errors.

    IF shape_1 > 0.5 AND BI-RADS_5 > 0.5 AND margin_? > 0.5 AND age_42 > 0.5 THEN CLASS=0
    IF BI-RADS_4 <= 0.5 AND age_43 <= 0.5 AND age_42 <= 0.5 AND margin_3 <= 0.5 AND margin_? > 0.5 AND shape_3 > 0.5 THEN CLASS=0
    IF shape_4 > 0.5 THEN CLASS=1
    IF age_35 <= 0.5 AND shape_1 > 0.5 AND age_65 <= 0.5 AND margin_5 > 0.5 AND density_2 <= 0.5 THEN CLASS=1
    IF age_35 <= 0.5 AND shape_1 > 0.5 AND age_65 > 0.5 AND margin_? > 0.5 AND BI-RADS_5 > 0.5 THEN CLASS=1
    IF BI-RADS_5 > 0.5 AND shape_4 <= 0.5 AND margin_? <= 0.5 THEN CLASS=1
    IF BI-RADS_3 <= 0.5 AND margin_? > 0.5 AND age_72 <= 0.5 AND shape_4 <= 0.5 AND age_55 > 0.5 AND shape_1 <= 0.5 AND
    density_3 <= 0.5 THEN CLASS=1
    IF BI-RADS_4 > 0.161 AND age_50 <= 0.102 AND shape_1 > 0.747 AND density_2 > 0.565 THEN CLASS=0
    IF age_27 <= 0.491 AND BI-RADS_5 > 0.095 AND shape_4 <= 0.362 AND age_60 <= 0.026 AND age_64 > 0.004 AND margin_? > 0.668
    THEN CLASS=0
    IF BI-RADS_5 > 0.098 AND age_42 <= 0.514 AND density_3 > 0.78 AND margin_? > 0.504 AND age_63 <= 0.714 AND age_60 > 0.745
    THEN CLASS=0
    IF shape_2 <= 0.402 AND shape_1 <= 0.123 AND margin_? <= 0.554 AND margin_5 > 0.17 AND BI-RADS_4 <= 0.605 AND age_67 <= 0.094
    AND shape_3 > 0.279 THEN CLASS=1
    IF shape_4 <= 0.969 AND BI-RADS_5 <= 0.162 AND margin_5 <= 0.637 THEN CLASS=0
    IF shape_1 > 0.25 AND age_79 > 0.953 AND density_2 <= 0.807 THEN CLASS=1
    IF margin_5 > 0.5 AND age_65 <= 0.5 AND shape_? > 0.5 THEN CLASS=1
    IF margin_4 <= 0.372 AND age_74 <= 0.976 AND shape_1 <= 0.028 AND BI-RADS_3 > 0.889 AND margin_5 > 0.88 THEN CLASS=1
    IF shape_4 <= 0.974 AND margin_3 <= 0.403 AND age_36 > 0.583 THEN CLASS=0

Figure 11: Explanation of the Mammographic mass data set.

####  A.0.8 Blood Transfusion Service Center Data Set

To demonstrate the RFMTC marketing model (a modified version of RFM), this
study adopted the donor database of Blood Transfusion Service Center in Hsin-
Chu City in Taiwan. The center passes their blood transfusion service bus to
one university in Hsin-Chu City to gather blood donated about every three
months. To build a FRMTC model, 748 donors were selected at random from the
donor database. There are 4 attributes:

  * •

R (Recency - months since last donation),

  * •

F (Frequency - total number of donation),

  * •

M (Monetary - total blood donated in c.c.),

  * •

T (Time - months since first donation), and

The class is a binary variable representing whether he/she donated blood in
March 2007 (1 stand for donating blood; 0 stands for not donating blood). The
data set is described and can be downloaded
here111111https://archive.ics.uci.edu/ml/datasets/Blood+Transfusion+Service+Center.
The explanation is printed in Figure 12. The explanation is composed of rules,
has a complexity of 76, a coverage of $100\%$ and has 150 classification
errors.

    IF R > 6.5 THEN CLASS=0
    IF R <= 6.5 AND M > 1125.0 AND F <= 18.0 AND T > 49.5 THEN CLASS=0
    IF R <= 6.5 AND M > 1125.0 AND F > 18.0 AND M <= 5625.0 THEN CLASS=1
    IF R <= 6.5 AND M > 1125.0 AND M > 4500.0 AND M > 5625.0 AND F > 25.0 THEN CLASS=1
    IF F > 4.5 AND R <= 6.5 AND F <= 18.0 AND T <= 49.5 AND T > 18.5 AND M > 1625.0 THEN CLASS=1
    IF F > 4.5 AND R <= 6.5 AND M <= 10875.0 THEN CLASS=1
    IF R <= 4.5 AND F > 4.5 AND T > 49.5 AND M <= 3125.0 AND F > 10.5 THEN CLASS=0
    IF F <= 4.5 AND R > 6.5 AND M > 375.0 AND M > 875.0 AND T <= 24.5 AND R > 10.5 AND R > 15.0 THEN CLASS=0
    IF F > 4.5 AND R <= 6.5 AND F <= 18.0 AND M > 2625.0 AND T <= 80.0 AND T <= 30.0 THEN CLASS=1
    IF F > 4.5 AND R <= 6.5 AND T > 82.5 AND F <= 43.5 THEN CLASS=1
    IF M <= 6164.961 AND F > 19.291 AND M > 5647.456 THEN CLASS=0
    IF F <= 40.892 AND M > 2055.415 AND R > 11.469 AND R <= 15.171 THEN CLASS=0
    IF F <= 32.328 AND M <= 2189.537 AND F > 5.305 AND T <= 20.136 AND F > 6.995 THEN CLASS=1
    IF F <= 32.328 AND M <= 2189.537 AND F > 5.305 AND T > 20.136 AND R <= 2.249 AND M > 1716.326 AND T > 63.353 THEN CLASS=0
    IF R > 6.5 AND F > 1.5 AND F > 17.5 THEN CLASS=0
    IF F <= 25.768 AND T <= 63.91 AND R > 10.216 AND R <= 12.862 AND M > 2050.118 THEN CLASS=0
    IF F <= 23.365 AND R <= 13.524 AND R <= 6.888 AND M <= 1579.136 THEN CLASS=0

Figure 12: Explanation of the Blood Transfusion Service Center data set.

####  A.0.9 Ecoli Data Set

This data set contains information of Escherichia coli. It is a bacterium of
the genus Escherichia that is commonly found in the lower intestine of warm-
blooded organisms. The data set has 336 instances split into 8 classes. There
are 8 attributes:

  * •

Sequence name: accession number for the SWISS-PROT database

  * •

mcg: McGeoch’s method for signal sequence recognition

  * •

gvh: von Heijne’s method for signal sequence recognition

  * •

lip: von Heijne’s Signal Peptidase II consensus sequence score (binary
attribute)

  * •

chg: presence of charge on N-terminus of predicted lipoproteins (binary
attribute)

  * •

aac: score of discriminant analysis of the amino acid content of outer
membrane and periplasmic proteins

  * •

alm1: score of the ALOM membrane spanning region prediction program

  * •

alm2: score of ALOM program after excluding putative cleavable signal regions
from the sequence

The data set is described and can be downloaded
here121212https://archive.ics.uci.edu/ml/datasets/ecoli. The explanation is
printed in Figure 13. The explanation is composed of 29 rules, has a
complexity of 112, a coverage of $99.4\%$ and 31 classification errors.

    IF alm1 <= 0.575 AND gvh <= 0.585 AND mcg <= 0.62 THEN CLASS=cp
    IF alm1 <= 0.575 AND gvh > 0.585 AND acc > 0.64 THEN CLASS=om
    IF acc <= 0.565 AND alm1 <= 0.58 AND mcg <= 0.615 AND alm1 <= 0.365 AND gvh > 0.66 THEN CLASS=om
    IF acc <= 0.565 AND alm1 <= 0.58 AND mcg > 0.615 AND gvh > 0.56 AND lip <= 0.74 THEN CLASS=pp
    IF acc <= 0.565 AND alm1 <= 0.58 AND mcg > 0.615 AND gvh > 0.56 AND lip > 0.74 THEN CLASS=omL
    IF acc <= 0.55 AND alm1 > 0.58 AND alm2 <= 0.77 AND mcg <= 0.62 THEN CLASS=im
    IF acc > 0.64 AND alm2 <= 0.575 AND gvh > 0.48 AND alm1 <= 0.575 THEN CLASS=om
    IF alm2 <= 0.615 AND alm1 <= 0.385 AND gvh <= 0.56 THEN CLASS=cp
    IF alm1 <= 0.575 AND acc <= 0.64 AND gvh <= 0.585 AND chg > 0.75 THEN CLASS=imL
    IF alm1 <= 0.575 AND acc <= 0.64 AND gvh > 0.585 AND acc <= 0.505 AND alm2 <= 0.375 THEN CLASS=pp
    IF alm1 > 0.585 AND mcg > 0.615 AND lip <= 0.74 AND alm2 <= 0.59 THEN CLASS=pp
    IF alm1 > 0.575 AND gvh <= 0.755 AND alm2 > 0.31 AND mcg <= 0.745 THEN CLASS=im
    IF alm1 > 0.575 AND gvh <= 0.755 AND alm2 > 0.31 AND mcg > 0.745 THEN CLASS=imU
    IF alm2 <= 0.615 AND gvh <= 0.565 AND alm1 <= 0.53 AND mcg > 0.71 AND gvh <= 0.54 THEN CLASS=imS
    IF alm2 <= 0.615 AND gvh > 0.565 AND acc > 0.64 THEN CLASS=om
    IF lip <= 0.956 AND alm2 > 0.678 AND mcg > 0.834 AND acc <= 0.585 AND acc > 0.539 THEN CLASS=imU
    IF lip > 0.956 AND alm1 <= 0.679 AND acc <= 0.769 AND chg <= 0.963 THEN CLASS=omL
    IF alm2 <= 0.645 AND acc <= 0.567 AND alm2 > 0.617 THEN CLASS=imU
    IF alm2 <= 0.241 AND gvh > 0.574 AND alm2 > 0.161 AND gvh <= 0.73 AND alm2 > 0.239 THEN CLASS=pp
    IF alm2 <= 0.241 AND gvh > 0.574 AND alm2 > 0.161 AND gvh > 0.73 THEN CLASS=pp
    IF mcg > 0.745 AND alm1 > 0.6 AND mcg <= 0.82 THEN CLASS=imU
    IF acc <= 0.495 AND lip <= 0.74 AND mcg <= 0.55 AND alm1 > 0.57 THEN CLASS=im
    IF alm2 <= 0.615 AND gvh > 0.585 AND acc <= 0.64 AND alm1 <= 0.705 AND alm1 > 0.355 THEN CLASS=pp
    IF alm2 <= 0.615 AND gvh > 0.585 AND acc > 0.64 THEN CLASS=om
    IF alm2 > 0.835 AND alm1 > 0.845 AND acc <= 0.56 THEN CLASS=im
    IF mcg <= 0.555 AND alm2 > 0.62 AND alm2 > 0.775 THEN CLASS=im
    IF alm1 <= 0.355 AND alm2 > 0.385 THEN CLASS=cp
    IF alm1 > 0.755 AND alm2 > 0.59 AND mcg <= 0.615 THEN CLASS=im
    IF alm1 <= 0.575 AND alm2 > 0.385 AND mcg > 0.615 AND gvh > 0.52 THEN CLASS=pp

Figure 13: Explanation of the Ecoli data set.

###  A.1 Tic-tac-toe Data Set

This data set encodes the complete set of possible board configurations at the
end of tic-tac-toe games, where “x” is assumed to have played first. The
target concept is “win for x” (i.e., true when “x” has one of eight possible
ways to create a ”three-in-a-row”). The data set contains 958 instances split
into 2 classes: “positive” and “negative”. There are 9 attributes.

  * •

top-left-square (TLS): {x,o,b}

  * •

top-middle-square (TMS): {x,o,b}

  * •

top-right-square (TRS): {x,o,b}

  * •

middle-left-square (MLS): {x,o,b}

  * •

middle-middle-square (MMS): {x,o,b}

  * •

middle-right-square (MRS): {x,o,b}

  * •

bottom-left-square (BLS): {x,o,b}

  * •

bottom-middle-square (BMS): {x,o,b}

  * •

bottom-right-square (BRS): {x,o,b}

The data set is described and can be downloaded
here131313https://archive.ics.uci.edu/ml/datasets/Tic-Tac-Toe+Endgame. The
explanation is printed in Figure 14. It is composed of 31 rules, has a
complexity of 117, a coverage of $85.1\%$ and 70 classification errors.

    IF MMS_o <= 0.5 AND MMS_b > 0.5 AND BRS_x <= 0.5 AND TLS_x <= 0.5 THEN CLASS=negative
    IF MMS_o <= 0.5 AND MMS_b > 0.5 AND BRS_x > 0.5 AND TLS_o <= 0.5 THEN CLASS=positive
    IF MMS_o > 0.5 AND TRS_x <= 0.5 AND BLS_b > 0.5 THEN CLASS=negative
    IF MMS_o > 0.5 AND BRS_x <= 0.5 AND TLS_b > 0.5 THEN CLASS=negative
    IF MMS_o > 0.5 AND BRS_x > 0.5 AND TLS_o > 0.5 AND TMS_b > 0.5 THEN CLASS=positive
    IF MLS_x <= 0.5 AND BLS_o <= 0.5 AND MMS_x > 0.5 AND TRS_o <= 0.5 THEN CLASS=positive
    IF MLS_x <= 0.5 AND BLS_o > 0.5 AND TLS_o > 0.5 AND MLS_o > 0.5 THEN CLASS=negative
    IF MLS_x > 0.5 AND TLS_x <= 0.5 AND BLS_o > 0.5 AND MMS_x > 0.5 THEN CLASS=positive
    IF MLS_x > 0.5 AND TLS_x > 0.5 AND BLS_x > 0.5 THEN CLASS=positive
    IF TRS_o <= 0.005 AND BRS_x <= 0.029 AND MMS_x <= 0.145 AND TLS_o > 0.558 THEN CLASS=negative
    IF TRS_o <= 0.005 AND BRS_x > 0.029 AND MMS_b <= 0.331 AND MRS_x > 0.426 THEN CLASS=positive
    IF TRS_o > 0.005 AND MMS_o > 0.243 AND BLS_x > 0.096 AND MRS_b > 0.097 THEN CLASS=positive
    IF TLS_o <= 0.019 AND BRS_o <= 0.305 AND MMS_b > 0.55 THEN CLASS=positive
    IF MMS_o <= 0.307 AND BLS_x <= 0.874 AND BRS_x > 0.223 AND TLS_o <= 0.218 THEN CLASS=positive
    IF BRS_o <= 0.47 AND MMS_x > 0.813 AND TRS_b > 0.117 AND MLS_x > 0.962 THEN CLASS=positive
    IF BRS_o > 0.47 AND MMS_x <= 0.372 AND MRS_x > 0.548 AND TLS_o > 0.968 THEN CLASS=negative
    IF BRS_o > 0.47 AND MMS_x > 0.372 AND BLS_o <= 0.173 AND MRS_x > 0.244 THEN CLASS=positive
    IF MMS_x <= 0.5 AND TRS_x <= 0.5 AND MRS_x > 0.5 AND BLS_o > 0.5 THEN CLASS=negative
    IF MMS_x <= 0.5 AND TRS_x > 0.5 AND TLS_x > 0.5 AND MMS_o <= 0.5 THEN CLASS=positive
    IF MMS_x <= 0.5 AND TRS_x > 0.5 AND TLS_x > 0.5 AND MMS_o > 0.5 THEN CLASS=positive
    IF MMS_x > 0.5 AND BLS_b > 0.5 AND MLS_o > 0.5 AND TLS_o <= 0.5 THEN CLASS=positive
    IF BRS_o <= 0.5 AND TLS_o <= 0.5 AND MMS_b <= 0.5 AND MMS_x > 0.5 THEN CLASS=positive
    IF BRS_o > 0.5 AND TMS_b > 0.5 AND MLS_x <= 0.5 AND TRS_o > 0.5 THEN CLASS=negative
    IF BMS_x <= 0.5 AND TRS_o > 0.5 AND TLS_x <= 0.5 AND MMS_o > 0.5 THEN CLASS=negative
    IF MMS_x > 0.88 AND BRS_o <= 0.657 AND BLS_o <= 0.023 THEN CLASS=positive
    IF MMS_o <= 0.85 AND BRS_o > 0.969 AND MMS_b > 0.435 AND TLS_b > 0.667 THEN CLASS=negative
    IF MMS_o <= 0.585 AND TLS_x <= 0.386 AND TRS_o <= 0.94 AND BLS_b > 0.635 THEN CLASS=positive
    IF MMS_o > 0.585 AND TLS_x <= 0.844 AND MLS_b > 0.903 AND MRS_o > 0.138 THEN CLASS=positive
    IF BLS_o > 0.755 AND MMS_x <= 0.516 AND TRS_o > 0.809 THEN CLASS=negative
    IF MMS_o <= 0.747 AND BLS_x > 0.726 AND TRS_o <= 0.282 THEN CLASS=positive
    IF MMS_o > 0.747 AND BRS_b > 0.249 AND BMS_x > 0.063 AND TLS_x <= 0.968 THEN CLASS=negative

Figure 14: Explanation of the Ecoli data set.