集成学习：AdaBoost, Bagging与Random Forest
近日翻书学习了一下集成学习相关的内容，在此做简单记录。
集成学习
集成学习通过构建并结合多个学习器来完成学习任务。——西瓜书
在集成学习中，首先需要根据学习任务构建多个弱学习器，这些弱学习器对学习任务有一定的泛化性能，可以是同质的（全部使用相同的学习算法），也可是异质的（使用多种学习算法）。将这些弱学习器（称个体学习器）通过某种方式组合起来作为一个学习器完成学习任务，即集成学习。通常要求集成学习要取得比组成它的弱学习器更优的泛化性能。
设计上个体学习器有如下要求：
- 准确性
- 多样性
这两个要求本身是对立的，增加多样性的同时必然会影响准确性，因此设计个体学习器的核心是如何权衡这二者。这属于集成学习研究核心问题，此处不作展开。
集成学习的代表算法有如下：
- AdaBoost（Boosting族算法之一）
- Bagging
- Random Forest（随机森林）
AdaBoost
AdaBoost是一种Boosting算法，其在$T$轮迭代中连续生成$T$个基学习器（同质集成学习中的个体学习器），根据基学习器的性能$\epsilon$确定基学习器权重$\alpha_t$，同时确定样本权重$D_m(x)$。在下一轮迭代中，使用带权重的样本训练下一个基学习器。
样本权重$D_m(x)$的引入，使得每轮迭代都更关注上一轮迭代中的基学习器做错的样本，令新一轮迭代生成的基学习器性能进行提升。其本质上是通过$D_m(x)$改变训练样本的分布，更突出前一轮训练中失败的样本，在后一轮作为重点。
基学习器权重$\alpha_t$的引入，使最终集成的学习器中更重视性能好的基学习器，而性能则通过$\epsilon$进行刻画，$\epsilon$是基学习器的错误率。$\alpha_t$的确定遵从“错误率低的基学习器占权重高”这一思想。错误率同样影响了下一轮样本权重的更新。
算法
最终目的是生成形如$H(x) = \sum_{t=1}^T \alpha_t h_t(x)$的集成学习器，因此我们需要计算所有的$\alpha_t$和$h_t(x)$。
在所有迭代的最开始，所有训练样本都是平等的，因此权重均分。假设有$N$个样本：
$$
D_1(x) = \frac{1}{N}
$$然后开始$T$轮迭代，每轮生成第$t$个基学习器：
$$
h_t(x) = New\space Learner(D_t)
$$判断$h_t(x)$的性能如何，计算错误率$\epsilon_t$：
$$
\epsilon_t = P\left(h_t(x)\neq y\right)
$$以$\epsilon$为指导，更新学习器权重与样本权重：
$$
\alpha_t = \frac{1}{2} \ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right)
$$更新样本权重$D_t(x)$，$Z_t$为归一化因子，使每次$D_t(x)$都为归一化的权重：
$$
D_{t+1}(x) = \frac{D_t(x) e^{-\alpha_t h_t(x) y}}{Z_t} \
Z_t = \sum_x D_t(x)e^{-\alpha_t h_t(x) y}
$$达到迭代上限，得到集成学习器$H(x) = \sum_{t=1}^T \alpha_t h_t(x)$。
推导与理解
有关学习器权重$\alpha_t$和样本权重$D_t(x)$的推导由最小化指数损失函数得出。
其一：Why exponential?
指数损失函数如下所示：
$$
loss = \sum_{i=1}^N e^{-y_i h(x_i)}
$$
表达式很好解释，以分类器为例：分类正确时预测结果和标签同号，指数为负，损失较小；分类错误时预测结果和标签异号，损失较大。
为何AdaBoost要使用指数损失？实际上这也是我最开始困扰的问题，至今也没有想明白，查阅了很多资料，都只是说明AdaBoost使用改损失作为优化对象，并未提及原因。
Wikipedia上对指数损失的解释如下：
The exponential loss is convex and grows exponentially for negative values which makes it more sensitive to outliers. The exponential loss is used in the AdaBoost algorithm.
仅仅提到指数损失的凸性以及指数型增长对于异常值的敏感度高。我猜想是利用了指数函数对正常值的低敏感度和对异常值的高敏感度，实现算法描述的“关注做错的样本”，不知思路是否如此，这里就先记住吧…
其二：一些数学
下面正式推导$\alpha$和$D(x)$更新的表达式。
总体思路像其他很多机器学习算法推导一样，依旧是最小化损失函数，AdaBoost采用指数损失。
考虑到AdaBoost使用多个基学习器做线性组合，每个加了权重的基学习器都希望尽可能减少损失，那么不妨从第$t$轮迭代生成的带权重基学习器$\alpha_t h_t(x)$入手，其在整个训练集上的平均损失为：
$$
loss = \mathbb{E}_{x\sim D_t} \left[e^{-y\alpha_th_t(x)}\right]
$$
AdaBoost使用了期望损失，考虑了分类正确和分类错误样本的权重对于损失的影响，这也反映了“关注做错样本”的设计思想。
我们考虑二分类器的情况，标签与预测结果取值只有${+1, -1}$，将上式展开，自然得到错误率$\epsilon_t$的引入：
$$\begin{aligned}
loss &= \mathbb{E}_{x\sim D_t} \left[e^{-y\alpha_th_t(x)}\right] \
&= \sum_i p(x_i) e^{-y_i\alpha_th_t(x_i)} \
&= \frac{n_s}{N}e^{-\alpha_t} + \frac{n_d}{N}e^{\alpha_t} \
&= (1-\epsilon_t)e^{-\alpha_t} + \epsilon_t e^{\alpha_t}
\end{aligned}$$
其中$n_s$和$n_d$分别表示$N$个样本中被$h_t$分类正确和分类错误的样本个数，从而引入错误率$\epsilon$。
然后对$\alpha_t$求导为零，得到$\alpha_t$，形式很简单：
$$
\frac{\partial loss}{\partial \alpha_t} = (\epsilon_t - 1) e^{-\alpha_t} + \epsilon_t e^{\alpha_t} = 0 \
\alpha_t = \frac{1}{2} \ln{\left(\frac{1-\epsilon_t}{\epsilon_t}\right)}
$$
至此推得每个基学习器的权重$\alpha_t$，它由当前基学习器错误率决定，本质上由基学习器的性能决定，即前文提到的“错误率低的基学习器占权重高”思想。
样本权重$D_t(x)$的更新就好理解了。利用指数损失的敏感性，针对那些分类出错的样本，我们增加对它们的“关注”，即提高权重，对分类正确的样本减少权重，所以$D_t(x)$直接与损失函数相乘即可，外加一个归一化因子：
$$
D_{t+1}(x_i) = \frac{1}{Z_t} D_t(x_i) e^{-y_i \alpha_t h_t(x_i)}
$$
至此基本的二分类AdaBoost推导完成。对其做些修改可得多分类和回归任务中的改进算法，此处不表。
Bagging
前文AdaBoost思想即Boosting（提升），在连续迭代中优化基学习器，最后将他们组合起来。
告别AdaBoost，换一种方式思考集成学习，从独立性入手得到Bagging算法，它比AdaBoost好理解很多。
Bagging的思想是对训练集做多组有放回的采样，从而得到多个子训练集，使用每个子训练集构建一个基学习器，最后得到一组基学习器。在预测时，对于分类任务按照“少数服从多数”决策，对回归任务则采用求平均值进行决策。
此外，Bagging在确定子训练集的同时确定了未使用的样本，这些样本可用作验证集检验基学习器性能。
Random Forest
Random Forest即随机森林，属于一种Bagging算法，其将决策树和Bagging方法结合，加入了随机因素。
传统决策树在每个分支节点计算所有属性的信息增益进行分支，随机森林则随机选取一个所有属性的子集，用子集计算信息增益进行分支。通过该方法构建一系列决策树，然后进行决策，即随机森林算法。