plane is amenable to quadratic optimization, with:

1. Let P1 **be the first evolutionary population, and** h
∗
the classifier with minimal error rate on E.

2. L1 = Ensemble-Selection(P1, E, {h
∗

})
3. For t = 2 **. . . T** :
(a) Evolve Pt−1 → Pt, using Lt−1 **as reference set.**
(b) Lt = Ensemble-Selection(Pt , E, Lt−1)
4. Return LT .
classifier ensemble; like in Boosting, the goal is to find classifiers which overcome the errors of the past classifiers. While the ensemble selection algorithm is launched at every generation, it uses the biased current population as classifier pool. In fact, On**-EEL addresses a dynamic optimization**
problem; if the classifier ensemble significantly changes between one generation and the next, the fitness landscape will change accordingly and several evolutionary generations might be needed to accommodate this change. On the other hand, as long as the current population does not perform well, the ensemble selection algorithm is unlikely to select further classifiers in the current ensemble; the fitness landscape thus remains stable. The population diversity does not directly result from the fitness function as in the Off**EEL case; rather, it relates with the dynamic aspects of the**
fitness function.

## 4. Experimental Setting

This section describes the experimental setting used to assess the EEL framework.

## 4.1 Datasets

Experiments are conducted on the six UCI datasets [19]
presented in Table 1. The performance of each algorithm is measured after a standard stratified 10-fold cross-validation procedure. The dataset is partitioned into 10 folds with same class distribution. Iteratively, all folds but the i-th one are used to train a classifier, and the error rate of this classifier on the remaining i**-th fold is recorded. The performance of the algorithm is averaged over 10 runs for each**
fold, and over the 10 folds.

## 4.2 Classifier Search Space

As mentioned earlier on, evolutionary ensemble learning can accommodate any type of classifier; Off-EEL and On**EEL could consider neural nets, genetic programs or decision** lists as genotypic search space. Our experiments will consider the most straightforward classifiers, namely separating hyperplanes, as these can easily be inspected and compared.

Formally, let X = IRd**be the instance space, a separating** hyperplane classifier h is characterized as (w, b) ∈ IRd × IR
with h(x) = < w, x > − b (< w, x > **denotes the scalar**
product of w and x). The search for a separating hyper-

$${\mathcal{F}}(h)=\sum_{i=1,\dots,n}\left(h(\mathbf{x}_{i})-y_{i}\right)^{2}.$$
$$({\mathfrak{h}})$$
2. (6)
As the above optimization problem can be tackled using standard optimization algorithms, it provides a well-founded baseline for comparison. Specifically, the first goal of the experiments is thus to assess the merits of evolutionary ensemble learning against three other approaches.

The first baseline algorithm referred to as Least Mean Square (LMS) uses a stochastic gradient algorithm to determine the optimal separating hyperplane in the sense of criterion given by Equation 6 (see pseudo-code in Figure 3).

The second baseline algorithm is an elementary evolutionary algorithm, producing the best-of-run separating hyperplane such that it minimizes the (training) error rate3.

The third reference algorithm is the prototypical ensemble learning algorithm, namely AdaBoost with its default parameters [8]. AdaBoost uses simple decision stumps [23]
baseline algorithm as weak learner (more on this below).

The learning error is classically viewed as composed from a variance term and a bias term [1]. The bias term measures how far the target concept tc **is from the classifier**
search space H**, that is, from the best classifier** h
∗
**in this**
search space. The variance term measures how far away one can wander from h
∗
**, wrongly selecting other classifiers in** H
(overfitting).

The comparison of the first and second baseline algorithms gives some insight into the intrinsic difficulty of the problem.

Stochastic gradient (LMS) will find the global optimum for criterion given by Equation 6, but this solution optimizes at best the training error. The comparison between the solutions respectively found by LMS and the simple evolutionary algorithm will thus reflect the learning variance term.

Similarly, the comparison of the first baseline algorithm and AdaBoost gives some insight into how the ensemble improves on the base weak learner; this improvement can be interpreted in terms of variance as well as in terms of bias
(since the majority vote of decision stumps allows for describing more complex regions than simple separating hyperplanes alone).

## 4.3 Experimental Setting

The parameters for the LMS algorithm (see Figure 3) are as follows: the training rate, set to η(t**) = 1**/(n
√t**), decreases**
over the training epochs; the maximum number of epochs allowed is T **= 10000; the stopping criterion is when the**
difference in the error rates over two consecutive epochs, is less that some threshold ǫ (ǫ = 10−7**). Importantly, LMS**
requires a preliminary normalization of the dataset, (e.g.

∀i = 1 . . . n, xi ∈ [−1, 1]d**). The final result is the error on**
the test set, averaged over 10 runs for each fold (because of the stochastic reordering of the training set) and averaged over 10 folds.

The classical AdaBoost algorithm [8] uses simple decision stumps [23], and the number of Boosting iterations is limited to 2000. Decision stumps are simple binary classifiers that 3**For 3-classes problems, e.g.** bos or cmc**, the classifier is**
characterized as two hyperplanes, respectively separating class 0 (resp. class 1) from the other two classes. In case of conflict (the example is simultaneously classified in class 0 by the first classifier and in class 1 by the second classifier), the tie is broken arbitrarily.