Improving Embeddings by Flexible Exploitation of Side Information

1 Introduction

Many machine learning approaches use distances between data points as a discriminating factor. In some cases, the plain Euclidean distance between points is meaningful and such methods can work well. Such distances are the starting onality-reduction techniques,

such as MDS [Cox and Cox, 2001], LLE [Roweis and Saul, 2000], Isomap [Tenenbaum et al., 2000], LEM [Belkin and Niyogi, 2003], and SDE [Weinberger and Saul, 2004]. Often, however, this distance does not capture the distinction one is trying to characterize. Approaches such as kernelized methods address this issue by mapping the points into new spaces where Euclidean distances may be more useful. An alternative approach is to construct a new distance metric over the points and use it in place of Euclidean distances, as explored by Xing et al. [Xing et al., 2003]. In this approach, some amount of side information is employed to learn a distance metric that captures the desired distinction.

In some situations it may be possible to obtain a small amount of information regarding the similarity of some points in a particular data set. Consider a large collection of images.

Finnegan Southey

Google Inc.

While it would be expensive to have a human examine and label the entire set, it might be feasible to have a human examine a small subset and provide information on how pairs of images relate to each other. Similarly, some expensive experiment might yield useful similarity information for a subset of the data. This paper will show how two kinds of such side information can be used in a preprocessing step for embedding techniques, leading to embeddings that capture the target properties. The method improves over earlier work in this area by using standard "off-the-shelf" optimization methods and by allowing more flexibility in the side information used.

The first kind of side information identifies pairs of points that belong to the same class or pairs that belong to different classes. Note that this information is about the classequivalence/inequivalence of points but does not give the actual class labels. Consider four points, x1, x2, x3, and x4. Given side information that x1 and x2 are in the same class, and that x3 and x4 also share a class, we cannot be certain whether the four points fall into one or two classes.

The second kind of side information takes the form of partial information about the similarity of points in the form of distances. For some pairs of points, one may have distances corresponding to an informative metric space, obtained by some expensive measurement. Molecular conformation problems are a good example. Some of the distances between pairs of atoms in a given molecule can be determined by nuclear magnetic resonance spectroscopy, but the procedure is costly and certainly not guaranteed to provide all such distances. Determining the rest of the distances can help in classifying the conformation of the molecule (see [Crippen and Havel, 1988] for more details).

These two kinds of side information can be used to learn a new distance metric. The distances between points in this new space can then be used with any embedding technique. We start by showing how class-equivalence side information can be used to learn such a metric and show the effect of using this new metric with a variety of embedding techniques. We then show how multiple applications of this method can be used to combine several learned distance metrics together into one in order to capture multiple attributes in the embedding. We also discuss how the class-equivalence approach can be kernelized, allowing for nonlinear transformations of the metric. Finally, we formulate a method for using the second type of side information, where we have partial information about desirable target distances between some pairs of points. Experimental results demonstrate the value of this preprocessing step.

1.1 RelatedWork

Our use of class equivalence relations to learn a metric follows [Xing et al., 2003]. In that work, a new distance metric is learned by considering side information. Xing et al. used side information identifying pairs of points as "similar". They then construct a metric that minimizes the distance between all such pairs of points. At the same time, they attempt to ensure that all "dissimilar" points are separated by some minimal distance. By default, they consider all points not explicitly identified as similar to be dissimilar. They present algorithms for optimizing this objective and show results using the learned distance for clustering, an application in which an appropriate distance metric is crucial. Other work on learning distance metrics has been primarily focused on classification, with side information in the form of class labels [Globerson and Roweis, 2006; Weinberger et al., 2006; Goldberger et al., 2005].

2 Learning a Metric fromClass-Equivalence Side Information

We will start with the simpler similar/dissimilar pair case, formalizing this notion of side information and stating an objective that will be optimized using standard semidefinite programming software. The use of this kind of side information allows one to select a characteristic for distinction. For example, one may have several images of faces. One sensible cluster is by presence or absence of a beard. Another is by the presence or absence of glasses. Different indications of similarity allow the capturing of either distinction. The following takes the same basic approach as [Xing et al., 2003] but offers a simpler optimization procedure using "off-the-shelf" optimization methods instead of their iterative method.

2.1 Derivation

Given a set of t points, {xi}ti=1 ⊆ Rn, we identify two kinds of class-related side information. First, a set class-equivalent (or similar) pairs of points

and, second, a set of class-inequivalent (dissimilar) pairs

We then wish to learn a matrix A that induces a distance metric D(A) over the points

where A ⪰ 0.

We define the following loss function, which, when minimized, attempts to minimize the squared induced distance between similar points and maximize the squared induced distance between dissimilar points

The optimization problem then becomes

The first constraint (positive semidefiniteness) ensures a Euclidean metric. The second excludes the trivial solution where all distances are zero. The constant in this constraint is arbitrary, affecting only the scale of the space. This objective will be optimized using standard semidefinite programming software and so it must be converted to a linear objective. Expanding the loss function

each squared distance term must be converted. We start by observing that vec(XYZ) = (Z T ⊗ X)vec(Y ), where vec() simply rearranges a matrix into a vector by concatenating columns and ⊗ is the Kronecker product. Note that (xi - xj)T A(xi - xj) = vec((xi - xj)T A(xi - xj)) because the left-hand side is a scalar. Using this and the fact that (aT ⊗ bT ) = vec(baT )T , we can rewrite the squared

The linear loss function is then

This form, along with the two constraints from (1), can be readily submitted to an SDP solver to optimize the matrix A1 . Aside from this convenient form, this formulation has other advantages over that used by Xing et al., especially with respect to the side information we can convey.

Xing et al. require at least one dissimilar pair in order to avoid the trivial solution where all distances are zero. The constraint on the trace that we employ means that we need not place any restrictions on pairings. Side information can consist of similar pairs only, dissimilar pairs only, or any combination of the two; the method still avoids trivial solutions.

1 We use the MATLAB SDP solver SeDuMi [Sturm, 1999]

Furthermore, in the absence of specific information regarding dissimilarities, Xing et al. assume that all points not explicitly identified as similar are dissimilar. This information may be misleading, forcing the algorithm to separate points that may, in fact, be similar. The formulation presented here allows one to specify only the side information one actually has, partitioning the pairings into similar, dissimilar, and unknown.

2.2 Results

Once a metric has been learned, the new distances can be used with any embedding technique. To demonstrate the benefits of this approach, we generated embeddings with and without the preprocessing step, informing the preprocessed embeddings about some characteristic of interest, and then examined the result. To show that the side information truly informs the embedding, two sets of informed embeddings were generated from the same data set, each with side information pertaining to two different characteristics. Structure in the resulting embeddings that captures the two different characteristics within a single data set is evidence that the method works as intended.

Embeddings were generated using a variety of techniques including MDS, Isomap, LEM, LLE, and SDE. The data set consisted of 200 images of faces and two distinctions are identified by side information: faces with beards vs. faces without beards and faces with glasses vs. faces without glasses. In one set of experiments (which we will call all-similar), all similar pairs were identified but no dissimilar pairs. The second set (which we will call five-pairs), simulating a situation where labelling is expensive, identifies only four similar pairs and one dissimilar pair. The pairs were selected at random. Techniques using the preprocessor are labelled as "Equivalence-Informed" (e.g., EquivalenceInformedMDS). In each case, a two-dimensional embedding is shown. The two classes are marked with X and O, respectively. Additionally, a subset of the images are displayed on the plot (plots with all images are unreadable). Some plots have been omitted due to space constraints.

Inspection reveals that, in general, the informed versions of these embeddings manage to separate the data based on the target property, whereas the uninformed versions are typically chaotic. Even when separation is poor in the informed embedding, there is usually much more structure than in the uninformed embedding. Equivalence-Informed MDS (Figures 1 and 2, five-pairs beards and all-pairs glasses omitted) offers mixed results, especially with five-pairs for glasses vs. no glasses (Figure 2), but MDS is a comparatively crude embedding technique in any case. Isomap with all-pairs works very well (Figure 3, glasses omitted) and with five-pairs it still manages to group the two classes but does not separate them well (Figure 4, glasses omitted). LEM separates well with all-pairs (Figure 5, glasses omitted) but shows weak separation in the five-pairs case (Figure 6, glasses omitted). The same effective grouping and varying separation occurs for LLE (figures omitted). Finally, SDE groups well, but is weak in separation in all cases (Figures 7 and 8, glasses omitted).

These results show that the side information can be effectively exploited to capture characteristics of interest where uninformed embedding techniques fail to automatically discover them. Moreover, two different characteristics (beards and glasses) have been captured within the same data set, even when using only small quantities of class-equivalence side information. Finally, the preprocessor is effective with a wide range of embedding techniques.

1st dimension

1st dimension

Figure 3: Isomap and Equivalence-Informed Isomap with (un)bearded distinction (all equivalent pairs)

Finally, Figures 9 and 10 are provided to give a numerical notion of the improvement offered by informed embeddings. The plots show the misclassification rate of k-means clustering in recovering the true classes of the images, after applying each of the uninformed and informed embeddings (indicated by, e.g., "MDS" and "Inf. MDS"). The informed methods achieve a lower error rate than their uninformed counterparts by better separating the data (except 4-pairs SDE).

1st dimension

1st dimension

Figure 5: LEM and Equivalence-Informed LEM with (un)bearded distinction (all equivalent pairs)

3 Multiple-Attribute Metric Learning with Class-Equivalence Side Information

In some cases, there may be more than one distinction to capture in data (e.g., glasses vs. no glasses and beards vs. no beards). The method above can be extended to construct a distance metric using multiple sets of side information, each corresponding to a different criterion. Multiple metrics are learned and then combined to form a single metric.

Suppose there are k different sets of side information over the same set of points. Using the optimization described above, k transformations, A1, · · · ,Ak can be learned. From each Ai, the dominant eigenvector vi can be taken and a new matrix assembled where each column is one of these eigenvectors, ¯ A = [ v1 · · · vk ]. This combined matrix de-

1st dimension

1st dimension

Figure 8: SDE and Equivalence-Informed SDE with (un)bearded distinction (4 equivalent/1 inequivalent pairs)

fines a rank k linear subspace onto which we can project the data. Applying singular value decomposition to ¯ A, one can form a matrix U from the k eigenvectors corresponding to the largest eigenvalues. The final transformation is then ˆ A = UU T , which is an orthonormal basis combining the distinctions drawn by each kind of side information.

3.1 Results

We demonstrate the effectiveness of this method by creating a single embedding that captures two distinctions. We repeat the earlier experiments but using both the (un)bearded and glasses/no glasses criteria together. Results were generated for all the embedding methods and their multipleattribute, equivalence-informed versions but some are omitted for space. In all cases, the side information consisted of all similar pairs and no dissimilar pairs.

The informed embeddings tend to discover the four distinct categories of faces (combinations of the presence and absence of beards and glasses). Informed MDS (Figure 11) separates these quite well, as do Informed Isomap (Figure 12) and Informed LLE (Figure 13). Results with Informed LEM (figure omitted) are roughly grouped. Finally, Informed SDE (Figure 14) does has trouble separating two categories, but a lot of useful structure is present. In all cases, the informed embeddings have distinct structure that the uninformed embeddings fail to capture. The only feature the uninformed embeddings seem to capture is the relative darkness of the images.

These results show that the multiple-attribute approach can capture the desired properties in a single embedding, while the uninformed versions fail to capture either of the properties of interest. Again, the method is straightforward to apply and works with a variety of embedding techniques.

4 KernelizingMetric Learning

Not uncommonly, nonlinear transformations of the data are required to successfully apply learning algorithms. One efficient method for doing this is via a kernel that computes a

1st dimension

1st dimension

Figure 14: SDE and Multi-Attribute Informed SDE with (un)bearded and (no)glasses attributes (all equivalent pairs)

similarity measure between any two data points. In this section, we show how to learn a metric in the feature space implied by a kernel, allowing our use of side information to be extended to nonlinear mappings of the data.

Conceptually, the points are mapped into a feature space by some nonlinear mapping Φ() and a metric is learned in that space. Actually applying the mapping is often undesirable (e.g., the feature vectors may have infinite dimension), so we employ the well known kernel trick, using some kernel K(xi, xj) that computes inner products between feature vectors without explicitly constructing them.

The squared distances in our objective have the form (xi - xj)T A(xi - xj). Because A is positive semidefinite, it can be decomposed into A = WW T . W can then be expressed as a linear combination of the data points, W = Xβ, via the kernel trick. Rewriting the squared distance

where A = ββT , we have now expressed the distance in terms of the matrix to be learned, A, and inner products between data points, which can be computed via the kernel, K. The optimization of A proceeds as in the non-kernelized version but with one additional constraint. The rank of A must be t because β is t by n and A=ββT . However, this constraint is problematic, so we drop it during the optimization and then find a rank t approximation of A via singular value decomposition.

5 Using Partial Distance Side Information

We will now discuss the use of the second kind of side information mentioned at the beginning of this paper. Recall that in this case, we have side information that gives exact distances between some pairs of points in some space natural to the data. Such partial distance information can be used to inform our learned metric. Given a set of similarities in the form of pairs for which distances are known

the following cost function is employed, which attempts to preserve the set of known distances

The optimization problem is then

A convenient form for this optimization is obtained using the same approach for quadratic terms used earlier

where Bij = (xi - xj)(xi - xj)T . Note that the d2ij term in the above is a constant so it can be dropped for the purposes of minimization, and the loss rewritten as

where Q = ∑(xi,xj)∈S vec(Bij)vec(Bij)T and R = ∑(xi,xj)∈S dijvec(Bij). This objective is still quadratic but a linear objective can be obtained via the Schur complement [Boyd and Vandenberghe, 2004], as we outline here.

The Schur complement relates the positive semidefiniteness of the matrix on the left and the expression on the right by an if-and-only-if relation

By decomposing Q = S T S, a matrix of the form

can be constructed. By the Schur complement, if J ⪰ 0, then the following relation holds

Note that this quantity is scalar. As long as J is positive semidefinite, the scalar t is an upper bound on the loss

Therefore, minimizing t subject to J ⪰ 0 also minimizes the objective. This optimization problem can be readily solved by standard semidefinite programming software

5.1 Results

Again, we demonstrate effectiveness by generating uninformed and informed embeddings but with target distances specified for some pairs of points. The distances used here are a portion of the distance DA computed in Section 2.2. That is, there are 200 images of faces and two distinctions are identified by class-equivalence side information: faces with beards vs. faces without beards and faces with glasses vs. faces without glasses. For each distinction, the distance matrix DA is computed, where no dissimilar pairs but all similar pairs are identified. Then 30 pairs of points are selected at random and their distances in DA are used as the side information for learning a new distance metric. This new distance metric is then used to inform the embeddings.

Results using these distances are somewhat noisier than with the class-equivalence informed embeddings but still provide good structure compared with the uninformed versions, and they group the data. Informed MDS (Figure 15, glasses omitted) and Informed Isomap (Figures 16, glassed omitted) group quite effectively, with a few images placed inappropriately. Informed LEM (Figures 17 and 18), Informed LLE (figures omitted), and Informed SDE (figures omitted) all give results similar to one another, and all show noisier performance on the glasses attribute than on the beards (beards are likely easier since they create a more substantial difference in an image than glasses). All methods group beardedness quite well. These last results show that preprocessing based on partial distance information is effective, although less so than the class-equivalence information. The informed embeddings are still more useful than the uninformed.

6 Conclusions

Many machine learning techniques handle complex data by mapping it into new spaces and then applying standard techniques, often utilizing distances in the new space. Learning a distance metric directly is an elegant means to this end. This research shows how side information of two forms, classequivalence information and partial distance information, can

1st dimension

1st dimension

1st dimension

1st dimension

Figure 16: Isomap and Distance-Informed Isomap with (un)bearded distinction (30 distances)

be used to learn a new distance as a preprocessing step for embedding. The results demonstrate that side information allows us to capture attributes of the data within the embedding in a controllable manner. Even a small amount of side information can improve the embedding's structure. Furthermore, the method can be kernelized and also used to capture multiple attributes in the same embedding. Its advantages over existing metric learning methods are a simpler optimization formulation that can be readily solved with off-the-shelf software and greater flexibility in the nature of the side information one can use. In all, this technique represents a useful addition to our toolbox for informed embeddings.

1st dimension

1st dimension

Figure 18: LEM and Distance-Informed LEM with (no)glasses distinction (30 distances)