半监督支持向量机的研究

ResearchonSemi-SupervisedSVMs(半监督支持向量机的研究)Yu-FengLiNationalKeyLaboratoryforNovelSoftwareTechnology,NanjingUniversity,ChinaURL::[e-mail]’13,Shanghai://lamda.nju.edu.cnLabeledDataIsExpensiveHowever,labelingprocessisexpensiveinmanyrealtasksDiseasediagnosisDrugdetectionImageclassificationTextcategorization…HumaneffortsandmaterialresourcesCollectionofunlabeleddataisusuallycheaperTwopopularschemesforexploitingunlabeleddatatohelpsupervisedlearningSemi-supervisedlearning:thelearnertriestoexploittheunlabeledexamplesbyitself.Activelearning:thelearneractivelyselectssomeunlabeledexamplestoqueryfromanoracleSeveralSurveysandBooksO.Chapelleetal.Semi-supervisedlearning.MITPressCambridge,2006.X.ZhuandA.Goldberg.Introductiontosemi-supervisedlearning.Morgan&ClaypoolPublishers,2009.Z.-H.ZhouandM.Li.Semi-supervisedlearningbydisagreement.KnowledgeandInformationSystems,24(3):415–439,2010.周志华.基于分歧的半监督学习,特邀综述.自动化学报.2013年11月.SSLearnerSLearnerGenerativemethods[Miller&Uyar,1997;Nigametal.,2000;Cozman&Cohen,2002]Co-training/Disagreement-basedmethods[Blum&Mitchell,1998;Balcanetal.,2005;Zhou&Li,2010]Graph-basedmethods[Blum&Chawla,2001;Zhuetal.,2003;Zhouetal.,2005;Belkinetal.,2006]Semi-supervisedsupportvectormachines(S3VMs)[Vapnik,1998;Bennett&Demiriz,1999;Joachims,1999;Chapelle&Zien,2005]Theseminalwork[Blum&Mitchell,1998]haswonthe‘10-yearbestpaper’awardinthe25thInternationalConferenceonMachineLearning(ICML’08).Theseminalwork[Zhuetal.,2003]haswonthe‘10-yearbestpaper’awardinthe30thInternationalConferenceonMachineLearning(ICML’13).Theseminalwork[Joachims,1999]haswonthe‘10-yearbestpaper’awardinthe26thInternationalConferenceonMachineLearning(ICML’09).S3VMsLarge-marginseparator(or,low-densityseparator)LabeledDataUnlabeledDataIn[Vapnik,SLT’98],itisshownthatlargemargincouldhelpimprovethegeneralizationlearningbound.://lamda.nju.edu.cnS3VMs:FormulationS3VMsareanmixed-integerprogram,thusintractableingeneral.SVMPriorknowledgeTextCategorization[Joachims1999;Joachims,2002]EmailClassification[Kockelkornetal.,2003]ImageRetrieval[Wangetal.,2003]Bioinformatics[Kasabov&Pang,2004]NamedEntityRecognition[Goutteetal.,2002]…ScalabilityofS3VMsWellSVM[Lietal.,JMLR13]EfficiencyofS3VMsMeanS3VM[Lietal.,ICML09]SafenessofS3VMsS4VM[LiandZhou,ICML11]CostsensitivityofS3VMsCS4VM[Lietal.,AAAI10]“多”“快”“好”“省”ScalabilityofS3VMsWellSVM[Lietal.,JMLR13]EfficiencyofS3VMsMeanS3VM[Lietal.,ICML09]SafenessofS3VMsS4VM[LiandZhou,ICML11]CostsensitivityofS3VMsCS4VM[Lietal.,AAAI10]“多”“快”“好”“省”GlobaloptimizationBranch-and-Bound[Chepelleetal.,NIPS2006]DeterministicAnnealing[Sindhwanietal.,ICML2006]ContinuationMethod[Chepelleetal.,ICML2006]Pro:goodperformanceonverysmalldatasetsCon:poorscalability(i.e.,couldnothandlewithmorethanseveralhundredexamples)LocaloptimizationLocalConbinatorialSearch[Joachims,ICML1999]AlternatingOptimization[Zhangetal.,ICML2009]ConstrainedConvex-ConcaveProcedure(CCCP)[Collobertetal.,JMLR2006]Pro:goodscalabilityCon:sufferfromlocaloptima,suboptimalperformanceSDPconvexrelaxation[Xuetal.,2005;DeBieandCristianini,2006]RelaxS3VMsasconvexSemi-DefiniteProgramming(SDP)SDPtypicallyscalesO(n6.5)wherenisthesamplesize[Zhangetal.,TNN2011].Pro:promisingperformanceCon:poorscalability(i.e.,couldnothandlewithmorethanseveralthousandexamples)CanwehaveascalableandconvexS3VM?WellSVM(WeaklyLabeledSVM)Hard,NotScalableEasy,ScalableCombinationEasy,Scalable…WellSVM[Lietal.,JMLR13]Step1:Initializealabelassignmenty0forunlabeleddataandsettheworkingsetC=y0.Step2:Generateaninformativelabelassignment𝐲andupdateC=C∪y.Step3:LearnanoptimalcombinationforthelabelassignmentsinCsuchthatthemarginismaximized.Step4:RepeatSteps2-3untilconvergence.CombinationWellSVM[Lietal.,JMLR13]y0yS3VMsPrimalS3VMsDualWellSVM[Lietal.,JMLR13]MinimaxRelaxationAdvantagesofWellSVMAtightandconvexrelaxationofS3VMsAtleastastightasexistingconve