集成学习

2018-07-02

集成学习是将多个模型组合在一起形成一个更强大的模型。往往单一的模型存在缺陷，只在某些方面表现的好，集成学习能够把这些有偏好的模型组合在一起，通过集体的决定将缺陷纠正。通俗的说，就是“三个臭皮匠顶个诸葛

Bagging

Bagging全称是Bootstrap Aggregation，bootstrap的意思是对样本集D有放回地抽取N个样本。Bagging的流程如下：

bootstrap获取样本子集$\tilde{D}$，并据此训练一个模型
重复n次，得到n个模型
将n个模型线性组合成最终模型

Bagging的每个模型是同类模型，训练数据是重采样获得的，因此每个模型肯定不相同但是两两之间存在相关性。从bias和variance的角度考虑，每个模型的期望和方差近似相等。显然$E[\frac{\sum X_i}{n}]=E[X_i]$，所以bias不变。

方差$Var(\frac 1n \sum X_i) = \frac 1{n^2}\sum Var(X_i) + Cov(X_1,X_2,…,X_i)$，所有模型的方差近似相等，并且协方差肯定大于0，所以最终模型的方差会比$\frac {Var(X_i)}n$大一些，但小于$Var(X_i)$（所有模型完全相同的情况）。

综上，Bagging能降低模型的variance而不能降低bias。因此，在选择Bagging的基学习器时，通常选用强学习器（高variance低bias），比如CART决策树，将容易过拟合的学习器“平均”成泛化能力强的学习器。显然，Bagging是可以并行的算法（同时训练n个模型）

随机森林

随机森林是Bagging和决策树的组合。令D为样本集，随机森林算法如下：

for t = 1,2,...,T:
	对样本集D重采样得到子数据集
	根据子数据集拟合一个决策树模型
G = 线性组合所有T个决策树模型
return G

这里的决策树模型一般选用CART决策树，并且不需要剪枝，希望得到低bias高variance的决策树用于bagging。

随机森林在CART决策树分裂时有一点改进：普通决策树是遍历所有M个特征，随机森林是从所有M个特征中随机选择m个（m << M），从这m个中选择最优分裂点。

OOB（out of bag）

所有bagging类的算法，包括随机森林，都可以使用OOB样本来做测试集验证误差。OOB指的是那些每一次重采样都没有被选中的样本，一个样本是OOB的概率为$P=(1-\frac 1N)^N$，当重采样次数趋向于∞时，概率为$\frac 1e$。大约有不到三分之一的样本是OOB样本，不参与训练，可以直接作为验证集。

Boosting

Boosting中文是提升方法，是另一种常见的集成学习方法。Boosting的核心思想是：迭代训练一系列学习器，每个学习器的样本分布与之前的学习器有关，最后将所有学习器线性组合作为最终输出。

Boosting每一个学习器的训练都用了相同的样本，所以每个学习器之间是强相关的，相关系数可以近似为1，因此方差近似不会改变$Var(\frac 1n \sum X_i) = Var(X_i)$。并且Boosting的思想是每一步训练一个新的学习器，来最小化整体损失函数，因此整体模型的bias是在逐渐减小的。所以，Boosting的基学习器应该选择弱学习器（高bias低variance）。

AdaBoost

二分类问题训练集：

$T=\lbrace(x_1,y_1),(x_2,y_2),...,(x_n,y_n) \rbrace, y \in \lbrace+1,-1 \rbrace$

初始化每个样本的权重为$w_i=\frac 1n$

for m = 1,2,…,M:

根据所有样本及其权重，训练得到分类器$G_m(x)$
计算$G_m(x)$在训练集上的误差，其中$I(x)$为0-1误差 $e_m = \sum_{i=1}^n w_iI(G_m(x_i) \neq y_i)$
根据误差，计算$G_m(x)$的系数，即一个模型在最终模型的权重由它在训练集上的误差决定

$\alpha_m = \frac 12 ln\frac{1-e_m}{e_m}$
更新样本权重，错误样本增大权重，正确样本减小权重 $w_i = \begin{cases} \frac{w_i}{Z_m}exp(-\alpha_m), & \text G_m(x)=y_i \\ \frac{w_i}{Z_m}exp(\alpha_m), & \text G_m(x)\neq y_i \end{cases}$

其中$Z_m$是归一化因子

$Z_m = \sum_{i=1}^n exp(-\alpha_my_iG_m(x_i)%uFF09$

最后将所有M步得到的分类器线性组合成最终分类器$$f(x)=\sum_{m=1}^M \alpha_mG_m(x)$$

模型解释

AdaBoost模型可以看作加法（additive model）模型，用前向分步算法和指数损失函数进行学习。

加法模型是指一系列学习器线性组合成的模型，前向分步算法是一种学习加法模型的贪心算法，不从整体优化模型，而是根据损失函数每一步学习一个基学习器及其参数。

AdaBoost算法的最终分类器是$f(x)=\sum_{m=1}^M \alpha_mG_m(x)$，令其损失函数为：

$L(y,f(x)) = exp(-yf(x))$

假设m-1步已经得到$f_{m-1}(x)$，第m步希望得到：

$\begin{aligned} (\alpha_m, G_m(x)) = \mathop{\arg\min}_{\ \alpha,G} \sum_{i=1}^n exp(-y_i(f_{m-1}(x_i)+\alpha G(x_i))) \end{aligned}$

令$w_{mi} = exp(-yif{m-1}(x))$，这就是第m步时每个样本的权重。$w_{mi}$与$\alpha ,G$不相关，所以上式可以写成：

$(\alpha_m, G_m(x)) = \mathop{\arg\min}_{\ \alpha,G} \sum_{i=1}^n w_{mi}exp(-y_i\alpha G(x_i))$

对于上式，首先求解

$G_m(x) = \mathop{\arg\min}_{\ G} \sum_{i=1}^n w_{mi}I(y_i\neq G(x_i))$

考虑预测的正确与否，展开后得到：

$\begin{aligned} \sum_{i=1}^n w_{mi}exp(-y_i\alpha G(x_i)) &= \sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha} + \sum_{y_i\neq G_m(x_i)}w_{mi}e^{\alpha} \\ &= (e^{\alpha}+e^{-\alpha})\sum_{i=1}^n w_{mi}I(y_i\neq G(x_i)) + e^{-\alpha}\sum_{i=1}^nw_{mi} \end{aligned}$

对$\alpha$求导并使导数为0，可以解得：

$\alpha_m = \frac12 ln\frac {1-e_m}{e_m}$

与AdaBoost算法中基分类器的系数一致

当错误率$e_m < 0.5$时，系数$\alpha_m > 0$，并且错误率越小，系数越大。表明单个模型越好，在总模型中权重越大，如果比纯随机（错误率0.5）要好，那这个模型在总模型中有正向的作用。

GBDT

GBDT全称Gradient Boosting Decision Tree，也是一种Boosting算法，并且被认为是效果最好的统计学习算法之一。GBDT基学习器用的是决策树，采用加法模型和前向分步算法。GBDT可以选用不同的损失函数来解决不同的决策问题，比如用平方损失函数解决回归问题，用指数损失函数解决分类问题。从这个角度，如果AdaBoost算法选用决策树作为基分类器，那AdaBoost算法可以看作GBDT的一个特例。

GBDT最终加法模型可以表示为：

$f_M(x) = \sum_{m=1}^M T(x;\theta_m)$

$T(x;\theta_m)$是表示第m个决策树， $\theta_m$表示决策树的参数，M是决策树的数量。

如果使用平方损失函数：

$\begin{aligned} L(y, f_m(x)) &= (y-f_m(x))^2 \\ &= (y - f_{m-1}(x) - T(x;\theta_m))^2 \\&= (r - T(x;\theta_m))^2 \end{aligned}$

令$r=y-f_{m-1}(x)$，称为当前模型拟合数据的残差，从损失函数的形式可以看到，这时候拟合第m棵决策树时，不要拟合训练数据的y，而要拟合残差r。换句话说，第m棵决策树的训练数据是$(x_i, yi-f{m-1}(x_i))$，这样自然而然每一步根据之前模型的残差可以训练一个决策树模型。

损失函数是平方损失时定义残差很方便，如果推广到一般损失函数，就需要引入梯度提升（gradient boosting）算法来计算。梯度提升算法相当于在函数空间内做梯度下降（gradient descent），用损失函数的负梯度在当前模型的值作为残差的近似值，第m步第i个样本的残差可以表示为：

$r_{mi} = -[\frac {\partial L(y,f(x_i)}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

例如，损失函数用对数似然损失函数：

$L(y,f(x)) = log(1+exp(-yf(x)))$

此时计算残差：

$\begin{aligned} r_{mi} &= -[\frac {\partial log(1+exp(-y_if(x_i)))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} \\ &= \frac y {1+exp(y_if_{m-1}(x_i))} \end{aligned}$

据此拟合第m棵决策树。