AdaBoost

李航《统计学习方法》
https://www.cnblogs.com/pinard/p/6133937.html
周志华《机器学习》

集成学习可以分为两大类：Bagging(Bootstrap aggregation) 和 Boosting。前者是并行的，后者是串行的。在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的，也就意味着，我们可以将弱学习算法提升为强学习算法。关于提升的方法有很多，这里我们讲述AdaBoost算法(Adaptive boosting algorithm)。
AdaBoost是Boosting族算法最著名的代表。AdaBoost提高前一轮被分错的样本的权值，降低前一轮被分正确的样本的权值，送到下一个分类器进行训练。最后将各个分类器加权多数表决，即赋予分类误差率越小的分类器更大的权值，使其在表决时话语权更大。AdaBoost最本质的性质是它能在学习过程中不断减少训练误差。
下面谈论的是AdaBoost的二分类问题。

伪代码如上图：

1. 初始化样本权值分布
2. 根据样本分布和样本数据训练出分类器ht$h_t$
3. 估计ht$h_t$的错误率
4. 根据错误率计算分类器ht$h_t$的权重
5. 更新样本分布，其中Zt$Z_t$是规范化因子
6. repeat 2-5步
7. 最终的分类器是各个分类器的线性组合

由(分类误差率<0.5)可以知道，分类器的错误率越高，那么它的权重越小，将来在做决策时的分量就小。
注意：所有分类器αt${\alpha }_t$相加起来并不为1，这里没有规范化操作。

AdaBoost二分类问题的损失函数优化
上面讲到了二分类AdaBoost的基学习器权重系数公式和样本权重更新公式。接下来，我们讲解这些是如何通过优化损失函数得到的。
AdaBoost为加法模型，损失函数为指数函数，学习算法是前向分步学习算法。
加法模型：最终的强分类器是若干个弱分类器加权得到
前向分步学习算法：我们的算法是通过一轮一轮的弱学习器学习（贪心策略），前面的分类器参数确定，通过优化损失函数来确定当前分类器的参数。
AdaBoost损失函数为指数函数，即：

因为学习的是加法模型，如果能够从前向后，每一步只学习一个基学习器及其系数，逐步逼近优化目标函数，那么就可以简化优化的复杂度。
利用前向分步学习算法的关系，可以得到损失函数为：

每步只需优化如上损失函数，注意：只有α$\alpha$和G(x)$G(x)$是参数。

确定α$\alpha$，求最优G(x)$G(x)$

此时的Gk(x)$G_k(x)$即为AdaBoost算法的基分类器，对应于它使得加权后的分类器分类误差率最小。
将Gk(x)$G_k(x)$带入并对α$\alpha$求导，使其等于0，便得到

AdaBoost小结：
Adaboost的主要优点有：

1. Adaboost作为分类器时，分类精度很高
2. 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
3. 作为简单的二元分类器时，构造简单，结果可理解
4. 不容易发生过拟合

Adaboost的主要缺点有：
对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。