Evolutionary bagging for ensemble learning

In plain words

Bagging builds many simple models, each trained on a random sample of the training data, and lets them vote. The sample given to each model is drawn once and then left alone. This paper changes that. It treats each model's sample as a candidate that can be improved, and it breeds the samples over several rounds, the way a genetic algorithm breeds solutions.

Each round, the models that do best are paired up. Each pair trades the examples that the other model got wrong, so that every model ends up with examples it can learn from. A few fresh random samples join each round, and a few samples are swapped at random to keep the group varied. The authors report that the resulting vote is usually more accurate than plain bagging and random forests on the datasets they tried, and that it scored best on F1 in the imbalanced settings they ran. The cost is much more computation, because every model is retrained in every round.

TL;DR

• Each bag is a bootstrap sample of the training rows, and a decision tree is fitted to it. The bags are then evolved for a fixed number of iterations by crossover (swapping misclassified rows between paired bags), a generation gap of new random bags, and mutation (swapping random rows in and out) §3.1 alg. 1 §3.3 §3.4.
• Fitness is the bag's accuracy times a size term, (K + bag size) / K eq. 1 §3.2.
• Author-reported: best or tied test accuracy on 10 of 12 datasets in the main table, and best test F1 in every imbalance setting shown §4.3 tab. 4 tab. 12.
• Everything above is author-reported. The released code differs from the paper in several places, listed under "Paper vs code". The code has no license.

Problem

Bagging reduces variance but not bias: the ensemble is only as good as its individual learners, and bootstrap samples are fixed once drawn §1. The authors argue that the content of each bag should be optimised rather than left as a random draw, and that existing evolutionary bagging work mostly targets imbalanced classification with under-sampling §1 §2. The paper targets classification only §5.

Method

The method is a population of bags. Each bag is one individual, and its genes are which training rows it holds §3.1. The population is evolved for a fixed number of iterations, and the final prediction is a majority vote over the bags' trees §4.2.

1. Initial bags. Draw N bootstrap bags. Each bag has a size s drawn uniformly from S/2 to S, where S is the number of training rows, and rows are sampled uniformly with replacement §3.1 §4.2 alg. 1. Fit one decision tree per bag §3.1.

2. Fitness. For each bag, the fitness is the bag's classification performance times a size term eq. 1 §3.2:

   fitness(b) = \alpha \times \frac{K + \phi_b}{K} eq. 1

   Here α is "the classification performance of the model associated with the bag", K is a user-defined constant that favours larger bags, and φ_b is the bag size §3.2. The paper does not say which data α is measured on.

3. Generation gap. Each new generation starts with G fresh random bags of random size, which replace part of the population §3.3 alg. 1.

4. Parent choice. The C = N − G bags with the highest fitness become crossover parents (rank selection) §3.4. The text also says parents are chosen probabilistically by fitness in one place §3.3. The parents are shuffled into pairs §3.4.

5. Crossover. For each pair, each parent keeps the training rows its own tree classifies correctly, and passes the rows it gets wrong to the other parent. Each pair produces two children §3.4 alg. 1.

6. Mutation. Choose M bags at random from the new population. In each, MS rows are replaced by MS rows drawn at random from the rows outside that bag §3.4 alg. 1. The paper does not say whether replacement is with or without replacement for the new rows.

7. Re-evaluate and repeat. Refit and rescore every bag, then repeat steps 2 to 6 for the number of iterations in the table below alg. 1 §4.2.

8. Prediction. Majority vote over the N trees §4.2. A fitness-weighted vote is also defined eq. 3 §4.5.6.

# EvoBagging  [alg. 1] [§3.1]
# Input:  train rows X and labels y; N bags; S max bag size; G new bags per
#         generation; M bags to mutate; MS rows swapped per mutated bag
# Output: N bags, each with one decision tree

def evobagging(X, y, N, S, G, M, MS, K, iterations):
    # C crossover parents per generation, with C = N - G  [alg. 1] [§3.4]
    C = N - G
    # Initial bags: bootstrap rows, random size in [S/2, S)  [§3.1] [§4.2]
    bags = [random_bootstrap_bag(X, y, S) for _ in range(N)]
    # Fit a tree to each bag and score it  [§3.2] [eq. 1]
    bags = [fit_and_score(bag, K) for bag in bags]
    for _ in range(iterations):
        # Generation gap: G fresh random bags  [§3.3]
        new_bags = [random_bootstrap_bag(X, y, S) for _ in range(G)]
        # Parents: the C bags with the highest fitness  [§3.4]
        parents = top_by_fitness(bags, C)
        # Shuffle the parents and pair them up  [§3.4]
        shuffle(parents)
        for first, second in pairs(parents):
            # Each parent keeps its correct rows, the wrong rows swap  [§3.4]
            child_a, child_b = crossover(first, second)
            new_bags += [child_a, child_b]
        # Mutation: M random bags swap MS rows with rows outside them  [§3.4]
        for bag in sample(new_bags, M):
            replace_rows(bag, MS, rows_outside(bag, X))
        # Refit and rescore the whole population  [alg. 1] [eq. 1]
        bags = [fit_and_score(bag, K) for bag in new_bags]
    return bags

Helper meanings: fit_and_score fits one tree to the bag's rows and returns the fitness in eq. 1. crossover returns the two children described in step 5.

Equations

Fitness eq. 1 is given above. The paper also uses an indicator for the bias measure in its ablation eq. 2 §4.5.1, and a weighted vote rule eq. 3 §4.5.6:

\hat{y} = \begin{cases} 0, & \text{if } \sum_{l \in L} P_{neg}\,acc_l < \sum_{l \in L} P_{pos}\,acc_l \\ 1, & \text{otherwise} \end{cases} eq. 3

Here l is an individual learner in the set L, and acc_l is that learner's training accuracy. P_neg and P_pos are not defined in the text. As printed, the rule returns 0 when the positive-class weight is the larger one. See "Pitfalls".

Hyperparameters

Per-dataset settings for the benchmark runs tab. 3. N is the number of bags, G the generation gap, M the number of bags mutated, K the size constant and iter the number of iterations.

tab. 3

Other settings:

Results

Author-reported. The main benchmark compares EvoBagging with bagging, random forest, extra-trees and gradient boosting. The release uses XGBoost for the last column, see "Paper vs code". Test accuracy in percent, with the paper's bracketed values in the last column tab. 4.

tab. 4

• EvoBagging is best or tied on 10 of 12 datasets, and strictly best on 9. It is not best on Mnist or Flare tab. 4.
• The paper says the Two-spiral gain is 11.6% over bagging and 18.3% over random forest §4.3. Table 4 gives 8.4 and 12.0 percentage points. No significance test is reported.
• Train accuracy of EvoBagging is about 99.9% on most datasets. On Abalone it is 91.09%, below bagging, random forest and extra-trees, which are near 99.9% tab. 4.
• The n-bit parity problems have no test split. On 6-bit and 8-bit parity, reported values are training accuracy only, over the number of bags. EvoBagging is higher than bagging and random forest when bags are few, and all methods reach 100% when more bags are added §4.2 §4.3 fig. 3 §4.1.1.
• Average fitness over iterations is plotted for three datasets. The text says it converges after a few iterations, depending on the dataset fig. 6 §4.3.
• Imbalanced data, test F1 (percent), at each imbalance ratio. EvoBagging is best in all nine ratio settings shown. Examples: Abalone 1:15 gives 28.60 for EvoBagging, 27.06 for bagging and 16.76 for random forest. Red wine at 1:6.35 gives 69.99, 67.41 and 66.35 tab. 12 §4.5.5.
• Bias (test-set error indicator, see "Pitfalls") falls over the iterations. Relative reduction from first to last iteration ranges from 2.2% (two-spiral) to 32.2% (Mnist) fig. 10 tab. 7 §4.5.1.
• Bagged-tree variance across 30 bootstrapped training sets is similar to bagging. The largest gap is the Car Q statistic, 0.531 for bagging against 0.448 for EvoBagging tab. 9 §4.5.2. Pairwise diversity among EvoBagging learners is higher than bagging on Ring, Mnist and Car tab. 10 §4.5.3.
• Sensitivity on Pima. Bag size ratio S from 25% to 100% gives accuracy 73.38, 75.97, 77.48 and 77.52 tab. 5. Iterations K from 1000 to 20000 gives 74.03, 77.52, 75.97 and 75.32 tab. 6. Mutated bags at 20% of N reduce average fitness, while 10% or less is stable §4.4.3 fig. 8. G at 16.67% was the grid-search optimum for N = 60 §4.4.2 fig. 7.
• Separate selection, the bags with highest fitness kept each iteration, lowers accuracy as more bags are kept: 77.04 with 0 kept, 76.22 with 4, 75.87 with 8, 75.58 with 12 and 75.63 with 16. Data coverage shrinks as well tab. 11 fig. 11 §4.5.4.
• Weighted and majority voting give similar accuracy over iterations on Pima and two-spiral fig. 12 §4.5.6.
• Cost: the paper says each iteration costs O(N × T), where T is the time to train one tree, so I iterations cost O(I × N × T), against O(N × T) for bagging §5.

Paper vs code

Repository: sydney-machine-learning/evolutionary-bagging, linked from the paper § Code and data. Commit 406fdac0. The repository has no LICENSE file. The code is a research script set: data loaders, evobagging_methods.py, one script per experiment, and configs.yml.

• Licence. No LICENSE file in the repository. Nothing is copied from it.
• Fitness. The paper's α is "classification performance" §3.2. The code fits the bag's tree on the bag's rows and scores it on the same rows, so α is training accuracy evobagging_methods.py. The size term uses the number of rows, duplicates included evobagging_methods.py. The tree depth is capped at the number of features [code: evobagging_methods.py#L31]. The paper gives no tree depth limit.
• Reported iteration. The code takes the iteration with the highest training majority-vote accuracy and reports the test accuracy at that iteration exp0_main_uci.py. The paper does not say this. Ties go to the first iteration (np.argmax).
• Iteration counts and bag numbers. configs.yml matches Table 3 for N, n_iter, K and the iteration count configs.yml. The G and M integers in code round differently from Table 3's percentages: Pima uses G = 10 against 15% of 60 = 9 configs.yml; Car uses G = 10 against 9 configs.yml; Churn uses G = 18 against 17.5 [code: configs.yml#L57-L63]; Ring uses G = 8 against 7.5 [code: configs.yml#L71-L77].
• Choice of N for baselines. The paper says the number of bags is the best for bagging, found in steps of 10 with the highest test metric §4.2. The code uses a 3-fold CV on the training data, in steps of 5, and picks the best choose_nbags.py. The paper's version selects on the test set.
• Gradient boosting. The paper's fourth baseline is "Gradient Boosting" tab. 4. The code uses xgboost.XGBClassifier with default settings and n_estimators = N baselines.py.
• Parent selection. The paper says rank selection §3.4 and also says probabilistic selection by fitness §3.3. The code takes the top C bags by fitness, then shuffles them into pairs evobagging_methods.py evobagging_methods.py.
• Selection step. The default is no separate selection step [code: exp0_main_uci.py#L97-L98]. The paper's Table 11 uses the same setting.
• Initial bag size. The code draws sizes in [S/2, S), with S excluded evobagging_methods.py. The paper writes U(S/2, S).
• Abalone classes. The paper gives four classes with no mapping. The code maps the Rings count to 1 for 0 to 7, 2 for 8 to 10, 3 for 11 to 15, and 4 above 15 data_processing.py.
• Mnist. The code loads scikit-learn's load_digits (8×8 digits, 1797 rows) data_processing.py, not the UCI file the paper cites.
• Two-spiral K. The text gives K = 100 §4.2. Table 3 and configs.yml give 1000 tab. 3 configs.yml.
• n-bit settings. The text says mutation size 1, K = 500 for 6-bit and 8-bit, and G at 20% §4.2. The code uses MS = 5% of S (3 for 6-bit, 12 for 8-bit), K = 100 for 6-bit and 1000 for 8-bit, G rounded up to an even number, M = 10% of N, and 5 iterations exp0_main_nbit.py exp0_main_nbit.py.
• Imbalance experiment. The text says negatives are under-sampled to 100%, 75%, 50% and 25% of their count, without replacement, and the test set is unchanged §4.5.5. The code keeps all negatives, resamples positives with replacement to reach each ratio, and applies the same resampling to the test set exp5_imbalanced.py. The imbalance script runs only random forest and bagging. No EvoBagging call was found in it [code: exp5_imbalanced.py#L58-L91].
• Random seeds. No seed is set in the scripts read. Only the train/test split is fixed (seed 1) data_processing.py. Runs are not bit-for-bit reproducible.
• Scripts not read in full. exp1 to exp4, exp6 and exp7 were only grepped for settings.

Pitfalls

• Fitness uses the bag's own training rows. Bag trees are scored on the rows they were fitted on evobagging_methods.py. With trees depth-capped at the number of features, EvoBagging's training accuracy is about 99.9% on most datasets tab. 4. For those datasets, α is close to 1 for most bags, so ranking is driven mainly by the size term (K + φ)/K. That is an inference from the code and the table, not a claim of the paper.
• Duplicates from bootstrap sampling. Rows are identified by their original index, so every copy of a row moves together when it is swapped in a crossover evobagging_methods.py. In mutation, sampling from the bag's index list and then removing every copy of each sampled index can remove more than MS rows, so bags can shrink [code: evobagging_methods.py#L120-L123]. The paper is silent on both.
• Weighted-vote equation. As printed eq. 3, the rule returns 0 when the weight of the positive class is larger. The code predicts the class with the larger weighted mean probability, and weights each bag's probabilities by its training accuracy evobagging_methods.py. Implement from the code, not the printed rule.
• Bias measure. Eq. 2 is a 0/1 indicator of misclassification per row. The text frames the same measure as the bias part of an MSE decomposition §4.5.1. The equation is not the bias-variance bias term. Read it as an error rate.
• Table 5 depths. Table 5 reports average tree depths of 8.5 to 12.4 for Pima tab. 5. Pima has 8 features, and the code caps depth at the number of features evobagging_methods.py. The released code cannot produce these depths.
• Table 11 baseline. Table 11's zero-selection row gives 77.04 on Pima, against 77.52 for the same setting in Table 4 and Table 6 tab. 11 tab. 4 tab. 6.
• Two-spiral gains. The 11.6% and 18.3% figures in the text do not match Table 4 (see Results).
• Table 7 percentages. Recomputing the reduction from the rounded means in Table 7 gives different values, e.g. Car 33.3% against 31.2%. Rounding of the three-decimal means probably explains this, but it cannot be checked from the table.
• Table typos. Table 4 has an unclosed parenthesis for Red wine train. Table 9 has "537" for Ring Q. Table 10 has "0.0.061" for Red wine double fault. Four Ring rows in Table 9 have the same value for both methods.
• Units of the brackets. Accuracies are in percent, but the bracketed standard deviations are fractions (0.001 to 0.043). The paper does not say this.
• Unsupported claims. The Discussion says global convergence is guaranteed because evolutionary algorithms search globally §5. The paper gives no proof or test. The bias-variance section says bias falls over 10 generations §4.5.1, but Table 3 uses 15 to 40 iterations, and the count used for that experiment is not stated.
• Cost. Every iteration refits all N trees, including unchanged ones [code: evobagging_methods.py#L167-L180]. Iteration count dominates runtime. The paper says the cost is O(I × N × T) §5.
• Hyperparameter search. The paper says G, M, MS and K were chosen with 5-fold CV on training data §4.2. The release has no such search. Its only search script is for N, with a different protocol choose_nbags.py.
• Section references. The text points to Section 4.1 for the best configuration §4.4 and to Section 4.4 as the "ablation study" §4.2. The configuration is in §4.2, and the hyperparameter study is §4.4.

Lineage

• Builds on: bagging §1, random forests §1, genetic algorithms, real-coded and binary §2, and evolutionary under-sampling for imbalanced data §2. None of these has a card in this wiki.
• Compared against: bagging, random forest, extra-trees and gradient boosting or XGBoost §4.2 tab. 4. For imbalance: bagging and random forest tab. 12.
• Related work named but not compiled: García and Herrera; Sun et al.; Roshan and Asadi §2.
• Superseded by: not stated.