核函数在模式识别中的应用

@support-vector.net•KernelMethodsareanewclassofpatternanalysisalgorithmswhichcanoperateonverygeneraltypesofdataandcandetectverygeneraltypesofrelations.•Correlation,factor,clusteranddiscriminantanalysisarejustsomeofthetypesofpatternanalysistasksthatcanbeperformedondataasdiverseassequences,text,images,graphsandofcoursevectors.•Themethodprovidesalsoanaturalwaytomergeandintegratedifferenttypesofdata.•Kernelmethodsofferamodularframework.•Inafirststep,adatasetisprocessedintoakernelmatrix.Datacanbeofvarioustypes,andalsoheterogeneoustypes.•Inasecondstep,avarietyofkernelalgorithmscanbeusedtoanalyzethedata,usingonlytheinformationcontainedinthekernelmatrix•Computationallymostkernel-basedlearningalgorithmsreducetooptimizingconvexcostfunctionsortocomputinggeneralizedeigenvectorsoflargematrices.•Kerneldesignisbasedonvariousmethods.Fordiscretedata(egsequences)oftenusemethodslikedynamicprogramming,branchandbound,discretecontinuousoptimization…•Combinationisveryefficientbutstillcomputationallychallenging,forourambitions…•Theflexiblecombinationofappropriatekerneldesignandrelevantkernelalgorithmshasgivenrisetoapowerfulandcoherentclassofmethods,whosecomputationalandstatisticalpropertiesarewellunderstood,•Increasinglyusedinapplicationsasdiverseasbiosequencesandmicroarraydataanalysis,textmining,machinevisionandhandwritingrecognition.•Generalintroductiontokernelmethods•Discussionofspecifickernel-basedalgorithms•Discussionofspecifickernelsforstrings•Fewexamplesbasedontextandsequencedata•Discussionofhowtocombineheterogeneousdatatypes(maybe)•Focusoneigen-algorithmsfromclassicmultivariatestats,combinedwithkernels…•KernelMethodsworkby:1-embeddingdatainavectorspace2-lookingfor(linear)relationsinsuchspace•Ifmapchosensuitably,complexrelationscanbesimplified,andeasilydetectedxx→φ()•1-Muchofthegeometryofthedataintheembeddingspace(relativepositions)iscontainedinallpairwiseinnerproducts*Wecanworkinthatspacebyspecifyinganinnerproductfunctionbetweenpointsinit(ratherthantheircoordinates)•2-Inmanycases,innerproductintheembeddingspaceverycheaptocompute....x1,xnx1,x2x1,x1xn,xnxn,x2xn,x1...x2,xnx2,x2x2,x1*Innerproductsmatrix•Algorithmsthatcanbeusedwithinnerproductinformation:–RidgeRegression–FisherDiscriminant–PrincipalComponentsAnalysis–CanonicalCorrelationAnalysis–SpectralClustering–SupportVectorMachines–Lotsmore……•FornowletusassumewehaveavectorspaceXwherethedatalives,andwherewecandefineinnerproducts…•AndwealsohaveasampleSofpointsfromthatspace…xzxziii,=∑wxb,+=0=')(Weconsiderlinearfunctionslikethis:theycouldbetheresultofFisherDiscriminantAnalyis,Ridgeregression,PCA,etc…Weconsiderre-writingthemasafunctionofthedatapoints(seeperceptronasexample)(wehaveasampleSofdatapoints)∑=iiixwα∑∈+=+=Sxiiibxxbxwxf'')(α…∑∑∑∑∑∑∑∈∈⊥∈⊥∈∈=+=+=+===SxjiiSxjiiSspanxjiiSxjiijSspanxiiSxiiSxiiiiiiiiixxxxxxxxxfxxwxxxwxf'0''')('')()()(αααααααThelinearfunctionf(x)canbewritteninthisformWithoutchangingitsbehavioronthesampleSeeWahba’sRepresentertheoremfortheorybehind…Notcrucialforthistalkforallalgorithmsweconsiderthisisalwaysvalid•Thisrepresentationofthelinearfunctiononlyneedsinnerproductsbetweendatapoints(nottheircoordinates!)•JUSTREWRITTENTHESAMETHINGfrom#parametersw=dimensionto#parametersα=samplesize!•Ifwewanttoworkintheembeddingspacejustneedtoknowthis:xx→φ()Kxxxx(,)(),()1212=φφfxwxbyxxbiii(),,=+=+∑αwyxiii=∑αPardonmynotation(,)(),()1212=φφKernelsarefunctionsthatreturninnerproductsbetweentheimagesofdatapointsinsomespace.Byreplacinginnerproductswithkernelsinlinearalgorithms,weobtainveryflexiblerepresentationsChoosingKisequivalenttochoosingΦ(theembeddingmap)Kernelscanoftenbecomputedefficientlyevenforveryhighdimensionalspaces–seeexample===+==++====(,);(,);,()(,,),(,,)(),()1212211222121222221122122212122212222φφ(efficiently).∑=iiixxKxf),()(α…•Kernelscanbedefinedongeneraltypesofdata(aslongasfewconditionsaresatisfied–seelater)•Manyclassicalalgorithmscannaturallyworkwithgeneral,non-vectorial,data-types!•Wecanrepresentgeneraltypesofrelationsongeneraltypesofdata…•Kernelsexisttoembedsequences,trees,graphs,generalstructures•SemanticKernelsfortext,Kernelsbasedonprobabilisticgraphicalmodels•etc•Givenasa