二、AdaBoost算法的训练误差分析
通过前一节例子的学习,我们知道,AdaBoost最基本的性质是它能在学习过程中
不断减少训练误差 ,即不断减少在训练数据集上的
分类误差率 。接下来一起来看
两个定理: 定理一(AdaBoost的训练误差界):
AdaBoost算法
最终分类器的训练误差界 为:
(0式) (上面的公式乍一看不是很明白~一定要看推导,我会很详细地给出推导。现在先口头
理解一下: 上式左边一个不等式,右边一个等式;不等式的左边仔细一看,就是当前最终分类器
对训练样本的误分类率。行了,知道这个就好了~)
我们把上式中涉及到的
几个函数 列出来:
(1式) -------------最终分类器(包含M个弱分类器)
(2式) -----------M个弱分类器的线性组合
(3式) ----------规范化因子
好了,为了方便接下来的推导,我们还要回顾上一篇
涉及的 几个公式:
(4式) -----------初始化训练数据的权值分布为均匀分布。
(5式) -------更新权值分布。
(6式) -------(5式)变形。
有了上面的5个式子,放心大胆地推导吧。
“0式”左边不等式的证明:当
时,
,因而
,所以不等式很容易证明了。不用多说~
接下来证明“0式”右边的等式:
即
AdaBoost的训练误差界 为
。
这一定理说明,可以在每一轮选取适当的分类器
使得该轮对应的规范化因子
最小,从而使训练误差
下降最快 。
接下来具体介绍一下
二类分类问题 的训练误差界,看一下是多少。
定理二(二类分类问题AdaBoost的训练误差界):
直接上公式:
其中,
。
要证明这个定理,我们再来
引入 几个式子:
(7式) ----------基本分类器
的分类误差率就等于被错误分类样本对应的权值之和。
(8式) 并且
我们知道 当
时,
;当
时,
。
这样就可以开始证明了。
证明: 所以定理左边的等式得证。至于不等式:
则可先由
和
在点
处的
泰勒展开式 推出不等式:
,进而得到。
上面这两个定理就介绍完了,接着在介绍一个推论,了解一下即可~
推论: 如果存在
,使得对所有
都有
,则有最终分类器的分类误差率:
-------------推导很简单~
这表明在此条件下,AdaBoost的训练误差是以
指数速率下降 的。
注意:
AdaBoost算法不需要知道下界 。 这正是Freund与Schapire设计AdaBoost时所考虑的。与一些早期的提升方法不同,AdaBoost具有
适应性, 即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来,
Ada是Adaptive的简写。 下一篇将介绍 AdaBoost算法的另一种解释~