learn

Learn++算法综述

摘要：learn++算法是一种适用于监督学习的、集成的、增量学习的、能学习新

类的算法。在进行训练时，把训练数据按不同子集分别进行训练。采用投票机制，将

若干弱学习机以权重投票的方式集成。在线学习时，不需要载入原始数

据。具有训练耗时少、所需存储空间少、算法效率高、训练结果不受训练数据顺序影

响等优点。也存在不少缺点，为此提出了不少改进算法。

关键词：learn++;增量学习；监督学习；综述

引言

Learn++最早由Polikar等人于2001年提出，是一种用于解决分类问题的、监

督学习的神经网络增量训练算法，主要针对多分类问题，其灵感来自于

AdaBoost集成算法［15］。它在数据融合、信号的无损评价等诸多模式识别领域有重

要应用［1,3,4,5］。Learn++算法能够增量的学习新来数据，即使新来数据属于新的

类，而不忘记已经学习到的旧知识，较好的解决了稳定性/可塑性难题⑹。

Learn++是一种集成算法，它采用投票机制，将若干弱学习机以权重投票的方式集成(分

类性能高的弱学习机，具有高的投票权重)。弱学习机的“投票权重”依赖与其正确分

类数据的权值，而数据的权值又根据分类结果的正确与否而动态变化。在这一点上，

learn++和AdaBoost很相似。learn++和AdaBoost最大的区别在于：AdaBoost的目的

在于提高分类器的分类性能，而learn++的目的在于增量的学习新来的数据［2］。

二算法步骤

Learn++算法的主要步骤如下

1初始化阶段：

1.1获得原始数据集D，并将D分成K个子数据集S(k)。其中k=1,2…K，S(k)

=［(X1,yj(X2,y2).......(Xm,ym)］。

1.2确定弱学习机的个数T。

1.3获得T个弱学习机。

2训练阶段：

循环k=1,2....K

2.1初始化w』)=D』)=1/m(k),?i,i=1,2

样本i的权重，m(k)代表数据集的数量。

m(k)。其中W1(i)代表

2.2循环t=1,2

2.2.1将每个样本的概率归一化，建立分布Dt

2.2.2根据Dt任意选择训练子集T&和测试子集TEt；

223用TRt训练弱学习机并得到假设ht：X?Y;

2.2.4计算此假设在训练子集和测试子集上的错误率：

&=Ei：h(xjMyjDt(i)onTRt+TEt

如果§>1/2.删除此弱学习机，回到步骤2.2.2.否则计算正规

化错误率：

Bt=Et/(1-Et)

2.2.5将本次循环已经训练的弱学习机hs进行集成，其中s=1,2….t,

得假设

1

Ht=argmaxy

€丫l:ht(x)=ylog(看)。

计算ht的在训练子集TRt和测试子集TEt的错误率:

m

Et=刀Dt(i)=刀Dt(i)[Ht(Xi工yi]

i：h(Xi)Myii=1

如果Et>1/2,删除弱学习机ht,t=t-1。回到步骤2.2.2。

2.2.6设Bt=Et/(1-Et)。修改数据集中每个样本的权值：

最终假设为:

D

t

=3t

??t+1(i)=??t(i)xifHt(xi)=yi

其他

Hfinai=argmaxy€Y刀

k=1

t：ht(x)=y

1

lOg(

□

三算法评价及相关改进算法

从上述算法步骤可看出learn++算法具有诸多优点

(1)需要设置的参数相对较少。从上述算法步骤可看出，learn++算法仅需设置子

数据集的个数K和弱学习机的个数k两个参数。

⑵能增量的学习新来的数据，而不会忘记“旧知识”，有效的避免的神经网络

学习中“突然遗忘”［7］现象。当然Learn++算法在增量的学习新来信息的过程中，

有一些“旧知识”确实会被忘记，但是这些被忘记的“旧知识”是可以忽略的［1］.

(3)因为learn++算法能够增量的学习新来的数据，所以它不需要存储

“旧

数据”，所需存储空间少。

(4)训练时间短。通常的强学习算法为找到最优分类面，而不得不进行大量

循环运算。learn++算法采用若干弱算法权重投票机制，而训练弱算法不需要获得最

优分类面，仅需获得一个大致分类面，所以训练时间短；同时learn++算法

对子集进行分别训练，因而其训练时间将进一步减少［1］。

(5)能够增量的学习新的类。

⑹不受训练数据的顺序影响［8］.

和众多其他算法一样，Learn++算法也存在诸多缺点，为此提出了不少改进算法。

当有新类出现时，learn++算法会遭受“投票制胜”(out-voting)困境。为了识

别新的类，根据learn++算法的投票原则，必须得构造足够多的、权重较高的、能识

别新类的学习机(也叫假设)，以使新类能够在“投票”中获得足够的“票数”支持而

被正确识别，但这会产生大量的、多余的学习器，且需要一定“教训”(新类刚出现

时，通常因为“票数”不够而不能被正确识别)。为克服此缺点，

Muhlbaier等人在［9］中提出了Learn++.MT算法。在Learn++.MT算法中，学习机的

投票权重是根据每个具体样本的分类结果而确定的，而不是learn++算法中的、根据

学习机对每个样本集的分类结果而确定的。

Learn++算法中，如果学习机对样本的识别率低于0.5，便放弃此学习机。如果

较多的学习机对数据集的识别率都低于0.5,所构造的分类器可能就不能很好

的代表此数据集。为此，JianYang等人在［10］中提出了learn++.H算法。它是通过

错误相关分区(ECP)去构造学习机的。

在神经网络学习中，为了使分类器具有足够的的性能足够好，必须要有足够

多的训练样本［11］。结论也可以证明，如果训练样本只属于一个类，即使样本的数

量足够多，它的分类性能仍然会比较低。同样的，在learn++算法中，为了使

每个学习机的分类性能较好，必须要有足够数量的数据集，且数据集中的数据不能只

属于一个类。如果不满足这个要求，learn++算法所构造的分类器的分类性

能便不会太好。同时，为了使分类器的性能够好，所选择的训练样本必须具有代表性。

如果训练的样本缺乏代表性，所构造的分类器的性能仍然不会太好。为了克服上述两

个缺点，使算法所构造的分类器具有更好的泛性，Al-Jun等人在［12］

中提出了一种改进的learn++算法，较好的解决上述问题。

Learn++算法也会遭受“数据非平衡”问题。在learn++算法中，如果每个数据集

的数据数量不一样，或者数据集的数量一样，而具体某类数据的数量远远大于其它类

的数量，都会引起“数据非平衡”问题。为克服这个问题，Muhlbaier

等人在［13］中，提出了learn++.MT算法。在learn++.MT算法中，引入的一个参数：

某个数据集中特定的类的样本数量跟所有数据集中该类的样本数量的比值。根据这个

参数及每个样本的分类结果，从而确定每个学习机的权重。

还有一些其它的learn++的改进算法。在［14］中，Gangardiwala等人提出了一种

新的学习机权重分配方式：依据每个样本被分类成功的概率而确定权重。

四结语

Learn++，作为一种监督学习的神经网络增量训练算法，具有能增量学习、设置

参数少、训练时间短、所需存储空间少、能学习新的类等诸多优点。但也存在不少不

足，例如会遭受“数据非平衡问题”等,为此提出了不少基于learn++的改进算法。

接下来的工作包括：⑴能否将learn++算法和AdaBoost算法结合。AdaBoost算

法能够确保算法的鲁棒性，防止算法性能恶化，而learn++算法则能增量学习。因此

如果能将两者优点结合，将产生一个性能好、能增量学习的全新算法.(2)能

否动态增加、修改或删除学习机。在learn++算法中，学习机的个数及具体算法

是由我们事先确定，而不能改变。但如果learn++算法能够随环境的改变而动态

改变学习机，便能够使learn++算法具备“概念漂移”功能，从而使learn++算法具

有更广的适用范围。(3)提出新的学习机权重分配方法。目前基于learn++算法

已经提出了不少新的学习机权重分配方法，是否还有更好的权重分配方法，值得

我们去思考和研究。

参考文献：

[1]:r,,,"Learn++:anincrementalleanningalgorithmfor

supervidneuralnetworks"[J].IEEETransactionsonSystems,ManandCyberneticsPartC:

ApplicationsandReviews,2001,31(4):497-508.

[2]:r,”Learn++:ANINCREMENTALLEARNINGALGORITHMBASEDON

PSYCHO-PHYSIOLOGICALMODELSOFLEARNING”[C],2001Proceedingof23rdAnnualEMBSInternatio

nalConference,PP.672-673,2001.

[3]:DeviParikh,,"CombiningClassifiersforMultinsorData

Fusion",pp.1232-1237,2004.

[4]:GenevieveJacques1,re,"MULTIRESOLUTIONWAVELETANALYSISAND

ENSEMBLEOFCLASSIFIERSFOREARLYDIAGNOSISOFALZHEIMERSDISEASE",ICASSP,PP.389-391,2005.

[5]:DeviParikh,,JophOagaro,”EnmbleofClassifiersApproachforNDT

DataFusion”2?04IEEEInternationalUltrasonics,Ferroelectrics,andFrequencyControlJoint

50thAnniversaryConference,PP.1063-1065,2004

[6]:erg,“Nonlinearneuralnetworks:principles,mechanismsaacbhitectures,

NeuralNetw.,vol.1,no.1,PP.17-61,1988.

[7]:M。McCloskey,,"Catastropicinterfereneeinconnectionistnetworks:the

quentialleariningproblem",inTHEPsychologyoflearningandMotivation,G.H,Bower,ed,vol

24,PP.109-164,AcademicPress,SanDiego,1989

[8]:r,ck,"Learn++:AClassifierIndependentIncrementalLearning

AlgorithmforSupervidNeuralNetworks”，PP.1742-1747,2002.

[9]ier,,":ANewApproachtoIncrementalLearning",

PP.52-61,2004

[10]JiangYang,Siwei,"HybridCommitteeMachineforIncrementalLearning

",PP.391-395,2005

[11]Blummer,eucht,"LearnabilityandtheVapnic-ChervonenkisDimension

"[J],JournaloftheAssociationforComputingMachinery,36:929-965,1989

[12]AI-JUNLI,"ANIMPROVEDALGORITHMINCREMENTAL

LEARN++",Proceedingsofthe2008InternationalConferenceOnWaveletAnalysisandPatter

nRecognition,PP.310-315,2008

[13]ier,s,"IncrementalLearningfromUnbalaneed

Data",PP.1057-1062,2004.

[14]diwala,r,"DynamicallyWeightedMajorityVotingforIncremental

LearningandComparisonofThreeBoostingBadApproaches",ProceedingsofInternationalJoi

ntConferenceonneuralNetworks,PP.1131-1136,2005

[15]:re,"Thestrengthofweaklearning",MachineLearning,vol,

5,pp.197-227,1990.