What is the difference between boosting and bagging (Random Forest)? Compare their tendency to overfit.

Bagging and boosting are ensemble learning methods that combine multiple models to improve prediction quality, but they do so in different ways.

Bagging (e.g., Random Forest):

• Creates multiple independent models (usually trees), each trained on a random bootstrap sample of data.
• The final prediction is an average (for regression) or a majority vote (for classification) of all models.
• The main goal is to reduce the variance of the model and increase robustness to noise.
• Tends to have lower overfitting because models are trained independently and averaging smooths errors.

Boosting:

• Models are trained sequentially, each trying to correct the errors of the previous ones.
• Data object weights are adjusted to focus more on difficult-to-classify examples.
• The final prediction is a weighted sum of all models' predictions.
• The main goal is to reduce bias and increase accuracy.
• More prone to overfitting, especially with many iterations and weak regularization.

Summary:

• Bagging better combats overfitting due to model independence and averaging.
• Boosting can overfit but often yields higher accuracy with proper tuning.

Example of Random Forest and AdaBoost (pseudo-code):

# Bagging
for i in range(N):
    sample = bootstrap_sample(data)
    model_i = train_decision_tree(sample)
models.append(model_i)

# Prediction
prediction = majority_vote([m.predict(x) for m in models])

# Boosting
weights = initialize_weights(data)
for i in range(N):
    model_i = train_weak_learner(data, weights)
    error = compute_error(model_i, data, weights)
    update_weights(weights, model_i, error)
models.append(model_i)

# Prediction
prediction = weighted_sum([m.predict(x) for m in models], model_weights)