Semi Supervised Learning on Riemannian Manifolds Presented by Nakul Verma May 10 2007 Outline Motivation for Semi supervised Learning and Manifold Learning Manifold Learning Algorithm Theoretical Justification Experimental Results 2 Outline Motivation for Semi supervised Learning and Manifold Learning Manifold Learning Algorithm Theoretical Justification Experimental Results 3 Supervised or Unsupervised Obtaining labeled data is expensive figures taken from 4 just with few labeled examples the decision boundary is very sensitive However if we add some unlabeled examples then 4 Semi Supervised Learning figures taken from 4 Takes advantage by learning the structure with unlabeled data and classifying the points with the labeled data 5 Manifold Learning In many applications data resides in a very low dimensional subspace of the ambient space However since most learning algorithms don t exploit the low dimensional structure suffer from computations done in high dimensions Manifold Example even though the surface resides in R3 we prefer to have learning algorithm dependent only on the intrinsic dimension 6 Semi Supervised Learning of Manifolds Left With a just a few labeled examples classification seems hard However if we add some unlabeled examples then vs Right Data seem to reside in a 1 dimensional figure 8 loop We can decide the label with more confidence We will formalize this notion and present an algorithm for doing classification in this setting 7 Outline Motivation for Semi supervised Learning and Manifold Learning Manifold Learning Algorithm Theoretical Justification Experimental Results 8 Preliminaries Assume There is an underlying manifold 4 residing in D from which all xi are generated Points are labeled according to a fixed classifier f 4 1 1 note that f needs to satisfy some properties discussed later Given k points x1 xk D assume first s k points have labels ci Goal Approximate the classifier f Using the classifier label the unlabeled points xi s i k 9 Manifold Learning Algorithm Step 1 Construct the adjacency graph with n nearest neighbors with edge weights 1 ie wij 1 if xi is close to xj 0 otherwise Step 2 Compute p eigenvectors corresponding to the smallest eigenvalues for the problem Le e Where L D W the graph Laplacian W is the adjacency matrix D is a diagonal matrix Dii j Wji The quadratic form is a measure of smoothness details later e T Le 1 2 w e e ij i j 2 ij 10 Manifold Learning Algorithm cont Step 3 Approximate the class by minimizing the error function Err a ci a e i s 2 i 1 solution given by a E E T 1 E Te Step 4 e11 e p1 where E e1s e ps Classify the unlabeled points i s by the following rule 1 if ci 1 a ei 0 o w 11 Outline Motivation for Semi supervised Learning and Manifold Learning Manifold Learning Algorithm Theoretical Justification Experimental Results 12 Basic Approach Consider Riemannian manifold 4 in D 4 has a natural operator called the Laplace Beltrami operator on differentiable functions ie a real differentiable manifold in which each tangent space is equipped with dot product is a second order differential operator defined as a divergence of the gradient 2 2 xi So why do we care 13 Laplace Beltrami Operator Reason 1 The Laplacian provides a basis on 32 4 space of all square integrable functions on 4 is a self adjoint positive semidefinate operator and its eigenfunctions form the basis Refer 3 for details As a consequence all f 32 4 can be written as f x ai ei x i 0 provided 4 is compact So if our class membership is represented by a square integrable function f 4 1 1 f can decomposed into linear combination of eigenfunctions 14 Laplace Beltrami Operator cont Reason 2 The Laplacian can be used as a smoothness functional def S f M f d f f d f f 2 M L2 M S f is called the smoothness functional such that value close to zero implies f being smooth Now since We have S ei ei ei S f f f 2 L M L2 M i provided ei is unit length 2 e e i i i i i i i i i 15 Tying it all together Consequently choosing the lowest p eigenfunctions provides a maximally smooth approximation to the manifold Mapping to lowest p eigenfunctions results in a smoother manifold Discrimination becomes easy 16 Tying it all together cont We can approximate the underlying manifold with a nearest neighborhood graph G The graph Laplacian L as defined before on G serves as a self adjoint positive semidefinate operator Thus any function on G can be decomposed as a sum of eigenfunctions of L Similarly we have a corresponding smoothness functional SG f f Lf G f T Lf 1 wij f i f j 2 2 i j 17 Outline Motivation for Semi supervised Learning and Manifold Learning Manifold Learning Algorithm Theoretical Justification Experimental Results 18 Results Though 2 provides results on many datasets we only focus on Handwritten digit recognition MNIST dataset Widely believed to lie on a five dimensional manifold though the ambient dimension is 28x28 784 Example Two dimensional PCA projection of handwritten digit 1 19 Results cont MNIST results total points 60 000 2 For fixed number of eigenvectors performance improves with number of labeled points but then saturates Algorithm achieves comparable performance to best k NN with a LOT fewer labeled points 20 Results cont Adding unlabeled data consistently improves classification accuracy 21 Summary We can greatly improve our classification rates without demanding too much labeled data This basic scheme is called Semi Supervised Learning which has received a lot of attention recently Using facts from analysis we observe that if the data lies on a manifold then we can develop an effective algorithm to classify well with only a few labeled points although not discussed these techniques can also be extended to do regularization on manifolds and graphs get sample complexity bounds perform dimensionality reduction 22 Questions Discussion 23 References 1 Belkin M Niyogi P 2003 Laplacian eigenmaps for dimensionality reduction and data representation Neural Computation 15 6 1373 1396 2 Belkin M Niyogi P 2004 Semi Supervised Learning on Riemannian Manifolds Machine Learning 56 209 239 3 Rosenberg S 1997 The Laplacian on a Riemannian Manifold Cambridge University Press 4 Zhu Xiaojin 2006 Semi Supervised Learning Literature Survey CS TR 1530 U of Wisconsin Madison 24
View Full Document
Unlocking...