这篇文章打算介绍一下boosting 和xgboost，这两天也看了好多文章，也感觉了解的不深，算是做个记录。
Boost算法
先简单提一下Bagging， 原理是从现有数据中有放回的抽取若干个样本构建分类器，重复若干次建立若干个分类器进行投票。
而Boost（提升）是指每一步都产生一个弱预测模型，然后加权累加到总模型中。每一步弱预测模型生成的依据都是损失函数的负梯度方向，若干步以后就可以达到逼近损失函数局部的最小值。
首先Boost是一个加法模型，有若干个基函数及其权重乘积之和的累加。
其中b是基函数，beta是基函数的系数，这就是最终分类器的样子。目标就是想办法使损失函数的期望最小值。
一步对m个分类起优化太难，因此有一个稍微折中的办法，因为是加法模型，每一步只对其中一个基函数及其系数进行求解，逐步逼近损失函数的最小值。
要使损失函数最小，那么新加的这一项刚好等于损失函数的负梯度。这样一步一步就使得损失函数下降最快。
这里的lambda可以和beta合并表示步长。对于这个基函数而言，其实就是关于x和这个函数梯度的一个拟合，然后步长的选择可以根据线性搜索，即寻找在这个梯度上下降最小值的那个步长，尽快逼近损失函数的最小值。
梯度提升完
GBDT
首先既然是树，上一篇介绍过，基函数是决策树，而损失函数则是根据具体问题具体分析，不过总体方法都是一样，梯度下降。
比如到第m步， 计算残差。
有了残差，再用（xi， rim）去拟合第m个基函数。假设这颗树把输入空间划分成j个空间R1m, R2m, ...., Rjm。假设在每个空间的输出为bjm。这样，第m棵树可以表示如下：
下一步，对树的每个区域分别用线性搜索的方法寻找最佳步长，然后与上面的区域预测值合并，最后可以得到第m步的目标函数。
对于GBDT容易出现过拟合，所以有必要增加一点正则项，比如叶子节点数目或叶子节点预测值的平方和，限制模型复杂度的过度提升。
XGBoost
之前用的梯度下降只考虑了一阶信息，根据泰勒展开，把二阶信息用上：
其中fm为参数的函数是正则项。可以表示如下：
对于决策树而言，最重要的一共有多少个节点以及节点的权值。所以决策树可以表示为：
各种公式，最后得到
可以得到的结果是：把新一步函数的损失函数变成了只与上一步相关的一个新的损失函数。这样可以遍历数据中所有的分割点，寻找新的损失函数下降最多的分割点，重复上述操作。
相比于梯度下降提升，XGBoost在划分新的树的时候还用到了二阶信息，因此能够更快的收敛；由于用c/c++写的，速度也快。在寻找最加分割点的时候，还可以引入并行计算，因此速度进一步提高。
参考文章：
XGBoost 与 Boosted Tree:多看几遍
