Two dimensional Large Margin Nearest Neighbor for Matrix Classification

1 Introduction

Matrix data is a common form of data that appears in a wide range of real applications. Examples of the data in matrix form include the gray-level images [Kong et al., 2005; Yang et al., 2013; You et al., 2004; Lu et al., 2016a; Lu et al., 2016b] in computer vision, multichannel EEG signals in biomedical engineering [Tomioka et al., 2006], and so on. In the fields of pattern recognition and computer vision, matrix data classification has essentially become one of the most important topics.

Many classification techniques have been proposed in past decades. Among those classification methods, k-nearest neighbor classifier (KNN) is one of the most popular ones since it has following advantages: the non-linearity of decision boundaries leads to good recognition performance and the computational complexity is independent of the number of classes. In addition, KNN can be applied in scenarios where not all categories are given at the time of training, such as, in face verification applications where the subjects to be recognized are unknown in advance.

The classification accuracy of KNN depends significantly on the distance metric which is used for determining k nearest neighbors[Xiang et al., 2008; Song et al., 2017; Shakhnarovich et al., 2006; Weinberger et al., 2005]. Usually, Euclidean distance is adopted in many cases. This is logical when the statistics of data is unknown or when all dimensions of samples are equally relevant. However, those assumptions are too strict. In most cases, distance analysis along some special directions of the feature space is more informative. In those cases, performing distance metric learning algorithm on data set can improve the performance of KNN greatly.

Traditional distance metric learning methods are designed for dealing with vectors. When they are applied to process matrix data, the matrix data should be previously collapsed into vectors. Normally, this is done by cascading each column of a matrix one by one. However, the spatial correlations of matrix are lost inevitably in this procedure. Moreover, the dimensionality of resulting vector may be very high. In this scenarios, traditional metric learning algorithm maybe can not be carried out due to the overfitting and high computational complexity.

To handle those problems, one feasible way is to use matrix-based feature reduction algorithms to transform the matrix data to low-dimensional vectors, and then to learn a distance metric on the low-dimensional resulting feature space by implementing the vector-based metric learning method. However, the feature reduction may lost some discriminate information of the data set which is crucial for classification. And there is literature revealing that performance of combining feature reduction and metric learning together would be better than that of the two-step solution [Brockmeier et al., 2013; Parameswaran and Weinberger, 2010; Song et al., 2017]. In addition, the two-step solution may involve too much computational cost. Recently, many tensorbased methods for matrix classification are proposed [Chang et al., 2016; Hou et al., 2014; Zhang and Chow, 2012; Nie and Xianga, 2009]. Those literatures prove that matrixbased methods are more efficient than vector-based methods for dealing with matrix data. This inspires us to develop matrix-based metric learning method.

In this paper, we propose a novel metric learning algorithm named two dimensional large margin nearest neighbor (2DLMNN) which can deal with matrix data directly. The 2DLMNN can be seen as the matrix extension of one dimensional large margin nearest neighbor (1DLMNN). The key difference between 2DLMNN and 1DLMNN lies in the model for data presentation. 2DLMNN works with matrix data, while 1DLMNN works with vector data. In the proposed method, we define a new kind of Mahalanobis distance special for matrix data, by using two projection matrices. Then by applying the proposed matrix-based Mahalanobis distance to the principle of 1DLMNN, we obtain the model of matrixbased large margin nearest nearest neighbor (2DLMNN). In addition, we propose a framework for solving the 2DLMNN. Convergence and computational complexity are discussed. Last, Several experiments on various data sets are conducted. The promising experimental results demonstrate the efficiency of the proposed method.

2 RelatedWorks

2.1 One Dimensional Large Margin Nearest Neighbor

One dimensional large margin nearest neighbor (1DLMNN) was first proposed in literature [Weinberger et al., 2005] to learn the distance metric for improving the performance of KNN. Then in literature [Torresani and Lee, 2006], the algorithm of 1DLMNN was extended to learn the low rank projection matrix for feature reduction. In this paper, we consider both of the two tasks of 1DLMNN.

Given l labeled examples {(⃗xi, yi)}li=1 , where ⃗xi ∈ Rd and yi ∈ {1, 2, · · · , c} is the corresponding label, c is the class number. For an inquiry input ⃗ xi, we call its k-nearest neighbors which have the same labels with ⃗xi as "target neighbors", and the rest samples whose labels are different from yi in the dataset as "imposters". The goal of 1DLMNN is to learn a linear transformation L : Rd -→ Rd1 (d1 ≤ d), which can be used to define the Mahalanobis distance as:

where L is the projection matrix of linear transformation L, and M = LT L.

In the projection space determined by the projection L, each sample L⃗xi is closer to its target neighbors than the imposters by one distance unit, i.e. large margin. The relationship of ⃗ xi 's target neighbor ⃗xj and imposter ⃗xl can be expressed as linear inequality constraint with respect to the D(·, ·):

To achieve this goal, the loss function of 1DLMNN is defined as

where ηij = 1 if the example ⃗xj is one of the k target neighbors of ⃗xi, otherwise, ηij = 0. yil ∈ {0, 1} is 1 if and only if yi = yl, [z]+ = max(z, 0) denotes the standard hinge loss and λ is a positive constant playing the role in balancing the effect of the two terms in Eq.(3). The optimization problem for minimizing objective in Eq.(3) can be solved by standard semi-definite programming solver, or the sub-gradient descent method.

2.2 Two Dimensional Linear Discriminant Analysis

2DLDA is one of the most important two dimensional subspace learning methods. It can be seen as the two dimensional extension of the vector-based linear discriminant analysis (1DLDA). For a matrix data set {Xi}li=1 with c classes, 2DLDA aims at finding two projection matrices L and R, to project Xi to its low dimensional embedding, i.e. Y = LT XiR. Let Mj denote the j-th class, which has lj samples. So, Xj = (1/lj) ∑Xi∈Mj Xi is the mean of samples in the j-th class, and X = 1/l ∑ Xi is the mean of the whole training set. The between-class distance Db and within-class distance Dw in the original space are defined as follows.

Meanwhile, in the projection space, we can also define the within-class distance ˜Dw and between-class distance ˜Db.

Thus, the optimal transformation matrices L and R can be solved by maximizing ˜Dw and minimizing ˜Db, simultaneously. As it is difficult to derive the optimal L and R simultaneously, 2DLDA solves L and R in an alternative way. In each alternative step, L and R are calculated by performing eigen-decomposition, respectively.

3 Two Dimensional Large Margin Nearest Neighbor(2DLMNN)

3.1 Useful Conceptions

Before giving the formulation of 2DLMNN, several useful conceptions are introduced.

Definition 1: Suppose Rm×n is a matrix linear space, the inner product operation between two matrices Y, X ∈ Rm×n is defined as < X, Y >= Tr(XT Y ), where Tr(·) is the trace of matrix ·.

Definition 2: Given a matrix linear space Rm×n with inner product defined by Definition 1, the distance between X1, X2 ∈ Rm×n is defined as D(X1, X2) = √< X1 - X2, X1 - X2 >.

As 2DLDA, we consider the projection Y = U T XV , where U ∈ Rl1×m and V ∈ Rl2×n are projection matrices to project matrix X ∈ Rm×n from Rm×n to Rl1×l2 . In the projected space, the distance between X1 and X2 is presented as follows.

where M1 = UU T and M2 = V V T . When Eq.(6) is seen from original space, it is called the matrix-based Mahalanobis distance. When U and V are identity matrices, Eq.(6) is called as matrix-based Euclidean distance.

It is easily to find that the matrix-based Mahalanobis distance DU,V (X, Y ) subjected to following properties.

1. DU,V (X, Y ) = DU,V (Y, X);
2. DU,V (X, Y ) ≥ 0;
3. DU,V (X, Y ) + DU,V (Y, Z) ≥ DU,V (X, Z);

3.2 ProblemFormulation

Given a matrix data set {(Xi, yi)}ni , Xi ∈ Rm×n and yi ∈ {1, · · · , c} is the label of Xi. U ∈ Rm×l1 (l1 ≤ m) and V ∈ Rn×l2 (l2 ≤ n) are left projection matrix and right projection matrix, respectively. The optimization problem of 2DLMNN is defined as follows.

where ηij = 1 if example Xj is one of the k target neighbors of Xi, otherwise, ηij = 0. λ is a positive constant used to balance the two terms in the objective. yil ∈ {0, 1} is 1 if and only if yi = yl, and [s]+ = max(s, 0) is the hinge function. It should be noticed that, the "target neighbors" and the "imposters" of each Xi are determined under the matrix-based Euclidean distance in advance.

The objective of the optimization problem (7) consists of two contrasting terms. The first term aims at pushing each sample Xi apart from other points with labels different from yi by an amount equal to 1 plus the distance from Xi to any of its k similarly-labeled closest points in the projected space. The second term encourages pulling each example Xi and its k target neighbors determined in the original input space closer. The first term corresponds to a margin condition similar to that of SVMs and it is used to improve generalization. The constant λ controls the relative importance of these two competing terms and it can be chosen via cross validation.

Considering the projection Y = U T XV , each row of U can be seen as one coefficient vector of columns in matrix X, therefore, the left projection matrix U capturing the distance information in rows of X. Similarly, right projection matrix V can be seen as the coefficient matrix of columns in matrix X, and it captures the distance information of columns of X. Since in the projections, the places of elements in the matrix X are not changed, it means that the spatial correlations of elements in the matrix X is preserved.

Upon optimization of the problem, test example Xt is classified according to the KNN rule applied to its projection Xt = U T XtV , by using the matrix-based Euclidean distance.

3.3 Optimization

In this section, we give the framework for solving the proposed method. Since it is difficult to solve the two projection matrices U and V in the objective (7) simultaneously, we derive an iterative algorithm in the following. More specially, for a fixed V , we can compute the optimal U by solving an optimization problem similar to the model of 1DLMNN. With the computed V fixed, we then update U by solving another optimization problem also similar to 1DLMNN. This procedure is repeated with a certain number of times as discussed in Algorithm 1.

Computation of U

Let V ∈ Rn×l2 fixed, we denote Qi = XiV , i = 1, · · · , l. The matrix-based Mahalanobis distance between Xi and Xj is √Tr(U T (Qi -Qj)(Qi -Qj)T U). The formulation in Eq.(7) is rewritten as

where D2U (Qi,Qj) = Tr(M1(Qi - Qj)(Qi - Qj)T ), and M1 = UU T .

If the vector distance in Eq.(6) is transformed into matrix form as

, we can find that D2U (Qi, Qj ) and D2 ( ⃗ xi, ⃗ xj) share the same formula. That means the optimization problem in the Eq.(8) is same with the one in Eq.(3) in shape. Therefore the solution method of Eq.(3) can be applied to that of Eq.(8).

In Eq.(3), optimization problem of the parameter M can be solved as a standard semi-definite programming model [Weinberger and Saul, 2009]. In Eq.(8), when l1 = m, i.e., M1 is full rank, the optimization problem in Eq.(8) is a convex problem, and it can also be solved by the method of Eq.(3). However, in our method, we do not constrain the projection matrices U and V to be full rank, that is to say, M1 = UU T and M2 = V V T might be low rank. Since lowrank constraint problem is awkward to solve, in our paper, we adopt sub-gradient descend method [Torresani and Lee, 2006] to learn the low rank projection matrices.

Let Γ(U) denote the objective function in Eq.(8), the differentiating Γ(U) with resect to the projection matrix U T

gives the following gradient for the update rule:

where h(s) = max{s, 0}, and at s = 0. We let h′ (s) = 0 by adopting a smooth hinge function as in literature [Rennie and Srebro, 2005].

Computation of V

Similarly, when U ∈ Rm×l1 is fixed, we can change the formula of our optimization problem in Eq. (7), and derive its V by solving another model similar to 1DLMNN. More concretely, by denoting Ri = U T Xi, i = 1, · · · , l, Eq.(7) is transformed into Eq.(11).

where D2V (Ri, Rj ) = T r(V T (Ri-Rj )T (Ri-Rj )V ). Thus, the computation of V is transformed into solving another optimization problem similar to 1DLMNN. Eq.(11) is also solved by sub-gradient descent method.

It should be noticed that, when U and V are not full rank, the solution of Eq.(8) or solution of Eq.(11) is closely related to the initial searching point. To make the alternative method converge, the initial searching point of U or V should be selected as the result solved in previous iteration step. The details are described in Algorithm. 1.

3.4 Convergence Analysis

As mentioned above, the proposed method is solved in an alternative way. Namely, we fix one variable and compute the other. The following proposition shows the convergence of the proposed method.

Proposition 1: In Algorithm 1, we use {U (s) , V (s) } to denote the solution at the s-th iteration, the objective function of the optimization problem defined in Eq.(7) at{U (s) , V (s) } is Γ(U (s) , V (s) ). So Γ(U (s) , V (s) ) monotonically decreases with growth of iteration number s.

Proof: Since U (s) ,V (s) are the solution at the s-th iteration calculated by an alternative way. U (s) = argminU (Γ(U, V (s-1) )) with initial searching point U (s-1) . V (s) = argminV (Γ(U (s) , V )) with initial searching point V (s-1) . So there are Γ(U (s) , V (s-1) ) < Γ(U (s-1) , V (s-1) ) and Γ(U (s) , V (s) ) < Γ(U (s) , V (s-1) ). Therefore, Γ(U (s) , V (s) ) < Γ(U (s-1) , V (s-1) ).■

Since Γ(U (s) , V (s) ) > 0, the series Γ(U (s) , V (s) ) would converge to a constant with s increasing. It means Algorithm 1 converges.

Algorithm 1 2DLMNN

Input:

1. Matrix data Xi|, i = 1, 2, · · · , l}
2. Initial matrix V (0) ,U (0) ,
3. Parameter λ, l1 and l2, maximum iteration number smax Output:
4. Left projection matrix U,
5. Right projection matrix V

Processing:

Initialize V by V (0)

Repeat

1. Update U by U (i) : Calculate Qi = XiV (i-1) , i = 1, · · · , n,and U (i) by solving optimization problem in Eq.(8) by sub-gradient gradient descent method with initial searching point U (i-1) .
2. Update V by V (i) : Calculate Ri = U (i-1) T Xi, i = 1, · · · , n, and V (i) by solving optimization problem in (11) by sub-gradient gradient descent method with initial searching point V (i-1) .

Until Convergence or the maximum number of iterations smax is reached

Return U, V .

3.5 Computational Complexity

One of the motivations to develop the matrix-based method is to reduce the computational complexity. In this section, we consider the computation complexities of 1DLMNN and 2DLMNN. Since different methods would lead to different computational complexity, we suppose both of 2DLMNN and 1DLMNN are solved by sub-gradient descent method without using any accelerating technique. The majority of the computational complexity in sub-gradient descent method is to calculate the sub-gradient of the objective function. Let la denote the amount of the iterations in sub-gradient descent. Eq.(8) involves lal1nml2(m+ n)kl2 + lmnl2 times of multiplications. So for smax times upgrading U and V , 2DLMNN have 2smaxla(l1nml2(m+n)kl2 +l2mnl2) times multiplications. Since smax, k are far less than other parameters, l1 ≈ l2 and m ≈ n, the complexity of 2DLMNN is O(lal2 1 n3 l2 ). Similarly, we can find that the computational complexity of 1DLMNN is O(lad1m3n3 l2 ). Since l2 1 ≪ d1m3 , the computational complexity of 2DLMNN is much less than that 1DLMNN.

4 Experimental Results

We evaluate our proposed method in four different aspects. The first is about the convergence behavior. The second is the comparison of classification accuracy. The third is to explore the ability of feature reduction of 2DLMNN. The last is to compare the computational consumption of the proposed 2D method with 1DLMNN.

4.1 Dataset description

We utilize six typical image datasets to evaluate the performance of the proposed method. They are Extended YaleB database [Belhumeur et al., 1997], AR face database 1 , Coil-100 2 , USPS handwritten digital database 3 , UMIST face database 4 and POLLEN database 5 . The scale of these image databases ranges from 16 × 16 to 64 × 64, and the feature dimensions range from 256 to 4096. The details of those datasets are described in Table 1.

4.2 Convergence behavior

We select four datasets to demonstrate the convergence of the proposed iterative algorithm, they are POLLEN, UMIST, AR, Coil-100, respectively. In the experiments, we empirically set λ = 0.5 [Parameswaran and Weinberger, 2010; Weinberger and Saul, 2009] and initial points V (0) and U (0) are given by performing 2DPCA [Yang et al., 2004]. We conduct the experiments with different dimensions, and the function value results obtained from 1 to 25 iterations are recorded. The curves of objective function are presented in Figure 1.

As seen from Figure 1. the values of objective function described in Eq.(7) decrease with iterations on the four datasets and the convergence is reached within 10 iterations. It identifies the Proposition 1 in real data and the convergence of our proposed method.

4.3 Classification results

We consider the 2DLMNN not using feature reduction, i.e the projection matrices are square matrices. We compare it with several state-of-art one dimensional supervised distance metric learning methods, i.e. one dimensional large margin nearest neighbor algorithm (1DLMNN), one dimensional sparse compositional metric learning (1DSCML) [Shi and Sha, 2014], one dimensional local distance metric learning (1DLDML) [Yang and Sukthankar, 2006], one dimensional information theory metric learning (1DITML) and one dimensional regressive virtual metric learning (1DLRVML) [Perrot and A., 2015]. In additional, we also compare 2DLMNN with one dimensional support vector machine

1 http://www2.ece.ohio-state.edu/ aleix/ARdatabase.html

2 http://www1.cs.columbia.edu/CAVE/research/softlib/coil-

100.html.

3 http://www-i6.informatik.rwth-aachen.de/ keysers/usps.html

4 http://images.ee.umist.ac.uk/danny/database.html

5 http://ome.grc.nia.nih.gov/iicbu2008/pollen/index.html

(1DSVM) and two dimensional support vector machine classifier (2DSVM) [Hou et al., 2014]. The kernel of those SVM based classifiers are adopt as linear kernel, and the rank of 2DSVM is set as 4, empirically. For all metric learning algorithms, the classification are output by KNN. The parameter k in KNN is tuned in {1, 2, 3, 4} by cross-validation [Kohavi and others, 1995]. The parameters in 1DLMNN and 2DLMNN are tuned in grid {0.1, · · · , 0.9}. Each dataset listed in Tabel 1 is randomly divided into training set, validate set and testing set by ratio 2 : 1 : 1. Since our method convergence within 10 iterations, the iteration number of proposed method is set as 10. For each algorithm, the average results of 50 runs are recorded. The experimental results shown in Table 2 demonstrate the efficiency of the proposed matrix-based method.

4.4 Feature reduction results

In this section, we explore the performance of the proposed method for feature reduction. Since 2DLDA is the most famous supervised matrix-based feature reduction method. We compare the classification accuracy of 2DLMNN with 2DLDA under different dimensions. For 2DLDA, matrix data was projected into low-dimensional space, then we employ 1DLMNN to learn a full rank metric on the low-dimensional space. The results of both of 2DLDA and 2DLMNN are output by KNN. The datasets are divided into three parts as section 4.3. The parameter k in KNN are tuned in {1, 2, 3, 4} by five-fold cross-validation. The parameters 2DLMNN are tuned in grid {0.1, · · · , 0.9}. Since our method convergence within 10 iterations, the iteration number of proposed method is set as 10. The feature reduction results are shown as Figure 2.

4.5 Computational complexity

Another motivation for investigating matrix-based methods is reducing the computational complexity of 1DLMNN in manipulating vectorized high-dimensional data. In this section, we compare 2DLMNN with 1DLMNN on the six data sets which have different size and scales. Both of 2DLMNN and 1DLMNN learn full rank metrics. For justice, these methods are implemented in their original formulations, without using other accelerating strategies. And the algorithms are performed in Matlab on Intel(R) i5-6300HQ @ 2.30 HZ. The results are shown in Table 3. We can find that 2DLMNN runs much faster than 1DLMNN.

5 Conclusions

In this paper, we have proposed a novel two dimensional metric learning algorithm for learning matrix-based distance metric. Different from the traditional LMNN, our method solved a left projection matrix and a right projection matrix by an alternative way. The convergence behavior, classification accuracy, and computational complexity of the proposed algorithm were analyzed. At last, comprehensive experimental evaluations have been conducted to demonstrate the effectiveness of the proposed methods.

Acknowledgments

This work was supported in part by the National Science Foundation of China under Grants 61522207 and 61473231.