A supervised non-linear dimensionality reduction approach for manifold learning
Highlights
► We propose a novel supervised non-linear dimensionality reduction (DR) approach that adopts the large margin concept. ► The approach adaptively estimates the local neighborhood surrounding each sample based on local density and similarity. ► It maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other. ► For validation purposes, we applied our method to the face recognition problem. ► Results obtained on six face data sets show that our approach outperforms many recent linear and non-linear DR techniques.
Introduction
In recent years, a new family of non-linear dimensionality reduction techniques for manifold learning has emerged. The most known ones are: kernel principal component analysis (KPCA) [1], locally linear embedding (LLE) [2], [3], Isomap [4], Supervised Isomap [5], Laplacian Eigenmaps (LE) [6], [7]. This family of non-linear embedding techniques appeared as an alternative to their linear counterparts which suffer of severe limitation when dealing with real-world data: (i) they assume the data lie in an Euclidean space and (ii) they may fail when the number of samples is too small. On the other hand, the non-linear dimensionality techniques are able to discover the intrinsic data structure by exploiting the local topology. In general, they attempt to optimally preserve the local geometry around each data sample while using the rest of the samples to preserve the global structure of the data.
In this paper we introduce a novel Supervised LE (S-LE) algorithm, which exploits the class label information for mapping the original data in the embedded space. The use of labels allows us to split graph Laplacian associated to the data into two components: within-class graph and between-class graph. Our proposed approach benefits from two important properties: (i) it adaptively estimates the local neighborhood surrounding each sample based on data density and similarity and (ii) the objective function simultaneously maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other. The main contributions of our work are as follows: (1) bypassing the use and selection of a predefined neighborhood for graph construction and (2) exploiting the discriminant information in order to get the non-linear embedding (spectral projection).
The combination between locality preserving property (inherited from the classical LE1) and the discriminative property (due to the large margin concept) represents a clear advantage for S-LE, compared with other non-linear embedding techniques, because it finds a mapping which maximizes the distances between data samples from different classes at each local area. In other words, it maps the points in an embedded space where data with similar labels fall close to each other and where the data from different classes fall far apart.
The adaptive selection of neighbors for the two graphs represents also an added value to our algorithm. It is well known that a sensitive matter affecting non-linear embedding techniques is represented by the proper choice for neighborhood size. Setting a too high value for this parameter would result in a loss of local information, meanwhile a too low value could result in an over-fragmentation of the manifold (problem known as ‘short-circuiting’). For this reason, setting an adequate value for this parameter is crucial in order to confer the approach topological stability.
The rest of the paper is organized as follows. Section 2 reviews some related work on linear and non-linear dimensionality reduction techniques. In this section, we also recall, for the sake of completeness, the classic Laplacian Eigenmaps algorithm. Section 3 is devoted to the presentation of our new proposed algorithm. Section 4 presents extensive experimental results obtained on a man-made object data set and on six face databases. Finally, Section 5 contains our conclusions and guidelines for future work.
Section snippets
Related work
During the last few years, a large number of approaches have been proposed for constructing and computing an embedded subspace by finding an explicit or non-explicit mapping that projects the original data to a new space of lower dimensionality [8], [9], [10]. These methods can be grouped into two families: linear and non-linear approaches.
Supervised Laplacian Eigenmaps
While the LE may give good results for non-linear dimensionality reduction, it has not been widely used and assessed for classification tasks. Indeed, many experiments show that the recognition rate in the embedded space can be highly depending on the choice of the neighborhood size in the reconstructed graph [15], [30], [31]. Choosing the ideal size, K or , in advance can be a very difficult task. Moreover, the introduced mapping by LE does not exploit the discriminant information given by
Experimental results
In this section, we report the experimental results obtained from the application of our proposed algorithm to the problem of visual pattern recognition. Extensive experiments in terms of classification accuracy have been carried out on a man-made object database as well as on some public face databases. All these databases are characterized by a large variation in object appearance.
Conclusions and future work
We proposed a novel supervised non-linear dimensionality reduction technique, namely Supervised Laplacian Eigenmap (S-LE). Our algorithm benefits from two important properties: (i) it adaptively estimates the local neighborhood surrounding each sample based on data density and similarity and (ii) the objective function simultaneously maximizes the local margin between heterogeneous samples and pushes the homogeneous samples closer to each other.
For validation purposes, we applied our method to
Acknowledgment
This work was partially supported by the Spanish Government under the project TIN2010-18856.
Bogdan Raducanu received the B.Sc. degree in computer science from the University “Politehnica” of Bucharest, Bucharest, Romania, in 1995 and the Ph.D. degree “Cum Laude” from the University of the Basque Country, Bilbao, Spain, in 2001. Currently, he is a senior researcher at the Computer Vision Center in Barcelona, Spain. His research interests are: computer vision, pattern recognition, machine learning, artificial intelligence, social computing and human–robot interaction. He is the author
References (38)
- et al.
Incremental Laplacian Eigenmaps by preserving adjacent information between data points
Pattern Recognition Letters
(2009) - et al.
Graph-optimized locality preserving projections
Pattern Recognition
(2010) - et al.
Face recognition using discriminant locality preserving projections
Image and Vision Computing
(2006) - et al.
Quotient vs. difference: comparison between the two discriminant criteria
Neurocomputing
(2010) - et al.
Marginface: a novel face recognition method by average neighborhood margin maximization
Pattern Recognition
(2009) - et al.
LPP solution schemes for use with face recognition
Pattern Recognition
(2010) - et al.
Nonlinear component analysis as a kernel eigenvalue problem
Neural Computation
(1998) - et al.
Nonlinear dimensionality reduction by locally linear embedding
Science
(2000) - et al.
Think globally, fit locally: unsupervised learning of low dimensional manifolds
Journal of Machine Learning Research
(2003) - et al.
A global geometric framework for nonlinear dimensionality reduction
Science
(2000)
Supervised nonlinear dimensionality reduction for visualization and classification
IEEE Transactions on Systems, Man, and Cybernetics-part B: Cybernetics
Laplacian eigenmaps for dimensionality reduction and data representation
Neural Computation
Spectral methods for dimensionality reduction
Graph embedding and extension: a general framework for dimensionality reduction
IEEE Transactions on Pattern Analysis and Machine Intelligence
Patch alignment for dimensionality reduction
IEEE Transactions on Knowledge and Data Engineering
Efficient and robust feature extraction by maximum margin criterion
IEEE Transactions on Neural Networks
Locally linear discriminant analysis for multimodally distributed classes for face recognition with a single model image
IEEE Transactions on Pattern Analysis and Machine Intelligence
Locality preserving projections
Face recognition using Laplacianfaces
IEEE Transactions on Pattern Analysis and Machine Intelligence
Cited by (130)
Semi-supervised imbalanced multi-label classification with label propagation
2024, Pattern RecognitionFast anchor graph preserving projections
2024, Pattern RecognitionSupervised feature selection on gene expression microarray datasets using manifold learning
2023, Chemometrics and Intelligent Laboratory SystemsKnowledge transfer in evolutionary multi-task optimization: A survey
2023, Applied Soft ComputingApplication of adaptive Laplacian Eigenmaps in near infrared spectral modeling
2022, Spectrochimica Acta - Part A: Molecular and Biomolecular SpectroscopyA comparative study on pretreatment methods and dimensionality reduction techniques for energy data disaggregation in home appliances
2022, Advanced Engineering Informatics
Bogdan Raducanu received the B.Sc. degree in computer science from the University “Politehnica” of Bucharest, Bucharest, Romania, in 1995 and the Ph.D. degree “Cum Laude” from the University of the Basque Country, Bilbao, Spain, in 2001. Currently, he is a senior researcher at the Computer Vision Center in Barcelona, Spain. His research interests are: computer vision, pattern recognition, machine learning, artificial intelligence, social computing and human–robot interaction. He is the author or co-author of about 60 publications in international conferences and journals. In 2010, he was the leading Guest Editor of Image and Vision Computing journal for a special issue on ‘Online Pattern Recognition’.
Fadi Dornaika received the Ph.D. in signal, image, and speech processing from the Institut National Polytechnique de Grenoble, France, in 1995. He is currently an Ikerbasque research professor at the University of the Basque Country. He has published more than 130 papers in the field of computer vision. His research concerns geometrical and statistical modelling with focus on 3D object pose, real-time visual servoing, calibration of visual sensors, cooperative stereo-motion, image registration, facial gesture tracking, and facial expression recognition.