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. 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.

2 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. 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.

3 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. 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.

4 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. 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.

5 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. 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.

6 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. 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.

7 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. 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].

8 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. The ideas in this section are made concrete in sec-tion3. Here various experimental results are given and com-parisons to LLE are Learning the Low Dimensional MappingThe problem is to find a function that maps high dimen-sional input patterns to lower dimensional outputs, givenneighborhood relationships between samples in input graph of neighborhood relationships may come frominformation source that may not be available for test points,such as prior knowledge, manual labeling, etc. More pre-cisely, given a set of input vectorsI={~X1.}

9 ,~XP},where~Xi D, i= 1, .. , n, find a parametric func-tionGW: D dwithd D, such that it has thefollowing properties:1. Simple distance measures in the output space (such aseuclidean distance) should approximate theneighbor-hood relationshipsin the input The Mapping should not be constrained to implement-ing simple distance measures in the input space andshould be able to learn invariances to complex It should befaithfuleven for samples whose neighbor-hood relationships are The contrastive Loss FunctionConsider the setIof high dimensional training vectors~Xi. Assume that for each~Xi Ithere is a setS~Xiof train-ing vectors that are deemed similar to~Xi. This set can becomputed by some prior knowledge - invariance to distor-tions or temporal proximity, for instance - which does notdepend on a simple distance. A meaningful Mapping fromhigh to low dimensional space maps similar input vectors tonearby points on the output manifold and dissimilar vectorsto distant points.

10 A new loss function whose minimizationcan produce such a function is now introduced. Unlike con-ventional Learning systems where the loss function is a sumover samples, the loss function here runs overpairs of sam-ples. Let~X1,~X2 Ibe a pair of input vectors shown to thesystem. LetYbe a binary label assigned to this 0if~X1and~X2are deemd similar, andY= 1if they aredeemed dissimilar. Define the parameterized distance func-tion to be learnedDWbetween~X1,~X2as the euclideandistance between the outputs ofGW. That is,DW(~X1,~X2) =kGW(~X1) GW(~X2)k2(1)To shorten notation,DW(~X1,~X2)is writtenDW. Then theloss function in its most general form isL(W) =P i=1L(W,(Y,~X1,~X2)i)(2)L(W,(Y,~X1,~X2)i) = (1 Y)LS(DiW)+Y LD(DiW)(3)where(Y,~X1,~X2)iis thei-th labeled sample pair,LSisthe partial loss function for a pair of similar points,LDthepartial loss function for a pair of dissimilar points, andPthe number of training pairs (which may be as large as thesquare of the number of samples).