Parametric Distance Metric Learning with Label Information

1 Introduction

The notion of similarity or dissimilarity plays a fundamental role in pattern recognition and machine learning. A promis­ ing direction to pursue is to learn good (dis)similarity mea­ sures from data. Recently, learning distance metrics from data has aroused a great deal of interest from machine learn­ ing researchers. One typically wants to embed patterns !n a (possibly non-metric) input space into a feature space, m which the Euclidean distance between points accurately re­ flects the dissimilarity between the corresponding patterns. Therefore the (linear or nonlinear) mapping from the input space to the feature space corresponds to feature .extra~tion. Alternatively, the feature space may be a low-d1menswnal space for data visualization. . . .

In this paper, we propose a parametnc d1stance metnc learning method in the supervised setting. The main ideas of our method are summarized as follows. Using class la­ bel information, we define a similarity measure (and hence also the corresponding dissimilarity measure) between pat­ terns in the input space. The dissimilarity measure implicitly induces a metric space for embedding the original patterns. To explicitly represent the mapping from the input space to the feature space, we then approximate the mapping by a re­ gression model to embed the original patterns in an Euclidean space. The regression parameters are estimated from da~a with the objective that the dissimilarity between patterns m the input space is approximated by the Euclidean distance be­ tween points in the feature space. Once the regression model has been found, any new pattern can be mapped to its corre­ sponding location in the feature space. Dist~nce-based Il_leth­ ods, such as k-means clustering, nearest ne1ghbor classifiers and support vector machines, can then be applied in the fea­ ture space for clustering or classification applications.

*This research has been partially supported by the Re­ search Grants Council of the Hong Kong Special Administra­ tive Region under grants DAGO I/02.EG28, HKUST2033/00E and HKUST6195/02E.

The rest of this paper is organized as follows. A modified metric incorporating class label information is proposed in Section 2. Section 3 outlines our regression model for metric learning and the corresponding optimization method. Exp.er­ imental results are presented in Section 4, and the last sectwn gives some concluding remarks.

2 Modified Metric with Label Information

Denote the input space by JRq and the set of all C possible class (target) labels by T. A training set V ~ JRq x T has n patterns {(x1 , tl), . .. , (xn, tn)}, where ti = r if pattern i belongs to class r. Here, each pattern is assumed to belong to only one class. In general, a number of similarity measures can be defined on these patterns [Gower and Legendre, 1986]. In this paper, we utilize also the label information in defining the similarity Sij between patterns xi and Xj:

where II · II denotes the Euclidean norm and /3 > 0 is a width parameter. The corresponding dissimilarity 8ij is then:

As illustrated in Figure 1, this (dis)similarity measure en­ joys some nice properties for pattern discrimination. For ex­ ample, the (dis)similarity between any two patterns in the same class is always larger (smaller) than that between any two patterns belonging to different classes. Moreover, the larger the Euclidean distance between the patterns is, the smaller is the within-class similarity while the larger is the between-class similarity.

In recent years, finite metric spaces and their embeddings have received much attention [Indyk, 2001; Linial et al., 1995]. Among embedding into normed spaces, embedding into an Euclidean space is the most popular.

Given the dissimilarity matrix ~ = [J;1]nxn· we are in­ terested in the question of whether and how the dissimilarity matrix ~ can be embedded. In other words, for the original points {XI , . . . , Xn}, we attempt to find a configuration of points {xi, .. . , xn} in some Euclidean space JR 1 such that the squared distances between these points will be equal to the so-defined dissimilarities J; 1 .

Theorem 1 Define d; 1 = ,;r;:;, with J; 1 as in (2). The matrix D = [d;1] is metric. In other words, d; 1 satisfies the following properties:

The following theorem confirms that ~ can be embedded.

The proof of this theorem can be found in [Zhang et al., 2003]. The subsequent task is then to find the embedding, i.e., points {xi , .. . , xn} E JR 1 such that the inter-point dis­ tance is equal to d; 1 . In general, obtaining an exact solution for these x; 's is difficult. Nevertheless, because D is met­ ric, an approximate solution can be easily obtained by using principal coordinate analysis or other multidimensional scal­ ing (MDS) methods [Cox and Cox, 2000] . We will return to this problem in Section 3.

Notice that the resultant Euclidean embedding will still in­ corporate information from both the input space representa­ tion (x ;) of the patterns and their corresponding class labels

( t ;). Moreover, the distance metric d;1, like the associated 6;1, enjoys those nice properties useful for pattern discrimination.

3 Metric Learning with Regression Model

As mentioned in Section 2, an approximate solution for {xi , . .. , xn} can be obtained by using MDS. However, this may be intractable for large data sets. Moreover, for new pat­ terns with unknown labels, the problem then is on how to determine s ; 1 in the first place. Following [Koontz and Fuku­ naga, 1972; Cox and Ferry, 1993; Webb, 1995], we attempt to find a mapping from x ; in the original input space JRq to x ; in the embedded Euclidean space JR 1 · One possibility is to first obtain a MDS configuration, and then construct a regres­ sion model from x ; to x ; [Cox and Ferry, 1993]. However, this mapping is not determined as part of the MDS procedure [Webb, 1995]. In the following, we will follow the approach of [Webb, 1995].

Denote the mapping from the original input space JRq to the embedded Euclidean space JR 1 by f = (h, .. . , !L)'. Assume that each j ; is a linear combination of p basis functions:

where W = [w1 ; ]p x l contains the free parameters, and the ¢ 1 (x)'s are basis functions that can be linear or nonlinear. The regression mapping (3) can be written in matrix form as

where <jJ(x) = [¢ I(x), ... , </>p (x)]'. Let X be the target con­ figuration, with d; 1 (X) = ,;r;:; where 6;1 is defined in (2). Using the iterative majorization algorithm, we then minimize the squared error

w.r.t. W, where %(W) = IIW'(</J(x;) - </J (x j))ll · More details can be found in [Zhang et al., 2003] .

4 Experiments

In this Section, we perform experiments on six benchmark data sets (Table 1) from the UCI repository [Murphy and Aha, 1994]. The distance metric is learned using a small subset of the labeled patterns, with l = p = q, </J(x) = x and the width (3 in (1) set to the average distance of the labeled patterns to the class means. The remaining patterns are then used for testing.

Table 2 shows the classification results by the nearest mean and nearest neighbor classifiers, with both the Euclidean and learned metrics. As can be seen, the learned metric almost always outperforms the original metric.

Next, we perform clustering experiments using the k­ means clustering algorithm, with the value of k set to the true number of clusters in each data set. The clustered patterns are assigned labels and the clustering accuracy is measured by comparing these labels with the true labels (as in classi­ fication problems). As these cluster labels can be permuted without changing the clustering solution, results reported here are based on the labeling with the highest clustering accuracy. As can be seen from Table 3, the learned metric outperforms that with the original metric on all data sets.

5 Concluding Remarks

In this paper, we proposed a new parametric method for dis­ tance metric learning based on class label information. Ex­ periments on UCI data sets show promising results.

The current work can be extended in several directions. First, nonlinear basis functions can be used to improve the approximation power of the regression mapping. Second, al­ though Theorem 1 states that the dissimilarity measure in­ duces a metric, it is not clear whether the matrix is also Eu­ clidean. If this is the case, a new kernel can then be defined on the joint space of the input space and class label space [Schi:ilkopf, 2002]. Third, in addition to using label infor­ mation, we will also incorporate manifold structure between neighboring patterns into our metric learning process.