《机器学习的几何观点.ppt》由会员分享，可在线阅读，更多相关《机器学习的几何观点.ppt（48页珍藏版）》请在三一办公上搜索。
1、A Geometric Perspective on Machine Learning,何晓飞浙江大学计算机学院,Machine Learning:the problem,f,何晓飞,Information(training data),f:XY,X and Y are usually considered as a Euclidean spaces.,Manifold Learning:geometric perspective,The data space may not be a Euclidean space,but a nonlinear manifold.,Manifold Lea
2、rning: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,Manifold Learning:current solution,Find a Euclidean embe
3、dding,and then perform traditional learning algorithms in the Euclidean space.,Simplicity,Simplicity,Simplicity is relative,Manifold-based Dimensionality Reduction,Given high dimensional data sampled from a low dimensional manifold,how to compute a faithful embedding?How to find the mapping function
4、?How to efficiently find the projective function?,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 concerns,Locality Preserving Projectio
5、ns,Principle:if xi and xj are close,then their maps yi and yj are also close.,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.,Locality Preserving Projections,Principle:if x
6、i 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:,Locality Preserving Projections,Principle:if xi and xj are close,then their maps yi and yj are also close.,Mathematical formulation:minimize the integral
7、of the gradient of f.,Stokes Theorem:,LPP finds a linear approximation to nonlinear manifold,while preserving the local geometric structure.,Manifold of Face Images,Expression(Sad Happy),Pose(Right Left),Manifold of Handwritten Digits,Thickness,Slant,Learning target:Training Examples:Linear Regressi
8、on Model,Active and Semi-Supervised Learning:A Geometric Perspective,Generalization Error,Goal of RegressionObtain a learned function that minimizes the generalization error(expected error for unseen test input points).Maximum Likelihood Estimate,Gauss-Markov Theorem,For a given x,the expected predi
9、ction error is:,Gauss-Markov Theorem,For a given x,the expected prediction error is:,Good!,Bad!,Experimental Design Methods,Three most common scalar measures of the size of the parameter(w)covariance matrix:A-optimal Design:determinant of Cov(w).D-optimal Design:trace of Cov(w).E-optimal Design:maxi
10、mum eigenvalue of Cov(w).Disadvantage:these methods fail to take into account unmeasured(unlabeled)data points.,Manifold Regularization:Semi-Supervised Setting,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,?,Measured(labeled)points:discriminant struc
11、tureUnmeasured(unlabeled)points:geometrical structure,?,random labeling,Manifold Regularization:Semi-Supervised Setting,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,?,random labeling,active learning,active learning+semi-supervsed learning,Manifold R
12、egularization:Semi-Supervised Setting,Unlabeled Data to Estimate Geometry,Measured(labeled)points:discriminant structure,Unlabeled Data to Estimate Geometry,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,Unlabeled Data to Estimate Geometry,Measured(la
13、beled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,Compute nearest neighbor graph G,Unlabeled Data to Estimate Geometry,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,Compute nearest neighbor graph G,Unlabeled Data to
14、 Estimate Geometry,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,Compute nearest neighbor graph G,Unlabeled Data to Estimate Geometry,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,Compute nearest neig
15、hbor graph G,Unlabeled Data to Estimate Geometry,Measured(labeled)points:discriminant structureUnmeasured(unlabeled)points:geometrical structure,Compute nearest neighbor graph G,Laplacian Regularized Least Square,Linear objective functionSolution,Active Learning,How to find the most representative p
16、oints on the manifold?,Objective:Guide the selection of the subset of data 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 minim
17、ize the least square error on the measured samples and preserve the local geometrical structure of the data space.,Active Learning,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 covari
18、ance matrix,Analysis of Bias and Variance,Select the first data point such that is maximized,Suppose k points have been selected,choose the(k+1)th point such that.Update,The algorithm,Consider feature space F induced by some nonlinear mapping,and=K(xi,xi).K(,):positive semi-definite kernel functionR
19、egression model in RKHS:Objective function in RKHS:,Nonlinear Generalization in RKHS,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,A Synthetic Example,A-optimal Design,Laplacian Regular
20、ized Optimal Design,A Synthetic Example,A-optimal Design,Laplacian Regularized Optimal Design,Combining active and semi-supervised learning for CBIR,First iteration,Second iteration,Application to image/video compression,Video compression,Topology,Can we always map a manifold to a Euclidean space wi
21、thout changing its topology?,？,Topology,Simplicial Complex,Homology Group,Betti Numbers,Euler Characteristic,Good Cover,Sample Points,Homotopy,Number of components,dimension,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,Challenges,Insufficient sample pointsChoose suitable radiusHow to identify noisy holes(user interaction?)Compute topology invariants from sparse sample points,Noisy hole,homotopy,homeomorphsim,Q&A,
