Empirical Risk Minimization for Metric Learning Using Privileged Information

1 Introduction

Learning a suitable distance metric from the given training instances plays an important role in many machine learning and computer vision tasks. Over the past decades, several distance metric learning (DML) methods have been proposed, e.g., information-theoretic metric leaning (ITML) [Davis et al., 2007], logistic discriminant metric learning (LDML) [Guillaumin et al., 2009], and discriminative deep metric learning [Hu et al., 2014]. Existing algorithms for metric learning have been shown to perform well empirically on a variety of applications, e.g., classification and clustering. While, most of them restrict the distance between a pair of similar/dissimilar instances to be lower/higher than a fixed threshold. Such fixed threshold based constraints may suffer from suboptimal performance when coping with some real world tasks with complex inter-class and intra-class variations (See Figure 1).

A natural solution to alleviate the limitations of fixed threshold based DML method is to design a locally adaptive decision rule. [Li et al., 2013] proposed to learn a secondorder local decision function in the original feature space to replace the fixed threshold. [Wang et al., 2014] introduced an adaptive shrinkage-expansion rule to shrink/expand the Euclidean distance as an adaptive threshold. These two earlier works both leverage the information from the original feature space to guild the decision making. However, the guidance from the original feature space might be relatively weak, since original feature is usually noisy and less discriminative. Another way is to incorporate additional knowledge beyond the original space.

It has been shown in [Vapnik and Izmailov, 2015] that a more reliable and effective model can be learned if some high-level additional knowledge is exploited during the training stage. Such high-level knowledge is called privileged information and is only available in training stage. It typically describes some important semantic properties of the training instance, such as the attributes, tags, textual descriptions or other high-level knowledge. This idea of privileged information is inspired by the human teaching-learning in which the students will learn better if a teacher can provide some explanations, comments, comparison or other supervision. It was first incorporated into SVM in the form of SVM+ [Vapnik and Vashist, 2009] and has been utilized in object localization [Feyereisl et al., 2014] and image categorization [Li et al., 2014] in recent years.

Motivated by [Vapnik and Izmailov, 2015], in this paper we develop a new DML method using privileged information under the generic empirical risk minimization (ERM) framework, termed as ERMML+. First, we represent each training instance with two forms of feature representations: one is original feature representation and the other is privileged information representation. Thereby an emerging problem is how to exploit privileged information for metric learning. Generally, there exists a semantic gap between the original space and the privileged space, since the original feature is at the low-level space while privileged information is a highlevel semantic knowledge. To bridge the semantic gap, we jointly learn two Mahalanobis distance metrics with positive semi-definite (PSD) constraints by minimizing the empirical loss penalizing the difference between the distance in the original space and the distance in the privileged information space. The distance in the privileged space functions as a local decision threshold to guide the metric learning like a teacher, which can effectively relax the fixed threshold. We optimize the objective function using the Accelerated Proximal Gradient (APG) approach to search a global optimum solution with a fast convergence rate. We have evaluated the proposed method on two real world problems: person reidentification and face verification. Experiment results show that by leveraging the privileged information, our method outperforms not only the classical metric learning algorithms, but also the state-of-the-art methods in the computer vision community.

2 RelatedWork

During the past decade, many algorithms have been developed to learn a Mahalanobis distance metric, e.g., [Weinberger and Saul, 2009; Davis et al., 2007; Guillaumin et al., 2009; Bian and Tao, 2012]. Here we only briefly review several most relevant works.

[Guillaumin et al., 2009] proposed a logistic discriminant metric learning (LDML) method which is related to our work, but LDML doesn't use any regularization term including the PSD constraint, which easily suffers from overfitting problem. The PSD constraint can provide a useful regularization to smooth the solution of the metric. [Bian and Tao, 2012] developed a loss minimization framework for metric learning, which is quite rigid since it relies on a strong assumption that the learned metric is bounded. Besides, [Guillaumin et al., 2009; Bian and Tao, 2012] both adopt the fixed threshold based constraints. Compared with them, we learn a PSD metric by exploiting the privileged information to construct a local decision function, which is more robust and shows better performance.

Recently, [Fouad et al., 2013] proposed a two stage strategy to exploit privileged information for metric learning based on ITML. They first learn a metric using the privileged information to remove some outlier pairs and then use the remaining pairs to learn a metric based on the original feature. Following [Fouad et al., 2013], [Xu et al., 2015] proposed a ITML+ method, in which privileged information is used to design a slack function to replace the slack variables in ITML. Compared with two ITML based methods [Fouad et al., 2013; Xu et al., 2015], we provide a new scheme to leverage privileged knowledge for distance metric learning under the generic ERM framework, which has good statistical property and can be extended easily by incorporating different loss functions and regularization terms. Moreover, we apply low rank selection for the learned metric in each iteration, which allows us to work directly with higher dimensional input data. While ITML based methods aim to learn a full matrix for the target distance metric that is in the square of the dimensionality, making it computationally unattractive for high dimensional data and prone to overfitting [Mignon and Jurie, 2012]. It is shown in the experiments that our method ERMML+ performs better than the ITML+ method.

3 ERM for DML

Assume we have a pairwise constrained training instances set Z = ¶(xi↪ zi↪ `i) ♣i = 1↪ 2↪ ▷ ▷ ▷ ↪ n♦, where xi 2 Rd ↪ zi 2 Rd are both defined on the same space, i is the index of the i-th pair of training instance, and `i is the label of the pair (xi↪ zi) defined by

where S denotes the set of similar pairs and D denotes the set of dissimilar pairs. The goal of DML is to learn a Mahalanobis distance metric defined by

where M 2 Rd⇥d is the learned PSD metric. The learned Mahalanobis distance dM(xi↪ zi) is expected to be small if xi and zi are similar, or large if they are dissimilar.

Given a metric M, how to determine whether two instances are similar or dissimilar? A common way is to compare their distance with a fixed decision threshold σ [Mignon and Jurie, 2012], then the decision function f can be defined by

If they are similar, the decision function f > 0, otherwise f < 0.

The problem of DML can be cast in the generic ERM framework by minimizing the empirical risk E(M)

where L(·) is a convex loss function (decrease progressively), e.g., log loss and smooth hinge loss. Previous DML methods [Guillaumin et al., 2009] and [Mignon and Jurie, 2012] are both under this framework.

4 ERM for DML using Privileged information

4.1 ProblemFormulation

Traditional pairwise constrained DML methods usually adopt the fixed threshold based decision function f, which is too rough to obtain a reasonable metric. In this paper, we aim to design a locally adaptive decision rule to alleviate the limitations of fixed threshold based methods.

Motivated by the [Vapnik and Izmailov, 2015], we exploit privileged information to design an adaptive decision function in the training stage. First, each training instance is represented with two forms of feature representations: one is xi 2 Rd from the original feature space; the other is x⇤i 2 Rd⇤ from the privileged space. The training set is reformulated as Z = ¶(xi↪ x⇤i ↪ zi↪ z⇤i ↪ `i) ♣i = 1↪ 2↪ ▷ ▷ ▷ ↪ n♦. Then, we replace the fixed threshold σ in (3) using the squared distance d2P(x⇤i ↪ z⇤i ), where P 2 Rd⇤⇥d⇤ is the distance metric matrix in the privileged information space. d2P(x⇤i ↪ z⇤i ) functions as the adaptive decision threshold. Our locally adaptive decision function is formulated by

To be simplified, we rewrite the decision function as

by introducing two block-diagonal matrices Ai and S. h·↪ ·i denotes the matrix inner product. Ai 2 R(d+d⇤ )⇥(d+d⇤ ) and S 2 R(d+d⇤ )⇥(d+d⇤ ) are defined by

We also take the severe imbalance of similar/dissimilar pairs into consideration by weighting each pair in our empirical risk function. Combining the new decision function f and the pair weight w, our problem can be formulated as

where Q = ¶M ⌫ 0;P ⌫ 0♦, wi is the weight of the similar/dissimilar pairs. If `i = 1 (-1), wi is defined by the reciprocal of the number of similar (dissimilar) pairs. Compared with ITML+, our formulation has a general form that follows the ERM framework.

In our model, d2P(x⇤i ↪ z⇤i ) can effectively guide the decision making in the original feature space like a teacher by controlling student's concept of similarity between training instances. See Figure 1 for two representative examples from the VIPeR dataset. In Figure 1, (a↪ b) and (d↪ e) are two similar pairs but with large inner-class variations; (b↪ c) and (e↪ f) are two dissimilar pairs while sharing large inter-class similarities. We can see that the learned metric M results in a suboptimal metric when only uses original feature for training, while the metric M+ performs better by exploiting the privileged information in the training stage. Note that we don't leverage privileged information in the testing stage.

4.2 Optimization using APG

In this paper, we use the well known log loss function as an example, 1 which is defined by L(u) = ln(1 + exp(-u)). Hence, the objective function in (9) is rewritten as

Then, we exploit the APG method [Nesterov, 2004] to solve the optimization problem. It has been proved that APG method can achieve the optimal convergence rate at O(1◁k2 ), where k is the number of iteration steps. However, APG method requires the condition that the objective function is Lipschitz continuous with a Lipschitz constant L. According to Property 1, we know that E(S) in (10) has a Lipschitzcontinuous gradient with a Lipschitz constant.

Property 1 Given any direction ∆ 2 R(d+d⇤ )⇥(d+d⇤ ) , the empirical risk E(S) satisfies

where L = 14 nP i=1 wikAik2F , and k · kF denotes the Frobenius norm.

Proof. The gradient of E(S) is computed by

Define function as φ(%) = hrE(S + %∆)↪∆i with % > 0, and we have

Hence,

We can see that the log loss based E(S) has a Lipschitz gradient with a constant L = 14 nP i=1 wikAik2F . This completes the proof.

Below, we detail the optimization procedure at step k.

Suppose the latest two approximate solutions Sk-1 and Sk-2 are known, we can construct the search point Zk at current step as a linear combination of the latest two approximate solutions

1 Due to the space limits, we only use one example for analysis. Other convex loss functions, e.g., smooth hinge loss and squared loss, can also be used in our model.

Algorithm 1 ERMML+

Input: The training set (xi↪ x⇤i ↪ zi↪ z⇤i ↪ `i) ↪ i = 1↪ 2↪ ▷ ▷ ▷ ↪ n. Output: S = diag(P↪M), where M is the learned metric. Initialize: L0, γ, ✏, ↵0, M0 = M-1 = Id⇥d , P0 = P-1 = Id⇤⇥d⇤ .

Iterative: k = 1↪ 2↪ · · ·

• 2: Compute Zk by (15).
• 1: Set ↵k = 12 ⇣1+ q1+4↵2k-1⌘.
• 3: Compute E(Zk) and rE(Zk) with a loss function.
• 5: Obtain Sk by solving (18) using (22) and (23).
• 4: Set tk = 1◁Lk-1.
• 6: If the condition in (24) is not satisfied, set Lk-1 = γLk-1 and return to step 4.

Until ♣E(Sk) -E(Sk-1)♣ < ✏.

• 7: Set Lk = Lk-1

where ↵k = 12 ⇣1+ q1+4↵2k-1⌘. The problem can be reformulated equivalently as a proximal regularization of the linearized function E(S) at Zk as

where tk is the step size of the gradient method. The gradient rE(Zk) is block-diagonal

By ignoring the constant term E(Zk) and adding another constant term tk 2 krE(Zk)k2F , the problem in (16) can be expressed equivalently as

where Hk is a block-diagonal matrix and it can be rewrote as

where

Since the two diagonal blocks M and P in S are not coupled, Mk and Pk can be obtained independently. We can compute Mk and Pk by projecting HMk and HPk into the positive semi-definite cone, respectively. We take Mk as an example. To obtain Mk, we conduct singular value decomposition (SVD) on HMk and then we have

where UM and ⇤M are obtained from the SVD. ⇤M is a diagonal matrix that contains all the singular values of HMk . Since M ⌫ 0, we can obtain Mk by

where ⇤M+ is diagonal with (⇤M+ )ii = max {0↪⇤Mii . Pk can be obtained in the same way by

Step Size Estimation

It's vital to choose an appropriate step size tk for APG algorithm. In [Nesterov, 2004], the reciprocal 1L of Lipschitz constant functions as the step size . However, it is too conservative to set tk = 1L for all k and it is also very time consuming to compute the Lipschitz constant directly.

Following [Beck and Teboulle, 2009], we first initialize L with a small value L0 and increase this estimate with a multiplicative factor γ (γ > 1) repeatedly until the following condition is satisfied

This procedure ensures that the step size is suitable. The process of the optimization is summarized in Algorithm 1.

Convergence Analysis

We show in the following theorem that by perform the APG method, the proposed method can achieve the optimal convergence rate at O(1◁k2 ).

Theorem 1 Let ¶Sk♦ be generated by the Algorithm 1. Then for any k > 1 we have

where ˆS is the optimal solution.

The proof of this theorem can follow the same strategy as in [Beck and Teboulle, 2009]. We omit the proof here for the space limits. We empirically verify the convergence rate of our method with APG in comparison with the standard gradient descent method using the same step size estimation strategy in Figure 2. We run this experiment on the LFW dataset as an example. We can see that the APG method converges fast than the standard gradient descent method.

5 Experiment

To validate the effectiveness of our method, we conduct experiments on three real-world datasets: VIPeR [Gray and Tao, 2008], iLIDS [Zheng et al., 2009], and LFW [Huang et al., 2007]. VIPeR and iLIDS are two person re-identification (reid) datasets and LFW is a face verification dataset. In each experiment, we present results by comparing the proposed ERMML+ method with various methods including LMNN, ITML, KLFDA [Xiong et al., 2014], KISSME [Kostinger et al., 2012], SEAML [Wang et al., 2014], and ITML+ [Xu et al., 2015]. Among them, KLFDA and KISSME are two state-of-the-art methods proposed recently for person re-id and face verification. The fixed threshold based method in section 3 is realized as a baseline, termed as ERMML. For a fair comparison, similar/dissimilar pairs weighting is also incorporated in ERMML. The fixed threshold is set as the mean of the squared Euclidean distances between all pairs of training instances. In the following experiments, we implement ERMML+ and ERMML using the log loss function.

5.1 Person Re-identification on VIPeR and iLIDS

VIPeR is a widely used person re-id dataset containing 632 pedestrians in which each person has a pair of images taken from widely differing views. The large viewpoint change of 90 degrees or more as well as huge lighting variations in VIPeR make it one of the most challenging person re-id datasets. iLIDS has 476 images of 119 pedestrians, which is collected at an airport and has severe occlusions.

We adopt the single-shot experiment setting in [Xiong et al., 2014] for all DML methods. The datasets are randomly divided into two parts and the testing set has p individuals. We repeat the random partition 10 times to get an average performance. For easy comparison, we evaluate the re-id results by the cumulative matching characteristic (CMC) curve, which is an estimate of finding the correct match in the top n match. To obtain the privileged information for ERMML+ and ITML+, we have trained several attribute detectors to detect the pedestrian attributes as the privileged information.

We utilize the weighted histograms of overlapping stripes descriptor 2 for original feature representation. The descriptor is a 5138 dimensional feature vector. For all methods, PCA is first used for dimension reduction. ERMML+ and ERMML are applied with all PCA components, since they employ the low-rank projection to obtain the PSD constrained metric. Other algorithms are applied with the first 100 dimensional PCA components.

Figure 3 plots the CMC curves on VIPeR with p = 316 for eight DML methods . We can see from Figure 3 that ERMML+ achieves the best performances 41▷93% at rank=1, which is better than all the other methods including SEAML, ITML+ , and two state-of-the-art methods KISSME and KLFDA. The baseline method ERMML obtains the second best result 36▷01% at rank=1 which can be owing to the effectiveness of log loss based ERM framework. ERMML+ achieves 5▷92% improvement over ERMML and ITML+ achieves 2▷45% improvement over ITML, which indicates that privileged information is helpful to learn a better metric and can play a more effective role in the ERM framework than the ITML framework. ERMML+ also achieves 14▷62% improvement over the adaptive DML method SEAML at rank=1. ITML and LMNN perform not very well due to the complex inter-class and inner-class variations in VIPeR. The success of ERMML+ mainly benefits from the exploring of privileged information and the ERM framework.

2 http://www.micc.unifi.it/lisanti/source-code/whos/

For a fair comparison, we also show the results of all methods with the same feature at Table 1. We can note that ERMML+ still perform the best even with the first 100 dimensional PCA components. We also compare the performance of ERMML+ with six newly released results on the VIPeR dataset using the same protocol , including SLKFP [Chen et al., 2015], QALF [Zheng et al., 2015], XQDA[Liao et al., 2015], PRCSL [Shen et al., 2015], MLAPG [Liao and Li, 2015], CVPDL[Li et al., 2015]. We can see that our method results in a new state-of-the-art performance on VIPeR.

Figure 4 compares ERMML+ with other DML methods by plotting the CMC curves on iLIDS with p = 60. It is apparent that by exploiting privileged information, our locally decision function in (5) significantly improves the performance of traditional method with a fixed threshold. Similarly as in Figure 3, ERMML+ achieves a significant improvement over ITML+ again, which shows that we can learn a better metric by incorporating the privileged information into the ERM framework.

5.2 Face Verification on LFW

LFW is a widely used face images database containing more than 13000 face images from 5749 individuals. We extract the 3456 dimensional SIFT descriptors as the original features, which are reduced to 200 dimensions using PCA for all methods. We use the face attribute 3 as the privileged information for ERMML+ and ITML+.

The dataset is divided into 10 folds, in which each fold has 300 similar image pairs and 300 dissimilar image pairs. In this experiment, we randomly choose K folds for training and the rest is used for testing. The procedure is repeated 10 times to report an average result. We only consider the pairwise constraints given by the similar/dissimilar pairs.

Figure 5 plots the ROC curves of different DML methods on LFW. It shows that privileged information based methods ERMML+ and ITML+ perform better. Our method improves ERMML by 2▷1% and is slightly better than ITML+ by 1▷1%. Note that the improvement brought by the privileged information is relatively small on LFW. It is mainly due to the fact that SIFT is already a strong visual descriptors, which can learn a good metric independently if sufficient training samples are provided.

3 http://www.cs.columbia.edu/CAVE/projects/faceverification/

To analyse the influence of privileged information in more depth, we compare the performance of ERMML+, ITML+, ERMML, and ITML by varying the number of training folds from K = 1 to K = 6 in Figure 6. Figure 6 shows that the benefit of privileged information tends to reduce with the increasing of the size of training set. That is because the metric learning algorithm may suffer from overfitting when the training samples are too limited while the incorporation of privileged information can effectively relieve the overfitting by introducing necessary correcting information. Our method would be particularly useful if there exist only a few training data or the original feature is weak.

6 Conclusion

In this paper, we propose to learn an effective metric learning method by exploiting privileged information in the generic empirical risk framework. We solve the problem efficiently by the Accelerated Proximal Gradient method. Our proposed method ERMML+ generalizes from the traditional metric learning methods using a fixed threshold by designing a locally adaptive decision rule based on privileged information. We apply the proposed method to solve two real world problems: person re-identification and face verification. Experiment results have shown that our method can outperform the state-of-the-art metric learning methods.

Acknowledgments

This work is partially supported by Australian Research Council (ARC) Projects DP-140102164, FT-130101457, and LE140100061, and the National 973 Program of China under grant 2014CB347600, and the National Nature Science Foundation of China under grants 61272393, 61322201, and 61432019, and the China Scholarship Council (CSC).