Ensemble Methods

Learning Objectives

• ✓Hiểu Bootstrap, Bagging và đánh giá Out-of-Bag (OOB)
• ✓Nắm Random Forest và feature importance (MDI, Permutation)
• ✓Hiểu Boosting và thuật toán AdaBoost 4 bước
• ✓Hiểu Gradient Boosting fit residuals (gradient descent trong function space)
• ✓Nắm XGBoost: regularized objective, Newton bậc 2, split gain

Ý Tưởng Ensemble

"Wisdom of the Crowd": kết hợp nhiều weak learners (chỉ cần accuracy > 50%) thành strong learner nếu các model đủ đa dạng (diverse) và tốt hơn random — như hội đồng 7 bác sĩ hội chẩn chính xác hơn 1 người. Ba nhóm: Bagging (train song song, độc lập → GIẢM Variance), Boosting (train nối tiếp, model sau sửa lỗi model trước → GIẢM Bias), Stacking (kết hợp output nhiều model khác loại bằng meta-learner). Mục tiêu: giảm một thành phần bias/variance mà không tăng thành phần còn lại.

Bootstrap & Bagging

Bootstrap là lấy mẫu CÓ HOÀN LẠI từ dataset gốc, mỗi bootstrap sample cùng kích thước n. Tính chất quan trọng: P(mẫu không được chọn) = (1−1/n)ⁿ ≈ e⁻¹ ≈ 0.368 → mỗi sample chứa ~63.2% mẫu gốc, ~36.8% bị bỏ qua dùng làm tập "Out-of-Bag" (OOB) test miễn phí. Bagging = Bootstrap Aggregating (Breiman, 1996): train B cây trên B bootstrap samples rồi majority vote (phân loại) / trung bình (hồi quy). Bagging giảm variance nhưng hạn chế: nếu có feature "dominant" thì mọi cây đều chọn nó ở root → tương quan ρ cao → variance giảm ít.

from sklearn.ensemble import BaggingClassifier

# OOB: dùng ~36.8% mẫu không nằm trong bootstrap làm validation
bag = BaggingClassifier(n_estimators=100, oob_score=True, random_state=42)
bag.fit(X_train, y_train)
print(f'OOB score: {bag.oob_score_:.3f}')  # ước lượng test error miễn phí

Random Forest

Random Forest = Bagging + Feature Randomness: tại mỗi split chỉ xét m features ngẫu nhiên thay vì tất cả p features (Classification: m=√p; Regression: m=p/3). Điều này giảm tương quan ρ giữa các cây (feature dominant không phải lúc nào cũng được xét) → giảm variance mạnh hơn Bagging thuần. Feature Importance có hai cách: MDI/Gini Importance (mức giảm impurity — nhanh, built-in, nhưng thiên vị feature high-cardinality) và Permutation Importance (xáo trộn 1 cột, đo mức giảm accuracy trên test — không thiên vị, dùng cho mọi model). RF là "go-to baseline" cho tabular data.

from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance

rf = RandomForestClassifier(
    n_estimators=200,
    max_features='sqrt',   # m = √p
    oob_score=True, n_jobs=-1, random_state=42
).fit(X_train, y_train)

print("Test:", rf.score(X_test, y_test), "OOB:", rf.oob_score_)
result = permutation_importance(rf, X_test, y_test, n_repeats=10)

Boosting & AdaBoost

Boosting train các model tuần tự, mỗi model sau tập trung sửa lỗi model trước, dùng base learner nông (decision stump depth=1). AdaBoost (Freund & Schapire, 1996) 4 bước: (1) khởi tạo trọng số wᵢ = 1/n cho mọi mẫu; (2) train stump, tính weighted error εₜ; (3) tính trọng số model αₜ = ½·ln((1−εₜ)/εₜ) — model tốt (ε thấp) → α lớn; (4) cập nhật trọng số mẫu: sai → wᵢ×exp(+αₜ) tăng, đúng → wᵢ×exp(−αₜ) giảm, rồi normalize. Kết quả: H(x) = sign(Σ αₜ·hₜ(x)). AdaBoost nhạy với noise & outliers (weight mẫu nhiễu tăng mãi).

from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

ada = AdaBoostClassifier(
    estimator=DecisionTreeClassifier(max_depth=1),  # stump
    n_estimators=100,
    learning_rate=0.1,
    random_state=42
).fit(X_train, y_train)
print("Test:", ada.score(X_test, y_test))

Gradient Boosting

Gradient Boosting (Friedman, 2001) tổng quát hóa Boosting: thay vì reweight sample, nó FIT model mới vào pseudo-residuals rᵢ = −∂L/∂F (chính là negative gradient của loss) — hoạt động với BẤT KỲ loss có đạo hàm (MSE → residual thường y−F, Log Loss → y−p). Mỗi cây mới = một bước gradient descent trong FUNCTION SPACE: Fₘ = Fₘ₋₁ + η·hₘ, residual ngày càng nhỏ qua mỗi round. Kiểm soát overfitting bằng shrinkage (learning rate η nhỏ 0.01–0.1 + nhiều cây), subsampling, max_depth 3–6 và early stopping.

from sklearn.ensemble import GradientBoostingClassifier

# F0 = mean(y) → fit cây vào residual → Fm = Fm-1 + η·hm
gb = GradientBoostingClassifier(
    n_estimators=200,
    learning_rate=0.05,    # shrinkage (η nhỏ + nhiều cây = tốt nhất)
    max_depth=3,
    subsample=0.8          # stochastic GB
).fit(X_train, y_train)
print("Test:", gb.score(X_test, y_test))

XGBoost

XGBoost (Chen & Guestrin, 2016) — eXtreme Gradient Boosting, thắng 17/29 giải Kaggle 2015, nhanh hơn GB truyền thống 10x+. Ba cải tiến chính so với GB: (1) Regularized objective = Loss + Ω(f) kiểm soát complexity; (2) Newton bậc 2 — xấp xỉ loss bằng Taylor: L ≈ L + gᵢ·fₜ + ½·hᵢ·fₜ² dùng cả gradient gᵢ và hessian hᵢ (curvature) nên hội tụ nhanh hơn GB chỉ dùng bậc 1; (3) tối ưu kỹ thuật (parallel split finding, cache-aware, tự xử lý missing values). Optimal Split Gain có tham số γ (min loss reduction) tạo post-pruning tự động: Gain ≤ 0 → không split.

import xgboost as xgb

model = xgb.XGBClassifier(
    n_estimators=200, max_depth=5, learning_rate=0.1,
    subsample=0.8, colsample_bytree=0.8,
    reg_lambda=1.0,   # L2 regularization
    reg_alpha=0.0,    # L1 regularization
    gamma=0.0,        # min loss reduction to split (pruning)
    early_stopping_rounds=20, eval_metric='logloss'
)
model.fit(X_train, y_train, eval_set=[(X_val, y_val)], verbose=False)

Bias–Variance & So Sánh

Bagging/RF dùng cây SÂU (low bias, high variance) → trung bình hóa triệt tiêu variance, giữ bias thấp, ít rủi ro overfit (tăng B an toàn). Boosting (AdaBoost/GB/XGB) dùng cây NÔNG/stumps (high bias, low variance) → sửa lỗi tuần tự giảm mạnh bias, nhưng variance có thể tăng nên cần regularization (η nhỏ, early stopping). Kết quả kỳ vọng trên tabular data: DT < Bagging < RF ≈ AdaBoost < GB < XGBoost. Chọn: baseline nhanh → Random Forest; accuracy tối đa → XGBoost/LightGBM; data rất lớn (>1M dòng) → LightGBM.