本节证明并未从集成学习源头开始,如若对集成学习还不是很清楚的同学,参考文章:
AdaBoost算法证明
本文以周志华西瓜书推导过程为例,以“
加性模型”(additive model)进行解析:
将基学习器
ht(x)线性组合,则基学习器的线性组合表示为如下
H(x)形式:
定义整个学习器的损失函数为指数损失函数(
exponential loss function),期望指数损失函数最小化:
其中
f ff是真实函数,
yi∈{−1,+1},
D 表示样本的权值分布(对于错误的样本权重要高一点,正确的样本权重要低一点,所有的样本组合起来就相当于有一个分布)。
若基学习器的线性组合
H(x)能够使得指数损失函数最小化,一般的做法就是求偏导数,令其等于零,求解。由于
f ( x ) 取值只有两种,所以其求偏导数之后的结果如下所示:
这意味着若指数损失函数最小化,则分类错误率也将最小化。说明指数损失函数是原任务的替代函数,但由于其连续可微,所以用它替代
0/1
损失函数作为优化目标。上面这么多就是说接下来用这个连续的指数损失函数做进一步的处理。
在AdaBoost算法中,第一个基分类器
h1通过直接将基学习算法用于初始数据分布而得到;之后的
ht和
α t 是通过迭代生成得到的。当基分类器
ht基于分布
Dt产生之后,基分类器的权重
αt应该使得
αtht最小化指数损失函数,只有
αt在判断错误的基分类器给予较小权值,判断正确的基分类器给予较大权值,才能使得
H(x)具有较准确的判断,从而最小化指数损失函数
其实就是误判率。为了求得基分类器的权重,对其求导:
到这里相当于自适应做完了,在这里,AdaBoost自适应的思想采取的是加权多数表决的方法,上述公式体现出来的就是加大分类器误差率小的弱分类器的权值,使其在表决中起较大作用。误差率较大的则相反。
现在要回到Boost的原理中对样本的处理,在改变这个样本的权值,或者说概率分布的时候,我们要实现的直观想法是:
提高那些被前一轮弱分类器错误分类样本的权值,
降低那些被正确分类的样本的权值。接下来我们去把这个公式证出来:
这里通过基学习器开始证明,看基学习器在什么样本分布下能够学出来最小化分类误差。
AdaBoost
在得到
Ht−1之后,调整样本分布,使得
ht能学出来之前的基学习器无法学习到的东西,能纠正
Ht−1的一些错误,那这个
ht就能够最小化:
于是理想的基学习器:
依据数学期望的定义,等价于令:
则理想的基学习器:
由此可见,理想的
ht将在分布
Dt下最小化分类误差。
Dt和
Dt+1的关系有:
上述公式就是下图AdaBoost的第7步更新公式,整个的AdaBoost算法如下图所示:
AdaBoost 算法第五行检查当前基分类器是否比随机猜测好,一旦不满足条件,当前基学习器即被抛弃,且学习过程停止。在这个请款下就有可能导致集成中包含基学习器数量过少,导致整体性能不佳。采用“重采样法”(re-sampling)来处理,即在每一轮学习中,根据样本分布对训练集重新采样,再用重采样而得到的样本集对基学习器进行训练,则可获得重启动。
评论(0)
您还未登录,请登录后发表或查看评论