机器学习的几何观点-LAMDA.ppt

1、A Geometric Perspective on Machine Learning,何晓飞浙江大学计算机学院,1,Machine Learning: the problem,f,何晓飞,Information(training data),f: XY,X and Y are usually considered as a Euclidean spaces.,2,Manifold Learning: geometric perspective,The data space may not be a Euclidean space, but a nonlinear manifold.,3,Ma

2、nifold Learning: the challenges,The manifold is unknown! We have only samples!How do we know M is a sphere or a torus, or else?How to compute the distance on M? versus,This is unknown:,This is what we have:,?,?,or else?,Topology,Geometry,Functional analysis,4,Manifold Learning: current solution,Find

3、 a Euclidean embedding, and then perform traditional learning algorithms in the Euclidean space.,5,Simplicity,6,Simplicity,7,Simplicity is relative,8,Manifold-based Dimensionality Reduction,Given high dimensional data sampled from a low dimensional manifold, how to compute a faithful embedding? How

4、to find the mapping function ?How to efficiently find the projective function ?,9,A Good Mapping Function,If xi and xj are close to each other, we hope f(xi) and f(xj) preserve the local structure (distance, similarity )k-nearest neighbor graph:Objective function:Different algorithms have different

5、concerns,10,Locality Preserving Projections,Principle: if xi and xj are close, then their maps yi and yj are also close.,11,Locality Preserving Projections,Principle: if xi and xj are close, then their maps yi and yj are also close.,Mathematical formulation: minimize the integral of the gradient of

6、f.,12,Locality Preserving Projections,Principle: if xi and xj are close, then their maps yi and yj are also close.,Mathematical formulation: minimize the integral of the gradient of f.,Stokes Theorem:,13,Locality Preserving Projections,Principle: if xi and xj are close, then their maps yi and yj are

7、 also close.,Mathematical formulation: minimize the integral of the gradient of f.,Stokes Theorem:,LPP finds a linear approximation to nonlinear manifold, while preserving the local geometric structure.,14,Manifold of Face Images,Expression (Sad Happy),Pose (Right Left),15,Manifold of Handwritten Di

8、gits,Thickness,Slant,16,Learning target:Training Examples:Linear Regression Model,Active and Semi-Supervised Learning: A Geometric Perspective,17,Generalization Error,Goal of RegressionObtain a learned function that minimizes the generalization error (expected error for unseen test input points).Max

9、imum Likelihood Estimate,18,Gauss-Markov Theorem,For a given x, the expected prediction error is:,19,Gauss-Markov Theorem,For a given x, the expected prediction error is:,Good!,Bad!,20,Experimental Design Methods,Three most common scalar measures of the size of the parameter (w) covariance matrix:A-

10、optimal Design: determinant of Cov(w).D-optimal Design: trace of Cov(w).E-optimal Design: maximum eigenvalue of Cov(w).Disadvantage: these methods fail to take into account unmeasured (unlabeled) data points.,21,Manifold Regularization: Semi-Supervised Setting,Measured (labeled) points: discriminant

11、 structureUnmeasured (unlabeled) points: geometrical structure,?,22,Measured (labeled) points: discriminant structureUnmeasured (unlabeled) points: geometrical structure,?,random labeling,Manifold Regularization: Semi-Supervised Setting,23,Measured (labeled) points: discriminant structureUnmeasured

12、(unlabeled) points: geometrical structure,?,random labeling,active learning,active learning + semi-supervsed learning,Manifold Regularization: Semi-Supervised Setting,24,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structure,25,Unlabeled Data to Estimate Geometry,Measu

13、red (labeled) points: discriminant structureUnmeasured (unlabeled) points: geometrical structure,26,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structureUnmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph G,27,Unlabeled Data to Estimate

14、 Geometry,Measured (labeled) points: discriminant structureUnmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph G,28,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structureUnmeasured (unlabeled) points: geometrical structure,Compute neares

15、t neighbor graph G,29,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structureUnmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph G,30,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structureUnmeasured (unlabel

16、ed) points: geometrical structure,Compute nearest neighbor graph G,31,Laplacian Regularized Least Square (Belkin and Niyogi, 2006),Linear objective functionSolution,32,Active Learning,How to find the most representative points on the manifold?,33,Objective: Guide the selection of the subset of data

17、points that gives the most amount of information.Experimental design: select samples to labelManifold Regularized Experimental DesignShare the same objective function as Laplacian Regularized Least Squares, simultaneously minimize the least square error on the measured samples and preserve the local

18、 geometrical structure of the data space.,Active Learning,34, In order to make the estimator as stable as possible, the size of the covariance matrix should be as small as possible.D-optimality: minimize the determinant of the covariance matrix,Analysis of Bias and Variance,35,Select the first data

19、point such that is maximized,Suppose k points have been selected, choose the (k+1)th point such that .Update,The algorithm,36,Consider feature space F induced by some nonlinear mapping , and =K(xi, xi).K(, ): positive semi-definite kernel functionRegression model in RKHS: Objective function in RKHS:

20、,Nonlinear Generalization in RKHS,37,Select the first data point such that is maximized,Suppose k points have been selected, choose the (k+1)th point such that .Update,Nonlinear Generalization in RKHS,38,A Synthetic Example,A-optimal Design,Laplacian Regularized Optimal Design,39,A Synthetic Example

21、,A-optimal Design,Laplacian Regularized Optimal Design,40,Application to image/video compression,41,Video compression,42,Topology,Can we always map a manifold to a Euclidean space without changing its topology?,？,43,Topology,Simplicial Complex,Homology Group,Betti Numbers,Euler Characteristic,Good C

22、over,Sample Points,Homotopy,Number of components, dimension,44,Topology,The Euler Characteristic is a topological invariant, a number that describes one aspect of a topological spaces shape or structure.,1,-2,0,1,2,The Euler Characteristic of Euclidean space is 1!,0,0,45,Challenges,Insufficient sample pointsChoose suitable radiusHow to identify noisy holes (user interaction?),Noisy hole,homotopy,homeomorphsim,46,Q & A,47,