集成学习概述
当做重要决定时，大家可能都会考虑吸取多个专家而不只是一个人的意见。集成学习也是如此。集成学习就是组合多个个体学习器，最后可以得到一个更好的学习器。
集成学习算法：
- bagging：用于减少方差的，个体学习器之间不存在强依赖关系，装袋
- boosting：用于减少偏差，个体学习器之间存在强依赖关系，提升
学习器的结合方式：
- voting：投票
- Stacking：用于提升预测结果，堆叠
集成学习之个体学习器
集成学习的第一个问题就是如何得到若干个个体学习器。这里我们有两种选择。
第一种就是所有的个体学习器都是一个种类的，或者说是同质的。比如都是决策树个体学习器，或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的，或者说是异质的。比如我们有一个分类问题，对训练集采用支持向量机个体学习器，逻辑回归个体学习器和朴素贝叶斯个体学习器来学习，再通过某种结合策略来确定最终的分类强学习器。
目前来说，同质个体学习器的应用是最广泛的，一般我们常说的集成学习的方法都是指的同质个体学习器。而同质个体学习器使用最多的模型是CART决策树和神经网络。
同质个体学习器按照个体学习器之间是否存在依赖关系可以分为两类，第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法，第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是 bagging 和随机森林（Random Forest）系列算法。
bagging
Bagging 是引导聚合的意思。减少一个估计方差的一种方式就是对多个估计进行平均。例如，我们可以用训练集的不同子集（随机选择并替代训练集）训练 M 个不同的树然后计算最后的结果：
Bagging 使用装袋采样来获取数据子集训练基础学习器。通常分类任务使用投票的方式集成，而回归任务通过平均的方式集成。
- 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping（有放回）的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（我们这里假设k个训练集之间是相互独立的，事实上不是完全独立）
- 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。但是是同种模型。（注：k个训练集虽然有重合不完全独立，训练出来的模型因为是同种模型也是不完全独立。这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
- 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
对于 Bagging 需要注意的是，每次训练集可以取全部的特征进行训练，也可以随机选取部分特征训练，例如随机森林就是每次随机选取部分特征。
随机森林是 bagging 的一个特化进阶版，所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在 bagging 的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离 bagging 的范畴。
boosting
Boosting 指的是通过算法集合将弱学习器转换为强学习器。boosting 的主要原则是训练一系列的弱学习器，所谓弱学习器是指仅比随机猜测好一点点的模型，例如较小的决策树，训练的方式是利用加权的数据。在训练的早期对于错分数据给予较大的权重。
对于训练好的弱分类器，如果是分类任务按照权重进行投票，而对于回归任务进行加权，然后再进行预测。boosting 和 bagging 的区别在于是对加权后的数据利用弱分类器依次进行训练。
boosting 是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：
- 先从初始训练集训练出一个基学习器；
- 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；
- 基于调整后的样本分布来训练下一个基学习器；
- 重复进行上述步骤，直至基学习器数目达到事先指定的值 T，最终将这 T 个基学习器进行加权结合。
结合策略
在上面几节里面我们主要关注于学习器，提到了学习器的结合策略但没有细讲，本节就对集成学习之结合策略做一个总结。我们假定我得到的 $T$ 个弱学习器是 ${h_1,h_2,…,h_T}$
平均法
对于数值类的回归预测问题，通常使用的结合策略是平均法，也就是说，对于若干个弱学习器的输出进行平均得到最终的预测输出。
最简单的平均是算术平均，也就是说最终预测是:
$$
H(x)=\frac{1}{T} \sum_{1}^{T} h_{i}(x)
$$
如果每个个体学习器有一个权重 $w$，则最终预测是:
$$
H(x)=\sum_{i=1}^{T} w_{i} h_{i}(x)
$$
其中 $w_i$ 是个体学习器 $h_i$ 的权重，通常有:
$$
w_{i} \geq 0, \quad \sum_{i=1}^{T} w_{i}=1
$$
投票法
对于分类问题的预测，我们通常使用的是投票法。假设我们的预测类别是 ${c_1,c_2,…c_K}$，对于任意一个预测样本 $x$，我们的 $T$ 个弱学习器的预测结果分别是 $(h_1(x),h_2(x)…h_T(x))$。
最简单的投票法是相对多数投票法，也就是我们常说的少数服从多数，也就是 $T$ 个弱学习器的对样本 $x$ 的预测结果中，数量最多的类别 $c_i$ 为最终的分类类别。如果不止一个类别获得最高票，则随机选择一个做最终类别。
稍微复杂的投票法是绝对多数投票法，也就是我们常说的要票过半数。在相对多数投票法的基础上，不光要求获得最高票，还要求票过半数。否则会拒绝预测。
更加复杂的是加权投票法，和加权平均法一样，每个弱学习器的分类票数要乘以一个权重，最终将各个类别的加权票数求和，最大的值对应的类别为最终类别。
学习法 stacking
上两节的方法都是对弱学习器的结果做平均或者投票，相对比较简单，但是可能学习误差较大，于是就有了学习法这种方法，对于学习法，代表方法是 stacking ，当使用 stacking 的结合策略时，我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。
在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。
Adaboost 详解
boosting 算法的基本原理
从图中可以看出，Boosting 算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目 $T$，最终将这 $T$ 个弱学习器通过集合策略进行整合，得到最终的强学习器。
不过有几个具体的问题 Boosting 算法没有详细说明。
- 如何计算学习误差率e?
- 如何得到弱学习器权重系数α?
- 如何更新样本权重D?
- 使用何种结合策略？
只要是 boosting 大家族的算法，都要解决这 4 个问题。那么 Adaboost 是怎么解决的呢？
Adaboost 算法的基本思路
假设我们的训练集样本是:
$$
T={(x, y_{1}),(x_{2}, y_{2}), \cdots,(x_m, y_m)}
$$
训练集的在第 $k$ 个弱学习器的输出权重为:
$$
D(k)=\left(w_{k 1}, w_{k 2}, \ldots w_{k m}\right) ; \quad w_{1 i}=\frac{1}{m} ; \quad i=1,2 \ldots m
$$
分类问题
首先我们看看 Adaboost 的分类问题。
分类问题的误差率很好理解和计算。由于多元分类是二元分类的推广，这里假设我们是二元分类问题，输出为 ${-1，1}$ ，则第 $k$ 个弱分类器 $G_k(x)$ 在训练集上的加权误差率为
$$
e_{k}=P\left(G_{k}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{m} w_{k i} I\left(G_{k}\left(x_{i}\right) \neq y_{i}\right)
$$
接着我们看弱学习器权重系数,对于二元分类问题，第k个弱分类器 $G_k(x)$ 的权重系数为:
$$
\alpha_{k}=\frac{1}{2} \log \frac{1-e_{k}}{e_{k}}
$$
为什么这样计算弱学习器权重系数？从上式可以看出，如果分类误差率 $e_k$ 越大，则对应的弱分类器权重系数 $\alpha_k$ 越小。也就是说，误差率小的弱分类器权重系数越大。具体为什么采用这个权重系数公式，我们在讲 Adaboost 的损失函数优化时再讲。
第三个问题，更新更新样本权重 $D$。假设第 $k$ 个弱分类器的样本集权重系数为 $D(k)=(w_{k1},w_{k2},…w_{km})$ ，则对应的第k+1个弱分类器的样本集权重系数为
$$
w_{k+1, i}=\frac{w_{k i}}{Z_{K}} \exp \left(-\alpha_{k} y_{i} G_{k}\left(x_{i}\right)\right)
$$
这里 $Z_k$ 是规范化因子
$$
Z_{k}=\sum_{i=1}^{m} w_{k i} \exp \left(-\alpha_{k} y_{i} G_{k}\left(x_{i}\right)\right)
$$
从 $w_{k+1,i}$ 计算公式可以看出，如果第 $i$ 个样本分类错误，则 $y_iG_k(x_i)<0$，导致样本的权重在第 $k+1$ 个弱分类器中增大，如果分类正确，则权重在第 $k+1$ 个弱分类器中减少。具体为什么采用样本权重更新公式，我们在讲 Adaboost 的损失函数优化时再讲。
最后一个问题是集合策略。Adaboost 分类采用的是加权表决法，最终的强分类器为
$$
f(x)={sign}\left(\sum_{k=1}^{K} \alpha_{k} G_{k}(x)\right)
$$
回归问题
接着我们看看 Adaboost 的回归问题。由于 Adaboost 的回归问题有很多变种，这里我们以 Adaboost R2 算法为准。
我们先看看回归问题的误差率的问题，对于第 $k$ 个弱学习器，计算他在训练集上的最大误差
$$
E_{k}=\max \left|y_{i}-G_{k}\left(x_{i}\right)\right| i=1,2 \ldots m
$$
然后计算每个样本的相对误差
$$
e_{k i} = \frac {\left|y_{i}-G_{k}\left(x_{i}\right)\right|} {E_k}
$$
这里是误差损失为线性时的情况，如果我们用平方误差，则 $
e_{k i} = \frac {\left|y_{i}-G_{k}\left(x_{i}\right)\right|^2} {E_k^2} $ ,如果我们用的是指数误差，则 $e_{k i}=1-\exp \left(\frac{-y_{i}+G_{k}\left(x_{i}\right) )}{E_k}\right)$.
最终得到第 $k$ 个弱学习器的误差率
$$e_{k}=\sum_{i=1}^{m} w_{k i} e_{k i}$$
我们再来看看如何得到弱学习器权重系数 $\alpha$ 。这里有：
$$
\alpha_k=\frac{e_k}{1-e_k}
$$
对于更新更新样本权重 $D$ ，第 $k+1$ 个弱学习器的样本集权重系数为
$$
w_{k+1, i}=\frac{ w _ {ki} }{ Z_k } \alpha_{k} ^ {1 - e _ {ki} }
$$
这里 $Z_k$ 是规范化因子
$$
Z_{k}=\sum_{i=1}^{m} w _ {ki} \alpha_{k}^{1-e _ {ki} }
$$
最后是结合策略，和分类问题稍有不同，采用的是对加权的弱学习器取权重中位数对应的弱学习器作为强学习器的方法，最终的强回归器为
$$
f(x) = G _ { k^\ast } (x)
$$
其中，$ G _ { k^\ast } (x) $ 是所有 $\ln \frac{1}{\alpha_k},k=1,2,\cdots,K$ 的中位数值对应序号 $ k^\ast $ 对应的弱学习器。
分类问题的损失函数优化
刚才上一节我们讲到了分类 Adaboost 的弱学习器权重系数公式和样本权重更新公式。但是没有解释选择这个公式的原因，让人觉得是魔法公式一样。其实它可以从 Adaboost 的损失函数推导出来。
从另一个角度讲，Adaboost 是模型为加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。
模型为加法模型好理解，我们的最终的强分类器是若干个弱分类器加权平均而得到的。
前向分步学习算法也好理解，我们的算法是通过一轮轮的弱学习器学习，利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。也就是说，第 $k-1$ 轮的强学习器为
$$
f_{k-1}(x)=\sum_{i=1}^{k-1} \alpha_{i} G_{i}(x)
$$
而第 $k$ 轮的强学习器为
$$
f_{k}(x)=\sum_{i=1}^{k} \alpha_{i} G_{i}(x)
$$
上两式一比较可以得到
$$
f_{k}(x)=f_{k-1}(x)+\alpha_{k} G_{k}(x)
$$
可见强学习器的确是通过前向分步学习算法一步步而得到的。
Adaboost 损失函数为指数函数，即定义损失函数为
$$
\arg \min _ {\alpha, G} \sum_{i=1}^{m} \exp \left (-y_{i} f_{k}(x_i)\right)
$$
利用前向分步学习算法的关系可以得到损失函数为
$$
\left(\alpha_k, G_{k}(x)\right) = \arg \min _ {\alpha, G} \sum_{i=1}^{m} \exp \left[\left(-y_{i}\right)\left(f_{k-1}(x_i)+\alpha_k G_k(x_i)\right)\right]
$$
令 $w_{k i}^{\prime}=\exp \left(-y_{i} f_{k-1}(x_i)\right)$ , 它的值不依赖于 $\alpha, G$ ，因此与最小化无关，仅仅依赖于 $ f _ {k-1} ( x_i ) $ ，随着每一轮迭代而改变。将这个式子带入损失函数，损失函数转化为
$$
\left(\alpha_{k}, G_{k}(x)\right)= \arg \min _ {\alpha, G} \sum_{i=1}^{m} w_{k i}^{\prime} \exp \left[-y_{i} \alpha_k G_k(x_i)\right]
$$
首先，我们求 $G_{k}(x)$，可以得到
$$
G_{k}(x)= \arg \min _ {G} \sum_{i=1}^{m} w_{k i}^{\prime} I\left(y_{i} \neq G_k\left(x_{i}\right)\right)
$$
将 $G_{k}(x)$ 带入损失函数，并对 $ \alpha $ 求导，使其等于 0，则就得到了
$$
\alpha_{k}=\frac{1}{2} \log \frac{1-e_{k}}{e_{k}}
$$
其中， $e_k$ 即为我们前面的分类误差率。
$$
e_{k}=\frac{\sum_{i=1}^{m} w_{k i}^{\prime} I\left(y_{i} \neq G_k\left(x_{i}\right)\right)}{\sum_{i=1}^{m} w_{k i}^{\prime}}=\sum_{i=1}^{m} w_{k i} I\left(y_{i} \neq G_k\left(x_{i}\right)\right)
$$
最后看样本权重的更新。利用 $f_{k}(x)=f_{k-1}(x)+\alpha_{k} G_{k}(x)$ 和 $w_{k i}^{\prime}=\exp \left(-y_{i} f_{k-1}(x_i)\right)$ ，即可得：
$$
w_{k+1, i}^{\prime}=w_{k i}^{\prime} \exp \left[-y_{i} \alpha_{k} G_{k}(x_i)\right]
$$
这样就得到了我们第二节的样本权重更新公式。
GBDT 详解
概述
GBDT 也是集成学习 Boosting 家族的成员，但是却和传统的 Adaboost 有很大的不同。回顾下 Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT 也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用 CART 回归树模型，同时迭代思路和 Adaboost 也有所不同。
在 GBDT 的迭代中，假设我们前一轮迭代得到的强学习器是$f_{t-1}(x)$ ，损失函数是 $L\left(y, f_{t-1}(x)\right)$ ，我们本轮迭代的目标是找到一个 CART 回归树模型的弱学习器 $h_t(x)$，让本轮的损失函数 $L\left(y, f_{t}(x)=L\left(y, f_{t-1}(x)+h_{t}(x)\right)\right.$ 最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
GBDT 的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
从上面的例子看这个思想还是蛮简单的，但是有个问题是这个损失的拟合不好度量，损失函数各种各样，怎么找到一种通用的拟合方法呢？
GBDT 的负梯度拟合
在上一节中，我们介绍了 GBDT 的基本思路，但是没有解决损失函数拟合方法的问题。针对这个问题，大牛 Freidman 提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个 CART 回归树。第 $t$ 轮的第 $i$ 个样本的损失函数的负梯度表示为
$$
r_{t i}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right) )}{\partial f\left(x_{i}\right)}\right]{f(x)=f{t-1}(x)}
$$
利用 $\left(x_{i}, r_{t i}\right) \quad(i=1,2, \dots m)$ ，我们可以拟合一颗 CART 回归树，得到了第 $t$ 颗回归树，其对应的叶节点区域 $R_{t j}, j=1,2, \cdots, J$ 。其中 $J$ 为叶子节点的个数。
针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的的输出值 $c_{tj}$ 如下：
$$
c_{t j}=\arg \min _ {c} \sum_{x_{i} \in R_{t j}} L\left(y_{i}, f_{t-1}\left(x_{i}\right)+c\right)
$$
这样我们就得到了本轮的决策树拟合函数如下：
$$
h_{t}(x)=\sum_{j=1}^{J} c_{t j} I\left(x \in R_{t j}\right)
$$
从而本轮最终得到的强学习器的表达式如下：
$$
f_{t}(x)=f_{t-1}(x)+\sum_{j=1}^{J} c_{t j} I\left(x \in R_{t j}\right)
$$
通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用 GBDT 来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
