机器学习的几何观点.ppt

AGeometricPerspectiveonMachineLearning,何晓飞浙江大学计算机学院,MachineLearning:theproblem,f,何晓飞,Information(trainingdata),f:XY,XandYareusuallyconsideredasaEuclideanspaces.,ManifoldLearning:geometricperspective,ThedataspacemaynotbeaEuclideanspace,butanonlinearmanifold.,ManifoldLearning:thechallenges,Themanifoldisunknown!Wehaveonlysamples!HowdoweknowMisasphereoratorus,orelse?HowtocomputethedistanceonM?versus,Thisisunknown:,Thisiswhatwehave:,?,?,orelse?,Topology,Geometry,Functionalanalysis,ManifoldLearning:currentsolution,FindaEuclideanembedding,andthenperformtraditionallearningalgorithmsintheEuclideanspace.,Simplicity,Simplicity,Simplicityisrelative,Manifold-basedDimensionalityReduction,Givenhighdimensionaldatasampledfromalowdimensionalmanifold,howtocomputeafaithfulembedding?Howtofindthemappingfunction?Howtoefficientlyfindtheprojectivefunction?,AGoodMappingFunction,Ifxiandxjareclosetoeachother,wehopef(xi)andf(xj)preservethelocalstructure(distance,similarity)k-nearestneighborgraph:Objectivefunction:Differentalgorithmshavedifferentconcerns,LocalityPreservingProjections,Principle:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.,LocalityPreservingProjections,Principle:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.,Mathematicalformulation:minimizetheintegralofthegradientoff.,LocalityPreservingProjections,Principle:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.,Mathematicalformulation:minimizetheintegralofthegradientoff.,StokesTheorem:,LocalityPreservingProjections,Principle:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.,Mathematicalformulation:minimizetheintegralofthegradientoff.,StokesTheorem:,LPPfindsalinearapproximationtononlinearmanifold,whilepreservingthelocalgeometricstructure.,ManifoldofFaceImages,Expression(SadHappy),Pose(RightLeft),ManifoldofHandwrittenDigits,Thickness,Slant,Learningtarget:TrainingExamples:LinearRegressionModel,ActiveandSemi-SupervisedLearning:AGeometricPerspective,GeneralizationError,GoalofRegressionObtainalearnedfunctionthatminimizesthegeneralizationerror(expectederrorforunseentestinputpoints).MaximumLikelihoodEstimate,Gauss-MarkovTheorem,Foragivenx,theexpectedpredictionerroris:,Gauss-MarkovTheorem,Foragivenx,theexpectedpredictionerroris:,Good!,Bad!,ExperimentalDesignMethods,Threemostcommonscalarmeasuresofthesizeoftheparameter(w)covariancematrix:A-optimalDesign:determinantofCov(w).D-optimalDesign:traceofCov(w).E-optimalDesign:maximumeigenvalueofCov(w).Disadvantage:thesemethodsfailtotakeintoaccountunmeasured(unlabeled)datapoints.,ManifoldRegularization:Semi-SupervisedSetting,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,?,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,?,randomlabeling,ManifoldRegularization:Semi-SupervisedSetting,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,?,randomlabeling,activelearning,activelearning+semi-supervsedlearning,ManifoldRegularization:Semi-SupervisedSetting,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructure,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,ComputenearestneighborgraphG,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,ComputenearestneighborgraphG,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,ComputenearestneighborgraphG,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,ComputenearestneighborgraphG,UnlabeledDatatoEstimateGeometry,Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure,ComputenearestneighborgraphG,LaplacianRegularizedLeastSquare,LinearobjectivefunctionSolution,ActiveLearning,Howtofindthemostrepresentativepointsonthemanifold?,Objective:Guidetheselectionofthesubsetofdatapointsthatgivesthemostamountofinformation.Experimentaldesign:selectsamplestolabelManifoldRegularizedExperimentalDesignSharethesameobjectivefunctionasLaplacianRegularizedLeastSquares,simultaneouslyminimizetheleastsquareerroronthemeasuredsamplesandpreservethelocalgeometricalstructureofthedataspace.,ActiveLearning,Inordertomaketheestimatorasstableaspossible,thesizeofthecovariancematrixshouldbeassmallaspossible.D-optimality:minimizethedeterminantofthecovariancematrix,AnalysisofBiasandVariance,Selectthefirstdatapointsuchthatismaximized,Supposekpointshavebeenselected,choosethe(k+1)thpointsuchthat.Update,Thealgorithm,ConsiderfeaturespaceFinducedbysomenonlinearmapping,and=K(xi,xi).K(,):positivesemi-definitekernelfunctionRegressionmodelinRKHS:ObjectivefunctioninRKHS:,NonlinearGeneralizationinRKHS,Selectthefirstdatapointsuchthatismaximized,Supposekpointshavebeenselected,choosethe(k+1)thpointsuchthat.Update,NonlinearGeneralizationinRKHS,ASyntheticExample,A-optimalDesign,LaplacianRegularizedOptimalDesign,ASyntheticExample,A-optimalDesign,LaplacianRegularizedOptimalDesign,Combiningactiveandsemi-supervisedlearningforCBIR,Firstiteration,Seconditeration,Applicationtoimage/videocompression,Videocompression,Topology,CanwealwaysmapamanifoldtoaEuclideanspacewithoutchangingitstopology?,？,Topology,SimplicialComplex,HomologyGroup,BettiNumbers,EulerCharacteristic,GoodCover,SamplePoints,Homotopy,Numberofcomponents,dimension,Topology,TheEulerCharacteristicisatopologicalinvariant,anumberth