Tags: MachineLearning
[TOC]
集成学习的思想可以用一句爷爷小时候经常和我说的话：三个臭皮匠，抵得过一个诸葛亮。就是集体决策，虽然集体中每个人的贡献都较小(弱学习器)，但是每个人考虑到的方面都不一样，通过对每个人的决策进行加权，最终可以得到一个比较完美的决策(强学习器)。而且这种集体决策的方式可以减小决策结果的扰动。
根据个体学习器的生成方式，目前集成学习的分类方式可以大致分为两类，串行序列化生成和并行生成，前者的代表算法有Adaboost, GBDT, 后者有Bagging, Random Forest。
Bagging
Bagging是Bootstrap Aggregating的缩写，Bagging是一种并行集成学习算法，有别于串行的boosting学习算法。Bagging直接基于自助采样(boostrap sampling)，就是有放回采样。给定包含m个样本的数据集，每次又放回采样1个样本，采样m次得到包含m个样本的采样集，原始数据每个样本有可能在采样集中多次出现。重复T*m次采样之后，我们就可以得到T个包含m样本的不同采样集。基于每个采样集训练一个基学习器，然后对基学习器进行结合，进行预测。比如对基学习器的输出结果进行平均，加权等。
m次采样，每次样本没有被采样到的概率是(1 - 1/m), 因此m次采样都没有被采集的概率是：
(1 - \frac{1}{m})^m
m \rightarrow \infty, (1-\frac{1}{m})^m \rightarrow \frac{1}{e} \approx 0.368
原有样本中0.368没有采样到的样本可以用来做包外(out of bag)估计,用来衡量模型的泛化能力。
这种对训练集的采样，可以看作是增强了基学习器的独立性(不同基学习器的训练数据分布存在差异)，使得最后组合的强学习器有着更强的泛化性能。周志华老师也在自己的书中说，从偏差-方差分析的角度而言，boosting是降低偏差，而bagging是降低方差。同时由于bagging对于训练集的依赖程度相对更低，产生的bias会相对更大。
具体算法流程如下：
如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。
Random Forest
随机森林是基于CART决策树构建Bagging集成学习器算法，简单来说，就是随机森林在训练的时候加入随机属性的选择。比如传统的决策树在选择划分属性的时候是在d个属性中选择一个最优属性，而随机森林则是在d个属性中先随机选择k个属性，然后再这k个属性中选择最优的属性。如果k = d,则此时就是传统的决策树，如果k = 1, 则是随机选取一个熟悉作为划分属性。
和基础bagging相比，随机森林在样本随机性(自助采样)上引入了属性的随机性(属性随机选择)。一般而言，random forest比基础bagging有着更低的泛化误差。
结合Bagging的算法流程，我们可以得出random forest的算法流程如下：
输入：样本集 D = {(x_1, y_1), ... (x_m, y_m)},迭代次数T。
过程：
1）t = 1,2,...T:
a) 对训练集进行随机采样，m次，得到包含m样本的采样集 D_t
b)用采样集训练第t个决策树模型h_t(x), 在决策树模型节点上，m个样本特征中随机选择k个样本作为样本特征，然后在k个样本特征值选择一个最优的特征作为决策树的左右子树划分。
2）如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。
Boosting
Boosting是一种串行生成基学习器的学习算法。先从初始训练集训练一个基学习器，然后根据基学习器的表现调整数据分布，使得先前对损失函数贡献更大的样本在后面的训练中得到更多的关注，改变权值，然后使用更新的分布训练下一个基学习器。直至生成的基学习器达到指定的数目T。然后将这T个学习器进行组合，对测试集进行预测。对于提升算法而言，我们主要要解决两个问题：一是如何改变训练数据的权值和分布，从何得到基学习器；二是如何将弱分类器组合成一个强分类器。
Adaboost
Adaboost是boosting族中的代表性算法。Adaboost一般用来解决分类问题那么Adaboost是如何解决前面提到的两个问题的呢？针对第一个问题，Adaboost提高前面被弱分类器分错的分类样本权值，降低前面分类正确的样本权值。针对第二个问题，Adaboost是采用加权表决的方式。即对分类误差小的若分类器使用更大的权重。
那么如何衡量分类误差，如何更新样本权重，如何更新分类器权重呢？先看算法流程：
初始数据分布是均匀分布，D_1(x) = 1/m, 分类器权重更新公式为\alpha_t = \frac{1}{2}ln(\frac{1 - \epsilon_t}{\epsilon_t})。 \epsilon_t是误差率，可以看出误差率越大的分类权重越小，误差率越小的分类器权重越大。对于二分类问题而言，\epsilon_t>0.5 也就是比random guess还差，这个分类器就被放弃了，提前结束训练。而数据分布的更新公式为7，也可以直观看出，分类正确的样本权重减小，分类错误的样本权重加大。二者是e^{2\alpha_t}比例关系。
下面看看二分类问题的adaboost的数学推导(来自周志华老师的书)：
给定数据集D和T个弱分类器，基于加性线性模型组合是：
H(x) = \sum_{t=1}^T a_t h_t(x)
目标函数是指数函数：
l_{exp}(H|D) = E_{x\in D}[e^{-f(x)H(x)}]
至于为啥要用指数函数呢？后面我们会看到。
最小化指数函数：
因此指数损失函数，是原来0，1损失函数的一致替代函数，由于替代函数有更好的数学性质，因此使用它作为优化目标。
GBDT
针对损失函数是平方顺势或者指数损失的时候，adaboost使用加法模型和向前分步算法优化比较简单。但是对于一般损失函数而言，则不好优化，针对这一问题，Friedman 提出梯度提升算法，使用损失函数的负梯度拟合当前损失近似值，拟合一个回归树。
GBDT又称梯度提升决策树，全名是gradient boosting decision tree，是boosting算法成员之一。和传统的boosting相比，gdbt的弱分类器只能使用决策树，而且boosting是根据误差率来调整训练集的分布，而GBDT是使用损失函数的负梯度来拟合本轮损失函数。什么意思呢？
举一个通俗的例子：假设现有的房价为10万每平，我们要预测房价，先用5万去拟合，此时的loss=5, 再用3去拟合剩下的损失，此时的损失为2， 再用1去拟合，损失为1， 再用0.5去拟合，此时损失为0.5，直到逐渐逼近10。
总结
集成学习中的学习器结合会从三个方面带来好处，1) 减小泛化性能不佳的问题，2) 降低陷入局部最小值的风险，3) 扩大假设空间
