转载:GBDT算法梳理

学习内容:

前向分布算法

负梯度拟合

损失函数

回归

二分类,多分类

正则化

优缺点

sklearn参数

应用场景


转自:https://zhuanlan.zhihu.com/p/58105824

GBDT是一种采用加法模型(即基函数的线性组合)与前向分步算法并以决策树作为基函数的提升方法。通俗来说就是,该算法由多棵决策树组成,所有树的结论加起来形成最终答案。

一、前向分步算法(考虑加法模型)

要理解GBDT算法,得先来了解一下什么是前向分步算法。下面一起来瞧瞧。

加法模型是这样的:

转载:GBDT算法梳理 (就是基学习器的一种线性组合啦)

其中, 转载:GBDT算法梳理 为基函数, 转载:GBDT算法梳理 为基函数的参数, 转载:GBDT算法梳理 为基函数的系数。

在给定训练数据及损失函数 转载:GBDT算法梳理 的条件下,学习加法模型成为损失函数极小化问题:

转载:GBDT算法梳理 (同时求解那么多参数,好复杂)

前向分步算法求解这一优化问题的思路:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步去逼近上述的目标函数式,就可简化优化的复杂度,每一步只需优化如下损失函数:

转载:GBDT算法梳理 (每步学习一个基函数和系数)

前向分步算法流程:

--------------------------------------------------------------------------------------------

输入:训练数据集T=({ 转载:GBDT算法梳理 });损失函数L(y,f(x));基函数集{ 转载:GBDT算法梳理 };

输出:加法模型f(x)

(1) 初始化 转载:GBDT算法梳理

(2) 对m=1,2,...,M

(a) 极小化损失函数

转载:GBDT算法梳理

得到参数 转载:GBDT算法梳理

(b)更新

转载:GBDT算法梳理

(3)得到加法模型

转载:GBDT算法梳理

------------------------------------------------------------------------------------------

可见,前向分步算法将同时求解从m=1到M所有参数 转载:GBDT算法梳理 的优化问题简化成逐步求解各个 转载:GBDT算法梳理 的优化问题了。

二、负梯度拟合

1.提升树算法

了解完前向分步算法,再来看看什么是提升树算法。

提升方法实际采用加法模型与前向分步算法,以决策树作为基函数的提升方法称为提升树。注意,这里的决策树为CART回归树,不是分类树。当问题是分类问题时,采用的决策树模型为分类回归树。为什么要采用决策树作为基函数呢?它有以下优缺点:

优点

  • 可解释性强
  • 可处理混合类型特征
  • 具有伸缩不变性(不用归一化特征)
  • 有特征组合的作用
  • 可自然处理缺失值
  • 对异常点鲁棒
  • 有特征选择作用
  • 可扩展性强,容易并行

缺点

  • 缺乏平滑性(回归预测时输出值只能是输出有限的若干种数值)
  • 不适合处理高维稀疏数据

由于树的线性组合可以很好地拟合训练数据,即使数据中的输入与输出之间的关系很复杂也是如此。

提升树模型可表示为:

转载:GBDT算法梳理

其中, 转载:GBDT算法梳理 表示决策树; 转载:GBDT算法梳理 为决策树的参数;M为树的个数;M为树的个数。

针对不同的问题,提升树算法的形式有所不同,其主要区别在于使用的损失函数不同。而损失函数的不同,决策树要拟合的值也会不同。就一般而言,对于回归问题的提升树算法来说,若损失函数是平方损失函数,每一步只需简单拟合当前模型的残差。

下面看一下在回归问题下,损失函数为平方损失函数的算法流程:

--------------------------------------------------------------------------------------------

输入:训练数据集T={ 转载:GBDT算法梳理 }, 转载:GBDT算法梳理

输出:提升树 转载:GBDT算法梳理

(1)初始化 转载:GBDT算法梳理

(2)对m=1,2,...,M

(a)计算残差

转载:GBDT算法梳理

(b)拟合残差 转载:GBDT算法梳理 学习一个回归树,得到 转载:GBDT算法梳理

(c)更新 转载:GBDT算法梳理

(3)得到回归问题提升树

转载:GBDT算法梳理

--------------------------------------------------------------------------------------------

2.梯度提升

提升树用加法模型与前向分布算法实现学习的优化过程。当损失函数为平方损失和指数损失函数时,每一步优化是很简单的。但对于一般损失函数而言,往往每一步都不那么容易。对于这问题,Freidman提出了梯度提升算法。这是利用最速下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值:

转载:GBDT算法梳理

作为回归问题在当前模型的残差的近似值,拟合一个回归树。

为什么要拟合负梯度呢?这就涉及到泰勒公式和梯度下降法了。

泰勒公式的形式是这样的:

  • 定义:泰勒公式是一个用函数在某点的信息描述其附近取值的公式。
  • 基本形式: 转载:GBDT算法梳理
  • 一阶泰勒展开: 转载:GBDT算法梳理

梯度下降法

在机器学习任务中,需要最小化损失函数 转载:GBDT算法梳理 ,其中 转载:GBDT算法梳理 是要求解的模型参数。梯度下降法常用来求解这种无约束最优化问题,它是一种迭代方法:选择初值 转载:GBDT算法梳理 ,不断迭代更新 转载:GBDT算法梳理 的值,进行损失函数极小化。

  • 迭代公式: 转载:GBDT算法梳理
  • 将 转载:GBDT算法梳理 在 转载:GBDT算法梳理 处进行一阶泰勒展开: 转载:GBDT算法梳理
  • 要使得 转载:GBDT算法梳理 ,可取: 转载:GBDT算法梳理 ,则: 转载:GBDT算法梳理 ,这里 转载:GBDT算法梳理 是步长,一般直接赋值一个小的数。

相对的,在函数空间里,有 转载:GBDT算法梳理

此处把 转载:GBDT算法梳理 看成提升树算法的第t步损失函数的值, 转载:GBDT算法梳理 为第t-1步损失函数值,要使 转载:GBDT算法梳理 ,则需要 转载:GBDT算法梳理 ,此处 转载:GBDT算法梳理 为当前模型的负梯度值,即第t步的回归树需要拟合的值。

至于GBDT的具体算法流程,在后续回归与分类问题会分开说明。

三、损失函数

在GBDT算法中,损失函数的选择十分重要。针对不同的问题,损失函数有不同的选择。

1.对于分类算法,其损失函数一般由对数损失函数和指数损失函数两种。

(1)指数损失函数表达式:

转载:GBDT算法梳理

(2)对数损失函数可分为二分类和多分类两种。

2.对于回归算法,常用损失函数有如下4种。

(1)平方损失函数:

转载:GBDT算法梳理

(2)绝对损失函数:

转载:GBDT算法梳理

对应负梯度误差为:

转载:GBDT算法梳理

(3)Huber损失,它是均方差和绝对损失的折中产物,对于远离中心的异常点,采用绝对损失误差,而对于靠近中心的点则采用平方损失。这个界限一般用分位数点度量。损失函数如下

转载:GBDT算法梳理

对应的负梯度误差为:

 

(4)分位数损失。它对应的是分位数回归的损失函数,表达式为:

转载:GBDT算法梳理

其中 转载:GBDT算法梳理 为分位数,需要我们在回归之前指定。对应的负梯度误差为:

转载:GBDT算法梳理

对于Huber损失和分位数损失,主要用于健壮回归,也就是减少异常点对损失函数的影响。

四、回归问题

梯度提升算法(回归问题)流程:

--------------------------------------------------------------------------------------------

输入:训练数据集T={ 转载:GBDT算法梳理 }, 转载:GBDT算法梳理;损失函数L(y,f(x));

输出:回归树 转载:GBDT算法梳理

(1)初始化

转载:GBDT算法梳理 注:估计使损失函数极小化的常数值,它是只有一个根结点的树

(2)对m=1,2,...,M

(a)对i=1,2,...N,计算

转载:GBDT算法梳理 注: 计算损失函数在当前模型的值,作为残差的估计

(b)对 转载:GBDT算法梳理 拟合一个回归树,得到第m棵树的叶结点区域 转载:GBDT算法梳理 ,j=1,2,...,J

(c)对j=1,2,...,J,计算

转载:GBDT算法梳理 注:在损失函数极小化条件下,估计出相应叶结点区域的值

(d)更新

转载:GBDT算法梳理

(3)得到回归树

转载:GBDT算法梳理

--------------------------------------------------------------------------------------------

五、分类问题(二分类与多分类)

这里看看GBDT分类算法,GBDT的分类算法从思想上和GBDT的回归算法没有区别,但是由于样本输出不是连续的值,而是离散的类别,导致我们无法直接从输出类别去拟合输出类别的误差。

为了解决这个问题,主要有两个方法,一个是用指数损失函数,此时GBDT退化为Adaboost算法。另一种方法用类似逻辑回归的对数似然函数的方法。也就是说,我们用的是类别的预测概率值和真实概率值的差来拟合损失。此处仅讨论用对数似然函数的GBDT分类。对于对数似然损失函数,我们有又有二元分类和的多元分类的区别。

1.二分类GBDT算法

  对于二分类GBDT,如果用类似逻辑回归的对数似然损失函数,则损失函数为:

  转载:GBDT算法梳理

  其中 转载:GBDT算法梳理 {-1,1}。此时的负梯度误差为:

  转载:GBDT算法梳理

  对于生成的决策树,我们各个叶子节点的最佳负梯度拟合值为

  转载:GBDT算法梳理

  由于上式比较难优化,我们一般使用近似值代替

  转载:GBDT算法梳理

  除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索,二分类GBDT与GBDT回归算法过程相同。

2.多分类GBDT算法

  多分类GBDT比二分类GBDT复杂些,对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为K,则此时我们的对数似然损失函数为:

  转载:GBDT算法梳理

  其中如果样本输出类别为k,则 转载:GBDT算法梳理 =1.第k类的概率 转载:GBDT算法梳理 的表达式为:

  转载:GBDT算法梳理

  集合上两式,我们可以计算出第t轮的第i个样本对应类别l的负梯度误差为:

  转载:GBDT算法梳理

  观察上式可以看出,其实这里的误差就是样本i对应类别l的真实概率和t-1轮预测概率的差值。

  对于生成的决策树,我们各个叶子节点的最佳负梯度拟合值为:

  转载:GBDT算法梳理

  由于上式比较难优化,我们一般使用近似值代替

  转载:GBDT算法梳理

  除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索,多分类GBDT与二分类GBDT以及GBDT回归算法过程相同。

六、正则化

  • 对GBDT进行正则化来防止过拟合,主要有三种形式。

    1.给每棵数的输出结果乘上一个步长a(learning rate)。

      对于前面的弱学习器的迭代:

      转载:GBDT算法梳理

      加上正则化项,则有

      转载:GBDT算法梳理

      此处,a的取值范围为(0,1]。对于同样的训练集学习效果,较小的a意味着需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起决定算法的拟合效果。

    2.第二种正则化的方式就是通过子采样比例(subsample)。取值范围为(0,1]。

      GBDT这里的做法是在每一轮建树时,样本是从原始训练集中采用无放回随机抽样的方式产生,与随机森立的有放回抽样产生采样集的方式不同。若取值为1,则采用全部样本进行训练,若取值小于1,则不选取全部样本进行训练。选择小于1的比例可以减少方差,防止过拟合,但可能会增加样本拟合的偏差。取值要适中,推荐[0.5,0.8]。

    3.第三种是对弱学习器即CART回归树进行正则化剪枝。(如控制树的最大深度、节点的最少样本数、最大叶子节点数、节点分支的最小样本数等)

七、GBDT优缺点

1.GBDT优点

  • 可以灵活处理各种类型的数据,包括连续值和离散值。
  • 在相对较少的调参时间情况下,预测的准确率也比较高,相对SVM而言。
  • 在使用一些健壮的损失函数,对异常值得鲁棒性非常强。比如Huber损失函数和Quantile损失函数。

2.GBDT缺点

  • 由于弱学习器之间存在较强依赖关系,难以并行训练。可以通过自采样的SGBT来达到部分并行。

八、sklearn参数

在scikit-learning中,GradientBoostingClassifier对应GBDT的分类算法,GradientBoostingRegressor对应GBDT的回归算法。

具体算法参数情况如下:

GradientBoostingRegressor(loss=’ls’, 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, alpha=0.9, verbose=0,
max_leaf_nodes=None, warm_start=False, presort=’auto’,
validation_fraction=0.1, n_iter_no_change=None, tol=0.0001)

参数说明:

  • n_estimators:弱学习器的最大迭代次数,也就是最大弱学习器的个数。
  • learning_rate:步长,即每个学习器的权重缩减系数a,属于GBDT正则化方化手段之一。
  • subsample:子采样,取值(0,1]。决定是否对原始数据集进行采样以及采样的比例,也是GBDT正则化手段之一。
  • init:我们初始化的时候的弱学习器。若不设置,则使用默认的。
  • loss:损失函数,可选{'ls'-平方损失函数,'lad'绝对损失函数-,'huber'-huber损失函数,'quantile'-分位数损失函数},默认'ls'。
  • alpha:当我们在使用Huber损失"Huber"和分位数损失"quantile"时,需要指定相应的值。默认是0.9,若噪声点比较多,可适当降低这个分位数值。
  • criterion:决策树节搜索最优分割点的准则,默认是"friedman_mse",可选"mse"-均方误差与'mae"-绝对误差。
  • max_features:划分时考虑的最大特征数,就是特征抽样的意思,默认考虑全部特征。
  • max_depth:树的最大深度。
  • min_samples_split:内部节点再划分所需最小样本数。
  • min_samples_leaf:叶子节点最少样本数。
  • max_leaf_nodes:最大叶子节点数。
  • min_impurity_split:节点划分最小不纯度。
  • presort:是否预先对数据进行排序以加快最优分割点搜索的速度。默认是预先排序,若是稀疏数据,则不会预先排序,另外,稀疏数据不能设置为True。
  • validationfraction:为提前停止而预留的验证数据比例。当n_iter_no_change设置时才能用。
  • n_iter_no_change:当验证分数没有提高时,用于决定是否使用早期停止来终止训练。

八、GBDT应用场景

GBDT几乎可以用于所有回归问题(线性/非线性),相对loigstic regression仅能用于线性回归,GBDT的适用面非常广。亦可用于分类问题。

上一篇:elasticsearch-1.3.0 之索引代码粗略梳理


下一篇:IPsec传输模式下ESP报文的装包和拆包过程