集成学习
Published:
集成学习的思想是采用若干的较弱的分类器集成为一个较强的分类器，本文主要以二分类问题为例，重点介绍AdaBoost算法的推导过程和训练误差上界。
Hoeffding‘s Inequality
可以先由一个不等式引入，介绍集成学习的思想。
如果有$n$个$i.i.d$的分类器$h_i(x)$，采用投票法进行集成，最终的结果假设为$H(x) = \text{sign}(\sum h_i(x))$, 假设每个基分类器的正确率为$p$,
根据 Hoeffding不等式 可以给出其误差上界， \(\begin{align} P(S_n - ES_n \le -t) \le \exp(-\frac{2t^2}{\sum_i (b_i-a_i)^2}) \end{align}\)
每个基分类器分类正确的事件为一个二项分布，因此代入上述不等式，
\[\begin{align} P(S_n - np \le -nt) &\le \exp(-2nt^2) \\ \text{With } ES_n &= np, [a_i,b_i] = [0,1] \end{align}\]而最终集成后的分类器错分的概率等价于，
\[\begin{align} P(H(x) \ne f(x)) &= P(S_n \le \frac{n}{2}) \\ &= P(S_n \le n(p-t)) , \text{With } t = p- \frac{1}{2} \\ & \le \exp(-2n(p-\frac{1}{2})^2) \\ \end{align}\]从最后的式子中可见，当$n$越大的时候，集成后的分类器错分的概率成指数级下降，也即当基分类器独立的时候，集成学习可以获得很好的效果，但在实际机器学习任务中，基分类器往往并不独立，这时候需要设计好的算法，著名的方法有Boosting和Bagging等。
Boosting
Boosting的想法来自基于上一个基学习器的学习结果对数据的分布进行改变，从而训练下一个基学习器。
Exponential Loss
AdaBoost是Boosting方法中的代表，其可以从加性模型在指数损失下推导得到，其中加性模型指的是基分类器采用加法的方式集成，并且每次在最小化损失函数的前提下训练得到新的基分类器： \(\min_{G,\alpha} L(y,\sum_i\alpha_iG_i(x))\)
在AdaBoost算法中，采用的损失函数为指数损失，而最终的分类结果采用$\text{sign} f(x)$
\[L(y,f(x)) = \exp(-f(x)y)\]指数损失有很好的性质，首先指数损失是$0-1$损失函数的凸上界，
\[\begin{align} \exp(-f(x)y) & \ge 1 , \text{sign}(f(x)) \ne y \\ \exp(-f(x)y) & \ge 0, \text{sign}(f(x)) = y\\ \text{Hence,} \exp(-f(x) y) &> I(f(x) \ne y) \end{align}\]再者对指数损失进行优化，得到的最优分类器，和直接使用0-1损失优化的结果是相同的，这被称为Bayes一致损失，由于按照0-1损失计算得到的分类器是Bayes最优分类器。
首先可以简要证明，Bayes最优分类器等价于选择概率最大的一类，也等价于最小化0-1损失函数，
\[\min E [I(f(x) \ne y)] = \max E[I(f(x) = y)] = \max P(f(x)=y )\]再者我们来看指数损失，选择最优的$f(x)$，我们采用求导的方式，
\[\begin{align} \mathcal{L} &= E[L(y,f(x))] = P(y=1) \exp(-f(x)) +P(y=-1) \exp(f(x)) \\ \frac{d \mathcal{L}}{df} &= -P(y=1) \exp(-f(x)) + P(y=-1) \exp(f(x)) =0\\ \end{align}\]对驻点的等式进行化简，
\[\begin{align} P(y=1) \exp(-f(x)) &= P(y=-1) \exp(f(x)) \\ \log P(y=1) - f(x) &= \log P(y=-1) + f(x) \\ f(x) &= \frac{1}{2} \log \frac{P(y=1)}{P(y=-1)} \end{align}\]最后使用$\text{sign} f(x)$进行分类，可以发现该结果的确为Bayes最优的结果，
\[\begin{align} \text{sign}(f(x)) &= 1, P(y = 1) > P(y=-1) \\ \text{sign}(f(x)) &= -1, P(y = 1) < P(y=-1) \\ \text{Hence } \text{sign}(f(x)) &= \max P(f(x) = y) \end{align}\]AdaBoost
上述推导给出了指数损失的合理性，本节我们利用指数损失，推导出AdaBoost的公式。
\[\min_{G,\alpha} E[L(y,\sum_i\alpha_iG_i(x))] = \min_{G,\alpha} E[\exp(-y \sum_i\alpha_iG_i(x))]\]考虑串行地逐次优化，当优化至基分类器$G_m$的时候，将与本次优化无关的量记作$w_{im}$,
\[\begin{align} &\min_{G_m, \alpha_m} \sum_i w_{im} \exp(-y \alpha_m G_m(x)) = E_{x \sim w_m} L(y,\alpha_m G_m(x))\\ \text{With }& w_{im} =\exp(-y \sum_{i=1}^{m-1}\alpha_iG_i(x) ) \end{align}\]可以注意到$w_{im}$ 相当于对数据$x$ 重新赋予了一个采样的权重，每次应该对其进行归一化，并且可以采用递推式进行更新，
\[\begin{align} w_{i,m+1} &= \frac{w_{i,m} \exp(-y \alpha_m G_m(x))}{Z_m} \\ \text{With } Z_m &= \sum_i w_{i,m} \exp(-y \alpha_m G_m(x)) \end{align}\]上式中的$Z_m$为每次计算得到的归一化常数，也即每一轮的优化目标，下面通过计算得到$G_m(x)$的训练方法，
\[\begin{align} \min_{G_m, \alpha_m} Z_m =&\min_{G_m, \alpha_m} \sum_i w_{im} \exp(-y \alpha_m G_m(x)) \\ =& \min_{G_m, \alpha_m} \sum_{G_m(x_i) = y_i} w_{im} \exp(-\alpha_m) + \sum_{G_m(x_i) \ne y_i} w_{im} \exp(\alpha_m) \\ =& \min_{G_m, \alpha_m} \sum_i w_{im} \exp(-\alpha_m)(1-I[G_m(x_i) \ne y_i]) + \sum_i w_{im} \exp(\alpha_m) I[G_m(x_i) \ne y_i ] \\ =& \min_{G_m,\alpha_m} \exp(-\alpha_m) + (\exp(\alpha_m) - \exp(-\alpha_m)) \sum_i w_{im} I[G_m(x_i) \ne y_i ] \\ =&\min_{G_m,\alpha_m} \exp(-\alpha_m) + (\exp(\alpha_m) - \exp(-\alpha_m)) e_m \\ \text{With } e_m =& \sum_i w_{im} I[G_m(x_i) \ne y_i] \\ \end{align}\]首先关注于$G_m(x)$，因此忽略和$\alpha_m$相关的项，
\[\begin{align} & \min_{G_m} \exp(-\alpha_m) + (\exp(\alpha_m) - \exp(-\alpha_m))e_m = \min_{G_m} e_m \end{align}\]定义带权重的错误率$e_m$，每次的$G_m(x)$相当于最小化$e_m$, 而对于$\alpha_m$同样对其求导，
\[\begin{align} L &= \min_{G_m,\alpha_m} \exp(-\alpha_m) + (\exp(\alpha_m) - \exp(-\alpha_m)) e_m\\ \frac{dL}{d \alpha_m} &= -\exp(-\alpha_m) +(\exp(\alpha_m)) +\exp(-\alpha_m)) e_m =0 \end{align}\]化简可以得到在指数损失的Bayes一致性相似的结果，
\[\begin{align} \exp(-\alpha_m) &=(\exp(\alpha_m)) +\exp(-\alpha_m)) e_m \\ \exp(-\alpha_m)(1-e_m) &= \exp(\alpha_m) e_m \\ -\alpha_m + \log (1-e_m) &= \alpha_m + \log e_m \\ \alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m} \end{align}\]综上我们就得到了AdaBoost的算法全过程，
\[\begin{align} w_{i,m+1} &= \frac{w_{i,m} \exp(-y \alpha_m G_m(x))}{Z_m} ,\text{With } Z_m = \sum_i w_{i,m} \exp(-y \alpha_m G_m(x)),w_{i,1} = \frac{1}{N} \\ G_m(x) &= \text{argmin } e_m, \text{With } e_m = \sum_i w_{im} I[G_m(x_i) \ne y_i ] \\ \alpha_m & = \frac{1}{2} \log \frac{1-e_m}{e_m} \end{align}\]上述更新过程有明显的含义，
- $w_{i}$ 表示对于数据$x$所赋予的权重，当上一轮将其错分类，其权重将变大
- $G_m(x)$ 通过最小化带权的错分率$e_m$训练得到
- $\alpha_m$表示每个基分类器的贡献，其错分率$e_m$越小，该分类器的贡献越大
最终算法将输出一个集成后的加性模型，
\[G(x) = \sum_m \alpha_m G_m(x)\]Upper bound for Loss
本节讨论AdaBoost算法中训练误差的上界，最终将得到和Hoeffding不等式类似地指数型下降的结果，证明集成学习的威力。
\[\begin{align} E I[G(x) \ne y] &= E I[\sum_m \alpha_m G_m(x) \ne y] \\ & \le E \exp (-y \sum_i \alpha_m G_m(x)) \\ &= \prod_m Z_m , \text{By Def of } Z_i \\ &= \prod_m \exp(-\alpha_m) + (\exp(\alpha_m) - \exp(-\alpha_m)) e_m \\ &= \prod_m \exp(\alpha_m) e_m +\exp(-\alpha_m) (1-e_m) \\ &= \prod_m 2 \sqrt{e_m(1-e_m)} ,\text{With } \alpha_m = \frac{1}{2} \log \frac{1-e_m}{e_m} \\ &= \prod_m \sqrt{1-(2e_m-1)^2} \\ &\le \prod_m \exp(-\frac{1}{2} (2e_m-1)^2) , \text{By} \sqrt{1-x} \le \exp(-\frac{x}{2} ) \\ &= \prod_m \exp(-2 (e_m - \frac{1}{2} )^2) \\ &= \exp(-2 \sum_{i=1}^m (e_m- \frac{1}{2} )^2) \end{align}\]最后几步化简得原因是对于$Z_m$最优的$G_m(x),\alpha_m$已经在更新公式中求出。
可以看见，$ \frac{1}{2} - e_m $ 表示分类器相较于随机分类的误差率的提升，该误差率的提升越低，可以给出的泛化误差的上界将更紧。
Bagging
Bagging基于自助法（Bootstrapping），对于样本量为$m$的数据集，采用有放回的$m$次重抽样得到新的数据集，此时每个样本包含在新数据集中的概率约为，
\(\lim_{m \rightarrow \infty} 1-(1-\frac{1}{m})^m = 1-\frac{1}{e}\) 因此新的数据集约包含$1-\frac{1}{e}$比例的样本量，此时不包含在数据集中的样本被称为包外样本（Out-of-Bag），可以用来做模型评估等作用。Bagging每次从样本中抽样，训练得到基分类器，最终将分类器集成。
相较于串行的提升方法Boosting，Bagging是一个并行的训练方法。而从偏差-方差分解的角度来看，Boosting针对于利用加性模型等逐步减小模型的偏差，而Bagging更重要的是针对于方差的减小。
Random Forest
随机森林是Bagging在决策树上的延申，不仅对于数据作自助法重抽样，同时对决策树中的决策变量集合也做重抽样，可以训练得到独立性更强的基分类器，从而获得更好的集成学习效果。