Bagging 和 boosting 有什么区别？
GBDT 和 XGBoost 差在哪？
先弄清楚：每个概念是什么
- Bagging（bootstrap aggregating）
- B 个模型各看一份 bootstrap 数据（有放回地抽 N 次），独立训练后取平均或投票。随机误差互相抵消，降 variance，bias 不变，所以 base 用 deep tree。例：一个样本没被抽中的概率 \((1-1/N)^N \to 1/e \approx 0.37\)，这些 out-of-bag 样本可以估 test error。
- Random forest
- Bagging + 每次 split 只在随机一部分 feature 里挑，让树之间 decorrelate。
- Boosting
- 串行训练浅树，每棵专门补前面的错。降 bias，但树深了很快把 noise 学进去。
- GBDT（gradient boosting）
- 每棵新树 fit 当前 loss 的 negative gradient，乘 learning rate 后加上去。
- XGBoost
- GBDT + Hessian + 显式正则 + 工程优化（并行找 split、缺失值自动选方向）。
30 秒回答
Bagging trains deep trees independently on bootstrap samples and averages them: it cuts variance, keeps bias, and parallelizes. Random forest also samples features at each split to decorrelate the trees, since averaging can't remove the ρσ² term. Boosting trains shallow trees sequentially, each fitting the current ensemble's errors; gradient boosting fits the negative gradient, the residual for squared loss. It cuts bias but can overfit noise, so we use a small learning rate, shallow trees, subsampling and early stopping. XGBoost adds a second-order Taylor expansion, regularization on leaf count and leaf weights, and parallel, sparsity-aware split finding.
对比
| Random forest | GBDT | XGBoost | |
|---|---|---|---|
| 训练 | 独立，可并行 | 串行 | 串行；树内部并行找 split |
| 单棵树 | 深，high variance | 浅 | 浅 |
| 主要降 | variance | bias | bias |
| 导数 | 不用 | gradient | gradient + Hessian |
| 防 overfit | bootstrap + 随机 feature | shrinkage、限深度、subsample | 再加 \(\gamma J + \tfrac12\lambda\|w\|^2\) |
推导
random forest 为什么还要随机选 feature（追问原题）
B 棵树，各自 variance \(\sigma^2\)，两两 correlation \(\rho\)：
\[ \mathrm{Var}\Big(\frac1B\sum_{b} f_b\Big) = \rho\sigma^2 + \frac{1-\rho}{B}\,\sigma^2 \]B 再大也只消掉第二项。最强的 feature 让每棵树都先拿它 split，\(\rho\) 大；随机选 feature 把 \(\rho\) 压下来。例：\(\sigma^2 = 1\)、B = 100，\(\rho = 0.5\) 时 0.505，\(\rho = 0.1\) 时 0.109。
GBDT：每棵新树 fit negative gradient
\[ r_i = -\frac{\partial \ell(y_i, f(x_i))}{\partial f(x_i)},\qquad f_m = f_{m-1} + \nu F_m \]\(F_m\) 是 fit \(r_i\) 的回归树。\(\ell = \tfrac12(y-f)^2\) 时 \(r_i = y_i - f_{m-1}(x_i)\)，就是 residual。
XGBoost：二阶展开 + 正则
\(g_i, h_i\)：loss 的一、二阶导；\(G_j, H_j\)：叶子 \(j\) 内求和；\(J\)：叶子数。
\[ \mathcal L \approx \sum_i \Big[g_i F(x_i) + \tfrac12 h_i F(x_i)^2\Big] + \gamma J + \tfrac12\lambda\sum_j w_j^2 \] \[ w_j^* = -\frac{G_j}{H_j + \lambda} \] \[ \text{gain} = \frac12\Big[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\Big] - \gamma \]gain < 0 就不 split。
手算例子
\(x = 1, 2, 3, 4\)，\(y = 1, 2, 6, 7\)，squared loss，每棵树只切一刀：
- \(f_0 = 4\)（均值），residual \(= (-3, -2, 2, 3)\)，MSE = 6.5。
- 第 1 棵树在 \(x \le 2.5\) 切开，叶子取 residual 均值 \(\mp 2.5\)。\(\nu = 1\) 时 \(f_1 = (1.5, 1.5, 6.5, 6.5)\)，MSE 降到 0.25。
- 换成 XGBoost 算左叶：\(g_i = f_0 - y_i\)，\(G = 5\)，\(H = 2\)。\(\lambda = 0\) 时 \(w^* = -2.5\)，同 GBDT；\(\lambda = 1\) 时 \(w^* \approx -1.67\)，被往 0 收了。
必答点
- Bagging：bootstrap + 并行 deep tree + 平均 → 降 variance
- Random forest：随机选 feature 降树间 \(\rho\)，因为 \(\rho\sigma^2\) 消不掉
- Boosting：串行补错 → 降 bias；shrinkage、浅树、early stopping 防 overfit
- GBDT fit negative gradient；XGBoost 加 Hessian 和正则，\(w^* = -G/(H+\lambda)\)
追问
Boosting 能并行吗？
树之间不能，第 m 棵依赖前 m−1 棵。XGBoost 在树内部并行，数据按 column 预排序成 block。
AdaBoost 和 GBDT 什么关系？
AdaBoost 对应 exponential loss，靠加大分错样本的权重；GBDT 适用任意可导 loss，靠 fit negative gradient。
XGBoost 怎么处理缺失值？
每个 split 学一个 default direction：缺失样本全放左、全放右各算一次 gain，取大的那边。
来源Murphy, PML1 §18.2–18.5（pp.608–620）· Bishop, PRML §14.2–14.3（pp.655–659）· Chen & Guestrin 2016, XGBoost §2.1–2.3、§3.4、§4.1