论文部分内容阅读
摘要：Boosting 算法是近年来在机器学习领域中一种流行的用来提高学习精度的算法。文中以AdaBoost算法为例来介绍Boosting的基本原理。
关键词：机器学习；Boosting；泛化误差；分类
中图分类号：TP181文献标识码：A文章编号：1009-3044(2008)36-2698-02
A Study of Boosting Algorithm
LU Gang1, CHEN Yong1, FAN Yong-xin2, HU Cheng1
(1.The Artillery Academy of PLA, Hefei 230031, China;2.China Construction Bank Yunnan Branch, Kunming 650021, China)
Abstract: Boosting is a general method for improving the accuracy of any given learning algorithm.This short overview paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting.
Key words: machine learning; boosting; generalization error; classification
1 引言
Freund 和 Schapire的AdaBoost算法問世便引起了机器学习和数理统计两大领域的广泛关注。它的思想起源于Valiant提出的PAC ( Probably Approximately Correct)学习模型。Kearns 和Valiant首次提出PAC学习模型中任意给定仅比随机猜测略好的弱学习算法是否可“boosted”为强学习算法。1990年，Schapire构造出一种多项式级的算法，对该问题做了肯定的证明，这是最初的Boosting算法。一年后，Freund提出了一种效率更高的Boosting算法。但是，这两种算法存在共同的实践上的缺陷，那就是都要求事先知道弱学习算法学习正确率的下限。这些早期的Boosting 算法首先被Drucker、Schapire和Simard应用于一次OCR工作中。1995年，Freund和schapire改进了Boosting算法，提出了AdaBoost (Adaptive Boosting)算法，此算法不需要任何关于弱分类器的先验知识，可以非常容易地应用到实际问题中。
2 AdaBoost算法
在机器学习领域中，AdaBoost算法得到极大的重视。实验结果显示，AdaBoost能显著提高学习精度和泛化能力，已经成为Boosting 系列中的代表算法。之后出现的各种Boosting算法都是在AdaBoost算法的基础之上发展而来的。对AdaBoost算法的研究应用大多集中在分类问题中，近年来也出现了一些在回归问题上的研究。寻找多个识别率不是很高的弱分类算法比寻找一个识别率很高的强分类算法要容易得多，AdaBoost算法的任务就是完成将容易找到的识别率不高的弱分类算法提升为识别率很高的强分类算法，这也是AdaBoost 算法的核心指导思想所在，如果算法完成了这个任务，那么在分类时，只要找到一个比随机猜测略好的弱分类算法，也就是给定一个弱学习算法和训练集，在训练集的不同子集上，多次调用弱学习算法，最终按加权方式联合多次弱学习算法的预测结果就可得到最终学习结果。
AdaBoost算法的基本思想是：首先给出任意一个弱学习算法和训练集(x1,y1), (x2, y2 ) ,..., (xm, ym) ,此处,xi∈X, X表示某个域或实例空间，在分类问题中是一个带类别标志的集合,yi∈Y={+1, -1}。初始化时, Adaboost为训练集指定分布为1/m，即每个训练例的权重都相同为1 /m 。接着，调用弱学习算法进行T次迭代，每次迭代后，按照训练结果更新训练集上的分布，对于训练失败的训练例赋予较大的权重，使得下一次迭代更加关注这些训练例，从而得到一个预测函数序列h1,h2,...,ht，每个预测函数ht也赋予一个权重，预测效果好的，相应的权重越大。T次迭代之后，在分类问题中最终的预测函数H采用带权重的投票法产生。单个弱学习器的学习准确率不高，经过运用Boosting算法之后，最终结果准确率将得到提高。每个样本都赋予一个权重, T次迭代，每次迭代后，对分类错误的样本加大权重。
离散的AdaBoost算法，给定训练样本集S={(x1,y1),(x2,y2)),…, (xl,yl)∈Rn×{-1,+1}}。其中xi(i=1,2,…,l)服从独立同分布。
离散的AdaBoost 算法的伪码描述如下：
1) 初始化权重：wi=1/l,i=1,2,…,l
2) 循环：Repeat from m=1,2,…,M:
① 使用权值wi，用弱分类器fm(x)拟合训练数据；
② 计算：
；
① 计算:Cm=log((1-errm)/errm)；
② 置wi<—wiexp[Cm•I(yi≠fn(xi))]，i=1,2,…,l，并且重新正则化权重使得 wi=1。
3）输出：分类器决策函数。
一个弱分类器的误差率只比随机猜测略好一些。Boosting的目的就是连续对反复修改的数据应用弱分类算法，由此产生一个弱分类器序列fm(x)，m=1,2,…,M。然后，通过一个加权的多数表决来合并全部预测，以产生最终预测：
这里，C1,C2,…,Cm由boosting算法来计算，并对每个fm(x)的贡献加权。它们的作用是对序列中较精确的分类器给予较高的影响。
在每个boosting迭代中，数据修改就是对每一训练样本(xi,yi)(i=1,2,…,l)实施加权w1,w2,…,wl。开始，所有权都被置成wi=1/l，以便第一步能够简单地用通常的方式在数据上训练分类器。对每一个相继的迭代m=2,3,…,M，样本的权值被分别修改，并且分类算法被再次应用于加权样本。在第m步，那些被前一个迭代步骤导出的分类器fm-1(x)误分类的样本权值提高，而被正确分类的样本权值降低。这样，随着迭代的进行，那些很难正确分类的样本受到了权重不断增长的影响。因此，每个后继分类器被强制关注那些被前面的分类器误分类的训练样本。
离散的AdaBoost算法中，步骤2（a）在加权样本上导出当前的分类器fm (x)。步骤2（b）计算当前加权误差率，步骤2（c）计算权值Cm，该权值在产生最终分类器f(x)时（步骤3）赋予fm(x)。在步骤2（d），为下一步迭代更新每个样本的权值。被fm(x)误分类的样本的权值被放大一个因子exp(Cm)，增加了对导出序列中下一个分类器fm+1(x)的相对影响。
离散的AdaBoost算法中弱分类器fm(x)返回离散的类标号。如果弱分类器改为实数值预测（如映射到区间[0,1]的概率），则可以对离散的AdaBoost做适当的修改，即下面所述的Real AdaBoost算法。
Real AdaBoost算法的伪码描述如下：
1）初始化权重：wi=1/l,i=1,2,…,l。
2）循环：Repeat for m=1,2,…,M:
① 在加权为wi的训练数据上拟合分类器以获得在区间[0,1]上的类概率估计Pm(x)=Pw(y=1|x)；
② 置弱分类器: ；
③ 置权重，wi<—wiexp[-yifm(xi)]，i=1,2,…,l，重新正则化权重使得 wi=1。
3）输出：分类器决策函数 。
以离散AdaBoost为例，如图1所示，其中弱分类器仅仅是个树桩——两个端节点的分类树。
初始的时候，只用单个弱分类器的分类错误率较高，但随着boosting迭代的进行，分类错误率明显减小，可见AdaBoost算法能够显著提升很弱的分类器的性能。
3 Boosting算法理论分析
Schapire, Singer和Freund首先从理论上推导出最终预测函数的训练误差：定义f(x)=αtht(x),则有H(x)=sign(f(x))，推出误差边界为：
式中我们可以看出,可以通过选择每一轮中的αt和ht来最小化Zt，使得训练误差迅速减小。大量的试验表明，Boosting不但能够提高学习精度，而且在训练了几千轮之后也不会发生过适应现象，而且其泛化误差在训练误差已经降到零后仍会继续降低。Schapire和Freund用Boosting C4.5对UCI中的“letter”样本集进行分类，图2是得出的相对于迭代次数T的误差曲线。
图2 图3
图2中，上面一条曲线是泛化误差，下面一条曲线是训练误差。从图中我们可以看出，在训练误差已经达到零后， Boosting仍能继续降低泛化误差，而不会因此出现泛化误差恶化的现象。泛化误差与训练轮数T无关，也就是说泛化误差不受训练轮数影响。图3反映出Boosting对边界的影响。当训练误差降为零后，Boosting仍然会继续提高训练样本的边界值，从而增大了最小边界，使分类的可靠性增加，使得泛化误差也能够继续下降。（下转第2708页）
（上接第2699页）
4 结束语
Boosting是近十几年来提出的最有效的学习思想之一，它最初是为分类问题而设计的，但也可以对它进行扩充以解决回归问题，并且Boosting的思想已被用到ranking和cost-sensitive上，也有一些研究者将Boosting应用到非监督学习问题上。Boosting在实际当中也得到了很多应用,例如，语音识别、医疗诊断等。目前，Boosting算法仍有许多值得研究的方向。Boosting中迭代次数是一个经验值，如何选择合适的迭代次数；Boosting在某些情况下会发生过适应现象，找到产生过适应的条件也是一个值得研究的方面；如何减少Boosting对噪声的敏感；Boosting和模糊集理论相结合在多分类中的应用等。近年来，张通等人在分析了一些流行的学习算法后，从一致性的观点对一些流行的学习算法如最小二乘法、支持向量机、Boosting等等进行了理论分析，发现这些学习算法都具有逼近贝叶斯最优解的性能，只是使用了不同的损失函数而已。这种理论分析的方法进一步完善了统计学习理论体系，得到了研究者们的普遍关注。另外，Boosting在实际应用中也有广泛的前景，例如：图像识别及检索、手写体字符识别、语音识别、文本分类等。
参考文献：
[1] ValiantL G .A Theory of the Learnable[J].Communications of the ACM,1984,27(11):1134-1142.
[2] Schapire R E, Freund Y, Bartlett P et al.Boosting the Margin: a New Explanation for the Effectiveness of Voting Methods [J].The Annals of Statistics,1998,26(5):1651-1686.
[3] Freund Y, Robert E. Schapire. A Short Introduction to Boosting[J].Journal of Japanese Society for Artificial Intelligence,1999,14(5):771-780.
[4] Freund Y, Schapire R. Experiments with a new boosting algorithm[C].In: Proceedings of the Thirteenth International Conference.San Francisco: Machine Learning,1996:148-156
[5] Zhang T. Statistical behavior and consistency of classification methods based on convex risk minimization[J].Annals of Statistics,2004(32):56-85
[6] Friedman J, Hastie T, Tibshirani R. Additive logistic regression: a statistics view of boosting[J].Annals of Statistics, 2000(28):337-407.
注：“本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。”
关键词：机器学习；Boosting；泛化误差；分类
中图分类号：TP181文献标识码：A文章编号：1009-3044(2008)36-2698-02
A Study of Boosting Algorithm
LU Gang1, CHEN Yong1, FAN Yong-xin2, HU Cheng1
(1.The Artillery Academy of PLA, Hefei 230031, China;2.China Construction Bank Yunnan Branch, Kunming 650021, China)
Abstract: Boosting is a general method for improving the accuracy of any given learning algorithm.This short overview paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting.
Key words: machine learning; boosting; generalization error; classification
1 引言
Freund 和 Schapire的AdaBoost算法問世便引起了机器学习和数理统计两大领域的广泛关注。它的思想起源于Valiant提出的PAC ( Probably Approximately Correct)学习模型。Kearns 和Valiant首次提出PAC学习模型中任意给定仅比随机猜测略好的弱学习算法是否可“boosted”为强学习算法。1990年，Schapire构造出一种多项式级的算法，对该问题做了肯定的证明，这是最初的Boosting算法。一年后，Freund提出了一种效率更高的Boosting算法。但是，这两种算法存在共同的实践上的缺陷，那就是都要求事先知道弱学习算法学习正确率的下限。这些早期的Boosting 算法首先被Drucker、Schapire和Simard应用于一次OCR工作中。1995年，Freund和schapire改进了Boosting算法，提出了AdaBoost (Adaptive Boosting)算法，此算法不需要任何关于弱分类器的先验知识，可以非常容易地应用到实际问题中。
2 AdaBoost算法
在机器学习领域中，AdaBoost算法得到极大的重视。实验结果显示，AdaBoost能显著提高学习精度和泛化能力，已经成为Boosting 系列中的代表算法。之后出现的各种Boosting算法都是在AdaBoost算法的基础之上发展而来的。对AdaBoost算法的研究应用大多集中在分类问题中，近年来也出现了一些在回归问题上的研究。寻找多个识别率不是很高的弱分类算法比寻找一个识别率很高的强分类算法要容易得多，AdaBoost算法的任务就是完成将容易找到的识别率不高的弱分类算法提升为识别率很高的强分类算法，这也是AdaBoost 算法的核心指导思想所在，如果算法完成了这个任务，那么在分类时，只要找到一个比随机猜测略好的弱分类算法，也就是给定一个弱学习算法和训练集，在训练集的不同子集上，多次调用弱学习算法，最终按加权方式联合多次弱学习算法的预测结果就可得到最终学习结果。
AdaBoost算法的基本思想是：首先给出任意一个弱学习算法和训练集(x1,y1), (x2, y2 ) ,..., (xm, ym) ,此处,xi∈X, X表示某个域或实例空间，在分类问题中是一个带类别标志的集合,yi∈Y={+1, -1}。初始化时, Adaboost为训练集指定分布为1/m，即每个训练例的权重都相同为1 /m 。接着，调用弱学习算法进行T次迭代，每次迭代后，按照训练结果更新训练集上的分布，对于训练失败的训练例赋予较大的权重，使得下一次迭代更加关注这些训练例，从而得到一个预测函数序列h1,h2,...,ht，每个预测函数ht也赋予一个权重，预测效果好的，相应的权重越大。T次迭代之后，在分类问题中最终的预测函数H采用带权重的投票法产生。单个弱学习器的学习准确率不高，经过运用Boosting算法之后，最终结果准确率将得到提高。每个样本都赋予一个权重, T次迭代，每次迭代后，对分类错误的样本加大权重。
离散的AdaBoost算法，给定训练样本集S={(x1,y1),(x2,y2)),…, (xl,yl)∈Rn×{-1,+1}}。其中xi(i=1,2,…,l)服从独立同分布。
离散的AdaBoost 算法的伪码描述如下：
1) 初始化权重：wi=1/l,i=1,2,…,l
2) 循环：Repeat from m=1,2,…,M:
① 使用权值wi，用弱分类器fm(x)拟合训练数据；
② 计算：
；
① 计算:Cm=log((1-errm)/errm)；
② 置wi<—wiexp[Cm•I(yi≠fn(xi))]，i=1,2,…,l，并且重新正则化权重使得 wi=1。
3）输出：分类器决策函数。
一个弱分类器的误差率只比随机猜测略好一些。Boosting的目的就是连续对反复修改的数据应用弱分类算法，由此产生一个弱分类器序列fm(x)，m=1,2,…,M。然后，通过一个加权的多数表决来合并全部预测，以产生最终预测：
这里，C1,C2,…,Cm由boosting算法来计算，并对每个fm(x)的贡献加权。它们的作用是对序列中较精确的分类器给予较高的影响。
在每个boosting迭代中，数据修改就是对每一训练样本(xi,yi)(i=1,2,…,l)实施加权w1,w2,…,wl。开始，所有权都被置成wi=1/l，以便第一步能够简单地用通常的方式在数据上训练分类器。对每一个相继的迭代m=2,3,…,M，样本的权值被分别修改，并且分类算法被再次应用于加权样本。在第m步，那些被前一个迭代步骤导出的分类器fm-1(x)误分类的样本权值提高，而被正确分类的样本权值降低。这样，随着迭代的进行，那些很难正确分类的样本受到了权重不断增长的影响。因此，每个后继分类器被强制关注那些被前面的分类器误分类的训练样本。
离散的AdaBoost算法中，步骤2（a）在加权样本上导出当前的分类器fm (x)。步骤2（b）计算当前加权误差率，步骤2（c）计算权值Cm，该权值在产生最终分类器f(x)时（步骤3）赋予fm(x)。在步骤2（d），为下一步迭代更新每个样本的权值。被fm(x)误分类的样本的权值被放大一个因子exp(Cm)，增加了对导出序列中下一个分类器fm+1(x)的相对影响。
离散的AdaBoost算法中弱分类器fm(x)返回离散的类标号。如果弱分类器改为实数值预测（如映射到区间[0,1]的概率），则可以对离散的AdaBoost做适当的修改，即下面所述的Real AdaBoost算法。
Real AdaBoost算法的伪码描述如下：
1）初始化权重：wi=1/l,i=1,2,…,l。
2）循环：Repeat for m=1,2,…,M:
① 在加权为wi的训练数据上拟合分类器以获得在区间[0,1]上的类概率估计Pm(x)=Pw(y=1|x)；
② 置弱分类器: ；
③ 置权重，wi<—wiexp[-yifm(xi)]，i=1,2,…,l，重新正则化权重使得 wi=1。
3）输出：分类器决策函数 。
以离散AdaBoost为例，如图1所示，其中弱分类器仅仅是个树桩——两个端节点的分类树。
初始的时候，只用单个弱分类器的分类错误率较高，但随着boosting迭代的进行，分类错误率明显减小，可见AdaBoost算法能够显著提升很弱的分类器的性能。
3 Boosting算法理论分析
Schapire, Singer和Freund首先从理论上推导出最终预测函数的训练误差：定义f(x)=αtht(x),则有H(x)=sign(f(x))，推出误差边界为：
式中我们可以看出,可以通过选择每一轮中的αt和ht来最小化Zt，使得训练误差迅速减小。大量的试验表明，Boosting不但能够提高学习精度，而且在训练了几千轮之后也不会发生过适应现象，而且其泛化误差在训练误差已经降到零后仍会继续降低。Schapire和Freund用Boosting C4.5对UCI中的“letter”样本集进行分类，图2是得出的相对于迭代次数T的误差曲线。
图2 图3
图2中，上面一条曲线是泛化误差，下面一条曲线是训练误差。从图中我们可以看出，在训练误差已经达到零后， Boosting仍能继续降低泛化误差，而不会因此出现泛化误差恶化的现象。泛化误差与训练轮数T无关，也就是说泛化误差不受训练轮数影响。图3反映出Boosting对边界的影响。当训练误差降为零后，Boosting仍然会继续提高训练样本的边界值，从而增大了最小边界，使分类的可靠性增加，使得泛化误差也能够继续下降。（下转第2708页）
（上接第2699页）
4 结束语
Boosting是近十几年来提出的最有效的学习思想之一，它最初是为分类问题而设计的，但也可以对它进行扩充以解决回归问题，并且Boosting的思想已被用到ranking和cost-sensitive上，也有一些研究者将Boosting应用到非监督学习问题上。Boosting在实际当中也得到了很多应用,例如，语音识别、医疗诊断等。目前，Boosting算法仍有许多值得研究的方向。Boosting中迭代次数是一个经验值，如何选择合适的迭代次数；Boosting在某些情况下会发生过适应现象，找到产生过适应的条件也是一个值得研究的方面；如何减少Boosting对噪声的敏感；Boosting和模糊集理论相结合在多分类中的应用等。近年来，张通等人在分析了一些流行的学习算法后，从一致性的观点对一些流行的学习算法如最小二乘法、支持向量机、Boosting等等进行了理论分析，发现这些学习算法都具有逼近贝叶斯最优解的性能，只是使用了不同的损失函数而已。这种理论分析的方法进一步完善了统计学习理论体系，得到了研究者们的普遍关注。另外，Boosting在实际应用中也有广泛的前景，例如：图像识别及检索、手写体字符识别、语音识别、文本分类等。
参考文献：
[1] ValiantL G .A Theory of the Learnable[J].Communications of the ACM,1984,27(11):1134-1142.
[2] Schapire R E, Freund Y, Bartlett P et al.Boosting the Margin: a New Explanation for the Effectiveness of Voting Methods [J].The Annals of Statistics,1998,26(5):1651-1686.
[3] Freund Y, Robert E. Schapire. A Short Introduction to Boosting[J].Journal of Japanese Society for Artificial Intelligence,1999,14(5):771-780.
[4] Freund Y, Schapire R. Experiments with a new boosting algorithm[C].In: Proceedings of the Thirteenth International Conference.San Francisco: Machine Learning,1996:148-156
[5] Zhang T. Statistical behavior and consistency of classification methods based on convex risk minimization[J].Annals of Statistics,2004(32):56-85
[6] Friedman J, Hastie T, Tibshirani R. Additive logistic regression: a statistics view of boosting[J].Annals of Statistics, 2000(28):337-407.
注：“本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。”