A study on linear discriminative learning algorithms for data dimensionality reduction

Abstract

Dealing with high-dimensional data has always been a major problem in applications for pattern recognition and machine learning. Typical applications involving high-dimensional data include face recognition, document categorization and image retrieval. Finding a low-dimensional representation of high-dimensional space, namely, dimensionality reduction is thus of great importance as it can reduce the complexity of the original space by embedding a high-dimensional space into a low-dimensional space while keeping most of the useful information. Among all the dimensionality reduction methods, Linear Discriminant Analysis (LDA) is the most popular method that has been widely used in many classification applications. In this thesis, we focus on the study of an orthogonal variant of LDA, called Trace Ratio criterion based LDA (TR-LDA), regarding theoretical analysis, semi-supervised extensions and applications. In this thesis, we first analyze the trace ratio problem and propose a new efficient algorithm to find an optimal solution of TR-LDA. Since there is no close-form solution for solving TR-LDA, the optimal solution of TR-LDA can only be calculated by an iterative process. However, currently existing algorithms for solving TR-LDA suffer from the drawback that the convergence of the iterative process is too slow causing very high computational complexity. To overcome the drawback, we analyze the basic strategies of currently existing algorithms for solving TR-LDA. We then improve them in both initialization and training strategies. The proposed algorithm is to use the greedy search to find the optimal solution of TR-LDA, which is more efficient than the existing ones. The original TR-LDA is supervised, which means it can only use labeled samples, while in most applications, unlabeled samples are sufficient to be used for enhancing the performance of TR-LDA. To handle unlabeled samples, we derive an orthogonal constrained semi-supervised framework. Based on this framework, we then extend TR-LDA to its semi-supervised version, called Trace Ratio criterion based Semi-supervised Discriminant Analysis (TR-SDA), by adding the graph Laplacian matrix associated with both labeled and unlabeled samples to the original objective function of TR-LDA. As a result, TR-SDA can find an optimal low-dimensional projection matrix by preserving the discriminative structure embedded in the labeled set as well as the geometric structure embedded in both the labeled and unlabeled sets. In addition to TR-SDA, we propose a semi-supervised dimensionality reduction, called SL-LDA, to enhance the conventional LDA performance by incorporating the soft labels into the scatter matrixes. The proposed method first propagates the label information from labeled set to unlabeled set via label propagation, where the predicted class labels of unlabeled samples, called soft labels, can be obtained. It then finds a transformed matrix to perform dimensionality reduction by incorporating the soft labels into the scatter matrixes. Its basic ideas are different from TR-SDA, which uses the labeled and unlabeled samples in a simple manner to construct a manifold regularized term and add it to the objective function of TR-LDA. In SL-LDA, by incorporating the soft labels into training, it can well preserve the more discriminative information embedded in the labeled and unlabeled sets hence obtaining a better subspace for dimensionality reduction. Finally, we apply TR-LDA to motor bearing fault diagnosis and medical diagnosis in the study of dementia. Since both applications require a large amount of data with features for describing the working condition of motors and symptoms of patients, they can be transformed into pattern recognition problems with high-dimensional dataset. In this way, we can use TR-LDA for feature extraction on the real motor datasets and official dementia dataset. Extensive simulations have verified the effectiveness of TR-LDA.

Date of Award	15 Feb 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Wai Shing Tommy CHOW (Supervisor)