梯度提升树(GBDT)type
status
date
slug
summary
tags
category
icon
password
Property
原理
GBDT概述
GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。Adaboost利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。无论是GBDT分类树还是GBDT回归树，底层使用的都是CART回归树，并没有使用CART分类树。
在GBDT的迭代中，假设前一轮迭代得到的强学习器是，损失函数是，本轮迭代的目标是找到一个CART回归树模型的弱学习器，让本轮的损失函数最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
GBDT的思想可以用一个通俗的例子解释：假如有个人30岁，首先用20岁去拟合，发现损失有10岁，这时用6岁去拟合剩下的损失，发现差距还有4岁，第三轮用3岁拟合剩下的差距，差距就只有一岁了。如果迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
从例子看这个思想还是蛮简单的，但是有个问题是这个损失的拟合不好度量，损失函数各种各样，怎么找到一种通用的拟合方法呢？
GBDT的负梯度拟合
针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。第轮的第个样本的损失函数的负梯度表示为
利用 可以拟合一颗CART回归树，得到了第颗回归树，其对应的叶节点区域。其中为叶子节点的个数。
针对每一个叶子节点里的样本，求出使损失函数最小，也就是拟合叶子节点最好的的输出值如下：
我们的目标是用之前一轮得到的学习器输出加上现在这一轮拟合残差得到的学习器输出一起，让整个损失函数进一步变小，即损失 比 进一步变小，所以要最小化
这样就得到了本轮的决策树拟合函数如下：
的意思是如果在第个叶子区域之内为1， 否则为0
从而本轮最终得到的强学习器的表达式如下：
通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
GBDT回归算法
输入是训练集样本， 最大迭代次数，损失函数
输出是强学习器
1) 初始化弱学习器
2) 对迭代轮数有：
- 对样本，计算负梯度：
- 利用 ，拟合一颗CART回归树，得到第颗回归树，其对应的叶子节点区域为 。其中为回归树t的叶子节点的个数。
- 对叶子区域，计算最佳拟合值
- 更新强学习器
3) 得到强学习器的表达式
GBDT分类算法
GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致无法直接从输出类别去拟合类别输出的误差。
为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。这里仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，又有二元分类和多元分类的区别。
二元GBDT分类算法
对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：
其中，则此时的负梯度误差为
求导后是，分子分母都乘以后，就变成
对于生成的决策树，各个叶子节点的最佳负梯度拟合值为
由于上式比较难优化，一般使用近似值代替
除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同
如果采用指数函数，那么Adaboost每一步就在拟合指数损失的梯度。也就是第轮要依据 拟合一颗决策树：
最后这个式子就是我们Adaboost的需要极小化的损失函数公式，它可以从第一步的GBDT的残差思路递推出来。Adaboost比GBDT先出来，等GBDT出来后，大家才发现Adaboost的思想和GBDT有非常类似之处，甚至可以用GBDT去解释。但这并不意味着两者有完全一样的梯度优化式子，只是有相似的算法思想而已
多元GBDT分类算法
多元GBDT要比二元GBDT复杂一些，对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为，则此时对数似然损失函数为：
其中如果样本输出类别为，则。第类的概率 的表达式为：
集合上两式可以计算出第轮的第个样本对应类别 的负梯度误差为：
观察上式可以看出，其实这里的误差就是样本对应类别的真实概率和轮预测概率的差值
对于生成的决策树，各个叶子节点的最佳负梯度拟合值为
由于上式比较难优化，一般使用近似值代替
除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同
GBDT常用损失函数
对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种:
a) 如果是指数损失函数，则损失函数表达式为
其负梯度计算和叶子节点的最佳负梯度拟合参见Adaboost
b) 如果是对数损失函数，分为二元分类和多元分类两种，参见前面
对于回归算法，常用损失函数有如下4种:
a)均方差，这个是最常见的回归损失函数了
b)绝对损失，这个损失函数也很常见
对应负梯度误差为：
c)Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。
这个界限一般用分位数点度量。损失函数如下：
对应的负梯度误差为：
d)分位数损失。它对应的是分位数回归的损失函数，表达式为
其中为分位数，需要我们在回归前指定。对应的负梯度误差为：
对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响
GBDT的正则化
和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式：
第一种是和Adaboost类似的正则化项，即步长，对于前面的弱学习器的迭代 ，如果我们加上了正则化项，则有， 的取值范围为 。对于同样的训练集学习效果，较小的 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
第二种正则化的方式是通过子采样比例（subsample），取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。
第三种是对于弱学习器即CART回归树进行正则化剪枝。
GBDT小结
由于GBDT的卓越性能，只要是研究机器学习都应该掌握这个算法，包括背后的原理和应用调参方法。目前GBDT的算法比较好的库是
xgboost，当然scikit-learn也可以。GBDT主要的优点有：
- 可以灵活处理各种类型的数据，包括连续值和离散值
- 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的
- 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数
GBDT不止可以使用健壮的损失函数来减少异常点一些。使用到的方法还有：通过正则化来减少异常点影响；通过无放回子采样来减少异常点影响。（对于异常点的鲁棒性，随机森林要比GBDT好的多）
GBDT的主要缺点有：
- 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行
补充
Friedman提出的梯度提升算法，初始化时是将样本标签的均值作为预测值，这样的话，随后通过真实值减预测值不就能得到残差了么？为什么还要用负梯度去拟合残差？
残差只是负梯度的特例，最终的目的是使得损失函数减少的最快，沿哪个方向减少最快呢？负梯度方向。拟合负梯度，相当于损失函数沿着负梯度方向减少。当损失函数为平方损失时，拟合残差就相当于平方损失沿着负梯度方向减小。但是当损失函数不是平方损失时，再拟合残差就不是损失函数沿着负梯度减小了，所以此时当然不能再拟合残差。
Adaboost和GBDT
Adaboost和GBDT不一样的地方最明显的就是损失函数了，adaboost的目标是找到一个可以使当前损失函数最小的弱分类器，具体的数学解是偏导数等于零的解。而GBDT不同的地方是说让偏导数等于零这个解不是对所有的损失函数有效的，在adaboost里面做分类的时候，指数函数做损失函数，这个解是可求的，但是换成一般函数怎么办呢？然后就在损失函数那里做一阶泰勒展开，容易做了，因为展开后变成了一个常数加上一阶梯度和新的弱分类器的乘积，所以梯度和弱分类器的乘积越小，损失函数就越小，所以要拿逆梯度来拟合新的弱分类器，这时候可以把弱分类器分类作为步长，让损失函数沿着梯度在做你梯度下降。至于一些正则项的存在很大程度是为了限制步长和弱分类器的复杂度，限制弱分类器的复杂度就不用说了，限制步长就是因为在逆梯度方向一步不能迈的太大。
GBDT算法迭代过程中，只是对上一步的误差进行拟合；而Adaboost算法里迭代的每一步都是对样本加权后数据进行拟合，然后使本次误差最小。GBDT的确和传统的boost算法不一样，不再围绕权重来做文章。它用的是负梯度拟合，那么这个负梯度拟合起到了和Adaboost样本权重类似的作用。
如果说GBDT二分类，样本标签不是{+1，-1}，而是{+1,0}，损失函数完全等价于逻辑斯特回归的损失函数
比如对于正例，二元逻辑回归的损失是：
负例则是：
对应GBDT的则正例和负例分别是： 和
如果逻辑斯特回归的样本标签是{+1,-1}，那么逻辑回归就没有办法和它的似然函数最大化对应了，只能用GBDT的优化思路来求解，所以说取(-1,1) 还是(0,1)要看优化求解思路
小结
- GBDT本质上是一个不断拟合负梯度的过程，因为很多文章介绍的时候都是以平方误差损失为例，而平方损失的偏导又刚好是残差，所以导致存在一种误解，GBDT就是不断学习残差，以至于换一个损失函数以后，很多人转不过来，其实只要有拟合负梯度的认知就很容易理解GBDT了。对于其中的两个关键问题：①至于为什么拟合负梯度可以得到一个好的模型呢？因为沿着负梯度的方向学习，效率是最高的，当负梯度为0时，全局损失函数就是最好的，得到的强学习器F(x)自然也是比较好的。②为什么每个弱学习器的组合方式是相加呢？因为梯度下降或者说泰勒展开式的形式就是加法。
- 对于分类问题，每棵CART树的分裂点选择还是基于MSE的，这样可以保证当前CART树的损失最小，但是每个叶子的预测值C不再是由所有样本label的均值确定，因为均值虽然可以使当前CART树的损失最小，却不能保证全局的损失最小，因此采用那个近似值公式重新计算一个C，但是这个C并不是当前CART树的最优值。
- 对于分类问题，其本质和回归树是一致，只不过对每个类别都建立一棵树，拟合的目标值是(0,1)，即概率值，只不过一般取得损失函数不同而已。
代码
在sacikit-learn中，
GradientBoostingClassifier为GBDT的分类类， GradientBoostingRegressor为GBDT的回归类。两者的参数类型完全相同，当然有些参数比如损失函数loss的可选择项并不相同。这些参数中，类似于Adaboost，我们把重要参数分为两类，第一类是Boosting框架的重要参数，第二类是弱学习器即CART回归树的重要参数。GBDT类库boosting框架参数
- n_estimators：也就是弱学习器的最大迭代次数，或者说最大的弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。默认是100。在实际调参的过程中，常常将n_estimators和learning_rate一起考虑
- learning_rate：每个弱学习器的权重缩减系数 ，也称作步长，加上了正则化项，强学习器的迭代公式为 。 的取值范围为 。对于同样的训练集拟合效果，较小的 意味着需要更多的弱学习器的迭代次数。通常用步长和迭代最大次数一起来决定算法的拟合效果。一般来说，可以从一个小一点的开始调参，默认是1。
- subsample： 即子采样，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间，默认是1.0，即不使用子采样。
- init：即初始化时候的弱学习器，拟合对应 ，如果不输入，则用训练集样本来做样本集的初始化分类回归预测。否则用init参数提供的学习器做初始化分类回归预测。一般用在我们对数据有先验知识，或者之前做过一些拟合的时候，如果没有的话就不用管这个参数了。
- loss： 即GBDT算法中的损失函数。分类模型和回归模型的损失函数是不一样的。
对于分类模型，有对数似然损失函数"deviance"和指数损失函数"exponential"两者输入选择。默认是对数似然损失函数"deviance"。一般来说，推荐使用默认的"deviance"。它对二元分离和多元分类各自都有比较好的优化。而指数损失函数等于把我们带到了Adaboost算法。
对于回归模型，有均方差"ls", 绝对损失"lad", Huber损失"huber"和分位数损失“quantile”。默认是均方差"ls"。一般来说，如果数据的噪音点不多，用默认的均方差"ls"比较好。如果是噪音点较多，则推荐用抗噪音的损失函数"huber"。而如果需要对训练集进行分段预测的时候，则采用“quantile”
- alpha：这个参数只有GradientBoostingRegressor有，当使用Huber损失"huber"和分位数损失“quantile”时，需要指定分位数的值。默认是0.9，如果噪音点较多，可以适当降低这个分位数的值
GBDT类库弱学习器参数
由于GBDT使用了CART回归决策树，因此它的参数基本来源于决策树类，也就是说，和DecisionTreeClassifier和DecisionTreeRegressor的参数基本类似。
- 划分时考虑的最大特征数max_features：可以使用很多种类型的值，默认是"None"，意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑 个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑 个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，用默认的"None"就可以了，如果特征数非常多，可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间
- 决策树最大深度max_depth：默认可以不输入，如果不输入的话，默认值是3。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间
- 内部节点再划分所需最小样本数min_samples_split：这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2，如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值
- 叶子节点最少样本数min_samples_leaf： 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1，可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值
- 叶子节点最小的样本权重和min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。 默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了
- 最大叶子节点数max_leaf_nodes：通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到
- 节点划分最小不纯度min_impurity_split：这个值限制了决策树的增长，如果某节点的不纯度(基于基尼系数，均方差)小于这个阈值，则该节点不再生成子节点。即为叶子节点 。一般不推荐改动默认值1e-7