经典机器学习系列(六)【集成学习】之周志华西瓜书-AdaBoost算法证明解析

91
0
2021年1月7日 09时03分

本节证明并未从集成学习源头开始,如若对集成学习还不是很清楚的同学,参考文章:

 

 

AdaBoost算法证明

 

本文以周志华西瓜书推导过程为例,以“加性模型”(additive model)进行解析:

 

将基学习器ht(x)线性组合,则基学习器的线性组合表示为如下H(x)形式:

 

屏幕截图 2021-01-04 125340

 

定义整个学习器的损失函数为指数损失函数(exponential loss function),期望指数损失函数最小化:

 

屏幕截图 2021-01-04 125400

 

其中f ff是真实函数,yi{1,+1}D 表示样本的权值分布(对于错误的样本权重要高一点,正确的样本权重要低一点,所有的样本组合起来就相当于有一个分布)。

 

若基学习器的线性组合H(x)能够使得指数损失函数最小化,一般的做法就是求偏导数,令其等于零,求解。由于f ( x ) 取值只有两种,所以其求偏导数之后的结果如下所示:

 

屏幕截图 2021-01-04 125448

 

这意味着若指数损失函数最小化,则分类错误率也将最小化。说明指数损失函数是原任务的替代函数,但由于其连续可微,所以用它替代0/1损失函数作为优化目标。上面这么多就是说接下来用这个连续的指数损失函数做进一步的处理。

 

在AdaBoost算法中,第一个基分类器h1通过直接将基学习算法用于初始数据分布而得到;之后的htα t 是通过迭代生成得到的。当基分类器ht基于分布Dt产生之后,基分类器的权重αt应该使得αtht最小化指数损失函数,只有αt在判断错误的基分类器给予较小权值,判断正确的基分类器给予较大权值,才能使得H(x)具有较准确的判断,从而最小化指数损失函数

 

屏幕截图 2021-01-04 125611

 

屏幕截图 2021-01-04 125636其实就是误判率。为了求得基分类器的权重,对其求导:

 

屏幕截图 2021-01-04 125658

 

到这里相当于自适应做完了,在这里,AdaBoost自适应的思想采取的是加权多数表决的方法,上述公式体现出来的就是加大分类器误差率小的弱分类器的权值,使其在表决中起较大作用。误差率较大的则相反。

 

现在要回到Boost的原理中对样本的处理,在改变这个样本的权值,或者说概率分布的时候,我们要实现的直观想法是:提高那些被前一轮弱分类器错误分类样本的权值降低那些被正确分类的样本的权值。接下来我们去把这个公式证出来:

 

这里通过基学习器开始证明,看基学习器在什么样本分布下能够学出来最小化分类误差。

 

AdaBoost在得到Ht1之后,调整样本分布,使得ht能学出来之前的基学习器无法学习到的东西,能纠正Ht1的一些错误,那这个ht就能够最小化:

 

屏幕截图 2021-01-04 125801

 

于是理想的基学习器:

 

屏幕截图 2021-01-04 125839

 

依据数学期望的定义,等价于令:

 

屏幕截图 2021-01-04 125907

 

则理想的基学习器:

 

屏幕截图 2021-01-04 130019

 

由此可见,理想的ht将在分布Dt下最小化分类误差。DtDt+1的关系有:

 

屏幕截图 2021-01-04 130100

 

上述公式就是下图AdaBoost的第7步更新公式,整个的AdaBoost算法如下图所示:

 

AdaBoost 算法

 

AdaBoost 算法第五行检查当前基分类器是否比随机猜测好,一旦不满足条件,当前基学习器即被抛弃,且学习过程停止。在这个请款下就有可能导致集成中包含基学习器数量过少,导致整体性能不佳。采用“重采样法”(re-sampling)来处理,即在每一轮学习中,根据样本分布对训练集重新采样,再用重采样而得到的样本集对基学习器进行训练,则可获得重启动。

 

发表评论

后才能评论