1 对决策树使用adaboost

对决策树使用adaboost时，有以下几个问题：

（1）adaboost每次更新的样本权重如何应用到决策树中？

　　由于我们不知道决策树的err目标是什么，因此通常的方法是根据权重对样本采样，然后给决策树训练，这样我们不需要修改决策树算法本身，样本的权重信息就传进去了。

（2）如果处理某个决策树的ε达到0的情况？

　　达到0时，相应的投票数变为无穷大，因此我们需要对树的强度做限制，使得ε不会为0。通常简单的做法是限制树的高度。

　　特别的，当树的高度被限制为1时，且不纯度定义为二分类错误时，decision Tree等效为decision stump:
　　

因此adaboost-Dtree就是：

2 深入看Adaboost

Adaboost是一个特殊的gradient boosting，它有自己的损失函数叫做errADA：

它也是01err的一个上界。

把adaboost写成gradient boosting的形式：

gradient Boosting是Adaboost的延伸。

已知前t-1轮的子模型和投票，在第t轮，选取合适的η和h(x)使得加上该轮后的总模型的损失函数最小，这就是gradient boosting：

如果这里的err是平方误差，有如下推导：

对h的大小做限制，后续用η控制大小，这里限制的方法是加一个平方项作惩罚项：

可以看出，这里是最小化平方误差，也就是在残差（s-y）上做回归。这里我们用回归树来做。

得到了h之后，接下来是选择合适的η：

也就是相当于对于残差和gt转换过的特征做单变量线性回归。

因此，我们的GBDT算法流程如下：