Bagging: Giảm phương sai cho cây học máy
Bản chất toán học của việc gộp nhiều mô hình bất ổn
Một cây quyết định sâu có độ chệch thấp nhưng phương sai rất cao: nó ghi nhớ nhiễu và rất nhạy với mẫu huấn luyện.
Năm 1996, Leo Breiman đề xuất Bagging (Bootstrap Aggregating) giúp triệt tiêu phương sai mà không tăng độ chệch.
1. Trực giác toán học: Sức mạnh số đông
$$ \operatorname{Var}\left(\frac{1}{B}\sum_{b=1}^B \hat{f}_b(x)\right) = \frac{\sigma^2}{B}. $$Không thể thu thập thêm dữ liệu thật, Bagging dùng Bootstrap: tái lấy mẫu có hoàn lại từ tập ban đầu để tạo $B$ tập huấn luyện.
2. Quy trình hai bước
- Bootstrap: Rút ngẫu nhiên có hoàn lại $B$ tập mẫu kích thước $N$. Trung bình mỗi tập chứa $\approx 63{,}2%$ số quan sát; $36{,}8%$ còn lại gọi là Out-Of-Bag (OOB).
- Aggregating: Trồng một cây sâu trên từng mẫu bootstrap. Khi dự đoán:
- Hồi quy: Lấy trung bình cộng dự đoán của $B$ cây.
- Phân loại: Lấy biểu quyết theo đa số (majority vote).
3. Out-Of-Bag Error: Kiểm định miễn phí
Mỗi quan sát được kiểm định trên chính các cây mà nó không tham gia huấn luyện (khoảng $B/3$ cây). Gom dự đoán OOB lại, ta có ước lượng sai số ngoài mẫu tương đương Cross-Validation mà không tốn chi phí.
4. Giới hạn và bước chuyển sang Random Forest
$$ \operatorname{Var} = \rho \sigma^2 + \frac{1 - \rho}{B}\sigma^2 \xrightarrow{B \to \infty} \rho \sigma^2. $$Khi có đặc trưng chi phối mạnh, các cây đều chọn cùng phép chia ở gốc khiến $\rho$ cao, làm nghẽn mức giảm phương sai. Để bẻ gãy sự tương quan này, Random Forest chọn ngẫu nhiên một tập con đặc trưng tại mỗi nút chia.
Tài liệu tham khảo
- Leo Breiman (1996), Bagging Predictors, Machine Learning, 24(2), 123–140.