4. Boosting 算法详解

Boosting 算法详解


  • Boosting算法简介

    李泽康 2017.10.21 AI Lab

    PAC

    • Probably approximately correct（概率近似正确）
    • Strongly learnable（强可学习）
      • Exist an algorithm that requires error can be driven arbitrarily close to 0.​
    • Weakly learnable（弱可学习）
      • Exist an algorithm that only requires the hypothesis that does better than random guessing.
    • 一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

    Adaboost

    • Adaboost从训练数据中学习一系列弱分类器，并将这些弱分类器线性组合成一个强分类器。

    • 它是一个加法模型:
      f(x)=∑m=1MαmGm(x) f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)
      αm\alpha_{m} ：分类器的系数， Gm(x)G_{m}(x) :不同的弱分类器

    • 损失函数为指数函数：

      (αm,Gm(x))=argminα,G∑i=1Nw‾miexp[−yiαG(xi)] (\alpha_{m},G_{m}(x)) = \arg\min_{\alpha, G} \sum_{i=1}^{N}\overline w_{mi}exp[-y_{i}\alpha G(x_{i})]

      其中 w‾mi=exp[−yifm−1(xi)] \overline w_{mi} = exp[-y_{i}f_{m-1}(x_{i})]

    • Adaboost 算法原理(以二分类为例)

      输入： (xi,yi),y=−1,+1 (x_{i}, y_{i}), y={-1, +1}

      1. 初始化训练数据的权值分布：D1=(w11,...,w1i,...,w1N) D_{1} = (w_{11}, ...,w_{1i},...,w_{1N}) w1i=1N,i=1,2,...,Nw_{1i} = \frac{1}{N}, i=1,2,...,N

      2. 对m=1,2,...,Mm=1, 2, ..., M

        1. 使用权值分布为DmD_{m} 训练得到弱分类器：Gm(x)G_{m}(x)

        2. 计算误差率：em=∑i=1NwmiI(Gm(xi)≠yi)e_{m} = \sum_{i=1}^{N}w_{mi}I(G_{m}(x_{i}) \neq y_{i})

        3. 计算分类器系数αm\alpha_{m} : αm=12log1−emem\alpha_{m} = \frac{1}{2}log\frac{1-e_{m}}{e_m}

        4. 更新权值分布：

        Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N)D_{m+1} = (w_{m+1,1},...,w_{m+1,i}, ... , w_{m+1,N})

        wm+1,i=wmiZmexp(−αmyiGm(xi))w_{m+1, i} = \frac{w_{mi}}{Z_{m}}exp(-\alpha_{m}y_{i}G_{m}(x_{i}))

        Zm=∑i=1Nwmiexp(−αmyiGm(xi))Z_{m} = \sum_{i=1}^{N}w_{mi}exp(-\alpha_{m}y_{i}G_{m}(x_{i}))

        其中，规范化因子ZmZ_{m} 使Dm+1D_{m+1} 成为一个概率分布

      3. 构建分类器的线性组合:f(x)=∑m=1MαmGm(x)f(x)= \sum_{m=1}^{M}\alpha_{m}G_{m}(x) 得到最终分类器Gm(x)=sign(f(x))G_{m}(x) = sign(f(x))

    • 一些分析

      1. Adaboost的正则化（防止过拟合）：定义learning_rate ll ,前面有：fm(x)=fm−1(x)+αmGm(x)f_{m}(x) = f_{m-1}(x) + \alpha_mG_{m}(x)

        加上正则化项有：fm(x)=fm−1(x)+lαmGm(x)f_{m}(x) = f_{m-1}(x) + l\alpha_mG_{m}(x)

      2. αm\alpha_{m}随eme_{m} 减小而增大，分类错误率越小的基本分类器在最终分类器中的作用越大

      3. adaboost不改变数据，只是改变数据的权值

      4. Adaboost的训练误差界：

        1N∑i=1NI(G(xi)≠yi)≤1N∑iexp(−yif(xi))=∏mZm≤exp(−2∑m=1Mγm2),γm=12−em\frac{1}{N}\sum_{i=1}^{N}I(G_(x_{i}) \neq y_{i}) \leq \frac{1}{N}\sum_{i}exp(-y_{i}f(x_{i})) = \prod_{m}Z_{m} \leq exp(-2\sum_{m=1}^{M}\gamma_{m}^{2}), \gamma_{m} = \frac{1}{2} - e_{m}

        So, adaboost训练误差以指数速率下降！

      5. Adaboost使用比较广泛的弱学习器是决策树和神经网络。

      6. 优势：分类精度比较高，比较灵活可以使用各种回归、分类模型作为弱学习器，不容易发生过拟合

        缺点：对异常数据比较敏感，可能对异常数据赋较大权值。

    GDBT

    • Gradient Decent Boosting Tree

    • Gradient Boosting 就是在函数空间的梯度下降

    • 是一个加法模型：

      F(x;w)=∑m=0Mamhm(x;wm)=∑m=0Mfm(x;wm)F(x;w)=\sum_{m=0}^{M}a_{m}h_{m}(x;w_{m})=\sum_{m=0}^{M}f_{m}(x;w_{m})

      xx ：输入样本，hmh_{m} :分类回归树，ww：回归树的参数，αm\alpha_{m} :每棵树权重

    • GDBT算法原理

      输入：(xi,yi),M,L(x_{i}, y_{i}), M, L

      1. 初始化f0f_{0}
      2. 对m=1,2,...,Mm = 1,2,...,M :
        1. 响应：y~i=−[∂L(yi,F(xi))∂F(xi)]F(x)=Fm−1(x),i=1,...,N\widetilde{y}_{i} = -[\frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}]_{F(x)=F_{m-1}(x)}, i=1,...,N
        2. 学习第m棵树：wm=argminw∑i=1N(y~i−hm(xi;wm−1))2w_{m} = \arg \min_{w}\sum_{i=1}^{N}(\widetilde y_{i}-h_{m}(x_{i}; w_{m-1}))^{2}
        3. line search 寻找步长：ρm=argminρ∑i=1NL(yi,Fm−1(xi)+ρh(xi;wm))\rho_{m} = \arg \min_{\rho} \sum_{i=1}^{N}L(y_{i}, F_{m-1}(x_{i}) + \rho h(x_{i};w_{m}))
        4. 令fm=ρmhmf_{m} = \rho_{m}h_{m} 则Fm=Fm−1+fmF_{m} = F_{m-1} + f_{m}

    • 一些分析

      1. GDBT就是使用决策树作为基分类器的boosting方法。与Adaboost不同的是GDBT是一个不断拟合残差并直接叠加到F上的过程，残差不断减小，Loss不断减小。
      2. 在GDBT里，F是泛函空间，f是函数，组合时直接叠加。而Adaboost中f是有权重的，在GDBT中权重信息被吸收到决策树的叶子节点里了。
      3. 初始化的时候
        • 随机
        • 用训练样本的充分统计量初始化
        • 用其他模型的预测值初始化，例：GDBT在搜索引擎排序中的应用 它使用了RF的输出作为GDBT的初始化，取得了不错的效果。
      4. 使用GDBT生成新特征，Practical Lessons from Predicting Clicks on Ads at Facebook, 2014.

    XGBoost

    • GDBT是函数空间的梯度下降，XGBoost是函数空间的牛顿法

    • 相比于GDBT，XGBoost多了正则化项，目标函数变为：∑LL(y^i;yi)+∑kΩ(fk)\sum_{L}L(\hat y_{i}; y_{i}) + \sum_{k}\Omega(f_{k})

      XGBoost采用的正则化项：Ω(f)=γT+12λ∣∣w∣∣2\Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^{2} , 其中，T：叶子节点数，w：叶节点分数

    • 误差函数的二阶泰勒展开：

      1. 在第t次迭代后：y^i(t)=y^i(t−1)+ft(xi)\hat y_{i}^{(t)} = \hat y_{i}^{(t-1)} + f_{t}(x_{i})

      2. 此时损失函数可以写为：L(y^i(t−1)+ft(xi),yi)L(\hat y_{i}^{(t-1)} + f_{t}(x_{i}), y_{i}), 需要学习的只有ftf_{t}

      3. 在y^i(t−1)\hat y_{i}^{(t-1)} 处将损失函数进行二阶泰勒展开：L(y^i(t−1),yi)+gift(xi)+12hift2(xi)L(\hat y_{i}^{(t-1)}, y_{i}) + g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^{2}(x_{i})

        其中，gi=∂y^(t−1)L(y^(t−1),yi)g_{i} = \partial_{\hat y^{(t-1)}}L(\hat y^{(t-1)},y_{i}) hi=∂y^(t−1)2L(y^(t−1),yi)h_{i} = \partial_{\hat y^{(t-1)}}^{2}L(\hat y^{(t-1)}, y_{i})

      4. 显然，L(y^i(t−1),yi)L(\hat y_{i}^{(t-1)}, y_{i}) 为常数，可以消掉，目标函数：L~(t)=∑i=1N[gift(xi)+12hift2(xi)]+Ω(ft)\widetilde {\mathcal {L}}^{(t)} = \sum_{i=1}^{N}[ g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^{2}(x_{i})] + \Omega(f_{t})

      5. L~(t)=∑i=1N[gift(xi)+12hift2(xi)]+γT+12∣∣w∣∣2=∑i=1N[giwq(xi)+12hiwq(xi)]+γT+12λ∑j=1Twj2\widetilde {\mathcal {L}}^{(t)} = \sum_{i=1}^{N}[ g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f_{t}^{2}(x_{i})] + \gamma T + \frac{1}{2}||w||^{2} = \sum_{i=1}^{N}[g_{i}w_{q_(x_{i})} + \frac{1}{2}h_{i}w_{q(x_{i})}] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_{j}^{2}

      6. 这个式子感觉挺复杂，现在我们要把他们统一起来，wq(xi)w_{q(x_{i})} 表示回归树对每个样本的预测值，wjw_{j} 表示每个叶子节点的分数，q(xi)q(x_{i}) 表示将样本分到某个叶子节点上。我们可以设集合Ij=i∣q(xi)=jI_{j} = {i|q(x_{i}) = j} ，此时：

        L~(t)=∑j=1T[∑i∈Ijgiwj+12(∑i∈Ijhi+λ)wj2]+γT=∑<em>j=1T[G</em>jwj+12(Hj+λ)wj2]+γT\widetilde {\mathcal {L}}^{(t)} = \sum_{j=1}^{T}[\sum_{i\in I_{j}}g_{i}w_{j} + \frac{1}{2} (\sum_{i\in I_{j}}h_{i} + \lambda)w_{j}^{2}] + \gamma T = \sum <em>{j=1}^{T}[G</em>{j}w_{j} + \frac{1}{2} (H_{j} + \lambda )w_{j}^{2}] + \gamma T

      7. 如何来使损失函数最小化：假定树的结构确定了，那么我们需要调整的只是wjw_{j} ，当L~(t)\widetilde {\mathcal {L}}^{(t)} 对wjw_{j} 导数为0时，取到极小，此时可以得到最优预测分数和最小损失：

        wj∗=−GjHj+λw_{j}^{*} = - \frac{G_{j}}{H_{j} + \lambda} L~∗=−12∑j=1TGj2Hj+λ+γT\widetilde {\mathcal {L}}^{*} = -\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^{2}}{H_{j} + \lambda } + \gamma T

      8. So， 怎么去确定树的结构呢？

        1. 暴力解所有树结构（np难啊）
        2. 贪心，每次分裂一个节点，计算增益：Gain=GL2HL+λ+GR2HR+λ−(GL+GR)2(HL+HR)+λ−γGain = \frac{G_{L}^{2}}{H_{L} + \lambda} + \frac{G_{R}^{2}}{H_{R} + \lambda} - \frac{(G_{L} + G_{R})^{2}}{(H_{L} + H_{R}) + \lambda} -\gamma
          • exact greedy
          • Weighted Quantile Sketch

    • 并行

    • 优势：

      1. 加入了正则化
      2. 使用了二阶导信息
      3. 列抽样来防止过拟合
      4. Weighted Quantile Sketch
      5. 样本数据预先排序，存储为block，利于并行
      6. 可以对缺失值自动处理

    • 调参

      https://www.analyticsvidhya.com/blog/2016/03/complete-guide-parameter-tuning-xgboost-with-codes-python/

    LightGBM

    一个基于决策树算法的分布式梯度提升框架，https://github.com/Microsoft/LightGBM

    • 与xgboost的速度比较

      Data xgboost xgboost_hist LightGBM
      Higgs 3794.34 s 551.898 s 238.505513 s
      Yahoo LTR 674.322 s 265.302 s 150.18644 s
      MS LTR 1251.27 s 385.201 s 215.320316 s
      Expo 1607.35 s 588.253 s 138.504179 s
      Allstate 2867.22 s 1355.71 s 348.084475 s

    • 内存占用比较：

      Data xgboost xgboost_hist LightGBM
      Higgs 4.853GB 3.784GB 0.868GB
      Yahoo LTR 1.907GB 1.468GB 0.831GB
      MS LTR 5.469GB 3.654GB 0.886GB
      Expo 1.553GB 1.393GB 0.543GB
      Allstate 6.237GB 4.990GB 1.027GB

    • 准确率比较：

      Data Metric xgboost xgboost_hist LightGBM
      Higgs AUC 0.839593 0.845605 0.845154
      Yahoo LTR NDCG1 0.719748 0.720223 0.732466
      MS LTR NDCG1 0.483956 0.488649 0.524255
      Expo AUC 0.756713 0.777777 0.777543

    • 两者区别：

      1. 切分算法：

        1. xgboost基于预排序（pre-sorted），对所有特征进行预排序，在寻找分割点时代价为O(#data)。很精确，但空间，时间，cache优化不友好。

        2. LightGBM使用了Histogram算法,它主要是把连续的浮点值离散化为k个整数，构造一个宽度为#bins（k）的直方图。根据这些离散值寻找最优分割。内存消耗大大降低，这样不需要存储预排序的结果，而且可以只保存特征离散后的值，这个值一般用8位整型存就够了，而在预排序算法中，需要使用32位分别储存index和feature value。内存消耗降低到1/8。时间复杂度从O(#data * #feature)变为O(#bins * #feature)。很好的利用了弱模型集成的思想。

          直方图算法

          ​

      2. 决策树生长策略：

        1. xgboost使用level-wise（容易多线程优化，控制模型复杂度，不容易过拟合，但比较低效）
        2. LightGBM使用带深度限制的leaf-wise

      3. LightGBM 的直方图差加速优化，提升一倍速度。

      4. 高效并行

        1. 原始

          特征并行 的主要思想是在不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。

          数据并行则是让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。

        2. LightGBM针对这两种并行方法都做了优化

          在特征并行算法中，通过在本地保存全部数据避免对数据切分结果的通信；

          在数据并行中使用分散规约(Reduce scatter)把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。**基于投票的数据并行(Parallel Voting)**则进一步优化数据并行中的通信代价，使通信代价变成常数级别。

      5. LightGBM是第一个直接支持类别特征的GBDT工具

    Reference

    Stay hungry, Stay foolish.

    回复 引用 0 1 条回复

  • 补一篇之前怼 XGBoost 的时候看的，T. Chen 本人写的 Tree Boosting 课件
    技术上网 required

    自己写的笔记

    回复 引用 1
回复
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开，我们正在尝试重连，请耐心等待