学习模型中的学习算法

学习模型中的学习算法

1kearns的识别算法在机械学习领域，重要的问题是如何使用观测数据来获得准确的评估。目前,随着计算机硬件技术的迅猛发展,学习准确率比运算速度显得更为重要。但是,在实际应用领域中,构造一个高精度的估计几乎是不可能的。Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于Valiant提出的PAC(ProbablyApproximatelyCorrect)学习模型。Valiant和Kearns提出了弱学习和强学习的概念,识别错误率小于1/2,也即准确率仅比随机猜测略高的学习算法称为弱学习算法;识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法?如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。1990年,Schapire最先构造出一种多项式级的算法,对该问题做了肯定的证明,这就是最初的Boosting算法。一年后,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷,那就是都要求事先知道弱学习算法学习正确率的下限。1995年,Freund和schapire改进了Boosting算法,提出了AdaBoost(AdaptiveBoosting)算法,该算法效率和Freund于1991年提出的Boosting算法几乎相同,但不需要任何关于弱学习器的先验知识,因而更容易应用到实际问题当中。之后,Freund和schapire进一步提出了改变Boosting投票权重的AdaBoost.M1,AdaBoost.M2等算法,在机器学习领域受到了极大的关注。2adabolst算法AdaBoost算法是Boosting家族最具代表性的算法,之后出现的各种Boosting算法都是在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的算法描述如下:3泛化误差分析Schapire,Singer和Freund首先从理论上推导出最终预测函数的训练误差:定义f(x)=∑tαtht(x)f(x)=∑tαtht(x),则有H(X)=sign(f(x)),进而推导出训练误差的边界为:1m1m{i:H(xi)≠yt}≤1m∑texp(−yif(xi))=∏tTZt(1)≤1m∑texp(-yif(xi))=∏tΤΖt(1)从(1)式中我们可以看出,可以通过选择每一轮中的αt和ht来最小化Zt,使得训练误差迅速减小。Schapire和Freund还证明了最终预测函数H的最大错误率为:H=∐tΗ=∐t2εt(1−εt)−−−−−−−−√2εt(1-εt)=∏t1−4γt2−−−−−−−√≤exp(−2∑tγt2)(2)=∏t1-4γt2≤exp(-2∑tγt2)(2)在(2)中,γt=1/2-εt,其中εt为训练误差。从该式中可以看出,只要我们选择的弱学习算法略好于随机猜想,训练误差将随t以指数级下降。AdaBoost算法出现之前的Boosting算法也有类似的性质,但学习之前需要事先知道λt的下限,这在实际当中是很难获得的。而AdaBoost可以在每轮训练中调整预测函数的错误率,体现出它的自适应性,因此不存在这样的问题。在此基础上,Schapire和Freund用VC维从训练误差的角度对Boosting算法的泛化误差进行了分析。VC维是学习算法复杂度及其学习能力的度量。推导出其泛化误差的上限为:Pˆr(H(x)≠y)+Oˆ(Tdm−−−√)(3)Ρ^r(Η(x)≠y)+Ο^(Τdm)(3)其中,m为训练例个数,d为学习算法的VC维,T为训练轮数,Pˆr(⋅)Ρ^r(⋅)表示对训练集的经验概率。式(3)表明,若训练轮数T过大,将导致过适应。但大量的试验表明,Boosting不但能够提高学习精度,而且在训练了几千轮之后也不会发生过适应现象,而且其泛化误差在训练误差已经降到零后仍会继续降低。Schapire和Freund在文献中用BoostingC4.5对UCI中的“letter”样本集进行分类,图1是得出的相对于迭代次数T的误差曲线。图1中,上面一条曲线是泛化误差,下面一条曲线是训练误差。从图中我们可以看出,在训练误差已经达到零后,Boosting仍能继续降低泛化误差,而不会因此出现泛化误差恶化的现象。为了解释这一现象,Schapire等从边界的角度对泛化误差作了分析,样本(x,y)的边界margin(x,y)定义如下:margin(x,y)=y∑tαtht(x)(4)margin(x,y)=y∑tαtht(x)(4)式(4)中αt=1/2ln((1-et)/et),margin的值属于[-1,+1]之间,其值可以被看作是对预测函数H预测结果的可信度。较大的正边界表示可信度高的正确的预测,较大的负边界表示可信度高的错误的预测。图2反映出Boosting对边界的影响。当训练误差降为零后,Boosting仍然会继续提高训练样本的边界值,从而增大了最小边界,使分类的可靠性增加,使得泛化误差也能够继续下降。Schapire给出了泛化误差的上限:Pˆr(margin(x,y)≤θ)+Oˆ(dmθ2−−−√)(5)Ρ^r(margin(x,y)≤θ)+Ο^(dmθ2)(5)从式(5)可以看出,泛化误差与训练轮数T无关,也就是说泛化误差不受训练轮数影响,这也解释了图1中的现象。Grove指出用Schapire提出的边界理论解释Boosting的泛化问题存在一定局限,并在文献中构造了LPBoost算法。LPBoost算法可以找到更大的最小边界的最大值,但其泛化性能却比Boosting要差,Grove指出仅仅提高最小边界的最大值并不能作为提高泛化性能的依据,有时反而会增大泛化误差。之后,越来越多的文献也指出,Boosting算法对噪声敏感,在不存在噪声的前提下,Boosting算法有较好的泛化性能。4uping试验自从Boosting算法出现以来,在机器学习领域备受关注,得到了很多的应用。Quinlan将C4.5决策树作为弱学习器,以UCI的27个数据库为数据集,选择迭代次数为10次。试验结果表明,使用单个决策树,其平均误差为15.66%,使用Boosting能够使平均误差降低到13.36%。Boosting能够使泛化误差明显降低,但Quinlan指出,Boosting在有些情况下会出现过适应。Schwenk和bengio采用两层前向神经网络作为弱学习器,进行手写体字符识别,对UCI中的字符数据集进行测试,结果表明误差降低到1.4%。Boosting在实际当中也得到了很多应用,例如,语音识别、医疗诊断等。文献将高斯模型作为弱分类器应用于音频识别。文献将Boosting用于人脸检测。文献将Boosting与Stumps结合用于进行文本分类。文献将Boosting方法和遗传算法结合进行滚动轴承的故障诊断。5算法的选择Boosting算法的简单高效受到了人们的很多关注。它使得在实际应用中,我们不必费力地寻找预测精度很高的算法,而只需找到一个比随机猜测略好的弱学习算法,就可以通过Boosting将其提升为强学习算法,从而也相应地达到提高预测精度的目的。Boosting要求“不稳定”的分类方法,例如:决策树、神经网络算法等。所谓不稳定指的是数据集的小的变动能够使得分类结果显著地变动。Boosting算法具有很多优点,它有较高的正确率,不需要先验知识,只需要选择合适的迭代次数等。但是它速度慢,在一定程度上依赖于训练数据集合和弱学习器的选择,训练数据不充足或者弱学习器太过“弱”,都将导致其训练精度的下降。另外,Boosting易受到噪声的影响,这是因为它在迭代过程中总是给噪声分配较大的权重,使得这些噪声在以后的迭代中受到更多的关注。目前,B