AdaBoost
这次再来记录一下什么是adaboost(Adaptive Boosting)，也是一个很早就知道用过的算法，一直没有仔细了解过，感谢林老师的课程，资料基本来自其课程内容，少量来自sklearn的官方文档。
开始前先贴一张表格，描述了一些算法之间的关系,文章主要顺着这个表格的次序来写，decision tree就略过了，改天重新写一个。
| aggregation type | blending | learning |
|---|---|---|
| uniform | voting | Bagging |
| non-uniform | linear | Adaboost |
| conditional | stacking | Decision Tree |
Blending
blending的中文意思是混合，核心思想也就是将一组弱分类器组合起来，得到更加有效和更加稳定的结果。当我们面对某一组训练数据，我们可以通过改变训练样本或学习算法，作出多个决策g，将这些g进行结合的方法包括几种：
- 取一般表现最好的分类器，即$$\begin{equation} G(X) = g_{t_i}(x) , t_i = \min_i E_{val}(g_t^-) \end{equation}$$
- 均匀混合各个分类器，即$$\begin{equation} G(X) = sign(\sum_{t=1}^T g_t(x)) \end{equation}$$
- 非均匀线性混合各个分类器，即$$\begin{equation} G(X) = sign(\sum_{t=1}^T \alpha_t g_t(x)) \end{equation}$$
- 条件混合各个分类器，即$$\begin{equation} G(X) = sign(\sum_{t=1}^T q_t(x) g_t(x)) \end{equation}$$
可以看到，第一种方案完全依赖于一个特别强的分类器，相当于我们通过做validation，确认一种最好的方案。而我们试图通过后三种方式，来混合得到更好的表现结果。
Uniform blending
uniform blending是一个很自然的想法，在classification场景下，
$$\begin{equation} G(X) = sign(\sum_{t=1}^T g_t(x))
\end{equation}$$
相当于让所有的弱分类器进行投票，得票最多的类别即为最终得到的类别。而在回归场景下，有
$$\begin{equation} G(X) = \dfrac{1}{T}(\sum_{t=1}^T g_t(x))
\end{equation}$$
仍然是一个类似投票的过程，我们认为对一组分类器的结果取平均值将由于我们选择其中某一个带来的结果，下面给一个简单的证明：
上文的叙述等价于以下数学表达式：
$$\begin{equation}
avg((g_t-f)^2) \ge (G-f)^2
\end{equation}$$
此处f为该处测试样本的实际值，G即为上文回归情况下，对所有弱分类器的平均值，即$ G=avg(g_t(x))$
我们将原不等式两边打开，其等价于如下式子：
$$\begin{aligned}
\Longleftrightarrow avg((g_t)^2 - 2f avg(g_t) +f^2 \ge G^2 -2fG + G^2 \\
\Longleftrightarrow avg(g_t)^2 - 2fG \ge G^2 - 2fG \\
\Longleftrightarrow avg(g_t)^2 \ge G^2
\end{aligned}$$
最后一个式子由均值不等式保证，故我们可以得知，如果我们以一组弱分类器的平均值作为最终的返回值，效果（与真实值的差异）一定好于我们随便选择其中一个预测来得更好，这就是我们使用blending方法的一点点理论保障。
Non-uniform blending
非均匀的混合方式也即我们为每个分类器的结果赋予不通的权值，以线性加权的结果作为最终的预测值。相比前一种，这个方法给了我们更多的自由度。我们只需要解决一个问题，即如何确定$\alpha$的值。其实这样的线性混合模型与一般的线性回归问题是类似的，我们仍旧通过最小化$E_{in}$来实现，即：
$$\begin{equation} \min_{\alpha_t \ge 0} \frac{1}{N}\sum_{n-1}^N(y_n - \frac{1}{T}\sum_{t=1}^T \alpha_t g_t(x_i))^2 \end{equation}$$这里除了约束条件外，与原先的线性回归问题几乎没有任何区别，我们只是将弱分类器们的权值作为了对特征的某一种转换，从而来试图得到更好的结果。
Selection and Stacking
stacking又被成为any blending，基本表述就是从训练集中我们找出T个分类器$g_1^-, g_2^-, … , g_n^-$，随后我们相当于做一次特征变换，将原来的样本$(x_n, y_n)$转化为$(z_n, y_n)$，其中$z=(g_1^-(x), g_2^-(x), …, g_n^-(x))$z，注意这里对所有g的选择将以validation的结果作为依据。
Bagging
learning类的方法与blending的方法的区别主要在于如何选取不同的弱分类器g，我们有多种选取g的方法，包括使用不同的决策模型(blendind)，对同一个模型使用不同的参数，某些算法天生带有随机性，或者选择不同的训练样本。
bagging的想法就主要基于选择不同的训练样本来得到不同的g，即每一次训练的时候不使用全部的样本，而是有选择的使用一部分。这里一个好的选择方式是使用统计学中bootsrap的方法，这详相当于一个有放回的组合问题，如果我们希望得到一个规模为N的训练集，则在原始样本中有放回地挑选N次，这样取出的集合就成为bootsrap。显然我们对N的大小并没有限制，可以大于或小于原始样本大小。
对于bagging算法而言，我们固定一个训练集合的大小，连续多次使用bootsrap的方法，得到一组训练集。随后我们选择一个分类算法A，分别在每一个训练集上训练，从而得到一组弱分类器，最终使用uniform blending的方法将他们组合起来，就是bagging算法返回的最终结果。
从直观上而言，bagging的每一步都只能分开一小部分样本，当我们连续多次使用后，就可以组合成为一个比较复杂的边界，帮助我们进行分类。前面提过，blending表现要好，最重要的是使得所有的$g_t$间的差异尽可能大，bootsrap帮助我们得到的结果就可以很好地满足这个条件。