only or all along evolution.

Two EEL frameworks have been designed to study these interdependent issues. The first one dubbed Offline Evolutionary Ensemble Learning (Off**-EEL) constructs the ensemble from the final population only. The second one, called**
Online Evolutionary Ensemble Learning (On**-EEL), gradually constructs the classifier ensemble as a selective archive**
of evolution, where some classifiers are added to the archive at each generation.

Both approaches combine a standard generational evolutionary algorithm with two interdependent components:
a new diversity-enhancing fitness function, and a selection mechanism. The fitness function, presented in Section 3.1 and generalizing the fitness devised by Liu et al. **[18], is inspired from co-evolution [13]. The selection process is used**
to extract a set of classifiers from either the final population
(Off-EEL) or the current archive plus the current population (On**-EEL), and proceeds by greedily maximizing the**
ensemble margin (Section 3.2).

Only binary or multi-class classification problems are considered in this paper. The decision of the classifier ensemble is the majority vote among the classifiers (ties being arbitrarily broken).

## 3.1 Diversity-Enforcing Fitness

Traditionally, Evolutionary Learning maximizes the number of correctly classified training examples (or equivalently minimizes the error rate). However, examples are not equally informative; therefore a rule correctly classifying a hard **example (e.g. close to the frontiers of the target concept) is**
more interesting and should be more rewarded than a rule correctly classifying an example which is correctly classified by almost all rules.

Co-evolutionary learning, first pioneered by Hillis [13],
nicely takes advantage of the above remark, gradually forging more and more difficult examples to enforce the discovery of high-quality solutions. Boosting proceeds along the same lines, gradually putting the stress on the examples which have not been successfully predicted so far.

A main difference between both frameworks is that Boosting exploits a finite set of labelled examples, while co-evolutionary learning has an infinite supply of labelled examples
(since it embeds the oracle). A second difference is that the difficulty of an example depends on the whole sequence of classifiers in Boosting, whereas it only depends on the current classifier population in co-evolution. In other words, Boosting is a memory-based process, while co-evolutionary learning is a memoryless one. Both approaches thus suffer from opposite weaknesses. Being a memory-based process, Boosting can be misled by noisy examples; consistently misclassified, these examples eventually get heavy weights and thus destabilize the Boosting learning process. Quite the contrary, co-evolution can forget what has been learned during early stages and specific heuristics, e.g. the so-called Hall-of-Fame, archive of best-so-far individuals, are required to prevent co-evolution from cycling in the learning landscape [20].

Based on these ideas, the fitness of classifiers is defined in this work from a set of reference classifiers noted Q**. The**
hardness of every training example x **is measured after the**
number of classifiers in Q which misclassify x**. The fitness of**
every classifier h **is then measured by the cumulated hardness of the examples that are correctly classified by** h.

Three remarks can be made concerning this fitness function. Firstly, contrasting with standard co-evolution, there is no way classifiers can "unlearn" to classify the training examples, since the training set is fixed. Secondly, as in Boosting, the fitness of a classifier reflects its diversity with respect to the reference set. Lastly, the classifier fitness function is highly multi-modal compared to the simple error rate: good classifiers might correctly classify many easy examples, or sufficiently many hard enough examples, or a few very hard examples.

Formally, let E = {(xi, yi), xi ∈ X , yi ∈ Y, i = 1 **. . . n**}
denote the training set (referred to as set of fitness cases in the GP context); each fitness case or example (xi, yi**) is** composed of an instance xi **belonging to the instance space**
X and the associated label yi **belonging to a finite set** Y .

Any classifier h **is a function mapping the instance space** X onto Y . The loss function ℓ is defined as ℓ : Y × Y 7→ IR,
where ℓ(y, y′**) is the (real valued) error cost of predicting**
label y **instead of the true label** y
′
.

The hardness or weight of every training example (xi, yi),
noted w Q

i
, or wi when the reference set Q **is clear from**
the context, is the average loss incurred by the reference classifiers on (xi, yi):

$$w_{i}={\frac{1}{|{\mathcal{Q}}|}}\sum_{h\in{\mathcal{Q}}}\ell(h(\mathbf{x}_{i}),y_{i}).$$
$$(1)$$

The cumulated hardness fitness F is finally defined as follows: F(h**) is the sum over all training examples that are**
correctly classified by h, of their weight wi **raised to power** γ. Parameter γ **governs the importance of the weights** wi
(the cumulated hardness boils down to the number of correctly classified examples for γ **= 0) and thus the diversity**
pressure.

$$\mathcal{F}(h)=\sum_{\begin{subarray}{c}i=1...n\\ h(\mathbf{x}_{i})=y_{i}\end{subarray}}w_{i}^{\gamma}\tag{2}$$  where $h$ is the $i$-th column of $h$.  
Parameter γ **can also be adjusted depending on the level**
of noise in the dataset. As noisy examples typically reach high weights, increasing the value of γ **might lead to retain**
spurious hypotheses, which happen to correctly classify a few noisy examples. When ℓ **is set to the step loss function**
(ℓ(y, y′**) = 0 if** y = y
′
, 1 otherwise) and γ **is set to 1, the**
above fitness function is the same as the one used by Liu et al. [18]. The value of γ **is set to 2 in the experiments**
(Section 4).

3.2 Ensemble Selection As noted earlier on, the selection of classifiers in a pool H = {h1, . . . , hT } **in order to form an efficient ensemble**
is formally equivalent to a feature selection problem. The equivalence is seen by replacing the initial instance space X
with the one defined from the classifier pool, where each instance xi is redescribed as the vector (h1(xi), . . . , hT (xi)).

Feature selection algorithms [12] could thus be used for ensemble selection; unfortunately, feature selection is one of the most difficult Machine Learning problems.

Therefore, a simple greedy selection process is used in this paper to select the classifiers in the diverse pools considered by the Off-EEL (Section 3.3) and On**-EEL (Section 3.4) algorithms. The novelty is the selection criterion, generalizing**
the notion of margin [11, 23] to an ensemble of examples as follows.