Successive overrelaxation for support vector machines

《Successive overrelaxation for support vector machines》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1032IEEETRANSACTIONSONNEURALNETWORKS,VOL.10,NO.5,SEPTEMBER1999SuccessiveOverrelaxationforSupportVectorMachinesOlviL.MangasarianandDavidR.MusicantAbstractÐSuccessiveoverrelaxation(SOR)forsymmetriclin-maximizethemarginwithrespecttoboththenormaltotheearcomplem

2、entarityproblemsandquadraticprogramsisusedseparatingplanesaswellastheirlocationusingastrategytotrainasupportvectormachine(SVM)fordiscriminatingfrom[19].betweentheelementsoftwomassivedatasets,eachwithmillionsInSectionII,westateourdiscriminationproblemasaclas

3、-ofpoints.BecauseSORhandlesonepointatatime,similartoPlatt'ssequentialminimaloptimization(SMO)algorithmwhichsicalsupportvectormachine(SVM)problem(1)andintroducelighthandlestwoconstraintsatatimeandJoachims'SVMwhichourvariantoftheproblem(4)thatallowsustostatei

4、tsdual(6)handlesasmallnumberofpointsatatime,SORcanprocessveryasanSOR-solvableconvexquadraticprogramwithbounds.largedatasetsthatneednotresideinmemory.ThealgorithmWeshowinPropositionII.1thatbothproblemsyieldtheconvergeslinearlytoasolution.Encouragingnumerical

5、resultssameanswerunderfairlybroadconditions.InSectionIII,wearepresentedondatasetswithupto10000000points.Suchmas-sivediscriminationproblemscannotbeprocessedbyconventionalstateourSORalgorithmandestablishitslinearconvergencelinearorquadraticprogrammingmethods,

6、andtoourknowledgeusingapowerfulresultofLuoandTseng[3,Proposition3.5].havenotbeensolvedbyothermethods.Onsmallerproblems,InSectionIV,wegivenumericalresultsforproblemswithlightSORwasfasterthanSVMandcomparableorfasterthandatasetswithasmanyas10000000points.Secti

7、onVdrawsSMO.someconclusionsandpointsoutfuturedirectionssuchasIndexTermsÐMassivedatadiscrimination,successiveoverre-parallelSORimplementationsthatmayleadtothesolutionlaxation,supportvectormachines.ofevenlargerproblems.Awordaboutournotation.Allvectorswillbeco

8、lumnvec-I.INTRODUCTIONtorsunlesstransposedtoarowvectorbyaprimesuperscriptUCCESSIVEoverrelaxation(SOR),originallydevelopedForavectorinthe-dimensionalrealspacetheplusSforthesolutionoflargesystemsoflinear