Discriminative learning quadratic discriminant function for handwriting recognition

In character string recognition integrating segmentation and classification, high classification accuracy and resistance to noncharacters are desired to the underlying classifier. In a previous evaluation study, the modified quadratic discriminant function (MQDF) proposed by Kimura et al. was shown to be superior in noncharacter resistance but inferior in classification accuracy to neural networks. This paper proposes a discriminative learning algorithm to optimize the parameters of MQDF with aim to improve the classification accuracy while preserving the superior noncharacter resistance. We refer to the resulting classifier as discriminative learning QDF (DLQDF). The parameters of DLQDF adhere to the structure of MQDF under the Gaussian density assumption and are optimized under the minimum classification error (MCE) criterion. The promise of DLQDF is justified in handwritten digit recognition and numeral string recognition, where the performance of DLQDF is comparable to or superior to that of neural classifiers. The results are also competitive to the best ones reported in the literature.     

High accuracy handwritten Chinese character recognition using LDA-based compound distances

To improve the accuracy of handwritten Chinese character recognition (HCCR), we propose linear discriminant analysis (LDA)-based compound distances for discriminating similar characters. The LDA-based method is an extension of previous compound Mahalanobis function (CMF), which calculates a complementary distance on a one-dimensional subspace (discriminant vector) for discriminating two classes and combines this complementary distance with a baseline quadratic classifier. We use LDA to estimate the discriminant vector for better discriminability and show that under restrictive assumptions, the CMF is a special case of our LDA-based method. Further improvements can be obtained when the discriminant vector is estimated from higher-dimensional feature spaces. We evaluated the methods in experiments on the ETL9B and CASIA databases using the modified quadratic discriminant function (MQDF) as baseline classifier. The results demonstrate the superiority of LDA-based method over the CMF and the superiority of discriminant vector learning from high-dimensional feature spaces. Compared to the MQDF, the proposed method reduces the error rates by factors of over 26%.     

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.     

Building compact MQDF classifier for large character set recognition by subspace distribution sharing

Quadratic classifier with modified quadratic discriminant function (MQDF) has been successfully applied to recognition of handwritten characters to achieve very good performance. However, for large category classification problem such as Chinese character recognition, the storage of the parameters for the MQDF classifier is usually too large to make it practical to be embedded in the memory limited hand-held devices. In this paper, we aim at building a compact and high accuracy MQDF classifier for these embedded systems. A method by combining linear discriminant analysis and subspace distribution sharing is proposed to greatly compress the storage of the MQDF classifier from 76.4 to 2.06 MB, while the recognition accuracy still remains above 97%, with only 0.88% accuracy loss. Furthermore, a two-level minimum distance classifier is employed to accelerate the recognition process. Fast recognition speed and compact dictionary size make the high accuracy quadratic classifier become practical for hand-held devices.     

Performance evaluation of pattern classifiers for handwritten character recognition

This paper describes a performance evaluation study in which some efficient classifiers are tested in handwritten digit recognition. The evaluated classifiers include a statistical classifier (modified quadratic discriminant function, MQDF), three neural classifiers, and an LVQ (learning vector quantization) classifier. They are efficient in that high accuracies can be achieved at moderate memory space and computation cost. The performance is measured in terms of classification accuracy, sensitivity to training sample size, ambiguity rejection, and outlier resistance. The outlier resistance of neural classifiers is enhanced by training with synthesized outlier data. The classifiers are tested on a large data set extracted from NIST SD19. As results, the test accuracies of the evaluated classifiers are comparable to or higher than those of the nearest neighbor (1-NN) rule and regularized discriminant analysis (RDA). It is shown that neural classifiers are more susceptible to small sample size than MQDF, although they yield higher accuracies on large sample size. As a neural classifier, the polynomial classifier (PC) gives the highest accuracy and performs best in ambiguity rejection. On the other hand, MQDF is superior in outlier rejection even though it is not trained with outlier data. The results indicate that pattern classifiers have complementary advantages and they should be appropriately combined to achieve higher performance. Received: July 18, 2001 / Accepted: September 28, 2001     

Building compact recognizers of handwritten Chinese characters using precision constrained Gaussian model,minimum classification error training and parameter compression

In our previous work, a so-called precision constrained Gaussian model (PCGM) was proposed for character modeling to design compact recognizers of handwritten Chinese characters. A maximum likelihood training procedure was developed to estimate model parameters from training data. In this paper, we extend the above-mentioned work by using minimum classification error (MCE) training to improve recognition accuracy and using both split vector quantization and scalar quantization techniques to further compress model parameters. Experimental results on a handwritten character recognition task with a vocabulary of 2,965 Kanji characters demonstrate that MCE-trained and compressed PCGM-based classifiers can achieve much higher recognition accuracies than their counterparts based on traditional modified quadratic discriminant function (MQDF) when the footprint of the classifiers has to be made very small, e.g., less than 2 MB.     

联机手写维吾尔文字母识别方法

通过分析维吾尔文字母自身的结构和书写特点,提出一种联机手写维吾尔文字母识别方案,并选择在手写汉字识别技术中所提出来的归一化、特征提取及常用的分类方法,从中找出最佳的技术选择。在实验对比中,采用8种不同的归一化预处理方法,基于坐标归一化的特征提取 (NCFE) 方法,以及改进的二次分类函数(MQDF)、判别学习型二次判别函数(DLQDF)、学习矢量量化(LVQ)、支持向量机(SVM)4种分类器。同时,再考虑字符在文档中的空间几何特征,进一步提高识别性能。在128个维吾尔文字母类别、38 400个测试样本的实验中,正确识别率最高达89。08%,为进一步研究面向维吾尔文字母特性的识别技术奠定重要基础。     

Determination of the optimal number of features for quadratic discriminant analysis via the normal approximation to the discriminant distribution

Given the joint feature-label distribution, increasing the number of features always results in decreased classification error; however, this is not the case when a classifier is designed via a classification rule from sample data. Typically, for fixed sample size, the error of a designed classifier decreases and then increases as the number of features grows. The problem is especially acute when sample sizes are very small and the potential number of features is very large. To obtain a general understanding of the kinds of feature-set sizes that provide good performance for a particular classification rule, performance must be evaluated based on accurate error estimation, and hence a model-based setting for optimizing the number of features is needed. This paper treats quadratic discriminant analysis (QDA) in the case of unequal covariance matrices. For two normal class-conditional distributions, the QDA classifier is determined according to a discriminant. The standard plug-in rule estimates the discriminant from a feature-label sample to obtain an estimate of the discriminant by replacing the means and covariance matrices by their respective sample means and sample covariance matrices. The unbiasedness of these estimators assures good estimation for large samples, but not for small samples.Our goal is to find an essentially analytic method to produce an error curve as a function of the number of features so that the curve can be minimized to determine an optimal number of features. We use a normal approximation to the distribution of the estimated discriminant. Since the mean and variance of the estimated discriminant will be exact, these provide insight into how the covariance matrices affect the optimal number of features. We derive the mean and variance of the estimated discriminant and compare feature-size optimization using the normal approximation to the estimated discriminant with optimization obtained by simulating the true distribution of the estimated discriminant. Optimization via the normal approximation to the estimated discriminant provides huge computational savings in comparison to optimization via simulation of the true distribution. Feature-size optimization via the normal approximation is very accurate when the covariance matrices differ modestly. The optimal number of features based on the normal approximation will exceed the actual optimal number when there is large disagreement between the covariance matrices; however, this difference is not important because the true misclassification error using the number of features obtained from the normal approximation and the number obtained from the true distribution differ only slightly, even for significantly different covariance matrices.     

采用虚拟训练样本的二次判别分析方法

小样本问题会造成各类协方差矩阵的奇异性和不稳定性. 本文采用对训练样本进行扰动的方法来生成虚拟训练样本, 利用这些虚拟训练样本克服了各类协方差矩阵的奇异性问题, 从而可以直接使用二次判别分析 (Quadratic discriminant analysis, QDA) 方法. 本文方法克服了正则化判别分析 (Regularized discriminant analysis, RDA) 需要进行参数优化的问题. 实验结果表明, QDA 的模式识别率优于参数最优化时 RDA 算法的识别率.     

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.     

On dimensionality, sample size, classification error, and complexity of classification algorithm in pattern recognition

This paper compares four classification algorithms-discriminant functions when classifying individuals into two multivariate populations. The discriminant functions (DF's) compared are derived according to the Bayes rule for normal populations and differ in assumptions on the covariance matrices' structure. Analytical formulas for the expected probability of misclassification EPN are derived and show that the classification error EPN depends on the structure of a classification algorithm, asymptotic probability of misclassification P?, and the ratio of learning sample size N to dimensionality p:N/p for all linear DF's discussed and N2/p for quadratic DF's. The tables for learning quantity H = EPN/P? depending on parameters P?, N, and p for four classifilcation algorithms analyzed are presented and may be used for estimating the necessary learning sample size, detennining the optimal number of features, and choosing the type of the classification algorithm in the case of a limited learning sample size.     

On estimation of nonlinear functionals from discrete noisy measurements

The principal objective of this paper is to estimate a nonlinear functional of state vector (NFS) in dynamical system. The NFS represents a multivariate functional of state variables which carries useful information of a target system for control. The paper focuses on estimation of the NFS in linear continuous-discrete systems. The optimal nonlinear estimator based on the minimum mean square error approach is derived. The estimator depends on the Kalman estimate of a state vector and its error covariance. Some challenging computational aspects of the optimal nonlinear estimator are solved by usage of the unscented transformation for implementation of the nonlinear estimator. The special quadratic functional of state vector (QFS) is studied in detail. We derive effective matrix formulas for the optimal quadratic estimator and mean square error. The quadratic estimator has a simple closed-form calculation procedure and it is easy to implement in practice. The obtained results we demonstrate on theoretical and practical examples with different types of an nonlinear functionals. Comparison analysis of the optimal and suboptimal estimators is presented. The subsequent application of the proposed optimal nonlinear and quadratic estimators demonstrates their effectiveness.     

A comparative study of cloud classification techniques

The purpose of this study was to determine the importance of infrared vs. visual features, textural vs. spectral features, hierarchical vs. single-stage decision logic, and quadratic vs. linear discriminant functions for classification of NOAA-1 visible and infrared tropical cloud data. Both a four-class problem, in which cloud types were grouped into (1) “low”, (2) “mix”, (3) “cirrus”, and (4) “cumulonimbus” classes, and a three-class problem, in which the “mix” class was excluded, were analyzed. The addition of at least one visual spectral feature to infrared spectral features improved the ability of the classifier to recognize all cloud classes except “low”. Combining textural features with spectral features did not significantly improve classification results achieved using only spectral features. For the four-class problem, a classification accuracy of 91% was obtained by using a two-stage variation of a single-stage, maximum likelihood classifier. For the three-class problem, classification accuracies of 98% were obtained using either single-stage or hierarchical decision logic and either quadratic or linear discriminant functions.     

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.     

Chinese calligraphic style representation for recognition

Chinese calligraphy draws a lot of attention for its beauty and elegance. The various styles of calligraphic characters make calligraphy even more charming. But it is not always easy to recognize the calligraphic style correctly, especially for beginners. In this paper, an automatic character styles representation for recognition method is proposed. Three kinds of features are extracted to represent the calligraphic characters. Two of them are typical hand-designed features: the global feature, GIST and the local feature, scale invariant feature transform. The left one is deep feature which is extracted by a deep convolutional neural network (CNN). The state-of-the-art classifier modified quadratic discriminant function was employed to perform recognition. We evaluated our method on two calligraphic character datasets, the unconstraint real-world calligraphic character dataset (CCD) and SCL (the standard calligraphic character library). And we also compare MQDF with other two classifiers, support vector machine and neural network, to perform recognition. In our experiments, all three kinds of feature are evaluated with all three classifiers, respectively, finding that deep feature is the best feature for calligraphic style recognition. We also fine-tune the deep CNN (alex-net) in Krizhevsky et al. (Advances in Neural Information Processing Systems, pp. 1097–1105, 2012) to perform calligraphic style recognition. It turns out our method achieves about equal accuracy comparing with the fine-tuned alex-net but with much less training time. Furthermore, the algorithm style discrimination evaluation is developed to evaluate the discriminative style quantitatively.     

Optimizing the data-dependent kernel under a unified kernel optimization framework

The kernel functions play a central role in kernel methods, accordingly over the years the optimization of kernel functions has been a promising research area. Ideally Fisher discriminant criteria can be used as an objective function to optimize the kernel function to augment the margin between different classes. Unfortunately, Fisher criteria are optimal only in the case that all the classes are generated from underlying multivariate normal distributions of common covariance matrix but different means and each class is expressed by a single cluster. Due to the assumptions, Fisher criteria obviously are not a suitable choice as a kernel optimization rule in some applications such as the multimodally distributed data. In order to solve this problem, recently many improved discriminant criteria (DC) have been also developed. Therefore, to apply these discriminant criteria to kernel optimization, in this paper based on a data-dependent kernel function we propose a unified kernel optimization framework, which can use any discriminant criteria formulated in a pairwise manner as the objective functions. Under the kernel optimization framework, to employ different discriminant criteria, one has to only change the corresponding affinity matrices without having to resort to any complex derivations in feature space. Experimental results based on some benchmark data demonstrate the efficiency of our method.     

Tree-Based Covariance Modeling of Hidden Markov Models

In this paper, we present a tree-based, full covariance hidden Markov modeling technique for automatic speech recognition applications. A multilayered tree is built first to organize all covariance matrices into a hierarchical structure. Kullback–Leibler divergence is used in the tree-building to measure inter-Gaussian distortion and successive splitting is used to construct the multilayer covariance tree. To cope with the data sparseness problem in estimating a full covariance matrix, we interpolate the diagonal covariance matrix of a leaf-node at the bottom of the tree with the full covariance of its parent and ancestors along the path up to the root node. The interpolation coefficients are estimated in the maximum likelihood sense via the EM algorithm. The interpolation is performed in three different parametric forms: 1) inverse covariance matrix, 2) covariance matrix, and 3) off-diagonal terms of the full covariance matrix. The proposed algorithm is tested in three different databases: 1) the DARPA Resource Management (RM), 2) the Switchboard, and 3) a Chinese dictation. In all three databases, we show that the proposed tree-based full covariance modeling consistently performs better than the baseline diagonal covariance modeling. The algorithm outperforms other covariance modeling techniques, including: 1) the semi-tied covariance modeling (STC), 2) heteroscedastic linear discriminant analysis (HLDA), 3) mixtures of inverse covariance (MIC), and 4) direct full covariance modeling.     

Stable estimation of a covariance matrix guided by nuclear norm penalties

Estimation of a covariance matrix or its inverse plays a central role in many statistical methods. For these methods to work reliably, estimated matrices must not only be invertible but also well-conditioned. The current paper introduces a novel prior to ensure a well-conditioned maximum a posteriori (MAP) covariance estimate. The prior shrinks the sample covariance estimator towards a stable target and leads to a MAP estimator that is consistent and asymptotically efficient. Thus, the MAP estimator gracefully transitions towards the sample covariance matrix as the number of samples grows relative to the number of covariates. The utility of the MAP estimator is demonstrated in two standard applications–discriminant analysis and EM clustering–in challenging sampling regimes.     

Improved Stein-type shrinkage estimators for the high-dimensional multivariate normal covariance matrix

Many applications require an estimate for the covariance matrix that is non-singular and well-conditioned. As the dimensionality increases, the sample covariance matrix becomes ill-conditioned or even singular. A common approach to estimating the covariance matrix when the dimensionality is large is that of Stein-type shrinkage estimation. A convex combination of the sample covariance matrix and a well-conditioned target matrix is used to estimate the covariance matrix. Recent work in the literature has shown that an optimal combination exists under mean-squared loss, however it must be estimated from the data. In this paper, we introduce a new set of estimators for the optimal convex combination for three commonly used target matrices. A simulation study shows an improvement over those in the literature in cases of extreme high-dimensionality of the data. A data analysis shows the estimators are effective in a discriminant and classification analysis.     

Discriminant analysis using certain normed exponential densities with emphasis on remote sensing application

The Bayes discriminant analysis based upon the normality assumption for population models does not lead to an exact evaluation of probabilities of correct classification and of misclassification unless it is restricted to a simplest possible situation. In order to overcome this and other computational difficulties that one faces in a complex situation such as the remote sensing, certain alternative densities are posed as models for the observations. It is shown that for a Bayes discriminant analysis these densities lead to piecewise linear discriminant functions even when the covariance matrices are unequal (a property not enjoyed in the normal case) and provide a theoretical solution for evaluating probabilities of correct classification and of misclassification. Also, some computational advantages are achieved.