集成模型

集成模型简单的总结，后续有时间再继续完善

集成模型主要目的就是为了降低模型的不确定性，通常来说集成模型可以分成两大类：

Bagging：这类方法的代表是随机森林
Boosting：这类方法的代表是GBDT和XGBoost

注意深度学习中用到的Dropout，其也可以理解为集成模型。随着每个mini-batch随机丢弃一些神经元，其最终会得到不同的网络结构，最终将其集成起来。

Bagging vs Boosting

相同点：两者都可以理解为base learning，且weak（指单个模型效果不太好）

不同点：bagging模型weak的原因是overfitting，而boosting模型weak的原因是underfitting。

实际两者基本的构筑都是基于决策树。

Bagging

Bagging主要是通过平均带来方差的减少（variance reduction）。假设有N个模型，每个模型再预测时的方差为 $\sigma^2$ 。则通过N个模型一起预测时的方差是（平均）： $\frac{\sigma^2} N$ 。

其代表方法随机森林区别于决策树的地方在于：构建树之前需要随机采样。这里包含了样本与特征2个方面。样本随机通常采用Bootstrap方法。

Random Forests = Bagging w. trees + random feature subsets

直观上理解就是, 采用 bootsrap 方法, 训练多个决策树, 最后对所有的结果进行投票。

Boosting

Boosting算法本质是通过学习一个个弱分类器，在之前分类器的基础上不断迭代，最终集成提升为强分类器。boosting方法大致可以分为两种：

Adaptive boosting: 通过分类误差率来调整样本的权重，经过迭代不断更新样本权重（提高错误样本权重，降低正确样本权重）（同时适用于基分类器）。最后将多个分类器组合在一起。
Gradient boosting : 基于残差来优化，不断更新迭代。最后将多个分类器组合在一起。

这里将主要讨论一下Gradient boosting方法。

CART回归树

GBDT使用的决策树基础是CART回归树，由于其每次迭代要拟合的是梯度值，属于连续值，所以不可以使用CART分类树。为了很好的评判拟合程序，选择使用平方误差（MSE）。

回归树的生成算法：

输入：训练数据集D:
输出：回归树 $f(x)$ .
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

选择最优切分变量 $j$ 与切分点 $s$ ，求解

\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]

遍历变量 $j$ ，对固定的切分变量 $j$ 扫描切分点 $s$ ，选择使得上式达到最小值的对 $(j,s)$ 。 $c_1,c_2$ 表示生成的左右两棵子树的均值。

用选定的对 $(j,s)$ 划分区域并决定相应的输出值：

R_{1}(j, s)=x\left|x^{(j)} \leq s, R_{2}(j, s)=x\right| x^{(j)}>s

\hat{c_{m}}=\frac{1}{N} \sum_{x_{1} \in R_{m}(j, s)} y_{i}, x \in R_{m}, m=1,2

继续对两个子区域调用步骤1和2，直至满足停止条件（特定迭代次数或值满足某些条件）。
将输入空间划分为 $M$ 个区域 $R_1,R_2,...R_M$ ，生成决策树：

f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \in R_{m}\right)

提升树

提升树的精髓就是利用残差作为新的样本，不断去迭代决策树，最终使用投票等方法得出最终结果。这是一种基础的思想，后续算法都是再次基础上改进得来。

加法模型与前向分布算法，以决策树作为基函数

提升树算法：

输入：训练数据集 $D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}$

输出：提升树 $f_M(x)$

初始化 $f_0(x)=0$
For $m=1,2,\dots\dotsM$

针对每个样本 $(x_i,y_i)$ ，计算残差

r _ { m , i } = y _ { i } - f _ { m - 1 } ( x _ { i } ) , i = 1 , 2 , \cdots , N

利用 $\left\{\left(x_{i}, r_{m, i}\right)\right\}_{i=1,2, \ldots, N}$ 训练出一个决策树（回归树），得到 $T ( x ; \Theta _ { m } )$
更新 $f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)$

完成以上迭代，即可得到提升树

f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)

GBDT

GBDT（Gradient Boosting Decision Tree），梯度提升树。结合上面两种思想构建而成。

GBDT是基于 Boosting的思想，串行地构造多棵决策树来进行数据的预测，对损失函数做梯度下降，每轮迭代都去拟合损失函数在当前模型下的负梯度，把待求的決策树模型当作参数，从而使得参数朝着最小化损失函数的方向更新。

精髓：利用最速下降的近似方法，具体指利用损失函数的负梯度拟合一个回归树。

GBDT算法

输入：训练数据集 $D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}$ ；损失函数 $L(y,f(x))$ .

输出：梯度提升树 $\hat{f}(x)$

初始化 $f_{0}(x)=\arg \min _{c} \sum_{i=1}^{N} L\left(y_{i}, c\right)$
For $m=1,2,\dots\dotsM$

针对每个样本 $(x_i,y_i)$ ，计算残差

r_{m, i}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]_{ \left.f(x)=f_{m-1}(x)\right)}, i=1,2, \ldots, N

利用 $\left\{\left(x_{i}, r_{m, i}\right)\right\}_{i=1,2, \ldots, N}$ ,训练出第 $m$ 棵回归树 $T_m$ ，其叶节点划分的区域为 $R_{m, j}, j=1,2, \ldots, J$
对于回归树的每一个叶节点，计算器输出值

c_{m, j}=\arg \min _{c} \sum_{x_{i} \in R_{m, j}} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+c\right), j=1,2, \ldots, J

更新 $f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J} c_{m, j} I\left(x \in R_{m, j}\right)$

得到最终的梯度提升回归树

\hat{f}(x)=f_{M}(x)=\sum_{m=1}^{M} \sum_{j=1}^{J} c_{m, j} I\left(x \in R_{m, j}\right)

实际使用时需要定义一个学习率 $\alpha$ 。且如果损失函数选用的是平方损失函数（MSE），其负梯度就是提升树中的直接相减的残差 $y-f(x_i)$ ，但这仅仅是特殊情况。

XGBoost

XGBoost（eXtreme Gradient Boosting）极端梯度提升，既可运用于分类，也可运用于回归。

XGBoost是对GBDT的进一步改进。传统GBDT在优化时只用到一阶导数信息， Xgboost则对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。
XGBOOST在损失函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的 score的L2模的平方和。从 Bias-variance tradeoff角度来讲，正则项降低了模型的 variance,使学习出来的模型更加简单，防止过拟合，这也是 Xgboost优于传统GBDT的一个特性。

相比于前面的不断迭代树求最优函数的推导，XGBoost可以反向去理解，先构造出一个最优的函数，进而最后再去反推树的形状。

如何构造目标函数

类似于上面介绍的方法，最终预测值都是采用累加的方法

假设已经训练好了K棵树，则对于第i个样本的（最终）预测值为：

\hat{y}_{i}=\phi\left(X_{i}\right)=\sum_{k=1}^{K} f_{k}\left(X_{i}\right), f_{k} \in \mathcal{F}

目标函数定义为两个部分，损失函数和控制每棵树复杂度的正则项：

\mathcal{L}(\phi) = \sum_{i} l\left(\hat{y}_{i}, y_{i}\right) + \sum_{k} \Omega\left(f_{k}\right)

对于回归问题，Loss可以选择MSE，对于分类问题，可以选择CrossEntropy，根据实际情况来选择

根据前 $k-1$ 棵树去构建第 $k$ 棵树，则可以表示为：

\hat{k}_{i}^{(t)}=\hat{k}_{i}(t-1)+f_{k}\left(x_{i}\right)

那么目标函数变化为：

\begin{aligned} \mathcal{L}(\phi) &=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}^{(k)}\right)+\sum_{k=1}^{K} \Omega\left(f_{k}\right) \\ &=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}^{(k-1)}+f_{k}\left(X_{i}\right)\right)+\sum_{k=1}^{K-1} \Omega\left(f_{K}\right)+\Omega\left(f_{K}\right)\end{aligned}

前K-1棵树的复杂度无意义，则第K棵树目标函数表示为：

\begin{aligned} \mathcal{L}^{(K)} &=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}^{(k-1)}+f_{k}\left(X_{i}\right)\right)+\Omega\left(f_{K}\right)\end{aligned}

目的就是最小化这个式子

目标函数的近似

这里用到二阶的泰勒公式

f ( x + \Delta x ) \approx f ( x ) + f ^ { \prime } ( x ) \Delta x + \frac { 1 } { 2 } f ^ { \prime \prime } ( x ) \Delta x ^ { 2 }

将 $f_k(X_i)$ 看作 $\Delta x$ （为何可以这样？因为每棵树迭代相加提升的数值很小，可以这样去理解）。则第K棵树目标函数转化为：

\mathcal{L}^{(K)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{(K-1)}\right)+g_{i} f_{K}\left(X_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(X_{i}\right)\right]+\Omega\left(f_{K}\right)

其中 $g_{i}=\partial_{\hat{y}^{(K-1)}}\left(y_{i}, \hat{y}^{(K-1)}\right), h_{i}=\partial_{ \hat{y}^{(K-1)}}^{2}\left(y_{i}, \hat{y}^{(K-1)}\right)$

将树的结构引入目标函数

树的复杂度定义如下：

\Omega\left(f_{K}\right)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}

其中 $T$ 衡量节点的个数， $\sum_{j=1}^{T} w_{j}^{2}$ 衡量了节点的值。定义 $f_K(x) = W_{q(x)}$

\begin{aligned} \mathcal{L}^{(K)} & \simeq \sum_{i=1}^{n}\left[g_{i} f_{K}\left(X_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(X_{i}\right)\right]+\Omega\left(f_{K}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\lambda \frac{1}{2} \sum_{j=1}^{T} w_{j}^{2} \\ &=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}

Tips:第二至三步：将所有节点1到n的循环改写成单独叶节点 $I_J$ 1到T的循环（优点：去除下标，包含二次项）

令 $G_{j}=\sum_{i \in I_{j}} g_{i}, H_{j}=\sum_{i \in I_{j} }g_{i}$ ，代入上式：

\mathcal{L}^{(K)}=\sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T

根据一元二次方程，每个叶子结点的 $score w_j$ 的解为:

w _ { j } ^ { * } = - \frac { G _ { j } } { H _ { j } + \lambda }

L ^ { ( K ) } = - \frac { 1 } { 2 } \sum _ { j = 1 } ^ { T } \frac { G _ { j } ^ { 2 } } { H _ { j } + \lambda } + \gamma T

优化方法（使用贪心算法）

接下来的目标就是学习寻找树的形状，一一例举进行比较不现实。由于已经推导出第K棵树最优结果 $L^{(K)}$ ，因此可以使用贪心算法，相较于上一步 $L^{(K)}_{old}$ ，不断寻找最优 $L^{(K)}_{new}$ ，目标是使得两者间差距最大。

因此对于一个叶子节点进行分裂，分裂先后得到的增益函数可以表示为：

G a i n=\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]-\gamma

第一项为左节点的score，第二项为右节点的score，第三项为上一步骤的score（如果不做分裂），第四项是多出来分支的附加项。式子等同于：

\mathcal{L}_{\text {split }}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma

论文中构造树的算法步骤如图：

但是一个个位移寻找过慢，算法优化后采用一块块进行位移计算。对于每个特征，只考察候选切分点(分位点)，减少计算复杂度。根据候选切分点把当前结点的样本放入对应的桶中，对每个桶的G,H进行累加。最后在候选切分点集合上贪心查找，论文描述如下：

具体如何选取切分点，这里使用 $h$ ，二阶梯度加权，细节部分参考论文，就不细写了。

XGBoost同样有很多优化，例如Shrinkage，列抽样，稀疏值处理等等，也不细展开了，具体详见论文。

不过在使用XGBoost这个库时，对于回归问题，假设迭代K轮，总共生成K棵树。然而对于分类问题，迭代K轮，C分类问题，总共生成CK棵树。原因是分类最后使用softmax函数，针对每一个类别都会生成一棵树，即单次迭代就会生成C棵树，后将对应类别的值相加再求softmax，才能得到类似分类的结果。

还有个LightGBM，其使用了一堆方法对XGBoost进行优化，速度快，且内存占用较低，想了解的自己看论文去吧。

这里仅仅是对自己学习的简单整理，还有很多地方不完善，后续根据情况再继续补补吧。

参考

李航《统计学习方法》

GBDT算法原理以及实例理解

XGBoost论文解读

AdaBoost、GBDT、RF、XGboost、LightGBM的对比分析

XGBoost原始论文：XGBoost: A Scalable Tree Boosting System

LightGBM原始论文：LightGBM: A Highly Efficient Gradient Boosting Decision Tree

乱谈府

乱谈府