machine learning / 机器学习

GBDT

GBDT

1.前言:

网上的GBDT教程很多,但基本都是举一些具体的例子演示一下算法的流程。对于原理往往给个EPaper的地址叫自己看,我又搜了下Gradient Boosting和梯度增强才知道为什么,恩根本没有Gradient Boosting 的中文教程。自己动手丰衣足食吧。

.

2.梯度增强:

GBDTGradient Boosting Decision Tree)叫做梯度增强决策树。看到眼熟的 Boosting大家就该明白这个算法肯定又是通过对迭代生成弱分类器,然后将弱分类器组合成强分类器的算法:)

梯度增强的目标是学到一个模型F,可以预测 ,然后最小化 和真实值y的均方误差 ,这个y表示的是训练集标记的平均值,而不是单独一个样本的标记。

在每次梯度增强的迭代过程 中,可能存在一些不完美的模型Fn(在开始的时候,该模型通常预测的是训练集标记的平均值,这是一个非常弱的模型)。梯度增强在迭代中并不会修改Fn本身,而是通过添加一个评估者h,从而建立一个新的更好的模型 。因此问题变成了怎么找到这个h

假如存在一个完美的h,那么必存在 ,等价于

因此梯度增强就要去拟合 。当模型不完美时,显然这个公式会产生一个损失值(误差)。梯度增强会随着每次迭代,使得模型Fn都会比上一次迭代的Fn-1变得更好,使得损失比上一次迭代变得更小,即损失在收敛(FnFn+1也越来越相似,如果存在完美拟合模型F×,那么最终Fn=Fn+1=F×,此时损失为0)。看到这大家就该明白了,这不就是梯度下降吗!!!这回大家知道这个算法为什么叫“梯度”增强了吧。

然后采用回归决策树学习模型的梯度增强算法就叫做GBDT

.

3.梯度增强算法:

给定训练集 ,迭代步数

该算法目的即找到一个合适的模型 使损失函数的期望值最小。这个损失函数表示为 ,需人为指定采用什么函数。那么有:

其中𝔼是期望值符号。

梯度增强通过附加权重γ的弱分类器h的和组成强分类器 来尽可能的使预测值和真实值y一致:

注意权重是boosting的一大特点,别问我为什么要加这个,自己翻一下boosting的概念就明白了,我那篇Adaboost的文章用权重也叫α很多文章都用γ当权重,会和文章后面的一个重要概念混淆。各种教程都不提这个会很坑新手

根据经验风险最小化原理,该算法尝试找到合适的 使得训练集中通过损失函数计算出的损失值的平均值最小。

.

算法按照以下步骤执行:

A.设置一个初始模型,由常值函数F0(x)组成,通过贪婪算法逐步展开:

这个就是经验风险最小化损失函数,而且上面那个CONST就是这个。

这段如果觉得绕的话看下第一节中的蓝色说明部分。

其中f表示弱分类器集合ℋ中的一个,有 ,注意f(xi)是一个具体的值,下面会解释。

现在明白了吧,F就是n种弱分类器计算出的平均损失最小的损失值再配上n个权重的总和。

F的形式终于搞定了,说好的梯度下降怎么玩?回头看下第一节中的蓝字,如果将损失函数绘制出来,函数曲线上的每两个点的梯度代表的是f(x)。也就是说f(x)FnFn-1的变化量(伪残差/反向梯度值),f(x)=0意味着完美拟合了。这不就是梯度下降吗!

B.开始迭代。

C.计算f(x)。根据梯度下降公式 ,对L求导即可,因此有fn(x)γ(n),很明显这是一个关于所有训练集样本残差的向量。

利用γ(n)作为训练集的样本标记(即 )学习当前迭代过程中对应的h(x)

D.然后通过线搜索算法可求 (自己联立一下上面的公式很容易得到)。

E.最后将所有求得的值带入公式 可求得当前迭代过程中的Fn

F.不断重复上述迭代步骤。

G.达到设置的最大迭代次数后,跳出循环,输出F

.

4.梯度增强决策树GBDT

给定训练集

首先选择固定大小的CART回归树(不是分类树)作为弱分类器。

在第n次迭代中拟合一棵决策树hn(x)计算其残差(样本标记值和预测值的差),设残差的数量为J ,同时每个残差会产生一个叶节点,因此共有J个叶节点。这样树就会将输入数据集划分为 J个不相交的区域。

利用指示函数Indicator Function),可以将hn(x)书写为 ,其中bj(n)是通过区域Rj(n)计算出的预测值。

bj(n)乘以系数αn,然后选择一个线搜索算法(比如梯度下降)最小化损失函数。这样模型又可以写成下面的样子(和第二节中一样):

对树中每个独立的区域分别设置αjn(n×j维向量)。而不用单一的αnn×1维向量)。这个方法叫做树增强(Tree Boost)。

现在模型可以更新为:

根据第二节的步骤计算上述模型即可。

.

5.树的大小:

J表示树的末端节点数,是数据集的可人工调节的方法参数。它表示模型变量之间最大可交互作用级别。当J=2时,变量间是不允许有任何交互作用的;J=3时,最多可以有两个变量交互作用,同理可推J=N时最多可以有N-1个变量交互作用。

通常当 时会达到比较好的增强效果,而且结果对J的选择数量相当不敏感(不容易因为J的选择问题造成不良的结果)。在大多数应用中J=2往往不够,而J>10又没什么必要。

.

6.正则化:

为了避免过拟合问题,很多算法都会引入正则化概念。在GBDT中迭代次数M往往被用来作为正则化参数。M越大则树越多,对训练集的拟合越好,训练集误差越低,然而太高可能会导致过拟合的问题。通常采用交叉验证集对M的大小进行调整。同时其它的正则化方法可以和这个方法一起使用。

.

.

2016.11.10 完成第一版内容,内容比较完整。

2016.11.11

原创内容,转载请注明出处

Leave a Reply

Your email address will not be published. Required fields are marked *