机器学习的几何观点-LAMDA课件

AGeometricPerspectiveonMachineLearning何晓飞浙江大学计算机学院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-optimalDesignLaplacianRegularizedOptima