集成学习

集成学习是一种由多种弱学习器组合成强学习器的策略，主要分为3类：Boosting方法、Bagging方法、Stacking方法。

一、Boosting

Boosting方法基于串行策略，新的学习器由旧的学习器生成。
代表算法有：

• AdaBoost
• 提升树BT
• 梯度提升树GBDT
• XGBoost

Boosting算法要解决两个问题：

• Q1：如何改变样本数据的权值？
• Q2：如何将弱分类器组合成强分类器？

1.1 AdaBoost

对于Boosting对应的两个问题，AdaBoost的策略为：

• A1：开始时分配同样权值，根据分类误差，提升弱分类器中分类错误的样本权值（对错误的更敏感），降低正确分类样本的权值。
• A2：采用加权表决法组合成强分类器，分类错误率小的分类器有更大的权值。

注：用到两种权值，一个是对样本的，一个是对分类器的。对样本的权值分类错的更大，对弱分类器的权值分类越好（错误率越小）的权值越大。

1.1.1 公式推导

数据有N个，基学习器有M个，如第m个基学习器为$B_m(x)$Bm​(x)，最终输出为由基学习器组合而成的最终学习器B(x)。
1.初始化权重分布
$D_m=(w_{m,1},w_{m,2},\cdots ,w_{m,N}),w_{m,i}=\frac {1}{N}$Dm​=(wm,1​,wm,2​,⋯,wm,N​),wm,i​=N1​
其中权值是分给每个样本的，$D_m$Dm​表示第m个基学习器的样本权值分配。

2.每个基学习器的学习过程

2.1 使用权值分布为$D_m$Dm​的数据集，得到基学习器$B_m(x)$Bm​(x)的分类结果
$B_m(x)=\chi \rightarrow \{-1,+1\}$Bm​(x)=χ→{−1,+1}
即将样本映射到区间[-1,+1]上。

2.2 弱分类器$B_m(x)$Bm​(x)的误差
$e_m=P(B_m\neq y_i) =\sum _{i=1}^{N}w_{m,i}I(B_m\neq y_i)$em​=P(Bm​̸​=yi​)=∑i=1N​wm,i​I(Bm​̸​=yi​)

2.3 计算$B_m(x)$Bm​(x)系数
$\alpha _m= \frac {1}{2} ln \frac {1-e_m}{e_m}$αm​=21​lnem​1−em​​

由上述公式可以看出某个弱分类器的权值分配的基本原则为：分类的越准，权值越大。

2.4 更新训练集权值分布
$D_{m+1} =(w_{m+1,1},w_{m+1,2},\cdots ,w_{m+1,N})$Dm+1​=(wm+1,1​,wm+1,2​,⋯,wm+1,N​)
其中
$w_{m+1,i}=\frac {w_{m,i}\cdot exp(-\alpha_m \cdot y_i B_m(x_i))}{Z_m}$wm+1,i​=Zm​wm,i​⋅exp(−αm​⋅yi​Bm​(xi​))​

$Z_m=\sum_{i=1}^{N}w_{m,i}\cdot exp(-\alpha _m y_i B_m(x_i))$Zm​=∑i=1N​wm,i​⋅exp(−αm​yi​Bm​(xi​))
其实我们可以发现$ y_i B_m(x_i)$要么为+1（分类正确），要么为-1（分类错误）。具体转化公式形式如下：
$w_{m+1,i}=\left\{\begin{matrix} \frac {w_{m,i}\cdot e^{-\alpha _m}}{Z_m} &y_i=B_m(x_i) \\ \frac {w_{m,i}\cdot e^{\alpha _m}}{Z_m} &y_i\neq B_m(x_i) \end{matrix}\right.$wm+1,i​={Zm​wm,i​⋅e−αm​​Zm​wm,i​⋅eαm​​​yi​=Bm​(xi​)yi​̸​=Bm​(xi​)​

其中$\alpha _m$αm​为(0,1)之间的数，可以看出分类错误的样本会获得更大的权重。

3. 基学习器的组合
$B(x)=sign(\sum _{m=1}^{M}\alpha _m B_m(x))$B(x)=sign(∑m=1M​αm​Bm​(x))

1.1.2 前向分布算法

AdaBoost算法是前向分布算法的一种特例，前向分布算法使求解加法模型的一种算法。
加法模型可以表示为：
$f(x)=\sum _{m=1}^{M} \alpha_m b(x;\gamma_m)$f(x)=∑m=1M​αm​b(x;γm​)

其中$ \alpha_m$为基学习器系数，$为基学习器系数， b(x;\gamma_m)$为基函数，$为基函数，\gamma_m$为基函数参数，学习加法模型可以可以转化为损失函数最小化问题：
$min_{\alpha_m \gamma_m}\sum_{i=1}^M L(y_i,\sum_{i=1}^M\alpha_m b(x;\gamma_m))$minαm​γm​​∑i=1M​L(yi​,∑i=1M​αm​b(x;γm​))

使用前向分布算法求解上述损失函数过程：
基本思想为从前往后，每次只学习一个基函数和它的系数，逐步优化目标函数。

1. 令$f_0(x)=0$f0​(x)=0
2. $(\alpha_m,\gamma_m)=argmin_{\alpha,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+\alpha b(x_i;\gamma))$(αm​,γm​)=argminα,γ​∑i=1N​L(yi​,fm−1​(xi​)+αb(xi​;γ))
   $f_m(x)=f_{m-1}(x)+\alpha_m b_m(x;\gamma_m)$fm​(x)=fm−1​(x)+αm​bm​(x;γm​)
3. $f(x)=\sum_{m=1}^M \alpha_m b(x;\gamma_m)$f(x)=∑m=1M​αm​b(x;γm​)
   可以从上述公式中看出，AdaBoost为前向分布算法的一种特殊情况。

1.2 梯度提升决策树GBDT

GBDT（梯度提升树）是以决策树（CART）为基学习器的Boosting类型的集成学习方法，与提升树在残差计算方面有所不同，提升树使用真正的残差，梯度提升树使用模型的负梯度拟合残差。

1.2.1 CART回归树

CART分类树采用Gini指数选取最优特征，根据的是信息的纯度，适用于离散的情况。但CART回归树需要拟合梯度值，需要使用连续值，所以使用平方误差来拟合误差。

1.2.2 GBDT算法描述

训练数据有N个，基础决策树有m个，根据决策树深度可以划分为J个叶子节点，c表示初始决策树预测值，$\Upsilon $表示决策树叶子节点参数值。

1. 初始化弱学习器
   $f_0(x)=argmin_c \sum_{i=1}^{N}L(y_i,c)$f0​(x)=argminc​∑i=1N​L(yi​,c)

2.第m个决策树的生成
（1）计算第m个决策树中每个样本残差
$r_{i,m}=-\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)}$ri,m​=−∂fm−1​(xi​)∂L(yi​,fm−1​(xi​))​

（2）得到叶子节点的划分区域$R_{jm},j=1,2,\cdots,J$Rjm​,j=1,2,⋯,J。J的大小由决策树深度决定。

（3）对叶子区域计算最佳拟合值
$\Upsilon_{jm} =argmin_\Upsilon \sum_{x_i \in R_{jm} }L(y_i,f_{m-1}(x_i)+\Upsilon)$Υjm​=argminΥ​∑xi​∈Rjm​​L(yi​,fm−1​(xi​)+Υ)

（4）更新第m个决策树
$f_m(x)=f_{m-1}(x)+\sum_{j=1}^{J}\Upsilon _{jm}I(x\in R_{jm})$fm​(x)=fm−1​(x)+∑j=1J​Υjm​I(x∈Rjm​)

3. 得到最终学习器
   $f(x)=f_M(x)=f_0(x)+\sum_{m=1}^{M}\sum_{j=1}^{J}\Upsilon _{jm}I(x\in R_{jm})$f(x)=fM​(x)=f0​(x)+∑m=1M​∑j=1J​Υjm​I(x∈Rjm​)

1.2.3 举个例子

数据如下，两个特征：年龄和体重；一个标签：身高，即根据年龄和体重预测身高。

编号	年龄（岁）	体重（kg）	身高（m）（标签）
0	5	20	1.1
1	7	30	1.3
2	21	70	1.7
3	30	60	1.8
4（需预测）	25	65	？

训练阶段

1. 初始化弱学习器
   $f_0(x)=argmin_c \sum_{i=1}^{N}L(y_i,c)$f0​(x)=argminc​∑i=1N​L(yi​,c)
   其中损失函数为平方损失，因为平方损失函数为一个凸函数，所以可以直接求导，导数为0即可求出参数c。
   $\frac{\partial L(y_i,c)}{\partial c}=\sum_{i=1}^N \frac{\partial \frac{1}{2} (y_i-c)^2}{\partial c}=\sum_{i=1}^{N}c-y_i$∂c∂L(yi​,c)​=∑i=1N​∂c∂21​(yi​−c)2​=∑i=1N​c−yi​
   令导数为0可以得到:
   $c=\frac{\sum_{i=1}^{N}y_i}{N}$c=N∑i=1N​yi​​
   即c的取值为所有样本标签值的均值。
   $c=(1.1+1.3+1.7+1.8)/4=1.475$c=(1.1+1.3+1.7+1.8)/4=1.475
   所以$f_0(x)=c=1.475$f0​(x)=c=1.475
2. 学习器的迭代m=1,2，···，M
   我们设置迭代次数m=1。
   计算负梯度，负梯度即为残差，使用残差作为新的标签值，进而利用新的标签分类。
   $r_{i,1}=-\frac{\partial L(y_i,f_{0}(x_i))}{\partial f_{0}(x_i)}$ri,1​=−∂f0​(xi​)∂L(yi​,f0​(xi​))​
   弱学习器$f_1(x)$f1​(x)得到残差数据如下：

编号	年龄	体重	新标签值
0	5	20	-0.375
1	7	30	-0.175
2	21	70	0.225
3	30	60	0.325

​ 接着遍历每个特征的每个取值找到合适的划分点是的总的误差最小，即在叶子节点中 分类错误的最小。例如使用年龄=5的条件划分，接着使用年龄=7划分·····，接着继续在 叶子节点划分，直到达到树的最大深度，最终生成一个决策树。
​ 在此次划分中选择的属性为年龄=21，按照是否小于21岁划分为两个叶子节点
​ 接着需要对每个叶子节点分配参数：
​ $\Upsilon_{j1} =argmin_\Upsilon \sum_{x_i \in R_{j1} }L(y_i,f_{0}(x_i)+\Upsilon) $
​ 损失函数为平方损失，利用求导并令导数为0可以求解出来参数。结果为：
​ $x_0,x_1\in R_{11},\Upsilon_{11}=-0.275$x0​,x1​∈R11​,Υ11​=−0.275
​ $x_2,x_3\in R_{21},\Upsilon_{21}=0.275$x2​,x3​∈R21​,Υ21​=0.275
​ 此时就构成了迭代一次后的决策树：
​ $f_1(x)=f_{0}(x)+\sum_{j=1}^{2}\Upsilon _{j1}I(x\in R_{j1})$f1​(x)=f0​(x)+∑j=12​Υj1​I(x∈Rj1​)

3. 得到最终学习器
   $f(x)=f_1(x)=f_0(x)+\sum_{m=1}^{1}\sum_{j=1}^{2}\Upsilon _{jm}I(x\in R_{jm})$f(x)=f1​(x)=f0​(x)+∑m=11​∑j=12​Υjm​I(x∈Rjm​)
4. 最终结果
   $f_0(x)=1.475$f0​(x)=1.475
   $f_1(x)=0.2250$f1​(x)=0.2250

测试结果
结果为$f(x)=1.475+（0.275）=1.75$f(x)=1.475+（0.275）=1.75

参考文献：
****：https://blog.****.net/blank_tj/article/details/82262431
Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial

1.3 XGBoost

XGBoost是改进的梯度提升(GB)算法，Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。

1.3.1 XGBoost 与 GB 的主要区别

• 对损失函数加入正则项，包括 L2 权重衰减和对叶子数的限制
• 使用牛顿法代替梯度下降法寻找最优解：前者使用一阶+二阶导数作为残差，后者只使用了一阶导数
• 传统 CART树寻找最优切分点的标准是最小化均方差；XGBoost 通过最大化得分公式来寻找最优切分点：

1.3.2 XGBoost 的一些内部优化

• 在寻找最佳分割点时，传统的方法会枚举每个特征的所有可能切分点。XGBoost 实现了一种近似的算法，大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
• XGBoost 考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper 提到能提高 50 倍。
• 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然 Boosting 算法迭代必须串行，但是在处理每个特征列时可以做到并行。
• 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致 cache miss，降低算法效率。Paper 中提到，可先将数据收集到线程内部的 buffer，然后再计算，提高算法的效率。
• XGBoost 还考虑了数据量比较大的情况，当内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。