深入理解Boosting

这篇文章尝试从数学角度理解Boosting，读者请做好心理准备，带好草稿纸:)

Boosting

Boosting 提升法.一种将多个弱分类器通过组合提升为强分类器的思想.
它实现的关键在于：在每轮迭代训练中，通过改变样本权重的方式改变样本分布，从而在下一轮对误分或者偏差大的样本进行近似局部的拟合(类似于加权回归中的加权,这更容易理解)，最后组合起来，达到提升的目的.
这里会有几个问题：
1.每轮训练偏差大小的标准是什么？(与损失函数有关)
2.弱分类器怎么组合？(损失函数 对 模型权重 求偏导)
3.样本权重怎样调整？

这些答案不同组合发展出了不同的Boosting方法。

AdaBoosting

这篇文章对AdaBoosting有非常详细的解说，写得非常好。公式部分慢慢看，其实不难 传送门
对这篇文章做一个总结：

1. Adaboosting的损失函数是指数损失:
2. 通过对损失函数的分析我们能找到每一轮的训练目标:
3. 损失函数对模型权重求偏导可得到模型权重的具体表达
4. 样本权重的更新由构造过程决定

Grandient Boosting 梯度提升

在上文的基础上，我们可以开始学习Gradient Boosting啦
Gradient Boosting可以从两条线来思考：
1.AdaBoosting的推广，当损失函数是平方损失的时候会怎么样
2.Friedman对Gradient Boosting的定义
趁热打铁，我们先从第一条线说起

LSBoost (Least Square Boosting)
AdaBoosting的损失函数是指数损失，而当损失函数是平方损失时，会是什么样的呢？损失函数是平方损失时，有：

括号稍微换一下：

中括号里就是上一轮的训练残差！要使损失函数最小，就要使当轮预测尽可能接近上一轮残差。因此每一轮的训练目标就是拟合上一轮的残差！而且我们可以发现，残差恰好就是平方损失函数对于f(x)的负梯度.这直接启发了Friedman提出Gradient Boosting的总体框架
LSBoosting算法流程如下：


Gradient Boosting框架
Friedman提出了直接让下一轮训练去拟合损失函数的负梯度的想法.当损失函数是平方损失时，负梯度就是残差(LSBoosting);不是平方损失函数时，负梯度是残差的近似.从而Gradient Boosting诞生了.其框架如下：

步骤5中，rho可用线性搜索(line search)的方式得到，可理解为步长.
显然，LSBoosting是Gradient Boosting框架下的特例

看到这里大家可能会想，每一轮中样本怎么改变呢？这在下一篇文章中会详细说明

L2Boosting
L2Boosting是LSBoosting的特例，它对各模型权重(步长)取的是1，样本权重也是1.这在Buhlmann P, Yu Bin的文章中有详细说明PDF.
这意味这只需要用新模型拟合残差，然后不经压缩地加入总体模型就好了…Friedman对其评价是”L2Boosting is thus nothing else than repeated least squares fitting of residuals”.明晃晃的不屑有没有…

其他Gradient Boosting
可以看到，在Gradient Boosting框架下，随着损失函数的改变，会有不同的Boosting Machine出现.

图自Boosting with the L2-Loss:Regression and Classication，Buhlmann P, Yu Bin 也就是上面的PDF
这些损失函数都有一个条件：光滑凸函数

XGBoost

xgboost就是从损失函数的角度提出的，它在损失函数里加入了正则惩罚项，同时认为单单求偏导还不够.因为求偏导实际是一阶泰勒展开,属于一阶优化，收敛速度还不够快.他提出了损失函数二阶泰勒展开式的想法.有兴趣的可以看这篇文章传送门

下一篇文章会以sklearn中的gradient_boosting为基础，具体谈一下GBDT的实现.源码在这