Boosting模型拟合能力很强，放开了让它拟合，可以任意精度的靠近目标函数，地球上的物理规律告诉我们，越牛逼的东西越容易走极端，拟合能力强所以就非常容易出现过拟合(overfitting)，于是各类Gradient Boosting的工程实现都想方设法的控制住boosting，别让它太自由。于是我们来看一下XGBoost如何控制体内巨大的能量，先定义几个符号。
数据集$D \in R^{n \times n}$表示有$n$个样本，每个样本$m$个特征的，如果使用$K$个基学习器来拟合训,那么预测值$\hat{y}$:
$$
\hat{y_i} = \phi(x_i) = \sum_{k=1}^{K}f_{k}(x_i)
$$
$f_{k}$是基学习器,这里基学习器实际上是回归树，给定一个样本$x_i$，回归数就能把这个样本分配到一个叶子结点，比如把样本分到了$l$-th个叶子，$w_l$表示第$l$个叶子结点的score：
$$
f_{k}(x_i) = w_{j}
$$
于是，最终预测出的$\hat{y}$就是$k$棵回归树预测出的$k$个叶子结点的scores的和。
1. 正则
说到防止过拟合，大概第一个想到的就是加正则吧，就像说到砍人就想起西瓜刀一样自然～总共要迭代$K$次学习$K$个基学习器，在每一轮的迭代中给损失函数增加正则项来约束本轮的学习器不要学的太好。对于回归树来说，结构越简单的树general能力越强，于是一种直觉的防止过拟合的手段就是约束本轮迭代的树不要太复杂，XGBoost中对树的叶子节点个数和输出的score进行惩罚
$$
L^{t} = \sum_{i=1}^{n} L \left [ y_i, y_i^{t-1} + f_{t}(x_i) \right ] + \Omega(f_{k})
$$
$$
\Omega(f_k) = \gamma T + \lambda \sum_{i=1}^{T} || w_{i} ||^2 + \alpha \sum_{i=1}^{T} |w_i|
$$
$T$表示回归树$f_{k}$叶子结点的个数, $w_i$叶子节点对应的score（分到这个叶子结点的样本输出这个值）， $\gamma$和$\lambda$ 控制每一项的强度，本身XGBoost也是支持$l_1$正则项，论文里没提，代码里面有，下面的推导还是按没有$L_1$的情况来。
求解上述公式中的$f_{t}$即第$t$轮的目标了，可以使用之前在GBDT中介绍的方法来求解，不过XGBoost采用二阶泰勒展开(Second-ordder approximation)来近似求解，这样做的好处有几点吧
- 二阶近似速度更快，即牛顿方法(Newton’s method)
- 目标函数很多时候是比较复杂的非线性(non-linear)函数，用二阶近似相当于我们在预测值附近构造了一个二次方程(quandratic functions)$\frac{1}{2}h_i(\hat{y}_i – \hat{y}_i^{(t-1)})^2$一定范围内的目标函数，这个比原来的复杂函数要跟更平滑，更容易求解。
- 相比于直接拟合原目标函数，采用二阶近似天然的引入了bias(平滑)，所以可以进一步削弱overfitting的问题
上面目标函数中我们把$\hat{y}^{t} = \hat{y}^{t-1} + f_{t}$，我们将$l(y_i, \hat{y}_i^{t})$展开到二阶
$$l(y_i, \hat{y}_i^{t}) = l(y_i, \hat{y}_i^{t-1} + f_{t}) \simeq l(y_i, \hat{y}_i^{t-1}) + g_i f_{t}(x_i) + \frac{1}{2}h_{i}f_{t}^{2}(x_i)$$
其中$g_i=\partial _{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)}), h_i = \partial^2 _{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)})$，带入到目标函数
$$L^{t} \simeq \sum_{i=1}^{n} \left [ l(y_i, \hat{y}_i^{t-1}) + g_i f_{t}(x_i) + \frac{1}{2}h_{i}f_{t}^{2}(x_i) \right ] + \Omega (f_{t})$$
其中$l(y_i, \hat{y}_i^{t-1})$是一个常数，于是问题是
$$L^{t} \simeq \sum_{i=1}^{n} \left [ g_i f_{t}(x_i) + \frac{1}{2}h_{i}f_{t}^{2}(x_i) \right ] + \Omega (f_{t})$$
其中$g_i$和$h_i$是常数，$f_{t}$是一棵回归数，它有$T$个叶子节点，每个叶子节点输出score是$w_j$，这里定义了一个集合用来分配样本到自己的划分（叶子节点）$I_{j} = \{ i | q(x_i) = j \}$意思是说$I_j$装填了所有被划分到第$j$个划分(叶子节点)的样本集合。于是进一步改写目标函数
$$L^{t} \simeq \sum_{i=1}^{n} \left [ g_i f_{t}(x_i) + \frac{1}{2}h_{i}f_{t}^{2}(x_i) \right ] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_j^2 $$
上面公式是$\sum_{i=1}^{n}$对有样本求和，跟之前聊的GBDT类似，可以把公式分解成添加$T$个子函数，相同叶子节点中的样本输出相同的$w$，所以被划分到叶子节点$I_j$的可以写成
$$w_j \sum_{i \in I_{j}} g_{i} + \frac{1}{2}\sum_{i\in I_{j}}h_i w_j^2 + \frac{1}{2}\lambda w_j^2 = w_j \sum_{i \in I_{j}} g_{i} + \frac{1}{2} w_j^2 (\sum_{i\in I_{j}}h_i + \lambda) $$
这是因为$f_t(x)$的能力就是给样本划分到某个区域，并返回一个score，属于样本划分$I_j$的样本必然都输出$w_j$，即$\sum_{i \in I_{j}} g_{i}f_{t}(x_i) = w_j \sum_{i \in I_{j}} g_{i} $，$T$的划分的话就是
$$= \sum_{j=1}^{T}\left [ w_j \sum_{i \in I_{j}} g_{i} + \frac{1}{2} w_j^2 (\sum_{i\in I_{j}}h_i + \lambda) \right ] + \gamma T$$
$\gamma T$是原来目标函数里的。现在我们先固定$f_t$对样本的划分，上面公式中对$w_j$求一阶导数，这里会有$T$个$w_j$，所以针对某个$w$，外层的$\sum_{j=1}^{T}$就没了。
$$\sum_{i \in I_{j}} g_i + w_j \left (\sum_{i \in I_{j}}h_i + \lambda \right )= 0 $$
于是此时可以知道最优$w_j$
$$w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i\in I_j} h_i + \lambda}$$
简化一下标记，$G_j = \sum_{i \in I_j} g_i, H_j = \sum_{j \in I_j} h_j$，即划分到该node中的样本的Gradients和Hessians，将最有$w_j$带入目标函数可以得到最优解的形式
$$l^{(t)}(q) = \sum_{j=1}^{T} \left [- G_j \cdot \frac{G_j}{H_j + \lambda} + \frac{1}{2} \left ( -\frac{G_j}{H_j + \lambda} \right )^2 (H_j + \lambda) \right ]$$
给加号左边的部分乘以0.5并不影响优化目标，简化一下就是原文的最优解
$$l^{(t)}(q) = – \frac{1}{2}\sum_{j=1}^{T} \frac{ G_j ^2}{H_j + \lambda} + \lambda T$$
上面这个最优解的意思是，在第$t$轮，只要告知怎么划分样本（用任何方法把样本划分开），就可以算出该划分方式能离目标值的差异情况，给你一个常数衡量这个差异。于是我们就可以使用这个常数来指导构造二叉树的过程，先把一堆样本分成两堆，再分别对两堆再分成两堆，即构造决策树的过程。显然这样构造不出最优的决策树，没办法NP-hard问题。最开始只有一个节点标记成$I_{0}$，此时预估值和目标的差异是
$$L_{0} = – \frac{1}{2} \frac{G_{0}^{2}}{H_{0} + \lambda} + \lambda \cdot 1 $$
其中$G_{0}$表示属于节点0的所有样本的将该节点分成两个后，差异是
$$L_{0L} + L_{0R} = – \frac{1}{2} \frac{ G_{0L}^2}{ H_{0L} + \lambda} – \frac{1}{2} \frac{ G_{0R}^2}{H_{0R} + \lambda} + \lambda \cdot 2 $$
用一个节点的差异（直觉上会更大）减去划分成两个节点的差异算出来的就是gain
$$\text{Gain}(0) = L_0 – (L_{0L} + L_{0R}) = \frac{1}{2} \left [ \frac{ G_{0L}^2}{ H_{0L} + \lambda} + \frac{1}{2} \frac{ G_{0R}^2}{H_{0R} + \lambda} – \frac{G_{0}^{2}}{H_{0} + \lambda} \right ] + \lambda $$
分裂后左节点是$\frac{ G_{0L}^2}{ H_{0L} + \lambda}$，右节点是$\frac{1}{2} \frac{ G_{0R}^2}{H_{0R} + \lambda}$，当前未分裂是$\frac{G_{0}^{2}}{H_{0} + \lambda}$,$\lambda$是因为你增加了一个叶子节点导致$f_t$变复杂了给你个惩罚。
2. 收缩系数和列采样
之前在GBDT中提到过收缩系数，就是在学习完第$t$轮的基函数后给它的输出又引入了一个系数，该系数进一步约束了这一轮的贡献，环节overfitting。至于列采样就是约束了第$t$轮的基函数使用那些特征，这个方法之前在随机森林中比较常见，不过现在大家也都放在GBDT的实现中了。