GBDT梯度提升决策树原理详解
GBDT 是常⽤的机器学习算法之⼀，因其出⾊的特征⾃动组合能⼒和⾼效的运算⼤受欢迎。 这⾥简单介绍⼀下 GBDT 算法的原理.
1、决策树的分类
决策树分为两⼤类，分类树和回归树。
分类树⽤于分类标签值，如晴天/阴天/雾/⾬、⽤户性别、⽹页是否是垃圾页⾯；
回归树⽤于预测实数值，如明天的温度、⽤户的年龄、⽹页的相关程度；
两者的区别：
分类树的结果不能进⾏加减运算，晴天晴天没有实际意义；
椒麻鸡做法回归树的结果是预测⼀个数值，可以进⾏加减运算，例如 20 岁+ 3 岁=23 岁。
GBDT 中的决策树是回归树，预测结果是⼀个数值，在点击率预测⽅⾯常⽤ GBDT，例如⽤户点击某个内容的概率。
2、GBDT 概念
GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升决策树。同为Boosting家族的⼀员，它和Adaboost有很⼤的不同。Adaboost 是利⽤前⼀轮弱学习器的误差率来更新训练集的权重，这样⼀轮轮的迭代下去，简单的说是Boosting框架+任意基学习器算法
+指数损失函数。GBDT也是迭代，也使⽤了前向分布算法，但是弱学习器限定了只能使⽤CART回归树模型，同时迭代思路和Adaboost也有所不同，简单的说Boosting框架+CART回归树模型+任意损失函数。
GBDT的思想可以⽤⼀个通俗的例⼦解释，假如有个⼈30岁，我们⾸先⽤20岁去拟合，发现损失有10岁，这时我们⽤6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们⽤3岁拟合剩下的差距，差距就只有⼀岁了。如果我们的迭代轮数还没有完，可以继续迭代下⾯，每⼀轮迭代，拟合的岁数误差都会减⼩。
要理解 GBDT，⾸先就要理解这个 B(Boosting)。
避重就轻的反义词Boosting 是⼀族可将弱学习器提升为强学习器的算法，属于集成学习（enmble learning）的范畴。Boosting ⽅法基于这样⼀种思想：对于⼀个复杂任务来说，将多个专家的判断进⾏适当的综合所得出的判断，要⽐其中任何⼀个专家单独的判断要好。通俗地说，就是"三个臭⽪匠顶个诸葛亮"的道理。
电脑内存不够
Boosting算法的学习机制：先从初始训练集训练出⼀个基学习器，再根据基学习器的表现对训练样本分布进⾏调整，使得先前基学习器做错的的训练样本在后续受到更多关注，然后基于调整后的样本分布训练下⼀个基学习器；重复进⾏，直到基学习器数⽬达到事先指定的值T，最终将这T个基学习器加权结合。
基于梯度提升算法的学习器叫做 GBM(Gradient Boosting Machine)。理论上，GBM 可以选择各种不同的学习算法作为基学习器。GBDT 实际上是 GBM 的⼀种情况。
为什么梯度提升⽅法倾向于选择决策树作为基学习器呢？(也就是 GB 为什么要和 DT 结合，形成 GBDT) 决策树可以认为是 if-then 规则的集合，易于理解，可解释性强，预测速度快。同时，决策树算法相⽐于其他的算法需要更少的特征⼯程，⽐如可以不⽤做特征标准化，可以很好的处理字段缺失的数据，也可以不⽤关⼼特征间是否相互依赖等。决策树能够⾃动组合多个特征。
不过，单独使⽤决策树算法时，有容易过拟合缺点。所幸的是，通过各种⽅法，抑制决策树的复杂性，降低单颗决策树的拟合能⼒，再通过梯度提升的⽅法集成多个决策树，最终能够很好的解决过拟合的问题。由此可见，梯度提升⽅法和决策树学习算法可以互相取长补短，是⼀对完美的搭档。
⾄于抑制单颗决策树的复杂度的⽅法有很多，⽐如限制树的最⼤深度、限制叶⼦节点的最少样本数量、限制节点分裂时的最少样本数量、吸收 bagging 的思想对训练样本采样（subsample），在学习
单颗决策树时只使⽤⼀部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样⼀部分特征、在⽬标函数中添加正则项惩罚复杂的树结构等。
演⽰例⼦：
考虑⼀个简单的例⼦来演⽰ GBDT 算法原理。
下⾯是⼀个⼆分类问题，1 表⽰可以考虑的相亲对象，0 表⽰不考虑的相亲对象。
特征维度有 3 个维度，分别对象 ⾝⾼，⾦钱，颜值
对应这个例⼦，训练结果是 perfect 的，全部正确， 特征权重可以看出，对应这个例⼦训练结果颜值的重要度最⼤，看⼀下训练得到的树。
Tree 0:
Tree 1:
3、原理推导
3.1 ⽬标函数
监督学习的关键概念：模型（model）、参数（parameters）、⽬标函数（objective function）
模型就是所要学习的条件概率分布或者决策函数，它决定了在给定特征向量时如何预测出⽬标。
参数就是我们要从数据中学习得到的内容。模型通常是由⼀个参数向量决定的函数。
⽬标函数通常定义为如下形式：
其中，L 是损失函数，⽤来衡量模型拟合训练数据的好坏程度；Ω称之为正则项，⽤来衡量学习到的模型的复杂度。
对正则项的优化⿎励算法学习到较简单的模型，简单模型⼀般在测试样本上的预测结果⽐较稳定、⽅差较⼩（奥坎姆剃⼑原则）。也就是说，优化损失函数尽量使模型⾛出⽋拟合的状态，优化正则项尽量使模型避免过拟合。
3.2 加法模型
杜字组词GBDT 算法可以看成是由 K 棵树组成的加法模型：
如何来学习加法模型呢？
解这⼀优化问题，可以⽤前向分布算法（forward stagewi algorithm）。因为学习的是加法模型，如果能够从前往后，每⼀步只学习⼀个基函数及其系数（结构），逐步逼近优化⽬标函数，那么就可以简化复杂度。这⼀学习过程称之为 Boosting。具体地，我们从⼀个常量预测开始，每次学习⼀个新的函数，过程如下：
在第 t 步，这个时候⽬标函数可以写为：
举例说明，假设损失函数为平⽅损失（square loss），则⽬标函数为：
其中，称
为残差（residual）。因此，使⽤平⽅损失函数时，GBDT 算法的每⼀步在⽣成决策树时只需要拟合前⾯的模型的残差。
3.3 泰勒公式
定义：
泰勒公式简单的理解，就是函数某个点的取值可以⽤参考点取值和 n+1 阶导数的来表⽰，⽽且这个公式是有规律的⽐较好记。
根据泰勒公式把函数在Ｘ点处⼆阶展开，可得到如下等式：
则等式(1) 可转化为：
假设损失函数为平⽅损失函数，把对应的⼀阶导数和⼆阶导数代⼊等式(4) 即得等式(2)。
由于函数中的常量在函数最⼩化的过程中不起作⽤，因此我们可以从等式(4) 中移除掉常量项，得：
3.4 GBDT 算法
⼀颗⽣成好的决策树，假设其叶⼦节点个数为T，决策树的复杂度可以由正则项
来定义，即决策树模型的复杂度由⽣成的树的叶⼦节点数量和叶⼦节点对应的值向量的 L2 范数决定。
定义集合为所有被划分到叶⼦节点的训练样本的集合。等式(5) 可以根据树的叶⼦节点重新组织为 T 个独⽴的⼆次函数的和：
红宝石鱼
定义，则等式(6) 可写为：
因为⼀元⼆次函数最⼩值处，⼀阶导数等于 0:
此时，⽬标函数的值为
综上，为了便于理解，单颗决策树的学习过程可以⼤致描述为： 1. 枚举所有可能的树结构 q 2. ⽤等式(8) 为每个 q 计算其对应的分数Obj，分数越⼩说明对应的树结构越好 3. 根据上⼀步的结果，找到最佳的树结构，⽤等式(7) 为树的每个叶⼦节点计算预测值
然⽽，可能的树结构数量是⽆穷的，所以实际上我们不可能枚举所有可能的树结构。通常情况下，我们采⽤贪⼼策略来⽣成决策树的每个节点。
1. 从深度为 0 的树开始，对每个叶节点枚举所有的可⽤特征
2. 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的⽅式来决定该特征的最佳分裂点，并记录该特征的最⼤收益（采⽤最佳分裂点时的收益）
3. 选择收益最⼤的特征作为分裂特征，⽤该特征的最佳分裂点作为分裂位置，把该节点⽣长出左右两个新的叶节点，并为每个新节点关联对应的样本集
4. 回到第 1 步，递归执⾏到满⾜特定条件为⽌
3.5 收益的计算
如何计算每次分裂的收益呢？假设当前节点记为 C，分裂之后左孩⼦节点记为 L，右孩⼦节点记为 R，则该分裂获得的收益定义为当前节点的⽬标函数值减去左右两个孩⼦节点的⽬标函数值之和：
根据等式（８）可得：
其中，
项表⽰因为增加了树的复杂性（该分裂增加了⼀个叶⼦节点）带来的惩罚。
huojian四、GBDT损失函数
这⾥我们再对常⽤的GBDT损失函数做⼀个总结。
1.对于分类算法，其损失函数⼀般有对数损失函数和指数损失函数两种:
(1)如果是指数损失函数，则损失函数表达式为
其负梯度计算和叶⼦节点的最佳残差拟合参见Adaboost原理篇。
(2)如果是对数损失函数，分为⼆元分类和多元分类两种，
对于⼆元分类上海市大学
2.对于回归算法，常⽤损失函数有如下4种:
（1）均⽅差，这个是最常见的回归损失函数了
（2）绝对损失，这个损失函数也很常见
对应负梯度误差为：
（3）Huber损失，它是均⽅差和绝对损失的折衷产物，对于远离中⼼的异常点，采⽤绝对损失，⽽中⼼附近的点采⽤均⽅差。这个界限⼀般⽤分位数点度量。
（4）分位数损失。它对应的是分位数回归的损失函数。
曹操的人物形象五、GBDT的正则化
