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

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

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

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

在GBDT的原理之后，拓展GBDT相关的细节，包括和Adaboost的异同，以及GBDT基础上优化的XGB和LightGBM

Adaboost简述

Adaboost与GBDT一样，同样是加法模型，同样需要解决的两个问题，权重 $\alpha_i$ 和第 m 轮迭代基函数 $f_i(x)$ ,与GBDT不同的是，Adaboost并没有规定基函数的类型。
Adaboost的提升思路是，改变数据分布，然后训练的模型会强化上一次错误的样本，而GBDT是改变拟合目标
Adaboost中最核心的是样本权重，每一次迭代中，都会更新 $w_i$ ，然后在计算误差时，采用加权误差，侧面改变数据分布

回归问题
1. 初始化样本权重向量 $w, w_i = \frac{1}{N}$
2. 基于当前数据集D $(x_i,y_i)$ ，训练基模型 $f_i(x)$
3. 计算最大误差 $E_{max} = max(|y_i - f_i(x)|)$ ，即所有样本中最大的误差
4. 对于所有样本，根据最大误差，调整相对误差
  线性误差： $e_i = \frac{|y_i - f_i(x)|}{E_{max}}$
  平方差误差： $e_i = \frac{|y_i - f_i(x)|^2}{E_{max}^2}$
  指数误差： $e_i = 1 - exp(\frac{-|y_i - f_i(x)|}{E_{max}})$ ..感觉这个在回归没啥用
5. 通过所有样本的权重和相对误差，计算当前迭代的模型的误差
  $\epsilon_t = \sum(w_i * e_i)$
6. 通过上面的加权误差，计算当前模型权重
  $\alpha_i = \frac{\epsilon_t}{1-\epsilon_t}$
7. 到这里当次迭代已经基本完成，根据当前结果，更新样本权重，Z为权重和，用来归一
  $w_{t+1},_i = \frac{w_t,_i*\alpha_i^{1-e_i}}{Z}$
分类问题
与GBDT不同，对于Adaboost来说，分类是更natural的事情。一个重要是的事情，在基分类和整个模型中，输出只是单纯的类目，即-1或1。在分类算法中，损失函数采用了指数损失函数，即

但是为啥是这个，似乎没有理论支持，其实这个只有符号不同( y==H(x)->1/ y!=H(x)->-1)
1. 同回归，初始化样本权重 $w_i$
2. 基于数据集，训练基模型 $f_t(x)$
3. 对于 $f_t(x)$ 的结果，计算当前迭代的加权错误率 $\epsilon_t = \sum w_{t-1},_i * I(f_t(x_i) \neq y_i)$
4. 基于错误率（准确率高于50%），计算当前模型的权重
  $\alpha_t = \frac{1}{2}*ln\frac{1-\epsilon_t}{\epsilon_t}$
  由于损失函数是 $exp(-y*H(x))$ ，所以可以推到在第 t 轮迭代时，损失为
  $E = \sum exp(-y*H_t(x)) = \sum exp(-y*H_{t-1}(x))*exp(-y*\alpha_t*f_t(x))$
  上式显然是一个累乘式子，从0～t-1~t，令样本呢权重 $w_i^1 = 1,w_i^t = exp(-y*H_{t-1}(x))$
  $E = \sum w_i^t*exp(-y_i*\alpha_t*f_t(x_i))$
  整体数据中，两种情况，预测正确 $y_i*f_t$ =1 或者预测错误 $y_i*f_t$ =-1
  $E = \sum_{y==f_t}w_i^t*exp(-\alpha_t) + \sum_{y!=f_t}w_i^t*exp(\alpha_t)$
5. 基于权重，更新样本权重向量，由于上式中，唯一可变的就是权重 $\alpha_t$ ，对上式求偏导，置零并求解( $exp(\alpha_t)$ 是常数值，可以直接提取出累加)
  $\frac{\partial E}{\partial \alpha_t} = -\sum_{y==f_t}w_i^t*exp(-\alpha_t) + \sum_{y!=f_t}w_i^t*exp(\alpha_t)$
  $\alpha_t*\sum_{y_i==f_t(x_i)} ln(w_t) = -\alpha_t*\sum_{y_i!=f_t(x_i)} ln(w_t)$
  $\alpha_t = \frac{1}{2} * ln(\frac{\sum_{y_i==f_t(x_i)}w_t}{\sum_{y_i!=f_t(x_i)}w_t})$
  即上面的替换成了加权误差的公式
6. 更新权重，上面已经写了 $w_i^t = exp(-y*H_{t-1}(x))$ ，所以，新一轮的权重为
  $w_i^t = \frac{w_i^{t-1}*(-y_i*\alpha_t*f_i(x_i))}{Z} \quad Z为归一值$

GBDT的优化

XGboost
在GBDT中，基函数就是CART，节点的分裂方式是完全按照最小二乘法去筛选的，但是在XGBoost中，引入了全新的目标函数和节点分裂方式，在分裂时就考虑结构化损失，同时梯度采用了二阶导。
$Obj = \sum_NL(y_i,F(x_i)) + \sum_K\Theta(f_i)$
在第k轮迭代的时候，不再单纯的用CART去拟合损失函数的一阶导，而是在结构和值上面，整体考虑Obj函数 $g_t$ 为一阶， $h_t$ 为二阶，这个在求的时候是固定值，因为样本固定，损失函数固定
$\sum[ g_t,_i*f_t(x_i) +\frac{1}{2}*h_t,_if_t^2(x_i)] + \Theta(f_i)$
在GBDT中，一般很难实现并发，因为需要依赖上一轮的残差，所以基本上都只能串行，然后其实XGBoost也是串行建树的，只是在生成单棵树里面，实现了并行。

更多的后续再研究

参考

https://en.wikipedia.org/wiki/AdaBoost
https://blog.csdn.net/pxhdky/article/details/84857366
http://zhanpengfang.github.io/418home.html

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