adaboost

adaboost原理

adaboost通过集成弱分类器来最终实现一个强分类器。

以下的讨论局限于二分类问题。并且注意正类标记为1,负类标记为-1。

弱分类器:优于随机水平。事实上,这很容易达到,因为对于低于随机水平的,只需要反转预测的label就可以高于随机水平了。

adaboost是一个加法模型,最终模型形如:
$$F(x) = \sum_{t=1}^T \alpha_t h_t(x)$$
$$H(x) = sign[F(x)]$$
其中,T是总迭代次数。$\alpha$是模型的权重,也就是需要求解的模型参数之一。另一部分参数就是各个基分类器。

我们的优化目标自然是最小化误差:
$$\arg \min Err(H;D) = \arg \min \frac{1}{m} \sum_{i=1}^m I(h(x_i) \neq y_i)$$
其中,m是样本数。

权重调整

adaboost通过调整误分类样本权重重新建模,来改进模型效果。
初始权重为$\frac{1}{m}$。

通过如下公式进行权重调整:
$$D_{t+1}(i) = \frac{1}{Z_t} D_t(i) \exp[-\alpha_t y_i h_t(x_i)]$$
其中,$Z_t$是规范化因子,保证权重大于等于0,和为1。$D_t(i)$是t轮迭代的样本权重。显然,当预测正确时,$y_i h_t(x_i) = 1$,新权重会减小;预测错误时,$y_i h_t(x_i) = -1$,新权重会增大。

因此,可以得到递推公式:
\begin{split} D_{t+1}(i) &&= \frac{1}{Z_t} D_t(i) \exp[-\alpha_t y_i h_t(x_i)] \newline
&&= \frac{1}{Z_t Z_{t-1}} D_{t-1}(i) \exp[-y_i(\alpha_t h_t(x_i) + \alpha_{t-1} h_{t-1}(x_i))] \newline
&&= \frac{1}{Z_t … Z_{1}} D_{1}(i) \exp[-y_i(\alpha_t h_t(x_i) + …+\alpha_{1} h_{1}(x_i))] \newline
&&= \frac{1}{Z_t … Z_{1}} D_{1}(i) \exp[-y_i F(x_i)] \end{split}

左右两边同时求和有:
\begin{split} 1 = \sum_{i=1}^m D_{t+1}(i) = \frac{1}{Z_t … Z_{1}} \frac{1}{m} \sum_{i=1}^m \exp[-y_i F(x_i)] \end{split}
\begin{split} Z = Z_t … Z_{1} = \frac{1}{m} \sum_{i=1}^m \exp[-y_i F(x_i)] \end{split}

adaboost误差上界

adaboost通过优化误差上界来优化模型效果。

下面证明:
$$ Err(H) = \frac{1}{m} \sum_{i=1}^m I(h(x_i) \neq y_i) \leq Z = \frac{1}{m} \sum_{i=1}^m \exp[-y_i F(x_i)]$$

证明如下:

对于求和的每一项有:
\begin{split} \text{If } H(x_i) \neq y_i \text{ then the LHS } = 1 \leq \text{RHS } = e^{+|F(x_i)|} \newline
\text{If } H(x_i) = y_i \text{ then the LHS } = 0 \leq \text{RHS } = e^{-|F(x_i)|} \end{split}
显然求和后不等式依旧成立。故而得证。

因此,我们的问题转化为优化Z。同时,我们采用step-wise的方法去进行优化,也就是逐步优化$Z_1,Z_2,Z_3,…,Z_t$。

权重系数求解

对$Z_t$最小化,令导数为0。

\begin{split} Z_t(\alpha_t,h_t) &&= \sum_{x_i \in A} D_t(x_i) exp[-\alpha_t] + \sum_{x_i \in \bar{A}} D_t(x_i) exp[-\alpha_t] \newline
\frac{d Z_t(\alpha_t,h_t)}{d \alpha_t} &&= \sum_{x_i \in A} -D_t(x_i) exp[-\alpha_t] + \sum_{x_i \in \bar{A}} D_t(x_i) exp[-\alpha_t] = 0 \newline
\sum_{x_i \in A} D_t(x_i) &&= \sum_{x_i \in \bar{A}} D_t(x_i) exp[2 \alpha_t] \end{split}

我们定义加权误差:
\begin{split} \epsilon_t(h) = \sum_{i=1}^m D_t(x_i)I(h(x_i) \neq y_i) = \sum_{x_i \in \bar{A}} D_t(x_i) \end{split}

因此有:
\begin{split} \alpha_t = \frac{1}{2} \ln \frac{1-\epsilon_t(h_t)}{\epsilon_t(h_t)} \end{split}

由于每个分类器都要求是弱分类器。也就是要求每个基分类器的 加权误差率 小于0.5。
因此,$\alpha_t$显然都大于0。

误差分析

将解出的权重系数带回:

\begin{split} Z_t(\alpha_t,h_t) &&= \sum_{x_i \in A} D_t(x_i) exp[-\alpha_t] + \sum_{x_i \in \bar{A}} D_t(x_i) exp[-\alpha_t] \newline
&&= (1-\epsilon_t(h_t))\sqrt{\frac{\epsilon_t(h_t)}{1-\epsilon_t(h_t)}} + \epsilon_t(h_t)\sqrt{\frac{1-\epsilon_t(h_t)}{\epsilon_t(h_t)}} \newline
&&= 2\sqrt{\epsilon_t(h_t) (1-\epsilon_t(h_t))}\end{split}

令:
\begin{split} \gamma_t = \frac{1}{2} - \epsilon_t(h_t) , \gamma_t \in (0,\frac{1}{2}]\end{split}

则有:

\begin{split} Z_t(\alpha_t,h_t) &&= 2\sqrt{\epsilon_t(h_t) (1-\epsilon_t(h_t))} \newline
&&= \sqrt{1-4\gamma_t^2} \newline
&& \leq \exp[-2 \gamma_t^2]\end{split}

因此:

\begin{split} Err(H) \leq Z \leq \exp[-2\sum_{t=1}^T \gamma_t^2] \end{split}

随着迭代次数增加,误差上界以指数级减小。

过拟合问题

adaboost在使用中常常不容易过拟合。也就是说验证集可以随着训练集精度提升而提升,并不存在一个下降的拐点。

一些相关的理论解释:

作者:知乎用户
链接:https://www.zhihu.com/question/41047671/answer/127832345
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
AdaBoost提出的论文对AdaBoost的泛化界进行了分析,使用了通常的学习器泛化界:
泛化错误(泛化错误可理解为测试错误) < 训练错误 + 学习算法容量相关项 (1)
由(1)式可见,当训练错误不变时,应当选择简单的学习模型,从而减少学习算法容量。然而在实验中已经观察到,在一些情况,训练错误已经是0了,继续训练还能进一步减小泛化错误,这里的继续训练意味着增加学习算法容量,理应导致泛化错误上升才对。因此(1)直接套上AdaBoost是解释不通的。更有JMLR 2008的论文发现,更多的实验观察与Boosting的理论及其统计解释都不符合,例如使用多层的决策树竟然比使用一层的简单决策树更好。理论不能解释实验肯定是理论的问题,于是人们觉得,(1)式不够好,可能把更加细微的因素忽略了。
于是AdaBoost的作者针对这一情况,提出了新的学习器泛化界:
泛化错误 < 训练Margin项 + 学习算法容量相关项 (2)
(1)中的训练错误是指一个数据样本分类对了就是0,错了就是1,而(2)里的“训练Margin”不仅看分类对错,还要看对的信心有多少,例如对于一个正类+1,分类器A输出+0.1,B输出+2,虽然都分类正确了,但B的信心更多。这样(2)就比(1)更加细致的刻画了学习器的表现。实验一看,果然AdaBoost在训练错误为0后,继续训练不能再减少训练错误了,确能够进一步减少训练Margin,也就是信心更足了。
看似解决了AdaBoost不容易过拟合的问题,然而好景不长,统计大牛Leo Breiman(bagging,random forest出自他手)来了个比 (2) 更紧的界(更紧就是更接近真实):
泛化错误 < 训练Margin的最小值 + 学习算法容量相关项 (3)
(3)的容量相关项目更小,但这不是关键,关键是根据这一理论,就应该去看训练Margin的最小值,也就是分类器在所有样本上信心最不足的那个。然而根据这一理论,Breiman设计了另一种Boosting算法arc-gv,最小训练Margin更小了,但实验效果比AdaBoost差了很多。于是乎Breiman的结论是,这个用训练Margin来刻画泛化错误整个就是不对的。大家都傻眼了,AdaBoost不容易过拟合的问题无解了。
7年之后。。。AdaBoost作者之一的工作发现,Breiman的实验竟然有问题:没有很好的控制决策树的复杂性,也就是说,AdaBoost和arc-gv关于“学习算法容量相关项”的值并不一样,虽然arc-gv的最小训练Margin更小,但后面一项更大啊,因此泛化错误就更大了。于是重做实验,都用一层决策树,这样后面一项都一样了,一看AdaBoost更好了,也就是说原来的Margin理论并没有错误,松了口气。该论文获ICML’06最佳论文奖。
但是这篇最佳论文奖并没有终结问题,当都用一层决策树时,AdaBoost的最小训练Margin比arc-gv还要小,也就是说,并没有否定(3)式。然而在实验中,最小化这个最小Margin的效果并不好。这篇论文也指出,可能要看Margin的分布,也就是算法在所有样本上的信心,而不是最差的那个样本上的信心。但这只是“可能”,理论研究者最求的是更紧的界。接下来都是我国研究者的贡献了,北京大学王立威等人的到了比(3)更紧的界,其中“训练Margin的最小值” 被替代为 “训练Margin的某一个值”,这某一个要解一个均衡式,但不管怎么说,最小Margin被替代掉了。南京大学的高尉和周志华教授推导出了“第k Margin界”,(3)和 “训练Margin的某一个值” 都是其k赋特定值的特例,并由此得到了基于“算法在所有样本上的信心”的界,比(3)式更好。
以上内容可见:CCL2014_keynote-周志华
Margin理论讨论的主要是学习算法在训练样本上的信心,学习算法的容量是不是随着训练轮数的增加而增加呢,其实并不一定,近来有工作表明,有差异的学习器的组合,能够起到正则化的作用,也就是减少学习算法容量(Diversity regularized ensemble pruning. ECML’12; On the Generalization Error Bounds of Neural Networks under Diversity-Inducing Mutual Angular Regularization)。在许多variance-bias 分解实验中也观察到,AdaBoost不仅是减少了bias,同时也减少了variance,variance的减少往往与算法容量减少有关。
总之这一方面还值得进一步探索,新原理的发型,有可能导致新型高效学习算法的发明,意义重大。

references

boosting and adaboost

adaboost为什么不容易过拟合呢?