- Nguyên lý Boosting: Xây dựng một chuỗi các cây quyết định tuần tự, trong đó mỗi cây mới tập trung học cách sửa chữa sai số thặng dư của các cây trước đó.
- Học từ Gradient: Gradient Boosting sử dụng gradient âm của hàm mất mát tổng quát làm mục tiêu huấn luyện cho cây kế tiếp.
- Khai triển Taylor bậc hai của XGBoost: Sử dụng cả đạo hàm bậc một (Gradient) và đạo hàm bậc hai (Hessian) để tối ưu hàm mục tiêu chính xác hơn.
- Thống trị dữ liệu dạng bảng: Vượt trội hơn hẳn mạng nơ-ron học sâu trên các tập dữ liệu có cấu trúc bảng, tài chính và rủi ro.
Gradient Boosting là gì?
Trong khi Random Forest áp dụng triết lý "dân chủ" xây dựng các cây độc lập và lấy biểu quyết đa số, kỹ thuật Boosting lại đi theo con đường "học tập từ sai lầm". Hãy tưởng tượng một học sinh làm một bài kiểm tra: lần đầu tiên làm sai một số câu, lần thứ hai học sinh đó sẽ tập trung ôn luyện kỹ đúng những câu đã làm sai, lần thứ ba tiếp tục sửa các lỗi còn sót lại. Lặp lại quá trình này nhiều lần, học sinh sẽ dần đạt điểm số hoàn hảo.
Đó chính là tư tưởng của Gradient Boosting. Mô hình khởi đầu bằng một dự đoán hằng số thô sơ. Sau đó, tại mỗi vòng lặp, một cây quyết định mới (thường là cây nông, gọi là base learner hoặc weak learner) được huấn luyện để dự đoán sai số thặng dư (residuals) của các cây đi trước. Kết quả cuối cùng là tổng có trọng số của toàn bộ chuỗi các cây.
Nhờ chiến lược học tập tuần tự này, Gradient Boosting liên tục nén sai số huấn luyện xuống mức rất thấp, biến một tập hợp các cây yếu thành một cỗ máy dự đoán cực kỳ mạnh mẽ và chính xác.
Cơ chế toán học của Gradient Boosting
Xét bài toán hồi quy với tập dữ liệu \(\{(x_i, y_i)\}_{i=1}^N\) và hàm mất mát khả vi \(L(y, \hat{y})\). Mục tiêu là tìm hàm dự đoán \(F(x)\) cực tiểu hóa tổng mất mát:
\[\mathcal{L} = \sum_{i=1}^N L(y_i, F(x_i))\]
Thuật toán hoạt động theo các bước tuần tự:
- Khởi tạo mô hình cơ sở: Bắt đầu bằng một giá trị dự đoán hằng số tối ưu:
\[F_0(x) = \arg\min_c \sum_{i=1}^N L(y_i, c)\]
Với hàm mất mát sai số bình phương \(L = \frac{1}{2}(y - \hat{y})^2\), \(F_0(x)\) chính là giá trị trung bình cộng \(\bar{y}\).
- Vòng lặp học tuần tự từ \(m = 1\) đến \(M\):
- Tính gradient âm (pseudo-residuals): Đo lường hướng và độ lớn của sai số đối với từng mẫu dữ liệu:
\[r_{im} = -\left[ \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right]_{F(x) = F_{m-1}(x)}\]
Với hàm mất mát MSE, \(r_{im} = y_i - F_{m-1}(x_i)\), đây chính là sai số thặng dư quen thuộc.
- Huấn luyện cây quyết định mới \(h_m(x)\): Khớp cây quyết định trên tập dữ liệu \(\{(x_i, r_{im})\}_{i=1}^N\) để dự đoán phần dư.
- Cập nhật mô hình: Bổ sung cây mới vào chuỗi với tốc độ học (shrinkage factor) \(\eta \in (0, 1]\):
\[F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)\]
Tốc độ học nhỏ (ví dụ \(\eta = 0.05\) hoặc \(0.1\)) đóng vai trò như một bộ điều chuẩn, ngăn các cây mới không chiếm ưu thế quá mức và giúp mô hình hội tụ mượt mà.
Đột phá của XGBoost (Extreme Gradient Boosting)
Được Tianqi Chen công bố mã nguồn năm 2014 (bài báo cùng Carlos Guestrin ra năm 2016), XGBoost nhanh chóng trở thành vũ khí chiến thắng áp đảo trong hầu hết các cuộc thi khoa học dữ liệu trên Kaggle nhờ các cải tiến toán học và kỹ thuật phần mềm vượt bậc:
1. Khai triển Taylor bậc hai của hàm mục tiêu
Gradient Boosting truyền thống chỉ sử dụng đạo hàm bậc một (Gradient). XGBoost tiến xa hơn bằng cách xấp xỉ hàm mất mát quanh điểm dự đoán hiện tại bằng khai triển chuỗi Taylor bậc hai:
\[\mathcal{L}^{(t)} \approx \sum_{i=1}^N \left[ L(y_i, \hat{y}^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t)\]
Trong đó:
- \(g_i = \partial_{\hat{y}^{(t-1)}} L(y_i, \hat{y}^{(t-1)})\) là gradient bậc một.
- \(h_i = \partial^2_{\hat{y}^{(t-1)}} L(y_i, \hat{y}^{(t-1)})\) là Hessian (đạo hàm bậc hai).
Nhờ có đạo hàm bậc hai \(h_i\), thuật toán có thể tính toán chính xác trọng số tối ưu tại mỗi nút lá \(w_j^*\) dưới dạng công thức giải tích đóng:
\[w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}\]
Và độ tăng chất lượng (Gain) khi phân chia một nút thành hai nút lá con:
\[\text{Gain} = \frac{1}{2} \left[ \frac{(\sum_{i \in I_L} g_i)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{(\sum_{i \in I_R} g_i)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{(\sum_{i \in I} g_i)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma\]
Nếu \(\text{Gain} \lt 0\), thuật toán sẽ không phân nhánh, đóng vai trò như cơ chế tự động tỉa cành (Pruning).
2. Hàm phạt điều chuẩn chặt chẽ \(\Omega(f)\)
XGBoost tích hợp trực tiếp độ phức tạp của cây vào hàm mục tiêu tối ưu:
\[\Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \alpha \sum_{j=1}^T |w_j|\]
Trong đó \(T\) là số lượng nút lá, \(\gamma\) là ngưỡng phạt tối thiểu để tạo thêm một lá mới, \(\lambda\) là điều chuẩn L2 và \(\alpha\) là điều chuẩn L1 trên trọng số các lá. Cơ chế này kiểm soát triệt để kích thước cây và chống quá khớp vượt trội.
3. Tối ưu hóa phần cứng và Tốc độ thực thi
- Xử lý giá trị thiếu (Sparsity Awareness): Mô hình tự động học nhánh đi tối ưu cho các mẫu có dữ liệu bị khuyết (
NaN). - Thuật toán Histogram: Gom các giá trị liên tục thành các thùng (bins) rời rạc, biến phép tìm điểm chia từ \(O(N \log N)\) thành \(O(N)\), tăng tốc độ huấn luyện lên hàng chục lần.
- Tính toán song song: Tận dụng tối đa các luồng CPU và bộ nhớ GPU.
Chiến lược tinh chỉnh siêu tham số then chốt (Hyperparameter Tuning)
Để đạt được sức mạnh tối đa từ XGBoost mà không rơi vào bẫy học vẹt (overfitting), các kỹ sư cần nắm rõ mối tương quan giữa các nhóm siêu tham số:
- Tốc độ học (learning_rate / eta) và số cây (n_estimators): Nên đặt learning_rate nhỏ (ví dụ \(0.01 - 0.05\)) kết hợp với số lượng cây lớn và cơ chế Early Stopping (dừng sớm khi điểm đánh giá trên tập kiểm tra không cải thiện sau \(10 - 20\) vòng lặp liên tiếp).
- Độ sâu tối đa của cây (max_depth): Khác với Decision Tree đơn lẻ có thể phát triển sâu vô hạn, cây trong Boosting chỉ nên có max_depth từ \(3\) đến \(8\) để giữ vai trò là các "người học yếu" (weak learners), tránh tạo ra các quy tắc phân nhánh quá cục bộ.
- Lấy mẫu ngẫu nhiên (subsample và colsample_bytree): Chọn giá trị trong khoảng \(0.7 - 0.8\) cho cả tỷ lệ lấy mẫu dòng dữ liệu lẫn tỷ lệ chọn cột đặc trưng ở mỗi cây. Kỹ thuật này giúp các cây thành phần phân tán góc nhìn và tăng cường tính khái quát hóa vượt trội.
Chủ đề này nằm trong Lecture 13 - Hyperparameter Tuning & Ensemble Methods của Khóa AI. Xem đề cương
Cài đặt mô phỏng Gradient Boosted Trees
Dưới đây là mã nguồn cài đặt thuật toán Gradient Boosted Decision Trees 1 chiều từ đầu bằng Python và C++17, mô phỏng cơ chế huấn luyện tuần tự trên phần dư và tổng hợp dự đoán.
# Gradient Boosted Decision Trees co ban: Hoc tren phan du residuals
import sys
def fit_stump_residual(xs, res):
n = len(xs)
best_mse = 1e18
best_t = xs[0]
best_c_l, best_c_r = 0.0, 0.0
sorted_idx = sorted(range(n), key=lambda i: xs[i])
for i in range(n - 1):
if xs[sorted_idx[i]] == xs[sorted_idx[i+1]]:
continue
thresh = (xs[sorted_idx[i]] + xs[sorted_idx[i+1]]) / 2.0
left_res = [res[j] for j in range(n) if xs[j] <= thresh]
right_res = [res[j] for j in range(n) if xs[j] > thresh]
c_l = sum(left_res) / len(left_res) if left_res else 0.0
c_r = sum(right_res) / len(right_res) if right_res else 0.0
mse = sum((r - c_l) ** 2 for r in left_res) + sum((r - c_r) ** 2 for r in right_res)
if mse < best_mse:
best_mse = mse
best_t = thresh
best_c_l = c_l
best_c_r = c_r
return best_t, best_c_l, best_c_r
def main():
data = sys.stdin.read().split()
if not data: return
it = iter(data)
n = int(next(it))
num_rounds = int(next(it))
lr = float(next(it))
xs = [float(next(it)) for _ in range(n)]
ys = [float(next(it)) for _ in range(n)]
# Initial constant prediction = mean(y)
f0 = sum(ys) / n
preds = [f0] * n
trees = []
for _ in range(num_rounds):
res = [ys[i] - preds[i] for i in range(n)]
t, c_l, c_r = fit_stump_residual(xs, res)
trees.append((t, c_l, c_r))
for i in range(n):
incr = c_l if xs[i] <= t else c_r
preds[i] += lr * incr
q = int(next(it))
q_xs = [float(next(it)) for _ in range(q)]
print(f"rounds={num_rounds} f0={f0:.4f}")
for qx in q_xs:
val = f0
for t, c_l, c_r in trees:
incr = c_l if qx <= t else c_r
val += lr * incr
print(f"{val:.4f}")
if __name__ == "__main__":
main()
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
void fit_stump_residual(const vector<double>& xs, const vector<double>& res, double &best_t, double &best_c_l, double &best_c_r) {
int n = xs.size();
vector<int> idx(n);
for (int i = 0; i < n; ++i) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int a, int b) { return xs[a] < xs[b]; });
double best_mse = 1e18;
best_t = xs[idx[0]];
best_c_l = 0.0; best_c_r = 0.0;
for (int i = 0; i < n - 1; ++i) {
if (xs[idx[i]] == xs[idx[i+1]]) continue;
double thresh = (xs[idx[i]] + xs[idx[i+1]]) / 2.0;
vector<double> left_res, right_res;
for (int j = 0; j < n; ++j) {
if (xs[j] <= thresh) left_res.push_back(res[j]);
else right_res.push_back(res[j]);
}
double sum_l = 0; for (double v : left_res) sum_l += v;
double sum_r = 0; for (double v : right_res) sum_r += v;
double c_l = left_res.empty() ? 0.0 : (sum_l / left_res.size());
double c_r = right_res.empty() ? 0.0 : (sum_r / right_res.size());
double mse = 0;
for (double v : left_res) mse += (v - c_l) * (v - c_l);
for (double v : right_res) mse += (v - c_r) * (v - c_r);
if (mse < best_mse) {
best_mse = mse;
best_t = thresh;
best_c_l = c_l;
best_c_r = c_r;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, num_rounds;
double lr;
if (!(cin >> n >> num_rounds >> lr)) return 0;
vector<double> xs(n), ys(n);
for (int i = 0; i < n; ++i) cin >> xs[i];
for (int i = 0; i < n; ++i) cin >> ys[i];
double sum_y = 0;
for (double v : ys) sum_y += v;
double f0 = sum_y / n;
vector<double> preds(n, f0);
vector<double> tree_t(num_rounds), tree_l(num_rounds), tree_r(num_rounds);
for (int r = 0; r < num_rounds; ++r) {
vector<double> res(n);
for (int i = 0; i < n; ++i) res[i] = ys[i] - preds[i];
fit_stump_residual(xs, res, tree_t[r], tree_l[r], tree_r[r]);
for (int i = 0; i < n; ++i) {
double incr = (xs[i] <= tree_t[r]) ? tree_l[r] : tree_r[r];
preds[i] += lr * incr;
}
}
int q;
cin >> q;
vector<double> q_xs(q);
for (int i = 0; i < q; ++i) cin >> q_xs[i];
cout << fixed << setprecision(4);
cout << "rounds=" << num_rounds << " f0=" << f0 << "\n";
for (int i = 0; i < q; ++i) {
double val = f0;
for (int r = 0; r < num_rounds; ++r) {
double incr = (q_xs[i] <= tree_t[r]) ? tree_l[r] : tree_r[r];
val += lr * incr;
}
cout << val << "\n";
}
return 0;
}
So sánh XGBoost, LightGBM và CatBoost
| Tiêu chí | XGBoost | LightGBM | CatBoost |
|---|---|---|---|
| Chiến lược phát triển cây | Level-wise (theo tầng) | Leaf-wise (theo lá tốt nhất) | Symmetric tree (cây đối xứng) |
| Tốc độ huấn luyện | Rất nhanh (hỗ trợ GPU) | Nhanh nhất trên dữ liệu khổng lồ | Rất nhanh, tối ưu tốt trên GPU |
| Xử lý biến phân loại (Categorical) | Hỗ trợ trực tiếp từ bản 1.5 (enable_categorical=True) |
Tự động gom nhóm phân loại | Xử lý trực tiếp, là thế mạnh chính của CatBoost |
| Nguy cơ Overfitting | Thấp nhờ điều chuẩn L1/L2 | Dễ bị nếu không giới hạn max_depth |
Cực thấp nhờ Ordered Boosting |
- Bẫy tăng quá nhiều cây trong Boosting: Không giống như Random Forest có thể tăng số lượng cây vô hạn, việc tăng số lượng rounds \(M\) quá lớn trong Gradient Boosting chắc chắn sẽ gây ra Overfitting. Luôn luôn sử dụng kỹ thuật
early_stopping_roundsđể ngắt huấn luyện kịp thời khi điểm số trên tập validation chững lại. - Quên chuẩn hóa tốc độ học với số cây: Khi giảm tốc độ học
learning_rateđi một nửa, bạn cần tăng số lượng câyn_estimatorslên tương ứng gấp đôi để đảm bảo mô hình đạt tới điểm tối ưu.
Câu hỏi thường gặp
Vì sao XGBoost vẫn đánh bại Deep Learning trên dữ liệu bảng (Tabular Data)?
Dữ liệu dạng bảng thường có các đặc trưng không đồng nhất, mối quan hệ rời rạc phi tuyến và chứa nhiều nhiễu biên. Cấu trúc cây quyết định phân chia trực giao của XGBoost tự nhiên phù hợp với kiểu dữ liệu này hơn rất nhiều so với các phép biến đổi ma trận liên tục mượt mà của mạng nơ-ron sâu.
Siêu tham số nào quan trọng nhất cần tinh chỉnh trong XGBoost?
learning_rate(thường chọn từ 0.01 đến 0.1).max_depth(độ sâu tối đa của cây, thường từ 3 đến 8).subsamplevàcolsample_bytree(tỷ lệ lấy mẫu dòng và cột, thường từ 0.7 đến 0.9 để chống overfitting).gammavàreg_lambda(tham số điều chuẩn cấu trúc cây).
Khái niệm Leaf-wise trong LightGBM khác gì Level-wise trong XGBoost?
- Level-wise: Phát triển cây cân bằng theo từng tầng ngang, chia đều mọi nút ở cùng độ sâu. An toàn, ít overfitting nhưng có thể lãng phí tính toán ở các nhánh ít đóng góp.
- Leaf-wise: Luôn luôn tìm và phân nhánh tại chiếc lá đem lại độ giảm sai số lớn nhất trên toàn bộ cây, bất kể nó ở độ sâu nào. Tạo ra cây sâu bất đối xứng, hội tụ nhanh hơn nhưng cần kiểm soát
max_depthcẩn thận.
Khóa AI – Introduction to Machine Learning: nền tảng Máy học từ thuật toán cơ bản đến Neural Networks và LLM, học bằng Python. Học thử buổi 1 miễn phí.


