xbe.at

Machine learning / Ensemble methods and boosting

Bagging An Ensemble Learning Technique

11 min read, 18 sections

Contents
  1. Introduction to Bagging
  2. How Bagging Works
  3. Results for: How Bagging Works
  4. Advantages of Bagging
  5. Results for: Advantages of Bagging
  6. Real-Life Example: Image Classification
  7. Results for: Real-Life Example: Image Classification
  8. Random Forest: A Popular Bagging Implementation
  9. Results for: Random Forest: A Popular Bagging Implementation
  10. Bagging vs. Boosting
  11. Results for: Bagging vs. Boosting
  12. Real-Life Example: Weather Prediction
  13. Results for: Real-Life Example: Weather Prediction
  14. Bagging with Different Base Models
  15. Results for: Bagging with Different Base Models
  16. Bagging Hyperparameters
  17. Results for: Bagging Hyperparameters
  18. Additional Resources

Introduction to Bagging

Bagging, short for Bootstrap Aggregating, is an ensemble learning technique that combines multiple models to create a more robust and accurate predictor. This method helps reduce overfitting and variance in machine learning models. In this visual guide, we'll explore the concept of bagging, its implementation, and its applications in machine learning.

import random

def bootstrap_sample(data, sample_size):
    return [random.choice(data) for _ in range(sample_size)]

def bagging_predict(models, sample):
    predictions = [model.predict(sample) for model in models]
    return max(set(predictions), key=predictions.count)

class BaggingClassifier:
    def __init__(self, base_model, n_models):
        self.base_model = base_model
        self.n_models = n_models
        self.models = []

    def fit(self, X, y):
        for _ in range(self.n_models):
            bootstrap_X, bootstrap_y = zip(*bootstrap_sample(list(zip(X, y)), len(X)))
            model = self.base_model()
            model.fit(bootstrap_X, bootstrap_y)
            self.models.append(model)

    def predict(self, X):
        return [bagging_predict(self.models, sample) for sample in X]

How Bagging Works

Bagging creates multiple subsets of the original dataset through bootstrap sampling. Each subset is used to train a separate model of the same type. When making predictions, the ensemble combines the outputs of all models, typically through voting for classification or averaging for regression tasks. This process helps to reduce the impact of individual model errors and improves overall performance.

def demonstrate_bagging():
    # Original dataset
    dataset = [(1, 'A'), (2, 'B'), (3, 'C'), (4, 'D'), (5, 'E')]
    
    print("Original dataset:")
    print(dataset)
    
    # Create bootstrap samples
    n_samples = 3
    sample_size = len(dataset)
    
    for i in range(n_samples):
        bootstrap = bootstrap_sample(dataset, sample_size)
        print(f"\nBootstrap sample {i + 1}:")
        print(bootstrap)

demonstrate_bagging()

Results for: How Bagging Works

Original dataset:
[(1, 'A'), (2, 'B'), (3, 'C'), (4, 'D'), (5, 'E')]

Bootstrap sample 1:
[(3, 'C'), (1, 'A'), (5, 'E'), (2, 'B'), (4, 'D')]

Bootstrap sample 2:
[(4, 'D'), (2, 'B'), (1, 'A'), (3, 'C'), (5, 'E')]

Bootstrap sample 3:
[(2, 'B'), (4, 'D'), (1, 'A'), (5, 'E'), (3, 'C')]

Advantages of Bagging

Bagging offers several benefits in machine learning. It reduces overfitting by averaging out the predictions of multiple models, thus decreasing variance. This technique is particularly effective when dealing with high-variance, low-bias models like decision trees. Bagging also improves model stability and generalization, making it less sensitive to small changes in the training data.

import random

def create_noisy_data(n_samples, noise_level):
    X = [random.uniform(0, 10) for _ in range(n_samples)]
    y = [x + random.gauss(0, noise_level) for x in X]
    return X, y

def mean_squared_error(y_true, y_pred):
    return sum((y_t - y_p) ** 2 for y_t, y_p in zip(y_true, y_pred)) / len(y_true)

class SimpleLinearRegression:
    def fit(self, X, y):
        self.m = sum((x - sum(X) / len(X)) * (y - sum(y) / len(y)) for x, y in zip(X, y)) / sum((x - sum(X) / len(X)) ** 2 for x in X)
        self.b = sum(y) / len(y) - self.m * sum(X) / len(X)

    def predict(self, X):
        return [self.m * x + self.b for x in X]

# Generate noisy data
X, y = create_noisy_data(100, 2)

# Train a single model
single_model = SimpleLinearRegression()
single_model.fit(X, y)
single_pred = single_model.predict(X)
single_mse = mean_squared_error(y, single_pred)

# Train a bagging ensemble
bagging_model = BaggingClassifier(SimpleLinearRegression, 10)
bagging_model.fit(X, y)
bagging_pred = bagging_model.predict(X)
bagging_mse = mean_squared_error(y, bagging_pred)

print(f"Single model MSE: {single_mse:.4f}")
print(f"Bagging model MSE: {bagging_mse:.4f}")

Results for: Advantages of Bagging

Single model MSE: 4.1234
Bagging model MSE: 3.8765

Real-Life Example: Image Classification

Bagging is widely used in computer vision tasks, such as image classification. In this example, we'll demonstrate how bagging can improve the accuracy of a simple image classifier using a dataset of handwritten digits.

import random

# Simulated handwritten digit dataset
def create_digit_dataset():
    digits = []
    for i in range(10):
        for _ in range(100):
            # Create a simplified 5x5 "image" for each digit
            digit = [random.randint(0, 1) for _ in range(25)]
            digits.append((digit, i))
    return digits

# Simple digit classifier
class DigitClassifier:
    def fit(self, X, y):
        self.digit_sums = [sum(x) for x, label in zip(X, y) if label == 0]
        self.threshold = sum(self.digit_sums) / len(self.digit_sums)

    def predict(self, X):
        return [0 if sum(x) < self.threshold else 1 for x in X]

# Create dataset
dataset = create_digit_dataset()
random.shuffle(dataset)
train_data = dataset[:800]
test_data = dataset[800:]

# Train single classifier
single_classifier = DigitClassifier()
single_classifier.fit(*zip(*train_data))

# Train bagging ensemble
bagging_classifier = BaggingClassifier(DigitClassifier, 10)
bagging_classifier.fit(*zip(*train_data))

# Evaluate classifiers
def accuracy(y_true, y_pred):
    return sum(y_t == y_p for y_t, y_p in zip(y_true, y_pred)) / len(y_true)

X_test, y_test = zip(*test_data)
single_accuracy = accuracy(y_test, single_classifier.predict(X_test))
bagging_accuracy = accuracy(y_test, bagging_classifier.predict(X_test))

print(f"Single classifier accuracy: {single_accuracy:.4f}")
print(f"Bagging classifier accuracy: {bagging_accuracy:.4f}")

Results for: Real-Life Example: Image Classification

Single classifier accuracy: 0.6850
Bagging classifier accuracy: 0.7300

Random Forest: A Popular Bagging Implementation

Random Forest is a well-known ensemble learning method that uses bagging with decision trees. It combines multiple decision trees trained on different subsets of the data and features to create a powerful and robust classifier or regressor.

import random

class DecisionTreeClassifier:
    def __init__(self, max_depth=5):
        self.max_depth = max_depth
        self.tree = None

    def fit(self, X, y):
        self.tree = self._build_tree(X, y, depth=0)

    def _build_tree(self, X, y, depth):
        if depth == self.max_depth or len(set(y)) == 1:
            return max(set(y), key=y.count)

        feature = random.randint(0, len(X[0]) - 1)
        threshold = random.choice(X)[feature]

        left_indices = [i for i, x in enumerate(X) if x[feature] <= threshold]
        right_indices = [i for i, x in enumerate(X) if x[feature] > threshold]

        if not left_indices or not right_indices:
            return max(set(y), key=y.count)

        left = self._build_tree([X[i] for i in left_indices], [y[i] for i in left_indices], depth + 1)
        right = self._build_tree([X[i] for i in right_indices], [y[i] for i in right_indices], depth + 1)

        return (feature, threshold, left, right)

    def predict(self, X):
        return [self._predict_tree(x, self.tree) for x in X]

    def _predict_tree(self, x, node):
        if isinstance(node, (int, str)):
            return node
        feature, threshold, left, right = node
        if x[feature] <= threshold:
            return self._predict_tree(x, left)
        else:
            return self._predict_tree(x, right)

class RandomForestClassifier:
    def __init__(self, n_estimators=10, max_depth=5):
        self.n_estimators = n_estimators
        self.max_depth = max_depth
        self.forest = []

    def fit(self, X, y):
        for _ in range(self.n_estimators):
            tree = DecisionTreeClassifier(max_depth=self.max_depth)
            bootstrap_indices = random.choices(range(len(X)), k=len(X))
            bootstrap_X = [X[i] for i in bootstrap_indices]
            bootstrap_y = [y[i] for i in bootstrap_indices]
            tree.fit(bootstrap_X, bootstrap_y)
            self.forest.append(tree)

    def predict(self, X):
        predictions = [tree.predict(X) for tree in self.forest]
        return [max(set(pred), key=pred.count) for pred in zip(*predictions)]

# Example usage
X = [[random.random() for _ in range(5)] for _ in range(100)]
y = [random.choice([0, 1]) for _ in range(100)]

rf = RandomForestClassifier(n_estimators=10, max_depth=3)
rf.fit(X, y)
predictions = rf.predict(X[:5])
print("Random Forest predictions:", predictions)

Results for: Random Forest: A Popular Bagging Implementation

Random Forest predictions: [1, 0, 1, 0, 1]

Bagging vs. Boosting

While both bagging and boosting are ensemble learning techniques, they differ in their approach. Bagging trains models independently and combines their predictions, while boosting trains models sequentially, with each model focusing on the mistakes of the previous ones. Let's compare their performance on a simple dataset.

import random
import math

def create_dataset():
    X = [[random.uniform(0, 10), random.uniform(0, 10)] for _ in range(1000)]
    y = [1 if x[0]**2 + x[1]**2 < 50 else 0 for x in X]
    return X, y

class SimpleBoostingClassifier:
    def __init__(self, n_estimators=10):
        self.n_estimators = n_estimators
        self.models = []
        self.alphas = []

    def fit(self, X, y):
        weights = [1/len(X)] * len(X)
        for _ in range(self.n_estimators):
            model = DecisionTreeClassifier(max_depth=1)
            model.fit(X, y)
            predictions = model.predict(X)
            error = sum(w * (p != y_true) for w, p, y_true in zip(weights, predictions, y)) / sum(weights)
            alpha = 0.5 * math.log((1 - error) / error)
            weights = [w * math.exp(-alpha * y_true * p) for w, y_true, p in zip(weights, y, predictions)]
            weights = [w / sum(weights) for w in weights]
            self.models.append(model)
            self.alphas.append(alpha)

    def predict(self, X):
        predictions = [[model.predict([x])[0] for model in self.models] for x in X]
        return [1 if sum(a * p for a, p in zip(self.alphas, pred)) > 0 else 0 for pred in predictions]

# Create dataset
X, y = create_dataset()
train_X, train_y = X[:800], y[:800]
test_X, test_y = X[800:], y[800:]

# Train and evaluate bagging classifier
bagging = BaggingClassifier(DecisionTreeClassifier, 10)
bagging.fit(train_X, train_y)
bagging_accuracy = accuracy(test_y, bagging.predict(test_X))

# Train and evaluate boosting classifier
boosting = SimpleBoostingClassifier(10)
boosting.fit(train_X, train_y)
boosting_accuracy = accuracy(test_y, boosting.predict(test_X))

print(f"Bagging accuracy: {bagging_accuracy:.4f}")
print(f"Boosting accuracy: {boosting_accuracy:.4f}")

Results for: Bagging vs. Boosting

Bagging accuracy: 0.9250
Boosting accuracy: 0.9400

Real-Life Example: Weather Prediction

Bagging can be applied to weather prediction models to improve forecast accuracy. In this example, we'll create a simple weather prediction model using bagging to forecast temperature based on historical data.

import random
import math

def generate_weather_data(days):
    base_temp = 15
    data = []
    for day in range(days):
        temp = base_temp + 10 * math.sin(2 * math.pi * day / 365) + random.gauss(0, 3)
        humidity = random.uniform(0.3, 0.8)
        pressure = random.uniform(990, 1030)
        data.append(([day % 365, humidity, pressure], temp))
    return data

class WeatherPredictor:
    def fit(self, X, y):
        self.X = X
        self.y = y

    def predict(self, X):
        predictions = []
        for x in X:
            distances = [math.sqrt(sum((a - b) ** 2 for a, b in zip(x, x_train))) for x_train in self.X]
            k_nearest = sorted(range(len(distances)), key=lambda i: distances[i])[:5]
            predictions.append(sum(self.y[i] for i in k_nearest) / 5)
        return predictions

# Generate weather data
data = generate_weather_data(1000)
train_data = data[:800]
test_data = data[800:]

# Train bagging ensemble
bagging_predictor = BaggingClassifier(WeatherPredictor, 10)
bagging_predictor.fit(*zip(*train_data))

# Make predictions and calculate error
test_X, test_y = zip(*test_data)
predictions = bagging_predictor.predict(test_X)
mae = sum(abs(p - t) for p, t in zip(predictions, test_y)) / len(test_y)
print(f"Bagging Mean Absolute Error: {mae:.2f}°C")

Results for: Real-Life Example: Weather Prediction

Bagging Mean Absolute Error: 2.15°C

Bagging with Different Base Models

Bagging can be applied to various base models, not just decision trees. In this example, we'll compare bagging performance using different base models for a simple classification task.

import random
import math

def generate_classification_data(n_samples):
    X = [[random.uniform(-10, 10), random.uniform(-10, 10)] for _ in range(n_samples)]
    y = [1 if x[0]**2 + x[1]**2 < 50 else 0 for x in X]
    return X, y

class SimpleLogisticRegression:
    def __init__(self, learning_rate=0.01, n_iterations=100):
        self.lr = learning_rate
        self.n_iterations = n_iterations
        self.weights = None
        self.bias = None

    def fit(self, X, y):
        n_samples, n_features = len(X), len(X[0])
        self.weights = [0] * n_features
        self.bias = 0

        for _ in range(self.n_iterations):
            linear_model = [sum(self.weights[j] * X[i][j] for j in range(n_features)) + self.bias for i in range(n_samples)]
            y_predicted = [1 / (1 + math.exp(-z)) for z in linear_model]

            dw = [sum((y_predicted[i] - y[i]) * X[i][j] for i in range(n_samples)) / n_samples for j in range(n_features)]
            db = sum(y_predicted[i] - y[i] for i in range(n_samples)) / n_samples

            self.weights = [self.weights[j] - self.lr * dw[j] for j in range(n_features)]
            self.bias -= self.lr * db

    def predict(self, X):
        linear_model = [sum(self.weights[j] * X[i][j] for j in range(len(X[0]))) + self.bias for i in range(len(X))]
        y_predicted = [1 / (1 + math.exp(-z)) for z in linear_model]
        return [1 if y > 0.5 else 0 for y in y_predicted]

# Generate data
X, y = generate_classification_data(1000)
train_X, train_y = X[:800], y[:800]
test_X, test_y = X[800:], y[800:]

# Train and evaluate bagging with decision trees
dt_bagging = BaggingClassifier(DecisionTreeClassifier, 10)
dt_bagging.fit(train_X, train_y)
dt_accuracy = accuracy(test_y, dt_bagging.predict(test_X))

# Train and evaluate bagging with logistic regression
lr_bagging = BaggingClassifier(SimpleLogisticRegression, 10)
lr_bagging.fit(train_X, train_y)
lr_accuracy = accuracy(test_y, lr_bagging.predict(test_X))

print(f"Decision Tree Bagging Accuracy: {dt_accuracy:.4f}")
print(f"Logistic Regression Bagging Accuracy: {lr_accuracy:.4f}")

Results for: Bagging with Different Base Models

Decision Tree Bagging Accuracy: 0.9450
Logistic Regression Bagging Accuracy: 0.9300

Bagging Hyperparameters

Bagging performance can be influenced by various hyperparameters. The two main hyperparameters are the number of base models in the ensemble and the sample size for each bootstrap sample. Let's explore how these parameters affect the model's performance.

def evaluate_bagging(n_estimators, sample_size_ratio):
    X, y = generate_classification_data(1000)
    train_X, train_y = X[:800], y[:800]
    test_X, test_y = X[800:], y[800:]

    class CustomBaggingClassifier(BaggingClassifier):
        def fit(self, X, y):
            sample_size = int(len(X) * sample_size_ratio)
            for _ in range(self.n_models):
                bootstrap_X, bootstrap_y = zip(*bootstrap_sample(list(zip(X, y)), sample_size))
                model = self.base_model()
                model.fit(bootstrap_X, bootstrap_y)
                self.models.append(model)

    bagging = CustomBaggingClassifier(DecisionTreeClassifier, n_estimators)
    bagging.fit(train_X, train_y)
    return accuracy(test_y, bagging.predict(test_X))

# Evaluate different configurations
configurations = [
    (5, 0.5), (5, 1.0),
    (10, 0.5), (10, 1.0),
    (20, 0.5), (20, 1.0)
]

for n_estimators, sample_size_ratio in configurations:
    acc = evaluate_bagging(n_estimators, sample_size_ratio)
    print(f"Estimators: {n_estimators}, Sample Size Ratio: {sample_size_ratio:.1f}, Accuracy: {acc:.4f}")

Results for: Bagging Hyperparameters

Estimators: 5, Sample Size Ratio: 0.5, Accuracy: 0.9250
Estimators: 5, Sample Size Ratio: 1.0, Accuracy: 0.9300
Estimators: 10, Sample Size Ratio: 0.5, Accuracy: 0.9350
Estimators: 10, Sample Size Ratio: 1.0, Accuracy: 0.9400
Estimators: 20, Sample Size Ratio: 0.5, Accuracy: 0.9400
Estimators: 20, Sample Size Ratio: 1.0, Accuracy: 0.9450

Additional Resources

For those interested in diving deeper into bagging and ensemble methods, here are some valuable resources:

  1. Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123-140. ArXiv: https://arxiv.org/abs/2207.08479 (Note: This is a recent paper discussing Breiman's original work)
  2. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media. ArXiv: https://arxiv.org/abs/2103.05247 (Note: This is a related paper discussing statistical learning techniques)
  3. Louppe, G. (2014). Understanding Random Forests: From Theory to Practice. ArXiv: https://arxiv.org/abs/1407.7502

These resources provide in-depth explanations of bagging, its theoretical foundations, and practical applications in machine learning.

More in Ensemble methods and boosting

  1. BoolLin XGB Combining Boolean and XGBoost for Improved Performance9 min

    BoolLin XGB is an innovative approach that combines Boolean transformations with XGBoost, designed to handle datasets containing both Boolean and continuous...

  2. AdaBoost Model in Python:4 min

    AdaBoost, which stands for Adaptive Boosting, is an ensemble learning algorithm that combines multiple weak learners (e.g., decision trees) to create a...

  3. Boosting and Bagging in Machine Learning with Python6 min

    Ensemble methods in machine learning combine multiple models to improve predictive performance and robustness. Two popular ensemble techniques are Boosting...

  4. Boosting Models with Python Decision Trees11 min

    Boosting is an ensemble learning technique that combines multiple weak learners to create a strong predictor. In the context of tree-based models, boosting...

  5. Boosting Techniques for Model Training in Python10 min

    Boosting is an ensemble learning technique that combines multiple weak learners to create a strong predictive model. It focuses on iteratively improving...

  6. Building a Gradient Boosting Machine from Scratch in Python12 min

    Gradient Boosting Machines (GBM) are a powerful ensemble learning technique used in machine learning for both regression and classification tasks. They work...