传统机器学习笔记 - GBDT（一）

作者: 纸上谈兵何某某 | 来源:发表于2019-08-14 16:49 被阅读0次

传统机器学习笔记 - GBDT（一）
传统机器学习笔记 - GBDT（二）
决策树在机器学习的理论学习与实践
决策树在机器学习的理论学习与实践
GBDT，XGBOOST
《机器学习技法》学习笔记11——GBDT
03-GBDT
集成学习之Boosting-gbdt
机器学习之-GBDT
机器学习算法：GBDT

学习GBDT的原理和细节（一）

在面试中，经常会出现GBDT以及相关算法的细节问题，所以这里做一下详细的学习记录

CART树的生成

在GBDT中，所有的树都是CART的回归树，回归树的目标是连续值，采用平方差判定。每次遍历所有的特征以及该特征的所有取值，对于可能的分割，计算 $\sum(y_i - c_1)^2+ \sum(y_j - c_2)^2$ c1,c2为分裂后节点内样本的平均值

GBDT概述

GBDT 梯度提升树，Gradien Boost Decision Tree，属于Boosting中的加法模型，与Adaboost为两个十分常用的Boosting模型，后续比较二者异同。
基于GBDT的思路，引申出的实现和优化包括了XGB，LightGBM。后续会针对他们进行学习

无论回归问题或者分类问题，每一棵树都是CART回归树
加法模型： $f(x) = \sum\alpha_i*B_i(x)$
可以看出，在第 i 次迭代时，需要求两个内容，系数 $\alpha$ 和基函数 B
整体模型目标最小化损失函数，通过逐步迭代向前，达到损失函数的最小值

GBDT_basic.png

方差损失函数 - 回归问题

$F(x) = \sum^M_i(f_i(x))$
$LL = \frac{1}{2}(y - F(x))^2$
对于回归问题，常用的损失函数就是平方差损失函数，针对这个损失函数和回归问题，可以替换进入上述流程。

初始化：照旧对原数据集T $(x_i,y_i)$ 训练第一棵CART树。回归树的的生成，是把同一个叶子节点的x，都会输出同一个值c，这个 $c_j$ 使得当前LL最小。
迭代 m:
1. 更新所有样本的目标值，不再拟合原y，而是拟合损失函数梯度，在GBDT中，仅拟合了一阶偏导。在上述平方差损失函数LL中， $r_i = y-F_{m-1}(x_i)$ 即简单的残差
2. 对于 $(x_i,r_i)$ 构建回归树，得到所有叶子节点，然后需要决定叶子节点的输出值c，使得LL最小
  ！！需要思考单棵回归树的生成，再结合当前的公式，解答具体这个c的取值（目前损失函数应该就是节点内样本 $r_i$ 的加权平均）
最后对于预测样本，就是结合c和叶子节点（树的作用）的加法结果的输出

作为串行的多棵树，来解决回归问题，树的本质是将样本空间划分不同的区域，然而树本身并不产生值，所以每一棵树只有在叶子节点的时候，才会平均出一个预测值，通过这个预测值，加上不同迭代过程划分的区域不同，逐步使预测分布的均值走向训练样本的分布的均值。

对数损失函数 - 分类问题

$LL = log(1 + exp(-y*F(x)))$
这个损失函数直观与Logistic Regression的有区别，在逻辑回归中，损失函数的表达最大化似然估计，即最大化函数 -> 最小化负的似然函数
$max( P(h(x)=y | x)) -> min( -P(h(x)=y | x)) -> min( -log(P(h(x)=y|x)))$
在整体的公式里面中，正负号太tricky，base的函数是 $h(f(x)) = \frac{1}{1+exp(-f(x))}$ 这个输出的是对应label为1的
$P(h(x)=y | x) = { h(x) = \frac{1}{1+exp(-f(x))} \quad y=1 \atop 1-h(x) =\frac{exp(-f(x))}{1+exp(-f(x))} = \frac{1}{1+exp(f(x))} \ \ y=0 }$
$LL=-log(P(h(x)=y|x))=log(1+exp(-y*f(x)))$
推导发现，跟最上面的是完全一样的，那可以开始训练全部GBDT的流程

初始化：可以把Label看作数值，同样可以应用回归树的训练，最小化树里面的平方差，然后得到叶子节点的输出值
迭代 m:
1. 同样开始拟合残差，这里的残差作为当前对数损失函数的偏导
  $-\frac{\partial log(1+exp(-y*F_{i-1}(x)))}{\partial F_{i-1}(x)} = -\frac{1}{1+exp(-y*F_{i-1}(x))}*exp(-y*F_{i-1}(x))*-y$
  $= \frac{y}{1+exp(y*F_{i-1}(x))}$
  新的树的拟合目标就是这个值
2. 新数据为 $(x_i,r_i)$ ，得到新树之后，就开始需要对叶子节点进行赋值，由于直接对 $c_j$ 求使 $log(1 + exp(-y*(F_{i-1}(x) + c_j)))$ 最小的这个值太难，所以 $c_j$ 求近似值，对于 j 叶子节点内 $x_k$ , $c_j = \frac{\sum(r_k)}{\sum(|r_k|(1-r_k))}$
3. 得到新一棵的叶子节点输出之后，就可以加入F(x),开始对样本进行更新

参考

https://www.cnblogs.com/pinard/p/6140514.html
http://www.csuldw.com/2016/03/26/2016-03-26-loss-function/
https://www.zybuluo.com/Dounm/note/1031900
https://www.jianshu.com/p/7219454f806c

传统机器学习笔记 - GBDT（一）
学习GBDT的原理和细节（一）在面试中，经常会出现GBDT以及相关算法的细节问题，所以这里做一下详细的学习记录 ...
传统机器学习笔记 - GBDT（二）
学习GBDT的原理和细节（二）在GBDT的原理之后，拓展GBDT相关的细节，包括和Adaboost的异同，以及G...
决策树在机器学习的理论学习与实践
决策树，是一种传统机器学习算法，也是机器学习的入门算法之一。在它的基础上，衍生了随机森林、GBDT、XGBOOST...
决策树在机器学习的理论学习与实践
决策树，是一种传统机器学习算法，也是机器学习的入门算法之一。在它的基础上，衍生了随机森林、GBDT、XGBOOST...
GBDT，XGBOOST
1.简介 gbdt全称梯度下降树，在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一，在前几年深度学习还没...
《机器学习技法》学习笔记11——GBDT
http://blog.csdn.net/u011239443/article/details/77435463 ...
03-GBDT
1. GBDT概述 GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回...
集成学习之Boosting-gbdt
一、什么是GBDT 二、GBDT与传统Adaboost的不同之处三、GBDT的负梯度拟合四、GBDT算法流程 ...
机器学习之-GBDT
机器学习算法：GBDT
1. Adaboost 的全局过程 2.AdaBoost 和GradientBoost 的公式 3.GBDT 算法...