Recently, a new kind of feature extraction method, manifold learning algorithms, based on the local geometry analysis have drawn much attention. Unlike PCA, which aims to preserve the global Euclidean structure of the data space, manifold learning algorithms aim to preserve the inherent manifold structure. Locally linear embedding (LLE), Isomap, Laplacian eigenmap, and locality preserving projection (LPP)1 are the most important manifold learning algorithms. All of these four algorithms attempt to embed the original data into a submanifold by preserving the local neighborhood structure. They are based on the assumption that the manifold’s intrinsic geometry can be fully determined by the local metric and the neighborhood information. Different from LLE, Isomap, and Laplacian eigenmap, LPP is a linear algorithm. It is quite simple and easy to realize. LPP is originally derived by the discretely approximation of the Laplace Beltrami operator on compact Rimannian manifold. He 1 have applied LPP on face recognition problem. The application has shown the effectiveness of LPP in discovering the the intrinsic geometrical structure of the data.
Based on LPP, we propose a novel algorithm, called uncorrelated locality preserving projection (ULPP). It shares the same locality preserving character as LPP, but at the same time it requires the basis vectors to be statistically uncorrelated. Uncorrelated attributes are highly desirable in pattern analysis, because they contain minimum redundancy.2 However, the basis vectors of LPP are statistically correlated, then the extracted features contain redundant information. Moreover, the overlapped information can distort the distribution of the features and even dramatically degrade the performance of LPP. In this paper, we overcome this problem by putting an uncorrelated constraint on the computation of the basis vectors. This makes the proposed ULPP algorithm much more robust.
Locality Preserving Projection
LPP1 can be explained by spectral graph theory. Let us assume that the -dimensional data set is distributed on a low-dimensional submanifold. We desire to find a set of -dimensional data points with the same local neighborhood structure as the data . In order to do so, we can construct a weighted graph , where is the set of all points; is the set of edges connecting the points; and is a similarity matrix with weights characterizing the likelihood of two points. The criterion function of LPP is as follows:
To make the mapping (embedding) not defined only for the original data set, LPP defines a transformation. That is, , where . Following some algebraic steps, we see that, and ; its entries are row (or column since is symmetric) sums of , ; returns a block diagonal matrix with block entry x. is the Laplacian matrix.1
In order to remove the arbitrary scaling factor in the embedding, LPP imposes a constraint as follows:
The transformation matrix that minimizes the objective function can be obtained by solving the generalized eigenvalue problem:1
Based on the matrix , for any instance , we can define the following linear transform from to :
Theorem 1: Any two features and in Eq. 6 are correlated.
Proof: Let the covariance matrix of the data be . It is easy to obtain the following equation:3, we have inequality, in general,
Uncorrelated Locality Preserving Projection
The algorithmic procedure of uncorrelated locality preserving projection (ULPP) is stated below:
1. Perform PCA projection. We project the data set into a PCA subspace to make the matrix become nonsingular. Let the transformation matrix of PCA be .
2. Construct the similarity of any two data points. For each sample , if is among the -nearest neighbors of , set the similarity ; otherwise, set the similarity . The similarity reflects the local structure of the data space.
3. Obtain the diagonal matrix and the Laplacian matrix .
4. Compute the uncorrelated locality preserving projections. Let , and for concision. Let be the uncorrelated locality preserving projections, thus we define
The uncorrelated locality preserving projections can be iteratively computed as follows:
5. Perform the ULPP transformation. Let . The embedding is as follow:is a -dimensional representation of and .
In this subsection, we provide the justification of our algorithm.
According to the following theorem, we can compute the uncorrelated direction as the eigenvector of [Eq. 12] associated with the the smallest eigenvalue of .
Theorem 2: The uncorrelated direction is the eigenvector corresponding to the smallest eigenvalue of the following eigenfunction:
Proof: Recall the minimization problem of LPP:uncorrelated direction , we add the constraints and , we have with respect to equal to zero:15 by , we have represents minimization problem to be optimized.
Multiplying the left-hand side of Eq. 15, respectively, by , we have, thus we can obtain15 can be written as18 into Eq. 19, we have
Experiments on FERET Data Set
FERET3 is a very popular database. Face image variations in the FERET database include pose, illumination, facial expression, and aging. In our experiment, we use a subset of the FERET data set. The data set we selected contains 72 people and 6 images for each individual. All images are aligned by the centers of the eyes and mouth and then scaled with resolution . We randomly select 3 images from each person for training, while the rest of the images of each individual are selected for testing. The experiments are repeated 20 times and the average accuracies of rank 1 to rank 3 are recorded and shown in Table 1. The results show ULPP gives the best performance. The recognition accuracy of ULPP increases from 85.90% with rank 1 to 91.07% with rank 3, which is about 10% higher than the recognition accuracy of LPP.
Recognition accuracies (%) comparison of FERET data set.
Experiments on AR Data Set
AR4 is also a popular database. Face image variations in the AR database include illumination, facial expression, and occlusion. In our experiment, 952 images (119 individuals, 8 images per person), which involve large variations in facial expression, are selected. We manually cropped the face portion of the images. All the cropped images are aligned at the centers of eyes and mouth and then normalized with resolution . We randomly select 4 images from each person for training, while the rest of the images of each individual are selected for testing. The experiments are repeated 30 times and the average accuracies of rank 1 to rank 3 are recorded and shown in Table 2. From Table 2, it can be seen that ULPP outperforms the other two methods. The recognition accuracy of ULPP increases from 80.32% with rank 1 to 86.51% with rank 3, which is about 5% higher than the recognition accuracy of LPP.
Recognition accuracies (%) comparison on AR data set.
This paper presents a novel feature extraction method, called uncorrelated locality preserving projection (ULPP). ULPP can extract uncorrelated features which contain minimum redundancy and are highly desirable for many applications. In this paper, we present a theoretical study on ULPP and provide an implementation of it. The experiments on face image data show the superiority of ULPP over the other both PCA and LPP.
This project is partially supported by National Natural Science Foundation of China (60502042) and 2010 Shanghai EXPO Special Project (2004BA908B07, 04DZ05807).