Low-Rank Coding with b-Matching Constraint for Semi-Supervised Classification

1 Introduction

In many real world applications, unlabeled data (e.g. images, texts, and videos) are easier to obtain than labeled ones. For classification tasks, traditional unsupervised learning methods, such as principal component analysis (PCA) [Turk and Pentland, 1991], are unable to utilize the class label information, while supervised methods such as linear discriminant analysis (LDA) [Bellhumeur et al., 1997] do not use the unlabeled samples during training. For these reasons, semi-

∗This research is supported in part by the NSF CNS award 1135660 and 1314484, Office of Naval Research award N0001412-1-0125 and N00014-12-1-1028, Air Force Office of Scientific Research award FA9550-12-1-0201, and IC Postdoctoral Research Fellowship award 2011-11071400006.

Yun Fu

Department of ECE and College of CIS Northeastern University, Boston, MA, USA yunfu@ece.neu.edu

supervised learning (SSL) has attracted much attention in recent years, because SSL learns from both labeled and unlabeled samples [Zhu, 2010; Culp and Michailidis, 2008].

Among various SSL techniques, graph based SSL (GSSL) has been extensively studied and widely applied to many applications due to its inspiring performance on accuracy and speed [Chapelle et al., 2006; Kveton et al., 2010; Liu et al., 2012b]. Zhu et al. proposed to use the harmonic property of Gaussian random field over the graph for SSL [Zhu et al., 2003]. Zhou et al. performed SSL with the local and global consistency [Zhou et al., 2003]. He et al. developed a generative model for GSSL by estimating priors and conditional probabilities [He et al., 2007]. Cai et al. proposed a semisupervised discriminant analysis (SDA) method, which employs a graph based smoothness regularization term [Cai et al., 2007].

Although many GSSL methods have been proposed, limited research focuses on how to construct effective graphs [Wang and Xia, 2012]. k-nearest neighbor (k-NN) and ϵ-neighborhood are two popular graph construction schemes. However, neither methods generate graphs that are balanced, or regular, which hinders learning. b-matching method can solve this problem by learning a symmetric and balanced graph [Jebara et al., 2009]. Unfortunately, these resulting graphs are highly dependant on the similarity function, and are therefore sensitive to sample variation or noise.

To be effective, SSL methods should obey the smoothness, cluster or manifold assumptions [Chen and Wang, 2007]. However, when the samples contain noise or large variations, these assumptions are often violated, and therefore the traditional similarity metric (e.g., Gaussian function) often fails. Fortunately, recent research shows that sparsity and lowrankness could successfully recover signals in noise [Wright et al., 2009; Cand`es et al., 2011; Liu et al., 2010; 2013; Li et al., 2013]. Some graphs based on sparse representation [Yan and Wang, 2009; He et al., 2011] or low-rank representation [Zhuang et al., 2012] have been proposed for SSL. These graphs have shown promising performance in some applications. Nevertheless, there are still some limitations. First, the reason for using sparse or low-rank representation coefficients as graph weights is not very clear. Second, these graphs are unbalanced, which could seriously degrade the classification performance.

All these limitations in existing graphs motivate us to design a novel graph construction model, with robust similarity metric and balanced property. Recent advances on lowrank representation suggest that noisy data drawn from different subspaces can be correctly recovered by seeking the lowest-rank encoding matrix for all samples [Liu et al., 2010; 2013]. Inspired by this observation, we propose to measure the similarities between different samples in the lowrank encoding space, instead of original sample space. To generate a sparse and balanced graph, we also incorporate the b-matching constraint. Then we build a joint optimization framework to learn low-rank codes and balance the graph simultaneously. After using a straightforward graph reweighting strategy, we present a semi-supervised learning algorithm by incorporating our low-rank coding based balanced (LRCB) graph with Gaussian harmonic function (GHF). Experimental results on the Extended YaleB, PIE, ORL and USPS databases demonstrate that our graph outperforms several state-of-the-art graph algorithms, especially when there is very small set of labeled samples.

The rest of this paper is organized as follows. In Section 2, we briefly review related work. Then we describe the proposed graph construction method in Section 3, and present a GSSL algorithm in Section 4. Experiments are reported in Section 5 before concluding in Section 6.

2 RelatedWork

Constructing an effective graph is the most important component in GSSL. As we discussed above, there has been some research specifically that targeted graph construction. Given a sample set X with n samples, graph construction aims at building a weighted graph G. Typically, graph construction models consist of three procedures: similarity metric between each pair of samples, sparsification of the graph, and graph reweighting. Then we have the graph G = S ◦W, where S is a binary matrix whose elements indicate the edges in graph. W can be the similarity matrix or other user-defined weighting matrices, and ◦ is the Hadamard product.

In the first step, kernel function k(·) (e.g., Gaussian kernel) is usually used to estimate the similarity between samples. After constructing a similarity matrix, a simple and widelyused approach for sparsification and re-weighting is the k nearest neighborhood (k-NN) method [Maier et al., 2008]. It greedily selects k significant neighbors for each node to construct a k-NN graph. As shown in [Jebara et al., 2009], constructing k-NN graph is equivalent to the following optimization problem:

From the objective function (1), we can observe that k-NN method cannot produce a symmetric graph, and therefore it always requires a symmetrization process after obtaining S. However, the resulting k-NN graph is not balanced, which may lead to a performance degradation in SSL. To address this problem, Jebara et al. proposed a b-matching method to construct a balanced graph [Jebara et al., 2009]. They employ a b-matching constraint when constructing the graph, and therefore the degree of every node is exactly equal to the constant b. This method simultaneously ensures both symmetry and balance of the graph in learning procedures. However, the performance of k-NN graph and b-matching graph is highly dependent on the similarity metric. If the metric is sensitive to sample variation or noise, the performance would be greatly degraded.

Another class of graph construction methods focuses on weighting the graphs. Yan et al. proposed an l1 graph, which utilizes sparse representation coefficients as the weights on graph [Yan and Wang, 2009]. l1 graph is constructed in a parameter-free manner, since the adjacency structure and graph weights are determined by the l1 optimization algorithm automatically. Furthermore, He et al. presented a nonnegative sparse probability graph (SPG) to further improve the classification performance of SSL [He et al., 2011]. However, the reason for using sparse representation coefficients as graph weights is not quite clear. Especially when the labeled samples are very limited, sparse coefficients are very sensitive to the variation in labeled samples, and then the label propagation results would be affected negatively. In addition, both l1 graph and SPG graph are not balanced.

Recently, Zhuang et al. proposed a non-negative low-rank and sparse (NNLRS) graph for semi-supervised classification [Zhuang et al., 2012]. Their graph construction enforces low-rankness and sparsity simultaneously, and employs the low-rank representation coefficients as graph weights. There are several key differences between NNLRS and our approach. First, NNLRS directly utilizes low-rank representation coefficients as graph weights, our approach, on the other hand, employs low-rank coefficients of each pair of samples to calculate their similarity. Second, our approach jointly learns a sparse and balanced graph with b-matching constraint, while NNLRS graph is dense and unbalanced, which is undesired for semi-supervised classification in terms of accuracy and computational cost.

3 Low-Rank Coding based Balanced Graph Construction

Assumed that the sample set X contains a set of l labeled samples Xl and a set of u unlabeled samples Xu, X = [x1, · · · , xl , xl+1, · · · , xl+u] = [Xl,Xu], n = l + u (each column is a sample, xi ∈ Rd ). The aim of SSL is to infer the missing labels of Xu with the aid of labeled sample set Xl. In this section, we first present a robust similarity metric in the low-rank space. Furthermore, to learn a sparse and balanced graph, we build a joint optimization model to learn the similarity matrix and the balanced graph simultaneously.

3.1 ProblemFormulation

Many current similarity metrics, such as Gaussian function, are sensitive to noise or large intra-class variations. Inspired by the recent advances on low-rank representation based subspace recovery, we propose to estimate similarity in the lowrank code space to address this problem. Let Z denote the unknown coefficient matrix for sample set X, low-rank method learns a matrix Z which has the lowest rank(Z ) and satisfies the constraint X = AZ + E, where A is an over-complete dictionary and E is sparse noise component [Liu et al., 2013]. The i-th column vector in Z is the low-rank code vector for xi. Due to the fact that Z can correctly recover multiple subspaces and its low-rankness, the low-rank codes in Z belonging to one subspace (i.e., one class) should be highly correlated. Liu et al. also show that low-rank coefficients are very robust to different kinds of noises [Liu et al., 2013]. Thus, it's reasonable to employ low-rank codes in estimating the similarity between all pairs of samples.

To clearly illustrate our new similarity metric, Fig. 1 compares two similarity metrics of digits images in the original space and low-rank code space. It shows that, in case of large intra-class variation or large inter-class correlation, similarity values calculated in original space may not be reliable. However, the noise-insensitive low-rank codes can correctly recover the subspace structures of multiple classes, and lowrankness means that codes belonging to the same class should have high correlations. Thus, the similarity metric in lowrank space obtains better results as shown in Fig. 1.

Sparsity is another important requirement for effective GSSL, which helps improve the classification accuracy and computational performance of GSSL algorithms [Wang and Xia, 2012]. As discussed above, b-matching constraint is well-suited for this requirement. We propose to build a joint optimization model by learning both low-rank codes and balanced graph. The objective function of our model is:

where A is the dictionary with the size of n × a, L and R are two a×m and m×n matrices that are used to approximate Z, m << n, ‖.‖F is the Frobenius norm, E is a sparse noise ma-

are trade-off parameters to balance the effects of other terms, S is a binary balanced graph and b is the constraint on the degree.

In Eq. (2), the first two terms ‖Z - LR‖2F +λ1 ‖E‖2,1 represents the improved version of low-rank representation. Not only does it reduce the computational cost, but also addresses the small sample size problem [Liu et al., 2012a]. The last term n∑ i,j=1 Sij (Z T Z )ij and constraint n∑ j=1 Sij = b indicate

that each node should has a degree of b and meanwhile the total similarity value should be maximized.

Eq. (2) can be rewritten as:

(3)

where ◦ is the Hadamard product, i.e., (A ◦ B)ij = AijBij .

3.2 Optimization

The last term in Eq. (3), 1Tn (S ◦ (Z T Z ))1n, makes it difficult to solve the objective function. Fortunately, we can relax it to 1Tn (S ◦ (Z T J))1n with a new constraint J = Z. Then we can rewrite (3) as:

To solve Eq. (4), we introduce several Lagrange multipliers and obtain the augmented Lagrange function:

where Y1, Y2, Y3 and Y4 are Lagrange multipliers and μ > 0 is a penalty parameter.

Although this problem is not jointly convex for all variables, it is convex for each variable when others are fixed. This equation can now be solved using the inexact ALM algorithm [Lin et al., 2011]. In particular, we alternately update the variables L, R, Z, J, S and E in the k + 1 iteration as follows:

where Q is the QR decomposition on ZkRT k .

where Mk = 2Lk+1Rk+1 + AT Y1 - 1aY2 + λ2Sk ◦ Jk + Y3 + μk(AT X - AT Ek + 1a1Tn + Jk).

Eq.(10) can be solved by a fast b-matching algorithm that is recently proposed in [Huang and Jebara, 2011], and the solution to Eq.(11) is presented in [Liu et al., 2010]. The details of the algorithm is outlined in Algorithm 1. A similar analysis to show the convergence property of Algorithm 1 can be found in [Lin et al., 2011].

Algorithm 1. Solving Problem (5) by Inexact ALM

Input: data matrix X, dictionary A, parameter λ1, λ2,

L0 ∈ Ra×m, R0 ∈ Rm×n , Z0 ∈ Ra×n , J0 ∈ Ra×n ,

E0 ∈ Rd×n ,S0 ∈ Rn×n , Y1 ∈ Rd×n , Y2 ∈ R1×n ,

Output: Sk, Zk, Lk, Rk, Ek

1:while not converged do

• 2: update Lk+1 using (6), given others fixed
• 3: update Rk+1 using (7), given others fixed
• 4: update Zk+1 using (8), given others fixed
• 5: update Jk+1 using (9), given others fixed
• 6: update Sk+1 using (10), given others fixed
• 7: update Ek+1 using (11), given others fixed

8: update the multipliers Y1, Y2 and Y3

• 9: update the parameter μk+1 by μk+1 = min(ρμk, μmax)

10: check the convergence conditions

• 11: k = k + 1
• 12: end while

4 Graph Re-Weighting for Semi-supervised Classification

Given a sample set X = [Xl,Xu], we can learn a regular and binary graph S and low-rank representation coefficients Z using Algorithm 1. As we discussed above, Z T Z is a good choice for measuring the similarity between each pair of samples. Thus, we can also re-weight the graph S using Z T Z, and finally obtain a sparse, symmetric, weighted and balanced graph W , W = S ◦ (Z T Z ), which is named low-rank coding based balanced (LRCB) graph.

Our LRCB graph W can be easily combined with the representative label propagation method, Gaussian harmonic function (GHF) [Zhu et al., 2003]. We denote Y = [Yl, Yu], where Yl contains the probability vectors for the labeled samples and Yu for the unlabeled samples.

The predicted probability vectors can then be obtained for unlabeled samples by:Yu = -YlLluL-1 uu , (12)

where L is the Laplacian matrix, L = D - W, and D is the diagonal matrix whose diagonal elements are the sum of corresponding columns.

These steps are summarized in Algorithm 2. Same as [Liu et al., 2010; 2012a], we use sample matrix, X, as the dictionary. Besides GHF, our LRCB graph can also be combined with other label propagation schemes such as local and global consistency (LGC) [Zhou et al., 2003].

Algorithm 2. LRCB Graph for Semi-supervised Learning

Input: data matrix X = [Xl, Xu] = [x1, x2, . . . , xn], dictionary A = X, parameters λ1 and λ2

Output: Yu

1. Normalize all the samples xi to unit-norm, xi = xi/ ‖xi‖.
2. Solve problem (5) by using Algorithm 1 and obtain optimal solution S and Z.
3. Graph re-weighting: W = S ◦ (Z T Z ).
4. Calculate probability vectors Yu for unlabeled samples Xu using (12).

5 Experiments

In this section, we evaluate the performance of our graph and related graphs in graph based semi-supervised learning.

5.1 Databases and Settings

In our experiments four image databases are used: Extended YaleB [Georghiades et al., 2001], PIE [Sim et al., 2003], ORL [Samaria and Harter, 1994] and USPS [Hull, 1994].

Extended YaleB Face Database. This database has 38 subjects and around 64 images under different illuminations per subject. We use the images of the first 15 subjects, and we crop and resize each image to the size of 32 × 32 pixels.

PIE Face Database. The PIE face database consists of 41368 images of 68 subjects. Each subject is shown in different poses, illuminations and expressions. We use the first 15 subjects and five near front poses (C05, C07, C09, C27, C29), and all the different illuminations and expressions. Each images is cropped and resized to the size of 32 × 32 pixels.

ORL Face Database. The ORL face database contains 400 images of 40 individuals. These images were captured at different times, varying the lighting and facial expressions. We crop and resize each image to 32 × 32 pixels.

USPS Digit Database. The USPS digit database consists of 9298 handwritten digit images of 10 numbers (0-9). The size of each image is 16 × 16 pixels.

In the experiments, we compare the following graphs obtained by different construction methods:

1. k-NN graph. In this graph, two samples are connected if one is among the k nearest neighbors of the other. The kNN-graph is conducted in two configurations. In k-NN-I, the number of nearest neighbors is set to 5; and in k-NNII, this number is set to 8. We use the Gaussian kernel to re-weight the edges, and the parameter δ is adjusted to achieve the best performance on different databases.
2. b-matching (BM) graph. We follow the algorithms described in [Jebara et al., 2009], and construct a weighted and balanced graph. The parameter b is selected to achieve the best results.
3. l1 graph. We construct the l1 graph according to [Yan and Wang, 2009], and also symmetrize this graph.
4. Sparse probability graph. Following the algorithms in [He et al., 2011], we construct the non-negative sparse probability graph (SPG).
5. LRR graph. In accordance with [Liu et al., 2010], we construct the LRR graph and symmetrize it. We adopt the same parameters as described in [Liu et al., 2010].
6. NNLRS graph. We construct the non-negative sparse and low-rank graph according to [Zhuang et al., 2012]. We also symmetrize this graph. The parameters are set as described in [Zhuang et al., 2012].
7. Our LRCB graph. Two major parameters are λ1 and λ2. To choose proper values for them, we evaluate the parameter sensitivity of our graph. Fig. 2 shows the accuracies of our graph under different settings of λ1 and λ2, respectively. Here, λ1 is to handle the corruptions or large noise in the samples, while λ2 is used to balance low-rank approximation and b-matching constraint. Since the images in Extended YaleB database are captured in a relatively controlled environment, there's not much corruptions and our graph is not sensitive to λ1 over a wide range. Fig. 2 also shows that our graph achieves similar results when λ2 is varied from 0.01 to 0.04. On other three databases, we obtain similar results. Thus, for all the four databases, λ1 and λ2 are separately set as 2 and 0.03. Another parameter b is set as 5, 10, 5, 5 in the Extended YaleB, PIE, ORL and USPS databases, respectively.

5.2 Experimental Results

We first normalize all the images to be unit-norm as shown in Algorithm 2. We randomly select 50 images of every class in the PIE and YaleB databases, and 100 images from each class in the USPS database. We use all the images of ORL database. All experiments are repeated 10 times, and each time we randomly select a subset of images for each individual to create labeled sample set. Unlike most existing semisupervised learning experiments, we test the performance of all compared methods with only a small set of labeled samples, because the goal of semi-supervised learning is to deal with practical tasks that have very limited labeled samples but a large amount of unlabeled ones. For each individual, the percentage of labeled samples on the Extend YaleB, PIE and USPS databases is varied from 5% to 30%. Since there are only 10 images of each individual in ORL database, this percentage varies from 10% to 50%.

Table 1 shows the average accuracies of different graphs combined with GHF label propagation strategy on four databases, when the percentages of labeled samples are 10%, 20% and 30%. Fig. 3 shows the average accuracies versus varying percentages of labeled samples. We can observe from Table 1 and Fig. 3 that:

• (a) BM graph usually outperforms k-NN graph, since BM graph emphasises sparsity and balance at the same time;
• (b) The advanced sparse representation based graph, SPG, outperforms k-NN graph in many cases on the Extended YaleB and PIE databases, and achieves comparable performance as BM graph;
• (c) NNLRS graph, which is a low-rank and sparse graph, performs better than other existing graphs in most cases;
• (d) When the percentage of labeled samples is increased, the performance of all compared methods is increased. Our LRCB graph outperforms other compared graphs in almost all cases, and it reaches great performance very quickly. When the labeled samples are very limited, e.g., under 10% of total number of samples, our graph can significantly improve the accuracy over the state-of-the-art graphs on three face databases.

5.3 Discussions

To illustrate why our graph outperforms other compared graphs, Fig. 4 visualizes several weighted graphs including k-NN-graph, LRR graph, NNLRS graph and our graph on the PIE face database. We can observe from Fig. 4 that kNN graph is sparse, but it's not balanced. LRR produces a very dense graph that is undesirable for GSSL. NNLRS graph is a little sparser than LRR graph, however, why low-rank graph could directly represent the similarities between different samples is unclear. Also, both LRR and NNLRS graphs are not balanced. Fig. 4(d) shows that our graph is much sparser than the aforementioned three graphs. It correctly connects the samples within each class (diagonal blocks in the graph), and meanwhile the misconnections between samples in different classes are fewer than other graphs. These results validate the superiority of our low-rank encoding based similarity metric.

Another consideration is the computational cost of our approach. Although solving low-rank coefficient matrix in Algorithm 1 is very efficient, the b-matching optimization requires more computational cost than the basic k-NN graph. We will design more efficient implementations in future work. In addition, we simply use sample setX itself as dictionary in Algorithms 1 and 2. Learning informative dictionary is expected to further enhance the classification performance, which could be another direction in our future work.

6 Conclusions

In this paper, we propose a novel graph construction approach for semi-supervised learning. By taking advantages of lowrank encoding and b-matching constraint, we jointly learn a symmetric, sparse and balanced graph. GHF method is then used for semi-supervised classification. Experimental results on the Extended YaleB, PIE, ORL and USPS databases demonstrate the effectiveness of our approach compared with several state-of-the-art methods. Moreover, when the labeled samples are very limited (under 10% of total number of samples), our approach demonstrates significant improvement in classification performance.

Acknowledgments

The authors want to thank the anonymous reviewers for their helpful comments, and thank Dmitry Kit and Ming Shao for their suggestions to improve the paper.