Bagging & Boosting¶

最简单的情形是L2损失（Least square），此时负梯度为： $$ -\frac{\partial L(y, F(x))}{\partial F(x)} = -\frac{\partial (y-F(x))^2}{\partial F(x)} = 2(y-F(x)) $$

注意，这是一个函数，而不是数值。忽略掉2这个缩放系数～

然后，我们用另外一个基模型来拟合它：

不难发现，这实际上就是在不断拟合残差！

如果使用L1损失（Least absolute deviation），此时负梯度为： $$ -\frac{\partial L(y, F(x))}{\partial F(x)} = -\frac{\partial |y-F(x)|}{\partial F(x)} = -\mathrm{sign}(y-F(x)) $$

依然，我们用一个基模型来拟合它。

这里比较有意思的是，在L1损失下，最佳的步长有一个漂亮的形式（加权中位数）：

为了处理长尾数据以及异常值，可以使用Huber Loss： $$ L(y,F) = \begin{cases} 0.5(y-F)^2&|y-F|\le \delta\\ \delta(|y-F|-\delta / 2)&|y-F|\gt \delta\\ \end{cases} $$

此时可以导出：

设数据集$(x_i, y_i) \in (R^d, R)\quad \forall i\in \{1,2,\cdots,n\}$

对于一个树模型$f(\cdot)$，可以做如下的reformulation：

$$ f_t(x) = w_{q(x)} $$

其中$q: R^d\to \{1,2,3,\cdots, T\}$，把输入的特征映射到某一个叶子结点，$w_j$就是每个叶子结点的最终预测。

在这个记号下引入$l_p$正则化：

$$ \Omega_p(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T \mathcal{L}_p (w_j) $$

在Boosting迭代的过程中，我们的目标函数是：

$$ \mathrm{obj_t}= \sum_{i=1}^n l(y_i, \hat{y_i}^{(t)}) + \Omega_p(f_t) $$

其中 $$ \hat{y_i}^{(t)} = \hat{y_i}^{(t-1)} + f_t(x_i) $$ 是通过多个学习器累加得到的。换言之$f_t(x_i)$每次都会拟合残差。

我们把损失函数做二阶展开： $$ l(u, v) \approx l(u, v_0) + \frac{\partial l(u, v)}{\partial v}\mid_{v=v_0} (v-v_0) + \frac{1}{2}\frac{\partial^2 l(u, v)}{\partial v^2}\mid_{v=v_0} (v-v_0)^2 $$ 记： $$ \begin{aligned} &g_i = \frac{\partial l(u, v)}{\partial v}\mid_{v=v_0}\\ &h_i = \frac{\partial^2 l(u, v)}{\partial v^2}\mid_{v=v_0} \end{aligned} $$

代入$u=y_i, v=\hat{y_i}^{(t)}, v_0=\hat{y_i}^{(t-1)}$，得到： $$ \begin{aligned} &\mathrm{obj_t} \\ \approx& \sum_{i=1}^n \left [l(y_i, \hat{y_i}^{(t-1)}) +g_i (\hat{y_i}^{(t)} - \hat{y_i}^{(t-1)}) +\frac{1}{2} h_i (\hat{y_i}^{(t)} - \hat{y_i}^{(t-1)})^2 \right] + \Omega_p(f_t)\\ \approx& \sum_{i=1}^n \left [g_i f_t(x_i) +\frac{1}{2}h_i f_t^2(x_i) \right] + \Omega_p(f_t) + \mathrm{const}\\ \approx& \sum_{i=1}^n \left [g_iw_{q(x_i)} +\frac{1}{2}h_i w_{q(x_i)}^2 \right]+ \Omega_p(f_t) + \mathrm{const}\\ \approx& \sum_{j=1}^T \left [(\sum_{i: q(x_i) = j} g_i) w_j + \frac{1}{2}(\sum_{i: q(x_i) = j} h_i) w_j^2 \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T \mathcal{L}_p (w_j) + \mathrm{const} \end{aligned} $$

记： $$ \begin{aligned} &G_j = (\sum_{i: q(x_i) = j} g_i) \\ &H_j = (\sum_{i: q(x_i) = j} h_i) \end{aligned} $$

不妨先取$l_2$正则化，那么： $$ \mathrm{obj_t} \approx \sum_{j=1}^T \left [ G_j w_j + \frac{1}{2}H_j w_j^2 \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 + \mathrm{const} $$ 也就是： $$ \mathrm{obj_t} \approx \sum_{j=1}^T \left [ G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2 \right] + \gamma T + \mathrm{const} $$

这个式子关于每个叶子节点$w_j$都是二次函数，立即得到最优解： $$ w_j^\dagger = -\frac{G_j}{H_j+\lambda} $$ 此时目标函数值为： $$ \mathrm{obj_t}^\dagger = -\frac{1}{2} \sum_{j=1}^T\frac{G_j^2}{H_j+\lambda} + \gamma T $$

这就是一棵树最优的损失：

在单棵树生长的过程中，我们也可以使用推导出的最优损失来计算增益，从而选择最优的分裂节点： $$ \mathrm{gain} = \frac{1}{2} \left[\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} \right] - \gamma T $$ 或者等价的： $$ \mathrm{gain} = \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} $$

1. 基于直方图的节点分裂：加速、节省内存，但是牺牲一定的精度
   • 注意这里生长的时候是leaf-wise的，一次只长一个叶子结点，这样可以提高精度，但是牺牲一定的泛化性
   • 而XGBoost是level-wise的，一次长一层
2. GOSS：基于梯度的降采样
   • 保留梯度（在L2损失下就是残差）较大的样本，和AdaBoost想法类似
   • 降采样梯度较小的样本，它们已经学的比较好了
   • 如此可以极大减少样本量，提高训练速度
3. Greedy Bundling：贪心算法求解变量捆绑问题
   • 寻找可以捆绑在一起的变量
   • 例如x=[1,0,0,0], y=[0,0,1,1]，可以发现这两个变量不会在同一个位置取到非零
   • 那么它们完全可以合并为z=[1,0,2,2]
4. Merge Exclusive Features：合并打包的变量
   • 对于找到的可以捆绑的变量，把它们merge为一个变量
   • MEF这块可以看一看这位大佬的知乎专栏
   • 这两个算法主要是为了解决高维数据稀疏的问题，通过变量的合并降低维度实现加速