集成学习 Boosting

image.png

Boosting

每次使用的是全部的样本，每轮训练改变样本的权重。下一轮训练的目标是找到一个函数f 来拟合上一轮的残差。当残差足够小或者达到设置的最大迭代次数则停止。Boosting会减小在上一轮训练正确的样本的权重，增大错误样本的权重。（对的残差小，错的残差大）

它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

1.代表自适应增强
2.每个预测变量都更加注意其前任错误预测的实例
3.通过更改训练实例的权重来实现
4.为每个预测变量分配一个系数\scriptstyle \alpha，以加权其在整体最终预测中的贡献
5.\scriptstyle\alpha取决于预测变量的训练错误

过程图

首先，在初始数据集（X，y）上对预测变量1进行训练，并确定预测变量1的训练误差。然后，可以使用此错误来确定\scriptstyle\alpha_1，它是预报变量1的系数。然后，使用\scriptstyle\alpha_1来确定预测变量2的训练实例的权重\scriptstyle w ^ {（2）}。

\scriptstyle\eta是介于0和1之间的数字；它用于缩小训练集的预测变量的系数\scriptstyle\alpha。重要的是要注意，在\scriptstyle\eta和估计量之间要进行权衡。\scriptstyle\eta的较小值应由大量估计量补偿。

注意绿色中显示的错误预测实例如何获得更高的权重。当加权实例用于训练预测变量2时，该预测变量被迫更加注意错误预测的实例。依次重复此过程，直到训练形成集合的N个预测变量为止。

AdaBoost:Prediction

分类

1.加权多数投票
2.In sklearn: AdaBoostClassifier

回归

1.加权平均
2.In sklearn: AdaBoostRegressor

重要的是要注意，各个预测变量不必是CARTs。但是，由于CARTs variance很大，因此大多数时候都在使用CART进行增强。

代码示例：

# Import models and utility functions
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split

# Set seed for reproducibility
SEED = 1

# Split dataset into 70% train and 30% test
X_train, X_test, y_train, y_test = train_test_split(X, y, stratify=y,
                                                    test_size=0.3,
                                                    random_state=SEED)
# Instantiate a classification-tree 'dt'
dt = DecisionTreeClassifier(max_depth=1, random_state=SEED)

# Instantiate a AdaBoost classifier 'adb_clf'
adb_clf = AdaBoostClassifier(base_estimator=dt, n_estimators=100)

# Fit 'adb_clf' to the training set
adb_clf.fit(X_train, y_train)

# Predict the test set probabilities positive class
y_pred_proba = adb_clf.predict_proba(X_test)[:, 1]

# Evaluate test set roc-auc score
adb_clf_roc_auc_score = roc_auc_score(y_test, y_pred_proba)

# Print adb_clf_roc_auc_score
print('ROC AUC score: {:.2f}'.format(adb_clf_roc_auc_score))

result

ROC AUC score: 0.99

Gradient Boosting (GB)

1.顺序纠正前任的错误。
2.不调整训练实例的权重。
3.使用每个预测变量的前任残差作为标签来训练每个预测变量的拟合度。

过程图

image.png

N棵树组成

使用特征矩阵X和数据集标签y训练树1。标记为\scriptstyle\hat y的预测用于确定训练集残差\scriptstyle r_1。

然后使用特征矩阵X和树1的残差\scriptstyle r_1作为标签来训练树2。然后使用预测的残差\scriptstyle\hat r_1确定标记为\scriptstyle r_2的残差的残差。

重复此过程，直到形成集合的所有N棵树都经过训练为止。用于训练梯度增强树的一个重要参数是shrinkge。

在这种情况下，收缩指的是对系综中每棵树的预测值乘以学习率\scriptstyle\eta（即介于0到1之间的数字）后，其集合就会收缩。在\scriptstyle\eta和估计量之间。为了使整体达到一定的性能，需要通过增加估计量的数量来补偿学习率的下降。

GB:Prediction

回归

In sklearn: GradientBoostingRegressor
分类
In sklearn: GradientBoostingClassifier

代码示例：

# Import models and utility functions
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error as MSE

# Set seed for reproducibility
SEED = 1

# Split dataset into 70% train and 30% test
X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    test_size=0.3,
                                                    random_state=SEED)
# Instantiate a GradientBoostingRegressor 'gbt'
gbt = GradientBoostingRegressor(n_estimators=300, max_depth=1, random_state=SEED)

# Fit 'gbt' to the training set
gbt.fit(X_train, y_train)

# Predict the test set labels
y_pred = gbt.predict(X_test)

# Evaluate the test set RMSE
rmse_test = MSE(y_test, y_pred) ** (1/2)

# pirnt the test set RMSE
print('Test set RMSE: {:.2f}'.format(rmse_test))

Test set RMSE: 4.01

GBDT

Gradient Boosted Decision Trees
与AdaBoost不同，GBDT每一次的计算是都为了减少上一次的残差，进而在残差减少（负梯度）的方向上建立一个新的模型。
GBDT是以决策树（CART）为基学习器的GB算法

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

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

XGBoost（eXtreme Gradient Boosting）

xgboost扩展和改进了GDBT，xgboost算法更快，准确率也相对高一些。
Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）

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

第t次的loss：
\begin{array}{l} \mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(t-1)}\right)+g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right) \\ \text { where } g_{i}=\partial_{\hat{y}(t-1)} l\left(y_{i}, \hat{y}^{(t-1)}\right) \text { and } h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right) \end{array}
\mathcal{L}_{s p l i t}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma

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

LightGBM

简单理解：增添了GOSS算法和EFB算法的GBDT称为LightGBM

GOSS（Gradient-based One-Side Sampling）

GOSS是通过区分不同梯度的实例，保留较大梯度实例同时对较小梯度随机采样的方式减少计算量，从而达到提升效率的目的。

原因：
因为在提升树训练过程中目标函数学习的就是负梯度（近似残差），梯度小说明训练误差已经很小了，对这部分数据的进一步学习的效果不如对梯度大的样本进行学习的效果好或者说对梯度小的样本进行进一步学习对改善结果精度帮助其实并不大。

EFB（Exclusive Feature Bundling）-独立特征合并

EFB是通过特征捆绑的方式减少特征维度（其实是降维技术）的方式来提升计算效率。

通常被捆绑的特征都是互斥的（一个特征值为零一个特征值不为零），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。

Leaf-wise的决策树生长策略

大部分决策树的学习算法通过 level-wise 策略生长树，记一次分裂同一层的叶子，不加区分的对待同一层的叶子，而实际上很多叶子的分裂增益较低没必要进行分裂，带来了没必要的开销。如下图：

image.png

LightGBM通过 leaf-wise 策略来生长树。每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。但是，当样本量较小的时候，leaf-wise 可能会造成过拟合。 所以，LightGBM 可以利用额外的参数 max_depth 来限制树的深度并避免过拟合。

image.png

补充：

image.png

一，LightGBM和XGBoost对比

LightGBM可以看成是XGBoost的升级加强版本，2017年经微软推出后，便成为各种数据竞赛中刷分夺冠的神兵利器。

正如其名字中的Light所蕴含的那样，和XGBoost相比，LightGBM在大规模数据集上跑起来更加轻盈。

模型精度：XGBoost和LightGBM相当。

训练速度：LightGBM远快于XGBoost。

内存消耗：LightGBM远小于XGBoost。

缺失值特征：XGBoost和LightGBM都可以自动处理特征缺失值。

分类特征：XGBoost不支持类别特征，需要OneHot编码预处理。LightGBM直接支持类别特征。

image.png
二，LightGBM性能优化原理概述

LightGBM在XGBoost上主要有3方面的优化。

1，Histogram算法:直方图算法。
2，GOSS算法:基于梯度的单边采样算法。
3，EFB算法:互斥特征捆绑算法。

可以用如下一个简单公式来说明LightGBM和XGBoost的关系：

LightGBM = XGBoost + Histogram + GOSS + EFB。

那么，Histogram算法，GOSS算法，和EFB算法分别从什么角度对XGBoost进行性能优化呢？我们先概括性地从全局进行分析，然后再逐个加以介绍。

XGBoost模型训练的总体的复杂度可以粗略估计为：

训练复杂度 = 树的棵数✖️每棵树上叶子的数量✖️生成每片叶子的复杂度。

由于XGBoost采用的基模型是二叉树，因此生成每片叶子需要分裂一次。而每次分裂，需要遍历所有特征上所有候选分裂点位，计算按照这些候选分裂点位分裂后的全部样本的目标函数增益，找到最大的那个增益对应的特征和候选分裂点位，从而生成一片新叶子。

生成一片叶子的复杂度可以粗略估计为：

生成一片叶子的复杂度 = 特征数量✖️候选分裂点数量✖️样本的数量。

Hitogram算法的主要作用是减少候选分裂点数量，
GOSS算法的作用是减少样本的数量，
EFB算法的作用是减少特征的数量。

通过这3个算法的引入，LightGBM生成一片叶子需要的复杂度大大降低了，从而极大节约了计算时间。

同时Histogram算法还将特征由浮点数转换成0~255位的整数进行存储，从而极大节约了内存存储。

三，Histogram算法

直方图算法是替代XGBoost的预排序(pre-sorted)算法的。

预排序算法首先将样本按照特征取值排序，然后从全部特征取值中找到最优的分裂点位，该算法的候选分裂点数量与样本数量成正比。
直方图算法通过将连续特征值离散化到固定数量(如255个)的bins上，使得候选分为点位为常数个(num_bins -1).

此外，直方图算法还能够作直方图差加速。当节点分裂成两个时，右边叶子节点的直方图等于其父节点的直方图减去左边叶子节点的直方图。从而大大减少构建直方图的计算量。

image.png

image.png
image.png
四，GOSS算法

GOSS算法全称为Gradient-based One-Side Sampling，即基于梯度的单边采样算法。

其主要思想是通过对样本采样的方法来减少计算目标函数增益时候的复杂度。
但如果对全部样本进行随机采样，势必会对目标函数增益的计算精度造成较大的影响。
GOSS算法的创新之处在于它只对梯度绝对值较小的样本按照一定比例进行采样，而保留了梯度绝对值较大的样本。
这就是所谓的单边采样。由于目标函数增益主要来自于梯度绝对值较大的样本，因此这种方法在计算性能和计算精度之间取得了很好的平衡。

image.png
五，EFB算法

EFB算法全称是Exclusive Feature Bundling，即互斥特征绑定算法。

EFB算法可以有效减少用于构建直方图的特征数量，从而降低计算复杂度，尤其是特征中包含大量稀疏特征的时候。
在许多应用场景下，数据集中会有大量的稀疏特征，这些稀疏特征大部分样本都取值为0，只有少数样本取值非0。
通常可以认为这些稀疏特征是互斥的，即它们几乎不会同时取非零值。
利用这种特性，可以通过对某些特征的取值重新编码，将多个这样互斥的特征捆绑成为一个新的特征。
有趣的是，对于类别特征，如果转换成onehot编码，则这些onehot编码后的多个特征相互之间是互斥的，从而可以被捆绑成为一个特征。
因此，对于指定为类别特征的特征，LightGBM可以直接将每个类别取值和一个bin关联，从而自动地处理它们，而无需预处理成onehot编码多此一举。


image.png

补充二

lightGBM

xgboost不同的地方：

  1. xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了务必要的开销。 leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。
  1. lightgbm使用了基于histogram的决策树算法，这一点不同与xgboost中的 exact 算法，histogram算法在内存和计算代价上都有不小优势。
  • 内存上优势：很明显，直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而xgboost的exact算法内存消耗为：(2 * #data * #features* 4Bytes)，因为xgboost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。
  • 计算上的优势，预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)
  1. 直方图做差加速
  • 一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。
  1. lightgbm支持直接输入categorical 的feature
  • 在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。
  1. 但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢？
  • xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。
  • lightgbm做了cache优化？
  1. lightgbm哪些方面做了并行？
    feature parallel
    一般的feature parallel就是对数据做垂直分割（partiion data vertically，就是对属性分割），然后将分割后的数据分散到各个workder上，各个workers计算其拥有的数据的best splits point, 之后再汇总得到全局最优分割点。但是lightgbm说这种方法通讯开销比较大，lightgbm的做法是每个worker都拥有所有数据，再分割？（没懂，既然每个worker都有所有数据了，再汇总有什么意义？这个并行体现在哪里？？）
    data parallel
    传统的data parallel是将对数据集进行划分，也叫 平行分割(partion data horizontally)， 分散到各个workers上之后，workers对得到的数据做直方图，汇总各个workers的直方图得到全局的直方图。 lightgbm也claim这个操作的通讯开销较大，lightgbm的做法是使用”Reduce Scatter“机制，不汇总所有直方图，只汇总不同worker的不同feature的直方图(原理？)，在这个汇总的直方图上做split，最后同步。
image.png

Adaboost(Adaptive Boosting)

参考链接：
Adaboost、GBDT与XGBoost的区别
一步一步理解GB、GBDT、xgboost
Lightgbm基本原理介绍
LightGBM
干货！30分钟学会 LightGBM
lightgbm,xgboost,gbdt的区别与联系

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,723评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,080评论 2赞 379
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,604评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,440评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,431评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,499评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,893评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,541评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,751评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,547评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,619评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,320评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,890评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,896评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,137评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,796评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,335评论 2赞 342

推荐阅读更多精彩内容