A Self-Representation Induced Classifier

1 Introduction

Nearest neighbor classifier (NNC) has been widely used in machine learning and pattern recognition tasks such as face recognition [Turk and Pentland, 1991], handwritten digit recognition [Lee, 1991], and image classification [Boiman et al., 2008], etc. NNC measures the distance/similarity between the query sample and each of the training samples independently, and assigns the label of the nearest sample to the query sample. If the training samples are distributed densely enough, the classification error of NNC is bounded by twice the classification error of Bayesian classifier. NNC

⇤Corresponding author

does not need the prior knowledge of sample distribution and it is parameter-free. However, NNC ignores the relationship between training samples [Vincent and Bengio, 2001], and often fails for high-dimensional pattern recognition tasks because of the curse of dimensionality [Bach, 2014]. Besides, all training samples should be stored in NNC and it becomes time-consuming in large scale problems [Muja and Lowe, 2014].

To reduce the computation burden of NNC and dilute the curse of dimensionality, nearest subspace classifier (NSC) was proposed. NSC measures the distance from the query sample to the subspace of each class and then classifies the query sample to its nearest subspace. The subspaces are often used to describe the appearance of objects under different lighting [Basri and Jacobs, 2003], viewpoint [Ullman and Basri, 1991], articulation [Torresani et al., 2001], and identity [Blanz and Vetter, 2003]. Each class can be modeled as a linear subspace [Chien and Wu, 2002], affine hull (AH) [Vincent and Bengio, 2001] or convex hull (CH) [Vincent and Bengio, 2001], hyperdisk [Cevikalp et al., 2008] or variable smooth manifold [Liu et al., 2011]. When one class is considered as a linear subspace, NSC actually represents a query sample by a linear combination of the samples in that class. In such a case, a set of projection matrices can be calculated offline, and thus NSC avoids the one-to-one searching process in NNC, reducing largely the time cost. Some approximate nearest subspace algorithms have also been proposed to further accelerate the searching process [Basri et al., 2011]. Whereas, NSC only considers the information of one class when calculating the distance from the query sample to this class, and it ignores the information of other classes.

As a significant extension to NSC, the sparse representation based classifier (SRC) [Wright et al., 2009] exploits the information from all classes of training samples when representing the given query sample, and it has shown promising classification performance [Wright et al., 2009]. Specifically, SRC represents the query sample as a linear combination of all training samples with l1-norm sparsity constraint imposed on the representation coefficients, and then it classifies the query sample to the class with the minimal representation error [Wright et al., 2009]. In spite of the promising classification accuracy, SRC has to solve an l1-norm minimization problem for each query sample, which is very costly. It has been shown in [Zhang et al., 2011] that the collaborative representation mechanism (i.e., using samples from all classes to collaboratively represent the query image) plays a more important role in the success of SRC. By using l2-norm to regularize the representation coefficients, the so-called collaborative representation based classification (CRC) demonstrates similar classification rates to SRC [Wright et al., 2009]. CRC has a closed-form solution to representing the query sample, and therefore has much lower computational cost than SRC.

Inspired by SRC and CRC, in [Chi and Porikli, 2014] a collaborative representation optimized classifier (CROC) is proposed to pursue a balance between NSC and CRC. In [Yang et al., 2011], feature weights are introduced to the representation model to penalize pixels with large error so that the model is robust to outliers. A kernel sparse representation model is proposed by mapping features to a high dimensional reproducing kernel Hilbert space [Gao et al., 2013]. In [Zhang et al., 2015], a sparse representation classifier with manifold constraints transfer is proposed to add manifold priors to SRC. Different variants of sparse representation models are developed for face recognition with single sample per person as well [Gao et al., 2014]. In addition, dictionary learning methods have been proposed to learn discriminative dictionaries for representation based classifiers [Liu et al., 2014; Harandi and Salzmann, 2015; Quan et al., 2015].

Most of the current representation based classifiers, including NSC, SRC and CRC, are sample oriented, and they represent a query sample as a combination of training samples. The time and memory complexity of such a "sample oriented" representation strategy, however, will increase rapidly with the number of training samples. For instance, in the training stage the time complexities of NSC and CRC are O(Kn3 ) and O((Kn)3 ), respectively, where K is the number of classes and n is the number of samples per class. Clearly, the complexity is polynomial w.r.t. the training sample number. In the testing stage, the memory complexities of NSC and CRC are both O(dKn), where d is the feature dimension. It is linear to the number of training sample and can be very costly for large scale pattern classification problems, where there are many classes and a lot of samples per class.

Different from those previous representation based classifiers, in this paper we investigate the representation based classification problem from a "feature oriented" perspective. Instead of representing a sample as the linear combination of other samples, we propose to learn how each feature (i.e., each element) of a sample can be represented by the features of itself. Such a self-representation property of features generally holds for most high dimensional data, and has been applied in machine learning and computer vision fields [Xu et al., 2015]. For example, in [Mitra et al., 2002] this property is used to select the representative features by feature clustering. In [Zhu et al., 2015], a regularized self-representation model is proposed for unsupervised feature selection.

Motivated by the self-representation property of sample features, we propose a novel self-representation induced classifier (SRIC), which learns a self-representation matrix for each class by its training data. To classify a query sample, we project it onto the learned self-representation matrix and compute its feature self-representation residual. The query sample is then classified to the class which has minimal feature self-representation residual. SRIC learns the selfrepresentation matrix individually for each class. In light of the principle of SRIC, we then present a discriminative SRIC (DSRIC) approach. Using all training data, for each class a discriminative self-representation matrix is trained to minimize the feature self-representation residual of this class while representing little the features of other classes. The classification of a query still depends on which class has the minimal feature self-representation residual. DSRIC is intuitive and easy to understand. The main contribution of this paper is summarized as follows

• ÷ We propose two novel feature-oriented representation classifiers, i.e., self-representation induced classifier (SRIC) and discriminative SRIC (DSRIC). The training and testing time complexity of SRIC and DSRIC is irrelevant to the number of samples.
• ÷ We prove that SRIC is equivalent to NSC with l2-norm regularization in terms of the final classification decision. Furthermore, we also prove that SRIC is essentially the principal component analysis (PCA) with eigenvalue shrinkage.
• ÷ Extensive experiments show that DSRIC has comparable or superior recognition rate to state-of-the-art representation based classifiers such as SRC and CRC; however, our theoretical complexity analysis and experimental results will show that DSRIC is much more efficient and needs much less storage space than other representation based classifiers.

2 Self-representation for classification

2.1 Nearest subspace classifier

Suppose that we have a set of training samples from K classes X = [X1↪ ▷▷▷↪Xk↪ ▷▷▷↪XK], where Xk = [x1k↪ ▷▷▷↪ xik↪ ▷▷▷↪ xnk] 2 Rd⇥n , is the sample subset of class k and xik is the ith sample of it, d is the feature dimension and n is the number of training samples in each class. Given a query sample z, the nearest subspace classifier (NSC) represents it by the samples of class k as:

where ak is the representation vector and ek is the representation residual vector.

To get an optimal representation of z, NSC minimizes the representation residual by solving the following least square problem:

The problem in Eq. (2) has a closed-from solution ˆak = (XTk Xk)-1XTk z if (XTk Xk)-1 is non-singular. In practice, an l2-norm regularization can be imposed on ak to make (XTk Xk)-1 more stable, resulting in an l2-norm regularized least regression problem:

The analytical solution to Eq. (3) is ˆak = (XTk Xk +λI)-1XTk z, where I is an identity matrix. Then the representation residual can be computed as rk = ∥∥∥z-Xk(XTk Xk +λI)-1XTi z∥∥∥2 2 . NSC classifies z to the class with the minimal representation residual. Let

The classification rule of NSC can be written as

Clearly, NSC learns a set of symmetric matrices Wk 2 <d⇥d to reconstruct the query sample for classification.

2.2 Self-representation induced classifier

Representation based classifiers such as NSC, SRC and CRC rely on the similarity between samples. They assume that a query sample can be well represented by a linear combination of the training samples. Here we consider the representation based classification problem from a very different viewpoint. Considering the fact that the features of a sample are correlated (especially for visual data), we propose to represent each feature of a sample as the linear combination of all the features of this sample. Finally, the sample is represented by itself. Actually, such a self-representation strategy has been used successfully in image processing and feature selection [Xu et al., 2015]. For example, in image denoising a pixel (i.e., a feature) is represented as the weighted average of its neighboring pixels. In [Zhu et al., 2015], feature similarity is defined and then representative features are selected by feature clustering.

Based on the above analysis, we present a selfrepresentation based classification scheme. We can write the training subset of class k as Xk = [fk1; ▷▷▷; fkj ; ▷▷▷; fkd] where fkj is the j th feature vector of Xk. We represent fkj as a linear combination of all the feature vectors:

where bj1↪ ▷▷▷↪ bjd are the representation coefficients and ejk is the representation residual vector. Let bj = [bj1↪ ▷▷▷↪ bjd]. Then Eq. (6) can be rewritten as fkj = bjXk. For all the feature vectors in Xk, they can be represented by Xk with Eq. (6). Let Bk = [b1; b2; ▷▷▷; bd] and Ek = [e1; e2; ▷▷▷; ed]. The representation of all features can be written as:

We call the feature based representation model in Eq. (7) selfrepresentation because it utilizes Xk to represent itself. To minimize the self-representation residual while avoiding the trivial solution, we have the following optimization problem:

where l(Ek) is the loss function and R(Bk) is the regularization item. If we choose square loss and F-norm regularization, the problem in Eq. (8) becomes:

Apparently, the problem in Eq. (9) has a closed-form solution:

2

3

4

5

6

7

8

9

Figure 1: Top row: self-representation matrices Bk↪ k = 0↪ 1↪ ▷▷▷↪ 9 learned from the USPS database. Bottom row: a query sample (from class 0) and its reconstructed images Bkz↪ k = 0↪ 1↪ ▷▷▷↪ 9.

where I 2 <d⇥d is an identity matrix. Given a query sample z, its self-representation can then be computed as ˆ Bkz and the self-representation residual is e = z - ˆ Bkz.

For each class, we can learn its self-representation matrix as above, and then we have a set of K self-representation matrices, B1↪ ▷▷▷↪Bk↪ ▷▷▷↪BK (we omit the superscript " ˆ " for the convenience of expression). The query sample z can be represented by each of the matrices and the classification can be made by checking which class has the minimal selfrepresentation residual:

We call the above classifier self-representation induced classifier (SRIC).

We use an example to illustrate how SRIC works. As shown in Fig. 1, 10 self-representation matrices Bk↪ i = 0↪ 1↪ ▷▷▷↪ 9, are learned from handwritten digit dataset USPS [Hull, 1994]. Certainly, matrix Bk tends to represent better the features of sample from class k. Fig. 1 also shows a query sample z (from class 0) and the reconstructed samples Bkz by all Bk. We can see that z is well represented by B0 and it has the minimal self-representation residual on class 0, resulting in a correct classification.

2.3 Equivalence between SRIC and NSC

The NSC represents a sample from the perspective of sample similarity, while the proposed SRIC represents a sample from the perspective of feature similarity. Though the representation strategies are different, interestingly, it can be proved that they lead to the same classification result. We have the following theorem.

Theorem 1 SRIC is equivalent to l2-norm regularized nearest subspace classifier, i.e., Bk=Wk, k = 1↪ 2↪ ▷▷▷↪K.

Proof 1 Applying singular value decomposition to Xk, Xk = Uk⇤kVT k , where Uk 2 <d⇥d , ⇤k 2 <d⇥n and Vk 2 <n⇥n . Then Bk andWk becomes:

If d < n, we let ⇤k = [Hk 0], where Hk 2 <d⇥d . Then we have

Because Hk is a diagonal matrix, we have ⇤b = ⇤w. As Wk = Uk⇤wUTk and Bk = Uk⇤bUTk , we can get Bk =Wk.

have the same conclusion, i.e., ⇤b = ⇤w and Bk =Wk. If d = n, let ⇤k = Hk, ⇤b and ⇤w are the same as those ⇤b

and ⇤w when d < n. Hence, Bk = Wk also holds on when d = n.

From the above proof, we can have the following remark.

Remark 1 SRIC is equivalent to principal component analysis with shrinkage.

From the Proof, we can see that, Xk and Bk have the same set of eigenvectors, i.e., Uk. Denote the hth eigenvalue of Xk as σh, then the hth eigenvalue ⇤bh of Bk will be σ2h λ+σ2h . Therefore, for SIRC the eigenvalues of Bk will be shrunk to the range [0 1). The smaller the eigenvalue, the less the shrinkage ratio.

3 Discriminative self-representation induced classifier

3.1 Discriminative self-representation

The learning of self-representation matrix Bk in SRIC is rather generative but not discriminative since it only depends on the training data of class k. In light of the principle of self-representation in SRIC, we can then propose a discriminative self-representation induced classifier (DSRIC), which exploits the training data from all classes to learn Bk.

SRIC aims to learn a Bk such that the self-representation residual kXk -BkXkk2F could be minimized. However, SRIC does not take the samples of other classes into account. In order to make the classification more discriminative, we also expect that Bk cannot well represent the features of other classes. One may consider to maximize kXj -BkXjk2F , j 6= k while minimizing kXk -BkXkk2F . However, this will make the whole objective function non-convex. Another much easier but still very reasonable choice is to learn a Bk such that the self-representation of Xj , j 6= k, over it will approach to zero, i.e., kBkXjk2F is very small. In other words, Bk is discriminative to represent the features of class k but not other classes. With these considerations, we propose the following DSRICmodel to learn Bk:

where λ1 and λ2 are the regularization parameters.

In Eq. (12), the first term kXk -BkXkk2F aims to minimize the self-representation residual; the second term Pj6=k kBkXjk2F enforces that Xj↪ j 6= k will not be well represented by Bk; the last term regularizes Bk to make the solution more stable. It is apparent that we still have a closed form solution of Bk:

As shown in Fig. 2, we use a subset of AR database [Martinez, 1998] to show the difference between SRIC and DSRIC. Fig. 2(a) shows the query sample that belongs to subject 10. In Fig. 2(b), the query face z is well reconstructed by B10 learned by SRIC. However, from Fig. 2(d), we can see that z is misclassified to subject 15. The reconstructed faces using DSRIC are shown in Fig. 2(c). From Fig. 2(e), we can see that z is correctly classified to subject 10. Though the reconstruction ability of SRIC is superior to DSRIC, DSRIC has better discrimination ability than SRIC.

.

3.2 Classification and algorithms

After we get a set of matrices B1↪ B2↪ ▷▷▷↪ BK, a query sample z is classified to the class with the minimal reconstruction error.

The algorithm of DSRIC is shown in Algorithm 1.

Algorithm 1 The algorithm of discriminative selfrepresentation induced classifier (DSRIC)

Input: A query sample z and the training set X = [X1↪X2↪ ▷▷▷↪XK].

Output: label(z)

• 1: Calculate B1↪B2↪ ▷▷▷↪BK by Eq. (13);
• 2: Calculate rk = kz - Bkzk22 ;
• 3: Get label(z) = argmink¶rk♦.

3.3 Complexity analysis

In this section, we discuss the time and space complexity of SRIC, DSRIC.

Training complexity

SRIC and DSRIC need to learn K self-representation matrices in the training stage by Eq. (10) and Eq. (13), respectively. The time complexity to solve Eq. (10) and Eq. (13) is O(d3 ). Hence the training time complexity of SRIC and DSRIC is O(Kd3 ). During the training stage, all the methods should contain the training set. Hence, the training memory of SRIC and DSRIC is Kd2 + Kdn.

Testing complexity

In the testing stage, the time complexity of SRIC and DSRIC is O(Kd2 ). As DSRIC only needs to store a set of d ⇥ d matrices, the storage space of DSRIC is Kd2 . When the number of samples is much larger than the number of feature dimensions, the advantage of DSRIC in time complexity and storage consumption is quite significant.

We will compare SRIC and DSRIC with NNC [Cover and Hart, 1967], NSC [Chien and Wu, 2002], NAH [Vincent and Bengio, 2001], NCH [Vincent and Bengio, 2001], SRC [Wright et al., 2009], CRC [Zhang et al., 2011] and CROC [Chi and Porikli, 2014] in the experiments. The time and space complexity in the training and testing stages of all the methods are listed in Table 1.

4 Experimental analysis

In this section, we test the performance of DSRIC 1 on eight UCI datasets, two handwritten digit recognition databases, two face recognition database and one gender classification dataset. We compare the proposed classifier with eight popular and state-of-the-art classifiers, including the nearest neighbor classifier (NNC) [Cover and Hart, 1967], nearest subspace classifier (NSC) [Chien and Wu, 2002], nearest convex hull classifier (NCH) [Vincent and Bengio, 2002], nearest affine hull classifier (NAH) [Vincent and Bengio, 2002], sparse representation based classifier (SRC) [Wright et al., 2009], collaborative representation based classifier (CRC) [Zhang et al., 2011] and collaborative representation optimization classifier (CROC) [Chi and Porikli, 2014]. Among them, NNC is a baseline benchmark, and the remaining are all representation based classifiers.

The performance of different classifiers is evaluated from three aspects: classification accuracy, the running time and memory consumption in the testing stage. In order to easily show the speedup and memory saving of DSRIC over other methods, in all the following experiments we take the running time and memory consumption of DSRIC as a unit (i.e., 1), and report the results of other methods based on it. All algorithms are run in an Intel(R) Core(TM) i7-2600K (3.4GHz) PC.

1 Since SRIC is equivalent to NSC, the results of SRIC will not be reported.

4.1 Parameter setting

There are two parameters in DSRIC: λ1 and λ2. In all the experiments, λ2 is fixed as 0.001 and λ1 is chosen on the training dataset by five-fold cross-validation. For the compared representation based methods, the parameters in NCH and NAH are set as 1 and 100, respectively, as suggested in the original paper; the regularization parameter in NSC, SRC and CRC is tuned from ¶0▷0005↪ 0▷001↪ 0▷005↪ 0▷01♦ and the best results are reported; following the experiment setting in [Chi and Porikli, 2014], the parameter of CROC is chosen by five-fold cross-validation on the training set.

4.2 UCI datasets

We first use eight datasets (derm, german, heart, hepatitis, iono, rice, thyroid, wdbc, wpbc, yeast) from the UCI machine learning repository [Asuncion and Newman, 2007] to evaluate the performance of DSRIC. The number of classes (c), number of features (f) and number of samples (s) of the eight datasets are illustrated in the right column of Table 2. The average classification accuracy(%), testing time (seconds) and testing memory (MB) over the eights datasets are listed at the bottom of Table 2.

From Table 2, we can see that the accuracy of DSRIC is about 2% higher than NSC, SRC and CRC, and 3% higher than CROC. Besides, DSRIC is much faster than the other representation based classifiers. Compared with NSC, SRC, CRC and CROC, the running time speedup by DSRIC is 64, 547, 106 and 130, respectively. Because NAH and NCH have to solve a QP problem for each query sample, the time consumption is very high compared with other classifiers. In terms of memory requirement, in this experiment DSRIC also has clear advantage.

4.3 Handwritten digit recognition

USPS The USPS dataset contains 7,291 training and 2,007 testing images. Each class has about 650 training samples, and each handwritten digit sample is a 16⇥16 image. The experimental results are listed in Table 3. Since each class has enough training samples and the feature dimension is not high in this experiment, the simple NNC achieves the best accuracy. The recognition rate of DSRIC is only 0.3% lower than NNC. However, DSRIC is significantly faster than NNC with 10,000 times speedup. In addition, the memory consumption of NNC is 2.8 times larger than DSRIC.

MNIST The MNIST dataset includes a training set of 60,000 samples and a test set of 10,000 samples. The size of each image is 28⇥28 and there are 10 classes of digit images. Compared to USPS, there are more training samples. Table 4 lists the recognition rate, testing time and testing memory by different methods. Similar to the results in USPS, the recognition rate of DSRIC equals to NSC, and is 1.4% lower than NNC. However, DSRIC avoids the one-to-one searching process in the training set and is 18,000 faster than NNC, which is very important in real-time applications. Compared with SRC, DSRIC is 51 times faster and saves 7.65 times the memory. Please note that the performances of NCH, NAH, CRC and CROC are not reported because these methods need to process a 60,000⇥60,000 square matrix and out-of-memory in our PC.

4.4 Face recognition

LFW database The LFW database contains images of 5,749 subjects in unconstrained environment. LFW-a is a version of LFW after alignment using commercial face alignment software. We gathered the subjects which have no less than eleven samples and then formed a dataset with 136 subjects from LFW-a. Each face image is firstly cropped to 102⇥120 and then resized to 32⇥32 images. We select 9 face images per subject for training and use the remaining face images for testing.

The experimental results are shown in Table 5. DSRIC has the highest recognition accuracy. Since there are 158 subject and the feature dimension is 1024, DSRIC does not show advantages in memory in this experiment.

4.5 Gender classification

In this section, a non-occluded subset (14 images per subject) of the AR dataset is used. It includes face images of 50 male and 50 female subjects. The images from the first 25 males and 25 females are used for training and the remaining for testing. Following the experiment setting in [Zhang et al., 2011], each face image is cropped to 60⇥43 and PCA is used to reduce the feature dimension to 50. The classification accuracy, testing time and testing memory are given in Table 6. One can see that DSRIC achieves the highest accuracy, and it costs much less running time and memory than others.

5 Conclusions

In this paper we investigated the representation based classification problem from a "feature oriented" perspective. Different from the existing representation based classifiers that represent a sample as the linear combination of other samples, we explored to represent a feature by its relevant features in the data, which we call self-representation. A selfrepresentation induced classifier (SRIC) was then proposed, which learns a self-representation matrix per class and uses these matrices for classification. The query sample is then classified to the class with the minimal reconstruction error. We proved that SRIC is equivalent to nearest subspace classifier (NSC) with l2-norm regularization in terms of classification decision. Furthermore, it can be shown that SRIC is essentially the principal component analysis (PCA) with eigenvalue shrinkage. We then proposed a discriminative SRIC (DSRIC) classifier, which not only minimizes the feature selfrepresentation residual of this class but represents little the features of other classes. The time and space complexity of DSRIC (except for the training memory) is invariant to the number of training samples, which makes it very suitable for large scale datasets with many training samples, e.g., USPS and MNIST. Experimental results on different pattern recognition tasks showed that DSRIC achieves comparable or superior recognition rate to state-of-the-art representation based classifiers, while it has higher efficiency and lower memory consumption.

6 Acknowledgement

This work was supported by the National Program on Key Basic Research Project under Grant 2013CB329304, the National Natural Science Foundation of China under Grants 61502332, 61432011, 61222210.