分类器融合(5):梯度提升决策树

| 研究学术  | 机器学习基础  分类器融合  梯度下降法  GBDT  决策树 

AdaBoost 决策树

AdaBoost-DTree($\mathcal D$)


对于$t=1,2,\ldots,T$,循环执行:

  1. 更新数据的权重$\mathbf u^{(t)}$;
  2. 通过决策树算法$\mbox{DTree}\left(\tilde{\mathcal D}, \mathbf u^{(t)}\right)$得到$g_t$;
  3. 计算$g_t$的投票权重$\alpha_t$。

返回$G=\mbox{LinearHypo}(\{\left(g_t,\alpha_t\right)\})$。

由此可见,AdaBoost 决策树需要加权决策树算法。对于有权重的算法,需要根据权重最小化$E_{in}$,通常有两种方法:

  • 一种方法是通过算法加权,在计算$E_{in}$的地方嵌入权重计算,比如AdaBoost采用的最小化加权误差
  • 另一种方法是将算法当成黑盒不变更,通过数据集加权,根据权重在bootstrap时“复制”数据,也就是加权的重采样。

AdaBoost决策树通常采用后一种方法,AdaBoost+sampling $\propto \mathbf u^{(t)}$+$\mbox{DTree}(\tilde{\mathcal D}_t)$。

AdaBoost 的$\alpha_t$通过错误率确定。对于所有$\mathbf x_n$不同的完全成长决策树,$E_{in}(g_t)=0$,那么$E_{in}^{\mathbf u}(g_t)=0$,因此$\epsilon_t=0$并且$\alpha_t=\infty$。合适的方法是让决策树弱些,在部分数据集上训练剪枝的决策树。即使在$\tilde{\mathcal D}_t$上得到错误率为0的决策树$g_t$,回到$\mathcal D$上$\alpha_t$可能是大于、等于或小于0。剪枝可采用常规方法或只限制决策树高度,在数据重采样阶段已经包含了只抽取部分数据的功能。因此,AdaBoost决策树=AdaBoost+sampling $\propto \mathbf u^{(t)}$+剪枝的$\mbox{DTree}(\tilde{\mathcal D}_t)$。

如果C&RT的高度限制为不超过1,当用二分类的误差作为不纯度时,AdaBoost决策树就是AdaBoost-Stump,此时通常有$\epsilon_t\neq 0$,一般不再需要sampling。

AdaBoost 理论分析:最速函数梯度下降法

AdaBoost的权重更新可以合并为 \[ u_n^{(t+1)}=u_n^{(t)}\cdot\blacklozenge_t^{-y_ng_t(\mathbf x_n)}, \] 由于$\blacklozenge_t=\exp(\alpha_t)$,因此 \[ u_n^{(t+1)}=u_n^{(t)}\cdot\exp\left(-y_n\alpha_tg_t\left(\mathbf x_n\right)\right), \] 那么 \begin{equation} u_n^{(T+1)}=u_n^{(1)}\cdot\prod_{t=1}^T\exp\left(-y_n\alpha_tg_t\left(\mathbf x_n\right)\right)={1\over N}\exp\left(-y_n\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)\right)。 \label{eq:un-t-plus-1} \end{equation} AdaBoost是分类器的线性组合,$\sum_{t=1}^T\alpha_tg_t(\mathbf x)$是$\{g_t\}$在$\mathbf x$上的投票得分(voting score),也就是对AdaBoost,$u_n^{(T+1)}\propto \exp\left(-y_n\cdot\left(\mbox{voting score on }\mathbf x_n\right)\right)$。

线性混合(linear blending),可以看作线性模型和以假设作为特征转换的结合 \[ G(\mathbf x_n)=\mbox{sign}\left(\overbrace{\sum_{t=1}^T\underbrace{\alpha_t}_{w_i}\underbrace{g_t(\mathbf x_n)}_{\phi_i(\mathbf x_n)}}^{\mbox{voting score}}\right)。 \] 对比hard-margin的SVM的边界${y_n\cdot\left(\mathbf w^T\phi(\mathbf x_n)+b\right)\over\lVert\mathbf w\rVert}$,投票得分可视为某种空间中非规范化的边界(距离)的度量,“$y_n$(voting score)=signed & unnormalized margin”。期望$y_n$(voting score)是正的,且越大越好,那么$\exp(-y_n(\mbox{voting score}))$越小越好,$u_n^{(T+1)}$越小越好。AdaBoost的$\sum_{n=1}^Nu_n^{(t)}$随着$t$的增大越来越小,在最后一轮 \begin{equation} \sum_{n=1}^Nu_n^{(T+1)}={1\over N}\sum_{n=1}^N\exp\left(-y_n\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)\right) \label{eq:sum-un-t-plus-1} \end{equation} 达到最小,边界$y_n\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)$最大化实现large margin的效果。

AdaBoost的误差界
图 1: AdaBoost的误差界 [PNG]

令线性评分函数$s=\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)$,AdaBoost的指数误差度量(exponential error measure)$\widehat{err}_{ADA}(s,y)=\exp(-ys)$是0/1误差$\widehat{err}_{0/1}(s,y)=[[ys\leq 1]]$的上界1,如上图右所示,通过0/1误差的凸上界(convex upper bound)$\widehat{err}_{ADA}$作为算法误差度量(algorithmic error measure),通过上界误差最小化使0/1误差最小化。

AdaBoost通过增加函数$h(\mathbf x)$的方式,使基于\eqref{eq:sum-un-t-plus-1}的误差$\widehat E_{ADA}=\sum_{n=1}^Nu_n^{(t+1)}$最小化, \begin{equation} \begin{aligned} \min_h\quad\widehat E_{ADA} &\overset{[1]}{=}{1\over N}\sum_{n=1}^N\exp\left(-y_n\left(\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)+ \eta h(\mathbf x_n)\right)\right)\\ &\overset{[2]}{=}\sum_{n=1}^Nu_n^{(t)}\exp\left(-y_n\eta h(\mathbf x_n)\right) \overset{\mbox{taylor}}{\approx}\sum_{n=1}^Nu_n^{(t)}\left(1-y_n\eta h(\mathbf x_n)\right)\\ &=\sum_{n=1}^Nu_n^{(t)}+\eta\sum_{n=1}^Nu_n^{(t)}\left(-y_nh(\mathbf x_n)\right), \end{aligned} \label{eq:min-E-ADA} \end{equation}

  • [1]:增加函数$h(\mathbf x)$,由\eqref{eq:sum-un-t-plus-1}可得$\sum_{\tau=1}^t\alpha_\tau g_\tau\left(\mathbf x_n\right)=\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau\left(\mathbf x_n\right)+\eta h(\mathbf x_n)$;
  • [2]:由\eqref{eq:un-t-plus-1}可得$u_n^{(t)}={1\over N}\exp\left(-y_n\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau\left(\mathbf x_n\right)\right)$。

公式\eqref{eq:min-E-ADA}形如梯度下降法最小化$E_{in}$ \[ \min_{\lVert\mathbf v\rVert=1}E_{in}(\mathbf w_t+\eta\mathbf v) \approx \underbrace{E_{in}(\mathbf w_t)}_{\mbox{known}} +\underbrace{\eta}_{\mbox{given positive}}\mathbf v^T\underbrace{\nabla E_{in}(\mathbf w_t)}_{\mbox{known}}, \] 好的$h(\mathbf x)$能最小化$\sum_{n=1}^Nu_n^{(t)}\left(-y_nh(\mathbf x_n)\right)$。对二分类,$y_n$和$h(\mathbf x_n)$都属于$\{-1,+1\}$,那么 \[ \begin{aligned} \sum_{n=1}^Nu_n^{(t)}\left(-y_nh(\mathbf x_n)\right) &=\sum_{n=1}^Nu_n^{(t)} \left\{ \begin{aligned} -1\quad\mbox{if }y_n=h(\mathbf x_n)\\ +1\quad\mbox{if }y_n\neq h(\mathbf x_n) \end{aligned} \right.\\ &=-\sum_{n=1}^Nu_n^{(t)}+\sum_{n=1}^Nu_n^{(t)} \left\{ \begin{aligned} 0\quad\mbox{if }y_n=h(\mathbf x_n)\\ 2\quad\mbox{if }y_n\neq h(\mathbf x_n) \end{aligned} \right.\\ &\overset{[1]}{=}-\sum_{n=1}^Nu_n^{(t)}+2E_{in}^{\mathbf u^{(t)}}(h)\cdot N, \end{aligned} \]

因此,也就是要使$E_{in}^{\mathbf u^{(t)}}(h)$变小,这就是AdaBoost中算法$\mathcal A$的任务,找出一个好的函数方向$h$。

AdaBoost通过近似最小化$\min_h\widehat E_{ADA}=\sum_{n=1}^Nu_n^{(t)}\exp\left(-y_n\eta h(\mathbf x_n)\right)$,公式\eqref{eq:min-E-ADA}的$[2]$等式,找到新的分类器$g_t=h$之后,还需要找到最佳的$\eta$, \[ \min_\eta\widehat E_{ADA}=\sum_{n=1}^Nu_n^{(t)}\exp\left(-y_n\eta g_t(\mathbf x_n)\right), \] $\eta$越大步越好。最佳的$\eta_t$会比固定的$\eta$在短期内下降更快(greedily faster),在最优化中通常称为最速(最陡)下降(steepest descent)。对于分类正确和错误两种情形,$u_n^{(t)}\exp\left(-y_n\eta g_t(\mathbf x_n)\right)$分别为$u_n^{(t)}\exp(-\eta)$和$u_n^{(t)}\exp(+\eta)$,那么有 \[ \widehat E_{ADA}=\left(\sum_{n=1}^Nu_n^{(t)}\right)\cdot \left( (1-\epsilon_t)\exp(-\eta)+\epsilon_t\exp(+\eta) \right), \] $\epsilon_t$表示错误率。 通过${\partial\widehat E_{ADA}\over\partial\eta}=0$可得最速梯度步长$\eta_t=\ln\sqrt{1-\epsilon_t\over\epsilon_t}=\alpha_t$。当进行到$t+1$轮迭代时,误差为 \[ \widehat E_{ADA}^{(t+1)}=\widehat E_{ADA}^{(t)}\cdot\left( (1-\epsilon_t)\exp(-\eta_t)+\epsilon_t\exp(+\eta_t) \right), \] 将$\eta_t$和$\widehat E_{ADA}^{(1)}=\sum_{n=1}^Nu_n^{(1)}=1$带入可得 \[ \widehat E_{ADA}^{(t+1)}=\prod_{\tau=1}^{t}\left(2\sqrt{\epsilon_\tau(1-\epsilon_\tau)}\right)。 \] 由此可见,最糟糕的情况是当$\epsilon_t={1\over 2}$时(错误率$\epsilon_t$始终小于正确率$1-\epsilon_t$),$\widehat E_{ADA}^{(t+1)}$不减少,否则$\widehat E_{ADA}^{(t+1)}$随着迭代增加不断减少。

因此,AdaBoost是近似的函数梯度(functional gradient)最速下降法。

任意误差函数的梯度提升

AdaBoost可以表示为最优化的形式 \begin{equation} \min_\eta\min_h{1\over N}\sum_{n=1}^N\exp\left(-y_n\left(\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)+ \eta h(\mathbf x_n)\right)\right), \end{equation} 每一轮找到$h$作为$g_t$,并决定该$g_t$要前进的距离$\eta_t$。利用更一般的误差函数,将AdaBoost推广到GradientBoost \begin{equation} \min_\eta\min_h{1\over N}\sum_{n=1}^Nerr\left(\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)+ \eta h(\mathbf x_n),y_n\right)。 \end{equation} GradientBoost分为两步:(1)确定$h$;(2)确定$\eta$。由于要采用梯度下降法,需要平滑的误差函数$err$,$h$也不限于二分类,可以推广到实数输出。通过采用不同的误差函数$err$,GradientBoost可实现回归、soft分类等功能。

梯度提升决策树

对于回归问题,采用误差函数$err(s,y)=(s-y)^2$,令$s_n=\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)$可得 \begin{equation} \min_\eta\min_h{1\over N}\sum_{n=1}^N\left(s_n+ \eta h(\mathbf x_n)-y_n\right)^2, \label{eq:min-gradientboost-regression-Ein} \end{equation} 内层最小化 \[ \begin{aligned} \min_h\ldots &\overset{\mbox{taylor}}{\approx}\min_h\left({1\over N}\sum_{n=1}^N\underbrace{err(s_n,y_n)}_{\mbox{constant}}+{1\over N}\sum_{n=1}^N\eta h(\mathbf x_n)\left.{\partial err(s,y_n)\over\partial s}\right\rvert_{s=s_n}\right)\\ &\overset{\quad\quad}{=}\min_h\left(\mbox{constants}+{\eta\over N}\sum_{n=1}^N2h(\mathbf x_n)(s_n-y_n)\right)。 \end{aligned} \] 如果对$h$无约束条件,那么$h(\mathbf x_n)=-\infty\cdot(s_n-y_n)$时取最小值。事实上,只需要$h$的方向,$h$的大小(magnitude)通过步长$\eta$控制。利用拉格朗日乘子法的思想,避免求解复杂的约束优化问题,惩罚大的$h$ \[ \begin{aligned} &\min_h\left(\mbox{constants}+{\eta\over N}\sum_{n=1}^N\left(2h(\mathbf x_n)(s_n-y_n)+(h(\mathbf x_n))^2\right)\right)\\ \Longleftrightarrow&\min_h\left(\mbox{constants}+{\eta\over N}\sum_{n=1}^N\left(\mbox{constant}+(h(\mathbf x_n)-(y_n-s_n))^2\right)\right)。 \end{aligned} \] 去掉常数项,带惩罚的近似函数梯度是数据集$\{(\mathbf x_n,y_n-s_n)\}$上,基于平方误差的回归。$y_n-s_n$表示期望的值与目前能达到的值之间的差异,表示尚未达到的部分,称为余数(residual)。好的$h(\mathbf x_n)$需要弥补余数的差距。

[1/2]因此,GradientBoost的回归问题就是通过余数上的回归找到$g_t=h$。

当$g_t$确定后,继续\eqref{eq:min-gradientboost-regression-Ein}的外层最小化 \[ \min_\eta{1\over N}\sum_{n=1}^N(s_n+\eta g_t(\mathbf x_n)-y_n)^2\Leftrightarrow\min_\eta{1\over N}\sum_{n=1}^N((y_n-s_n)-\eta g_t(\mathbf x_n))^2, \] 这是单变量的线性回归,非常容易求解, \begin{equation} \eta={\sum_{n=1}^Ng_t(\mathbf x_n)(y_n-s_n)\over\sum_{n=1}^Ng_t^2(\mathbf x_n)}。 \label{eq:gbdt-eta} \end{equation}

[2/2]因此,GradientBoost的回归问题通过单变量回归求解最优作为步长$\alpha_t=\eta$。

梯度提升决策树(GBDT,gradient boosted decision tree)


初始化$s_1=s_2=\ldots=s_N=0$;

对于$t=1,2,\ldots,T$,循环执行:

  1. 利用$\mathcal A(\{(\mathbf x_n,y_n-s_n)\})$得到$g_t$,其中$\mathcal A$是基于平方误差的回归算法(例如C&RT);
  2. 利用\eqref{eq:gbdt-eta}更新步长$\alpha_t=\mbox{OneVarLinearRegression}(\{(g_t(\mathbf x_n),y_n-s_n)\})$;
  3. 更新$s_n\leftarrow s_n+\alpha_tg_t(\mathbf x_n)$;

返回$G(\mathbf x)=\sum_{t=1}^T\alpha_tg_t(\mathbf x)$。

GBDT就是AdaBoost决策树的回归版本。

参考文献

    脚注

    1. 其它误差界可参考线性分类模型的相关资料。 


    打赏作者


    上一篇:机器学习三原则     下一篇:分类器融合(6):融合模型总结