基本思想

一轮轮训练弱分类器、把被前一轮分错的样本权重调高让后续分类器更重视这些难样本，最后再按各分类器的准确度加权投票把它们组合成一个强分类器。

算法步骤

输入：训练数据集 T=(x1,y1),(x2,y2),⋅⋅⋅(xn,yn)T={(x_1,y_1),(x_2,y_2),\cdot\cdot\cdot(x_n,y_n)}，其中xi∈χ⊆Rnx_i \in \chi \sube \bf R^n，yi∈Y={−1,+1}y_i \in \mathcal{Y} = \{-1, +1\}；弱学习器算法；

输出：最终分类器 G(x)G(x)

一、初始化训练数据的权值分布

D1=(w11,⋅⋅⋅,w1i,⋅⋅⋅w1n), w1i=1n, i=1,2,⋅⋅⋅nD_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

二、计算参数更新权值

  • 使用具有权值分布DmD_m的训练数据集学习，得到基本分类器Gm(x):χ→{−1,+1}G_m(x):\chi \rightarrow \{-1,+1\}

  • 计算Gm(x)G_m(x)在训练数据集上的分类误差率

em=P(Gm(xi)≠yi)=∑i=1nwmiI(Gm(xi)≠yi)e_m=P(G_m(x_i) \ne y_i)=\sum_{i=1}^n w_{mi}I(G_m(x_i) \ne y_i)

也就是：

em=∑i=1nwmi(Gm(xi)≠yi)∑i=1nwmie_m=\frac{\sum_{i=1}^n w_{m_i} (G_m(x_i) \ne y_i)}{\sum_{i=1}^n w_{m_i}}

AdaBoost规定下一轮的权重按下面规则更新（未归一化）：

wm+1i=wmi⋅e−αmyiGm(xi)w_{m+1i}=w_{mi} \cdot e^{-\alpha_my_iG_m(x_i)}

现在解释e−αmyiGm(xi)e^{-\alpha_my_iG_m(x_i)}：

  1. 如果分类正确，yi=Gm(xi)y_i=G_m(x_i)，所以yiGm(xi)=1y_iG_m(x_i)=1，指数变成e−αme^{-\alpha_m}，这是一个小于 1 的数，权重下降。

  2. 如果分类错误，yi≠Gm(xi)y_i \ne G_m(x_i)，所以yiGm(xi)=−1y_iG_m(x_i)=-1，指数变成eαme^{\alpha_m}，这是一个大于 1 的数，权重上升。

引入归一化常数ZmZ_m用来保证所有新权重加起来还是11

Zm=∑i=1nwmie−αmyiGm(xi)Z_m=\sum_{i=1}^n w_{mi} e^{-\alpha_my_iG_m(x_i)}

  • 计算Gm(x)G_m(x)的系数αm\alpha_m，我们先给出公式，后面在证明：

αm=12log1−emem\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}

  • 更新训练数据集的权值分布：

Dm+1=(wm+1,1,⋯ ,wm+1,i,⋯ ,wm+1,n)wm+1,i=wmiZmexp⁡(−αmyiGm(xi)),i=1,2,⋯ ,nD_{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

我们现在来证明系数αm\alpha_m

我们的目标是选择αm\alpha_m让这一轮整体损失最小，设置损失函数：

Lossm=∑i=1nwmiexp⁡(−αmyiGm(xi))Loss_m=\sum_{i=1}^n w_{mi}\exp(-\alpha_my_iG_m(x_i))

我们把ZmZ_m拆分成两部分：

把“分对的那些点”的索引集合记成 C (Correct),把“分错的那些点”的索引集合记成 W (Wrong).那么可以写成：Zm=∑i∈Cwm,ie−αm+∑i∈Wwm,ie+αm.把两堆权重分别合并一下：令Wright=∑i∈Cwm,i,Wwrong=∑i∈Wwm,i.注意：按定义，em=WwrongWright+Wwrong.而1−em=WrightWright+Wwrong.通常我们会把上一轮权重重归一化成 ∑iwm,i=1, 这样就直接有：Wwrong=em,Wright=1−em.\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}

所以我们得到：

Lossm=(1−em)e−αm+emeαmLoss_m=(1-e_m)e^{-\alpha_m}+e_me^{\alpha_m}

对αm\alpha_m求导并设为0得到：

αm=12log1−emem\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}

三、构建基本基本分类器的线性组合

f(x)=∑m=1MαmGm(x)f(x)=\sum_{m=1}^M \alpha_mG_m(x)

得到最终分类器：

G(x)=sign(f(x))=sign(∑m=1MαmGm(x))G(x)=sign(f(x))=sign(\sum_{m=1}^M \alpha_mG_m(x))