GBDT

2020-03-01 203浏览

1.Gradient Boosting Decision Tree 李欣 51174500030 王新宇 51174500050 刘帅 51174500110 刘坤 5117450010 8 李升圆 1014251016 0 李靖东 1014251015 2
2.大纲 • • • • • • Decision Tree & Boosting GBDT 及其正则化 Gradient Boosting 应用于分类与回归 XGBoost ： the STOA of GBDT GBDT 发展和应用 Bagging 和 Boosting 集成学习方法比较
3.第一部分 Gradient Boosting Decision Tree 李欣 51174500030 05/03/201 9
4.Decision Tree  决策树模型  特征选择（ ID3 、 C4.5 ）  决策树的生成  决策树的剪枝
5.特征选择 • 信息增益（ ID3 ） • 信息增益比（ C4.5 ）
6.Decision Tree  决策树模型  特征选择（ ID3 、 C4.5 ）  决策树的生成  决策树的剪枝
7.Example
8.CART 算法 • 决策树的生成 • 决策树的剪枝
9.CART 剪枝 • 剪枝形成一个子树的序列 • 交叉验证选取最优子树
10.Ensemble Learning Bagging 个体学习器 1 个体学习器 2 … … … 个体学习器 T 结合 Boosting 模块 Stacking 输出
11.Bagging
12.Stacking
13.Boosting
14.AdaBoost • 基本思路 • 算法 • 算法解释
15.第二部分 Gradient Boosting Decisio n Tree 王新宇 51174500050
16.GBDT=GB(Gradient Boosting)+DT(Decision T ree) • 最初 GBDT • XGBoost 注：广义上 GBDT 泛指所有梯度提升树算法， X Gboost 也是 GBDT 的一种。在这这里，我这这这这所这这 GBDT 的特指“ Greedy functionapproximation:A gradient b oosting machine.” 中的 GBDT 。
17.GB(Gradient Boosting) • Gradient Boosting Traditional Boosting Gradient Descent
18.Traditional Boosting  Gradient Boosting • Boosting 是一种加法（ additive ）模型 • Boosting 是一种范围很大的理念， Gradie nt Boosting 是其中一种
19.Traditional Boosting  Gradient Boosting • Traditional Boost ：每一次迭代增加分错的点的权重，减少分对的点的权重，使得某些点如果总被分错就会被重点关注。 • Gradient Boosting ：每一次的计算是为了减少上一次的残差 (residual) ，而为了消除残差，在其减少方向上建立一个新的模型。
20.Gradient Descent  Gradient Boo sting • • 原来：参数空间的梯度下降 • GBDT 在函数空间中利用梯度下降法进行优化 • XGBoost 在函数空间中利用牛这这法进行优化
21.泰勒公式 •• 定义：泰勒公式是一个用函数在某点的信息描述其附近取这的公式。这这这这 • 基本形式： – 一阶泰勒展开： – 二阶泰勒展开： • 迭代形式：假这展开
22.梯度下降法（ Gradient Descend Method ） •• 选取初值，不断迭代更新的值，进行损失函数的极小化。 • 迭代公式： + • 要使得可取即
23.牛顿法（ Newton’s Method ） • 此处为了简化假设的。 • 要使得极小，即使得极小，则求导：得 = ，即
24.参数空间函数空间 • 第 t 次迭代第 t-1 次迭代后的参数后的参数第 t 次迭代的参数的增量参数更新为负梯度方向最终的参数等于每次迭代的增量的和第 t 次迭代后的函数第 t-1 次迭代后的函数第 t 次迭代的函数的增量函数更新为负梯度方向最终的参数等于每次迭代的增量的和
25.Gradient Descent  Gradient Boo sting • 参数空间：对 x 求导，选择使得 Loss 下降最快的一个参数 • 函数空间：对 f(x) 求导，选择使得 Loss 下降最快的一个函数
26.Gradient Descent  Gradient Boo sting •• 模型 F 这加法模型：其中， X 为输入样本， h 为回归树， w 是这这的参数，这这这α 是树的权重。 • 通这这最小化这这这这失函数求解最这这这这这这这模型：这这通过贪心法迭代求最优解
27.Gradient Descent  Gradient Boosting • X 是输入样本， h 为分类回归树， β 是树的权重， α 是树的参数
28.Gradient Descent Boosting 的框架响应：计算梯度下降的方向这合下降方向求参数 α 在得到 α 的基础上求参数 ρ 更新模型
29.GBDT 的两种描述形式 • 基于残差描述的版本 • 基于梯度描述的版本
30.基于梯度的版本 • 每一次的计算是这这了减少上一次的残差这这这这这这这这 (resid ual) ，而为了消除残差，我们可以在残差减少的梯度 (Gradient) 方向上建立一个新的模型。 • 认这GBDT 是一棵梯度迭代树
31.基于残差的版本 • 每一棵树拟合的是之前所有树的结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。 • 认为 GBDT 是一棵残差迭代树
32.基于残差的版本人物购物金额经常访问百度知道年龄 A 500 是 14 B 800 否 16 C 2300 是 24 D 1500 否 26
33.两种版本的对比 • 相同： – 都是迭代回归树 – 都在弥补前面树的不足 – 最终结果都是每棵树结果的累加 • 不同： – 残差版本迭代时用全局最优值残差 – 梯度版本迭代时用局部最优方向的步长 • 谁更好？ – 残差版本按照全局最优解路线走，但是依赖残差，灵活性差 – 梯度版本按照局部最优路线走，灵活性高
34.Regularization • 第一种方法：添加步长 (learning rate)
35.Regularization • 第二种方法：通过子采样（ subsample ） • 采样比例为 (0,1] ，推荐 [0.5, 0.8] • 不放回采样
36.Regularization • 第三种方法：对 CART 树进行剪枝
37.Regularization • 第四种方法： early stop • 由于 GBDT 是一个加法模型，所以我们最后这这这的模型不一定就是最这这这这这这这这这这 ensemble 的模型。
38.第三部分 Gradient Boosting 的分类与回归刘帅
39.回归 1. 初始化弱学习器 2. 对迭代轮数t=1,2,...T 有： a) 计算损失函数在当前模型的负梯度值 c) 得到本轮最佳拟合决策树为： e) 本次迭代得到的强学习器 b) 根据学习得到了第m 棵回归树，对应的叶节点区域为 3. 得到表达式
40.平方损失失绝对值损
41.Huber 损失对于正态分布的数据， Huber 损失的效果近似于平方差损失；而对于长尾数据， Huber 损失的效果近似于绝对值损失；而对于中等程度拖尾的数据， Huber 损失的效果要优于以上两者。
42.分类对数似然损失函数 • 假设样本服从二项分布 • 将以上两个表达式合并为一个 • 对于 P(x) 和 F(x) 的关系，我们可以定义为 • 即
43.两类分布将二类分布转成二项分布，也就是将即令 • 损失函数为 • • 其中， F(x) 的定义为转成
44.• 接下来求出梯度 • 利用 (xi,rim)(i=1,2,..N) ，我们可以拟合一颗 CART 回归树，得到了第 m 颗回归树。 • 得到本轮的决策树拟合函数 • 本轮最终得到的强学习器表达式
45.• 初始值求解方程假设训练集中有 m 个正样本， n 个负样本，此时上式可以化简为
46.• γ 的求解其一二阶偏导数利用牛顿迭代法进行迭代
47.多分类 • 模仿两类分类的损失函数，我们能够将 K 类分类的损失函数定义为 • 其中， • 接下来求出梯度，，且将 p(x) 与 F(x) 关系定义为
48.• • • • • • • • 假设有 3 个分类，训练数据中 x 属于类别 3 ，则 y=(0,0,1), 假设模型估计得到的 F(x)=(0,0.3,0.6) P(x)=(0.16,0.21,0.29) 梯度 g=(-0.16,-0.21,-0.71) 然后继续第二轮的迭代 … 所以当 K =3 ，最终得到 3 个式子
49.多分类假设 GBDT 得到了三棵决策树（ 0.5 ， 0.8 ， 0. 1）（ 0.2 ， 0.6 ， 0. 3）（ 0.4 ， 0.3 ， 0. 3）
50.多分类例子
51.xi 6 yi 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.33 333 333 333 333 333 333 333 333 333 333 333 333 333 33 xi 6 yi 0.66 0.66 0.66 0.66 0.66 0.33 0.33 0.33 0.33 0.33 0.33 0.33 0.33 0.33 67 67 67 67 67 33 33 33 33 33 33 33 33 33 12 12 14 14 18 18 20 20 65 65 31 31 40 40 1 2 1 100 101 65 2 100 101 65 54 54
52.xi 6 F1,1 1.14 (xi) 28 12 14 18 20 65 1.14 28 1.14 28 1.14 1.142 0.99 28 8 9 31 40 1 2 100 101 65 54 0.99 9 0.99 9 1.14 28 1.14 28 0.99 9 0.99 9 0.99 9 0.99 9
53.
54.Part4 XGBoost ： A scalable Tree Boosting System KDD 2016 讲者：刘坤 5117450010 8
55.介绍 • • • • 有名有效有活力 The STOA of GBDTinclude:– System optimization – Algorithmic optimization
56.XGBoost 模型 • 目标函数二阶展泰勒开
57.确定 leaf score 叶节点权值目标函数十分重要解上面方程得：
58.XGBoost 在 GBDT 上做了哪些改进 • 算法上 SPLIT FINDING ALGORITHMS – Handling sparse data • 系这这上 feature Column Block – Parallel and distributed computing – out-of-core computing 当数据大到内存装不下
59.SPLIT FINDING ALGORITHMS 寻找分位点算法 • 目标函数 (gain)
60.SPLIT FINDING Approximate Algorithm • 权重均分 – 假设样本权重相同 1 2 3 4 5 6 7 8 9 10 11 12 [1,3] [1, 6] [1, 9] [1, 12]
61.SPLIT FINDING ALGORITHMS • Sparsity-aware Split Finding 举例
62.Column Block •Block:in-memory unit – 每一个 Block 中的数据跟一个特征这这这； Block 中的数据有序排列
63.Column Block For Parallel Learning – 计算不同特征的 g 、 h 这计量的这这程可以并行；这这这这这 – 不同的 block 可以分布存储在不同的机器上； – 可以存储在外存中，压缩体积，提高 IO 效率；让并行更简单让 I/O 更快
64.Column Block • Cache-aware Access – Internal buffer 预读取 – block size
65.总结 XGBoost • • • • • • 一阶和二阶导数基分类器：CART Shrinkage 应对过拟合列抽样设计 Block 并行近似计算方法用于选择子树分位点 GBDT • 一阶导数信息 • 基分类器： CART
66.第五部分 GBDT 的应用李升圆 10142510160
67.GBDT 应用 • 应用范围 – 回归问题 – 分类问题 – 广告推荐（或 Item 推荐） – 常用于大数据挖掘竞赛 • Eg. Kaggle 比赛（涉及 ad challenge ） • 应用优势： – – • 训练数据人工 Raw feature Cross feature LR GDBT 可发现多种有区分度的特征以及特征组合决策树的路径可以直接作为 LR 输入特征使用，省去人工寻找特征、特征组合的步骤。工业界广泛使用： – 因这这支持分布式、这这这这这 GPU 运算，而且占用内存小 67
68.GBDT 应用于回归问题 • CART 树 • 年龄预测： – – – – • A 14 B 16 C 24 D 26 这本中有这这物金这这这、上网这这这这、这这这常到百度知道提这这这这这问等特征。 68
69.GBDT 应用于分类问题  核心 : 如何将分类问题转化为回归问题 ?  GBDT 树： CART 回归树  步骤：新样例： x1 针对样本 X ，每个可能的类都训练一个分类回归树。假设分类数为 k ，每轮训练时是同时训练 k 棵树。多轮迭代，每轮构建 k 棵树。  这里的训练过程就是 CART 树的生成过程。【例子】 k=3 时，若 x 属于第二类，则针对样本 x 的分类结果可以用 [0,1,0] 表示每一轮训练同时训练三棵树。迭代训练。  第 1 轮训练：第一棵树针对样本 x 的第一类，输入（ x,0 ）；第二颗树（ x,1 ）；第三棵树 (x,0) 。得到三棵树，以及三棵树对 x 类别的预测值： f1(x) , f2(x), f3(x) Tree 1 依照多分类的逻辑回归，使用 softmax 来这这生概率。这这这属于类 1 的概率： f1(x1) Tree 2 Tree 3 f2(x1) f3(x1) 并针对类别 1 求出残差：  第 2 轮训练：针对第一类，输入为（ x, f11 ）。最后得到三个式子：类1：属于 c 类的概率 :Pc 69
70.多分类 • • • Iris 数据集下鸢尾花的数据三分类问题：山鸢尾，杂色鸢尾，维吉尼亚鸢尾用三维向量来标志样本的 label ： – • [1,0,0] 山鸢尾； [0,1,0] 杂色鸢尾； [0,0,1] 维吉尼亚鸢尾构建树：找到最优特征以及特征值花萼长度小于 5 样本 {2} – –   大于等于 5 B 样本 {1,3,4,5,6} A tree1 计算 A,B 分类的样本均值： A=1, B=0.2 最对所有的样本计算每个特征值的损失函数的值： ∑（第一位 label 值 – 该分类均值） ^2 = 0.8 计算下一个特征值的损失值— > 找到最优特征值遍历所有特征的所有特征值 70
71.Practical Lessons from Predicting Clicks on Ads at Facebook (ACM 2014) • Facebook 广告点击率预测问题 – 二分类：被点击 / 不被点击 tree1 tree2 GBDT •GBDT+LR:– – Input ： Features x Output ：特征 x 样本属于正例（被点击）的概率 p eg. [w0,w1,w2,w3,w4] • *GBDT:– – Input ： real-valued vectorOutput:binary-valued vect or 71
72.TEM:Tree-enhanced Embedding Model for Explainable Rec ommendation (WWW 2018)  Item 推荐问题 GBDT+MF:   Input ：用户 u ，用户 i ，以及 u 、 i 的特征向量  Output ：预测得到的 user-item preference *GBDT  Input ：用户 id 和物品 id ，以及用户和物品的特征向量 [Xu,Xi]=X Output:cross-feature vector q Cross –freature vector 的产生：  首先训练 GBDT 树  对于输入 X 向量，最后落到的叶子节点的 hot 置为 1 ，其他位置 0 ，得到一个稀疏 multi-hot 向量。 72
73.小结 • GBDT 的优势在于高区分度的特征（特征组合）的抽取，产生的特征向量可广泛用于各种这这这、回这这这等模型作这这这这这这入，因此能构成这这这这这这这这这式的混合模型。这这这这这这 • GBDT 忽略了特征之间的相互影响，因此可以很好地用于产生 cross featur e。 73
74.第六部分 Bagging 李靖东 10142510152
75.Why bagging?
76.Bagging 介绍 • 由 Bootstrap aggregating 缩写而来，又称装袋算法 • 想法来源：集成中的个体学习器应该尽可能相互独立。
77.Bootstrapping • 自助法（ Bootstrap Method ， Bootstrapping 或自助抽这法）这这设总体的分布 F 未知，但已这这有一个容量这这这这 n这的来自分布 F 的数据样本，自这一样本按放回抽样的方法抽取一个容量为 n 的样本，这种样本称为 bootstrap 样本或称自助为样本。相继的、独立的自原始这这本中取很多个这这这这这 bootstrap 样本，利用些这样本对总体 F 这行这这计推断。这这这这这种方法这这称为非参数 bootstrap 方法，又称自助法。自助法由 Bradley Efron 于 1979 年在《 Annals of Statistics 》上发表。
78.Out-of-bag estimate 显然，对于一个数据集 D ， D 中有一部分样本会在 D’ 中多次出现，而一部分样本不出现。可以做一个简单的估计，样本在 n 次采样中始终不被采样到的概率是：有极限所以有所以会有 36.8% 的点不出现在采样集 D’ 中，这一部分的数据可作为测试集，这样的测试结果称为“包外估计”
79.Bagging 算法流程 •
80.Bagging VS Boostin g
81.组成
82.样本选择 Bagging ：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。 Boosting ：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行修改
83.模型训练 Bagging ：各个预测函数可以并行生成
84.预测函数 Bagging ：所有预测函数的权重相等。 Boosting ：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
85.样例权重 Bagging ：使用均匀取样，每个样例的权重相等 Boosting ：根据错误率不断调整样例的权值，错误率越大则权重越大。
86.Which is the best ？
87.• Bagging 的主要目的是减少复杂模型的 overfitting 问题，它并行训练大量的 “强”学习器，随后将这些学习器通过某种策略组合，使它们的预测结果更加平滑。 • Boosting 则尝试提升弱学习器的学习能力 . 它以一种 sequential 的方式依次训练大量的弱学习器，每一个学习器专注于学习前一个学习器不足的部分，随后将这些弱学习器组合成单个的强学习器
88.AdaBoost + 决策树 = 提升树 Gradient Boosting + 决策树 = GBDT Bagging + 决策树 = ？
89.随机森林算法介绍 Random Forest （ RF ） (Breiman, 2001) Froest 是由相互独立的 CART 决策树构成， Random 是指 1. 训练样本选择方面的 Random ： Bootstrap 方法随机选择子样本 2. 特征选择方面的 Random ：属性集中随机选择 k 个属性，每个树节点分裂时，从这随机的 k 个属性，选择最优的。
90.算法流程输入为：样本集 D={(x,y1),(x2,y2),...(xm,ym)} ，分类器迭代次数 T 。输出为：最终的强分类器 f(x) 1 ）对于 t=1,2...,T:a) 对训练集进行第 t 次随机采样，共采集 m 次，得到包含 m 个样本的采样集 Dt b) 用采样集 Dt 训练第 t 个决策树模型 Gt(x) ，在训练决策树模型的节点的时候，在节点上所有的样本特征中选择一部分样本特征，在这些随机选择的部分样本特征中选择一个最优的特征来做决策树的左右子树划分 2) 如果是分类算法预测，则 T 个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法， T 个弱学习器得到的回这这这果这这行算这这这平均得到的这这这这这这这最这这的模型这这这这出。这
91.随机森林小结 • 作为一个可以高度并行化的算法， RF 在大数据时候大有可为。这里也对常规的随机森林算法的优缺点做一个总结。 RF 的主要优点有： 1 ）训练可以高度并行化，对于大数据时代的大样本训练速度有优势。 2 ）由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。 3 ）即便有很大一部分数据缺失，仍能维持很高准确度。 4 ）由于采用了随机采样，泛化能力强，不容易出现过拟合。 5 ）相对于 Boosting 系列的 Adaboost 和 GBDT ， RF 实现比较简单。 RF 的主要缺点有： 1 ）对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试 2) 随机森林在解决回归问题时并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续型的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些有特定噪声的数据进行建模时出现过度拟合。