Bagging

Overview

Bagging fits several models to different random samples of the training rows and combines their outputs, usually by majority vote. It reduces variance but not bias, so the ensemble is only as good as its members. The samples are drawn once and then fixed, and that fixed draw is the point the variant below changes 2208.02400 §1. Only one card in the wiki lists this concept, so the page covers the plain baseline and that one variant.

Variants

Plain bagging

Each member is fitted to one bootstrap sample of the rows, drawn uniformly with replacement, and the final prediction is a majority vote over the members 2208.02400 §4.2. In the paper's benchmarks the members are decision trees, and bagging is one of four baselines, with random forest, extra-trees and gradient boosting 2208.02400 §4.2 tab. 4. The number of bags is chosen per dataset. The paper says it was picked on the test set in steps of 10, and the release picks it with cross-validation on the training data 2208.02400 §4.2. Card: Evolutionary bagging for ensemble learning, which holds the baseline numbers.

Evolutionary bagging (EvoBagging)

Each bag is treated as a candidate that can be improved. Over a fixed number of iterations, the bags' row sets are changed rather than redrawn 2208.02400 §3.1 alg. 1. Three operations drive the change:

• Fitness. A bag scores its classification performance times a size term that favours larger bags, (K + size) / K 2208.02400 §3.2 eq. 1.
• Crossover. The best-scoring bags are paired. Each child keeps the rows its tree gets right and takes the rows the other parent gets wrong 2208.02400 §3.4 alg. 1.
• Generation gap and mutation. A share of fresh random bags joins each round, and a few bags have rows swapped at random with rows outside them 2208.02400 §3.3 2208.02400 §3.4.

Author-reported results: best or tied test accuracy on 10 of 12 tabular datasets, and strictly best on 9 2208.02400 tab. 4. The paper also reports the best test F1 at every imbalance ratio it tried, against bagging and random forest 2208.02400 tab. 12 2208.02400 §4.5.5. The gains are small on several datasets. On Mnist and Flare, EvoBagging is not the best method 2208.02400 tab. 4.

The cost grows with iterations. Every iteration refits all N trees, so the total cost is about I × N × T, against N × T for bagging, where T is the time to train one tree 2208.02400 §5.

When to use which

The paper gives no significance test for its accuracy gaps 2208.02400 §4.3.

Implementation sketch

Plain bagging, the common core. Bag size is a parameter because this card does not state the size for plain bagging.

# Draw one bootstrap sample of row indices, with replacement  [§4.2]
def bootstrap_rows(n_rows, size):
    return [random_index(n_rows) for _ in range(size)]

# One member per bag; the card's members are decision trees  [§4.2]
bags = [bootstrap_rows(len(X), size) for _ in range(N)]
members = [fit_tree(X[bag], y[bag]) for bag in bags]

# Final prediction: majority vote over the members  [§4.2]
def predict(x):
    return majority([m.predict(x) for m in members])

EvoBagging replaces the fixed bags with a loop. The steps follow alg. 1; the paper's own pseudocode is the reference, and the card's Method section gives the details.

# Evolve the bags for a fixed number of rounds  [alg. 1]
for _ in range(iterations):
    # Score each bag: accuracy times (K + size) / K  [eq. 1]
    # Keep the best C = N - G bags as parents  [§3.4]
    # Pair the parents; children swap the rows each parent got wrong  [§3.4]
    # Add G fresh random bags  [§3.3]
    # Swap MS rows in M random bags  [§3.4]
    # Refit every tree on its bag  [alg. 1]
    members = refit(bags)

Contradictions

• Two-spiral gain. The text gives 11.6% over bagging, and Table 4 gives 8.4 points 2208.02400 §4.3 tab. 4. Unresolved.
• Two-spiral K. The text gives 100, and Table 3 gives 1000 2208.02400 §4.2 tab. 3.
• Parent selection. The paper describes rank selection in one place and fitness-proportional choice in another 2208.02400 §3.3 2208.02400 §3.4.
• Fitness data. The paper does not say which rows the accuracy term in the fitness is measured on 2208.02400 §3.2. The card's Pitfalls section reports that the release scores each bag on its own training rows.
• Imbalance experiment. The text says negatives are under-sampled, and the test set is unchanged 2208.02400 §4.5.5. The release resamples positives instead, see the card.
• Baseline bag count. The paper picks it on the test set, and the release picks it with cross-validation 2208.02400 §4.2.
• Pima baseline. One EvoBagging row without selection gives 77.04, and the main table gives 77.52 for the same setting 2208.02400 tab. 11 2208.02400 tab. 4.

Papers

• Evolutionary bagging for ensemble learning: evolves the bag contents over rounds, and the only card in the wiki that lists this concept.