機(jī)器學(xué)習(xí)的幾何觀點(diǎn)-LAMDA課件

AGeometricPerspectiveonMachineLearning何曉飛浙江大學(xué)計(jì)算機(jī)學(xué)院1AGeometricPerspectiveonMacMachineLearning:theproblemf何曉飛Information(trainingdata)

f:X→YXandYareusuallyconsideredasaEuclideanspaces.2MachineLearning:theproblemfManifoldLearning:geometricperspectiveThedataspacemaynotbeaEuclideanspace,butanonlinearmanifold.?

Euclideandistance.?

fisdefinedonEuclideanspace.?ambientdimension? geodesicdistance.?fisdefinedonnonlinearmanifold.?manifolddimension.instead…3ManifoldLearning:geometricpManifoldLearning:thechallengesThemanifoldisunknown!Wehaveonlysamples!HowdoweknowMisasphereoratorus,orelse?HowtocomputethedistanceonM?

versusThisisunknown:Thisiswhatwehave:??orelse…?TopologyGeometryFunctionalanalysis4ManifoldLearning:thechallenManifoldLearning:currentsolutionFindaEuclideanembedding,andthenperformtraditionallearningalgorithmsintheEuclideanspace.5ManifoldLearning:currentsolSimplicity6Simplicity6Simplicity7Simplicity7Simplicityisrelative8Simplicityisrelative8Manifold-basedDimensionalityReductionGivenhighdimensionaldatasampledfromalowdimensionalmanifold,howtocomputeafaithfulembedding?Howtofindthemappingfunction?Howtoefficientlyfindtheprojectivefunction?9Manifold-basedDimensionalityAGoodMappingFunctionIfxiandxjareclosetoeachother,wehopef(xi)andf(xj)preservethelocalstructure(distance,similarity…)k-nearestneighborgraph:Objectivefunction:Differentalgorithmshavedifferentconcerns10AGoodMappingFunctionIfxiLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.11LocalityPreservingProjectionLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.12LocalityPreservingProjectionLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.Stokes’Theorem:13LocalityPreservingProjectionLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.Stokes’Theorem:LPPfindsalinearapproximationtononlinearmanifold,whilepreservingthelocalgeometricstructure.14LocalityPreservingProjectionManifoldofFaceImagesExpression(Sad>>>Happy)

Pose(Right>>>Left)15ManifoldofFaceImagesExpressManifoldofHandwrittenDigitsThicknessSlant16ManifoldofHandwrittenDigitsLearningtarget:TrainingExamples:LinearRegressionModelActiveandSemi-SupervisedLearning:AGeometricPerspective17Learningtarget:ActiveandSemGeneralizationErrorGoalofRegression

Obtainalearnedfunctionthatminimizesthegeneralizationerror(expectederrorforunseentestinputpoints).MaximumLikelihoodEstimate18GeneralizationErrorGoalofReGauss-MarkovTheoremForagivenx,theexpectedpredictionerroris:19Gauss-MarkovTheoremForagiveGauss-MarkovTheoremForagivenx,theexpectedpredictionerroris:Good!Bad!20Gauss-MarkovTheoremForagiveExperimentalDesignMethodsThreemostcommonscalarmeasuresofthesizeoftheparameter(w)covariancematrix:A-optimalDesign:determinantofCov(w).D-optimalDesign:traceofCov(w).E-optimalDesign:maximumeigenvalueofCov(w).Disadvantage:thesemethodsfailtotakeintoaccountunmeasured(unlabeled)datapoints.21ExperimentalDesignMethodsThrManifoldRegularization:Semi-SupervisedSettingMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?22ManifoldRegularization:Semi-Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?randomlabelingManifoldRegularization:Semi-SupervisedSetting23Measured(labeled)points:disMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?randomlabelingactivelearningactivelearning+semi-supervsedlearningManifoldRegularization:Semi-SupervisedSetting24Measured(labeled)points:disUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructure25UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure26UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG27UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG28UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG29UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG30UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG31UnlabeledDatatoEstimateGeoLaplacianRegularizedLeastSquare(BelkinandNiyogi,2006)LinearobjectivefunctionSolution32LaplacianRegularizedLeastSqActiveLearningHowtofindthemostrepresentativepointsonthemanifold?33ActiveLearningHowtofindtheObjective:Guidetheselectionofthesubsetofdatapointsthatgivesthemostamountofinformation.Experimentaldesign:selectsamplestolabelManifoldRegularizedExperimentalDesignSharethesameobjectivefunctionasLaplacianRegularizedLeastSquares,simultaneouslyminimizetheleastsquareerroronthemeasuredsamplesandpreservethelocalgeometricalstructureofthedataspace.ActiveLearning34Objective:Guidetheselection

,Inordertomaketheestimatorasstableaspossible,thesizeofthecovariancematrixshouldbeassmallaspossible.D-optimality:minimizethedeterminantofthecovariancematrixAnalysisofBiasandVariance35

Selectthefirstdatapointsuchthatismaximized,Supposekpointshavebeenselected,choosethe(k+1)thpointsuchthat.UpdateManifoldRegularizedExperimentalDesignWhereareselectedfromThealgorithm36ManifoldRegularizedExperimenConsiderfeaturespaceFinducedbysomenonlinearmappingφ,and<f(xi),f(xj)>=K(xi,xi).K(·,·):positivesemi-definitekernelfunctionRegressionmodelinRKHS:ObjectivefunctioninRKHS:NonlinearGeneralizationinRKHS37ConsiderfeaturespaceFinducSelectthefirstdatapointsuchthatismaximized,Supposekpointshavebeenselected,choosethe(k+1)thpointsuchthat.UpdateKernelGraphRegularizedExperimentalDesignwhereareselectedfromNonlinearGeneralizationinRKHS38KernelGraphRegularizedExperASyntheticExampleA-optimalDesignLaplacianRegularizedOptimalDesign39ASyntheticExampleA-optimalDASyntheticExampleA-optimalDesignLaplacianRegularizedOptimalDesign40ASyntheticExampleA-optimalDApplicationtoimage/videocompression41Applicationtoimage/videocomVideocompression42Videocompression42TopologyCanwealwaysmapamanifoldtoaEuclideanspacewithoutchangingitstopology?…？43TopologyCanwealwaysmapamaTopologySimplicialComplexHomologyGroupBettiNumbersEulerCharacteristicGoodCoverSamplePointsHomotopyNumberofcomponents,dimension,…44TopologySimplicialComplexHomoTopologyTheEulerCharacteristicisatopologicalinvariant,anumberthatdescribesoneaspectofatopologicalspace’sshapeorstructure.1-2012TheEulerCharacteristicofEuclideanspaceis1!0045TopologyTheEulerCharacteristChallengesInsufficientsamplepointsChoosesuitableradiusHowtoidentifynoisyholes(userinteraction?)Noisyholehomotopyhomeomorphsim46ChallengesInsufficientsampleQ&A4747AGeometricPerspectiveonMachineLearning何曉飛浙江大學(xué)計(jì)算機(jī)學(xué)院48AGeometricPerspectiveonMacMachineLearning:theproblemf何曉飛Information(trainingdata)

f:X→YXandYareusuallyconsideredasaEuclideanspaces.49MachineLearning:theproblemfManifoldLearning:geometricperspectiveThedataspacemaynotbeaEuclideanspace,butanonlinearmanifold.?

Euclideandistance.?

fisdefinedonEuclideanspace.?ambientdimension? geodesicdistance.?fisdefinedonnonlinearmanifold.?manifolddimension.instead…50ManifoldLearning:geometricpManifoldLearning:thechallengesThemanifoldisunknown!Wehaveonlysamples!HowdoweknowMisasphereoratorus,orelse?HowtocomputethedistanceonM?

versusThisisunknown:Thisiswhatwehave:??orelse…?TopologyGeometryFunctionalanalysis51ManifoldLearning:thechallenManifoldLearning:currentsolutionFindaEuclideanembedding,andthenperformtraditionallearningalgorithmsintheEuclideanspace.52ManifoldLearning:currentsolSimplicity53Simplicity6Simplicity54Simplicity7Simplicityisrelative55Simplicityisrelative8Manifold-basedDimensionalityReductionGivenhighdimensionaldatasampledfromalowdimensionalmanifold,howtocomputeafaithfulembedding?Howtofindthemappingfunction?Howtoefficientlyfindtheprojectivefunction?56Manifold-basedDimensionalityAGoodMappingFunctionIfxiandxjareclosetoeachother,wehopef(xi)andf(xj)preservethelocalstructure(distance,similarity…)k-nearestneighborgraph:Objectivefunction:Differentalgorithmshavedifferentconcerns57AGoodMappingFunctionIfxiLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.58LocalityPreservingProjectionLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.59LocalityPreservingProjectionLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.Stokes’Theorem:60LocalityPreservingProjectionLocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.Stokes’Theorem:LPPfindsalinearapproximationtononlinearmanifold,whilepreservingthelocalgeometricstructure.61LocalityPreservingProjectionManifoldofFaceImagesExpression(Sad>>>Happy)

Pose(Right>>>Left)62ManifoldofFaceImagesExpressManifoldofHandwrittenDigitsThicknessSlant63ManifoldofHandwrittenDigitsLearningtarget:TrainingExamples:LinearRegressionModelActiveandSemi-SupervisedLearning:AGeometricPerspective64Learningtarget:ActiveandSemGeneralizationErrorGoalofRegression

Obtainalearnedfunctionthatminimizesthegeneralizationerror(expectederrorforunseentestinputpoints).MaximumLikelihoodEstimate65GeneralizationErrorGoalofReGauss-MarkovTheoremForagivenx,theexpectedpredictionerroris:66Gauss-MarkovTheoremForagiveGauss-MarkovTheoremForagivenx,theexpectedpredictionerroris:Good!Bad!67Gauss-MarkovTheoremForagiveExperimentalDesignMethodsThreemostcommonscalarmeasuresofthesizeoftheparameter(w)covariancematrix:A-optimalDesign:determinantofCov(w).D-optimalDesign:traceofCov(w).E-optimalDesign:maximumeigenvalueofCov(w).Disadvantage:thesemethodsfailtotakeintoaccountunmeasured(unlabeled)datapoints.68ExperimentalDesignMethodsThrManifoldRegularization:Semi-SupervisedSettingMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?69ManifoldRegularization:Semi-Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?randomlabelingManifoldRegularization:Semi-SupervisedSetting70Measured(labeled)points:disMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?randomlabelingactivelearningactivelearning+semi-supervsedlearningManifoldRegularization:Semi-SupervisedSetting71Measured(labeled)points:disUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructure72UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure73UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG74UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG75UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG76UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG77UnlabeledDatatoEstimateGeoUnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG78UnlabeledDatatoEstimateGeoLaplacianRegularizedLeastSquare(BelkinandNiyogi,2006)LinearobjectivefunctionSolution79LaplacianRegularizedLeastSqActiveLearningHowtofindthemostrepresentativepointsonthemanifold?80ActiveLearningHowtofindtheObjective:Guidetheselectionofthesubsetofdatapointsthatgivesthemostamountofinformation.Experimentaldesign:selectsamplestolabelManifoldRegularizedExperimentalDesignSharethesameobjectivefunctionasLaplacianRegularizedLeastSquares,simultaneouslyminimizetheleastsquareerroronthemeasuredsamplesandpreservethelocalgeometricalstructureofthedataspace.ActiveLearning81Objective:Guidetheselection

,Inordertomaketheestimatorasstableaspossible,thesizeofthecovariancematrixshouldbeassmallaspossible.D-optimality:minimizethedeterminantofthecovariancematrixAnalysisofBiasandVariance82

Selectthefirstdatapointsuchthatismaximized,Supposekpointshavebeenselected,choosethe(k+1)thpointsuchthat.UpdateManifoldRegularizedExperimentalDesignWhere