机器学习之提升方法

    提升(Boosting)是一种常用的统计学习方法，是一族将弱学习器提升为强学习器的算法，属于集成学习(ensemble)。

    Boosting方法通俗点理解就是“三个臭皮匠，顶个诸葛亮”。也就是所谓地将多个专家的判断进行综合所得出的判断，要比一个专家单独的判断要好。Boosting主要是通过分步迭代的方式构建模型，在迭代的每一步构建的弱学习器都是弥补了已有模型的不足。

写在模型之前

    机器学习之中的监督学习有几个重要的组成部分，可以初略地分为：模型(model)、参数(parameters)和目标函数(objective function)。

模型

    模型指定了对于给定的$x_i$如何去预测输出$y_i$。比如之前总结的线性模型(线性回归、Logistic回归)采用线性加权的方式进行预测得到$\hat y_i=\theta^T x_i$。对于线性回归来说线性模型的输出可以是连续值也可以通过sigmoid变换得到概率。

参数

    参数是需要学习的东西，在线性模型中，就是指系数$\theta$

目标函数

    模型和参数指定了给定输入如何做预测，但是并没有指明如何寻找较优的参数，所以每个模型都有一个目标函数，通过拟合训练数据，优化目标函数，进而可以求得参数。一般目标函数表示成下面两项：

$$Obj(\Theta)=L(\Theta)+\Omega(\Theta)$$

目标函数主要包含两项：损失函数和正则项。$L(\Theta)$可以称之为损失函数，用来衡量拟合训练数据的程度，比如说常见的平方误差等。$\Omega(\Theta)$可以称之为正则化项，用来衡量模型复杂程度的，比如说线性模型中常见的正则化项有$l2$正则和$l1$正则。损失函数鼓励我们建立的模型尽量拟合训练数据，最后用来预测的话会有比较小的偏差。而正则化项则鼓励更加简单的模型，当模型简单之后，不容易过拟合，使得模型具有泛化能力。

GBM

    基于梯度提升算法的学习器叫做GBM(gradient boosting machine)，通过集成(ensemble)多个弱学习器，通常基学习器是决策树(通常是CART树,不同于决策树，每一个叶子都会有具体的分数)，来构建最终的预测模型。
问题1：为什么基学习器倾向于决策树？
    决策树可以认为是if-then规则的集合，易于理解，解释性强，速度快；需要更少的特征工程(缺失值处理、不用特征标准化等)。但是单独使用决策树容易导致过拟合，但是可以通过抑制决策树的复杂性、降低单棵决策树的拟合能力，再通过梯度提升方法集合多个决策树，可以很好的解决这个问题。

GBDT概述

    Boosting Tree的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。

    为了消除残差，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boost中，每个新的模型的建立是为了使得之前模型的残差往梯度方向减少。

加法模型

    GBDT算法可以看成是由K棵树组成的加法模型：

$$\hat y_i=\sum_{k=1}^Kf_k(x_i),f_k\in F$$

以回归任务为例，F对应了所有回归树的集合，回归树可以将输入数据转化成一个score。加法模型实际上是直接学习决策树。该加法模型的目标函数可以定义为：

$$Obj=\sum_{i=1}^nl(y_i,\hat y_i)+\sum_{k=1}^K\Omega(f_k)$$

其中，$\Omega$表示决策树的复杂度，该如何定义树的复杂度呢？如何学习加法模型呢？

前向分步算法

    在优化目标函数之前，我们首先得知道树的参数是什么。使用CART树对样本进行分类或者是回归，是从根节点到叶节点的细化的逐步细化的过程，落在相同叶节点的样本的预测值是相同的。CART树的学习过程就是构造如何使用特征得到划分，从而得到score的过程。总之，一棵决策树的核心就是“树结构”和“叶节点的score”，那么我们要学习的$f_i$都包含树的结构以及叶子分数。一次性训练所有的树的结构以及树的分数并不是一件容易的事情。因此我们采用前向分布算法，即所谓的贪心法，每一步只学习一个树的结构和叶子分数，逐步逼近优化的目标，从而简化复杂度。具体地，我们从一个常量预测开始，每次学习一个新的树。其中$\hat y_i^{(t)}$表示步骤t的预测值：

$$\begin{align} \hat y_i^0&=0\\\\ \hat y_i^1&=f_1(x_i)=\hat y_i^0+f_1(x_i)\\\\ \hat y_i^2&=f_1(x_i)+f_2(x_i)=\hat y_i^1+f_2(x_i)\\\\ &……\\\\ \hat y_i^t&=\sum_{k=1}^tf_k(x_i)=\hat y_i^{t-1}+f_t(x_i) \end{align}$$

那么，如何决定每一步哪一棵树f被加入呢？选取标准还是最小化目标函数。
在第t步，模型对$x_i$的预测为：$\hat y_i^t=\hat y_i^{t-1}+f_t(x_i)$，其中$f_t(x_i)$为这一次我们要学习的树。目标函数可以写为：
\begin{equation}\begin{split} Obj(t)&=\sum_{i=1}^nl(y_i,\hat y_i^t)+\sum_{i=i}^t\Omega(f_i)\\\\
& =\sum_{i=1}^nl(y_i,\hat y_i^{t-1}+f_t(x_i))+\Omega(f_t)\\\\
\end{split}\tag{1}\end{equation}
举例说明，假设损失函数是均方误差，则目标函数可以表示为：
\begin{equation}\begin{split} Obj(t)&=\sum_{i=1}^nl(y_i-(\hat y_i^t))^2+\Omega(f_t)\\\\
& =\sum_{i=1}^n[2(\hat y_i^{t-1}-y_i)f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)+C\\\\
\end{split}\end{equation}
其中，$(\hat y_i^{t-1}-y_i)$称为残差，因此，使用平方损失函数时，GBDT算法的每一步在生成决策树时只需要拟合前面的模型的残差。
每一棵回归树都在学习前N-1棵树的残差。

GBDT的正则化

    为了防止GBDT过拟合，徐亚对其进行正则化。GBDT正则化的三种方式：

1. 加入和步长$\lambda$类似的正则项
   对于第t轮，我们将预测值可以表示为： $$\hat y_i^t=\sum_{k=1}^tf_k(x_i)=\hat y_i^{t-1}+f_t(x_i)$$ 加入正则项之后，变为： $$\hat y_i^t=\sum_{k=1}^tf_k(x_i)=\hat y_i^{t-1}+\lambda f_t(x_i)$$ $\lambda$取值介于0-1之间，对于同样的训练集效果，较小的步长一位置我们需要更多的弱学习器迭代次数。通常采用步长和迭代最大次数一起决定算法的拟合效果。
2. 子采样(subsample)
   这里提到的子采样和随机森林不一样，随机森林是有放回地抽样，这里是不放回地抽样。如果取值为1，则全部使用，等于没有使用子采样。若小于1，则表示只有有份样本会做GBDT的决策树拟合，防止过拟合。又是也会称之为随机梯度提升树。
3. 正则化剪枝
   剪枝包括预剪枝和后剪枝。在决策树有介绍。

GBDT(Gradient Boosting Decision Tree)主要就是利用梯度下降(Gradient descent)的想法应用在Boosting中，因为前向分布算法是一个残差逼近的过程，新学习的树需要让残差进一步下降。梯度提升算法主要是使残差沿着负梯度方向逐渐减少，逼近拟合值。

XGBoost

xgboost(eXtreme Gradient Boosting)是由陈天奇提出，可以说是GBDT的升级版。

目标函数

    目标函数和之前提到的一样，包括损失函数和正则项。目标函数同公式(1)。这里，为了表示一般情况，我们将公式(1)泰勒展开，近似得到我们原来的目标：
二阶泰勒展开公式:

$$f(x+\Delta x)\approx f(x)+f'(x)\Delta x+\frac12f''(x)\Delta x^2$$

定义：

$$g_i=\frac{\partial l(y_i,\hat y_i^{t-1})}{\partial \hat y_i^{t-1}},h_i=\frac{\partial^2 l(y_i,\hat y_i^{t-1})}{\partial^2 \hat y_i^{(t-1)}}$$

目标函数的二阶泰勒展开：

$$Obj(t)\approx \sum_{i=1}^n[l(y_i,\hat y_i^{t-1})+g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)+C$$

移除常数项，得：

$$\sum_{i=1}^n[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)$$

这个目标函数值依赖于每个数据点的在误差函数上的一阶导数和二阶导数。通过推导取探索出如何进行树的学习。树的复杂度如何定义。可以将树拆分成结构部分$q$和叶子score部分$\omega$。$q$把输入映射到叶子的索引号上面去，而$\omega$给定额每个索引号对应的叶子score是什么。用数学公式可以表示为：$f_t(x)=\omega_q(x)$举个例子，树的复杂度可一考虑叶子的节点数和叶子score,我么可以使用叶节点的综述和叶子score平方和的加权来表示树的复杂度。

$$\Omega(f_t)=\gamma T+\frac12\lambda\sum_{j=1}^Tw_j^2$$

其中，$\gamma$和$\lambda$是超参数，人为指定，$T$代表的树的叶子节点个数。
通过对公式进行进一步地整理，我们可以得到最终的目标函数可以表示为：
\begin{equation}\begin{split} Obj(t)&\approx \sum_{i=1}^n[l(y_i,\hat y_i^{t-1})+g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\gamma T+\frac12\lambda\sum_{j=1}^Tw_j^2+C\\\\
& =\sum_{i=1}^n[g_iw_{q(x_i)}+\frac12h_iw_{q{(x_i)}}^2]+\gamma·T+\frac12\lambda\sum_{j=1}^Tw_j^2+C\\\\
&=\sum_{j=1}^T[(\sum_{i \in I_j}g_i)w_j+\frac12(\sum_{i \in I_j}h_i)w_j^2]+\gamma·T+\frac12\lambda\sum_{j=1}^Tw_j^2+C\\\\
&=\sum_{j=1}^T[(\sum_{i \in I_j}g_i)w_j+\frac12(\sum_{i \in I_j}h_i+\lambda)w_j^2]+\gamma·T+C\\\\
\end{split}\end{equation}
进一步简化，令$G_j=\sum_{i \in I_j}g_i$,$H_j=\sum_{i \in I_j}h_i$，得：

$$Obj(t)=\sum_{j=1}^T[G_jw_j+\frac12(H_j+\lambda)w_j^2]+\gamma T$$

目标函数对$w_j$求偏导得：

$$\frac{\partial Obj(t)}{\partial w}=G_j+(H_j+\lambda)w_j \tag{2}$$

让公式(2)==0，得：$w_j=-\frac{G_j}{H_j+\lambda}$,并将该解带入回目标函数，得：

$$Obj(t)=-\frac12\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T$$

构造树结构

    根据上述推导，了解到如何评价一棵树的好坏，接下来我们将树进行分解，对于当前节点，如何对该节点进行划分，将该节点划分成两个子节点?借鉴决策树的做法，使用贪心法，枚举可行的分割点，选择增益最大的分割点进行划分,则节点划分之前和划分之后的目标函数之差表示为：

$$Gain=\frac12[\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$$

如果$Gain$比$\gamma$稍小，最好不要增加这个分支，达到预剪枝的一个效果。通过这种方式，不断构造各种分发的树，进而构造最佳的树。

Adaboost

    Adaboost(Adaptive Boosting)是通过改变训练数据的权重，将若干弱分类器组合成一个强分类器。Adaboost关于改变样本权重具体做法是提高那些前一轮被弱分类器错误分类的样本的权值，使得被分错的样本在当前轮能够受到更大的关注。关于将弱分类器组合问题，本质上是加权求和，具体地就是加大分类误差率下的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使得在表决中起较小的作用。

分类算法描述

设一个二分类训练数据集为：

$$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$$

每一个样本点由实例与标记组成,$y_i \in y={-1,+1}$

1. 初始化训练数据的权值分布 $$D_1=(w_{11},…,w_{1i},…,w_{1N}),w_{1i}=\frac1N,i=1,2,…,N$$
2. 对于$m=1,2,…,M$
   (1)使用具有权值分布$D_m$的训练数据集学习，得到基本分类器： $$G_m(x):x->{-1,1}$$ (2)计算$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)$$ (3)计算G_m(x)的系数： $$\alpha_m=\frac12log\frac{1-e_m}{e_m}$$ (4)更新数据集的权值分布： $$D_{m+1}=(w_{m+1,1},…,w_{m+1,i},…,w_{m+1,N})$$ $$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_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}$成为一个概率分布。
3. 构建基本分类器的线性组合 $$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$ 得到最终分类器： $$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$ 这一小节，主要是介绍弱学习器的权值公式以及样本权重更新公式。下一小节将通过目标函数来推导。

   目标函数

       Adaboost算法是模型为加法模型、损失函数是指数函数、学习算法为前向分布算法的二分类学习方法。

   误差函数

   第$m-1$轮和第$m$轮的弱学习器为： $$f_{m-1}=\sum_{i=1}^{m-1}\alpha_iG_i(x)$$ $$f_{m}=\sum_{i=1}^{m}\alpha_iG_i(x)=f_{m-1}(x)+\alpha_mG_m(x)\tag{3}$$ 公式(3)正式体现了强学习器为前向分布算法一步步得到的。损失函数为指数函数，定义损失函数为： $$(\alpha_m,G_m(x))=argmin\sum_{i=1}^Nexp[-y_i(f_{m-1}(x_i)+\alpha G_m(x_i))]$$ 令$w_{mi}’=exp(-y_if_{m-1}(x))$,该值不依赖于$\alpha,G$而改变，与最小化无关。但依赖于$f_{m-1}(x)$，随着每一轮迭代而发生改变。损失函数可以表示为： $$(\alpha_m,G_m(x))=argmin\sum_{i=1}^Nw_{mi}'exp[-y_i\alpha G_m(x_i)]$$ 求$G_m(x)$，对于任意的$\alpha \ge 0$,使得上式子最小的$G_m(x)$可以由下面得： $$G_m(x)=argmin\sum_{i=1}^mw_{mi}'I(y_i\neq G(x_i))$$ 将$G_m(x)$代入损失函数，并对$\alpha$进行求导，使其等于0，于是我们得到 $$\alpha_m=\frac12 log\frac{1-e_m}{e_m},e_m=\sum_{i=1}^N w_{mi}'I(y_i\neq G(x_i))$$ 由于$f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)$，以及$w_{mi}’=exp[-y_if_{m-1}(x_i)]$,样本更新权重可表示为： $$w_{m+1，i}'=w_{m,i}exp[-y_i\alpha_mG_m(x_i)]$$

正则项

    为了防止Adaboost过拟合，通常是会加入正则项，这个正则项通常称之为步长，之前在GBDT小节中提到的。

参考资料

李航,统计学习方法，清华大学出版社，2012
GBDT残差迭代
GBDT梯度迭代
GBDT算法深入解析
GBDT详细推导
陈天奇中文介绍XGboost