On improving robustness of LDA and SRDA by using tangent vectors

[EN] In the area of pattern recognition, it is common for few training samples to be available with respect to the dimensionality of the representation space; this is known as the curse of dimensionality. This problem can be alleviated by using a dimensionality reduction approach, which overcomes the curse relatively well. Moreover, supervised dimensionality reduction techniques generally provide better recognition performance; however, several of these tend to suffer from the curse when applied directly to high-dimensional spaces. We propose to overcome this problem by incorporating additional information to supervised subspace learning techniques using what is known as tangent vectors. This additional information accounts for the possible differences that the sample data can suffer. In fact, this can be seen as a way to model the unseen data and make better use of the scarce training samples. In this paper, methods for incorporating tangent vector information are described for one classical technique (LDA) and one state-of-the-art technique (SRDA). Experimental results confirm that this additional information improves performance and robustness to known transformations.

section_content: In the area of pattern recognition, it is common for few training samples to be available with respect to the dimensionality of the representation space; this is known as the curse of dimensionality (Bellman, 1961). To handle this problem, it has become popular to use dimensionality reduction (also known as subspace learning) as a preprocessing step. However, several dimensionality reduction techniques also struggle due to the lack of samples, or in other words, they are also affected by the curse. In these cases, a tandem strategy is often used by applying a more robust technique as an initial step. This strategy, though less useful from the discriminative point of view, reduces the dimensionality down to a more appropriate size for the subsequent discriminative dimensionality reduction. The most well-known tandem is PCA+LDA (Yang and Yang, 2003; Yang et al., 2005), i. e., where Principal Component Analysis is performed over the original representation space and afterwards Linear Discriminant Analysis (Fukunaga, 1990) is applied. Note that PCA is an unsupervised technique, whereas LDA is supervised, which is crucial since the use of a supervised technique generally helps to boost the recognition performance considerably. 

The motivation for this paper was to improve supervised subspace learning techniques so that they are able to cope with scarce data in highdimensional feature spaces. Even though a tandem strategy overcomes the curse of dimensionality for the less robust supervised subspace learning techniques, it would clearly be more desirable for these techniques to work well in high-dimensional spaces, up to the point of not necessarily requiring a previous dimensionality reduction. This goal is addressed in this paper by considering the known transformations that a sample can exhibit which do not modify the class membership. In fact, we can consider that these known transformations model the unseen samples (as if increasing the training set), thereby overcoming the curse of dimensionality. Consider for instance the rotations and displacements of facial images due to imperfect alignments. Even though these variations are expected to appear, it is known that they do not change the identity of the person appearing in the image. One method to account for the possible combinations of these base transformations is the tangent distance (Simard et al., 1993) ; however, it is only applicable to distance-based classifiers. In this work only the tangent vectors are used as a way to obtain more information from the training set, without imposing any restrictions on the classifier. Related to this paper, Schölkopf et al. (1997) and Mika et al. (1999) use the tangent vectors to improve Support Vector kernels and make them somewhat invariant to the tangent vector transformations. 

The paper addresses two supervised techniques: the first is the classic LDA (including the PCA+LDA variant), and the second is the stateof-the-art Spectral Regression Discriminant Analysis (SRDA) (Cai et al., 2008; Chen et al., 2009). In the literature, there are many other methods that could be considered (see for instance Burges (2005) and van der Maaten and Postma (2009) for a review of some of them). Nevertheless, the techniques we have chosen are known to perform well and illustrate an idea which could be applied to other methods in future works. 

The contributions of the paper are the following. First, we reformulate LDA so that it is expressed in terms of the covariance matrix, which can be better estimated by using tangent vectors (see Section 3. 1). This modification helps to overcome the singularity problems that LDA has when there are few training samples, improves recognition performance, and also increases the robustness of the learned subspace to known transformations. Second, we present a method to incorporate the tangent vector information in SRDA that keeps the characteristic of being solvable by systems of linear equations, thus continuing to be efficient for learning (see Section 3. 2). Also, the recognition performance improves and the robustness of the learned subspaces to known transformations increases. Finally, in Section 4, we present empirical results that confirm the benefits when using the proposed modifications.
section_name: Introduction

section_content: Suppose we have a point x ∈ R D generated from an underlying distribution, and that the possible transformations or manifold of x is given by t(x, α), a function which depends on a parameter vector α ∈ R L with the characteristic that t(x, 0) = x. The dimensionality of α is essentially the degrees of freedom of possible variations that x can have. In real applications, the manifold t(x, α) is highly non-linear; however, for values close to α = 0, it can be reasonable to approximate it by a linear subspace. This can also be interpreted as representing the manifold by its Taylor series expansion evaluated at α = 0, and discarding the second and higher order terms (Simard et al., 1998)

The partial derivatives v l = ∂ t/∂α l are known as the tangent vectors, since they are tangent to the transformation manifold t at point x. 

The concept of the tangent vector approximation is illustrated in Figure 1 for a single direction of variability. As can be observed, the approximation can be quite good for small values of α ; however, as the norm α increases, the deviation from the true manifold t is expected to increase. 

When comparing two points, as a similarity measure between them, it would be ideal to use the minimum distance between their respective transformation manifolds. As an approximation to this, one can use the minimum distance between the subspaces spanned by the tangent vectors (Simard et al., 1998), which is known as the tangent distance (TD). The single-sided tangent distance considers only one of the tangent subspaces and has the advantage of being more efficient to compute (Dahmen et al., 2001). From a classification perspective, the tangent subspace can either be for the reference (RTD) or the observation (OTD).
section_name: Preliminaries and Overview of the Tangent Vectors

section_content: There are several methods to estimate the tangent vectors, although, unfortunately, there is no general way to estimate them for every task. The most intuitive method is to use the difference between the sample and its transformation as tangent vectors. However, this method can only be used if it is possible to generate a transformation of a sample. The most well-known method of estimating tangent vectors is the one proposed t(x, α) by Simard et al. (1998). This method is only applicable to image based problems, having been employed successfully to model the following: scaling, rotation, vertical and horizontal translation, parallel and diagonal hyperbolic transformations, and trace thickening. 

There are other methods that try to estimate the tangent vectors from the training set, instead of adding some prior knowledge. One method of this type is presented in Keysers et al. (2004), which is based on maximum likelihood estimation. Another method is to use the difference between a sample and its nearest neighbors from the same class as tangent vectors. 

The methods of Simard and the nearest neighbors were used in the experiments. However, as discussed in Section 3 and empirically observed, the latter is less useful since it does not provide as much additional information and it does not help to overcome the singularity problems.
section_name: Estimation of Tangent Vectors

section_name: Tangent Vectors in Subspace Learning

section_content: The objective of LDA is that the obtained subspace should discriminate the classes well. To this end, LDA simultaneously maximizes the distances between the class centers (between-class scatter matrix) and minimizes the distances within each class (within-class scatter matrix). It is straightforward to reformulate LDA so that it is stated in terms of the covariance matrix Σ x and a normalized between-class scatter matrix Σ µ. The objective function is then

The solution of the LDA objective (3) is the following generalized eigenvalue decomposition

with Λ being a diagonal matrix of generalized eigenvalues and the columns of B being the generalized eigenvectors. By having a solution of LDA in terms of the covariance matrix, for a given dataset X = {x 1,. . ., x N }, we are able to use a better empirical estimation for Σ x that considers tangent vectors (Keysers et al., 2004) given by

where Σ X is the usual estimation of the covariance matrix and V l is the set that includes all of the tangent vectors of type l. The weights γ 1,. . ., γ L account for the importance of each tangent vector type depending on the distributions p(α 1 ),. . ., p(α L ); however, in practice, these are parameters that need to be estimated. A good rule of thumb is to set them equal for all tangent types and to sample them so that Tr(Σ V ) is a certain fraction of Tr(Σ X ). This improved version of LDA will be referred to as TLDA. 1

A better estimation for Σ µ is not obtained since it is reasonable to assume that the distributions p(α 1 ),. . ., p(α L ) are symmetric, a case in which the tangent vectors cancel out. Intuitively, this makes sense because the tangent vectors give information about how a sample might vary and not about the other classes. 

One of the shorthands of classical LDA is that if the dimensionality of the vectors is higher than the number of training samples, then Σ X is singular and therefore there is no unique solution to the generalized eigenvalue problem. With the new estimation of Σ x, if the tangent vectors are linearly independent from the training samples (which is the case for Simard's method), the rank goes from N for Σ X to N(L + 1) for Σ X ∪V, which can drastically reduce the number of samples that are necessary to avoid singularities. Thus, for LDA, the estimation (6) of Σ x provides for LDA a way to take better advantage of the limited training data, normally avoiding a singularity and making the solution more robust to the known class-invariant transformations. This is observed in the experimental results. 

A popular method to overcome the singularity problem in classical LDA is to previously reduce dimensionality by means of PCA. Since PCA is also based on the estimation of the covariance matrix, it can also be improved by including tangent vector information, i. e., TPCA. Even though TLDA overcomes the singularity problem, TLDA combined with a previous reduction by TPCA gives very good performance as can be observed in the experiments section. 

The computational complexity of the method basically depends on the tangent vector estimation technique. In the case of Simard's method, the computation of the tangent vectors are O(KDN) with K ≪ D being the size of the convolution kernel. In comparison to the complexity of the eigenvalue decomposition, this additional cost is not significant.
section_name: Tangent Vectors in LDA

section_content: SRDA is similar to LDA. In fact, the starting optimization criterion is the same as LDA and, thus, the solution is given by Equation (4). However, to make the computation fast, SRDA avoids the need to do an eigenvalue decomposition. Observe that Equation (4) can be rewritten as

where X ∈ R D×N is the centered data matrix ordered by classes, i. e., X = [x 1,1µ,. . ., x C,N Cµ], and W ∈ R N×N is a matrix composed mostly of zeros, having the matrices W c ∈ R N c ×N c for c = 1,. . ., C along the diagonal, in which the elements of W c are all equal to N -1 c, with N c being the number of samples of class c. 

As presented in Cai et al. (2008), the problem in Equation ( 4 ) can be tackled by solving the system of linear equations Y = XT B, where Y ∈ R N×C-1 is a matrix whose columns are C -1 eigenvectors of W which are orthogonal to the vector of ones. Matrix W has exactly C nonzero eigenvalues all equal to one, and obtaining a set of eigenvectors is trivial. In fact, for each class c, there is an eigenvector with elements equal to N -1/2 c in the positions of the samples of class c and zeros for all other elements. Therefore, finding Y reduces to orthogonalize these trivial eigenvectors with respect to the vector of ones. However, the system Y = XT B may not have a solution, so it was proposed to find the B that best fits the equation in a regularized least squares sense. The optimization function of SRDA is then given by

where ρ is the regularization parameter. 

Incorporating the tangent vectors into SRDA cannot be done in the same way as for LDA (Section 3. 1), since SRDA does not directly use the covariance matrix. Furthermore, the modification should be done in such a way that the problem can still be solved as systems of linear equations, thus retaining the advantages of SRDA. Using matrix notation, Equation ( 6 ) can be written as

where the columns of matrix V X ∈ R D×NL are all the tangent vectors of the training samples in X. With a few manipulations, it can be shown that, when including the tangent vectors, the generalized eigenvalue problem can be expressed as

where Z = [ X γV X ], and the new weight matrix is the same as W, but W ′ is padded with NL rows and columns of zeros at the bottom and on the right. The eigenvalues of W ′ are also only C all equal to one, and the eigenvectors are the same as for W, but padded with NL zeros at the bottom. The final optimization function for SRDA including the tangent vector information is then given by

where the columns of matrix Y ′ are C -1 eigenvectors of W ′ which are orthogonal to the vector composed of ones for the first N elements and zeros for the remaining NL. 

The optimization function for the Tangent Vector SRDA (TSRDA) 1 is basically the same as for the original SRDA. The computational complexity increases by the computation of the tangent vectors, and the linear systems increase in number of equations, but with the same number of unknowns. Thus, it continues to be a very efficient algorithm.
section_name: Tangent Vectors in SRDA

section_content: The proposed approaches have been assessed with three facial image recognition tasks: gender recognition, expression recognition, and identification. 2 Although only image problems were considered, the same approach can be applied in other tasks as long as the known transformations can be represented as tangent vectors. The gender dataset that we used is composed of 1892 samples of 32 × 40 pixel images and the objective for this dataset is to determine the gender, male or female (Villegas and Paredes, 2011). The expressions dataset is composed of 1929 samples of 32 × 32 pixel images obtained from the databases: Cohn-Kanade (Kanade et al., 2000) (using the emotion labels from Buenaposada et al. (2008) ), AR (Martinez and Benavente, 1998), and JAFFE (Lyons et al., Dec 1999). The objective for this dataset is to classify the facial expression as one of 7 possibilities: a neutral expression, a person screaming, or one of the six basic emotions (Donato et al., Oct 1999). The performances for both datasets were estimated using a 5-fold cross-validation. Finally, for face identification, the dataset and evaluation protocol were the same as in Zhao et al. (2007), although with an image size of 32 × 40. A special characteristic of this dataset is that the 116 subjects used for the subspace learning are different from the 200 subjects used in the testing phase (10 images per subject). Therefore, the goal for this dataset is to learn a subspace that is suitable for face identification in general. 

Since the objective of the experimentation was to compare the subspace learning methods with and without the tangent vector information, we kept the feature set and classifier constant. A k-NN classifier with the Euclidean distance in the learned subspace was used on all tasks; however, for the face identification task, the tangent distances were also tested, applying the same learned projection on the tangents. This shows that the tangent distances can also be applied in a discriminative subspace, which can further improve the recognition results. 

The tangent vectors were estimated using the method from Simard et al. (1998) for modeling horizontal and vertical translation, rotation, and scaling. Tangent vectors estimated by nearest neighbors were also used, which illustrates the behavior of the algorithms with tangent vectors that are linearly dependent on the training set. To indicate which tangent types were employed for learning, in the results, a sub-index is added to the method acronym showing "hvrs" for Simard's method and "kθ" for θ = {1, 2, 4, 8, 16, 32} nearest neighbors. The γ parameter was set to be the same for all tangent types and was varied as explained in Section 3. 1. The intermediate PCA/TPCA and the final subspace dimensionalities were varied between 1 and 256 and the best result for each technique is the one presented. The ρ for SRDA was varied and adjusted like the other parameters, and did not rely on an automatic method (Chen et al., 2009). 

As a reference and to show that supervised subspace learning methods generally perform poorly when applied directly to high-dimensional feature vectors, results for other linear and supervised techniques are included: namely, Marginal Fisher Analysis (MFA) (Yan et al., 2007), Locality Sensitive Discriminant Analysis (LSDA) (Cai et al., 2007), Supervised Locality Preserving Projections (SLPP) (Zheng et al., 2007), and Nonparametric Discriminant Analysis (NDA) (Bressan and Vitrià, 2003). The implementations used for MFA, LSDA, SLPP, and SRDA were written by D. Cai and for NDA was written by J. Vitrià.
section_name: Experiments

section_content: The results of the experiments for each dataset are presented in tables 1, 2, and 3, respectively. Included are the estimated classification error rates, the subspace dimensionalities, and the training and testing times. Note that the training times agree with the complexity analysis in Section 3; however, the computation of the tangents was not optimized, unlike the eigenvalue decomposition. Thus, the execution time of the proposed methods could be significantly improved, especially considering that it is easily parallelizable. 

As can be observed in the tables, in several cases the proposed methods show a statistically significant improvement when using Simard's tangents; in the rest of the cases, the performance remains the same. For the gender dataset (Table 1 ), no results are shown for LDA or TLDA kθ because the covariance matrix is singular. The proposed TLDA hvrs was not affected by this singularity problem and, except for SRDA, obtains a significantly better performance than all baseline techniques. The performance of TLDA improves further when using a previous step of TPCA, even when using tangent vectors obtained by nearest neighbors. Still, the best result was when Simard's tangents were used. In the expressions dataset (Table 2 ), the improvement of TLDA hvrs with respect to LDA was enormous, up to the point of being statistically the same as with PCA preprocessing. In the case of SRDA, an improvement was also observed when using tangents, although with a lower confidence level. Note that for both TLDA and TSRDA, there was no further improvement with PCA preprocessing; nevertheless, this is not necessarily a bad thing. Ideally, the supervised dimensionality reduction should be done in the original feature space so that no discriminative information is discarded. If the method works well in the original space, it is not expected to get better results when using PCA preprocessing. In the identification dataset (Table 3 ), very competitive recognition rates were achieved, particularly with TSRDA, even though a simple pixel based representation was used in comparison to the Local Binary Pattern (LBP), which is known to be a better representation for face recognition (Ahonen et al., 2006). For this dataset, the improvement comparing SRDA and TSRDA was statistically significant; however, the results for TLDA remained the same. Note that the use of the tangent distance improved the performance further, confirming that the tangent vectors are also useful in the learned subspace. 

Regarding the combination of different types of tangents (i. e., hvrs+kθ), we did not observe that the performance improved further when more tangent vector types were used. The reason for this may have been setting the γ parameter to be the same for all tangent vectors. The problem of using different factors for each tangent type and automatically obtaining them is a topic that needs further research.
section_name: Recognition Performance

section_content: To analyze the robustness to the transformations considered during learning, figures 2, 3, and 4 present plots of the relative improvement in recognition of the proposed methods. These plots compare the methods with or without the tangents as the test samples are artificially transformed. All the graphs have the same y-axis range in order to make it easier to compare them with each other. 

For the gender dataset, only LDA shows marginal improvement. However, it must be taken into account that gender recognition is a two-class problem and the target space dimensionality is only one, so it is a challenging task. In contrast, for the other two datasets (expressions and identification), a much greater improvement is observed. As the transformations of the images grow, when the tangents are used (TPCA+TLDA hvrs and TSRDA hvrs ), each time the relative improvement is greater than without them (PCA+LDA and SRDA). This shows that the subspaces learned with the tangents are more robust to these transformations. This is observed even though the Euclidean distance is employed, which is not invariant to these transformations. This effect can be explained by the fact that without the tangents, those directions of variability are not taken into account and might be removed by the learned projection. Interestingly, a better transformation invariance was obtained for LDA than for SRDA on the three datasets.
section_name: Robustness to Known Transformations

section_content: In this paper, two supervised dimensionality reduction techniques, Linear Discriminant Analysis (LDA) and the state-of-the-art Spectral Re-gression Discriminant Analysis (SRDA), have been analyzed and modifications that use the tangent vector information have been proposed for them. 

Experiments were conducted using three facial image recognition tasks: gender, expressions, and identification. Depending on the dataset, the proposed methods, TLDA and TSRDA, provided a significantly better recognition performance, and in no case did we observe a degradation. In the case of TLDA, the singularity of the covariance matrix due to the limited number of training samples was avoided. Another result was that the subspaces learned tended to be more robust to the transformations that were used during learning. Furthermore, an additional gain was obtained by using the same dimensionality reduction for the tangents and by employing a tangent distance. 

The parameters γ 1,. . ., γ L, which weight the importance that is given to each of the tangent types (e. g. rotation, nearest neighbor, etc. ), were set to be the equal, i. e., γ 1 = γ 2 =. . . = γ L. This seemed to prevent further improvements when combining several tangent types. The γ parameters could be set to be different for each tangent type and adjusted using crossvalidation or a Markov Chain Monte Carlo. By doing this, better results would be expected; however, the cost of the algorithm could increase dramatically. A future direction for research is to develop a better method to find adequate values for these parameters. Another interesting idea to explore would be to use an optimization criterion based on the singlesided tangent distance, which can eliminate the need to estimate such parameters. 

The same ideas presented here could be used to improve other existing subspace learning methods. Interesting examples are the works by Yang et al. (2011) and Villegas and Paredes (2011), which try to learn the subspace while also considering what the subsequent classifier will be. Another example would be the family of methods based on preserving the neighborhood such as the recent work of Gui et al. (2012). 

Another important direction for future research is the development of methods for estimating tangent vectors for other tasks so that these techniques can be used in more applications, not only the ones related to image recognition. We plan to apply this approach to the bag-of-words representation to model word-count variability. Zhao et al. (2007), execution times are not available. § TSRDA hvrs,TD better than SRDA Euc. for a confidence level of 95%. ♯ TSRDA hvrs,TD better than TSRDA hvrs,Euc. for a confidence level of 95%.
section_name: Conclusions

section_name: Acknowledgments

section_content: Work partially supported through the EU 7th Framework Programme grant tranScriptorium (Ref: 600707 ), by the Spanish MEC under the STraDA research project ( TIN2012-37475-C02-01 ) and by the Generalitat Valenciana under grant Prometeo/2009/014.
section_name: Acknowledgments