Robust Distance Metric Learning with Auxiliary Knowledge

1 Introduction

A lot of machine learning and pattern recognition methods, such as clustering, classification, and regression approaches, involve the use of a distance metric over the input feature space. The performance of these methods often depends highly on the choose of metric. Instead of determining a metric manually, a promising approach is to learn an appropriate metric from data automatically. Distance metric learning has become an emerging topic in which the goal is to induce a powerful distance metric from labeled examples. The distance metric is found by keeping "similar" objects close together while separating "dissimilar" ones. In recent years, a number of metric learning methods have been developed, which have shown to perform well when sufficient training data are available. However, in many real-world applications, training examples are very few, and in which the performance of these methods may significantly degrade due to the "overfitting" problem [Hoi et al., 2008][Yang and Jin, 2006].

∗This work was performed when Zheng-Jun Zha was visiting Microsoft Research Asia as a research intern.

To derive reliable distance metric from the few labeled examples, one solution is to leverage auxiliary knowledge sources to assist distance metric learning, such as the structure information provided by the abundant unlabeled examples [Hoi et al., 2008] and the knowledge derived from auxiliary data (e.g., the distance metrics learned from auxiliary data). Different from labeled data, unlabeled data are typically widely available, and existing studies have shown that this knowledge can be helpful in distance metric learning [Hoi et al., 2008]. Here "auxiliary data" means the data that are collected from different sources and different from the target data in distribution. Such auxiliary data is easy to be obtained in practice and has proved useful in various applications [Pan et al., 2008] [Gupta and Ratinov, 2008] [Talvitie and Singh, 2007] [Mansour et al., 2007] [Satpal and Sarawagi, 2007].

However, directly applying the metric learned from auxiliary examples may not perform well since it might be biased to the distribution of the auxiliary data. Two straightforward approaches for leveraging the auxiliary data are : (1) to construct an "ensemble" combining the distance metric derived independently from the limited training data and the labeled auxiliary examples; and (2) to learn an "aggregated" distance metric from the combination of the limited labeled examples and auxiliary data. However, these methods may not work well mainly due to the distribution difference between the target and the auxiliary data. Moreover, learning an "aggregated" metric is typically expensive because the size of auxiliary data is usually large. Thus there is a need for a more efficient and effective approach for exploiting auxiliary knowledge to assist distance metric learning.

In this paper, we develop two novel algorithms for learning distance metric from only a small amount of labeled examples by simultaneously exploiting abundant unlabeled examples, as well as incorporating available prior knowledge from auxiliary data. Specifically, the distance metric learning is formulated as a regularized loss minimization problem. Two metric learning approaches are developed on the basis of manifold regularization and log-determinant divergence regularization technique, respectively, which can handle multiple knowledge, namely leveraging multiple auxiliary knowledge simultaneously to assist metric learning from few labeled examples. The weights of the auxiliary knowledge are optimized automatically to reflect the utility of these knowledge. We apply the proposed methods to face recognition task. The experimental results show that our methods can construct reliable distance metric and do significantly improve the performance when training data are limited.

The rest of this paper is organized as follows. We review related work in Section 2. Section 3 describes the proposed distance metric learning methods. Experimental results are reported in Section 4, followed by concluding remarks in Section 5.

2 RelatedWork

Our work is closely related to the previous studies on supervised distance metric learning [Yang and Jin, 2006] [Yang, 2007]. Most existing methods learn a distance metric from side information that is presented in a set of pairwise constraints: equivalence constrains that include pairs of "similar" examples and inequivalence constraints for "dissimilar" examples. The optimal distance metric is derived by keeping "similar" examples close and enforcing the "dissimilar" examples well separated. We briefly review some representative work here.

In recent years, a number of algorithms have been proposed for supervised distance metric learning. [Bar-Hillel et al., 2005] proposed Relevant Components Analysis (RCA) method to learn a linear transformation from the equivalence constrains, which can be used directly to compute the distance between two examples. Disciminative Component Analysis (DCA) and Kernel DCA [Hoi et al., 2006] improved RCA by exploiting negative constraints and aim to capture nonlinear relationships using contextual information. [Schultz and Joachims, 2003] extended the support vector machine to distance metric learning by encoding the pairwise constraints into a set of linear inequalities. [Xing et al., 2003] formulated distance metric learning as a constrained convex programming problem by minimizing the distance between the data points in the same classes under the constraint that the data points from different classes are well separated. Neighborhood Component Analysis (NCA) [Goldberger et al., 2004] learned a distance metric by extending the nearest neighbor classifier. [Weinberger et al., 2006] proposed the maximum-margin nearest neighbor (LMNN) method that extends NCA through a maximummargin framework. [Globerson and Roweis, 2006] learned a Mahalanobis distance by collapsing examples in the same class to a single point and keeping examples from different classes far away. [Davis et al., 2007] formulated distance metric learning as a Bregman optimization problem. [Hillel and Weinshall, 2007] defined the similarity as the gain in coding length by shifting from pairwise independent encoding to joint encoding. [Yang and Jin, 2007] presented a Bayesian framework for distance metric learning that estimates a posterior distribution for the distance metric from labeled pairwise constraints. [Yeung et al.,

2007] proposed a nonlinear metric learning method based on the kernel approach. [Alipanahi et al., 2008] show a strong relationship between distance metric learning methods and Fisher Discriminant Analysis (FDA). [Hoi et al., 2008] proposed a semi-supervised distance metric learning method that integrates both labeled and unlabeled examples.

3 Distance Metric Learning with Auxiliary Knowledge

3.1 Problem Set-UP

Let C = {x1, x2, · · · , xN} denote a collection of N data points, where xi ∈ Rd is the d dimensional feature vector. For the labeled examples in C, two sets of pairwise constraints are available,which are denoted by S and D, respectively.

where S is the set of similar pairwise constraints, and D is the set of dissimilar pairwise constraints.

For any two data points xi and xj , a Mahalabobis distance between them can be expressed as:

where M ∈ Rd×d is the Mahalabobis metric, a symmetric matrix of size d × d. In general, Mmust be positive smeidefinite (M⪰ 0) to satisfy the properties of metric, i.e., nonnegativity and triangle inequality. When M is equal to the identity matrix I, the distance in Eq.(1) reduces to the Euclidean distance.

Many recent studies on distance metric learning focus on learning the Mahalabois matric M by leveraging the similar and dissmilar pairwise relations in S and D. However, in many real-world scenario, the labeled examples are usually insufficient. As a result, the typical metric learning methods may suffer from the "overfitting" problem and can not provide reliable distance metric. On the other hand, the abundant unlabeled data add some auxiliary knowledge, i.e., the previously learned metrics from auxiliary data, are typically available and beneficial to the metric learning task. Therefore, we propose to learn a robust metric under the assistance of these auxiliary metrics and the abundant unlabeled data in C. LetM= {M1,M2, · · · ,MK} denote the set of K available auxiliary metrics Mi ∈ Rd×d. Our goal is to find an optimal distance metric from the data collection C, the sets of pairwise constraints S and D, and the set of auxiliary metrics M. To achieve this goal, two novel distance metric learning algorithms are developed in the following subsections.

3.2 Our Approach

Given the above information C, S, D, andM, we can formulate the distance metric learning problem into the following optimization framework:

where f is some objective function defined over the given data and M∗ is the desired distance metric. The key to find the optimal distance metric is to formulate a proper objective function f. Following the regularized loss minimization principle, we can define f as a regularized loss function as:

where L(·) is a loss function defined on the pairwise constraints while R(·) is the regularization term that takes advantage of unlabeled data and auxiliary knowledge to prevent "overfitting" and enhance the generalization and robustness of the distance metric.

Eq.(3) provides a generic solution for learning robust metric from limited training data by exploiting auxiliary knowledge and unlabeled data. This solution offers great flexibility and efficiency, because it directly manipulates the previously learned metric as an abstraction of the auxiliary data and requires no raw auxiliary data. This also makes it applicable even when the raw data are not accessible. From this generic solution, one can derive concrete algorithm by choosing certain loss functions L(·) and regularization function R(·). While the choices are virtually numerous, we discuss two specific algorithms here.

Loss Function

One common principle for metric learning is to keep the "similar" data points close and separate the "dissimilar" ones. Following this principle, the loss function L(·) should be defined in the way such that the minimization of the loss function will result in minimizing the distances between the data points with similar constraints and maximizing the distances between the data points with dissimilar constraints. We adopt the sum of squared distances expression for defining the loss function in terms of its effectiveness and efficiency:

where tr(·) means the trace operation on matrix, ηs and ηd are two trading-off parameters balancing the similar and dissimilar constraints, and

Next, we move our effort to define proper regularization function R(·).

Log-Determinant Regularization Function

As aforementioned, the training data are usually limited in practice and the available auxiliary knowledge (i.e., the auxiliary metrics M) can be utilized to assist the distance metric learning. To encode M into f, we resolve to the regularization function R(·), which is a key to prevent "overfitting" and enhance generalization and robustness of the learned metric. We define R(·) in the way such that the minimization of R(·) will result in minimizing the divergence between the target metric M and the auxiliary metric Mk ∈ M. In other words, we aim to regularize M as close as possible to the auxiliary distance metrics. Here we adopt Bregman divergence [Davis et al., 2007] to measure the difference between M and Mk as:

where g(·) is a strict convex and continuously differentiable function. We define g(·) as -logdet(·) and get the log-determinant divergence between M and Mk:

where we ignore the constant term regardingMk.

Based on Eq.(5), we formulate R(·) as a combination of the divergence between M and each auxiliary knowledge Mk:

Substituting Eq.(4) and Eq.(6) into Eq.(3), we can get the concrete algorithm named L-DML (i.e., Log-determinant regularized Distance Metric Learning):

where μ = {μk}Kk=1 are the weights that reflect the utility of the auxiliary metrics, ‖μ‖2 is the L-2 norm of the weights and γ is a scalar. The new regularizer ‖μ‖2 is adopted to penalize large weights on auxiliary metrics, and it thus prevents "overfitting" on the auxiliary knowledge. How to determine the weights {μk}Kk=1 is a problem, given the difficulty of knowing each auxiliary metric's utility to the target metric. To overcome this problem, L-DML is motivated to learn the weights {μk}Kk=1 automatically and simultaneously with the target metric M. The solution will be discussed later.

Manifold Regularization Function

The aforementioned L-DML algorithm has leveraged the auxiliary metrics on the basis of log-determinant regularization technique. However, it does not take advantage of any information of unlabeled data which can be useful for distance metric learning, especially when labeled data are limited. Therefore, we put effort to define a new regularizer such that it can simultaneously encode the auxiliary metrics M= {Mk}Kk=1 and the unlabeled examples in the data collection C. We define the new regularization term following manifold regularization principle.

Given auxiliary metric Mk, the distance between two data points xi and xj under Mk can be calculated as dMk (xi, xj) = √(xi -xj)T Mk(xi -xj). Based on such distance measure, a data adjacency graph Wk ∈ RN×N can be derived from the data collection C, wherein each element Wk(i, j) is the edge weight between two samples xi and xj. Considering the target metric M, the distance between xi and xj is dM(xi, xj) = √(xi -xj)T M(xi -xj) that can be further written as dM(xi, xj ) = √(xi - xj )T PPT(xi - xj) with P ∈ Rd×m is some corresponding linear mapping and M = PPT. We can find that learning of M is equivalent to the learning of a linear projective mapping P in the feature space. Following the manifold regularization principle, we formulate the regularizer in the way such that the minimization of the regularizer will result in making the linear projective mapping being smooth over the data adjacency graph. Mathematically, we write the regularizer as:

where Lk is the graph Laplacian defined as Dk -Wk, Dk ∈ RN×N is a diagonal matrix with Dk(i, i) = ∑Ni=1 Wk(i, j), and pl is the l-th column of matrix P

Based on Eq.(8), we can define the regularization term R(·) as the combination of Rk(·) to incorporate all the auxiliary metrics and unlabeled data information.

Substituting the loss function in Eq.(4) and the regularizer in Eq.(9) into Eq.(3), we can get the following algorithm. We name it as M-DML (i.e., Manifold regularized Distance Metric Learning) algorithm.

where α = {αk}Kk=1 are the weights that reflect the utility of the auxiliary metrics, β is a scalar, and regularizer ‖α‖2 is the L-2 norm of the weights {αk}Kk=1 that prevents "overfitting" on auxiliary metrics. We can find that the LRDML algorithm in [Hoi et al., 2008] is a special case of our M-DML method. Specifically, M-DML will reduce to LRDML when only Euclidian metric is available as the auxiliary metric, i.e., M = {I}.

3.3 Learning by Alternating Optimization

Up to now we have shown that multiple auxiliary metrics, unlabeled data, and the pairwise constraints on labeled examples can be integrated into a regularized loss minimization framework. Two distance metric learning algorithms L-DML and M-DML have been developed by exploiting log-determinant and manifold regularization technique, respectively. Now we discuss the solution of them.

We first consider M-DML. Equation (10) is a standard formulation of Semidefinite Programs (SDP) [Stephen and Lieven, 2003] under any fixed α and can be solved efficiently using existing convex optimization packages, such as SeDuMi [Sturm, 1999]. However, α is crucial to the performance of M-DML. Since the utility may vary intensively among different auxiliary metrics, α should vary as well as according to their utility. Thus M-DML is motivated to learn both the distance metric M and the linear combination coefficients α simultaneously. We can realize the joint learning of M and α by adopting the alternating optimization technique to solve Eq.(10) in an iterative manner. Specifically, we solve M-DML as follows: solving Eq.(10) with respect toM with fixed α; then optimizing Eq.(10) with respect to α with M taking the value obtained before; and alternatively iterating the above two steps until the decrement of the objective function is zero. This process will converge to the optimal solution since the objective function is convex to both M and α. Analogously, the L-DML method can also be solved via alternating optimization.

4 Experiments

In this section, we investigate the performance of the proposed L-DML and M-DML methods for face recognition.

4.1 Data Sets

We employ four face image data sets in our experiments: ORL [Samaria and Harter, 1994], Yale [Belhumeur et al., 1997], Extended Yale-B [Georghiades et al., 2001], and CMU PIE [Sim et al., 2003] collections. The ORL data set contains 40 distinct human subjects and each subject has ten gray images. The Yale corpus consists of 165 gray images of 15 subjects and there are 11 images per person. The Extended YaleB data set contains 161,289 gray images of 38 human subjects under nine poses and 64 illumination conditions. We choose the frontal pose and use all the images under different illumination, thus there are 64 images for each person. The CMU PIE corpus contains 41,368 images of 69 subjects under 13 different poses, 43 different illumination conditions, and with four different expressions. We choose ten subjects under two near frontal poses and all the images under different illuminations and expressions. Thus there are 68 images per subject and 680 images in total. For computational efficiency, all the face images are manually aligned and cropped. The size of each cropped image is 20 × 20 pixels with 256 gray levels per pixel. The feature (pixel values) are then normalized to [0,1].

4.2 Experimental Setting and Results

Among the four data collections, we choose ORL, Yale and CMU PIE as the auxiliary data sets and Extended Yale-B as the target data. We learn the auxiliary metrics using Relevance Component Analysis (RCA) [Bar-Hillel et al., 2005] from ORL, Yale, and CMU PIE data. Then we randomly select t images per subject from Extended Yale-B data set with the labels to form the training data and the remaining images are considered to be the test examples. We gradually increase t (t = 2, 4, 6, 8, 10), and for each t we perform ten trials and then compute the average performance. The tradeoff parameters are empirically set as: ηd and γ (β) are about one-forth and one-eighth of ηs, respectively.

For comparison purpose, we also evaluate seven existing methods for recognizing the face images in target data: Euclidean distance (EU), Xing's method (Xing) [Xing et al., 2003], RCA [Bar-Hillel et al., 2005], DCA [Hoi et al., 2006], NCA [Goldberger et al., 2004], LMNN [Weinberger et al., 2006], and LRDML [Hoi et al., 2008]. Each of them is applied in the following four ways.

• "Target" (Tar): Learn the distance metric from target data.
• "Auxiliary" (Aux): Learn the distance metrics from labeled auxiliary data.
• "Aggregate" (Agg): Learn the distance metrics from the combination of target and auxiliary data.
• "Ensemble" (Ens): Construct an "ensemble" combining the distance metrics derived independently from target and auxiliary data.

The semi-supervised metric learning method LRDML has not been applied in "Auxiliary" and "Ensemble" ways since the auxiliary data are fully-labeled and thus no unlabeled example is available.

We treat face recognition as a multi-class classification problem and use the nearest neighborhood classifier to perform the classification. Table 1 provides the performance of all the approaches. We only show the average performance over all t due to the lack of space. From the results, we can find that, by effectively leveraging auxiliary knowledge, the proposed L-DML method outperforms all the existing approaches. By exploiting auxiliary knowledge and unlabeled data at the same time, M-DML achieves the best overall performance. Fig. (1) shows the detailed performance of LDML and M-DML vary with the size of training data. For comparison purpose, the performance of LRDML, which is a semi-supervised method, and LMNN, which achieves the best performance among existing supervised methods, are also illustrated in Fig.(1). From the results, it can be found that L-DML and M-DML can achieve better performance than LMNN and LRDML with the same number of training examples. From another perspective, the proposed methods need much less training data to reach the same performance than the existing approaches.

We further investigate the performance comparison between utilizing multiple auxiliary metrics and single auxiliary metric. Table 2 provides the results of L-DML and M-DML when they exploit multiple auxiliary metrics and each individual auxiliary metric. We also illustrate the results of LDML and M-DML that adopt uniform weights, i.e., assign equal weights to all the three auxiliary metrics (see Eq.(7) and Eq.(10). From the results we can clearly see that exploiting the three auxiliary metrics leads to better results than only using each individual auxiliary metric. We can also see that our automatic weight learning approach outperforms the method of adopting uniformweights. This indicates that the proposed L-DML and M-DML are able to weight auxiliary knowledge properly.

5 Conclusions

We have developed two novel approaches for learning reliable distance metric from limited training data by exploiting auxiliary knowledge. These approaches are efficient and flexible as they directly utilize the metrics learned from the auxiliary data and require no raw auxiliary examples. Moreover, the proposed methods can effectively take advantage of multiple auxiliary metrics. We apply the proposed approaches to face recognition and compare them with various existing methods. The results show that our methods are more effective than the state-of-art methods for learning robust distance metric from few labeled examples.