梯度提升(Gradient Boosting)
自己写的老物了, 整理一下发出来, 可能会修改
1. 任意损失函数的Boosting
损失函数的一般表示是: $$ L(y_i, f(x_i)) $$
考虑使用前向分步算法求解一个任意损失函数:
$$ (\beta_m, \gamma_m) = arg\min\limits_{\beta, \gamma} \sum\limits_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma)) \tag{4.1}$$
既然 $\beta b(x_i;\gamma)$ 和 $f_{m-1}(x_i)$ 相比是等价无穷小量, 使用 泰勒级数 在 $f_{m-1}(x_i)$ 附近展开:
$$ L \approx \frac{1}{N} \sum\limits_{i=1}^N L(y_i, f_{m-1}(x_i)) + \beta \sum\limits_{i=1}^N \left. { \frac{\partial L(y_i, s)}{\partial s} } \right |_{s=f_{m-1}(x_i)} b(x_i;\gamma) \tag{4.2}$$
为 (2) 添加正则化项防止 $b(x_i;\gamma)$ 变得太大, 既然我们已经有了 $\beta$ 去调整这个项的大小了:
$$\begin{aligned} L & \approx \frac{1}{N} \sum\limits_{i=1}^N L(y_i, f_{m-1}(x_i)) + \frac{\beta}{2} \sum\limits_{i=1}^N \left. { 2 \frac{\partial L(y_i, s)}{\partial s} } \right |_{s=f_{m-1}(x_i)} b(x_i;\gamma) + b^2(x_i;\gamma) \\ \text{(Strip the constants)} & = \beta \sum\limits_{i=1}^N 2 \frac{\partial L}{\partial s} b(x_i;\gamma) + b^2(x_i;\gamma) \\ & = \beta \sum\limits_{i=1}^N (b(x_i;\gamma) + \frac{\partial L}{\partial s})^2 - (\frac{\partial L}{\partial s} )^2 \end{aligned}\tag{4.3}$$
参考了林轩田的机器学习技法MOOC
2. Gradient Boosting
现在可以最小化损失函数:
- 求解 $b(x_i;\gamma)$. 从 (3) 可知: $$\gamma_m = arg\min\limits_\gamma \beta \sum\limits_{i=1}^N \left(b(x_i;\gamma) + \left. { \frac{\partial L(y_i, s)}{\partial s} } \right |_{s=f_{m-1}(x_i)} \right)^2$$
也就是在每一步 $m$ 中, 利用损失函数的梯度 $-\frac{\partial L(y_i, s)}{\partial s}$ 训练基分类器 $b(x_i;\gamma_m)$. 这就是为什么它被称为梯度提升算法
$$ \text{fit } b(x_i;\gamma_m) = - \left. { \frac{\partial L(y_i, s)}{\partial s} } \right |_{s=f_{m-1}(x_i)}$$ 2. 求解 $\beta$ $$\beta_m = arg\min\limits_\beta \sum\limits_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i;\gamma_m))$$ 既然我们已经有了 $y_i$, $f_{m-1}(x_i)$ 和 $b(x_i;\gamma_m)$, 那原问题就变成了一个简单的一维变量最优化问题, 那就很容易解决了整个算法的思想很简单, 最常用的基分类器是决策树, 称为gradient boosting decision tree (GBDT)
3. GBDT回归算法
基分类器是CART回归树
- 输入: 训练集${\displaystyle {(x_{i},y_{i})}_{i=1}^{n},}$可导损失函数${\displaystyle L(y,F(x)),}$基分类器个数/迭代个数$M$
- 输出: 集成回归器$ F_M(x) $
- 初始化 $$ F_0(x) = \underset{\gamma}{\arg\min} \sum_{i=1}^n L(y_i, \gamma) $$
- 对m个基分类器/回归器 1. 计算损失函数对每个样本的一阶导数近似: $$ r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F(x)=F_{m-1}(x)} \quad {i=1, \ldots, n}$$
- 使用${(x_i, r_{im})}_{i=1}^n$训练下一个回归树 $${\displaystyle h_{m}(x)=\sum _{j=1}^{J_{m}}c_{jm}I(x\in R_{jm}),}$$
- 用一维线性搜索最优化基分类器在每个区间的输出$$ c_{mj} = \underbrace{arg; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{m-1}(x_i) +c) $$ 其中$R_{tj}, j =1,2,…, J$, $J$为叶子节点的数量
- 更新强学习器 $$ F_{M}(x) = f_{m-1}(x) + \sum\limits_{j=1}^{J}c_{mj}I(x \in R_{tj}) $$
4. GBDT分类算法
- 二分类算法 定义预测模型 $$ p(x)=\frac{e^{F(x)}}{e^{F(x)}+e^{-F(x)}} $$ $$ F(x)=\frac{1}{2}log(\frac{p(x)}{1-p(x)}) $$ 预测时将$F(x)$转换成$p(x)$, 然后比较大小. 在此之上定义对数损失函数(MLE损失)
- 多分类算法 类似于Softmax $$ p_k(x) = \frac{\exp(f_k(x))} { \sum\limits_{l=1}^{K} exp(f_l(x))} $$ $$ F_k(x) = log(p_k(x)) - \frac{1}{K} \sum\limits_{i=1}^K log(p_i(x))$$ 损失函数为: $$ L(y, f(x)) = - \sum\limits_{k=1}^{K}y_klog;p_k(x) $$ 集合上两式，我们可以计算出第t轮的第i个样本对应类别k的负梯度误差为: $$ r_{tik} = -\bigg[\frac{\partial L(y, f(x_i)))}{\partial f(x_i)}\bigg]_{f_k(x) = f_{k, t-1};; (x)} = y_{il} - p_{k, t-1}(x_i) $$ 过程:
- 初始化先验分布为均匀分布$ F_k(x) = 1/K $
- 对 $t = 1, 2, \cdots, T$ a. 对每个label, 计算$p_k(x)$ b. 对每个label, 计算损失函数$f_{l, t}$在每个样本$i$处的一阶导数 c. 分别拟合一阶导数, 更新$F_k(x)$
5. 正则化
- Shrinkage $$ f_{k}(x) = f_{k-1}(x) + \nu h_k(x) $$采用步长$0< \upsilon <1$降低每个模型的贡献, 往往伴随着$M$的增加, 即缩减每个基分类器的贡献, 同时使用更多的基分类器, 降低过拟合
- Stochastic gradient boosting 类似于Bagging的手段, 每棵树生成的时候都使用一部分训练数据
- Number of observations in leaves 在停止条件里加入叶节点的样本数量, 小于等于就停止
- Penalize Complexity of Tree
6. 一些其他内容
- DART(Dropout Addictive Regression Tree): 为了解决Boosting过程中, 首先产生的树拥有更大的贡献, 采取类似于Dropout的方法: 每次新加一棵树，这棵树要拟合的并不是之前全部树ensemble后的残差，而是随机抽取的一些树ensemble；同时新加的树结果要规范化一下.
XGBoost
两篇文章已经介绍得很好了:
一句话, 在子树中, 某一个特征的重要度就是所有使用该特征分裂的节点的损失的减少值, 亦即:$$ Gain= - \frac12 \left[ \frac{(G_L+G_R)^2}{H_L+H_R+\lambda} - \frac{G_L^2}{H_L+\lambda} - \frac{G_R^2}{H_R+\lambda} \right] - \gamma $$对某个特征求gain之和, 再对所有基分类器求算术平均值即可得到特征重要度.