提升方法：GBDT , XGBOOST & AdaBoost

提升 (boosting) 方法是一种常用的统计学习方法，应用广泛且有效，在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类器性能。

• GBDT
  • 提升的概念
  • 提升算法
  • 梯度提升决策树 GBDT
• XGBOOST
• AdaBoost
  • 误差分析
• 参考文献

GBDT

我们知道随机森林的决策树分别采样建立, 相对独立。 那么引来了如下思考 :

• 假定当前一定得到了 \(m-1\) 颗决策树, 是否可以通过现有样本和决策树的信息, 对第 \(m\) 颗决策树的建立产生有益的影响呢 ?
• 各个决策树组成随机森林后, 最后的投票过程可否在建立决策树时即确定呢?

答案是肯定的，这也就是提升（boosting）的方法所解决的问题。

提升的概念

提升是一个机器学习技术, 可以用于回归和分类问题, 它每一步产生一个弱预测模型(如决策树), 并加权累加到总模型中，最终得带一个强预测模型; 如果每一步的弱预测模型生成都是依据损失函数的梯度方向, 则称之为梯度提升(Gradient boosting)。

提升的方法基于这样一个思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是“三个臭皮匠顶个诸葛亮”的道理。

梯度提升算法首先给定一个目标损失函数, 它的定义域是所有可行的弱函数集合(基函数); 提升算法通过迭代的选择一个负梯度方向上的基函数来逐渐逼近局部极小值。这种在函数域的梯度提升观点对机器学习的很多领域有深刻影响。

梯度提升算法实际上和梯度下降算法是一样的，只不过看问题的角度不同，比如在线性回归中，我们通过梯度下降来优化参数 \(\theta\) ，使损失函数能达到（局部）最小值；如果我们换个角度，我们优化的不是 \(\theta\)，而是 \(h_\theta(x) = \theta^T x\) 这个函数，再通过沿梯度方向下降的方法达到损失函数（局部）最小值，就变成了梯度提升算法。

提升算法

给定输入向量 \(x\) 和输出变量 \(y\) 组成的若干训练样本 \((x_1, y_1), (x_2,y_2),...,(x_n,y_n)\) , 目标是找到近似函数 \(F(x)\) , 使得损失函数 \(L(y,F(x))\) 的损失值最小。

损失函数 \(L(y,F(x))\) 的定义不唯一，典型定义有以下两种：

• \(L(y,F(x)) = \frac{1}{2}(y - F(x))^2\)，这个定义其实默认误差服从高斯分布
• \(L(y,F(x)) =| y - F(x) |\)，这个定义则认为误差服从Laplace（双指数）分布

假设最优解为 \(F^*(x)\)，则：

\[F^*(x) =\arg\min_F E(x, y)[L(y, F(x))]\]

该式的意思就是使损失函数期望风险最小化的参数 \(F(x)\) 为最优解 \(F^*(x)\)。

我们知道任何函数都可以被分解为一族基函数的线性组合，比如傅立叶分解可以把任何函数分解为三角函数的线性组合，所以这里的 \(F(x)\) 也不例外，我们假设它是一族基函数 \(f_i(x)\) 的线性组合，即： \[F(x) = \sum_{i=1}^M\gamma_if_i(x) + const\]

算法推导

我们使用梯度提升方法寻找最优解 \(F(x)\), 使得损失函数在训练集上的期望最小。方法如下:

• 首先, 令 \(f_0(x) = 1\)，求常系数 \(\gamma_0\) : \[F_0(x) =\gamma_0f_0(x) =\gamma_0 =\arg\min_\gamma\sum_{i=1}^n L(y_i,\gamma)\]

  • 若损失函数采用平方定义，上式可以解得：\(F_0(x) =\gamma =\frac{1}{n}\sum_{i=1}^ny_i\)
  • 若损失函数采用绝对值定义，则解 \(F_0(x)\) 为 \(y_1, y_2 ... y_n\) 的中位数
• 知道 \(F_0(x)\) 之后，接下来用递推的思路来想，如果已知 \(F_0(x), F_1(x) ... F_{m-1}(x)\) ，如何求 \(F_m(x)\) ？于是得到下面的公式： \[F_m(x) = F_{m-1}(x) + \arg \min_{f \in H} \sum_{i=1}^nL(y_i, F_{m-1}(x_i) + f(x_i))\]

• 我们可以用梯度下降的方法近似计算上式。若使 \(\sum_{i=1}^nL(y_i, F_{m-1}(x_i) + f(x_i))\) 取得最小值，我们可以对 \(f(x_i)\) 求偏导求出梯度，然后沿负梯度方向下降一个步长 \(\gamma_m\)，由于这个步长可以通过线性搜索求出最优值，所以该步长与负梯度的乘积可以近似为上式的最小值，于是得到如下的更新公式： \[F_m(x) = F_{m-1}(x) - \gamma_m \sum_{i=1}^n\nabla_fL(y_i, F_{m-1}(x_i))\]

提升算法

1. 初始给定模型为常数 \(F_0(x) = \arg \min_\gamma \sum_{i=1}^n L(y_i, \gamma)\)
2. 对于 \(m=1\) 到 \(M\)
   1. 计算伪残差 (pseudo residuals) \(r_{im} = [\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}]_{F(x) = F_{m-1}(x)}\) \(i = 1, 2 ... n\)
   2. 使用数据 \(\{(\overrightarrow{x_i}, r_{im})\}_{i=1}^n\) 训练拟合残差的基函数 \(f_m(x)\) （比如一棵决策树）
   3. 计算步长 $m = {i=1}^nL(y_i, F{m-1}(x_i) - f_m(x_i)) $
      • 一维优化问题
   4. 更新模型：\(F_m(x) = F_{m-1}(x) - \gamma_m \cdot f_m(x)\)

梯度提升决策树 GBDT

在提升算法中，如果基函数选择的是决策树，那么算法又叫梯度提升决策树，也就是GBDT。

GBDT

• 在第 \(m\) 步的梯度提升是根据伪残差数据计算决策树 \(t_m(x)\)。

• 令树 \(t_m(x)\) 的叶节点数目为 \(J\), 即树 \(t_m(x)\) 将输入空间划分为 \(J\) 个不相交区域\(R_{1m},R_{2m},...,R_{Jm}\) ,并且决策树 \(t_m(x)\) 可以在每个区域中给出某个类型的确定性预测。使用指示记号 \(I(x)\), 对于输入 \(x\), \(t_m(x)\) 为: \[t_m(x) = \sum_{j=1}^Jb_{jm}I(x \in R_{jm})\]

• 其中，\(b_{jm}\) 是样本 \(x\) 在区域 \(R_{jm}\) 的预测值，\[I(x) = \begin{cases} 1, & x == True \\ 0, & x == False \end{cases}\]

• 使用线性搜索计算学习率,最小化损失函树
  • \(F_m(x) = F_{m-1}(x) + \gamma_m \cdot t_m(x)\)
  • \(\gamma_m = \arg \min_\gamma\sum_{i=1}^nL(y_i, F_{m-1}(x_i) + \gamma_mt_m(x_i))\)
• 进一步：对树的每个区域分别计算步长，从而系数 \(b_{jm}\) 被合并到步长中，从而:
  • \(F_m(x) = F_{m-1}(x) + \sum_{j=1}^J\gamma_mI(x \in R_{jm})\)
  • \(\gamma_{jm} = \arg \min_\gamma\sum_{x_i \in R_{jm}}L(y_i, F_{m-1}(x_i) + \gamma_mt_m(x_i))\)

参数设置和正则化

对训练集拟合过高会降低模型的泛化能力, 需要使用正则化技术来降低过拟合。

• 对复杂模型增加惩罚项, 如 : 模型复杂度正比于叶结点数目或者叶结点预测值的平方和等
• 用决策树剪枝
• 叶结点数目控制了树的层数, 一般选择 \(4≤J≤8\)
• 叶结点包含的最少样本数目
  • 防止出现过小的叶结点, 降低预测方差
• 梯度提升迭代次数 \(M\) :
  • 增加 \(M\) 可降低训练集的损失值, 但有过拟合风险
  • 交叉验证

GBDT总结

• 函数估计本来被认为是在函数空间而非参数空间的数值优化问题，而阶段性的加性扩展和梯度下降手段将函数估计转换成参数估计。
• 损失函数是最小平方误差、绝对值误差等，则为回归问题；而误差函数换成多类别Logistic似然函数，则成为分类问题。
• 对目标函数分解成若干基函数的加权和，是常见的技术手段：神经网络、径向基函数、傅立叶/小波变换、SVM都可以看到它的影子。

XGBOOST

\[F_m(x)=F_{m-1}(x)+\arg\min_{f\in H}\sum_{i=1}^nL(y_i, F_{m-1}(x_i) + f(x_i))\]

普通提升算法包括GBDT在计算上式实采用的是梯度提升，也就是只用了一阶导数信息，如果常识二阶导数的信息呢？

目标函数：\(J(f_t) = \sum_{i=1}^nL(y_i, F_{m-1}(x_i) + f_t(x_i)) + \Omega(f_t) + C\) 其中，\(\Omega(f_t)\) 为正则项，\(C\) 为常数，目的是要求出使目标函数最小的 \(f_t\)。

二阶Taylor展式： \[f(x + \triangle x) = f(x) + f'(x)\triangle x + f''(x)\triangle x^2 + O(x^3)\]

令： \[g_i = \frac{\partial L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}, h_i = \frac{\partial^2 L(y_i, F_{m-1}(x_i))}{\partial F_{m-1}(x_i)}\]

对 \(J(f_t)\) 二阶Taylor展开并省略高阶无穷小得：

\[J(f_t) \approx \sum_{i=1}^n (L(y_i, F_{m-1}(x_i)) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)) + \Omega(f_t) + C\]

决策树的描述 * 使用决策树对样本做分类(回归)，是从根结点到叶节点的细化过程；落在相同叶节点的样本的预测值是相同的 * 假定某决策树的叶结点数目为 \(T\)，每个叶结点的权值为 \(\overrightarrow{w} = (w_1,w_2 ... w_T)\) ，决策树的学习过程，就是构造如何使用特征得到划分，从而得到这些权值的过程。叶权值就是这个叶节点的预测结果，若是分类问题，也就是这类样本的标签。 * 样本 \(x\) 落在叶结点 \(q\) 中，定义描述决策树函数为: \(f_t(x) = w_q(x)\) * 一个决策树的核心即“树结构”和“叶权值”

决策树的复杂度可考虑叶结点数和叶权值，如使用叶结点总数和叶权值平方和的加权： \[\Omega(f_t) = \gamma \cdot T_t + \lambda \cdot \frac{1}{2}\sum_{j=1}^Tw_j^2 \] 其中，\(T_t\) 为叶子的个数。

我们继续来推导目标函数 \(J(f_t)\)：

\[\begin{array}{lcl} J(f_t) = \sum_{i=1}^n [L(y_i, F_{m-1}(x_i)) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t) + C \\ \ \ \ \ \ \ \ = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+ \Omega(f_t) + C \\ \ \ \ \ \ \ \ =\sum_{i=1}^n[g_iw_q(x_i) + \frac{1}{2}h_iw_q^2(x_i)] + \gamma \cdot T_t + \lambda \cdot \frac{1}{2}\sum_{j=1}^Tw_j^2 + C \\ \ \ \ \ \ \ \ = \sum_{j=1}^T [(\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i)w_j^2] + \gamma \cdot T_t + \lambda \cdot \frac{1}{2}\sum_{j=1}^Tw_j^2 + C \\ \ \ \ \ \ \ \ = \sum_{j=1}^T[(\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\lambda + \sum_{i \in I_j}h_i)w_j^2] + \gamma \cdot T_t + C \end{array}\]

令 \(G_j = \sum_{i \in I_j}g_i\)，\(H_j = \sum_{i \in I_j}h_i\)，从而： \[J(f_t) = \sum_{j=1}^T[G_jw_j + \frac{1}{2}(\lambda + H_j)w_j^2] + \gamma \cdot T_t + C\]

对 \(w_j\) 求偏导得： \[\frac{\partial}{\partial w_j}J(f_t) = G_j + (\lambda + H_j)w_j\]

令 \(\frac{\partial J(f_t)}{\partial w_j} = 0\)，得： \[w_j = -\frac{G_j}{\lambda + H_j}\]

回代入目标函数得： \[J(f_t) = -\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{\lambda + H_j} + \gamma \cdot T_t\]

这就是目标函数最后的结果，值越小代表决策树的结构越好。

我们要构建一颗决策树 \(f_t\)，使目标函数 \(J(f_t)\) 达到最小，构建时可借鉴ID3/C4.5/CART的做法：

• 如何进行子树划分？
  • 对于某可行划分, 计算划分后的 \(J(f_t)\)
  • 对于所有可行划分, 选择 \(J(f_t)\) 降低最小的分割点
• 枚举可行的分割点, 选择增益最大的划分, 继续同样的操作, 直到满足某阈值或得到纯节点
  • \(Gain(\phi) = \frac{1}{2}[\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}]\)

XGBOOST总结

• XGBOOST 与 GBDT 的区别在于更新模型的方法不同，其余都是一样的
• 相对于传统的GBDT，XGBoost使用了二阶信息，可以更快的在训练集上收敛
• 由于“随机森林族”本身具备防止过拟合的优势，因此XGBoost仍然一定程度的具有该特性
• XGBoost的实现中使用了并行/多核计算, 因此训练速度快; 同时它的原生语言为C/C++, 这是它速度快的实践原因

AdaBoost

思考：如果对GBDT的基函数的学习中，不止考虑函数的参数和权值，而是对样本本身也加权，会得到什么结果呢？这其实就是Adaboost的思想。

AdaBoost算法

• 设训练数据集 \(T={(x_1,y_1), (x_2,y_2)...(x_N,y_N)}\)，初始化训练数据的权值分布 \(D_1 = (w_{11}, w_{12}, ..., w_{1i}, ...., w_{1N})\), \(w_{1i} = \frac{1}{N}\), \(i = 1, 2, ... N\)。

• 对于 \(m = 1, 2, ... M\)，\(M\) 为树的棵数:

  • 使用具有权值分布 \(D_m\) 的训练数据集学习, 得到基本分类器 \[G_m(x) : x \rightarrow \{-1, 1\}\]

  • 计算 \(G_m(x)\) 在训练数据集上的分类误差率: \[e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^Nw_{mi}I(G_m(x_i) \neq y_i)\]

  • 计算 \(G_m(x)\) 的系数 \[\alpha_m = \frac{1}{2}\log \frac{1-e_m}{e_m}\]

  • 更新训练数据集的权值分布 \[D_{m+1} = (w_{m+1, 1}, w_{m+1, 2}, ...., w_{m+1, i}, ..., w_{m+1, N})\] \[w_{m+1, i} = \frac{w_{mi}}{Z_m}\exp(-\alpha_m y_iG_m(x_i)), i = 1, 2, ... , N\]
  • 这里，\(Z_m\) 是归一化因子： \[Z_m = \sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i))\]

  • 它使 \(D_{m+1}\) 成为一个概率分布（和为1）。

• 构建基本分类器的线性组合 \[f(x) = \sum_{m=1}^M\alpha_mG_m(x)\]

• 得到最终分类器： \[G(x) = sign(f(x)) = sign(\sum_{m=1}^M\alpha_mG_m(x))\]

算法解释

我们先分析 \(G_m(x)\) 的系数：\(\alpha_m = \frac{1}{2}\log \frac{1-e_m}{e_m}\)，这里的 \(e_m\) 是分类错误率。 这个式子实现了这么一个理论：如果一个分类器的分类错误率超过50%，那么这个分类器还不如随机分类（默认均匀分布，随机分50%错误率）来得好，把这个分类器直接反转效果反而会更好。

• 如果 \(e_m < 0.5\)，则 \(1- e_m > 0.5\)，所以 \(\frac{1-e_m}{e_m} > 1\)，可以得到 \(\log\frac{1-e_m}{e_m} > 0\)，即：\(\alpha_m > 0\)，说明如果这个分类器的错误率小于0.5则权值为正，表示可以参考这个分类器的结果，并且错误率越低分类器的权值越大；
• 如果 \(e_m > 0.5\)，则 \(1- e_m < 0.5\)，所以 \(\frac{1-e_m}{e_m} < 1\)，可以得到 \(\log\frac{1-e_m}{e_m} < 0\)，即：\(\alpha_m < 0\)，就相当于把分类器反转。

再来看权值更新公式，\(w_{m+1, i} = \frac{w_{mi}}{Z_m}\exp(-\alpha_m y_iG_m(x_i)), i = 1, 2, ... , N\)

• 先看指数上的一小部分 : \(-\alpha_m y_iG_m(x_i)\)，其中 \(-\alpha_m\) 为该分类器的权值，\(y_i\) 为第 \(i\) 个样本的实际类别且 \(y_i \in \{-1, 1\}\)，\(G_m(x_i)\) 为预测类别。

  • 若预测类别与实际类别一致，则 \(y_iG_m(x_i) > 0\)，反之则 \(y_iG_m(x_i) < 0\)
  • 如果该分类器比较靠谱的话（\(e_m < 0.5\)），\(\alpha_m\) 是个正数，反之是个负数。
  • 综合起来看：如果靠谱的分类器预测错了（或者不靠谱的分类器预测对了），则 \(-\alpha_m y_iG_m(x_i) > 0\)，反之则 \(-\alpha_m y_iG_m(x_i) < 0\)

• \(Z_m\) 是用来归一化的，不用看，把其他部分合起来：

  • 如果 \(-\alpha_m y_iG_m(x_i) > 0\)，则 \(\exp(-\alpha_m y_iG_m(x_i)) > 1\)，进而得到 \(w_{m+1, i} = w_{mi} * 一个大于1的数\)，即权值增加。
  • 如果 \(-\alpha_m y_iG_m(x_i) < 0\)，则 \(\exp(-\alpha_m y_iG_m(x_i)) < 1\)，进而得到 \(w_{m+1, i} = w_{mi} * 一个小于1的数\)，即权值降低。

• 结论：如果分类器预测错了则增加该样本的权值，在下次分类时重点关注该样本；如果分类正确则降低该样本的权值，在下次分类时弱化该样本。也就是样本的权值动态变化，如下图所示：

误差分析

AdaBoost算法最终的误差界为：

\[\frac{1}{N}\sum_{i=1}^NI(G_m(x_i) \neq y_i) \leqslant \frac{1}{N}exp(-y_if(x_i)) = \prod_mZ_m\]

证明

• 前半部分：当 \(G(x_i) \neq y_i\) 时，\(y_if(x_i) < 0\)，因而 \(exp(-y_if(x_i)) \geqslant 1\)，而 \(\frac{1}{N}\sum_{i=1}^NI(G_m(x_i) \neq y_i) \leqslant 1\)，所以 \(\frac{1}{N}\sum_{i=1}^NI(G_m(x_i) \neq y_i) \leqslant \frac{1}{N}exp(-y_if(x_i))\)，前半部分得证。
  
• 后半部分：

  • 由 \(Z_m\) 的定义式得：\(w_{mi}exp(-\alpha_my_iG_m(x_i)) = Z_mw_{m+1,i}\) \[\begin{array}{lcl} \frac{1}{N}exp(-y_if(x_i)) \\ = \frac{1}{N}\sum_i\exp(- \sum_{m=1}^M\alpha_my_iG_m(x_i)) \\ = \sum_iw_{1i}\prod_{m=1}^M\exp(-\alpha_my_iG_m(x_i)) \\ = Z_1\sum_i w_{2,1}\prod_{m=2}^M\exp(-\alpha_my_iG_m(x_i)) \\ = Z_1Z_2\sum_i w_{3,1}\prod_{m=3}^M\exp(-\alpha_my_iG_m(x_i)) \\ = .... \\ = Z_1Z_2...Z_{M-1}\sum_i w_{M,1}\exp(-\alpha_my_iG_m(x_i)) \\ = \prod_{m=1}^MZ_m \end{array}\]

  • 后半部分得证

这一结果说明，可以在每一轮选取适当的 \(G_m\) 使得 \(Z_m\) 最小，从而使训练误差下降最快。

训练误差界

\[\begin{array}{lcl} Z_m = \sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i)) \\ \ \ \ \ \ = \sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha_m} + \sum_{y_i\neq G_m(x_i)}w_{mi}e^{\alpha_m} \end{array}\]

因为 \(\alpha_m = \frac{1}{2}\log\frac{1-e_m}{e_m}\)，\(\sum_{y_i=G_m(x_i)}w_{mi} = 1 - e_m\)，\(\sum_{y_i\neq G_m(x_i)}w_{mi} = e_m\) 所以 \[\begin{array}{lcl} Z_m = (1- e_m)e^{-\alpha_m} + e_me^{\alpha_m} \\ \ \ \ \ \ = 2\sqrt{e_m(1-e_m)} \\ \ \ \ \ \ = \sqrt{1-4\gamma_m^2} \end{array}\] 其中，\(\gamma_m = \frac{1}{2} - e_m\)。

由此得到： \[\prod_{m=1}^MZ_m = \prod_{m=1}^M \sqrt{1-4\gamma_m^2} \leqslant \exp(-2\sum_{m=1}^M\gamma_m^2)\]

取 \(\gamma_1, \gamma_2....\) 的最小值，记为 \(\gamma\)， 则有： \[\frac{1}{N}\sum_{i=1}^NI(G_m(x_i) \neq y_i) \leqslant \exp(-2M\gamma^2)\]

这表明AdaBoost训练误差是以指数速率下降的！

AdaBoost总结

• AdaBoost算法可以看做是采用指数损失函数的提升方法，其每个基函数的学习算法为前向分步算法
• AdaBoost的训练误差是以指数速率下降的
• AdaBoost算法不需要事先知道下界 \(\gamma\)，具有自适应性(Adaptive)，它能自适应弱分类器的训练误差率

参考文献

• 李航，统计学习方法，清华大学出版社，2012
• Jerome H. Friedman. Greedy Function Approximation: A Gradient Boosting Machine. February 1999