一, 前向分布算法
加法模型
加法模型公式:
其中, 为基函数, 为基函数参数, 为基函数系数, 表示该项函数在加法模型中的重要性
前向分步算法
在给定训练数据和损失函数 L(y,f(x)) 的条件下, 学习加法模型成为经验风险极小化 (即损失函数极小化问题)
即最小化每一步生成的基函数之和. 前向分步算法求解这一优化问题的想法是: 由于学习的是加法模型, 如果能从前向后每一步只学习一个基函数及其系数, 逐步逼近优化目标函数式. 那么可以简化算法复杂度, 优化每一步的基分类器. 即每次只优化当前的基分类器, 使其损失函数最小.
《统计学习方法》
《统计学习方法》
这样, 前向分布算法将同时求解从 m=1 到 M 的所有参数的优化问题简化为逐次求解各个基分类器对应的参数问题.
负梯度拟合
大牛 Freidman 提出了用损失函数的负梯度来拟合本轮损失的近似值, 进而拟合一个 CART 回归树. 第 t 轮的第 i 个样本的损失函数的负梯度表示为:
利用 我们可以拟合一颗 CART 回归树, 得到了第 t 颗回归树, 其对应的叶节点区域 . 其中 J 为叶子节点的个数. 针对每一个叶子节点里的样本, 我们求出使损失函数最小, 也就是拟合叶子节点最好的的输出值 如下:
这样我们就得到了本轮的决策树拟合函数如下:
从而本轮最终得到的强学习器的表达式如下:
通过损失函数的负梯度来拟合, 我们找到了一种通用的拟合损失误差的办法, 这样无轮是分类问题还是回归问题, 我们通过其损失函数的负梯度的拟合, 就可以用 GBDT 来解决我们的分类回归问题. 区别仅仅在于损失函数不同导致的负梯度不同而已.
损失函数
不同问题对应的损失函数不同, 这篇博客做了一个很好的总结. 后续对应不同的问题会有不同的损失函数. 梯度提升树 (GBDT) 原理小结 http://www.cnblogs.com/pinard/p/6140514.html
回归
二分类, 多分类
二元 GBDT 分类算法
对于二元 GBDT, 如果用类似于逻辑回归的对数似然损失函数, 则损失函数为:
其中 . 则此时的负梯度误差为
对于生成的决策树, 我们各个叶子节点的最佳负梯度拟合值为
由于上式比较难优化, 我们一般使用近似值代替
除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索, 二元 GBDT 分类和 GBDT 回归算法过程相同.
多元 GBDT 分类算法
多元 GBDT 要比二元 GBDT 复杂一些, 对应的是多元逻辑回归和二元逻辑回归的复杂度差别. 假设类别数为 K, 则此时我们的对数似然损失函数为:
其中如果样本输出类别为 k, 则 . 第 k 类的概率 的表达式为:
集合上两式, 我们可以计算出第 轮的第 个样本对应类别 的负梯度误差为
观察上式可以看出, 其实这里的误差就是样本 对应类别 的真实概率和 轮预测概率的差值. 对于生成的决策树, 我们各个叶子节点的最佳负梯度拟合值为
上式比较难优化, 我们可以使用近似值代替
除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索, 多元 GBDT 分类和二元 GBDT 分类以及 GBDT 回归算法过程相同.
正则化
和 Adaboost 一样, 我们也需要对 GBDT 进行正则化, 防止过拟合. GBDT 的正则化主要有三种方式.
• 第一种是和 Adaboost 类似的正则化项, 即步长 (learning rate). 定义为 , 对于前面的弱学习器的迭代
如果我们加上了正则化项, 则有
的取值范围为 . 对于同样的训练集学习效果, 较小的 意味着我们需要更多的弱学习器的迭代次数. 通常我们用步长和迭代最大次数一起来决定算法的拟合效果.
• 第二种正则化的方式是通过子采样比例 (subsample). 取值为 (0,1]. 注意这里的子采样和随机森林不一样, 随机森林使用的是放回抽样, 而这里是不放回抽样. 如果取值为 1, 则全部样本都使用, 等于没有使用子采样. 如果取值小于 1, 则只有一部分样本会去做 GBDT 的决策树拟合. 选择小于 1 的比例可以减少方差, 即防止过拟合, 但是会增加样本拟合的偏差, 因此取值不能太低. 推荐在 0.5, 0.8 之间. 使用了子采样的 GBDT 有时也称作随机梯度提升树 (Stochastic Gradient Boosting Tree, SGBT). 由于使用了子采样, 程序可以通过采样分发到不同的任务去做 boosting 的迭代过程, 最后形成新树, 从而减少弱学习器难以并行学习的弱点.
• 第三种是对于弱学习器即 CART 回归树进行正则化剪枝.
优缺点
优点
可以灵活处理各种类型的数据, 包括连续值和离散值.
在相对少的调参时间情况下, 预测的准确率也可以比较高. 这个是相对 SVM 来说的.
使用一些健壮的损失函数, 对异常值的鲁棒性非常强. 比如 Huber 损失函数和 Quantile 损失函数.
缺点
由于弱学习器之间存在依赖关系, 难以并行训练数据. 不过可以通过自采样的 SGBT 来达到部分并行.
sklearn 参数
class sklearn.ensemble.GradientBoostingClassifier(loss='deviance', learning_rate=0.1, n_estimators=100, subsample=1.0, criterion='friedman_mse', min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_depth=3, min_impurity_decrease=0.0, min_impurity_split=None, init=None, random_state=None, max_features=None, verbose=0, max_leaf_nodes=None, warm_start=False, presort='auto', validation_fraction=0.1, n_iter_no_change=None, tol=0.0001)[source]¶
几个主要参数:
loss : {'deviance', 'exponential'}, optional (default='deviance') loss function to be optimized. 'deviance' refers to deviance (= logistic regression) for classification with probabilistic outputs. For loss 'exponential' gradient boosting recovers the AdaBoost algorithm. 损失函数
learning_rate: 学习率
n_estimators: int (default=100) 弱学习器的个数
应用场景
由于缺乏这方面的经验, 故此部分不作赘述. 查到了一篇文章: GBDT 入门教程之原理, 所解决的问题, 应用场景讲解
参考
[机器学习] 集成学习 (三)---- 前向分步算法, 提升树与 GBDT
GBDT 算法详解 https://www.zybuluo.com/Dounm/note/1031900#412
来源: https://juejin.im/post/5c7b7bf451882530a269a1ba