Learning a Distance Metric by Empirical Loss Minimization

1 Introduction

It is essential to choose a suitable metric for learning machines, e.g., k-means based clustering and nearest-neighbor based classification. A good metric helps to encode the geometry information of the instance distribution, and thus improves the performance of learning algorithms. In recent years, several metric learning algorithms have been proposed, e.g., neighbourhood component analysis [Goldberger et al., 2004], metric learning via large margin nearest neighbor [Weinberger et al., 2006], information-theoretic metric learning method [Davis et al., 2007], robust metric learning [Zha et al., 2009] and semisupervised metric learning [Baghshah and Shouraki, 2009]. They share a similar intrinsic idea that a good metric keeps the similar instances close and dissimilar ones apart, and show promising performances empirically. However,it is not easy to study their statistical properties, e.g., the consistency of the learned metric. Closely related to metric learning, several algorithms were developed for subspace learning [Bian and Tao, 2008; 2011], with various intuitions. Again, theoretical analyses are omitted.

In this paper, we propose a new metric learning framework, i.e., loss function based metric learning, in which the metric is estimated by minimizing an empirical risk over a training set. This framework enjoys one important advantage that the learned metric is consistent when the cardinality of the training set goes infinite. On the contrary, it is difficult to prove the consistency of existing metric learning algorithms and there is no results show that these algorithms are consistent. To prove the consistency of the loss function based metric learning, we first show that the empirical risk converges to its expected counterpart at rate O(1/√n), and then we show the learned metric that minimizes the empirical risk converges (at least equivalently) to the best metric that minimizes the expected risk, given the assumption that the best metric is bounded.

We then develop two example algorithms by using the proposed loss function based metric learning framework. The first one uses the log loss for calculating the empirical risk, while the second one is based on the hinge loss but in a smoothed form (to achieve the computational efficiency). In both algorithms, we show that their objective functions are convex and each has a Lipschitz gradient. Therefore, we can optimize both objective functions iteratively based on a fast gradient method, which has the optimal convergence rate at O(1/k2 ), wherein k is the number of iteration steps.

To evaluate the effectiveness of the proposed metric learning algorithms, we compare them against popular metric learning algorithms, e.g., NCA [Goldberger et al., 2004], LMNN [Weinberger et al., 2006], RCA [Shental et al., 2002], and [Xing et al., 2002]. On six data sets from the UCI machine learning repository [Asuncion and Newman, 2007], the nearest neighbor based classification shows that the proposed log loss and smoothed hinge loss based metric learning algorithms achieve competitive performance on all experiments.

2 Loss Function basedMetric Learning

We observe a set of independent and identically-distributed (i.i.d.) instances Z = { (xi, yi) | i = 1, 2, ..., n} that are drawn from an unknown joint distribution P (x, y), which is defined on X ×Y, wherein X is a measurable space and Y is a finite discrete set. Define similar and dissimilar sets

By defining a metric M, which is a positive semidefinite matrix, the distance between two instances xi and xi′ is given by

Metric learning finds a metric M that encodes the side information defined by instance pairs in S and D. In particular, we expect that the learned metric M makes distances between samples of pairs in S small and distances between samples of pairs in D large.

2.1 Empirical Risk

Introducing random variable r such that r = 1 if (x, x′ ) ∈ S and r = -1 if (x, x′ ) ∈ D, then we can use the following risk for metric learning

where the unknown distribution P (x, x′ , r) is defined on the space X 2 × {-1, 1} and f (x, x′ , r) is a decision function.

Given the training data sampled from a joint unknown distribution P (x, y), but not directly from P (x, x′ , r). It is necessary to consider P (x, x′ , r) being induced from P (x, y): to obtain a triplet (x, x′ , r) sampled from P (x, y), we first independently sample (x, y) and (x′ , y′), and then determine r by checking values of y and y′ . Thus, based on the training set Z, we can construct a corresponding set Z ′ for P (x, x′ , r), i.e., Z ′ = {(xi, xi′ , rii′ )| 1 ≤ i < i′ ≤ n}. It is worth emphasizing that Z ′ is not i.i.d. for P (x, x′ , r). For example, even two triplets (xi, xi′ , rii′ ) and (xj , xj′ , rjj′ ) can be dependent if any two indeces in a quadruple (i, i′ , j, j ′ ) are the same. This example shows that data directly sampled from P (x, x′ , r) are not i.i.d. either.

Therefore, given the empirical risk defined by

it is theoretically necessary to answer the following two questions: 1) does this empirical risk converge to the expected risk (2)? and 2) if so, how can we use this empirical risk to obtain a consistent estimation of a metric?

2.2 Metric Estimation

To estimate the metric by minimizing the empirical risk, it is necessary to specify the decision function f and the loss function ℓ. According to [Maurer, 2005], one possible choice of f is

where M is a metric and c is a positive variable denoting the decision threshold, i.e., we predict r = 1 if f > 0, or r = -1 otherwise. The choice of f implies an essential difference between metric learning and classification: the former predicts on an instance pair (x, x′ ) while the later predicts on a single instance x. Regarding the loss function ℓ, there are many choices, e.g., the log loss and the hinge loss. We develop two example algorithms in Section 4, and consider a general loss function for subsequent theoretical analyses.

By combining the decision function (4) and a general loss function ℓ, the best metric M ⋆ associated with the decision threshold c⋆ that minimizes the expected risk (2) are given by

Property 2.1. If the second order moment of the marginal distribution P (x) is finite, i.e., E‖x‖2 < ∞, then for any convex loss function ℓ(u) that is upper bounded by a0|u| + b0, (both a0 and b0 are positive constants), the expected risk Rℓ(f ) is convex and well defined on {M, c|M ⪰ 0, c ≥ 0}.

Proof. For any fixed (M, c), we have

Because x and x′ are independent, and E‖x‖2 < ∞, we have Rℓ(f ) = Eℓ(rf ) < ∞, i.e., it is well defined on {M, c|M ⪰ 0, c ≥ 0}. In additoin, f is linear in (M, c) and ℓ(u) is convex, so ℓ(rf ) is convex jointly on (M, c). Finally, since the expectation operation is linear, Rℓ(f ) = Eℓ(rf ) is also convex. This completes the proof.

The theoretical analyses in the rest of the paper are based on the following assumption.

Assumption 2.2. The best metric M ⋆ and the decision threshold c⋆ are bounded, i.e., 0 ⪯ M ⋆ ⪯ αI and 0 ≤ c ≤ α, wherein α is a sufficiently large positive constant.

This assumption is natural for metric learning, because a well-posed problem should have a bounded metric with a bounded decision threshold. Let Q = { (M, c) |0 ⪯ M ⋆ ⪯ αI , 0 ≤ c ≤ α}, and then the empirical estimation for (5) can be redefined by

Similar to the proof for Property 2.1., we can show that ˆRℓ(f, Z ′ ) is convex, and thus (7) has the global optimal solution. In the rest of the paper, we refer to (7) as the loss function based metric learning framework. According to Property 2.1., any loss function ℓ that satisfies the condition

can be used in this framework. Section 4 shows two examples based on the log loss and a smoothed hinge loss, respectively.

3 Consistency

In this section, we study the consistency of the proposed loss function based metric learning framework. We first prove that the empirical risk (3) converges to the expected risk (2) at rate O(1/√n) under Assumption 2.2, wherein n is the cardinality of the training set. We then prove that the metric ˆM learned by minimizing the empirical risk (3) is consistent.

3.1 Convergence of the Empirical Risk

According to discussions above, the empirical risk (3) is not an independent sum over the training set Z ′ . Thus, the proof for its convergence to the expected risk is nontrivial. In this subsection, we prove that the empirical risk ˆRℓ(f,Z ′ ) converges to Rℓ(f ) in probability at rate O(1/√n). First, we have the following theorem.

Theorem 3.1. Given the loss function ℓ that satisfies the condition (8), and the fourth order moment of the marginal distribution P (x) is finite, i.e., E‖x‖4 <∞, then

Proof. In the rest of the proof, we denote ℓ(rii′f (xi, x′i )) by ℓii′ .

First, since the expectation operation is linear, we have

Then, the second moment of the empirical risk is given by

Define three index sets, I0 = {(i, i′ , j, j ′ )|1 ≤ i < i′ ≤ n, 1 ≤ j < j ′ ≤ n, )}, I1 = {(i, i′ , j, j ′ )|(i, i′ , j, j ′ ) ∈ I0, and i, i′ , j, j ′ are different from each other}, and I2 = I0 - I1. It can be calculated that the cardinalities of I1 and I2 are n(n - 1)(n - 2)(n - 3)/4 and n(n - 1)(4n - 6)/4, respectively.

Next, we split the summation in (11) into two terms T1 and T2, i.e.,

For T1, the independence between ℓii′ and ℓjj′ leads to

where K1 = max(M,c)∈QRℓ(f ). The existence of K1 is guaranteed by the fact that Rℓ(f ) is convex and non-negative function and Q = { (M, c) |0 ⪯ M ⪯ αI, 0 ≤ c ≤ α} is a closed set.

According to (6), on Q = { (M, c) |0 ⪯ M ⪯ αI, 0 ≤ c ≤ α}, we have

Furthermore, since E‖x‖4 < ∞, E(ℓ2 ) can then be upper bounded by a sufficiently large constant K2,

Thus, we have

Combining (10), (14) and (17), we have

Since K1 and K2 are constants and do not depend on (M, c), we have (9). This completes the proof.

By Chebyshev's inequality, (9) immediately gives the following Corollary.

Corollary 3.2. The empirical risk converges to the expected risk at rate root-n, i.e.,

3.2 Consistency of the LearnedMetric

We have proved that for any function f specified by (M, c), the empirical risk (3) converges to the expected risk (2). Next, the following proof for Theorem 3.3 shows that the learned distance metric ˆM by minimizing the empirical risk converges to the best distance metric M ⋆ that minimizes the expected risk.

Theorem 3.3. Given the conditions in Theorem 3.1, the learned ( ˆM , ˆ c) by minimizing the empirical risk (7) is consistent, i.e.,

Proof. According to (7), ( ˆM , ˆ c) minimizes the empirical risk ˆRℓ(f,R), and thus we have

Similarly, (M ⋆ , c⋆ ) minimizes the expected risk Rℓ(f ), and thus it gives

Combining (21) and (22), we have

Therefore,E[Rℓ(

By (9) and Chebyshev's inequality, we have

When Rℓ(M, c) is strongly convex, (25) implies (20). When Rℓ(M, c) is weakly convex, (M ⋆ , c⋆ ) is an equivalent solution set, and thus (25) implies that ( ˆM , ˆ c) converges to this equivalent solutions set. This completes the proof.

4 Example Algorithms

We develop two example algorithms by using the proposed loss function based metric learning framework. They use the log loss and a smoothed hinge loss [Rennie, 2005], respectively. For each example, we show that its empirical risk has a Lipschitz gradient, and thus can be optimized by using a fast algorithm with the optimal convergence rate at O(1/k2 ), wherein k is the number of iteration steps.

To simplify formulations in following subsections, we introduce a block-diagonal matrix X = diag(M, c), and thus the decision function can be rewritten as

where 〈A, B〉 = tr(AT B) and

Furthermore, the training set Z ′ = {(xi, xi′ , rii′ )| 1 ≤ i < i′ ≤ n} contains m = n(n - 1)/2 triplets. For convenience, we replace the paired index (i, i′ ) with a single index j, and thus Z ′ = {(xj, x′j , rj)| 1 ≤ j ≤ m}. Each rj is associated with a block-diagonal matrix Aj = diag (-(xj - x′j )(xj - x′j )T , 1).

4.1 The Log Loss based Example

In this example, we use the log loss function

which has a gradient |∇ℓ(u)| ≤ 1 and satisfies the condition (8), i.e., ℓ(u) < |u| + 1.

We replace the loss function in (7) with (28), and then the empirical risk can be rewritten as

According to Property 4.1 shown below, we know that ˆR(X ) in (29) has a Lipschitz gradient with the parameter L = (1/4m) ∑mj=1 ‖Aj‖2F .

Property 4.1. For any directionΔ ∈ S (p+1)×(p+1) , where p is the dimension of an instance x, we have

Proof. First, the gradient of ˆR(X ) is given by

Define function φ(ϵ) = 〈∇ ˆR(X + ϵΔ), Δ〉 with ϵ > 0, and then we have

Therefore,

This completes the proof.

The log loss based empirical risk ˆR(X ) is convex and has a Lipschitz gradient, so we can obtain the optimal solution of (29) by using the improved first-order method [Nesterov, 2004]. It has been proved that this method achieves the optimal convergence rate at O(1/k2 ), wherein k is the number of iteration steps. Below, we show the optimization procedure for each iteration step in three stages.

Stage 1 We solve a standard first-order problem defined by

which utilizes the gradient of the solution Xk = diag(Mk, ck) at the current iteration step. Note that ∇ ˆR(Xk) can be calculated by using (31) and it is block-diagonal. The problem (34) is equivalent to

where Y 1 k is block-diagonal and it is given by

According to (35), we have 1) the two diagonal blocks M and c in X are not coupled, so M 1 k and c1k in X 1 k can be obtained independently; and 2) it is invariant to rotation, so it can be reduced to an optimization on a diagonal matrix by rotating it to the eigen-space of Y 1 k . This equivalent problem is easy to deal with. We show the solution directly and omit details. To obtain M 1 k , we conduct eigen-decomposition on the first block of Y 1 k and then we have

According to the constraint 0 ⪯ M ⪯ αI in Q, we have

where I = { i |0 ≤ λi ≤ α}. For c1k , since 0 ≤ c ≤ α, we have

Stage 2 We solve another minimization that combines all the gradients in the previous iterations and makes use of a proxfunction pp(X ) for the primal feasible set Q

where the weighting parameter αi = (i + 1)/2 according to [Nesterov, 2004] and pp(X ) is required to be strongly convex with the parameter σp. We choose the prox-function as

which vanishes at X0 = O and has the convexity parameter σp = 2. Similar to the method used to solve (34), we can get X 2 k = diag(M 2 k , c2k ) by

where I = { i |0 ≤ σi ≤ α} and {σi, ζi} are the corresponding eigenvalues and eigenvectors of

and

Stage 3 Xk+1 = diag(Mk+1, ck+1) for the next iteration step is given by the weighted combination

where it is suggested that τk = (k + 1)/(k + 3) [Nesterov, 2004]. Algorithm 1 summarizes the above procedure.

4.2 The Smoothed Hinge Loss Case

In the second example, we utilize the smoothed hinge loss (Rennie 2005), which is defined by

Its gradient is given by

Algorithm 1 Loss function based metric learning

Input: The training set Z ′ = {(xj , x′j , rj )|1 ≤ j ≤ m} Output: The metric M and decision threshold c For k = 0, 1, 2, ...

• Compute ˆR(Xk) by (28) for log loss, or by (48) for the smoothed hinge loss
• Compute ∇ ˆR(Xk) by (31) for the log loss, or by (49) for the smoothed hinge loss
• Update X 1 k = diag(M 1 k , c1k ) by (38) and (39)

The smoothed hinge loss satisfies the condition (8) by |ℓ(u)| ≤ |u| + 0.5. With the smoothed hinge loss, the empirical risk is given by

and its gradient is

The following property shows that the empirical risk (48) has a Lipschitz gradient (the proof is similar to the one for Property 4.1).

Property 4.2. For any directionΔ ∈ S (p+1)×(p+1) , where p is the dimension of the instance x, we have

Since (48) has a Lipschitz gradient with L = (1/m) ∑mj=1 ‖Aj‖2F , we can solve it by using the same iterative procedure and Algorithm 1 as for the log loss case.

5 Experiments

In this section, we evaluate the effectiveness of the proposed example algorithms, i.e., the log loss based metric learning algorism (LLML) and the smoothed hinge loss based metric learning algorithm (sHLML), by comparing them against three popular metric learning algorithms, i.e., the distance metric learning method (DML) proposed in [Xing et al., 2002], neighborhood component analysis [Goldberger et al., 2004] (NCA), and large margin nearest neighbor method [Weinberger et al., 2006] (LMNN). We only consider the fully supervised learning case, in which all labels of the instances in training set are known, and thus we have the similarity or dissimilarity information of all instance pairs from the training set. However, it is worth emphasizing that the proposed example algorithms can readily deal with the case that only side information [Xing et al., 2002] on the training set is known, LLML

sHLML

DML

NCA

LMNN

LLML

sHLML

DML

NCA

LMNN

Figure 1: Performance evaluation on data sets from the UCI machine learning repository. Each method is represented by a box with whiskers. The box has lines at the lower quartile, median, and upper quartile values of the classification error rates on twenty independent experiments, and the error rate outside 1.5 times of the interquartile range from the ends of the box is regarded as whisker.

i.e., the labels of the instances in the training set are unknown but only the similarity and the dissimilarity information between (not necessarily all) instance pairs is known. Six data sets from the UCI Machine Learning Repository [Asuncion and Newman, 2007] are used in our experiments, including "BalanceScale","Flare","Glass","Iris","Soybean" and "Wine". On each data set, we randomly select 20 percents data as the training set and use the rest as the test set. A metric is learned by using different algorithms from the training data, and then the nearest neighbour classification with the learned metric is conducted on the test data. Twenty independent experiments on each data set are conducted, and the classification error rate of different metric learning algorithms are shown in Figure 1 by using the boxplot. From the results, one can see that the proposed loss function based algorithms have competitive performances on all six data set. In particular, significant improvements are achieved on the "BalanceScale", "Soybean", and "Wine" data sets.

6 Conclusion

In this paper, we have proposed the loss function based metric learning framework, in which the metric is estimated by minimizing an empirical risk. We proved that under natural assumptions on the instance distribution and the used loss function, the learned metric is consistent. Based on this framework, we have developed two example algorithms, which are based on the log loss and a smoothed hinge loss, respectively.

Since the empirical risk of each algorithm has a Lipschitz gradient, they can be optimized with the optimal convergence rate. Sufficient experimental results on the data sets from UCI machine learning repository confirmed their effectiveness compared against popular metric learning algorithms.

Acknowledgments

This work was supported in part by Australian Research Council Future Fellowship (Grant No. FT100100971), Australian Research Council (ARC) Discovery Project DP1093762 and Discovery Project DP0988016.