Convolutional 2D LDA for Nonlinear Dimensionality Reduction

1 Introduction

Linear discriminant analysis (LDA) is a classical method for dimension reduction and classification. It is commonly used in machine learning and pattern recognition, which shows promising performance in applications such as face recognition [Belhumeur et al., 1997]. By maximizing the trace of between-class scatter matrix and minimizing the trace of within-class scatter matrix, the classical LDA aims to find the optimal projection vectors.

The main idea of LDA is simple and effective. The classical LDA, however, demands that input data should be represented by vector. Such constraint is a significant drawback to express complex data. For example, image, the most widely used 2D data format, isn't suitable for vector representation. In order to tackle this problem, one kind of method utilizes the classical LDA combined with matrix-vector transformation [Ma et al., 2013][Ren et al., 2012]. However, what this transformation brings is huge computational expense. In order to process 2D data directly, many method based on 2D data format [Li and Yuan, 2005][Yang et al., 2004] is proposed. Another way to address this problem is twodimensional linear discriminant analysis (2D LDA) [Ye et al., 2004][Ren et al., 2015], which removes matrix-vector transformation. Using the original 2D-structure data format, 2D LDA can preserve more co-related information which leads to better performance.

∗This work is supported in part by the National Natural Science Foundation of China under Grant 61379094, in part by the Open Research Fund of Key Laboratory of Spectral Imaging Technology, Chinese Academy of Sciences, and in part by the Fundamental Research Funds for the Central Universities under Grant 3102017AX010. Feiping Nie is the corresponding author.

With the wave of artificial intelligence, deep version of many classical methods have shown its power again. In recent years, some methods related to classical PCA [Chan et al., 2014] and LDA [Dorfer et al., 2015] achieved promising performance in combination with deep neural networks. The purpose of these methods is to utilize the learning capacity of networks and the effective optimization tool, namely stochastic gradient descent and its variants. However, the combination of classical LDA and deep neural networks means complex network construction and gradient calculation.

In this paper, we propose a convolutional 2D LDA method that aims to solve above the limitation for high-volume and high-order data nonlinear dimensionality reduction. Different from [Dorfer et al., 2015], we employ a special Convolutional Neural Networks (CNN) to optimize LDA objective function instead of maximizing eigenvalues of scatter matrix. The key novelty of our method is that using such CNN structure makes the optimization easier than others and gains better performance. Meanwhile, the whole networks is a nonlinear 2D dimensionality reduction method which optimizes classification and dimensionality reduction networks simultaneously.

2 RelatedWork

2.1 Revisiting LDA

The classical LDA aims to project the original data into a lower-dimensional space. Meanwhile, the projection should separate the lower-dimensional data. In order to calculate the degree of separation, scatter matrix of projected data is employed. We denote the original data as X ∈ Rl×n , which contains c classes π = [π1, π2, . . . , πc]. Suppose the projection is defined by W ∈ Rl×c . The transformation of classical LDA is yi = W T xi, where xi ∈ Rl×1 is a sample from the original data. In order to find the optimal projection matrix W, we use between-class scatter matrix Sb and within-class scatter matrix Sw which are defined as follows:

where ni is the number of samples in class πi, N is the number of whole samples, Mi = 1 ni ∑Xj∈πi Xj is the average

value of class πi and M = 1N ∑ci=1 ∑Xj∈πi Xj is the average value of the whole dataset.

Accordingly, the transformed lower-dimensional betweenclass and within-class scatter matrix can be:

Based on the above condition of separation, the optimal W should be:

In [Hou et al., 2012], the above function can be rewritten as follow:

where Tr(·) denotes the matrix trace operation.

2.2 2D LDA

The major differences between LDA and 2D LDA is the data representation format. In order to project 2D-format data, 2D LDA employs a set of transformation matrices. We denotes U, V as the transformation matrices and X = [X1,X2, . . . ,Xn] as the input data, where Xi ∈ Rm×n . In this way, the projected between-class and within-class scatter matrix can be rewritten as:

Once the scatter matrix of 2D-format data is determined, the same objective function as classical LDA can be formulated. What make difference between objective function of classical LDA and 2D LDA is the transformation matrices. Hence, the optimization target would be a set of transformation matrices U, V :

As mentioned in [Hou et al., 2012], the objective function is defined as follows:

2.3 Regularized LDA

In the procedure of solving LDA problem, calculating the inverse matrix of within-class scatter matrix is essential. However, the within-class scatter matrix ˜ Sw might be singular under certain circumstances such as tiny sample set of data. This property will make the problem hard to solve. In order to avoid singularity of within-class scatter matrix, regularization terms are added to common LDA problem. Meanwhile, such regularization terms can be helpful to prevent over-fitting problem.

In [Mahanta et al., 2013], an iterative regularized MVLDA is proposed. They use estimates of scatter matrices as regularization terms. The estimates of within-class scatter matrix can be obtained iteratively:

The estimates of between-class scatter matrix are defined as:

Based on these estimates, the regularized scatter matrices are defined as:

where Ssw = SWR ⊗ SWL and Ss b = SBR ⊗ SBL.

Another simple regularized LDA utilizes identity matrix to avoid singularity of within-class scatter matrix. The objective function of LDA can be formulated in a unified format:

If we add an identity matrix to within-class scatter matrix, the whole itemwill meet the full rank condition. The regularized objective function can be:

2.4 Deep Version of LDA

In [Andrew et al., 2013], a Canonical Correlation Analysis (DCCA) method based on deep neural networks is proposed. DCCA shows remarkable results in simultaneously recorded acoustic and articulatory speech data. In [Dorfer et al., 2015], another kind of deep linear discriminant analysis is proposed, which is used for image classification. The original Categorical Cross Entropy is replaced with summation of eigenvalues, which has the same objective function with common 2D LDA.

3 Convolutional 2D LDA

In this section, we expound on the proof of convolutional 2D LDA and it's corresponding CNN construction.

3.1 LDA Based on Nonlinear Projection

Our goal is to find a 2D nonlinear projection that can be used for dimensionality reduction. We denotes D = [D1, D2, . . . , Dn] as the input data and ψ(·) as nonlinear projection. As long as the projected data di = ψ(Di) maximizes the trace of between-class scatter matrix and minimizes the trace of within-class scatter matrix, we can regard such projection as nonlinear 2D LDA dimensionality reduction method.

Different from classical LDA or 2D LDA, what nonlinear projection brings is better representation performance in the projected subspace. However, an essential and difficult barrier is the optimization of nonlinear projection. In order to tackle this problem, we use a special CNN structure to optimize the whole networks. This kind of optimization is the key novelty of our method.

3.2 LDA in Network

Using CNN to realize dimension reduction is our basic idea. Assume that the nonlinear projection defined by CNN is x = g(A) ∈ Rm×1 , in which x is a m-dimensional vector indicating dimension reduction output, g(·) denotes CNN that performs projection and A represents the original data. If the optimal nonlinear projection g∗ (·) maximizes the trace of between-class scatter matrix and minimizes the trace of within-class scatter matrix after projection, the optimal nonlinear projection g∗ (·) shares the same goal with the classical LDA.

We denote the output of CNN as X = [g(A1), g(A2), . . . , g(An)] ∈ Rm×n and the One-Hot Encoding label of data as Y ∈ Rn×c . Following the realization of regularized LDA, which is helpful to prevent calculation of singular matrix and over-fitting, the objective function is defined as:

where

Due to the complicated structure of CNN g(·), it is tough to optimize this objective function. Fortunately, we can rewrite the objective function in another way which can be easily optimized:

where

proof: The equivalence of Eq.1 and Eq.5 can be proved by Lagrange multiplier method. Suppose we have obtained the optimal W and b in Eq.5, the result of substituting them into Eq.5 should be equal to Eq.1. Hence, the optimal solution for b can be obtained by setting the derivative of Eq.5 with respect to b to zero. Thus, we have:

Substituting b into Eq.5:

Setting the derivative of Eq.8 with respect to W to zeros:

3.3 Network Construction

From the above theorem we can see that if we put a optimization layer above the original CNN g(·) that receives dimension reduction results X and outputs XT W +1bT , we would be able to optimize W and b simultaneously.

Meanwhile, the optimal CNN g(·) in Eq.1 can be obtained because Eq.1 shares the same optimal solution with Eq.5 in such circumstances, which means that the dimensionality reduction networks can be optimized via the optimization layer. Furthermore, the new added optimization layer can be used for classification evaluation of dimensionality reduction performance.

From the 5-layer networks LeNet-5 [Lecun et al., 1998] to ResNet [He et al., 2016] which contains up to 1202 layers, depth of neural network is becoming incredibly huge. The purpose of our method, however, is to examine the effectiveness of this kind of specially designed networks instead of using the great generalization ability of deep networks. Thus, we use two kinds of network structure to examine our method. A simplified dimensionality reduction networks is employed that contains two convolutional layers and one fully connected layer to compare with traditional algorithms. A more complex networks which contains three convolutional layers with batch normalization [Ioffe and Szegedy, 2015] and one fully connected layer with dropout[Hinton et al., 2012] is used to compare with other algorithms based on deep learning.

As mentioned in Eq.5, we use one single layer to perform classification above the dimensionality reduction networks. It converts the dimensionality reduction results into One-Hot encoding label in class space, which can be regarded as classification networks. Meanwhile, this classification networks is in charge of optimizing the dimensionality reduction networks. The loss of whole networks is defined as the Frobenius norm of difference between classification and label, as shown in Eq.5. Figure 1 illustrates the training and deploy procedure. In order to optimize the whole networks, the extra optimization layer is added in the training stage. It can be used as classifier and optimizer simultaneously. Once the optimization of whole networks is finished, the optimization layer can be excluded from original networks.

In this way, we can combine dimensionality reduction and classification stage into a end-to-end networks, which shares the same objective function with regularized 2D LDA. Apparently, our method is a nonlinear 2D LDA method.

4 Experiment

In this section, we compare the proposed convolutional 2D LDA with eight traditional algorithms, including LDA [Belhumeur et al., 1997], 2D LDA [Ye et al., 2004], 2D PCA [Yang et al., 2004], Bilinear SVM [Pirsiavash et al., 2009], S2D LDA [Inoue and Urahama, 2006], P2D LDA [Inoue and Urahama, 2006], Tensor LPP [He et al., 2005] and CRP [Chang et al., 2015]. Experiments are performed on two handwritten digit datasets. We also compare our method with other four algorithms based on deep learning, including NIN [Lin et al., 2013], Maxout [Goodfellow et al., 2013], DeepCNet [Graham, 2014] and DeepLDA [Dorfer et al., 2015]. In addition, we provide detailed networks architecture and hyper parameters settings used in our experiment.

4.1 Datasets and Experiment Setup

We use three datasets to conduct our experiments.

MNIST dataset: The MNIST dataset contains 60,000 examples used for handwritten digits recognition.

CVL dataset: The CVL dataset [Diem et al., 2013] is generated for the ICDAR2013 Handwritten Digit Recognition Competition. There are 21,780 handwritten digit images in this dataset. The size of each image is 32×32.

USPS dataset: The USPS dataset is used for light weight handwritten digit recognition. It contains 9,298 handwritten digit images in this database with the size of 16×16.

As mentioned in section 3.2, we adopt two kinds of networks with two and three convolutional layers, one fully connected layer and it's corresponding LDA classification and optimization layer. In Table 1 we outline the architecture of our model in detail. The whole networks is trained with momentum [Sutskever et al., 2013] and Adam [Kingma and Ba, 2014] SGD optimizer in TensorFlow[Abadi et al., 2016]. For a more convincing result, all hyper parameters for different datasets are identical. It is noteworthy that batch size is an essential hyper parameter because lack of certain classes in a mini-batch would make the weighted label ˜ Y meaningless. The batch size is set to 100 and the learning rate to 0.0002. The regularization weight γ is set to 0.0001.

4.2 Experimental Results

Traditional Method

In this experiment, we use classification accuracy to compare our algorithm with other eight methods, including LDA, 2D LDA, 2D PCA, Bilinear SVM, S2D LDA, P2D LDA, Tensor LPP and CRP. Two different classifiers are used in this experiment which are SVM and 1-Nearest-Neighbor (1NN). Note that our method utilizes the extra optimization layer to classify, instead of SVM or 1NN. Because the Bilinear SVM itself is a classifier, we compare it with our method directly. In order to evaluate the effectiveness of our method, three different sizes of training sets for both datasets are employed.

The experiment results using 80% training data for each dataset are shown in Table 2. Our method outperforms other eight methods in different datasets and classifiers. This result shows that our method takes the advantages of deep neural networks. Meanwhile, the effectiveness of our method can be verified. When we use CVL dataset with SVM classifier, our method outperforms classical 2D LDA by 8.9% in terms of classification accuracy.

The experiment results using 20 training data for each dataset are shown in Table 3. The CRP method achieves the best results in CVL dataset using SVM and 1NN classifier. The second best one is our method. In USPS dataset, our method consistently performs better than the other method. What we can see from this experiment is that the CNN starts to suffer from Insufficient data.

The experiment results using 10 training data for each dataset are shown in Table 5. With the decrease of training data, all the methods show worse results. Our method achieves the 3rd place in CVL dataset using 1NN classifier. When it comes to SVM classifier, our method shows barely satisfactory results. In USPS dataset, our method achieves the 2nd place compared with other algorithms. Although the number of training data is extremely small, our method still outperforms 2D LDA by 10.8% in USPS dataset using 1NN as classifier.

Deep Learning Method

In this experiment, we use classification accuracy to compare our algorithm with several deep learning method in MNIST dataset, including NIN, Maxout, DeepCNet, DeepLDA. Note that we use the simplified and the complex model to compare. In Table 4, we can observe that our method achieves promising results. Although our simplified version method shows poor performance compared with other method, we can still say that accuracy of 99.2% is not a bad result in consideration of its structure.

From the above experiments, we can observe that the proposed method performs fairly good in rich data context. Compared with classical 2D LDA, our method achieves better performance in all of the datasets and classifiers. when dealing with insufficient data, the proposed method still shows a satisfactory result. Taking into account all these three experiments, we can say that our method achieves a promising performance.

4.3 Discussion

It is interesting to see that our method gets a more satisfying performance in rich data context compared with insufficient data condition. This drawback might be caused by three reasons.

First, according to Eq.5, the optimal dimensionality reduction networks can be obtained with optimal W and b. With insufficient data, the final dimensionality reduction networks is optimized with non-optimal W and b.

Second, the over-fitting problem in deep neural networks would be serious when we use small dataset. In Table 5, the whole training dataset contains only 100 samples while deep neural networks needs a large number of data.

The last reason is the training trick. All of the experiments are conducted with the same hyper parameters. If the hyper parameters are adjusted for insufficient data, the classification accuracy would be higher. In Table 6 and Table 7, the hyper parameters adjusted for insufficient data lead to a better performance. All we have done is setting the learning rate higher to overcome the over-fitting problem. The our method+ in Table 6 and Table 7 uses learning rate of 0.0004 and 0.0006 respectively. The learning rate used in our original experiment is 0.0002.

When we increase the number of training data from 100 to 200 in CVL dataset, the average classification accuracy improvement of our method and CRP are 16.9% and 8.9%. When we use more data, the average classification accuracy improvement of our method and CRP are 24.5% and 16.4%.

Such phenomenon can be seen in USPS dataset as well. Compared with CRP algorithm that shows great performance using few data, our method shows much faster performance growth with the increasement of training data number.

The experiment results show two major features of our method. One of them is that our method need more data than other methods. Another one is that better performance can be achieved with sufficient data. As a result of CNN structure, this kind of features are obvious.

5 Conclusion

In this paper, we have proposed a convolutional 2D LDA method for nonlinear dimensionality reduction. The difficult problem of optimization is solved by a clever equivalence of two objective functions. The proposed method employs a two stage end-to-end CNN to realize dimensionality reduction. Effectiveness of such structure has been proved with two different networks. Our convolutional 2D LDA method outperforms the classical LDA in all experiment settings. With sufficient data, our method shows remarkable dimensionality reduction ability.