Performance and Efficiency Recent Advances in Supe

PerformanceandEfficiency:RecentAdvancesinSupervisedLearningSHENGMAANDCHUANYIJIThispaperreviewsrecentadvancesinsupervisedlearningwithafocusontwomostimportantissues:performanceandefficiency.Performanceaddressesthegeneralizationcapabilityofalearningmachineonrandomlychosensamplesthatarenotincludedinatrainingset.Efficiencydealswiththecomplexityofalearn-ingmachineinbothspaceandtime.Asthesetwoissuesaregeneraltovariouslearningmachinesandlearningapproaches,wefocusonaspecialtypeofadaptivelearningsystemswithaneuralarchitecture.Wediscussfourtypesoflearningapproaches:traininganindividualmodel;combinationsofseveralwell-trainedmodels;combinationsofmanyweakmodels;andevolutionarycomputationofmodels.Weexploreadvantagesandweaknessesofeachapproachandtheirinterrelations,andweposeopenquestionsforpossiblefutureresearch.Keywords—Evolutionarycomputation,hybridmodels,neuralnetworks,supervisedlearning.I.INTRODUCTIONInmanyimportantapplicationareassuchassignalpro-cessing,patternrecognition,control,andcommunication,nonlinearadaptivesystemsareneededtoapproximateun-derlyingnonlinearmappingsthroughlearningfromex-amples.Inorderforapproximationstobesufficientlyaccurate,agoodperformanceisrequiredfornonlinearadaptivesystems.Meanwhile,manyapplications,especiallythoseinemergingareasofwirelesscommunicationandnetworking[24],[38],[79],[95],requirethelearningtobedoneinrealtimeinordertoadapttoarapidlychangingstochasticenvironment.OtherapplicationssuchasdataminingandsearchingtheWebneedtodealwithverylargedatasets[37],[66],andthusthelearningtimemustscalenicelywithrespecttothesizeofdatasets.Sincethesizeoflearningmachinesdeterminesthememoryrequiredforimplementation,alearningmachinewithacompactstructureispreferred.Therefore,achallengingproblemishowtodevelopadaptivelearningsystemswithacompactManuscriptreceivedOctober30,1998;revisedApril2,1999.ThisworkwassupportedbytheNationalScienceFoundationunderECS-9312594and(CAREER)IRI-9502518.S.MaiswithIBMT.J.WatsonResearchCenter,Hawthorne,NY10532USA(e-mail:[e-mail]).C.JiiswiththeDepartmentofElectrical,Computer,andSystemsEngineering,RensselaerPolytechnicInstitute,Troy,NY12180USA(e-mail:[e-mail]).PublisherItemIdentifierS0018-9219(99)06910-8.structurethatcanachievegoodperformanceandbeadaptedinrealtime.Thegoalofthispaperistoaddresstheimportantissuesofperformanceandreal-timelearningfornonlinearadaptivelearningmachinesbyreviewingrecentworkintheinterdisciplinaryareasofadaptivelearningsystems,statistics,andinformationtheory.Therearetwoaspectswhentheseissuesareinvestigated:architectureofadaptivelearningmachinesandlearningscenarios(approaches).Thelearningscenarioconsideredisthesupervisedlearningfornonparametricnonlinearregres-sionincludingclassificationasaspecialcase.Wediscussseveralgeneralframeworks,suchastheexpectation-maximization(EM)framework,thecombinationscheme,weaklearning,andevolutionaryalgorithms,allofwhichaimatimprovingtheefficiencyandperformanceofalearningmachine.Inordertobecomprehensive,aneuralnetworkisusedasasamplearchitecturetoshowhowthesegeneralframeworksareapplied.Thereasonwhyneuralnetworksarechosenisthattheyhavebeenshowntobeuniversalapproximatorstoageneralclassofnonlinearfunctions[9]andhavebecomepopularrecently.Thegeneralframeworkcanbeappliedtootherlearningmachines.This,however,isnotthefocushere.Insupervisedlearning,performanceaddressestheprob-lemofhowtodevelopalearningmachinetoachieveoptimalperformanceonsamplesthatarenotincludedinatrainingset.Efficiencydealswiththecomplexityofalearningmachineinbothspaceandtrainingtime.Specifically,thespacecomplexityofaneuralnetworkreferstoitssize,andthetimecomplexitycharacterizesthecomputationaltimeneededtodevelopsuchaneuralnetwork.Thesethreeissuesareinterrelated.Theperformanceofasupervisedlearningsystemischaracterizedbyitsgeneralizationerror,whichmeasuresthedistancebetweentheoutputfunctionofatrainedmodelandanunderlyingtargetfunction.Mostexistingmethodsfortrainingneuralnetworksinsupervisedlearningsufferfromanintrinsicprobleminpatternrecognition:thebiasandvariancedilemma[39],[47].Thatis,ifaneuralnetworkistoolarge,1itmayoverfitaparticulartrainingsetand1Forinstance,feedforwardneuralnetworkswithtoomanyneurons.0018–9219/99$10.001999IEEEPROCEEDINGSOFTHEIEEE,VOL.87,NO.9,SEPTEMBER19991519therebyfailtomaintaingoodgeneralizationerror.Asmallneuralnetwork,however,maybesufficienttoapproximateanoptimalsolution.Inaddition,oneimportantalgorith-micproblemishowtodealwithacomplexoptimizationproblemwithpossiblymanylocalminima.Thesizeofalearningmachinecanbecharacterizedbythespacecomplexity,whichisrelatedtothenumberoffreeparameters(forinstance,thenumberofweightsofaneuralnetwork).Alearningmachineisconsideredtobeefficientinspaceifitsspace-complexityscalesasapolynomialfunctionintermsofthedimensionoffeaturevectors.2Ithasbeenfoundthatcompactadaptivelearningsystemslikemultilayerfeedforwardneuralnetworksareefficientapproximatorsofawideclassofsmoothfunctions.Theypossessapolynomialspacecomplexity[10].Otherlearningmachines,whichconsistoflocalizedmodelssuchasnearestneighborclassifiers[27],Parzenwindow