Boosting算法基于如下理论：
在概率近似正确学习(probably approximately correct, PAC)的框架中，一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率仅比随机猜测略好，那么称这个概念是强可学习的。在PAC框架中，强可学习与弱可学习是等价的。
这意味着在学习中，如果已经发现了“弱学习算法”，那么可以提升(boost)为“强学习算法”。其中需要解决两个问题：
- 如何在每轮弱分类器的学习中改变训练数据的权值，即改变样本的概率分布；
- 如果将弱分类器组合成一个强分类器。
adaboost
adaboost(Adaptive Boosting)算法表述如下：
输入：训练数据集 $T={(x_1,y_1),\dots,(x_N,y_N)}$ ，其中 $x_i \in \mathcal{X} \subseteq \Re^n$ ， $y_i \in \mathcal{Y} = {-1, 1}$ ； 输出：分类器 $G(x)$ 。
(1) 初始化训练数据的权值为等权值分布：
\[D_1 = (w_{1,1},\dots,w_{1,N}), \, w_{1,i}=\frac{1}{N}, \, i=1,\dots,N\](2) 使用具有权值分布 $D_m$ 的训练数据集学习，其中， $m=1,\dots,M$ ，得到弱分类器：
\[G_m(x): \mathcal{X} \to \{-1,+1\}\]计算 $G_m(x)$ 的训练错误率(error rate)，即加和所有分类错误的权值：
\[e_m = P(G_m(x_i) \neq y_i) = \sum_{G_m(x_i) \neq y_i} w_{m,i}\]其中， $w_{m,i}$ 表示第 $m$ 轮中第 $i$ 个实例的权值，且 $\sum_{i=1}^N w_{m,i} = 1$ 。
计算 $G_m(x)$ 的系数(该系数即用于调整每次迭代时训练样本分布的新权值)：
\[\alpha_m = \frac{1}{2} \ln \frac{1-e_m}{e_m}\]以此系数更新训练样本的权值分布：
\[D_{m+1} = (w_{m+1,1},\dots,w_{m+1,N})\]其中，单个样本的权重 $w_{m+1,i}$ ，根据样本是否被错分，计算如下：
\[w_{m+1,i} = \left\{ \begin{array}{l l} \frac{w_{m,i}}{\sum_{j=1}^N w_{m,j}} e^{-\alpha_m}, & \quad G_m(x_i) = y_i \\ \frac{w_{m,i}}{\sum_{j=1}^N w_{m,j}} e^{\alpha_m}, & \quad G_m(x_i) \neq y_i \end{array} \right.\]这将使得正确分类的样本权重降低，而错误分类的样本权重升高，每次错误分类样本的权值将被放大 $e^{2\alpha_m} = e_m/(1-e_m)$ 倍。因此，错误分类的样本在下一轮学习中将发挥更大作用，adaboost总是基于错误来提升分类器性能。这里解决了第一个问题，即不改变训练数据，只是不断改变训练数据权值的分布，使得训练数据在弱分类器的学习中起不同的作用。
当错误分类数为0，或者错误率低于某个阈值，可以结束迭代，得到所有的弱分类器。
(3) 构建弱分类器的线性组合：
\[f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)\]得到最终的强分类器：
\[G(x) = {\rm sign}(f(x)) = {\rm sign} \left( \sum_{m=1}^M \alpha_m G_m(x) \right)\]其中， $y = \mathrm{sign}(x)$ 是符号判别函数， $x \in \Re, \, y \in {-1,1}$ 。
这里解决了第二个问题，即将弱分类器组合成一个强分类器。
小结：通常都认为adaboost和SVM是监督学习中最强大的两种方法。实际两者也有不少相似之处，并且原始的这两种算法都只能用于二元分类问题。如果我们把弱分类器想象成SVM的一个核函数，也可以按照最大化某个最小间隔的方法重写adaboost算法，而它们的不同也在于所定义的间隔计算方式有所不同，特别是在高维空间下更加明显。
具体实现
单层决策树 decision stump
参考
- 统计学习方法, 李航, 8. 提升方法