Multi-Level Metric Learning via Smoothed Wasserstein Distance

1 Introduction

Metric learning problem targets at learning an optimal distance matrix M via minimizing the distance function, such as Mahalanobis distance

to capture the important relationships among data for a given task. It has been shown to be indispensable when used in conjunction with many computer vision techniques that heavily rely on distances or similarities [Roth et al., 2014; Hu et al., 2014].

To obtain a well-learned M, various kinds of metric learning algorithms have been proposed, e.g., large-margin nearest neighbors (LMNN) [Weinberger and Saul, 2009], information-theoretic metric learning (ITML) [Davis et al., 2007], logistic discriminant metric learning (LDML) [Guillaumin et al., 2009], robust metric learning [Luo and Huang, 2018; Wang et al., 2014], etc. Among all these works, LMNN is widely used and generalized. If we denote the similar sample pairs by S and triplet constraint by R as:

∗To whom all correspondence should be addressed.

then LMNN model can be formulated as:

where µ ∈ [0, 1] controls relative weight between two terms, and ξijk is a safety margin distance for each triplet. Although LMNN is proved to be very effective in learning a good Mahalanobis distance for practical problems, it is sensitive to Euclidean distance when it computes neighbors of each sample at the beginning.

As with LMNN, most metric learning works mainly focus on improving the discriminability of the distance matrix M via minimizing the squared Mahalanobis distance from similar sample pairs. Especially, the descriptors of the sample pairs they address are usually assumed to be aligned in advance. However, in practice, such an assumption is often violated due to some unavoidable factors like geometrical deformation, non-linear lighting changes and heavily intensity noise. In this case, Mahalanobis distance is not applicable due to its limitation on descriptors of sample data.

Fortunately, the Wasserstein distance, as a cross-bin distance function, is good at dealing with such kind of hard-toalign problem. It at present plays an important role in many practical applications, including computer vision, statistics and etc [Bisot et al., 2015]. The original Wasserstein distance is motivated by the theory of optimal transport and some related methods used in image processing and compressed sensing [Rubner et al., 2000]. Due to its high time complexity, many researchers try to improve the efficiency by simplifying the linear programming formulation with regard to Wasserstein distance or designing a parallel method for Wasserstein distance related problems [Ling and Okada, 2007; Li et al., 2017].

In this paper, we proposed a novel multi-level metric learning method using smoothed Wasserstein distance as a measure of errors between samples. To enhance the discriminability of model, we choose the ground distance as a Mahalanobis distance. Meanwhile, to take advantage of the crucial structured information that exist in data space, we learn a global smoothed Wasserstein distance through a shared distance matrix and local smoothed Wasserstein distance with additional auxiliary distance matrices, where the former reflects commonalities between various classification and the later captures classification-specific idiosyncrasies. Smoothed Wasserstein distance yields not only a distance value but also a optimal transformation plan. Thus, our method is more stable in characterizing the differences between two samples with noise than traditional Euclidean or Mahalanobis distance. We propose to jointly optimize the Mahalanobis distance matrix in the ground distance and the Wasserstein distance flow-network by using the alternative iterative strategy. The effectiveness of the proposed method is demonstrated by a series of computer vision tasks.

For a given vector a = (a1, a2, · · · , ad)⊤, diag(a) = A corresponds to a square diagonal matrix such that ∀i,Ai,i = ai. e represents a unit vector, and I is the unit matrix.

2 Multi-Level Metric Learning via Smoothed Wasserstein Distance

We start this section by revisiting the Smooth Wasserstein distance, and then propose our multi-level metric learning model.

2.1 SmoothedWasserstein Distance

Wasserstein distance is actually the optimal solution of transportation problem in linear programming. It can be viewed as a minimum amount of work required to move all the earth from the source to the destination [Sandler and Lindenbaum, 2011]. Given two signatures P = {(p1,wp1 ), (p2,wp2 ), · · · , (pm,wpm )} and Q =

{(q1,wq1 ), (q2,wq2 ), · · · , (qn,wqn ), the Wasserstein distance between them is defined as

where D = {d(i, j)}, i = 1, · · · ,m, j = 1, · · · , n is the ground distance matrix, and d(i, j) defines the cost of moving one unit of earth from the source pi to the target qj. F = {f(i, j)}, i = 1, · · · ,m, j = 1, · · · , n is a flow-network matrix, and f(i, j) denotes the amount of earth moved from the source pi to the target qj.

Optimizing Wasserstein distance problem is actually solving several costly optimal transport problems. Furthermore, the Wasserstein itself is not a smoothed function of its arguments because of a minimum of affine function, which limits the application of Wasserstein distance. To overcome the above problems, some researchers proposed to smooth the optimal transport problem with an entropic term [Cuturi, 2013]

where h is the (strictly concave) entropy function

and γ > 0 is a balance parameter. In this paper, we call Eq. (6) as smoothed Wasserstein distance.

2.2 NewMulti-Level Metric LearningModel Using Smoothed Wasserstein Distance

The ground distance in Eq. (6) is usually Euclidean, cosine or Sparse L1-norm distances. However, these distances can neither admit arbitrary linear scalings and rotations of the feature space nor exploit the discriminative information that exists in data space. Therefore, in this paper, we use the Mahalanobis distance as the ground measurement to improve the discriminative capability of Wγ. The squared Mahalanobis distance between the i-th bin of P and the j-th bin of Q can be expressed as

where M is a global linear transformation of the underlying space, and DM = {dM(i, j)} is the ground distance.

On the basis of Eq. (8), we can construct a Mahalanobis smoothed Wasserstein distance (Wγ,M for short). Let the smoothed Wasserstein distance between signatures P and Q be Wγ,M(P,Q) and the triplet be (P,Q, S) ∈ R. Then, replacing the Mahalanobis distance in Eq. (3) with Wγ,M, a novel LMNN model based on Wγ,M is obtained as follows

As we can see, model (9) only uses a global Wγ,M, thus it is hard to capture the local discriminative information of samples. To further improve the performance of (9), we model the commonalities between various classification through a shared Mahalanobis distance matrix M0 ⪰ 0 and the classification-specific idiosyncrasies with additional matrices M1,M2, · · ·,MC ⪰ 0 in the ground distance, where C denotes the number of classes in samples. As a result, we can rephrase Eq. (8) as

where t = 1, 2, · · ·, C.

Additionally, we can easily prove that each √dM,t(i, j) is indeed a pseudo-metric. Using Eq. (10) as the ground distance, problem (6) can be rewritten as

where DM,t = {dM,t(i, j)}, ∀i, j.

In modeling, we have to ensure that the learning algorithm does not put too much emphasis onto the shared parameters M0 or the individual parametersM1,M2, ···,MC. To ensure this balance, we use the regularization term stated below

where I is an identity matrix and the trade-off parameter ρt controls the regularization of Mt for all t = 0, 1, · · ·,C. Therefore, model (9) is further rewritten as

Different from the existing metric learning methods, which use a global Mahalanobis metric to measure the differences between samples, we use multiple smoothed Wasserstein distances to adaptively learn global and local structures of data space, which is helpful for practical multi-classification problems. However, solving problem (13) is very challenging since it needs to optimize multiple Wasserstein distance problems. This may lead to high computation complexity. In the next section, we will propose an efficient algorithm to solve model (13).

3 Optimization Algorithm

There are two groups of variables that need to be learned in model (13), i.e., flow-network F and matrices M0,M1, · · · ,MC. When flow-network F is fixed, model (13) turns into the Mahalanobis-like metric learning problem, i.e.,

Though the above problem is non-convex, we can compute its sub-gradient with

where t = 1, 2, · · ·, C.

Next, we can update each Mt(t = 0, 1, · · ·, C) using subgradient method, i.e.,

where PS+ (·) denotes the projection operator and τ > 0 is a step size. In our method, we set ρ0 = 1, and ρt = 1C , t = 1, · · · ,C. We can use the similar technique as in [Weinberger and Saul, 2009] to reduce the computation complexity of (16).

When Mt, t = 0, 1, · · ·,C are fixed, problem (13) can be splited into some independent traditional smoothed Wasserstein distance sub-problems, which can be solved by the method in [Rolet et al., 2016]. Here we omit the detailed process for solving smoothed Wasserstein distance subproblems. Algorithm 1 summarizes the main steps of the proposed method.

4 Experimental Results

In this section, to prove the effectiveness of the proposed method, we apply it to three kinds of computer vision applications, i.e., person re-identification, facial kinship verification and video classification.

4.1 Person Re-identification

During this part, we evaluate the proposed method on person re-identification task, which aims to match a given probe Algorithm 1 Optimization Algorithm for solving Problem (13)

• 1: Input: Training data set, and parameters kg, ki, ρ0, {ρt, t = 1, · · · ,C}, γ, λ and µ
• 2: Output: Global distance matrix M0 and local distance matricesMt, t = 1, · · · ,C
• 3: Initialize: Mt = I, t = 0, · · · ,C
• 4: Calculate the smoothed Wasserstein distance between each pair of signatures.
• 5: Construct the set S and R by selecting ki target neighbors and kg imposters for each training instance.
• 6: Initialize the learning rate α
• 7: repeat
• 8: FixMt, t = 0, · · · ,C, solve for the Wasserstein distance flow-network F.
• 9: Fix F.
• 10: repeat
• 11: Compute the gradient ∇Mt, t = 0, · · · ,C by Eq. (15).
• 12: UpdateMt, t = 0, · · · ,C by Eq. (16).
• 13: until Converge
• 14: until Converge

image against a collection of gallery images. We use two challenge person re-identification datasets at multi-shot scenario, i.e., PRID 2011 dataset [Hirzer et al., 2011] and iLIDSVID dataset [Office, 2008]. Some example pairs appeared in different camera views from these two datasets are shown in Fig. 2.

• PRID 2011 dataset - The PRID 2011 dataset includes 385 persons showed in camera view A and 749 persons in camera view B, with 200 persons of them appeared in both camera views [Hirzer et al., 2011].
• iLIDS-VID dataset - The iLIDS-VID dataset involves 300 different pedestrians observed across two disjoint camera views in public open space [Office, 2008].

Compared Methods: We compute Wasserstein distance, also called Earth Mover's Distance (EMD) directly as a baseline. Besides, we also compare the proposed method against four representative methods, including Pairwise Constrained Component Analysis (PCCA) [Mignon and Jurie, 2012], KISSME [Koestinger et al., 2012], Local Fisher Discriminant Analysis (LFDA) [Pedagadi et al., 2013] and Marginal Fisher Analysis (MFA) [Yan et al., 2007].

Experiment Settings: In the experiment, we split each dataset into two folds. In each time, one fold of data is for training and the other fold is used as testing data. We randomly generate five splits, and the average results are as final performance. Specifically, for PRID 2011 dataset, there are 200 person image pairs. Half of them are randomly selected for training and the rest are for testing. To evaluate the test set, we follow the same procedure described in [Hirzer et al., 2011], i.e., camera A is used as probe set and camera B is as gallery set. Thus, each of the 100 persons in the probe set is searched in a gallery set of 649 persons. For iLIDS-VID dataset, there are 300 person image pairs. All these pairs are randomly divided into two folds of the same size.

We focus on multi-shot scenario. 26960-d Local Maximal Occurrence (LOMO) feature is extracted for each frame of both datasets [Liao et al., 2015]. PCA is further applied to reduce the feature dimension to 100-d for our method and 65-d for KISSME method. In addition, to decrease the quantity of calculation of flows in our method, we cluster each sequence into several frames and use clustering centers to represent the corresponding sequence. For those only applicable to singleshot scenario methods, we average the centers as features. We choose linear kernel for MFA method.

Experiment Results: To measure the performance of person re-identification task, we report the widely used Cumulative Match Characteristic (CMC) performance curves averaged across the experiments in Fig. 3. It is obvious that our method always outperforms other compared methods, especially for PRID 2011 dataset. Because our method not only tries to learn a global distance matrix, but also takes advantage the local information. LFDA also achieves good performance because it does a better job at selecting the features with no need of PCA pre-processing step while making full use of the locally scaled affinity matrix. MFA obtains comparable results to LFDA. In contrast to LFDA, the advantage of MFA is its ability to maximize the marginal discriminant even when the assumption of a Gaussian distribution for each class is not true. With the increase of the rank value, LFDA and MFA catch up the proposed method. Simply use Wasserstein distance without metric learning couldn't take advantage of the prior knowledge in training data, thus performs worse in all compared methods.

In addition, we also report the Proportion of Uncertainty Removed (PUR) scores [Pedagadi et al., 2013]:

(a) PRID 2011

(b) iLIDS-VID

Figure 3: CMC curves for each method on two datasets: (a) PRID 2011 dataset; (b) iLIDS-VID dataset.

where N is the size of the gallery set, r is the rank. The rank of the correct match was recorded and accumulated to generate the match characteristic M(r). The PUR scores of two datasets along with the CMC values at rank = 1, 10, 20 are summarized in Table 1 and Table 2. The highest and second highest CMC and PUR scores in every experiment at every ranking were highlighted in red and blue, respectively. As shown in the table, the overall PUR score is higher for the PRID 2011 dataset, probably because the iLIDS-VID dataset is very challenging due to clothing similarities among people, cluttered background, viewpoint and lighting variations across camera views as shown in Fig. 2.

4.2 Facial Kinship Verification

In this section, we evaluate our methods on facial kinship verification task, which is to determine whether there is a kin relation between a pair of given face images. We use KinFaceW-II dataset, and some example pairs are shown in Fig. 4 [Lu et al., 2014].

• KinFaceW-II dataset - KinFaceW-II dataset consists of four representative types of kin relations: Mother-Son (M-S), Father-Son (F-S), Mother-Daughter (M-D) and Father-Daughter (F-D), respectively. Each relation contains 250 pairs of kinship images.

Compared Methods: We compute Euclidean and EMD distance between a pair of faces directly as a baseline. Also, traditional Mahalanobis distance between images of a pair is computed, where the metric matrix is inverse of covariance between two vectors. We compare the proposed methods against two representative metric learning methods, i.e., KISSME [Koestinger et al., 2012] and LDML [Guillaumin et al., 2009].

Experiment Settings: As a benchmark for comparison, we use the pre-specified training/testing split, which is generated for 5-fold cross validation [Lu et al., 2014]. We use the given Local Binary Patterns (LBP) and Histogram of Oriented Gradients (HOG) from image blocks. Each kind of feature is as one feature vector of a signature. For other methods, we simply concatenate these two features. PCA is further employed to reduce dimensionality of each vector to 100 dimension.

Experiment Results: To measure the kinship verification accuracy for all these compared methods, we report a Receiver Operator Characteristic (ROC) curve in Fig. 5. It seems that our method achieves best results on M-S and M-D relations. For other two relations, our method can get comparable results. Since it is difficult to distinguish which performs better, we compute Equal Error Rate (EER) of the respective method, and use 1 - EER as evaluation criterion, as shown in Fig. 5.

4.3 Video Classification

In this section, we evaluate our methods on video classification task, which is assigning an video to a predefined class. We use traffic video database. Several frames of different videos from the database are shown in Fig. 6.

• Traffic video database - Traffic video database consists of 254 video sequences of highway traffic in Seattle [Chan and Vasconcelos, 2005]. As in [Chan and Vasconcelos, 2005], each sequence was converted to grayscale, resized to 80 × 60 pixels, and then clipped to a 48 × 48 window over the area with the most total motion. For each frame, we use gray values as feature representation

Compared Methods: We compare our method with five widely used classification methods, including K-nearest Neighbor method (KNN) [Peterson, 2009], Support Vector Machine (SVM) [Fan et al., 2008], LMNN [Weinberger and Saul, 2009], and LMNN with capped trace norm [Huo et al., 2016] and Fantope norm [Law et al., 2014].

Experiment Settings: For our method, we simply use pixel intensities of each frame as feature vectors. Since each video sequence contains 42 to 52 frames, to reduce the amount of computation, we cluster every sequence into several frames. We treat each video as a signature, and the cluster centers are its feature vectors. The weights of each signature are determined by the proportion of samples in each cluster. For other methods, we follow the same procedure described in [Chan and Vasconcelos, 2005], i.e., for each video clip, the mean image is subtracted and the pixel intensities were normalized to have unit variance. For LMNN with capped trace norm and Fantope norm methods, the regularization parameters are tuned from range {10-4 , 10-3 , 10-2 , 10-1 , 1, 10, 102 }, and parameter rank of matrix M is from [30 : 5 : 70].

Experiment Results: We compute classification accuracy for each method as evaluation criterion. As shown in Fig. 7, KNN method using Euclidean distance works worst on this task. SVM method increases the performance of KNN method by about 2 ∼ 3%. When we use LMNN method with or without norm to learn Mahalanobis distance, we choose KNN classifier (K = 1). The proposed method does a better job than other compared methods in this task, which proves the effectiveness of using smoothed Wasserstein distance.

5 Conclusion

In this paper we proposed a novel multi-level metric learning algorithm. In our method, the errors between two samples are characterized using the smoothed Wasserstein distance. We consider the ground distance as a Mahalanobis distanc and automatically learn the corresponding matrices by the alternative iterative approach. To enhance the robustness of model, we further learn the global distance with regard to all samples and the local distance with regard to samples with specific class label. It is noteworthy that our method can be extended to other metric learning models. We verify the abilities of our method on several real-world datasets. The experimental results show that the proposed method consistently outperforms some related methods and obtains better classification results than traditional Mahalanobis metric learning approaches.

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China under Grants 61572388,

• 61703327, the National Key Research and Development Program of China (2017YFE0104100), and in part by the Key R&D Program-The Key Industry Innovation Chain of Shaanxi under Grant 2017ZDCXL-GY-05-04-02 and Grant 2017ZDCXL-GY-05-04-02.