心不留意外尘 / 机器学习概要 / Adaboost算法

0 0

   

Adaboost算法

2013-09-02  心不留意...

Adaboost算法

(2011-10-02 00:55:43)

from http://blog.sina.com.cn/s/blog_68ffc7a40100udqf.html

关于Adaboost算法,我在前面的博客中也有两篇文章中提到了,分别是《Probably approximately correct learning》,《信息检索系统之三-learn to rank》。这两篇文章主要是讲了一些Adaboost算法的概念和具体实施。这篇博客主要着重分析一下Adaboost为什么是这样的,它是怎么被推导出来的。通过公式的推导,可能使大家对Adaboost有更加深刻的理解。

Adaboost算法是一种在工业界中非常流行的算法,它最大的作用是能够把不同的分类器组合在一起形成一个最终的强分类器,这个强分类器综合了这些不同分类器的优点,因此能够达到很好的分类效果。呵呵,这的确是一种非常诱人的想法,我们传统的分类方法总是在纠结在哪种分类器好,哪个特征比较有效,现在好了,不管三七二十一,把它们全部组合起来,吸取它们所有的优点。这的确是一种非常靠谱的做法。

下面我们来具体看看算法是怎么样的。我们首先假设一下我们的场景,有一组样本,每个样本x都具有一组特征向量,y代表样本的分类,y有两个值-1和+1,代表着两种分类。这就是一个简单的两分类问题。

Adaboost算法具体如下:

5C473EBBE92E7AD061E68A9D839FC7288FC450D5

解释一下这个算法。分布D表示什么意思?在训练过程中,每个样本所起的作用或者说是权重是不一样,有的样本很重要,千万不能分类分错了,有的样本不是很重要,分错也没关系。这种重要性就是通过权重来表达,每个样本都有这么一个权重。D就是这个权重的分布,一个离散变量的分布。需要说明的是这个分布D在迭代的过程中是不断被更新变化的。这个怎么理解呢?也很简单。最初在第一次迭代的时候,D是一个等概率独立分布,每个样本的权重都一样,每个样本都一样重要。在经过一次弱分类后,有的样本被正确得分类,有的样本分错了。那么在下一个分类器在分类的时候,被正确分类的样本的重要性就下降了,这些样本已经被前面的分类器正确处理了,我就不用在这上面重复做功了。相反,错误分类的样本重要性就上升了,这些样本前面的分类器没有正确处理,这个我得好好重视一下,争取把这些样本分好了。分布D更新的规则如算法所示,清晰明了。

FA2FE804B77E398698AE33452D0D2F83FE50C32A是一组给定的弱分类器,这些分类之所以被称之为弱分类器,是因为这些分类器的往往效果实在不怎么样,正确率往往仅仅略大于50%,比瞎猜略好一点。我们从中选出一个分类器B1785EB74740C2C30227496F686BCA6BCF3D5CE0,使得错误代价02DBC2B349F6F639B4DBE2240F954141BADDAECB最小,并以此得出下一轮迭代的样本权重分布。

40B504DD4315CDE5E0098203A065B96543FA3539是一个归一化因子,是为了使得D117BA2E97F3501083056136F0BA794C2B3C38C1变成一个概率,1524AF9C32978C7AD4ADF3E182515F4C46196CD2从而变成一个分布。因此

337353D2C26F8F2E69F632AB65BFB10C2253C598

sign()是取符号函数,它返回数字的符号,比如sign(-1.2)=-1, sign(20) = 1。

最终的分类的结果H(x)是所有弱分类器h(x)投票的结果,各个弱分类器h(x)的话语权不同,通过权重7E097BD5D8647E2F88EB3CA224EE9CB9FE552AB0来控制。

算法讲到这里就已经很明白了,写个程序实施起来也没什么问题,网上也有开源的实现,随便copy一个过来改改都能用。比较著名的有一个Learning based java的实现,还有一个Adaboost.java也可以用好像。

下面就来尝试推导一下Adaboost算法为什么是这样的,是怎么来的。

首先对于一个分类器h,我们怎么判定它是否有效呢?用一个指标-误判损失,注意各个样本的权重有不同,该公式定义如下:

B909017BF814809E2342D24B977CC0BE86E163DE

在这里我们用了指数,为什么要用指数,在后面的推导中你会看到指数的作用,在后面我会进一步说明。

在一次迭代后,h与当前得到的组合分类H组合成一个新的组合分类器H+ah,其对应的误判损失为:

9A4651411CAA56ED5651BC8FA800E90F87B2C230

这是整个组合分类的误判损失,可以把它分解到每个样本上,得到每个样本的平均误判损失为:

B117DAD9C92D0C7840EF2D1A5302D38B20AFA77E

注意,h(x)的值只能为1或-1,y的值也只能是1或-1,yh(x)的值也只能是1或-1,这个特性在上述公式的推导中得以使用。

得到了上述每个样本的平均误判损失,我们的目标是求7E097BD5D8647E2F88EB3CA224EE9CB9FE552AB0[1],使得每个样本的平均误判损失最小。方法是求偏导,并让其为0,解这个方程组,如下

B918C1C73140FD13A2DB426242C113E04520F722

该方程的解也很容易,如下:

B446DB2D0042D4AEDED57D70A4D90B1579712AF4

F1E85A7E2938ACBFF1C7777FF1934E1D94A08C19,那么上述解可以表达为

13DF8BA50DAE4F6A04C521E1CE7B861077C2D826

这就是弱分类器h(x)的权重7E097BD5D8647E2F88EB3CA224EE9CB9FE552AB0[2],它就是这么来的。

接下来的问题,样本权重的分布式怎样的?

C1B02E0D40532FA5E028446E515D0BEED4C68B11在h=0点对h进行泰勒级数展开,我们让7E097BD5D8647E2F88EB3CA224EE9CB9FE552AB0[3]=1,那么就有如下推导

BDAD5FE587A59E08D830EFF8139E3BC36A5D9FC0公式1

注意y^2=1并且h(x)^2=1, 这对上面的推导很重要。

那么根据公式1,我们希望找到一个完美的最优h(x)使得C1B02E0D40532FA5E028446E515D0BEED4C68B11[1]最小,其表达式如下:

2BB6A332BEEFA5A1F1C1B856C8947913E8A3F6A7公式2

注意这里面的变量是h,BE344EA1EC50DA1860223A331D36139C98E2A69C在这里相对h是常量。再对公式2进行归一化,得到公式3

2E100149A3AE1A7021F107A96541276709096942公式3

我们引入一个新的分布w(x,y),它的分布表达式为774AFE80AA37E067AE51B92D5120587CF672DF1C

那么完美的公式3就可以写成:

30DE4EFDF31B682FD2BAA1C9D267AE4898158F29公式4

公式4展开就是

A56353E690A84FF892C3F243E8628F73C1E28288

h(x)和y一样,要么为1,要么为-1,为了使得B2346DBF9A7CE2746C5BD984F6D6A2F687A792CA最大,那么h(x)保持和y一样的符号取值时应该可以使得B2346DBF9A7CE2746C5BD984F6D6A2F687A792CA[1]最大,那h的最优解为

B0DCA3FF9C3579E23C3559D9CE5AE905982B6767

根据这个公式,可以知道h的最优解对应的x的分布为774AFE80AA37E067AE51B92D5120587CF672DF1C[1],因此774AFE80AA37E067AE51B92D5120587CF672DF1C[2]就是样本的权重分布。那么就有

8E8D0A64AB76361B7DE43972F9C899F44057C156

这就是h理想的最优解对应的样本权重的分布更新公式。分布更新公式推导的关键就是求出完美的h(x)的表达式,通过完美的h(x)的表达式我们就可以得到x的分布公式,根据x的分布公式我们就很容易得出权重的分布更新公式。完美的h(x)所对应的x的权重分布就是一个理想状态下的x的权重分布,我们在算法执行中给定的h(x)未必是这个完美的h(x),但是它是当前迭代轮次与完美解最接近的,因此完美解结果对应的分布也就是我们想要的。其实从公式3的表达式上我们就应该能够看出样本的系数了。

下面我们就来面对最后一个问题,为什么我们要用指数来衡量误判损失?直接用F1E85A7E2938ACBFF1C7777FF1934E1D94A08C19[1]不也不行么?我们来看看用单个样本的平均指数误判损失作为目标函数得到的我们的最优化的h(x)是多少?推导如下

682093BF55E79E63575970EF1348AE42DB1CCA57

根据最优化的的结果,我们可以得到

0F19ABF044B94A3816BB02D29723792AA893ED69公式5

看到公式5,你会发现这非常得巧妙,根据单个样本的平均指数误判损失得到的最优h(x)可以得到使得0114EEF1BFCD96B654B35C52839CCA26803DD65F最大的y,也就是样本的分类,想想贝叶斯公式,这个最优解h(x)实际上能够得到最大后验概率,这多么理想啊,所以你就会明白选择指数误判损失是多么明智的选择。但我个人怀疑,是否有其他形式的误判损失衡量,比如线性啊等等,也能得到类似最大化后验概率这样的理想的结果。好像论文中也没有给出说明,但是至少可以得到指数误判损失已经很好了,这就足够了。

好了,得到了分类器权重公式,样本权重分布的更新公式,还证明了指数误判损失的优越性,有了这三点,相信大家已经比较深刻得明白Adaboost的来龙去脉了吧。

Adaboost还有一些值得深入讨论的地方,比如如何解决多分类的问题等等,有兴趣的读者可以进一步阅读相关论文。

[1]http://www.zhenv5.com/?p=765

[2]http://code.google.com/p/pr-toolkit/source/browse/applications/postagging/trunk/src/edlin/classification/AdaBoost.java?r=5

[3]The top ten Algorithms in Data Mining

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多