1Announcements• Presentation assignments – on class web page.• MidtermHistogram:Manifold Learning• Maybe a better term would be: distance preserving low-dimensional Euclidean representations that are suitable for some manifold data.– For Riemannian manifolds• Try to preserve local distances or geodesic distances.• With low-dimensional Euclidean embedding.2Multi-dimensional Scaling• Given distances between points– In many applications (psychology) we have similarities, not points.• Produce low-dimensional point set that preserves distances. If x are the initial points, and y are the low dimensional points, we want:()−−−i jjijiyyxx2minMDS vs. PCA• PCA – linear projection of points, – can only decrease distances. – Tries to preserve points location.• MDS can extend distances also.• For low-dim points, they are equivalent– PCA preserves location and distances.PCA MDS3Distances and Inner products22222222222,2 :So)(2)()(0 :So . : thatso Normalize,2matrices. ,,,,Let products.inner pairwise knowing toequivalent is pointsbetween distances pairwise Knowingijijijjijjijijijijjijiiijijjiiijijjiji jijiijiijjjiiijTjiijjiijdndnddbndndbBntrdnbBtrdnbBtrdbbxbbbdXDBxxbxxd−−+=−==+=+====−+==−= 0Algorithm• Convert Distance matrix, D, to Inner Product matrix, B.• Factor B = QAQT, where Q is an orthonormal(rotation) matrix, and A is diagonal.– Possible since B is symmetric.– Can do this with SVD.• Use first d columns of QA1/2as d-dimensional points. These provide optimal approximation to inner products (and distances).4ISOMAP• Like MDS, but tries to preserve geodesic distances on a manifold.– Compute near-neighbors• Assume Euclidean distances are appropriate for these.– Compute geodesic distances between all pairs of points• Geodesic distance taken as shortest path among set of local distances.• Can use shortest path algorithm.– Apply MDS to these distances.LLE• Embedding that only preserves local distances and angles.• Inspired by manifold data, in which local distaces are ~ Euclidean.• Also, local distances may be more meaningful/important.• More modest goal than ISOMAP which tries to preserve all distances on manifold.5Local distances are well-preserved. Geodesic distances are not.For example, the equator is ~ the yellow stripe.LLE Algorithm• For each point– Find nearest neighbors.– Rep. pt as weighted sum of neighbors.• Approximate weights, points in low dimension.• Error in reconstructing point using weights in low dimension indicates how much distances have changed.6Local Weights1. tosum toscale then and 1Gfor solvecan weso , of magnitude with thescales 2 that Note . all of vector a is Here,2,021:get wes,multiplier Lagrange with thisWriting)()( and 1 constraintwith )(22wwwwwwwwwww===−=∂∂ −+=−•−====−=−=GGGewGxxGwGGwwxwwxjjTkjijjjjkTjkkjjjjjjjλλλλλεηηηηεLow-dimensional approximation( ) ( ) 0. of eigenvalue with 1s, allofr eigenvecto produces andon translatiremoves 0 tosum sY'assuming smallest; ignore (We s.eigenvaluesmallest with M ofrseigenvecto the tocorrespond toY choosingby done is Thiserror. theminimize to thisofon rank versi low thefind want toWer.rectangula is Xbut matrix, square a is M that Note)(0)(usually minimized iserror tion reconstruc weights,all Using2MXXXWIWIXXWXWETiTTjjiji
View Full Document
Unlocking...