基本思想
一轮轮训练弱分类器、把被前一轮分错的样本权重调高让后续分类器更重视这些难样本，最后再按各分类器的准确度加权投票把它们组合成一个强分类器。
算法步骤
输入：训练数据集 T={(x_1,y_1),(x_2,y_2),\cdot\cdot\cdot(x_n,y_n)}，其中x_i \in \chi \sube \bf R^n，y_i \in \mathcal{Y} = \{-1, +1\}；弱学习器算法；
输出：最终分类器 G(x)
一、初始化训练数据的权值分布
D_1=(w_{11},\cdot\cdot\cdot,w_{1i},\cdot\cdot\cdot w_{1n}), \space w_{1i}=\frac{1}{n},\space i=1,2,\cdot\cdot\cdot n
二、计算参数更新权值
-
使用具有权值分布D_m的训练数据集学习，得到基本分类器G_m(x):\chi \rightarrow \{-1,+1\}
-
计算G_m(x)在训练数据集上的分类误差率
e_m=P(G_m(x_i) \ne y_i)=\sum_{i=1}^n w_{mi}I(G_m(x_i) \ne y_i)
也就是：
e_m=\frac{\sum_{i=1}^n w_{m_i} (G_m(x_i) \ne y_i)}{\sum_{i=1}^n w_{m_i}}
AdaBoost规定下一轮的权重按下面规则更新（未归一化）：
w_{m+1i}=w_{mi} \cdot e^{-\alpha_my_iG_m(x_i)}
现在解释e^{-\alpha_my_iG_m(x_i)}：
-
如果分类正确，y_i=G_m(x_i)，所以y_iG_m(x_i)=1，指数变成e^{-\alpha_m}，这是一个小于 1 的数，权重下降。
-
如果分类错误，y_i \ne G_m(x_i)，所以y_iG_m(x_i)=-1，指数变成e^{\alpha_m}，这是一个大于 1 的数，权重上升。
引入归一化常数Z_m用来保证所有新权重加起来还是1
Z_m=\sum_{i=1}^n w_{mi} e^{-\alpha_my_iG_m(x_i)}
-
计算G_m(x)的系数\alpha_m，我们先给出公式，后面在证明：
\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}
-
更新训练数据集的权值分布：
D_{m+1} = (w_{m+1,1}, \cdots, w_{m+1,i}, \cdots, w_{m+1,n}) \\ w_{m+1,i} = \frac{w_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(x_i)), \quad i = 1, 2, \cdots, n
我们现在来证明系数\alpha_m
我们的目标是选择\alpha_m让这一轮整体损失最小，设置损失函数：
Loss_m=\sum_{i=1}^n w_{mi}\exp(-\alpha_my_iG_m(x_i))
我们把Z_m拆分成两部分：
\begin{align} &\text{把“分对的那些点”的索引集合记成 } \mathcal{C}\ (\text{Correct}),\quad \text{把“分错的那些点”的索引集合记成 } \mathcal{W}\ (\text{Wrong}). \nonumber \\[6pt] &\text{那么可以写成：} \nonumber \\[4pt] &Z_m = \sum_{i \in \mathcal{C}} w_{m,i} e^{-\alpha_m} + \sum_{i \in \mathcal{W}} w_{m,i} e^{+\alpha_m}. \nonumber \\[10pt] &\text{把两堆权重分别合并一下：令} \nonumber \\[4pt] &W_{\text{right}} = \sum_{i \in \mathcal{C}} w_{m,i}, \qquad W_{\text{wrong}} = \sum_{i \in \mathcal{W}} w_{m,i}. \nonumber \\[10pt] &\text{注意：按定义，} \nonumber \\[4pt] &e_m = \frac{W_{\text{wrong}}}{W_{\text{right}} + W_{\text{wrong}}}. \nonumber \\[10pt] &\text{而} \nonumber \\[4pt] &1 - e_m = \frac{W_{\text{right}}}{W_{\text{right}} + W_{\text{wrong}}}. \nonumber \\[10pt] &\text{通常我们会把上一轮权重重归一化成 } \sum_i w_{m,i} = 1, \text{ 这样就直接有：} \nonumber \\[4pt] &W_{\text{wrong}} = e_m, \qquad W_{\text{right}} = 1 - e_m. \nonumber \end{align}
所以我们得到：
Loss_m=(1-e_m)e^{-\alpha_m}+e_me^{\alpha_m}
对\alpha_m求导并设为0得到：
\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}
三、构建基本基本分类器的线性组合
f(x)=\sum_{m=1}^M \alpha_mG_m(x)
得到最终分类器：
G(x)=sign(f(x))=sign(\sum_{m=1}^M \alpha_mG_m(x))