机器学习的几何观点

AGeometricPerspectiveonMachineLearning何晓飞浙江大学计算机学院1MachineLearning:theproblemf何晓飞Information(trainingdata)f:X→YXandYareusuallyconsideredasaEuclideanspaces.2ManifoldLearning:geometricperspectiveThedataspacemaynotbeaEuclideanspace,butanonlinearmanifold.☒Euclideandistance.☒fisdefinedonEuclideanspace.☒ambientdimension☑geodesicdistance.☑fisdefinedonnonlinearmanifold.☑manifolddimension.instead…3ManifoldLearning:thechallengesThemanifoldisunknown!Wehaveonlysamples!HowdoweknowMisasphereoratorus,orelse?HowtocomputethedistanceonM?versusThisisunknown:Thisiswhatwehave:??orelse…?TopologyGeometryFunctionalanalysis4ManifoldLearning:currentsolutionFindaEuclideanembedding,andthenperformtraditionallearningalgorithmsintheEuclideanspace.5Simplicity6Simplicity7Simplicityisrelative8Manifold-basedDimensionalityReductionGivenhighdimensionaldatasampledfromalowdimensionalmanifold,howtocomputeafaithfulembedding?Howtofindthemappingfunction?Howtoefficientlyfindtheprojectivefunction?fff9AGoodMappingFunctionIfxiandxjareclosetoeachother,wehopef(xi)andf(xj)preservethelocalstructure(distance,similarity…)k-nearestneighborgraph:Objectivefunction:Differentalgorithmshavedifferentconcerns10LocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.11LocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.12LocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.Stokes’Theorem:13LocalityPreservingProjectionsPrinciple:ifxiandxjareclose,thentheirmapsyiandyjarealsoclose.Mathematicalformulation:minimizetheintegralofthegradientoff.Stokes’Theorem:LPPfindsalinearapproximationtononlinearmanifold,whilepreservingthelocalgeometricstructure.14ManifoldofFaceImagesExpression(SadHappy)Pose(RightLeft)15ManifoldofHandwrittenDigitsThicknessSlant16Learningtarget:TrainingExamples:LinearRegressionModelActiveandSemi-SupervisedLearning:AGeometricPerspective17GeneralizationErrorGoalofRegressionObtainalearnedfunctionthatminimizesthegeneralizationerror(expectederrorforunseentestinputpoints).MaximumLikelihoodEstimate18Gauss-MarkovTheoremForagivenx,theexpectedpredictionerroris:19-4-3-2-10123400.10.20.30.40.50.60.70.8-4-3-2-10123400.10.20.30.40.50.60.70.8Gauss-MarkovTheoremForagivenx,theexpectedpredictionerroris:Good!Bad!20ExperimentalDesignMethodsThreemostcommonscalarmeasuresofthesizeoftheparameter(w)covariancematrix:A-optimalDesign:determinantofCov(w).D-optimalDesign:traceofCov(w).E-optimalDesign:maximumeigenvalueofCov(w).Disadvantage:thesemethodsfailtotakeintoaccountunmeasured(unlabeled)datapoints.21ManifoldRegularization:Semi-SupervisedSettingMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?22Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?randomlabelingManifoldRegularization:Semi-SupervisedSetting23Measured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure?randomlabelingactivelearningactivelearning+semi-supervsedlearningManifoldRegularization:Semi-SupervisedSetting24UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructure25UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructure26UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG27UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG28UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG29UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG30UnlabeledDatatoEstimateGeometryMeasured(labeled)points:discriminantstructureUnmeasured(unlabeled)points:geometricalstructureComputenearestneighborgraphG31LaplacianRegularizedLeastSquare(BelkinandNiyogi,2006)LinearobjectivefunctionSolution32ActiveLearningHowtofindthemostrepresentativepointsonthemanifold?33Objective:Guidetheselectionofthesubsetofdatapointsthatgivesthemostamountofinformation.Experimentaldesign:selectsamplestolabelManifoldRegularizedExperimentalDesignSharethesameobjectivefunctionasLaplacianRegularizedLeastSquares,simultaneouslyminimizetheleastsquareerroronthemeasuredsamplesandpreservethelocalgeometricalstructureofthedataspace.ActiveLearning34,Inordertomaketheestimatorasstableaspossible,thesizeofthecovariancematrixshouldbeassmallaspossible.D-optimality:minimizethedeterminantofthecovariancematrix2()CovIy12TXLXI12TTHZZXLXIˆwˆ()Covw112ˆ()TTZZXLXIZwyAnalysisofBiasa