Source-linked AI summary
Evolutionary bagging for ensemble learning
Giang Ngo, Rodney Beard, Rohitash Chandra
TL;DR
Bagging keeps training samples fixed and can preserve individual learners’ bias. The paper proposes EvoBagging, which evolves bag contents with evolutionary operators; across classification benchmarks, it outperforms bagging and random forests while maintaining diversity.
Problem
Bagging mainly reduces variance, so individual learners’ bias can remain, motivating optimization of the training samples contained in each bag.
Method
EvoBagging uses evolutionary algorithms to shuffle and update training samples among bags through crossover, mutation, and generation-gap selection.
Results
EvoBagging outperforms bagging and random forests across binary and multiclass classification problems while maintaining good performance on balanced and imbalanced datasets.
Takeaways & Limitations
EvoBagging maintains a diverse ensemble of learners without reducing performance accuracy relative to conventional ensemble methods.
Takeaways & Limitations
EvoBagging has been evaluated only on classification tasks and uses decision trees as individual learners; regression and other learners remain future evaluation targets.
Abstract
from arXiv · showhide
Ensemble learning has gained success in machine learning with major advantages over other learning methods. Bagging is a prominent ensemble learning method that creates subgroups of data, known as bags, that are trained by individual machine learning methods such as decision trees. Random forest is a prominent example of bagging with additional features in the learning process. Evolutionary algorithms have been prominent for optimisation problems and also been used for machine learning. Evolutionary algorithms are gradient-free methods that work with a population of candidate solutions that maintain diversity for creating new solutions. In conventional bagged ensemble learning, the bags are created once and the content, in terms of the training examples, are fixed over the learning process. In our paper, we propose evolutionary bagged ensemble learning, where we utilise evolutionary algorithms to evolve the content of the bags in order to iteratively enhance the ensemble by providing diversity in the bags. The results show that our evolutionary ensemble bagging method outperforms conventional ensemble methods (bagging and random forests) for several benchmark datasets under certain constraints. We find that evolutionary bagging can inherently sustain a diverse set of bags without reduction in performance accuracy.
1. Introduction
Ensemble methods aggregate multiple learners to improve performance, while bagging mainly reduces variance and can preserve individual-learner bias. EvoBagging addresses this limitation by evolving training samples across bags to improve diversity and representation.
- Ensemble learning aggregates predictions from multiple machine learning models, often improving performance over individual models.
- Bagging trains learners on sampled subsets and reduces model variance, but typically preserves the individual learner’s bias.
- High-bias learners, such as unsuitable decision trees, can transfer underfitting errors into the aggregated ensemble.
- Prior bagging improvements adjusted bag size or other learner properties without optimizing the training samples contained in each bag.
- EvoBagging uses evolutionary algorithms to shuffle and update data among bags, iteratively enhancing ensemble diversity and reducing bias-related errors.
2. Background
Genetic algorithms are evolutionary optimization methods that have been applied broadly, including machine learning. Their encoding choices affect computational difficulty, accuracy, and search-space continuity.
- Genetic algorithms evolve populations of candidate solutions through evolutionary operators such as selection, crossover, and mutation.
- Binary encoding can create computational, accuracy, and search-space discontinuity challenges.
- Real-coded genetic algorithms have shown better performance than binary encoding for selected problems.
- Genetic algorithms are widely used in optimization applications and commonly support machine-learning hyperparameter tuning.
3. Methodology
EvoBagging treats bag contents as an evolving population: bootstrapped bags are trained, evaluated, recombined, mutated, and refreshed to improve learner quality while maintaining diversity.
- Framework: EvoBagging evolves bag contents rather than keeping bootstrapped training samples fixed, prioritizing higher-performing bags and using generation-gap selection.
- Bagging baseline: Canonical bagging bootstraps N bags of S samples, trains independent models, and aggregates their predictions through voting or averaging.
- Population: The population contains N bags, with each individual representing one bag in the evolutionary search.
- Evolutionary cycle: The algorithm initializes random-size bags, then repeatedly adds new bags, creates crossover offspring, mutates selected bags, and updates the population.
- Representation: Binary encoding represents whether each training instance belongs to a bag, with chromosome length set by the maximum bag size.
- Fitness function: Fitness combines classification performance with a bag-size term controlled by K, discouraging small over-fitted bags.
- Generation gap: The generation gap introduces random bags each generation to replace weaker bags and enforce population diversity.
- Operators: Crossover replaces incorrectly classified samples, while mutation swaps samples with those outside the selected bag to maintain diversity.
4. Results
The evaluation covers classification on balanced and imbalanced benchmark datasets, with EvoBagging compared against conventional ensemble methods.
- The evaluation focuses on classification problems using both class-balanced and imbalanced benchmark datasets.
- EvoBagging is evaluated against conventional ensemble methods including bagging and random forests.
- The supplied results passage identifies benchmark classification evaluation but reports no numerical outcome.
4.1. Datasets
The evaluation uses parity and two-spiral problems alongside eleven varied benchmark datasets, including datasets with differing class distributions.
- N-bit parity and two-spiral problem: The 3-bit parity problem maps binary inputs to odd or even parity labels.
- N-bit parity and two-spiral problem: The 6-bit and 8-bit parity problems contain 64 and 256 binary-string samples, respectively, and report training accuracy only.
- N-bit parity and two-spiral problem: The two-spiral problem contains 194 samples described by two features, x1 and x2, for challenging binary classification.
- Benchmark datasets: The benchmark evaluation uses eight UCI datasets and three Penn Machine Learning Benchmarks datasets varying in size, features, and classes.
- Benchmark datasets: Table 2 records benchmark class distributions by showing the proportions of minority and majority classes.
4.2. Experiment setting
The experiments compare EvoBagging with tree-based ensemble baselines under matched bag counts and repeated randomized evaluation settings.
- Experiment setting: Decision trees are the individual learners, while bagging, random forests, and extra-trees provide the main baselines, with gradient boosting added for test classification comparison.
- Experiment setting: EvoBagging and all baselines use the optimal bagging bag count, selected by searching at intervals of 10 using the highest test classification metric.
- Experiment setting: The test set comprises 20% of the original data and uses a randomized stratified split to preserve class distributions.
- Experiment setting: Thirty independent experiments with different random initializations are run, and the mean and standard deviation of each metric are reported.
- Experiment setting: Parity experiments vary the number of bags from 10 to 100, with G fixed at 20% of N and mutation applied to 10% of N.
4.3. Preliminary results
EvoBagging improves or matches bagging-based ensembles across the reported preliminary evaluations, especially when learner counts are constrained, while bag fitness increases during evolution.
- Preliminary results: EvoBagging initially achieves higher training accuracy than bagging and random forest on both 6-bit and 8-bit parity problems, especially with fewer bags.
- Preliminary results: All methods eventually reach 100% training accuracy as more bags are added, but EvoBagging is considerably better when the learner count is constrained.
- Preliminary results: EvoBagging outperforms baselines in most benchmark cases, while its ROC curves show comparable classification accuracy to bagging on Ionosphere and Abalone.
- Preliminary results: On the two-spiral problem, EvoBagging exceeds bagging and random forests by 11.6% and 18.3% in accuracy, respectively.
- Preliminary results: The average fitness of all bags gradually improves during evolution, with convergence after a few iterations depending on the dataset.
4.4. Influence of hyperparameters
Hyperparameter studies show that bag size, generation gap, mutation rate, mutation size, and bag-size control affect fitness, accuracy, and diversity-related behavior.
- Maximum bag size S: A maximum bag-size ratio of 100% generally gives the best classification result, although the gap from 75% is minimal.
- Generation gap G: The optimal generation gap is 16.67% for N=60; 50% causes unpredictable fitness fluctuations, while 3.33% improves slowly with lower fitness.
- Number of mutated bags M: Mutation rates below 10% produce mostly similar fitness, whereas mutating 20% of bags lowers average fitness by adding excessive randomness.
- Mutation size MS: Average fitness evolves steadily when mutation size MS is 5%; larger ratios lower fitness, while 1% limits diversity despite exceptionally high fitness.
- Bag size control K: The bag-size control K rewards larger bags to prevent collapse into multiple small bags, but oversized bags can overfit and need scaling with training-set size.
4.5. Ablation study
The ablation studies examine whether EvoBagging reduces individual-learner bias, preserves comparable variance, maintains learner diversity, and avoids harmful selection effects while improving imbalanced classification.
- Evolution: Bias gradually decreases over 10 generations across four datasets, providing empirical evidence that evolution reduces individual learners’ bias error.The average bias is measured for each learner across test samples.
- Evolution: Relative bias reduction is lowest on Abalone, Pima, Flare, and two-spiral, identified as the most difficult datasets by classification performance.The comparison uses average bias between the first and last iterations across 12 benchmark datasets.
- Bias-variance trade-off: EvoBagging exhibits variance comparable to bagging across different training sets, with less variation on the Red wine dataset.Six diversity measures compare 30 ensembles trained on different training data, using predictions on the same test set.
- Learner diversity: EvoBagging learners are more diverse than bagging on Ring, Mnist, and Car, while remaining comparable on Red wine.The experiment evaluates six diversity measures between individual learners.
- Selection effects: Selecting more bags reduces accuracy and training-data coverage, causing similar bags and increasing the risk of representing only easy-to-learn data.The selection experiment uses rank selection on Pima; higher selection rates continuously reduce coverage over generations.
- Imbalanced datasets: EvoBagging dominates bagging and random forests under the tested class-imbalance ratios, with larger improvements at higher imbalance.The authors attribute this result to operators optimizing toward representative bags; both majority- and minority-class classification improve.
- Voting rule: Majority and weighted voting produce mostly similar performance, so majority voting can provide faster inference without tuning the voting rule.This pattern is reported for Pima and two-spiral across iterations.
5. Discussion
EvoBagging evolves bag contents through crossover, mutation, and selection to improve learner bias and ensemble diversity, but its iterative training increases computational cost and limits current evaluation scope.
- Method: Crossover replaces incorrectly classified samples with new samples, aiming to populate bags with examples that their learners can model effectively.The paper connects crossover with diversification and convergence, including for imbalanced datasets.
- Method: EvoBagging evolves bag data by shuffling indices, unlike conventional bagging, which keeps bag contents fixed.The framework uses single-objective discrete optimization and can also be applied as a post-processing step to bagging or random forest.
- Scope: EvoBagging has been evaluated only on classification tasks and uses decision trees as individual learners.The paper identifies regression and other learner types, including neural networks, as future evaluation areas.
- Limitations: O(I × N × T) is EvoBagging’s stated time complexity when convergence requires I iterations, compared with O(N × T) for bagging and random forest.The additional cost comes from retraining learners across iterations; proposed scaling directions include fewer iterations or approximate fitness evaluation.
6. Conclusions
The paper introduces EvoBagging, an evolutionary ensemble method that improves errors in bootstrapped learners. It reports stronger performance than bagging and random forests across classification settings while maintaining ensemble diversity.
- Contribution: EvoBagging is presented as a novel evolutionary-algorithm implementation for ensemble learning.The paper evaluates its effectiveness and algorithm design across multiple datasets.
- Findings: EvoBagging improves bias-related error in individual learners trained on bootstrapped bags.This is the paper’s stated learner-level improvement.
- Findings: EvoBagging outperforms bagging and random forests on binary and multiclass classification problems.It also maintains good performance on class-balanced and imbalanced datasets.
- Findings: EvoBagging maintains a diverse ensemble of individual learners, identified as a major factor associated with improved performance over conventional ensembles.The reported design components include crossover, mutation, and generation-gap-based selection.