集必得特

集必得特

文章目录

• GBDT
• • 一、 DT：回归树 Regression Decision Tree
  • 二、 GB：梯度迭代 Gradient Boosting
  • 三、 GBDT工作过程实例
  • • 图1和图2 效果相同，为何还需GBDT？
  • caokan
• GBDT
• • 1.简介
  • 2 正式介绍
  • caokan

GBDT

• 三概念：
  • Regression Decistion Tree（即DT)，
  • Gradient Boosting（GB)，
  • Shrinkage (算法的一个重要演进分枝，目前大部分源码都按该版本实现）。
  • 搞定这三后就能明白GBDT如何工作
  • 理解它如何用于搜索排序则需额外理解RankNet
  • 下文将逐个碎片介绍，最终把整张图拼出来。

一、 DT：回归树 Regression Decision Tree

• 提起决策树
• 首先想到的就是C4.5分类
• 一开始就把GBDT中的树想成分类树，那就是歪路，
  • 不要以为GBDT是很多棵分类树
• 决策树分，回归树和分类
• 预测实数值，明天温度、用户年龄、网页的相关程度
• 分类标签值，如晴天/阴天/、用户性别、网页是否是垃圾页面
• 前者的结果加减是有意义，后者则无意义，如男+男+女=？
• GBDT的核心在于累加所有树的结果作为最终结果
  • 就像前面对年龄的累加（-3是加负3
  • 分类树的结果没办法累加的，所以GBDT中的树都是回归树，不是分类树，这点对理解GBDT相当重要（GBDT调整后也可用于分类但不代表GBDT的树是分类树）。
  • 回归树是如何工作？

 

• 以对人的性别判别/年龄预测，
• 每个instance都是一个我们已知性别/年龄的人，
• feature则包括这个人上网的时长、上网的时段、网购所花的金额

 

• 先说分类树，C4.5分类树在每次分枝时，
• 穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的feature和阈值（熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1），
• 按照该标准分枝得到两个新节点，
• 用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，
• 或达到预设的终止条件，
• 若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

 

• 回归树总体流程类似
• 不过在每个节点（不一定是叶子节点）都会得一个预测值
• 年龄为例，预测值=属于这个节点的所有人年龄的平均值
• 分枝时穷举每一个feature的每个阈值找最好的分割点
  • 衡量标准不是最大熵，是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N
• 被预测出错的人数越多，错离谱，均方差就越大，
  • 最小化均方差能找到最靠谱的分枝依据
• 分枝直到每个叶子节点上人的年龄都唯一（太难了）或达到预设的终止条件（叶子个数上限），若最终叶子节点上人的年龄不唯一，
  • 则以该节点上所有人的平均年龄做为该叶子节点的预测年龄
• 还不明白可以Google “Regression Tree”，
  • 或阅读本文的第一篇论文中Regression Tree部分。

二、 GB：梯度迭代 Gradient Boosting

• 我并不想多讲Gradient Boosting的原理，
  • 不明白原理无碍于理解GBDT中的Gradient Boosting。
  • 砂锅问可阅读这篇英文wiki

 

• Boosting，迭代，即通过迭代多棵树共同决策。
• 难道是每棵树独立训练一遍，
  • 比如A这个人，第一棵树认为是10岁，
  • 第二棵树认为是0岁，
  • 第三棵树认为是20岁，
  • 我们就取平均值10岁做最终结论？
  • –当然不是！且不说这是投票方法并不是GBDT，
  • 训练集不变，独立训练三次的三棵树必定完全相同，这样做完全没有意义。
  • GBDT是把所有树的结论累加起来做最终结论的，所以可以想到每棵树的结论并不是年龄本身，而是年龄的一个累加量。
  • GBDT的核心在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。
  • A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。
  • 第二棵树里我们把A的年龄设为6岁去学习，
    • 如果第二棵树真的能把A分到6岁的叶子节点，
    • 那累加两棵树的结论就是A的真实年龄；
    • 如果第二棵树的结论是5岁，则A仍然存在1岁的残差，
    • 第三棵树里A的年龄就变成1岁，
    • 继续学。这就是Gradient Boosting在GBDT中的意义

三、 GBDT工作过程实例

• 训练集4人，A,B,C,D，14,16,24,26。
• A、B高一和高三；
• C,D应届毕业和工作两年
• 传统的回归决策树，得图1

 

• 现用GBDT，
• 数据太少，
• 限定叶子节点做多有两，即每棵树都只有一个分枝，
  • 且限定只学两棵树。
  • 我们会得到如下图2

 

• A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。
• 所以A的残差就是16-15=1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。A,B,C,D的残差分别为-1,1，-1,1。
• 拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。
• 第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。

 

• 现在A,B,C,D的预测值都和真实年龄一致了。
• A: 14岁高一，购物少，经常问学长问题；预测A = 15 – 1 = 14
• B: 16岁高三；购物少，经常被学弟问问题；预测B = 15 + 1 = 16
• C: 24岁应届毕业生；购物多，经常问师兄问题；预测C = 25 – 1 = 24
• D: 26岁工作两年；购物多，经常被师弟问问题；预测D = 25 + 1 = 26

 

• 哪里体现了Gradient
• 回到第一棵树结束时想一想，
  • 无论此时cost function是什么，是均方差还是均差，只要它以误差作为衡量标准，残差向量(-1, 1, -1, 1)都是它的全局最优方向，这就是Gradient。

 

• 已把GBDT最核心、运算过程讲完了！
• 讲到这里很容易发现三个问题

图1和图2 效果相同，为何还需GBDT？

• 过拟合是指为了让训练集精度更高，学到了很多”仅在训练集上成立的规律“，导致换一个数据集当前规律就不适用了。
• 只要允许一棵树的叶子节点足够多，训练集总能训练到100%（大不了最后一个叶子上只有一个instance)。
• 在训练精度和实际精度（或测试精度）之间，后者才是我们想要真正得到的。

 

• 图1为了达到100%精度用3个feature（上网时长、时段、网购金额），分枝“上网时长>1.1h” 显然过拟合，这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时，但用上网时间是不是>1.1小时来判断所有人的年龄很显然是有悖常识；

 

• 图2的boosting虽然用两棵树 ，但其实只用2个feature就搞定，
  • 后一个feature是问答比例，图2的依据更靠谱。
• Boosting每一步的残差计算变相增大分错instance的权重，
  • 分对的instance都趋向0
  • 后面的树就能越来越专注那些前面被分错的instance。
• 就像做互联网，先解决60%用户的需求凑合，
  • 再解决35%用户需求，
  • 最后才关注那5%人的需求，就能逐渐把产品做好，
  • 因为不同类型用户需求可能完全不同，需分别独立分析。
• 如刚上来就一定要做到尽善尽美，往往最终会竹篮打水

 

caokan

• 添加链接描述

GBDT

1.简介

• 梯度下降树
• 传统机器学习算法里对真实分布拟合的最好的算法之一，
• 深度学习还没有大行其道之前，gbdt在各种竞赛大放异彩。
• 效果确实不错。
• 用于分类也可以用于回归。
• 可以筛选特征。
• gbdt的面试考核点，大致有下面几个:

 

• gbdt 算法流程？
  • 如何选择特征
  • gbdt 如何构建特征
  • 如何用于分类
  • 通过什么方式减少误差
  • 效果相比于传统的LR，SVM效果为什么好些
  • 如何加速训练？
  • 参数有哪些，如何调参
  • 实战当中遇到的一些问题 ？
  • 的优缺点 ？

2 正式介绍

• gbdt 用加法模型（即基函数的线性组合）
  • 不断减小训练过程产生的残差来达到将数据分类或者回归
• 一张图片，
  • 说明gbdt的训练过程

 

• gbdt多轮迭代,每轮迭代产生一个弱分类器，
• 每个分类器在上一轮分类器的残差基础上训练。
• 弱分类器要求足够简单，低方差和高偏差。
• 训练的过程是通过降低偏差来不断提高最终分类器的精度，
• （此处可证明的）

 

• 弱分类器一般选CART TREE（分类回归树）。
• 高偏差和简单的要求 每个分类回归树深度不很深。
• 最终的总分类器将每轮训练得到的弱分类器加权求和（也就是加法模型）。

 

• 模型最终描述为：

caokan

• 添加链接描述