集成学习是将多个模型组合在一起形成一个更强大的模型。往往单一的模型存在缺陷,只在某些方面表现的好,集成学习能够把这些有偏好的模型组合在一起,通过集体的决定将缺陷纠正。通俗的说,就是“三个臭皮匠顶个诸葛
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为样本集,随机森林算法如下:
|
|
这里的决策树模型一般选用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
二分类问题训练集:
初始化每个样本的权重为$w_i=\frac 1n$
for m = 1,2,…,M:
- 根据所有样本及其权重,训练得到分类器$G_m(x)$
- 计算$G_m(x)$在训练集上的误差,其中$I(x)$为0-1误差
根据误差,计算$G_m(x)$的系数,即一个模型在最终模型的权重由它在训练集上的误差决定
更新样本权重,错误样本增大权重,正确样本减小权重
其中$Z_m$是归一化因子
最后将所有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)$,令其损失函数为:
假设m-1步已经得到$f_{m-1}(x)$,第m步希望得到:
令$w_{mi} = exp(-yif{m-1}(x))$,这就是第m步时每个样本的权重。$w_{mi}$与$\alpha ,G$不相关,所以上式可以写成:
对于上式,首先求解
考虑预测的正确与否,展开后得到:
对$\alpha$求导并使导数为0,可以解得:
与AdaBoost算法中基分类器的系数一致
当错误率$e_m < 0.5$时,系数$\alpha_m > 0$,并且错误率越小,系数越大。表明单个模型越好,在总模型中权重越大,如果比纯随机(错误率0.5)要好,那这个模型在总模型中有正向的作用。
GBDT
GBDT全称Gradient Boosting Decision Tree,也是一种Boosting算法,并且被认为是效果最好的统计学习算法之一。GBDT基学习器用的是决策树,采用加法模型和前向分步算法。GBDT可以选用不同的损失函数来解决不同的决策问题,比如用平方损失函数解决回归问题,用指数损失函数解决分类问题。从这个角度,如果AdaBoost算法选用决策树作为基分类器,那AdaBoost算法可以看作GBDT的一个特例。
GBDT最终加法模型可以表示为:
$T(x;\theta_m)$是表示第m个决策树, $\theta_m$表示决策树的参数,M是决策树的数量。
如果使用平方损失函数:
令$r=y-f_{m-1}(x)$,称为当前模型拟合数据的残差,从损失函数的形式可以看到,这时候拟合第m棵决策树时,不要拟合训练数据的y,而要拟合残差r。换句话说,第m棵决策树的训练数据是$(x_i, yi-f{m-1}(x_i))$,这样自然而然每一步根据之前模型的残差可以训练一个决策树模型。
损失函数是平方损失时定义残差很方便,如果推广到一般损失函数,就需要引入梯度提升(gradient boosting)算法来计算。梯度提升算法相当于在函数空间内做梯度下降(gradient descent),用损失函数的负梯度在当前模型的值作为残差的近似值,第m步第i个样本的残差可以表示为:
例如,损失函数用对数似然损失函数:
此时计算残差:
据此拟合第m棵决策树。