资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,A Geometric Perspective on Machine Learning,何晓飞,浙江大学计算机学院,1,Machine Learning: the problem,f,何晓飞,Information,(training data),f: X,Y,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.,Euclidean distance.,f,is defined on Euclidean space.,ambient dimension,geodesic distance.,f,is defined on nonlinear manifold.,manifold dimension.,instead,3,Manifold 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 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 to find the mapping function ?,How to,efficiently,find the projective function ?,9,A Good Mapping Function,If,x,i,and,x,j,are close to each other, we hope f(,x,i,) and f(,x,j,) preserve the local structure (distance, similarity ),k,-nearest neighbor graph:,Objective function:,Different algorithms have different concerns,10,Locality Preserving Projections,Principle: if,x,i,and,x,j,are close, then their maps,y,i,and,y,j,are also close.,11,Locality Preserving Projections,Principle: if,x,i,and,x,j,are close, then their maps,y,i,and,y,j,are also close.,Mathematical formulation: minimize the integral of the gradient of,f,.,12,Locality Preserving Projections,Principle: if,x,i,and,x,j,are close, then their maps,y,i,and,y,j,are also close.,Mathematical formulation: minimize the integral of the gradient of,f,.,Stokes Theorem:,13,Locality Preserving Projections,Principle: if,x,i,and,x,j,are close, then their maps,y,i,and,y,j,are 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 Digits,Thickness,Slant,16,Learning target:,Training Examples:,Linear Regression Model,Active and Semi-Supervised Learning: A Geometric Perspective,17,Generalization Error,Goal of Regression,Obtain a learned function that minimizes the,generalization error,(expected error for unseen test input points).,Maximum 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-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 structure,Unmeasured (unlabeled) points: geometrical structure,?,22,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,?,random labeling,Manifold Regularization: Semi-Supervised Setting,23,Measured (labeled) points: discriminant structure,Unmeasured (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,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,26,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph,G,27,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph,G,28,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph,G,29,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph,G,30,Unlabeled Data to Estimate Geometry,Measured (labeled) points: discriminant structure,Unmeasured (unlabeled) points: geometrical structure,Compute nearest neighbor graph,G,31,Laplacian Regularized Least Square (Belkin and Niyogi, 2006),Linear objective function,Solution,32,Active Learning,How to find the most representative points on the manifold?,33,Objective: Guide the selection of the subset of data points that gives the most amount of information.,Experimental design: select samples to label,Manifold Regularized Experimental Design,Share the,same,objective function as,Laplacian Regularized Least Squares, simultaneously minimize the least square error on the measured samples and preserve the local 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 point such that is maximized,Suppose k points have been selected, choose the,(k+1)th,point such that .,Update,Manifold,Regularized Experimental,Design,Where are selected from,The algorithm,36,Consider feature space F induced by some nonlinear mapping, and =K(,x,i,x,i,).,K(, ): positive semi-definite kernel function,Regression model in RKHS:,Objective function in RKHS:,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,Kernel Graph Regularized Experimental,Design,where are selected from,Nonlinear Generalization in RKHS,38,A Synthetic Example,A-optimal Design,Laplacian Regularized Optimal Design,39,A Synthetic Example,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 Cover,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 points,Choose suitable radius,How to identify noisy holes (user interaction?),Noisy hole,homotopy,homeomorphsim,46,Q & A,47,
展开阅读全文