Adaboost

直观视角

提升方法是一种基于弱分类器的方法。它将若干个弱分类器按照一定的权重进行线性组合，提高分类器的性能，建立最终的模型。

一般来说，我们会改变数据的概率分布，即给予不同的权重，然后对不同权重的数据进行多次学习获得若干个弱分类器。最后对这若干个弱分类器进行加权线性组合。

这就引出了两个问题：如何改变数据的分布？如何确定弱分类器线性组合的权重？

直观上，我们会更加关注被误分类的数据点，因为其往往包含更多的信息。对于弱分类器，我们会更加偏向分类正确率高的分类器，给予其更高的权重。

其实，这就是Adaboost的思想。

数学视角

首先，我们假定数据$T=\{(x_1, y_1), ...,(x_N, y_N)\}​$。初始情况下，我们将数据分布设为均匀分布，即权重为

$D_1=(w_{11}, w_{12}, ..., w_{1N})=(\frac{1}{N},\frac{1}{N},..., \frac{1}{N})$。然后我们就可以构建第一个弱分类器$G_m(x):X\to\{-1, +1\}$。接下来，我们需要计算这个分类器的误分类率。因为我们对数据赋予了权重，误分类率也就是被误分类数据点的权重之和。$e_m=\sum\limits_{G_m(x_i)\neq y_i}w_{mi}$。然后计算分类器的权重，$\alpha_m=\frac{1}{2}ln(\frac{1-e_m}{e_m})$。从这公式中，我们可以看出，当$e_m\le 0.5$，$ln(\frac{1-e_m}{e_m})\ge 1$，即如果一个分类器的误分类率越小，赋予其的权重就越大，在最终分类的作用越大。当我们基于当前数据分布构建了一个弱分类器之后，我们需要重新确定数据的分布，对于被误分类的数据点给予更大的权重。$D_{m+1}=(w_{m+1, 1},..., w_{m+1, N})$，其中，$w_{m+1,i}=\frac{w_{m,i}}{Z_m}exp(-\alpha_my_iG_m(x_i))$, $Z_m=\sum\limits_{i=1}^Nw_{m,i}exp(-\alpha_my_iG_m(x_i))$。可以看出，$Z_m$只是为了使权重和为1。权重公式告诉我们，对于误分类点，即$y_i\neq G_m(x_i)$，新的权重会比原来的更大。在重新给予权重之后，就可以学习一个新的分类器了。

最终，我们获得了组合的分类器，即$f(x)=\sum\limits_{m=1}^M\alpha_mG_m(x)$, $G(x)=sign(f(x))$。