NTUML 27. 梯度提升决策树(GBDT)

AdaBoost决策树

在介绍AdaBoost决策树之前,先回顾一下之前讲过的随机森林。随机森林的核心是,将一些决策树(内层)使用bagging的方法(外层)聚合起来。如果把决策树和AdaBoost算法结合起来,那么就得到了AdaBoost决策树。但是有一点需要注意:AdaBoost算法里要求基算法在训练时能够接受样本的权重,但是之前CART算法不能根据各个样本的权重做调整,因此现在最关键的问题是要对决策树算法作出修改,使其可以接受样本的权重,在每个\(t\)得到不一样的\(g_t\) ,即要实现一个加权的决策树算法\({\rm DTree}(\mathcal{D}, {\bf u}^{(t)})\)

加权算法的核心是,其需要根据权重最佳化根据权重加权过的\(E_{\rm in}\)。因此相对应的有两种处理办法

  • 将原有的基算法看作是白盒,查找其在何处修改\(E_{\rm in}\),然后在该处加上对权重的处理逻辑。例如SVM中,就是对应hinge loss的部分。但是决策树算法实现里有很多启发式算法,如果挨个分析哪部分跟\(E_{\rm in}\)有关,就比较麻烦
  • 将原有的基算法看作是黑盒,将送入算法的数据做变化。回想之前对bootstrapping的描述,其实质上也隐含了“权重”的概念:权重是3的数据,其实就是该数据复制3份;权重是7的数据,其实就是该数据复制7份。那么,推而广之,对送入算法的数据的变化方法就是根据数据的权重做采样。这样,就可以得到一组大小为\(N'\)的新数据集\(\tilde{\mathcal{D}}_t\),其中每种数据的比例正比于\(\bf u\),也就能体现权重的影响

因此,AdaBoost决策树的核心算法就是,将原始数据集\(\mathcal{D}\)按照\({\bf u}^{(t)}\)做抽样,然后使用得到的新数据集\(\tilde{\mathcal{D}}_t\)按照原有的决策树算法训练。不过这里还有一个矛盾:AdaBoost通常需要一些比较弱的基分类器,而原有的决策树算法初衷是要树完全增长。回想原来AdaBoost里每个基分类器的权重(票数)\(\alpha_t\)是由加权错误率\(\epsilon_t\)决定,即\(\alpha_t = \ln \blacklozenge_t = \ln \sqrt{(1-\epsilon_t)/\epsilon_t}\)。如果决策树\(g_t\)所有\({\bf x}_n\)上自由生长,且训练数据两两不等,那么就会有\(E_{\rm in}(g_t) = 0\),进而\(E_{\rm in}^{\bf u}(g_t) = \epsilon_t = 0\),即\(\alpha_t = \infty\),这棵树成了一个独裁者!

鉴于上面的情势,考虑AdaBoost的核心思想,为了避免上述状况的发生,还是需要基分类器都足够弱。让基分类器(这里是决策树)足够弱的方法有两种:

  • 对决策树进行剪枝,参见前面讲过的剪枝方法。或者一种最简单有效的方法是限制树的高度
  • 不送入全部数据,使用前面提到的采样方法。采样概率\(\propto {\bf u}^{(t)}\)

综合以上讨论,可以得到:AdaBoost决策树 = AdaBoost + 采样概率\(\propto {\bf u}^{(t)}\) + 剪枝过的决策树\({\rm DTree}(\tilde{\mathcal{D}}_t)\)

对树做剪枝的极端情况是,树的高度\(\le 1\)。考虑之前讲过的决策树(C&RT算法),树高为1的数只有一个分枝。回顾决策树的分枝条件定义,其要做的是让左右子树各自的不纯度两者加起来的值最小。如果不纯度的定义为二元分类误差,那么实际上此时决策树退化成了一个决策树桩。即前面提到的AdaBoost决策树桩是AdaBoost决策树的一种特殊情况

最优化角度看AdaBoost

之前讲解AdaBoost时,曾经提出过样本权重的更新法则 \[ u_n^{(t+1)} = \begin{cases}u_n^{(t)} \cdot \blacklozenge_t & {\rm if\ incorrect} \\ u_n^{(t)} / \blacklozenge_t & {\rm if \ correct}\end{cases} \] 这个式子可以做进一步化简:考虑之前提到的,如果\(y_n \in \{-1, +1\}\),那么当分类结果正确时,有\(y_ng_t({\bf x}_n) = 1\),否则\(y_ng_t({\bf x}_n) = -1\)。因此上式可以简写为递推式 \[ u_n^{(t+1)} = u_n^{(t)} \cdot \blacklozenge_t^{-y_ng_t({\bf x}_n)} \] 带入\(\blacklozenge_t = e^{\alpha_t}\),可以得到 \[ u_n^{(t+1)} = u_n^{(t)} \cdot \exp(-y_n\alpha_tg_t({\bf x}_n)) \] 将这个递推式展开,有 \[ u_n^{(T+1)} = u_n^{(1)} \cdot \prod_{t=1}^T\exp(-y_n\alpha_tg_t({\bf x}_n)) = \frac{1}{N} \cdot \exp\left(-y_n\sum_{t=1}^T\alpha_tg_t({\bf x}_n)\right) \] 注意最后指数里有一部分可以对应于AdaBoost的总假设函数\(G({\bf x})\)\(G({\bf x}) = {\rm sign}\left( \sum_{t=1}^T \alpha_tg_t({\bf x})\right)\)。可以将\(\sum_{t=1}^T \alpha_t g_t({\bf x})\)记为\(\{g_t\}\)\(\bf x\)上的投票得分(voting score)

前面还说过,AdaBoost实际上是一个线性混合的过程:将所有基假设函数看作是对原始数据的一个变换,然后在转换后的空间里学习出一个线性模型,这个线性模型就说明了每个\(g_t\)会占几票。如果将基假设函数的变换过程\(g_t({\bf x}_n)\)写为\(\phi_i({\bf x}_n)\),将每个\(g_t\)的票数写为权重的样子\(w_i\),那么投票得分就可以改写为\(\sum_{i=1}^T w_i\phi_i({\bf x}_n)\)。回顾之前提到的SVM间隔的定义,\({\rm margin} = \frac{y_n \cdot ({\bf w}^\mathsf{T}\phi({\bf x}_n) + b)}{\|{\bf w}\|}\),如果忽略掉这个式子中的常数项\(b\),正则项\(1/\|{\bf w}\|\)和用来判断点是落在分离超平面正确一侧还是错误一侧的\(y_n\),其核心部分\({\bf w}^\mathsf{T}\phi({\bf x}_n)\)其实传递的是点到超平面距离的概念。因此,\(y_n \cdot {\rm voting\ score}\)实际上就是带符号的且没有做过正则化的间隔,我们也希望这个间隔是一个比较大的正数。既然如此,那么\(\exp(-y_n({\rm voting\ score}))\)就应该越小越好,\(u_n^{(T+1)}\)也应该越小越好。实际上,AdaBoost就是在减小\(\sum_{n=1}^Nu_n^{(t)}\),其本质也是要让分离超平面离数据点的间隔变大。也就是说,它要减小的是 \[ \sum_{n=1}^N u_n^{(T+1)} = \frac{1}{N}\sum_{n=1}^N\exp\left(-y_n\sum_{t=1}^T\alpha_tg_t({\bf x}_n)\right) \] 再次搬出之前提到过很多次的线性得分\(s = \sum_{t=1}^T \alpha_t g_t({\bf x}_n)\),以及之前提到的0/1误差函数\({\rm err_{0/1}}(s, y) = [\![ys \le 0]\!]\)。如果将上面的这个式子看作是AdaBoost某种意义上要减小的误差函数,记为\(\widehat{\rm err}_{\rm ADA}\),那么有\({\rm \widehat{err}_{ADA}} = \exp(-ys)\)(称为指数损失函数)也是\(\rm err_{0/1}\)的上界。因此可以说,AdaBoost也是在减小0/1误差函数的凸上限,进而达到解好分类问题的目的

接下来,要证明AdaBoost算法的确可以减小\(\rm \widehat{err}_{ADA}\)。这个证明过程类似于之前提到的梯度下降法(GD),只不过GD是要找到一个向量\(\bf v\)作为下降方向,而AdaBoost是要找到一个基函数\(g_t\)作为下降方向。即在第\(t\)步迭代,为了寻找最优的\(g_t\),就是要求解 \[ \min_h \widehat{E}_{\rm ADA} = \frac{1}{N}\sum_{n=1}^N\exp\left(-y_n\left(\sum_{\tau = 1}^{t-1}\alpha_\tau g_\tau ({\bf x}_n) + \eta h({\bf x}_n)\right)\right) \] 将上式展开,代入\(u_n^{(t)} = \frac{1}{N}\cdot \exp(-y_n \sum_{t=1}^T\alpha_t g_t({\bf x}_n))\),可知 \[ \begin{align*} \min_h \widehat{E}_{\rm ADA} &= \frac{1}{N}\sum_{n=1}^N\exp\left(-y_n\left(\sum_{\tau = 1}^{t-1}\alpha_\tau g_\tau ({\bf x}_n) + \eta h({\bf x}_n)\right)\right) \\ &= \frac{1}{N}\sum_{n=1}^N\exp\left(-y_n\sum_{\tau = 1}^{t-1}\alpha_\tau g_\tau ({\bf x}_n) \right)\cdot\exp(-y_n\eta h({\bf x}_n)) \\ &= \sum_{n=1}^N u_n^{(t)}\exp(-y_n\eta h({\bf x}_n)) \end{align*} \] 将上式在零点附近做泰勒展开,可得 \[ \begin{align*} \min_h \widehat{E}_{\rm ADA} &= \sum_{n=1}^N u_n^{(t)}\exp(-y_n\eta h({\bf x}_n)) \\ &\approx \sum_{n=1}^Nu_n^{(t)}(1-y_n\eta h({\bf x}_n)) \\ &= \sum_{n=1}^N u_n^{(t)} - \eta\sum_{n=1}^N u_n^{(t)}y_nh({\bf x}_n) \end{align*} \] 这就很像之前GD \(\min_{\|v\|=1} E_{\rm in}({\bf w}_t + \eta {\bf v}) \approx E_{\rm in}({\bf w}_t) + \eta {\bf v}^\mathsf{T}\nabla E_{\rm in}({\bf w}_t)\)的形式了!同理,这里\(\sum_{n=1}^N u_n^{(t)}\)是常数项,因此最好的\(h\)会最小化\(\sum_{n=1}^N u_n^{(t)}(-y_nh({\bf x}_n))\)

由于这里考虑的是二元分类问题,因此\(y_n \in \{-1, +1\}, h({\bf x}_n) \in \{-1, +1\}\)。利用这个性质,展开要最小化的式子,有 \[ \begin{align*} \sum_{n=1}^N u_n^{(t)}(-y_nh({\bf x}_n)) &= \sum_{n=1}^N u_n^{(t)} \begin{cases} - 1 & {\rm if\ }y_n = h({\bf x}_n) \\ +1 & {\rm if\ }y_n \not= h({\bf x}_n)\end{cases} \\ &= - \sum_{n=1}^N u_n^{(t)} + \sum_{n=1}^N u_n^{(t)} \begin{cases} 0 & {\rm if\ }y_n = h({\bf x}_n) \\ 2 & {\rm if\ }y_n \not= h({\bf x}_n)\end{cases} \\ &= -\sum_{n=1}^N u_n^{(t)} + 2\sum_{n=1}^N u_n^{(t)} [\![y_n \not= h({\bf x}_n)]\!] \\ &= -\sum_{n=1}^N u_n^{(t)} + 2E_{\rm in}^{ {\bf u}^{(t)}}(h) \cdot N \end{align*} \] 也就是说,要最小化\(\sum_{n=1}^N u_n^{(t)}(-y_nh({\bf x}_n))\),实质上就是要最小化\(E_{\rm in}^{ {\bf u}^{(t)}}(h)\),而这正是AdaBoost的算法\(\mathcal{A}\)做的事!即\(\mathcal{A}\)找到了一个好的梯度下降的函数方向\(g_t = h\)

根据上面的推导,AdaBoost通过近似最小化\(\widehat{E}_{\rm ADA} = \sum_{n=1}^N u_n^{(t)}\exp(-y_n\eta h({\bf x}_n))\)来找到一个最优的函数\(g_t = h\)。那么在找到\(g_t\)以后,能不能不满足于像原始GD那样每次只移动固定的一小步\(\eta\),而是通过最小化\(\widehat{E}_{\rm ADA} = \sum_{n=1}^N u_n^{(t)}\exp(-y_n\eta g_t({\bf x}_n))\),找一个最优的\(\eta_t\),让这一步迈得大一点?观察求和项里的情况:如果分类正确,即\(y_n = g_t({\bf x}_n)\),则要求和的那一项变为\(u_n^{(t)}\exp(-\eta)\);如果分类错误,就会有\(y_n \not= g_t({\bf x}_n)\),要求和的那一项变为\(u_n^{(t)} \exp(+\eta)\)。因此对求和项分拆并代入\(\epsilon_t\)的定义,有 \[ \begin{align*} \sum_{n=1}^N u_n^{(t)}\exp(-y_n\eta g_t({\bf x}_n)) &= \sum_{n=1}^N \left(u_n^{(t)}[\![y_n = g_t({\bf x}_n)]\!]\exp(-\eta) + u_n^{(t)}[\![y_n = g_t({\bf x}_n)]\!]\exp(+\eta) \right) \\ &= \exp(-\eta)\cdot \sum_{n=1}^N u_n^{(t)}\cdot \frac{\sum_{n=1}^N u_n^{(t)}[\![y_n = g_t({\bf x}_n)]\!]}{\sum_{n=1}^N u_n^{(t)}} + \exp(+\eta)\cdot \sum_{n=1}^N u_n^{(t)}\cdot \frac{\sum_{n=1}^N u_n^{(t)}[\![y_n \not= g_t({\bf x}_n)]\!]}{\sum_{n=1}^N u_n^{(t)}} \\ &= \exp(-\eta) \cdot \sum_{n=1}^N u_n^{(t)}\cdot(1-\epsilon_t) + \exp(+\eta)\cdot \sum_{n=1}^N u_n^{(t)}\cdot\epsilon_t \\ &= \sum_{n=1}^N u_n^{(t)}\cdot \left((1-\epsilon_t)\exp(-\eta) + \epsilon_t\exp(+\eta)\right) \end{align*} \] 求解\(\frac{\partial \widehat{E}_{\rm ADA}}{\partial \eta} = 0\)可以得到最优的\(\eta_t\),而 \[ \begin{align*} &\frac{\partial \widehat{E}_{\rm ADA}}{\partial \eta} = 0 \\ \Leftrightarrow & \sum_{n=1}^N u_n^{(t)}\cdot \left(-(1-\epsilon_t)\exp(-\eta) + \epsilon_t\exp(+\eta)\right) = 0 \\ \Leftrightarrow & -(1-\epsilon_t) + \epsilon_t\exp(+2\eta) = 0 \\ \Leftrightarrow & \exp(+2\eta) = \frac{1-\epsilon_t}{\epsilon_t} \\ \Leftrightarrow & \eta = \ln\sqrt{ \frac{1-\epsilon_t}{\epsilon_t}} = \alpha_t \end{align*} \] 因此,其实\(\alpha_t\)是跨度最大的\(\eta_t\)

综上所述,AdaBoost是沿着近似函数梯度(方向是函数而不是向量),向最优方向做了最大程度的下降

梯度提升

对上一节所讲的内容做一个总结,就是AdaBoost每一步都是在最小化指数误差:每一步找到一个\(h\)作为\(g_t\),然后决定要走多远,这个跨度就是\(\alpha_t\)

既然AdaBoost实际上每一步都是在最小化某个误差函数,那么可否对其进行扩展,让其每一步优化的误差函数可以是之前讲过的那些误差函数?答案是肯定的,扩展以后得到的算法称为梯度提升算法(Gradient Boosting),形式为 \[ \min_\eta\min_h \frac{1}{N}\sum_{n=1}^N{\rm err}\left(\sum_{\tau=1}^{t-1} \alpha_\tau g_\tau ({\bf x}_n) + \eta h({\bf x}_n), y_n\right) \] 在这个框架下,就可以使用不同的\(h\)来做Boosting,解决不同的问题

例如,如果要使用Boosting方法求解回归问题,将\(\sum_{\tau = 1}^{t-1}\alpha_\tau g_\tau({\bf x}_n)\)写成\(s_n\),那么误差函数就应该是平方误差,\({\rm err}(s, y) = (s - y)^2\)。对上式内层求最小\(h\)的问题,在零点做泰勒展开,有 \[ \begin{align*} \min_h \frac{1}{N}\sum_{n=1}^N {\rm err}(s_n + \eta h({\bf x}_n), y_n) &\approx \min_h \frac{1}{N} \sum_{n=1}^N {\rm err}(s_n, y_n) + \frac{1}{N}\sum_{n=1}^N \eta h({\bf x}_n)\frac{\partial {\rm err}(s, y_n)}{\partial s}{\huge|}_{s=s_n} \\ &= \min_h {\rm constants} + \frac{\eta}{N}\sum_{n=1}^N h({\bf x}_n)\cdot2(s_n - y_n) \end{align*} \] 由于是一个最小化问题,因此要让\(h\)越小越好。如果\(s_n - y_n\)为正,那么\(h\)就应该为负;否则\(h\)就应该为正。但是这里没有限制,因此此时有\(h({\bf x}_n) = -\infty \cdot (s_n - y_n)\)。由于要做的只是寻找一个方向,因此这里可以(也应该)对\(h\)的大小做一个限制,\(h\)的大小由\(\eta\)来解决。直观的做法是在求解时对\(h\)的大小做一个限制,例如\(\|h\|=1\),但是有限制的最优化问题求解起来比较麻烦。另一种方法,是借鉴拉格朗日乘子和\(\ell_2\)正则化的思想,将\(h\)的大小作为惩罚项放进要求解的问题中,有 \[ \begin{align*} \min_h &&&{\rm constants} + \frac{\eta}{N}\sum_{n=1}^N(2h({\bf x}_n)(s_n - y_n) + (h({\bf x}_n))^2) \\ &=&&{\rm constants} + \frac{\eta}{N}\sum_{n=1}^N\left({\rm constant} + (h({\bf x}_n) - (y_n -s_n))^2\right) \end{align*} \] 如果将上式所有常数项都去掉(其存在与否不影响结果),那么其实就是要找\(\min_h \sum_{n=1}^N (h({\bf x}_n) - (y_n - s_n))^2\),而这个问题实际上还是一个回归问题,只不过此时目标值从\(y_n\)变成了残差\(y_n - s_n\)。因此用来做回归的梯度提升就是通过对残差做回归,来找到最优的\(g_t = h\)

在有了最优的\(h\)以后,接下来就是要求解最优的\(\eta\)。这个优化问题可以写为 \[ \begin{align*} &\min_\eta \frac{1}{N}\sum_{n=1}^N (s_n + \eta g_t({\bf x}_n) - y_n)^2 \\ = &\min_\eta \frac{1}{N}\sum_{n=1}^N ((y_n - s_n) - \eta g_t({\bf x}_n))^2 \end{align*} \] 其实质是一个单变量的线性回归问题,输入是经过\(g_t\)变换过的原始输入,输出是残差项

将上述内容组合在一起,就可以得到梯度提升决策树算法(GBDT)

\(s_1 = s_2 = \ldots = s_N = 0\)

\(t=1,2,\ldots, T\)

  1. 使用\(\mathcal{A}(\{({\bf x}_n, y_n-s_n)\})\)获得\(g_t\),其中\(\mathcal{A}\)是一个最小化平方误差的回归算法,通常是被剪枝过的C&RT决策树
  2. 计算\(\alpha_t = {\rm OneVarLinearReg}(\{(g_t({\bf x}_n), y_n-s_n)\})\)
  3. 更新\(s_n \leftarrow s_n + \alpha_t g_t({\bf x}_n)\)

返回\(G({\bf x}) = \sum_{t=1}^T \alpha_t g_t({\bf x})\)

GBDT是AdaBoost-决策树用来求解回归问题的“表亲”,在实践中非常常用

(笔者注:GBDT的两个很有名的实现XGBoost和LightGBM也可以用来求解分类问题,sklearn也有GBDTClassifier)

聚合模型方法综述

至此,所有聚合模型已介绍完毕,这里对它们做一回顾

  • 模型的混合法,是在得到各个不同的\(g_t\)以后做聚合,分为一下三种混合方式

    • 均匀混合:每个\(g_t\)票数相同,追求模型的复杂性
    • 非均匀混合:实际上就是对输入通过\(g_t\)做一个变换,然后训练一个线性模型。其追求的是模型的复杂性,但是需要小心使用,防止过拟合
    • 条件混合:与非均匀混合类似,只不过最后训练的是非线性模型。这种方法通常又称为模型的堆叠法(stacking)。其追求的也是模型的复杂性
  • 模型的学习法,是一边学习\(g_t\)一边做聚合。关系可见下图 聚合学习模型概览

    其中随机森林、AdaBoost-DTree和GBDT都是很常用的模型

模型聚合有时可以起到特征变换的作用,使得最后得到的\(G({\bf x})\)很强,避免了欠拟合的问题;有时可以起到正则化的作用,使最后得到的\(G({\bf x})\)不偏不倚,避免了过拟合的问题。总之,适当的模型聚合(有时又称组合ensemble),可以得到更好的效果

坚持原创技术分享,您的支持将鼓励我继续创作!