集成学习之Boosting

集成学习ensemble learning 又叫集成模型、模型融合、多分类器系统、基于委员会的学习，是KDD CUP、Kaggle等竞赛的神器。简单说，通过构建并结合多个学习器来完成学习任务。

• 分类：

• 个体学习器强依赖关系，串行生成的序列化方法，Boosting

  • 代表方法：AdaBoost、GBDT、XGBoost
  • 关注：降低偏差

• 个体学习器非强依赖，同时生成的并行化方法，Bagging

  • 代表方法：RF（随机森林）
  • 关注：降低方差

本篇短文只介绍集成学习的Boosting方法。其中，GBM（Gradient Boosting Machine），或称为Boosted Tree、GBDT、GBRT或LambdaMART等，指利用梯度提升方法的树结构算法。XGBoost全称是 eXtreme Gradient Boosting（极限梯度提升）。它是 GBM的一个c++ 实现，作者为正在华盛顿大学研究机器学习的大牛陈天奇，毕业于上海交通大学ACM班，从事大规模机器学习研究。XGBoost的改进是一点一滴来的，是一篇篇论文的积累，很多方法并非XGBoost第一次提出，可以说XGBoost把算法和系统实现都做得淋漓尽致。

参考资料/推荐读物

• Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In 22nd SIGKDD Conference on Knowledge Discovery and Data Mining, 2016
• Friedman J H. Greedy Function Approximation: A Gradient Boosting Machine[J]. Annals of Statistics, 2001, 29(5):1189-1232.
• Github: dmlc/xgboost
• Zhou Z H. Ensemble Methods: Foundations and Algorithms[M]. Taylor & Francis, 2012.
• 周志华. 机器学习 : = Machine learning[M]. 清华大学出版社, 2016.
• XGBoost originates from research project at University of Washington, see also the Project Page at UW.

【目录】

泰勒公式

泰勒公式，通俗来讲是"用多项式函数去逼近光滑函数"。在实际应用中，当我们对精度的要求并不太高的时候可以截断多项式函数，从而获得某点附近取值的估计。常用来求近似值、误差估计、建立数值计算格式等等。在本篇中，梯度下降法和牛顿法都利用了泰勒展开。

• 定义：泰勒公式是一个用函数在某点的信息描述其附近取值的公式。局部有效性
• 基本形式： $$f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(x_{0})}{n!}(x-x_{0})^{n}$$
• 一阶泰勒展开： $$f(x)\approx f(x_{0})+f'(x_{0})(x-x_{0})$$
• 二阶泰勒展开： $$f(x)\approx f(x_{0})+f'(x_{0})(x-x_{0})+f''(x_{0})\frac {(x-x_{0})^{2}}{2}$$
• 迭代形式：假设$x^{t}=x^{t-1}+\Delta x$，将$f(x^{t})$在$x^{t-1}$处进行泰勒展开： $$f(x^{t})=f(x^{t-1}+\Delta x)\approx f(x^{t-1})+f'(x^{t-1})\Delta x+f''(x^{t-1})\frac{\Delta x^{2}}{2}$$

梯度下降法（Gradient Descend Method）

在机器学习任务中，需要最小化损失函数$L(\theta)$，其中是要求解的模型参数$\theta$。梯度下降法常用来求解这种无约束最优化问题，它是一种迭代方法：选取初值$\theta^{0}$，不断迭代，更新$\theta$的值，进行损失函数的极小化。

• 迭代公式：$\theta^{t}=\theta^{t-1}+\Delta\theta$
• 将$L(\theta^{t})$在$\theta^{t-1}$处进行一阶泰勒展开： $$L(\theta^{t})=L(\theta^{t-1}+\Delta\theta)\approx L(\theta^{t-1})+L'(\theta^{t-1})\Delta\theta$$
• 要使得$L(\theta^{t})<L(\theta^{t-1})$，可取$\Delta\theta=-\alpha L'(\theta^{t-1})$，则：$\theta^{t}=\theta^{t-1}-\alpha L'(\theta^{t-1})$
• 这里的$\alpha$是步长，可通过线性搜索确定，但一般直接赋值一个很小的数

牛顿法（Newton's Method）

牛顿法同梯度下降类似，也是一种最优化方法，并且，与梯度下降法相比，牛顿法利用了泰勒二阶展开。

• 将$L(\theta^{t})$在$\theta^{t-1}$处进行二阶泰勒展开： $$L(\theta^{t})\approx L(\theta^{t-1})+L'(\theta^{t-1})\Delta\theta+L''(\theta^{t-1})\frac{\Delta\theta^{2}}{2}$$
• 为了简化分析过程，假设参数是标量（即$\theta$只有一维），则可将一阶和二阶导数分别记为g 和h： $$L(\theta^{t})\approx L(\theta^{t-1})+g\Delta\theta+h\frac{\Delta\theta^{2}}{2}$$
• 要使得$L(\theta^{t})$极小，即让 $$g\Delta\theta+h\frac{\Delta\theta^{2}}{2}$$ 极小，可令 $$\frac{\partial(g\Delta\theta+h\frac{\Delta\theta^{2}}{2})}{\partial\Delta\theta}=0$$
• 求得 $$\Delta\theta=-\frac{g}{h}$$ ，故 $$\theta^{t}=\theta^{t-1}+\Delta\theta=\theta^{t-1}-\frac{g}{h}$$
• 参数$\theta$推广到向量形式，迭代公式：$\theta^{t}=\theta^{t-1}-H^{-1}g$，这里H是海森矩阵

从参数空间到函数空间

• Boosted Tree在函数空间中利用梯度下降法进行优化
• XGBoost在函数空间中用牛顿法进行优化

从梯度下降到梯度提升（GBM）

在函数空间，某些函数是做不到梯度下降的，例如，树结构的算法在函数空间上实质是分段函数。因此，需要借用梯度下降的思想，产生了梯度提升算法。

• 梯度下降是参数空间

  • $\theta^{t}=\theta^{t-1}+\theta_{t}$，$\theta_{t}$表示第t次迭代的参数增量
  • $\theta_{t}=-\alpha_{t}g_{t}$，其中，g为一阶导数，$\alpha$为步长，参数更新方向为负梯度方向
  • $$\theta=\sum_{t=0}^{T}\theta_{t}$$ ，最终参数等于每次迭代的增量的累加和
  • $\theta_{0}$是初值

• 梯度提升是函数空间

  • $f^{t}=f^{t-1}+f_{t}$，$f_{t}$表示第t次迭代的函数增量
  • $f_{t}=-\alpha_{t}g_{t}(x)$，其中，g为一阶导数，$\alpha$为步长，拟合为负梯度方向
  • $$F(x)=\sum_{t=0}^{T}f_{t}(x)$$ ，最终函数等于每次迭代的增量的累加和
  • $f_{0}(x)$是模型初始值，通常为常数

从牛顿方法到牛顿提升（XGBoost）

借鉴梯度提升算法，XGBoost的核心是利用牛顿方法在参数空间转换到函数空间。

• 牛顿方法是参数空间

  • $\theta^{t}=\theta^{t-1}+\theta_{t}$，$\theta_{t}$表示第t次迭代的参数增量
  • $\theta_{t}=-H_{t}^{-1}g_{t}$，其中，g为一阶导数，H为海森矩阵，参数更新方向为负梯度方向
  • $$\theta=\sum_{t=0}^{T}\theta_{t}$$ ，最终参数等于每次迭代的增量的累加和
  • $\theta_{0}$是初值

• 牛顿提升是函数空间

  • $f^{t}=f^{t-1}+f_{t}$，$f_{t}$表示第t次迭代的函数增量
  • $$f_{t}=-\frac{g_{t}(x)}{h_{t}(x)}$$ ，其中，g为一阶导数，h为二阶导数，拟合为负梯度方向
  • $$F(x)=\sum_{t=0}^{T}f_{t}(x)$$ ，最终函数等于每次迭代的增量的累加和
  • $f_{0}(x)$是模型初始值，通常为常数

Boosting算法

综上所述，Boosting 算法是一种加法模型（additive training），模型公式： $$F(x)=\sum_{t=0}^{T}f_{t}(x)$$ ，其基分类器常采用回归树[Friedman 1999]和逻辑回归[Friedman 2000]。

• 树模型有以下优缺点：

  • 可解释性强
  • 可处理混合类型特征
  • 具体伸缩不变性（不用归一化特征）
  • 有特征组合的作用
  • 可自然地处理缺失值
  • 对异常点鲁棒
  • 有特征选择作用
  • 可扩展性强，容易并行
  • 缺乏平滑性（回归预测时输出值只能输出有限的若干种数值）
  • 不适合处理高维稀疏数据

接下来，我们从CART最基本的回归树开始介绍，从而到GBDT和XGBoost

CART分类回归树

CART回归树，也叫分类回归树（Classification and regression tree），与决策树不同的是，在每个叶子节点包含一个分数。

• 监督学习的算法构成：模型，参数 和 目标函数

  • 模型和参数

    • 模型指给定输入xi如何去预测输出 yi。我们比较常见的模型如线性模型（包括线性回归和logistic regression）采用了线性叠加的方式进行预测
    • $\hat{y}_{j}=\sum\omega_{j} x_{i,j}$
    • 其实这里的预测y可以有不同的解释，比如我们可以用它来作为回归目标的输出，或者进行sigmoid 变换得到概率，或者作为排序的指标等。而一个线性模型根据y的解释不同（以及设计对应的目标函数）用到回归，分类或排序等场景。
    • 参数指我们需要学习的东西，在线性模型中，参数指我们的线性系数w。

  • 目标函数：损失和正则

    • 监督学习通用目标函数： $$Obj(\Theta)=L(\Theta)+\Omega(\Theta)$$
    • $L(\Theta)$：训练损失，测量模型拟合数据的程度
    • $\Omega(\Theta)$：正则化，策略模型的复杂度
    • 这样目标函数的设计来自于统计学习里面的一个重要概念叫做Bias-variance tradeoff。
    • Bias可以理解为假设我们有无限多数据的时候，可以训练出最好的模型所拿到的误差。而Variance是因为我们只有有限数据，其中随机性带来的误差。
    • 目标中误差函数鼓励我们的模型尽量去拟合训练数据，这样相对来说最后的模型会有比较少的 bias。而正则化项则鼓励更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。

  • 优化算法

• CART实例

  首先是模型。Boosted tree 最基本的组成部分叫做回归树(regression tree)，也叫做CART

  

  CART会把输入根据输入的属性分配到各个叶子节点，而每个叶子节点上面都会对应一个实数分数。上面的例子是一个预测一个人是否会喜欢电脑游戏的 CART，你可以把叶子的分数理解为有多可能这个人喜欢电脑游戏。有人可能会问它和decision tree的关系，其实我们可以简单地把它理解为decision tree的一个扩展。从简单的类标到分数之后，我们可以做很多事情，如概率预测，排序。

  然后是目标函数：CART设定目标函数之后，会通过优化算法进行优化。下图以单变量CART为例展示了目标函数的优化过程。

• CART融合

  一个CART往往过于简单无法有效地预测，因此一个更加强力的模型叫做tree ensemble。

  

  我们用两棵树来进行预测。我们对于每个样本的预测结果就是每棵树预测分数的和。到这里，我们的模型就介绍完毕了。现在问题来了，我们常见的随机森林和boosted tree和tree ensemble有什么关系呢？如果你仔细的思考，你会发现RF和boosted tree的模型都是tree ensemble，只是构造（学习）模型参数的方法不同。第二个问题：在这个模型中的“参数”是什么。在tree ensemble中，参数对应了树的结构，以及每个叶子节点上面的预测分数。

• 树融合方法

  • 广泛应用于GBM（梯度提升方法）、RF（随机森林）中
  • 具体伸缩不变性，不用归一化特征
  • 可以学习到特征之间的高阶交互
  • 可以规模化，在工业中广泛应用

GBDT算法原理

Friedman J H. Greedy Function Approximation: A Gradient Boosting Machine[J]. Annals of Statistics, 2001, 29(5):1189-1232.

Friedman于论文” Greedy Function Approximation…”中最早提出GBDT，其模型F定义为加法模型：

其中，x是输入样本，h是分类回归树（CART），w是分类回归树参数，$\alpha$是每棵树的权重。

通过最小化损失函数求解最优模型： $$F^{*}=arg_{F}min\sum_{i=0}^{N}L(y_{i},F(x_{i};w))$$

• 具体算法 输入： $$(x_{i},y_{i})$$ ，T，L

  1. 初始化$f_{0}$

  2. for t=1 to T do

     1. 计算响应： $$y_{i}=-[\frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}]_{F(x)=F_{t-1}(x)}$$ ，i=1,2,...N
     2. 学习第t棵树： $$w^{*}=arg_{w}min\sum_{i=1}^{N}(y_{i}-h_{t}(x_{i};w))^{2}$$
     3. 线性搜索找步长： $$\rho^{*}=arg_{\rho}min\sum_{i=1}^{N}L(y_{i},F_{t-1}(x_{i})+\rho h_{t}(x_{i};w^{*}))$$
     4. 令$f_{t}=\rho^{*}h_{t}(x;w^{*})$，更新模型：$F_{t}=F_{t-1}+f_{t}$

  输出：$F_{T}$

XGBoost算法原理

Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In 22nd SIGKDD Conference on Knowledge Discovery and Data Mining, 2016

XGBoost先是在Github上公开使用，后来由陈天奇写论文公开。

• 自适应的学习（Boosting）：

  • $$\hat{y}_{i}^{(0)}=0$$ ， $$\hat{y}_{i}^{1}=\hat{y}_{i}^{0}+f_{1}(x_{i})$$ ， $$\hat{y}_{i}^{2}=\hat{y}_{i}^{1}+f_{2}(x_{i})$$ ， $$\hat{y}_{i}^{t}=\hat{y}_{t-1}^{0}+f_{t}(x_{i})$$
  • $$\hat{y}_{i}^{t}=\sum_{k=1}^{t}f_{t}(x_{i})$$

• 设定目标函数：

  • $$obj^{(t)}=\sum_{i=1}^{n}l(y_{i},\hat{y}^{t}_{i})+\sum_{i=1}^{n}\Omega(f_{i})=\sum_{i=1}^{n}l(y_{i},\hat{y}^{t-1}_{i}+f_{t}(x_{i}))+\Omega(f_{t})$$
  • 泰勒展开： $$f(x^{t})=f(x^{t-1}+\Delta x)\approx f(x^{t-1})+f'(x^{t-1})\Delta x+f''(x^{t-1})\frac{\Delta x^{2}}{2}$$
  • 因此： $$obj^{(t)}=\sum_{i=1}^{n}[l(y_{i},\hat{y}^{t-1}_{i})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t})$$
  • 例子： $$obj^{(t)}=\sum_{i=1}^{n}(y_{i}-(\hat{y}^{t-1}_{i}+f_{t}(x_{i})))^{2}+\Omega(f_{t})=\sum_{i=1}^{n}(2(\hat{y}^{t-1}_{i}-y_{i})f_{t}(x_{i})+f_{t}(x_{i})^{2})+\Omega(f_{t})$$

• 模型函数： $$obj(x)=\sum_{i=1}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t})$$ ，其中， $$g_{i}=\frac{\partial L(y_{i},\hat{y}^{t-1})}{\partial\hat{y}^{t-1}}$$ ， $$h_{i}=\frac{\partial^{2} L(y_{i},\hat{y}^{t-1})}{\partial^{2}\hat{y}^{t-1}}$$

• 基学习器定义： $$f_{t}(x)=\omega_{q(x)}$$ ，$\omega$表示一棵树中叶子的权重，q表示一棵树的结构，T表示每棵树叶子的节点数

• 启发式复杂度定义： $$\Omega(f_{t})=\gamma T+\frac{1}{2}\sum_{j=1}^{T}\omega_{j}^{2}$$ ，由叶子节点数目和L2正则项组成

  • 为什么要用L2正则？Boosting算法容易过拟合

• 某个叶子的目标函数：假设：$I_{j}=\{i|q(x_{i})=j\}$为叶子j中包含的所有实例

• 定义：$G_{j}=\sum_{i\in I_{j}}g_{i}$，$H_{j}=\sum_{i\in I_{j}}h_{i}$

• 假设： $$\omega_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda}$$ ，则 $$obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T$$
• 利用obj作为树结构分数评估

• 枚举所有不同树结构的贪心法

所以我们的算法也很简单，我们不断地枚举不同树的结构，利用这个打分函数来寻找出一个最优结构的树，加入到我们的模型中，再重复这样的操作。不过枚举所有树结构这个操作不太可行，所以常用的方法是贪心法，每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算

对于每次扩展，我们还是要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？我假设我们要枚举所有 x<a 这样的条件，对于某个特定的分割a我们要计算a左边和右边的导数和。

我们可以发现对于所有的a，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL和GR。然后用上面的公式计算每个分割方案的分数就可以了。