大连理工大学硕士学位论文
3) 假设
学习的目的是构造对目标的表示作为学习的结论，在这里即产生一个函数。此函数
通过作用在训练集的观测值上而产生一个标识，这样的函数称为假设，记为
在Boosting中，每次学习都产生一个假设，我们称为弱假设;最终联合所有弱假设而得到的判别函数称为最终假设或最终判别准则，记为H(x)。 4)
Dt。
ht：X?Y?R分布
Boosting方法的第 t 次循环中提供给弱学习算法的关于训练集样本的分布，记为
5) 下：
误判率
由第 t 次弱学习而得弱假设的错判概率称为误判率，这里此误判率(error)定义如
?t?Pr~D[ht(xi)?yi]?it?Di:ht(xi)?yit(i) （2.1）
2.2 AdaBoost.MH算法简介
2.2.1 AdaBoost算法背景
AdaBoost的前身是Boosting算法。Boosting作为一种通用的学习算法，可以提高任一给定算法的性能。Boosting根源于研究机器学习的理论框架 ——“PAC”学习模型（由Valiant提出的关于可学习性的理论：Probably、Approximately、Correct）。Kearns and Valiant最先指出，在“PAC”学习模型中，若存在一个多项式级的学习算法来识别一组概念，并且识别率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测的略好，那么这组概念是弱可学习的。如果能将一个弱学习算法提升为强学习算法，那么在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。[18]
1989年Schapire[18]提出了第一个可证的具有多项式复杂度的Boosting算法。他的主要方法如下：
1） 通过对N个训练样本的学习，得出初始判别G1；
2） 判别G2是对新的N个样本学习的结果，此N个样本中的半数为被G1错判的； 3） G3的训练集为由G1, G2作出不同判断的N个样本组成；
-15-
一种基于AdaBoost.MH算法的汉语多义词排歧方法
4） 由Boosting作出最终判别准则： GB = 多数意见(G1, G2, G3)。
在这篇文章中，Schapire在理论上证明了最终判别准则GB对G1判别准确率的提高。但由于此方法实施起来需要大量的时间、存储空间及样本，因此使用起来极不方便。
一年之后，Freund[19]开发了一个更有效的Boosting算法，即“投票方式Boosting方法”。这种相对简单、行之有效的方法通过平行地作多次学习，再对各次学习的弱假设以多数意见来作为最后的判别准则。尽管此算法在某种程度上说是理想的，但还是存在某种实际的缺陷。
这两种方法都是通过多次运行弱学习算法，每次将其应用于样本空间的不同分布上，得出多个弱学习所产生的弱假设，最后采用多数投票的原则综合所有弱假设给出一个简单的最终的判别准则，从而达到提高弱学习算法的准确率的目的。两种算法都是通过不断加大样本中难以判别的样本的权重，迫使弱学习算法得出在这些样本上犯更少错误的假设。
Drucher，Schapire和Simard[20]首次在OCR项目中对这些早期Boosting算法进行了实验。两种算法在理论上都要求弱学习算法有固定的误判率，实际上，这是很难做到的。这使得人们迫切地想找到一种更具适应性和实用性的算法。
AdaBoost算法于1995年由Freund和Schapire[21]提出，解决了许多早期Boosting算法的实际困难。它的最终判别准则的精确度是依赖所有弱学习过程得出的弱假设的，因而更能全面地挖掘弱学习算法的能力。也正是由于此种原因而得名“Adaptive Boosting”，简称AdaBoost（“Ada”是“adaptive”的缩写）。同时，它也是应用于实际问题的一个有效的方法。 2.2.2 AdaBoost算法基本思想
AdaBoost算法的输入是一个训练集(x1,y1),.....(xm,ym)其中xi属于某个域或实例空间X，yi?Y， Y为有限的表示空间，Y?{?1,?1}。AdaBoost在一系列的迭代中重复调用给定的弱或基本学习算法。
算法的描述参见表2.1。算法的数据流程图参见图2.1。
算法的主要思想是维持训练集上的一个分布或权重集（表示为Dt）。初始状态下，分布D的权值是相同的。在每次迭代中，运用表中的调整公式调整每个样本的权值，使每次输入弱学习器的样本集具有不同的权重，让弱学习器集中学习那些使用前一规则最难以预测的样本上。
-16-
大连理工大学硕士学位论文
弱规则的作用是用来产生一个弱假设：ht：X?{?1,?1}。弱假设的好坏由错误率来?t（公式2.1）衡量，而且误差的测量是与学习器被训练的分布Dt相关的。在实际用用中，弱学习器的算法可以是作用于训练实例的权重分布Dt，也可以是取样于分布Dt的某一训练子集（未赋权重）[21]。
表2.1 AdaBoost算法描述 输入：
(x1,y1),.....(xm,ym)
其中xi?X，yi?Y且Y?{?1,?1}
初始化：D1(i)?1/m
训练过程：For t = 1，… ，T：
a) 把Dt传给并调用弱规则学习器；
b) 获得?t?Pr~D[ht(xi)?yi]的弱规则 ht：X?{?1,?1}
itc) 选择?t?12ln(1???)
d) 利用调整公式调整矩阵D的权值 Dt?1(i)?输出：最终假设
TDt(i)exp(??tyi[l]ht(xi)Zt其中Zt是正规化因子
H(x)?sign[??tht(x)]
t?1 得到弱假设ht后，AdaBoost需要选择一个参数?t?R（参见表2.1）。?t测量了
ht的重要性，如果?t?1/2,则?t?0（这种情况下，可以认为没有总误差），而且
?t越小,?t越大。然后使用表2.1中的规则修正分布Dt。规则的作用是增加被ht错分的
实例权重，减少正确分类的实例的权重。因此，权重趋向于难以分类的实例上。最终规则H是T个弱假设（?t是赋给ht的权重）的占绝大部分的投票。
Schapire和Singer[23]阐述了如何将AdaBoost及其分析扩展到处理输出值为实值或置信预测的弱假设上的。也就是说，对每个实例x，弱假设ht输出一个预测h(x)?R，其标记是预测标签（-1或+1），梯度 |ht(x)| 给出了预测的置信度。
-17-
一种基于AdaBoost.MH算法的汉语多义词排歧方法
图2.1 AdaBoost 算法的数据流程图
Fig. 2.1 Data flow diagram of AdaBoost algorithm
2.2.3 AdaBoost算法误差的分析
AdaBoost最基本的理论特性是它减少总误差的能力。对于二值问题，随机猜测任意实例类别的错误率为50%。记ht的误差?t为
12??t，其中?t测量了ht的预测比随机
测量好的程度。Freund和Schapire[18]证明最终假设H的训练误差（训练集中错误比例）上限为：
?[2?t(1??t)]??tt1?4?t)?exp(?2??t)t22 （2.2）
上式表明，对于某一??0有?t?? ，只要每个弱假设的预测能力比随机猜测好一些，训练误差就会成指数级的下降。先前的Boosting算法也具有类似的特性，但是在它开始学习之前需要获得一个更低的类间距。通常这样的类间距是很难获得的。AdaBoost适应于每个单独弱假设的错误率，因此它是自适应的。
-18-
大连理工大学硕士学位论文
Freund和Schapire[21]阐述了如何根据训练误差、样例的大小m，弱假设空间的VC维度d和Boosting的迭代次数T来限制最终假设的总误差。而且还利用Baum和Haussler的技术阐明了高概率地情况下，总误差至多为：
Pr[H(x)?y]?O(Tdm) （2.3）
其中Pr[H(x)?y]表示训练样本的经验概率。这个边界表示如果迭代次数过多Boosting会发生过适应。在实际实验中，有时的确如此，然而，在早期的大部分实验中，一些作者[22，24]得到的经验结论却是：Boosting经常不会发生过适应，甚至在迭代上千次的情况下。而且在训练误差降到0之后，AdaBoost有时会继续降低总误差，这明显违背上面的边界。
图2.2所示为[25]中BoostingC4.5对UCI中的样本进行分类，得到的相对于迭代次数T的误差曲线和类间距分布图。左图中上面一根曲线表示泛化误差，下面一根曲线表示训练误差。
图2.2误差曲线和类间距分布图
Fig. 2.2 Error curves and the margin distribution graph
从左图中可以看到，当训练误差达到零后，Boosting仍然会继续降低泛化误差，并没有因为迭代次数的增多出现泛化变差的情景。这个现象与机器学习中通常所遵循的“Occam's Razor'，原则相违背。
基于这些经验发现，Schapire et al.[25]在Bartlett工作的基础上，给出了一个关于训练实例类间距的另一可选分析。实例(x,y)的类间距被定义为：
-19-