Dimensionality Reduction by Learning an Invariant Mapping

1 Dimensionality Reduction by Learning an Invariant MappingRaia Hadsell, Sumit Chopra, Yann LeCunThe Courant Institute of Mathematical SciencesNew York University, 719 Broadway, New York, NY 1003, yann(November 2005. To appear in CVPR 2006)AbstractDimensionality Reduction involves Mapping a set of highdimensional input points onto a low dimensional mani-fold so that similar points in input space are mapped tonearby points on the manifold. Most existing techniques forsolving the problem suffer from two drawbacks. First, mostof them depend on a meaningful and computable distancemetric in input space. Second, they do not compute a func-tion that can accurately map new input samples whose re-lationship to the training data is unknown.

2 We present amethod - called Dimensionality Reduction by Learning anInvariant Mapping (DrLIM) - for Learning a globally co-herent non-linear function that maps the data evenly to theoutput manifold. The Learning relies solely on neighbor-hood relationships and does not require any distance mea-sure in the input space. The method can learn mappings thatare Invariant to certain transformations of the inputs, as isdemonstrated with a number of experiments. Comparisonsare made to other techniques, in particular IntroductionModern applications have steadily expanded their use ofcomplex, high dimensional data. The massive, high dimen-sional image datasets generated by biology, earth science,astronomy, robotics, modern manufacturing, and other do-mains of science and industry demand new techniques foranalysis, feature extraction, Dimensionality Reduction , Reduction aims to translate high dimen-sional data to a low dimensional representation such thatsimilar input objects are mapped to nearby points on a man-ifold.

3 Most existing Dimensionality Reduction techniqueshave two shortcomings. First, they do not produce afunc-tion(or a Mapping ) from input to manifold that can be ap-plied to new points whose relationship to the training pointsis unknown. Second, many methods presuppose the exis-tence of a meaningful (and computable) distance metric inthe input example, Locally Linear Embedding (LLE) [15] lin-early combines input vectors that are identified as neigh-bors. The applicability of LLE and similar methods to im-age data is limited because linearly combining images onlymakes sense for images that are perfectly registered andvery similar.

4 Laplacian Eigenmap [2] and Hessian LLE [8]do not require a meaningful metric in input space (theymerely require a list of neighbors for every sample), butas with LLE, new points whose relationships with trainingsamples are unknown cannot be processed. Out-of-sampleextensions to several Dimensionality Reduction techniqueshave been proposed that allow for consistent embedding ofnew data samples without recomputation of all samples [3].These extensions, however, assume the existence of a com-putable kernel function that is used to generate the neigh-borhood matrix. This dependence is reducible to the depen-dence on a computable distance metric in input limitation of current methods is that they tend tocluster points in output space, sometimes densely enough tobe considered degenerate solutions.

5 Rather, it is sometimesdesirable to find manifolds that are uniformly covered method proposed in the present paper, called Di-mensionality Reduction by Learning an Invariant Mapping (DrLIM), provides a solution to the above problems. Dr-LIM is a method for Learning a globally coherent non-linearfunction that maps the data to a low dimensional method presents four essential characteristics: It only needs neighborhood relationships betweentraining samples. These relationships could come fromprior knowledge, or manual labeling, and be indepen-dent of any distance metric. It may learn functions that are Invariant to complicatednon-linear trnasformations of the inputs such as light-ing changes and geometric distortions.

6 The learned function can be used to map new samplesnot seen during training, with no prior The Mapping generated by the function is in somesense smooth and coherent in the output contrastive loss function is employed to learn the param-etersWof a parameterized functionGW, in such a way thatneighbors are pulled together and non-neighbors are pushedapart. Prior knowledge can be used to identify the neighborsfor each training data method uses an energy based model that uses thegiven neighborhood relationships to learn the mappingfunction. For a family of functionsG, parameterized byW,the objective is to find a value ofWthat maps a set of highdimensional inputs to the manifold such that the euclideandistance between points on the manifold,DW(~X1,~X2) =||GW(~X1) GW(~X2)||2approximates the semantic sim-ilarity of the inputs in input space, as provided by a set ofneighborhood relationships.

7 No assumption is made aboutthe functionGWexcept that it is differentiable with Previous WorkThe problem of Mapping a set of high dimensional pointsonto a low dimensional manifold has a long history. Thetwo classical methods for the problem are Principal Com-ponent Analysis (PCA) [7] and Multi-Dimensional Scal-ing (MDS) [6]. PCA involves the projection of inputs to alow dimensional subspace that maximizes the variance. InMDS, one computes the projection that best preserves thepairwise distances between input points. However both themethods - PCA in general and MDS in the classical scalingcase (when the distances are euclidean distances) - generatea linear recent years there has been a lot of activity in design-ing non-linearspectral methodsfor the problem.

8 Thesemethods involve solving the eigenvalue problem for aparticular matrix. Recently proposed algorithms includeISOMAP (2000) by Tenenbaumet al. [1], Local Linear Em-bedding - LLE (2000) by Roweis and Saul [15], LaplacianEigenmaps (2003) due to Belkin and Niyogi [2] and Hes-sian LLE (2003) by Donoho and Grimes [8]. All the abovemethods have three main steps. The first is to identify a listof neighbors of each point. Second, a gram matrix is com-puted using this information. Third, the eigenvalue prob-lem is solved for this matrix. The methods differ in how thegram matrix is computed. None of these methods attemptto compute afunctionthat could map a new, unknown datapoint without recomputing the entire embedding and with-out knowing its relationships to the training points.

9 Out-of-sample extensions to the above methods have been pro-posed by Bengioet al. in [3], but they too rely on a prede-termined computable distance a somewhat different line Sch oelkopfet al. in1998 [13] proposed a non-linear extension of PCA, calledKernel PCA. The idea is to non-linearly map the inputs toa high dimensional feature space and then extract the prin-cipal components. The algorithm first expresses the PCAcomputation solely in terms of dot products and then ex-ploits the kernel trick to implicitly compute the high dimen-sional Mapping . The choice of kernels is crucial: differ-ent kernels yield dramatically different embeddings.

10 In re-cent work, Weinbergeret al. in [11,12] attempt to learnthe kernel matrix when the high dimensional input lies on alow dimensional manifold by formulating the problem as asemidefinite program. There are also related algorithms forclustering due to Shi and Malik [14] and Nget al. [17].The proposed approach is different from these methods;it learns a function that is capable of consistently mappingnew points unseen during training. In addition, this functionis not constrained by simple distance measures in the inputspace. The Learning architecture is somewhat similar to theone discussed in [4,5].Section2describes the general framework, the loss func-tion, and draws an analogy with a mechanical spring sys-tem.