机器学习算法总结之Boosting family：Boosting Tree、GBDT
写在前面
上一篇 机器学习算法总结之Boosting family：AdaBoost 提到Boost但是没说它的整个框架及分类，就在这里记一下。
- Boosting（提升方法） = 加法模型 + 前向分步算法 + 损失函数
- AdaBoost = Boosting + 损失函数是指数函数（基函数任意）
- Boosting Tree（提升树） = Boosting + 基函数是决策树（损失函数任意）
所以从上面的结构可以看出Boosting是一个大的概述性的框架/算法，而AdaBoost 和Boosting Tree是其中的子集/特例。
常用的损失函数主要包括：
1）指数损失函数：决定了Adaboost必须进行加权取样（权重由错误率决定），以进行下一个模型的参数学习，并且决定了最终模型也是加权累计
2）平方误差损失函数：决定了BRT的下一个模型应该学习前一个模型的残差
3）一般损失函数：决定了GBRT/GBDT的下一个模型应该学习前一个模型的梯度（残差近似）
1.提升树（Boosting Tree）简介
提升树是以分类树或者回归树为基本分类器的提升方法。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
提升树模型可以表示为决策树的加法模型：
提升树算法采用的也是前向分步算法，首先确定初始提升树f0（x）=0，第m步的模型为：
通过经验风险极小化确定下一棵树的参数
2.提升树算法
根据前述Boosting框架中三个条件的不同，可以将提升树细分为几种情况：
（1）BDT（提升决策树，二分类）：二叉分类树 + 指数函数 → 加权
可以发现其实就是讲AdaBoost中的基本分类器限定为二分类模型，可以说是AdaBoost的特例。
下面就不再赘述了
（2）BRT（提升回归树）：二叉回归树 + 平方误差函数 → 残差
（3）GBDT（梯度提升决策树）：二叉回归树（或分类树） +普通损失函数 → 损失函数的负梯度
当损失函数式平方误差函数时，就等于BRT
2.1 BRT算法推导
已知一个训练数据集T={(x1,y1),(x2,y2),…,(xN,yN)},X为输入空间，Y为输出空间。如果将输入空间X划分为J个不相交的区域R1，R2…,RJ，并且在每个区域上确定输出的常量cj，那么树可以表示为：
其中，参数：表示树的区域划分和各个区域上的常数，J是回归树的复杂度即叶结点个数。BRT采用的前向回归算法已在第一部分给出，当采用平方误差作为损失函数时：
其中：r=y-f（x）为模型拟合数据的残差。
给出提升回归树算法的具体步骤：
2.2 BRT算法实例（统计学习方法P149）
3. 梯度提升树（GBDT）
GBDT也是Boosting家族的一个重要成员，GBDT有很多简称，有GBT（Gradient Boosting Tree） GTB(Gradient Tree Boosting ) GBRT(Gradient Boosting Regression Tree) MART(Multiple Additive Regression Tree) 其实都是一种算法。
GBDT的弱学习器限定了只能使用CART回归树模型，在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是ft−1(x), 损失函数是L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)，让本轮的损失损失L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
通俗一点解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
于是，解决问题的关键变成了在多种多样的损失函数条件下，怎么找到这个合适的拟合量？
3.1 GBDT的负梯度拟合
针对一个一般损失函数，Freidman提出了梯度提升的算，利用损失函数的负梯度在当前模型的值
来拟合本轮损失的近似值，进而拟合一个回归树。
3.2 GBDT回归算法
我们知道了怎么去找到这个拟合值，接下来就可以生成GBDT模型了。
输入：训练集样本T={(x,y1),(x2,y2),...(xm,ym)}， 最大迭代次数T, 损失函数L。
输出：强学习器f(x)
（1）初始化弱学习器：
（2）对m=1,2，...，M：
（a）对样本i = 1,2,...，N，计算负梯度：
（c）对j=1,2，...，J，计算最佳拟合值
（d）更新学习器：
（3）得到强学习器表达式：
3.3 GBDT分类算法
GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。为了解决这一问题，可以用类似于逻辑回归的对数似然函数，也就是用的是类别的预测概率值和真实概率值的差来拟合。
3.3.1 GBDT二元分类算法
对于二元分类GBDT问题，
- 可以选择损失函数为： L(y,f(x))=log(1+exp(−yf(x)))
- 则此时的负梯度误差为：rti=−[∂L(y,f(xi)))∂f(xi)]f(x)=ft−1(x)=yi/(1+exp(yif(xi)))
- 各个叶节点的最佳残差拟合值为：ctj=argminc∑xi∈Rtjlog(1+exp(−yi(ft−1(xi)+c)))
- 由于上式比较难优化，一般选择使用近似值代替：
有上述过程可以看出，出了负梯度计算和叶节点的残差拟合之外，GBDT分类与回归算法过程相同。
3.3.2 GBDT多元分类算法
对于多元分类问题
- 假设有K类，则此时对数似然函数为：
- 其中如果样本输出类别为k， 则yk = 1。第k类的概率为：
- 结合上述两式，可以算出第t轮的第i个样本对应类别 l 的负梯度误差为
观察可以发现，其实这里的误差啊就是样本i对应类别l 的真实概率和（t-1）轮预测概率的差值。
- 叶节点的最佳残差拟合值为
- 由于上式比较难优化，一般选择使用近似值代替：
-
3.4 GBDT常用损失函数
差不多前面重要的算法也都讲完了，接下来稍微总结一下。
对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种
对于回归算法，其损失函数一般有均方差、绝对损失、Huber损失、分位数损失四种。
ps.（1）Huber损失（Huber Loss wiki），它是均方差和绝对损失的折中，即对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。
pps.（2）分位数损失：
ppps. 对于Huber损失和分位数损失，只要用于健壮回归，也就是减少异常点对损失函数的影响。
3.5 GBDT正则化
和所有机器学习算法一样，GBDT也免不了会出现过拟合风险，需要正则化来减弱，主要有三种形式：
（1）第一种是和Adaboost类似的正则化项，即步长(learning rate)。定义为ν,对于前面的弱学习器的迭代
（2）第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。
（3）第三种是对于弱学习器即CART回归树进行正则化剪枝。与之前一篇决策树内容讲过的相同。（机器学习中树模型算法总结之 决策树（下））
小结
GBDT主要的优点有：
1) 可以灵活处理各种类型的数据，包括连续值和离散值。
2) 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
GBDT的主要缺点有：
1）由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
由于GBDT算法的卓越性，使其成为机器学习研究必须掌握的算法之一，很多面试的问题也都会涉及这个方面，包括其原理、实现以及参数调优等。目前GBDT的算法比较好的库是xgboost，sklearn。
以上~
2018.04.18