机器学习 学习笔记(18) 提升树

提升树是以分类树或回归树为基本分类器的提升方法,提升树被认为是统计学习中性能最好的方法之一。

提升方法实际采用加法模型(即基函数的线性组合)与前向分步算法。以决策树为基函数的提升方法称为提升树(boosting tree)。对分类问题决策树时二叉分类树,对回归问题是二叉回归树。提升树模型可以表示为决策树的加法模型:

,其中

表示决策树,

为决策树的参数,M个树的个数。

提升树算法采用前向分步算法,首先确定初始提升树

,第m步的模型是

其中

为当前模型,通过经验风险极小化确定下一颗决策树的参数

由于树的线性组合可以很好地拟合训练数据,即使数据中的输入与输出之间的关系很复杂也是如此,所以提升树是一个高功能的学习算法。

下面叙述回归问题的提升树。

一直一个训练数据集

为输入空间,Y为输出空间。如果将输入空间

划分为J个互不相交的区域

,并且在每个区域上确定输出的常量

,那么树可以表示为:

,其中参数

表示树的区域划分和各区域上的常数,J是回归树的复杂度即叶结点个数。

回归问题的提升树使用以下前向分步算法:

在前向分步算法的第m步,给定当前模型

,需求解

得到

,即第m棵树的参数。

当采用平方误差损失函数时,

,其损失变为

这里

是当前模型拟合数据的残差,所说义,对回归问题提升树算法来说,只需简单地拟合当前模型的残差。

回归问题提升树算法描述如下:

输入:训练数据集

输出:提升树

(1)初始化

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

        (a)计算残差

        (b)拟合残差

学习一个回归树,得到

        (c)更新

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

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

作为回归问题提升树算法中的残差的近似值,拟合一个回归树。

梯度提升算法描述如下:

输入:训练数据集

,损失函数

输出:回归树

(1)初始化

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

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

   (b)对

拟合一个回归树,得到第m棵树的叶结点区域

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

   (d)更新

(3)得到回归树

算法第一步初始化,估计使损失函数极小化的常数值,它是一个只有一个根节点的树。第二步(a)步计算损失函数的负梯度在当前模型的值,将它作为残差的估计,对于平方损失函数,它就是所说的残差;对于一般损失函数,它就是残差的近似值,(b)步估计回归树叶结点区域,以拟合残差的近似值,(c)步利用线性搜索估计叶结点区域的值,使损失函数极小化。(d)更新回归树。第三步得到输出的最终模型

Gradient boosting Decision Tree(GBDT)

GB算法中最典型的基学习器是决策树,尤其是CART,正如名字的含义,GBDT是GB和DT的结合。要注意的是这里的决策树是回归树,GBDT中的决策树是个弱模型,深度较小一般不会超过5,叶子节点的数量也不会超过10,对于生成的每棵决策树乘上比较小的缩减系数(学习率<0.1),有些GBDT的实现加入了随机抽样(subsample 0.5<=f <=0.8)提高模型的泛化能力。通过交叉验证的方法选择最优的参数。因此GBDT实际的核心问题变成怎么基于

使用CART回归树生成

  CART分类树在很多书籍和资料中介绍比较多,但是再次强调GDBT中使用的是回归树。作为对比,先说分类树,我们知道CART是二叉树,CART分类树在每次分枝时,是穷举每一个feature的每一个阈值,根据GINI系数找到使不纯性降低最大的的feature以及其阀值,然后按照feature<=阈值,和feature>阈值分成的两个分枝,每个分支包含符合分支条件的样本。用同样方法继续分枝直到该分支下的所有样本都属于统一类别,或达到预设的终止条件,若最终叶子节点中的类别不唯一,则以多数人的类别作为该叶子节点的性别。回归树总体流程也是类似,不过在每个节点(不一定是叶子节点)都会得一个预测值,以年龄为例,该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点,但衡量最好的标准不再是GINI系数,而是最小化均方差--即(每个人的年龄-预测年龄)^2 的总和 / N,或者说是每个人的预测误差平方和 除以 N。这很好理解,被预测出错的人数越多,错的越离谱,均方差就越大,通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一(这太难了)或者达到预设的终止条件(如叶子个数上限),若最终叶子节点上人的年龄不唯一,则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

Xgboost

  Xgboost是GB算法的高效实现,xgboost中的基学习器除了可以是CART(gbtree)也可以是线性分类器(gblinear)。下面所有的内容来自原始paper,包括公式。

  (1). xgboost在目标函数中显示的加上了正则化项,基学习为CART时,正则化项与树的叶子节点的数量T和叶子节点的值有关。

  (2). GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x),xgboost不仅使用到了一阶导数,还使用二阶导数。

    第t次的loss:

    对上式做二阶泰勒展开:g为一阶导数,h为二阶导数

  (3). 上面提到CART回归树中寻找最佳分割点的衡量标准是最小化均方差,xgboost寻找分割点的标准是最大化,lamda,gama与正则化项相关

   xgboost算法的步骤和GB基本相同,都是首先初始化为一个常数,gb是根据一阶导数ri,xgboost是根据一阶导数gi和二阶导数hi,迭代生成基学习器,相加更新学习器。

xgboost与gdbt除了上述三点的不同,xgboost在实现时还做了许多优化

  • 在寻找最佳分割点时,考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低,xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者,然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
  • xgboost考虑了训练数据为稀疏值的情况,可以为缺失值或者指定的值指定分支的默认方向,这能大大提升算法的效率,paper提到50倍。
  • 特征列排序后以块的形式存储在内存中,在迭代中可以重复使用;虽然boosting算法迭代必须串行,但是在处理每个特征列时可以做到并行。
  • 按照特征列方式存储能优化寻找最佳的分割点,但是当以行计算梯度数据时会导致内存的不连续访问,严重时会导致cache miss,降低算法效率。paper中提到,可先将数据收集到线程内部的buffer,然后再计算,提高算法的效率。
  • xgboost 还考虑了当数据量比较大,内存不够时怎么有效的使用磁盘,主要是结合多线程、数据压缩、分片的方法,尽可能的提高算法的效率。

gbdt 无论用于分类还是回归一直都是使用的CART 回归树

参考

  1. 《统计学习方法》
  2. https://www.cnblogs.com/wxquare/p/5541414.html
  3. GBDT详解
  4. 机器学习算法GBDT的面试要点总结-上篇

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

循环神经网络(RNN)

前言: 前馈神经网络的输入和输出的维数都是固定的,不能任意改变。当处理序列数据时,前馈神经网络就无能力为了。因为序列数据是变长的。为了使得前馈神经网络能处理变长...

35860
来自专栏决胜机器学习

机器学习(十六) ——SVM理论基础

机器学习(十六)——SVM理论基础 (原创内容,转载请注明来源,谢谢) 一、概述 支持向量机(supportvector machine,SVM),是一种分类...

39170
来自专栏AI科技大本营的专栏

详解 | 如何用Python实现机器学习算法

作者 | Lawlite 人生苦短,就用 Python。 在 Kaggle 最新发布的全球数据科学/机器学习现状报告中,来自 50 多个国家的 16000 多位...

60680
来自专栏海天一树

某公司自然语言处理算法笔试题

1 请列出几种文本特征提取算法 答:文档频率、信息增益、互信息、X^2统计、TF-IDF 2 简述几种自然语言处理开源工具包 答:LingPipe、FudanN...

31270
来自专栏机器学习算法工程师

基础|认识机器学习中的逻辑回归、决策树、神经网络算法

逻辑回归。它始于输出结果为有实际意义的连续值的线性回归,但是线性回归对于分类的问题没有办法准确而又具备鲁棒性地分割,因此我们设计出了逻辑回归这样一个算法,它的输...

17530
来自专栏ATYUN订阅号

机器学习入门——使用python进行监督学习

? 什么是监督学习? 在监督学习中,我们首先要导入包含训练特征和目标特征的数据集。监督式学习算法会学习训练样本与其相关的目标变量之间的关系,并应用学到的关系对...

520100
来自专栏杨熹的专栏

权重初始化的几个方法

其中第一步 权重的初始化 对模型的训练速度和准确性起着重要的作用,所以需要正确地进行初始化。

27320
来自专栏数据科学学习手札

(数据科学学习手札26)随机森林分类器原理详解&Python与R实现

一、简介   作为集成学习中非常著名的方法,随机森林被誉为“代表集成学习技术水平的方法”,由于其简单、容易实现、计算开销小,使得它在现实任务中得到广泛使用,因为...

51470
来自专栏超然的博客

Network Embedding

基于Hierarchical softmax 的skip-gram 模型,优化的目标函数如

47240
来自专栏自学笔记

Some methods of deep learning and dimensionality reduction

上一篇主要是讲了全连接神经网络,这里主要讲的就是深度学习网络的一些设计以及一些权值的设置。神经网络可以根据模型的层数,模型的复杂度和神经元的多少大致可以分成两类...

10420

扫码关注云+社区

领取腾讯云代金券