# Bagging: Giảm phương sai cho cây học máy


Một [cây quyết định]({{< ref "decision-tree.md" >}}) sâu có [độ chệch thấp nhưng phương sai rất cao]({{< ref "bias-variance-tradeoff.md" >}}): 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

Nếu có $B$ biến ngẫu nhiên độc lập cùng phương sai $\sigma^2$, trung bình cộng của chúng có phương sai giảm $B$ lần:
$$
\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]({{< ref "bootstrap-method.md" >}}): 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

1. **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)**.
2. **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

Nếu các cây tương quan với nhau ($\rho > 0$), phương sai của tổ hợp là:
$$
\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]({{< ref "random-forest.md" >}}) 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*](https://doi.org/10.1007/BF00058655), *Machine Learning*, 24(2), 123–140.