集成学习(ensemble learing)主要包含两大类：bagging和boosting
简单的说：

参考资料：
http://www.cnblogs.com/gasongjian/p/7648633.html
http://www.52caml.com/head_first_ml/ml-chapter6-boosting-family/

boosting系列

历史由来：Kearns和Valiant首先提出了”强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。他们指出：

在概率近似正确（probably approximately correct，PAC）学习框架中：

①. 一个概念（一个类，label），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；
②. 一个概念（一个类，label），如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。

Schapire后来证明了: 强可学习和弱可学习是等价的。 也就是说，在PAC学习的框架下，一个概念是强可学习的 充分必要条件 是这个概念是弱可学习的。 表示如下：

强可学习⇔弱可学习

如此一来，问题便成为：在学习中，如果已经发现了”弱学习算法”，那么能否将它提升为”强学习算法”？
boosting的思路： 从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合弱分类器，得到一个强分类器。Boosting方法在学习过程中通过改变训练数据的权值分布，针对不同的数据分布调用弱学习算法得到一系列弱分类器。

1. 在每一轮学习之前，如何改变训练数据的权值分布？

2 如何将一组弱分类器组合成一个强分类器？

Adboost

对于一个二分类问题，adboost通过如下方式学习弱分类器，然后将弱分类器线性组合成一个强分类器。
step1: 初始化训练数据的权值分布,即假设初始化权重一样
$<span class="arithmatex"><span class="MathJax_Preview">D_1 = (w11,w12,...w_{1n}), w_{1i}=1/n</span><script type="math/tex">D_1 = (w11,w12,...w_{1n}), w_{1i}=1/n$
step2: adboost开始反复学习基本分类器，在每一轮m=1,2...M依次执行如下操作：
a) 使用当前分布Dm加权的训练数据集，学习基本分类器$G_m(x)$: X -> {-1, 1}
b) 计算基本分类器$G_m(x)$在加权训练数据集上的分类误差率
$<span class="arithmatex"><span class="MathJax_Preview">e_m = P(G_m(x_i)≠y_i)=\sum_{G_m(x_i)≠y_i} w_{mi}</span><script type="math/tex">e_m = P(G_m(x_i)≠y_i)=\sum_{G_m(x_i)≠y_i} w_{mi}$
c) 计算$G_m(x)$的系数，$\alpha_m=1/2log((1-e_m)/e_m)$, 表示Gm在最终分类器的重要性。从表达式来看，误差越小的其权重越高。
d) 更新新的训练数据集的权重 $D_{m+1}=(w_{m+1, 1}... w_{m+1, n})$ 其中Zm是对w做的归一化。
$<span class="arithmatex"><span class="MathJax_Preview">w_{m+1, i}= w_{m, j}/Z_m exp(-\alpha_m y_i G_m(x_i))</span><script type="math/tex">w_{m+1, i}= w_{m, j}/Z_m exp(-\alpha_m y_i G_m(x_i))$

可以看到误差大的样本，am较小，其新的权重就比较小

step3： 构建基本分类器的线性组合 $f(x)=\sum \alpha_m G_m(x)$

训练误差

adaboost的一个基本性质是：在学习过程中能不断减少训练误差。
【定理】AdaBoost算法最终分类器的误差界为

AdaBoost与前向分步算法

Adaboost算法模型可以认为是：模型是加法模型、损失函数为指数函数、学习算法为前项分布算法的二分类学习方法。

对于加法模型$<span class="arithmatex"><span class="MathJax_Preview">f(x)=\sum_1^M \beta_m b(x;\gama_m )</span><script type="math/tex">f(x)=\sum_1^M \beta_m b(x;\gama_m )$
其中b为基函数，$\beta_m$ 为系数。给定训练数据以及损失函数L(y, f(x))的条件下，学习加法模型就是要最小化损失函数$<span class="arithmatex"><span class="MathJax_Preview">min \sum_1^n L(y_i, \sum_1^M \beta_m b(x_i;\gama_m ))</span><script type="math/tex">min \sum_1^n L(y_i, \sum_1^M \beta_m b(x_i;\gama_m ))$
前向分步算法就是每次只学习一个基函数以及其系数，然后将所有结果做加权

可以证明： AdaBoost就是前向分步算法的一个特例

提升树

	基函数/模型	细节	优化方法
AdaBoost		指数损失
gbdt	以cart为基础分类器	可自定义	只用一阶导数信息
xgboost	gbtree树分类 gblinear：线性模型	可自定义	用到二阶导数信息； 加入正则项； 列抽样(借鉴了rf)； 缺失值处理； 分裂节点寻找的近似方法
lightgbm			1 xgb是level-wise的，lgb是leaf-wise分裂的； 2 histogram算法，离散化； 3 支持类别特征

即以分类树/回归树为基础分类器的提升方法，采用加法模型与前向分步算法。
$<span class="arithmatex"><span class="MathJax_Preview">f_M(x)= \sum T(x;\Theta_m)</span><script type="math/tex">f_M(x)= \sum T(x;\Theta_m)$
所以提升树算法总的来说就是：
- 确定初始提升树f0(x) = 0
- 第m步的模型就是 $f_m(x) = f_{m-1}(x) + T(x;\Theta_m)$
- 通过经验风险最小化确定下一个决策树的参数

在实际操作的时候，会有如下3类

1. 平方误差损失的回归问题
   对于平方误差损失，有$L(y, f_{m-1}(x) + T(x;\Theta_m))= [r -T(x;\Theta_m) ]^2$
   即对于回归问题的提升树来说，就是简单的拟合当前模型的残差。

2. 指数损失的分类问题。
   只需将Adaboost算法中的基本分类器设置为二类分类树即可。

3. 一般损失函数的一般决策问题
   对于一般的损失函数，可能求解最优问题不像前面两个这么简单。针对这个问题，Freidmao 提出了gradient boosting(梯度提升)， 即利用最速下降法的近似方法。
   其关键是利用损失函数的负梯度在当前模型的值，作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

其他更高级的提升树： xgboost，lightgbm
xgboost

bagging系列

也称为自举汇聚法(boostrap aggregating)：
从原始数据集中又放回的抽取n个训练样本，进行k轮抽取，训练k个模型。然后最终将这k个模型结果进行叠加。

比如随机森林