Do unbalanced data have a negative effect on LDA?

For two-class discrimination, Xie and Qiu [The effect of imbalanced data sets on LDA: a theoretical and empirical analysis, Pattern Recognition 40 (2) (2007) 557–562] claimed that, when covariance matrices of the two classes were unequal, a (class) unbalanced data set had a negative effect on the performance of linear discriminant analysis (LDA). Through re-balancing 10 real-world data sets, Xie and Qiu [The effect of imbalanced data sets on LDA: a theoretical and empirical analysis, Pattern Recognition 40 (2) (2007) 557–562] provided empirical evidence to support the claim using AUC (Area Under the receiver operating characteristic Curve) as the performance metric. We suggest that such a claim is vague if not misleading, there is no solid theoretical analysis presented in Xie and Qiu [The effect of imbalanced data sets on LDA: a theoretical and empirical analysis, Pattern Recognition 40 (2) (2007) 557–562], and AUC can lead to a quite different conclusion from that led to by misclassification error rate (ER) on the discrimination performance of LDA for unbalanced data sets. Our empirical and simulation studies suggest that, for LDA, the increase of the median of AUC (and thus the improvement of performance of LDA) from re-balancing is relatively small, while, in contrast, the increase of the median of ER (and thus the decline in performance of LDA) from re-balancing is relatively large. Therefore, from our study, there is no reliable empirical evidence to support the claim that a (class) unbalanced data set has a negative effect on the performance of LDA. In addition, re-balancing affects the performance of LDA for data sets with either equal or unequal covariance matrices, indicating that having unequal covariance matrices is not a key reason for the difference in performance between original and re-balanced data.     

Group recursive discriminant subspace learning with image set decomposition

Discriminant subspace learning is a widely used feature extraction technique for image recognition, since it can extract effective discriminant features by employing the class information and Fisher criterion. A crucial research topic on this technique is how to rapidly extract sufficient and effective features. Recently, recursive discriminant subspace learning technique has attracted lots of research interest because it can acquire sufficient discriminant features. Generally, it recursively decomposes image samples and extracts features from a number of decomposed sample sets. The major drawback of most recursive discriminant subspace learning methods is that they calculate the projective vectors one by one, such that they suffer from big computational costs. The recursive modified linear discriminant method and the incremental recursive Fisher linear discriminant method employ a simple solution for this problem, which calculates the class number minus one projective vectors in each recursion. However, this solution produces the unfavorable projective vectors with poor discriminant capabilities, and it cannot provide the terminating criterion for recursive computation and make the projective vectors orthogonal. In this paper, we propose a novel recursive learning approach that is group recursive discriminant subspace learning, which can rapidly learn multiple orthogonal subspaces with each spanned by a group of projective vectors. And we present a rule to select favorable projective vectors per recursion and provide a matrix-form-based terminating criterion to determine the number of recursions. Experiments on three widely used databases demonstrate the effectiveness and efficiency of the proposed approach.     

On optimal pairwise linear classifiers for normal distributions:the two-dimensional case

Optimal Bayesian linear classifiers have been studied in the literature for many decades. We demonstrate that all the known results consider only the scenario when the quadratic polynomial has coincident roots. Indeed, we present a complete analysis of the case when the optimal classifier between two normally distributed classes is pairwise and linear. We focus on some special cases of the normal distribution with nonequal covariance matrices. We determine the conditions that the mean vectors and covariance matrices have to satisfy in order to obtain the optimal pairwise linear classifier. As opposed to the state of the art, in all the cases discussed here, the linear classifier is given by a pair of straight lines, which is a particular case of the general equation of second degree. We also provide some empirical results, using synthetic data for the Minsky's paradox case, and demonstrated that the linear classifier achieves very good performance. Finally, we have tested our approach on real life data obtained from the UCI machine learning repository. The empirical results that we obtained show the superiority of our scheme over the traditional Fisher's discriminant classifier     

具有统计不相关性的最佳鉴别特征空间的维数定理

提出并严格证明了具有统计不相关性的最佳鉴别特征空间的维数定理：对含有L个类别的模式识别问题，具有统计不相关性的最佳鉴别特征空间的维数为（L－1）：说明了具有统计不相关性的最佳鉴别变的与Wilks所提出的经典的模式特征抽取方法的关系。在一定的条件下，具有统计不相害性的最佳鉴别矢量集等价于Wilks所提出的经典鉴别矢量集。经典的模式特征抽取方法可以用来在不损失任何Fisher鉴别信息的意义下，对含有L个类别的模式识别问题。抽取（L－1）个具有统计不相关性的最佳鉴别特征。     

An optimal symmetrical null space criterion of Fisher discriminant for feature extraction and recognition

Linear discriminant analysis (LDA) is one of the most effective feature extraction methods in statistical pattern recognition, which extracts the discriminant features by maximizing the so-called Fisher’s criterion that is defined as the ratio of between-class scatter matrix to within-class scatter matrix. However, classification of high-dimensional statistical data is usually not amenable to standard pattern recognition techniques because of an underlying small sample size (SSS) problem. A popular approach to the SSS problem is the removal of non-informative features via subspace-based decomposition techniques. Motivated by this viewpoint, many elaborate subspace decomposition methods including Fisherface, direct LDA (D-LDA), complete PCA plus LDA (C-LDA), random discriminant analysis (RDA) and multilinear discriminant analysis (MDA), etc., have been developed, especially in the context of face recognition. Nevertheless, how to search a set of complete optimal subspaces for discriminant analysis is still a hot topic of research in area of LDA. In this paper, we propose a novel discriminant criterion, called optimal symmetrical null space (OSNS) criterion that can be used to compute the Fisher’s maximal discriminant criterion combined with the minimal one. Meanwhile, by the reformed criterion, the complete symmetrical subspaces based on the within-class and between-class scatter matrices are constructed, respectively. Different from the traditional subspace learning criterion that derives only one principal subspace, in our approach two null subspaces and their orthogonal complements were all obtained through the optimization of OSNS criterion. Therefore, the algorithm based on OSNS has the potential to outperform the traditional LDA algorithms, especially in the cases of small sample size. Experimental results conducted on the ORL, FERET, XM2VTS and NUST603 face image databases demonstrate the effectiveness of the proposed method.     

On an extended fisher criterion for feature selection

This correspondence considers the extraction of features as a task of linear transformation of an initial pattern space into a new space, optimal with respect to discriminating the data. A solution of the feature extraction problem is given for two multivariate normal distributed pattern classes using an extended Fisher criterion as the distance measure. The introduced distance measure consists of two terms. The first term estimates the distance between classes upon the difference of mean vectors of classes and the second one upon the difference of class covariance matrices. The proposed method is compared to some of the more popular alternative methods: Fukunaga-Koontz method and Foley-Sammon method.     

A novel Bayesian logistic discriminant model: An application to face recognition

The linear discriminant analysis (LDA) is a linear classifier which has proven to be powerful and competitive compared to the main state-of-the-art classifiers. However, the LDA algorithm assumes the sample vectors of each class are generated from underlying multivariate normal distributions of common covariance matrix with different means (i.e., homoscedastic data). This assumption has restricted the use of LDA considerably. Over the years, authors have defined several extensions to the basic formulation of LDA. One such method is the heteroscedastic LDA (HLDA) which is proposed to address the heteroscedasticity problem. Another method is the nonparametric DA (NDA) where the normality assumption is relaxed. In this paper, we propose a novel Bayesian logistic discriminant (BLD) model which can address both normality and heteroscedasticity problems. The normality assumption is relaxed by approximating the underlying distribution of each class with a mixture of Gaussians. Hence, the proposed BLD provides more flexibility and better classification performances than the LDA, HLDA and NDA. A subclass and multinomial versions of the BLD are proposed. The posterior distribution of the BLD model is elegantly approximated by a tractable Gaussian form using variational transformation and Jensen's inequality, allowing a straightforward computation of the weights. An extensive comparison of the BLD to the LDA, support vector machine (SVM), HLDA, NDA and subclass discriminant analysis (SDA), performed on artificial and real data sets, has shown the advantages and superiority of our proposed method. In particular, the experiments on face recognition have clearly shown a significant improvement of the proposed BLD over the LDA.     

Learning the kernel matrix by maximizing a KFD-based class separability criterion

The advantage of a kernel method often depends critically on a proper choice of the kernel function. A promising approach is to learn the kernel from data automatically. In this paper, we propose a novel method for learning the kernel matrix based on maximizing a class separability criterion that is similar to those used by linear discriminant analysis (LDA) and kernel Fisher discriminant (KFD). It is interesting to note that optimizing this criterion function does not require inverting the possibly singular within-class scatter matrix which is a computational problem encountered by many LDA and KFD methods. We have conducted experiments on both synthetic data and real-world data from UCI and FERET, showing that our method consistently outperforms some previous kernel learning methods.     

SVM-based feature extraction for face recognition

The primary goal of linear discriminant analysis (LDA) in face feature extraction is to find an effective subspace for identity discrimination. The introduction of kernel trick has extended the LDA to nonlinear decision hypersurface. However, there remained inherent limitations for the nonlinear LDA to deal with physical applications under complex environmental factors. These limitations include the use of a common covariance function among each class, and the limited dimensionality inherent to the definition of the between-class scatter. Since these problems are inherently caused by the definition of the Fisher's criterion itself, they may not be solvable under the conventional LDA framework. This paper proposes to adopt a margin-based between-class scatter and a regularization process to resolve the issue. Essentially, we redesign the between-class scatter matrix based on the SVM margins to facilitate an effective and reliable feature extraction. This is followed by a regularization of the within-class scatter matrix. Extensive empirical experiments are performed to compare the proposed method with several other variants of the LDA method using the FERET, AR, and CMU-PIE databases.     

LDA算法及其在人脸识别中的应用

线性特征提取在人脸识别中的应用非常广泛,LDA是其主要方法之一,它基于Fisher 判别准则,然而,当人脸训练样本数小于人脸样本向量的维数时,变换矩阵将无法直接得到,因此线性判别分析过程失效。采用了一种改进的基于Fisher 准则的LDA方法,针对小样本问题提出了一种有效地解决类内散布矩阵奇异的方法,而且用ORL人脸数据进行了实验验证。实验证明该方法在正确识别率方面表现突出。     

Linear dimensionality reduction via a heteroscedastic extension of LDA: the Chernoff criterion

We propose an eigenvector-based heteroscedastic linear dimension reduction (LDR) technique for multiclass data. The technique is based on a heteroscedastic two-class technique which utilizes the so-called Chernoff criterion, and successfully extends the well-known linear discriminant analysis (LDA). The latter, which is based on the Fisher criterion, is incapable of dealing with heteroscedastic data in a proper way. For the two-class case, the between-class scatter is generalized so to capture differences in (co)variances. It is shown that the classical notion of between-class scatter can be associated with Euclidean distances between class means. From this viewpoint, the between-class scatter is generalized by employing the Chernoff distance measure, leading to our proposed heteroscedastic measure. Finally, using the results from the two-class case, a multiclass extension of the Chernoff criterion is proposed. This criterion combines separation information present in the class mean as well as the class covariance matrices. Extensive experiments and a comparison with similar dimension reduction techniques are presented.     

广义主分量分析及人脸识别

传统的主分量分析和Fisher线性鉴别分析在处理图像识别问题时都是基于图像向量的。该文提出了一种直接基于图像矩阵的主分量分析方法,它的突出优点是大大加快了特征抽取的速度。在ORL标准人脸库上的试验结果表明,该文所提出的方法不仅在识别性能上优于传统的主分量分析方法和Fisher线性鉴别分析方法,而且特征抽取的速度得到了很大的提高。     

一种新的基于高斯混合模型的线性判别分析

Fisher准则函数的前提条件就是假设每类样本数据满足单峰高斯分布,即各类样本在模式空间的分布近似椭球状,但是当训练样本数据较多且呈多峰分布时,传统的Fisher准则函数并不能准确反映样本数据的分布,显然基于Fisher准则函数的线性判别分析得到的最优判别矢量集也不是最优的。针对这种情况,通过引入高斯混合模型的概念,提出了一种新的基于高斯混合模型的线性判别分析方法,同时也给出了在该模型下的最优判别矢量集的直接求解方法,并通过实验证明了该算法的有效性。     

Kernel quadratic discriminant analysis for small sample size problem

It is generally believed that quadratic discriminant analysis (QDA) can better fit the data in practical pattern recognition applications compared to linear discriminant analysis (LDA) method. This is due to the fact that QDA relaxes the assumption made by LDA-based methods that the covariance matrix for each class is identical. However, it still assumes that the class conditional distribution is Gaussian which is usually not the case in many real-world applications. In this paper, a novel kernel-based QDA method is proposed to further relax the Gaussian assumption by using the kernel machine technique. The proposed method solves the complex pattern recognition problem by combining the QDA solution and the kernel machine technique, and at the same time, tackles the so-called small sample size problem through a regularized estimation of the covariance matrix. Extensive experimental results indicate that the proposed method is a more sophisticated solution outperforming many traditional kernel-based learning algorithms.     

基于粒子群算法的LDA实现方法研究

针对传统线性判别分析方法存在的问题,在研究现有理论成果的基础上,提出一种新的LDA实现方法。该方法首先对原有的Fisher准则进行修正,然后通过迭代搜寻最佳鉴别矢量,最后对获取的鉴别矢量进行比较分析。在标准的JAFFE人脸库上的表情识别和地区综合消费水平的评价中的实验结果表明,此算法不仅具有良好的识别效果而且还可以突破样本维数的限制;与其他LDA算法相比,该算法更具灵活性且更易于实现。     

Modeling inverse covariance matrices by expansion of tied basis matrices for online handwritten Chinese character recognition

The state-of-the-art modified quadratic discriminant function (MQDF) based approach for online handwritten Chinese character recognition (HCCR) assumes that the feature vectors of each character class can be modeled by a Gaussian distribution with a mean vector and a full covariance matrix. In order to achieve a high recognition accuracy, enough number of leading eigenvectors of the covariance matrix have to be retained in MQDF. This paper presents a new approach to modeling each inverse covariance matrix by basis expansion, where expansion coefficients are character-dependent while a common set of basis matrices are shared by all the character classes. Consequently, our approach can achieve a much better accuracy–memory tradeoff. The usefulness of the proposed approach to designing compact HCCR systems has been confirmed and demonstrated by comparative experiments on popular Nakayosi and Kuchibue Japanese character databases.     

Speed up kernel discriminant analysis

Linear discriminant analysis (LDA) has been a popular method for dimensionality reduction, which preserves class separability. The projection vectors are commonly obtained by maximizing the between-class covariance and simultaneously minimizing the within-class covariance. LDA can be performed either in the original input space or in the reproducing kernel Hilbert space (RKHS) into which data points are mapped, which leads to kernel discriminant analysis (KDA). When the data are highly nonlinear distributed, KDA can achieve better performance than LDA. However, computing the projective functions in KDA involves eigen-decomposition of kernel matrix, which is very expensive when a large number of training samples exist. In this paper, we present a new algorithm for kernel discriminant analysis, called Spectral Regression Kernel Discriminant Analysis (SRKDA). By using spectral graph analysis, SRKDA casts discriminant analysis into a regression framework, which facilitates both efficient computation and the use of regularization techniques. Specifically, SRKDA only needs to solve a set of regularized regression problems, and there is no eigenvector computation involved, which is a huge save of computational cost. The new formulation makes it very easy to develop incremental version of the algorithm, which can fully utilize the computational results of the existing training samples. Moreover, it is easy to produce sparse projections (Sparse KDA) with a L ₁-norm regularizer. Extensive experiments on spoken letter, handwritten digit image and face image data demonstrate the effectiveness and efficiency of the proposed algorithm.     

Discriminative features for text document classification

Abstract The bag-of-words approach to text document representation typically results in vectors of the order of 5000–20,000 components as the representation of documents. To make effective use of various statistical classifiers, it may be necessary to reduce the dimensionality of this representation. We point out deficiencies in class discrimination of two popular such methods, Latent Semantic Indexing (LSI), and sequential feature selection according to some relevant criterion. As a remedy, we suggest feature transforms based on Linear Discriminant Analysis (LDA). Since LDA requires operating both with large and dense matrices, we propose an efficient intermediate dimension reduction step using either a random transform or LSI. We report good classification results with the combined feature transform on a subset of the Reuters-21578 database. Drastic reduction of the feature vector dimensionality from 5000 to 12 actually improves the classification performance.An erratum to this article can be found at     

An improved discriminative common vectors and support vector machine based face recognition approach

An improved discriminative common vectors and support vector machine based face recognition approach is proposed in this paper. The discriminative common vectors (DCV) algorithm is a recently addressed discriminant method, which shows better face recognition effects than some commonly used linear discriminant algorithms. The DCV is based on a variation of Fisher’s Linear Discriminant Analysis for the small sample size case. However, for multiclass problem, the Fisher criterion is clearly suboptimal. We design an improved discriminative common vector by adjustment for the Fisher criterion that can estimate the within-class and between-class scatter matrices more accurately for classification purposes. Then we employ support vector machine as the classifier due to its higher classification and higher generalization. Testing on two public large face database: ORL and AR database, the experimental results demonstrate that the proposed method is an effective face recognition approach, which outperforms several representative recognition methods.     

Discriminative common vectors for face recognition

In face recognition tasks, the dimension of the sample space is typically larger than the number of the samples in the training set. As a consequence, the within-class scatter matrix is singular and the linear discriminant analysis (LDA) method cannot be applied directly. This problem is known as the "small sample size" problem. In this paper, we propose a new face recognition method called the discriminative common vector method based on a variation of Fisher's linear discriminant analysis for the small sample size case. Two different algorithms are given to extract the discriminative common vectors representing each person in the training set of the face database. One algorithm uses the within-class scatter matrix of the samples in the training set while the other uses the subspace methods and the Gram-Schmidt orthogonalization procedure to obtain the discriminative common vectors. Then, the discriminative common vectors are used for classification of new faces. The proposed method yields an optimal solution for maximizing the modified Fisher's linear discriminant criterion given in the paper. Our test results show that the discriminative common vector method is superior to other methods in terms of recognition accuracy, efficiency, and numerical stability.