Chinese Journal of Computers   Full Text
Title	Localized Proximal Support Vector Machine via Generalized Eigenvalues
Authors	YANG Xu-Bing1) CHEN Song-Can1) YANG Yi-Min2)
Address	1)(College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics, Naning 210016) 2)(Department of Statistics, Nanjing University of Finance and Economics, Nanjing 210003)
Year	2007
Issue	No.8(1227—1234)
Abstract &   Background	Abstract A binary classifier termed as proximal support vector machine via generalized eigenvalues(GEPSVM), is proposed recently. It aims to obtain two nonparallel planes generated from their corresponding generalized eigenvalue problem and has equivalent test correctness to SVM. In nature, GEPSVM attempts fitting two-class points with two planes. For an unseen sample, according to decision rule of GEPSVM, it will be assigned to the closest planes. In fact, this rule, in most cases, may result in poor test correctness. In this paper, based on GEPSVM, a new classifier named Localized GEPSVM is presented. Instead of two fitting planes, an unknown sample will be classified to the closest localized planes, i.e., convex hull, which are generated from the projections of two-class training points, respectively. Compared to GEPSVM, LGEPSVM outperforms GEPSVM in test correctness. Derivatively, LGEPSVM also develops an algorithm for solving convex hull on the projective hyperplane. Besides simple geometrical interpretation, this algorithm eases up to kernel version. Finally, Test accuracy of LGEPSVM algorithms will be validated on some artificial and real UCI datasets. keywords proximal support vector machine; generalized eigenvalues; convex hull; localization; classification background This work is supported by two National Natural Science Foundation projects of China (grant Nos.60473035 and 70671052). The former project is "Enhanced Linear Discriminant Analysis and its Generalization". Due to its simplicity and efficiency, linear discriminant analysis (LDA) has shown its outstanding classification performance and effective dimension-reduction in many applications such as handwritten digit recognition, face detection in image, text categorization and target tracking. However, there are also many embarrassments in LDA, such as singularity of scatter matrix, single training sample each class, limitation problem of rank and so on. To breakthrough the foresaid limits, the authors have directly defined new optimization criterion to widen application range of LDA. Nowadays, another popular linear classifier, support vector machine (SVM) is based on the structural risk minimization (SRM) principle and aims at maximizing the margin between the points of two-class data classification. However, SVM requires a solution of quadratic programming (QP) problem. Recently, Fung and Mangasarian introduced a proximal SVM (PSVM), which replaces inequality with equality constraints of the SVM framework. In doing so, the authors claim that the computational complexity can be greatly decreased without resulting in discernible loss of classification accuracy. Furthermore, PSVM classifies two-class points to the closest of two parallel planes that are pushed apart as far as possible. With similar starting point in defining objective function of LDA, Proximal support vector via generalized eigenvalue (GEPSVM) can be interpreted as replacing class centers of LDA with proximal planes. In a viewpoint of proximal planes, GEPSVM is another version of PSVM, in which only a set of linear algebra problem needs to be solved instead of a QP problem of traditional SVM. Its proximal planes are generated by a generalized eigenvalue problem such that GEPSVM is superior to SVM in computational time but has still comparable test correctness. The latter project is "Topology Synthesis of Evaluating Statistical Index Architecture and Generating Projection Set to be Evaluated", which aims to construct a new mechanism to evaluate classifier’ performance in statistical comparison. For an unseen test point, according to decision rule of GEPSVM, it is assigned to that class of its closest plane. However, this rule, even in linear-separable cases, may result in poor test correctness, i.e., generalization. In this paper, based on GEPSVM, a new classifier termed as Localized GEPSVM (LGEPSVM) is present. Instead of two proximal planes, an unknown sample is classified to the closest localized planes, i.e., convex hulls, which are generated from the projection of two-class training points, respectively. In addition to reporting the average accuracies, the authors performed paired t-tests comparing LGEPSVM to GEPSVM. In most real datasets here, LGEPSVM outperforms GEPSVM in test accuracy. Derivatively, LGEPSVM is also used to develop an algorithm for solving minimal convex hull on the projection hyperplane which can solve subclass classification and piecewise linear regression problems etc.