Adaboost算法

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算法具体如下：

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

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

是一个归一化因子，是为了使得变成一个概率，从而变成一个分布。因此

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

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

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

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

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

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

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

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

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

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

该方程的解也很容易，如下：

令，那么上述解可以表达为

这就是弱分类器h(x)的权重，它就是这么来的。

接下来的问题，样本权重的分布式怎样的？

在h=0点对h进行泰勒级数展开，我们让=1，那么就有如下推导

公式1

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

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

公式2

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

公式3

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

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

公式4

公式4展开就是

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

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

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

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

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

公式5

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

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

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

[1]http://www./?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