支持向量机与文本分类

SupportVectorMachines InstituteofComputationalLinguisticsZhihuiJin outline LinearSVMNon LinearSVMTextCategorization LinearSVM SeparableCase Considertheproblemofseparatingthesetoftrainingvectorsbelongingtotwoseparateclasses D x1 y1 xl yl xi Rd yi 1 1 withhyperplanew x b 0Thesetofvectorsissaidtobeoptimallyseparatedbythehyperplaneifitisseparatedwithouterrorandthedistancebetweentheclosestvectortothehyperplaneismaximal Hyperplaneclassifiers g x w x bUsuallyweaddtheconstraint g x w x b 1Thatis allthetrainingexamplessatisfy equivalently Letd d betheshortestdistancefromthehyperplanetotheclosestpositive negative example Themarginofthehyperplaneisdefinedtobed d separatinghyperplane w x b 0decisionfunction f x sgn w x b Themarginisgivenby HencethehyperplanethatoptimallyseparatesthedataistheonethatminimizeSubjectto dualproblemmaximize subjectto i 0and AccordingtoKuhn Tuckerconditiononlythepointswhichsatisfywillhavenon zeroLagrangemultipliers ThesepointsaretermedSupportVectors SV w x b 0 Supportvector LinearSVM Non SeparableCase lobservationsconsistingofapair xi Rd i 1 landtheassociated label yi 1 1 Introducepositiveslackvariables i andmodifytheobjectivefunctiontobe correspondstotheseparablecase Non LinearSVM InthecasewherealinearboundaryisinappropriatetheSVMcanmaptheinputvector x intoahighdimensionalfeaturespace z Bychoosinganon linearmapping theSVMconstructsanoptimalseparatinghyperplaneinthishigherdimensionalspace onlyrequiresdotproducts Optimalproblem maximize subjectto i 0andDecisionfunction Kernelfunction TextCategorization InductivelearningInpute Output f x confidence class Inthecaseoftextclassification theattributearewordsinthedocument andtheclassesarethecategories PROPERTIESOFTEXT CLASSIFICATIONTASKS High DimensionalFeatureSpace SparseDocumentVectors HighLevelofRedundancy Textrepresentationandfeatureselection BinaryfeaturetermfrequencyInversedocumentfrequencynisthetotalnumberofdocumentsDF w isthenumberofdocumentsthewordoccursin LearningSVMS TolearnthevectoroffeatureweightsLinearSVMSPolynomialclassifiersRadialbasisfunctions processing TextfilesareprocessedtoproduceavectorofwordsSelect300wordswithhighestmutualinformationwitheachcategory removestopwords Aseparateclassifierislearnedforeachcategory Anexample Reuters trends controversies Category interestWeightvectorlargepositiveweights prime 70 rate 67 interest 63 rates 60 anddiscount 46 largenegativeweights group 24 year 25 sees 33 world 35 anddlrs 71 TextCategorizationResults Dumaisetal 1998 PapersontextcategorizationusingSVMS ThorstenJoachims joachims 01a AStatisticalLearningModelofTextClassificationforSupportVectorMachinesThorstenJoachims joachims 99c Tra