机器学习 | 从加法模型讲到GBDT算法

作者：JSong, 日期：2017.10.10

集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务，常可获得比单一学习器显著优越的泛化性能，这对“弱学习器”尤为明显。

目前，有三种常见的集成学习框架：bagging，boosting和stacking。第一种是并行的，各个基学习器之间不存在强依赖关系，代表是随机森林算法。后两者是串行的，基学习器之间存在强依赖关系，必须串行生成。具体可参见我的文章机器学习|集成学习。

1、前向分步算法（forward stagewise algorithm）

考虑加法模型

\[f(x)=\sum_{i=m}^{M} \beta_{m}b(x;\gamma_m)
\]

其中, \(b(x;\gamma_{m}),\,\beta_{m}\) 分别为基函数和基函数的系数。

在给定训练数据及损失函数 \(L(y,f(x))\) 的条件下，学习加法模型成为一个极小化问题：

\[\arg_{\beta_{m},\gamma_{m}}\min\sum_{i=1}^{N}L(y_i,\sum_{m=1}^{M}\beta_{m}b(x_i;\gamma_{m}))
\]

这是一种典型的加法模型，令

\[f_m(x)=\sum_{i=1}^{m}\beta_{i}b(x;\gamma_{i})
\]

当M=m时，代入上面的式子可得

\[(\beta_{m},\gamma_{m})=\arg_{\beta,\gamma}\min\sum_{i=1}^{N}L(y_i,f_{m-1}(x)+\beta\,b(x;\gamma))
\]

即我们可以通过构造迭代把求解所有参数的问题简化为逐次求解每一对参数的问题（这是一种贪婪的算法）。

算法（前向分步算法）：

(1). 初始化\(f_{0}(x)=0\);

(2). 对m=1,2,...M

(a). 极小化损失函数：

\[(\beta_{m},\gamma_{m})=\arg_{\beta_{m},\gamma_{m}}\min\sum_{i=1}^{N}L\left(y_i,f_{m-1}(x)+\beta_{m}b(x_i;\gamma_{m})\right)
\]

得到参数 \(\beta_m,\,\gamma_m\)

(b). 更新：

\[f_{m}(x)=f_{m-1}(x)+\beta_{m}b(x;\gamma_{m})
\]

(3). 得到加法模型

\[f(x)=f_{M}(x)=\sum_{i=m}^{M} \beta_{m}b(x;\gamma_m)
\]

2、AdaBoost算法

前向分布算法是一种算法的框架，接下来我们对于二分类问题构造一个具体的boosting算法。

考虑二分类问题，令 \(y\in \{-1,1\}\) ,在逻辑回归模型中，对应的损失函数是log(1+exp(-yf(x))), 这里我们用x近似log(1+x)，选取一个简单的指数损失函数：

\[L(y,f(x))=\exp[-yf(x)]
\]

同时规定所有的基函数满足 \(b(x;\gamma)\in \{-1,1\}\) ,利用前向分布算法，我们每一步需要极小化损失函数：

\[\begin{align}
L_{m}(\beta,\gamma)&=\sum_{i=1}^{N}\exp[-y_{i}(f_{m-1}(x_i)+\beta_{}b(x_i;\gamma_{}))]\\
&=\sum_{i=1}^{N}\exp[-y_{i}f_{m-1}(x_i)]\cdot\exp[-y_{i}\beta_{}\cdot\,b(x_i;\gamma_{})]\\
&=\sum_{i=1}^{N}\bar{w}_{mi}\exp[-y_{i}\beta_{}\cdot\,b(x_i;\gamma_{})]
\end{align}
\]

其中 \(\bar{w}_{mi}=\exp[-y_{i}f_{m-1}(x_i)]\) ,其与 \(\gamma\) 和 \(\beta\) 都无关，所以不影响到上述的极小化。

在上述这个损失函数中，两个参数之间存在耦合项，在不确定b的形式时无法用导数求极值。考虑到b只能取值1和-1，继续简化上述损失函数可得：

\[L_{m}(\beta,\gamma)=(e^{\beta}-e^{-\beta})\sum_{i=1}^{N}\bar{w}_{mi}\mathcal{I}(b(x_i;\gamma)\neq_{}y_{i})+e^{-\beta}\sum_{i=1}^{N}\bar{w}_{mi}
\]

在这个式子中，两个参数实现了分离，计算它的梯度会发现，其等价于两个极小化问题。首先求解极小化问题：

\[\gamma_{m}=\arg_{\gamma}\min\sum_{i=1}^{N}\bar{w}_{mi}\mathcal{I}(b(x_i;\gamma)\neq_{}y_{i})
\]

带入损失函数中，再利用导数求解参数 \(\beta\) 的值：

\[\frac{dL_{m}(\beta,\gamma_{m})}{d\beta}=[e_{m}+(1-e_m)e^{-2\beta}]\cdot_{}e^{\beta}\sum_{i=1}^{N}\bar{w}_{mi}
\]

其中

\[e_{m}=\frac{\sum_{i=1}^{N}\bar{w}_{mi}\mathcal{I}(b(x_i;\gamma_m)\neq_{}y_{i})}{\sum_{i=1}^{N}\bar{w}_{mi}}=\sum_{i=1}^{N}w_{mi}\mathcal{I}(b(x_i;\gamma_m)\neq_{}y_{i})
\]

\[w_{mi}=\frac{\bar{w}_{mi}}{\sum_{i=1}^{N}\bar{w}_{mi}}
\]

求解导数值可得

\[\beta_m=\frac{1}{2}\ln\frac{1-e_{m}}{e_{m}}
\]

注：此时的 \(e_{m}\) 与 \(\gamma_{m}\) 的极小化函数完全等价，又注意到 \(w_{mi}\) 和为1,所以不妨把 \(\gamma_{m}\) 的极小化函数修改为 \(e_m\), 这个意义下 \(e_m\) 即是基函数的分类误差率。

注意到，这个时候事实上并不需要参数 \(\gamma\) 的显示存在，其隐形的存在于每个基函数的训练时使用的损失函数中，更进一步，其代表了每个样本的权重。通俗点讲，算法在串行迭代过程中，那些分类不准确的样本点在下一步的基分类模型中是会被重点照顾。

最后我们把上述过程整理成Adaboost算法

算法（Adaboost算法）：

(1). 初始化训练数据的权值分布

\[D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N}),\,\,w_{1i}=\frac{1}{N}
\]

(2). 对m=1,2,...M

( a ). 使用具有权值分布 \(D_{m}\) 的训练数据集学习，得到基本分类器

\[G_{m}(x): X \rightarrow\{-1,1\}
\]

\[G_{m}(x)=\arg_{G(x)}\min\sum_{i=1}^{N}w_{mi}\mathcal{I}(G(x_i)\neq_{}y_{i})
\]

( b ). 计算 \(G_{m}(x)\) 在训练数据集上的分类误差率

\[e_{m}=Pr(G_{m}(x_i)\neq_{}y_{i})=\sum_{i=1}^{N}w_{mi}\mathcal{I}(G(x_i)\neq_{}y_{i})
\]

( c ). 计算 \(G_{m}(x)\) 的系数

\[\alpha_{m}=\frac{1}{2}\ln\frac{1-e_m}{e_m}
\]

( d ). 更新训练数据集的权值分布

\[D_{m+1}=(w_{m+1,1},\cdots,w_{m+1,i},\cdots,w_{m+1,N})
\]

\[w_{m+1,i}=\frac{w_{mi}\exp(-\alpha_{m}y_{i}G_{m}(x_i))}{Z_m}
\]

这里 \(Z_m\) 是规范化因子，它使得 \(\sum_{i}w_{m+1,i}=1\)

(3). 构建基本分类器的线性组合

\[f(x)=\sum_{m=1}^{M}\alpha_{m}G_{m}(x)
\]

得到最终分类器

\[G(x)=sign(f(x))=sign\left(\sum_{i=m}^{M}\alpha_{m}G_{m}(x)\right)
\]

一些注释

1、\(\alpha_m\) 表示 \(G_{m}(x)\) 在最终分类器中的重要性（和并不为1），当 \(e_m\) 不大于 1/2 时， \(\alpha_m\) 非负，且随着 \(e_m\) 的减小而增大，即分类误差率越小的基础分类器越重要。

2、训练集数据的权值分布可以写成：

\[w_{m+1,i}=\left\{\begin{align}
\frac{w_{mi}}{Z_m}e^{-\alpha_m},&\,&G_{m}(x_i)=y_i\\
\frac{w_{mi}}{Z_m}e^{\alpha_m},&\,&G_{m}(x_i)\neq_{}y_i
\end{align}\right.\]

由此可知，被基础分类器误分类样本权值得以扩大，而被正确分类样本权值得以缩小，且这个缩放的倍数是指数级别的。通过不断改变训练数据的权值分布，使得训练数据在每个基础分类器的训练中起到不同的作用，同时也使得模型的方差得以降低（过拟合）。

3、Friedman指出Adaboost事实上是基于逻辑回归的加法模型。

在上面的这些论述，我们从从损失函数出发推导出Adaboost算法的，指数损失函数在Adaboost算法中有很重要的作用，但它不是Adaboost算法核心的思想。Adaboost算法最大的魅力在于它在给样本分配权重，那根据这个思路，即只限定到Adaboost算法的第(2)(b)步,看看我们能不能推出损失函数来(限定每个基础分类器的输出为1或-1)。

经过一些计算，我们发现损失函数必须满足以下几个条件（加上可导就差不多充要了）

分离性

\[L(y,f(x)+g(x))=L(y,f(x))\cdot_{}L(y,g(x))
\]

关于xf(x)值不变？

\[L(1,1)=L(-1,-1),\,\,L(1,-1)=L(-1,1)
\]

\[L(y,f(x))=L(-y,-f(x)),\,\,L(y,-f(x))=L(-y,f(x))
\]

而指数损失函数正好满足，而且相对也简单

3、Gradient Boosting

一条不一样的路，待续

Adaboost算法的推导过程

回到前向分步算法，给定初始 \(f_0(x)\) 后, 我们每一步迭代需要计算如下最优化问题

\[\arg_{\beta_{m},\gamma_{m}}\min\sum_{i=1}^{N}L(y_i,f_{m}(x_i)=\sum_{j=1}^{m}\beta_{j}b(x_i;\gamma_{j}))
\]

在不清楚基础分类器的情况下，它是一个泛函，很难求解。现在我们换一个思路，上式可以写成

\[L^{'}(f_{m}(x_1),f_{m}(x_2),\cdots,f_{m}(x_N))=\sum_{i=1}^{N}L(y_i,f_{m}(x_i))
\]

此时损失函数可以看成是关于 \(\{f_{m}(x_i)\}\) 的函数，这个时候就可以用梯度下降算法来求解啦：

\[\frac{\partial\,\,L^{'}(f_{m}(x_1),f_{m}(x_2),\cdots,f_{m}(x_N))}{\partial\,\,f_{m}(x_i)}=\frac{\partial\,L(y_i,f_{m}(x_i))}{\partial\,\,f_{m}(x_i)}
\]

\[f_{m+1}(x)=f_{m}(x)-\beta_{m+1}\frac{\partial\,L(y,f_{m}(x))}{\partial\,\,f_{m}(x)}
\]

这里的步长不是固定值，而是设计为

\[\beta_{m+1}=\arg_{\beta}\min\sum_{i=1}^{N}L\left(y_i,f_{m}(x_i)-\beta\frac{\partial\,L(y_i,f_{m}(x_i))}{\partial\,\,f_{m}(x_i)}\right)
\]

最终可得Gradient Boosting 回归算法

算法：Gradient Boosting

输入：训练集 X和y，一个可微的损失函数 \(L(y,f(x))\),迭代数M

算法：

(1). 用一个常数值初始化：

\[f_{0}(x)=\arg_{\gamma}\min\sum_{i=1}^{N}L(y_i,\gamma)
\]

(2). For m=1 to M:

(a) 计算伪残差：

\[\gamma_{im}=-\left[\frac{\partial\,L(y_{i},f(x_{i}))}{\partial\,f(x_{i})}\right]_{f(x)=f_{m-1}(x)}
\]

根据伪残差拟合一个基础分类器（例如决策树）\(b_{m}(x)\),即利用训练集 \(\{x_{i},\gamma_{im}\}\) 训练基础分类器.

( c ) 计算乘子：

\[\beta_{m}=\arg_{\beta}\min\sum_{i=1}^{n}L(y_i,f_{m-1}(x_{i})+\beta_{}b_{m}(x_{i}))
\]

(d) 更新模型：

\[f_{m}(x)=f_{m-1}(x)+\beta_{m}b_{m}(x)
\]

(3) 输出 \(f_{m}(x)\)

对于回归任务，最常用的损失函数是L2测度，此时

\[L(y,f(x))=(y-f(x))^2/2
\]

\[\gamma_{im}=-\frac{\partial\,L(y_{i},f(x_{i}))}{\partial\,f(x_{i})}=y_i-f(x_i)
\]

刚好是模型的残差。另外常用的损失函数还有L1测度和修正的Huber loss函数（L1测度存在不可导点）

L1测度（绝对值损失函数）：

\[L(y,f(x))=|y-f(x)|
\]

Huber 损失函数：

\[L(y,f(x))=\left\{\begin{align*}
\frac{1}{2}(y-f(x))^2 & &|y-f(x)|\leq \delta\\
\delta(|y-f(x)|-\delta/2|) & & |y-f(x)|>\delta
\end{align*}\right.\]

对于分类任务，假设一共有K类，我们首先建立K个score函数 \(F_{1}(x)、\ldots,F_{K}(x)\)
其次将score函数用于计算概率：

\[P_{1}(x)=\frac{e^{F_{1}(x)}}{\sum_{i=1}^{K}e^{F_{i}(x)}}
\]

\[\cdots
\]

\[P_{K}(x)=\frac{e^{F_{K}(x)}}{\sum_{i=1}^{K}e^{F_{i}(x)}}
\]

然后拟合K个模型就好，其中可以用K-L散度作为损失函数。这种方法的好处在于对异常值不敏感。

Gradient tree boosting

Gradient boosting 一般使用决策树（尤其是CART）作为基础分类器。针对这种特殊情况，Friedman设计了一个修正的gradient boosting 算法。

在第m步，模型需要拟合一颗决策树 \(b_{m}(x)\). 令 \(J_m\) 是叶子数目，该决策树将输入空间分配到不相交的 \(J_m\) 个区域中： \(R_{1m},\ldots,R_{J_{m}m}\) ，并把每一个区域中的输入预测为常数。利用示性函数，我们可以把决策树的输出写为：

\[b_{m}(x)=\sum_{j=1}^{J_{m}}v_{jm}\mathcal{I}(x\in R_{jm})
\]

其中 \(v_{jm}\) 是对应区域预测的值。

将该系数乘以某个值，并利用线性搜索方法使得损失函数最小化：

\[f_{m}(x)=f_{m-1}(x)+\beta_{m}b_{m}(x)
\]

\[\beta_{m}=\arg_{\beta}\min\sum_{i=1}^{N}L(y_{i},f_{m-1}(x_i)+\beta_{}b_{m}(x_{i}))
\]

Friedman 提出可以针对每一个区域选出一个最好的乘子 \(\beta\), 并且把这种方法称为 “Tree Boost”:

\[f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J_m}\beta_{jm}\mathcal{I}(x\in\,R_{jm})
\]

\[\beta_{jm}=\arg_{\beta}\min\sum_{x_i\in\,R_{jm}}L(y_{i},f_{m-1}(x_i)+\beta)
\]

我们重新来考虑 Tree Boosting. 给定含n个样本m个特征的数据集：

\[\mathcal{D}=\{(x_i,y_i)\}\,(|\mathcal{D}|=n,\,x_i\in\,\mathbb{R}^{m},y_i\in\mathbb{R})
\]

假定基础模型是CART决策树，当决策树的叶子数为T时，Tree将输入值划分到T个区域，每一个区域都有指定的值，令 \(q：\mathbb{R}^{m}\rightarrow\{1,2,\ldots,T\}\) 为数的结构，则决策树的输出可以表示为：

\[b(x)=w_{q(x)}
\]

XGBoost 不考虑梯度，直接将损失函数泰勒展开知道二阶导数

\[\mathcal{L}^{(t)}=\sum_{i=1}^{n}l(y_i,\hat{y_i}^{(t-1)}+f_{t}(x_i))+\Omega(f_t)
\]

二阶泰勒逼近可以快速优化上述问题

\[\mathcal{L}^{(t)}=\sum_{i=1}^{n}[l(y_i,\hat{y_i}^{(t-1)})+g_{i}f_{t}(x_i)+\frac{1}{2}h_{i}f_{t}^{2}(x_i)]+\Omega(f_t)
\]

其中g和h是l的一阶导数和二阶导数（自变量为 \(\hat{y}\) ). 可以看到第一项是常数项，所以我们只需要优化第二项。

另外指定正则项为

\[\Omega(f_t)=\gamma_{}T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}
\]

则上式可以重写为

\[\tilde{\mathcal{L}}^{(t)}=\sum_{i=1}^{n}[g_{i}f_{t}(x_i)+\frac{1}{2}h_{i}f_{t}^{2}(x_i)]+\gamma_{}T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}
\]

\[\tilde{\mathcal{L}}^{(t)}=\sum_{j=1}^{T}[(\sum_{i\in\,I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in\,I_j}h_i+\lambda)w_{j}^{2}]+\gamma\,T
\]

其中 \(I_{j}=\{i|q(x_i)=j\}\) . 对于固定的决策树结构 q(x), 我们可以计算叶子j上的最优权重 \(w_{j}^{* }\) :

\[G_j=\sum_{i\in\,I_j}g_i,\,\,\,H_{j}=\sum_{i\in\,I_j}h_i
\]

\[w_{j}^{* }=-\frac{G_j}{H_j+\lambda}
\]

以及对应的损失函数

\[\tilde{\mathcal{L}}^{(t)}(q)=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma\,T
\]

上式可以用于度量决策树结构q，可以当成打分函数。我们可以遍历所有的结构找到最优的决策树。当然一般的遍历所有决策树是不可能的，一个贪婪的想法是将其作为增益函数，每一次尝试去对已有的叶子加入一个分割，对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算：

\[\mathcal{L}_{split}=\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}]-\gamma
\]

附机器学习算法中GBDT和XGBOOST的区别有哪些?

传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点