×

Graph-optimized locality preserving projections. (English) Zbl 1191.68611

Summary: Locality preserving projections (LPP) is a typical graph-based dimensionality reduction (DR) method, and has been successfully applied in many practical problems such as face recognition. However, LPP depends mainly on its underlying neighborhood graph whose construction suffers from the following issues: (1) such neighborhood graph is artificially defined in advance, and thus does not necessary benefit subsequent DR task; (2) such graph is constructed using the nearest neighbor criterion which tends to work poorly due to the high-dimensionality of original space; (3) it is generally uneasy to assign appropriate values for the neighborhood size and heat kernel parameter involved in graph construction. To address these problems, we develop a novel DR algorithm called graph-optimized locality preserving projections (GoLPP). The idea is to integrate graph construction with specific DR process into a unified framework, which results in an optimized graph rather than predefined one. Moreover, an entropy regularization term is incorporated into the objective function for controlling the uniformity level of the edge weights in graph, so that a principled graph updating formula naturally corresponding to conventional heat kernel weights can be obtained. Finally, the experiments on several publicly available UCI and face data sets show the feasibility and effectiveness of the proposed method with encouraging results.

MSC:

68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.B. Tenenbaum, Mapping a manifold or perceptual observations, in: Proceedings of Neural Information Processing Systems (NIPS), 1998.; J.B. Tenenbaum, Mapping a manifold or perceptual observations, in: Proceedings of Neural Information Processing Systems (NIPS), 1998.
[2] Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326 (2000)
[3] Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation, 15, 6, 1373-1396 (2003) · Zbl 1085.68119
[4] X.F. He, D. Cai, S.C. Yan, H.J. Zhang, Neighborhood preserving embedding, in: Proceedings of IEEE International Conference on Computer Vision (ICCV), 2005.; X.F. He, D. Cai, S.C. Yan, H.J. Zhang, Neighborhood preserving embedding, in: Proceedings of IEEE International Conference on Computer Vision (ICCV), 2005.
[5] X.F. He, P. Niyogi, Locality preserving projections, in: Proceedings of Neural Information Processing Systems (NIPS), 2003.; X.F. He, P. Niyogi, Locality preserving projections, in: Proceedings of Neural Information Processing Systems (NIPS), 2003.
[6] Yan, S. C.; Xu, D.; Zhang, B. Y.; Zhang, H. J.; Yang, Q.; Lin, S., Graph embedding and extensions: a general framework for dimensionality reduction, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 1, 40-51 (2007)
[7] Turk, M.; Pentland, A., Eigenfaces for recognition, Journal of Cognitive Neuroscience, 3, 1, 71-86 (1991)
[8] Belhumeur, P. N.; Hespanha, J. P.; Kriegman, D. J., Eigenfaces vs. Fisherfaces: recognition using class specific linear projection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 7, 711-720 (1997)
[9] X. Zhu, Semi-supervised learning literature survey, Technical Report, 2008.; X. Zhu, Semi-supervised learning literature survey, Technical Report, 2008.
[10] W. Liu, S.-F. Chang, Robust multi-class transductive learning with graphs, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.; W. Liu, S.-F. Chang, Robust multi-class transductive learning with graphs, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
[11] Wang, F.; Zhang, C. S., Label propagation through linear neighborhoods, IEEE Transactions on Knowledge and Data Engineering, 20, 1, 55-67 (2008)
[12] L.S. Qiao, S.C. Chen, X.Y. Tan, Sparsity preserving projections with applications to face recognition. Pattern Recognition 43(1) (2010) 331-341; L.S. Qiao, S.C. Chen, X.Y. Tan, Sparsity preserving projections with applications to face recognition. Pattern Recognition 43(1) (2010) 331-341 · Zbl 1186.68421
[13] S. Yan, H. Wang, Semi-supervised learning by sparse representation, in: Proceedings of SIAM International Conference on Data Mining (SDM), 2009.; S. Yan, H. Wang, Semi-supervised learning by sparse representation, in: Proceedings of SIAM International Conference on Data Mining (SDM), 2009.
[14] M. Maier, U. Luxburg, Influence of graph construction on graph-based clustering measures, in: Proceedings of Neural Information Processing Systems (NIPS), 2008.; M. Maier, U. Luxburg, Influence of graph construction on graph-based clustering measures, in: Proceedings of Neural Information Processing Systems (NIPS), 2008.
[15] T. Jebara, J. Wang, S. Chang, Graph Construction and b-Matching for Semi-Supervised Learning, in: Proceedings of International Conference on Machine Learning (ICML), 2009.; T. Jebara, J. Wang, S. Chang, Graph Construction and b-Matching for Semi-Supervised Learning, in: Proceedings of International Conference on Machine Learning (ICML), 2009.
[16] H.T. Chen, H.W. Chang, T.L. Liu, Local discriminant embedding and its variants, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2005.; H.T. Chen, H.W. Chang, T.L. Liu, Local discriminant embedding and its variants, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2005.
[17] D.Y. Zhou, O. Bousquet, T.N. Lal, J. Weston, B. Scholkopf, Learning with local and global consistency, in: Proceedings of Neural Information Processing Systems (NIPS), 2004.; D.Y. Zhou, O. Bousquet, T.N. Lal, J. Weston, B. Scholkopf, Learning with local and global consistency, in: Proceedings of Neural Information Processing Systems (NIPS), 2004.
[18] M. Wu, B. Scholkopf, A local learning approach for clustering, in: Proceedings of Neural Information Processing Systems (NIPS), 2006.; M. Wu, B. Scholkopf, A local learning approach for clustering, in: Proceedings of Neural Information Processing Systems (NIPS), 2006.
[19] Y. Bengio, O. Delalleau, N.L. Roux, Label propagation and quadratic criterion, in: Proceedings of Semi-Supervised Learning, MIT Press, Cambridge, 2006.; Y. Bengio, O. Delalleau, N.L. Roux, Label propagation and quadratic criterion, in: Proceedings of Semi-Supervised Learning, MIT Press, Cambridge, 2006.
[20] Bengio, Y.; Monperrus, M.; Larochelle, H., Nonlocal estimation of manifold structure, Neural Computation, 18, 10, 2509-2528 (2006) · Zbl 1107.68077
[21] H. Wang, S.C. Yan, D. Xu, X.O. Tang, T. Huang, Trace ratio vs. ratio trace for dimensionality reduction, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007, pp. 108-115.; H. Wang, S.C. Yan, D. Xu, X.O. Tang, T. Huang, Trace ratio vs. ratio trace for dimensionality reduction, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007, pp. 108-115.
[22] Yang, J.; Zhang, D.; Yang, J. Y.; Niu, B., Globally maximizing, locally minimizing: unsupervised discriminant projection with applications to face and palm biometrics, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 4, 650-664 (2007)
[23] Deng, W. H.; Hu, J. N.; Guo, J.; Zhang, H. G.; Zhang, C., Comments on “globally maximizing, locally minimizing: unsupervised discriminant projection with application to face and palm biometrics”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 30, 8, 1503-1504 (2008)
[24] Luo, P.; Zhan, G. X.; He, Q.; Shi, Z. Z.; Lu, K., On defining partition entropy by inequalities, IEEE Transactions on Information Theory, 53, 9, 3233-3239 (2007) · Zbl 1326.94036
[25] Rudin, W., Principles of Mathematical Analysis (1964), McGraw-Hill: McGraw-Hill New York · Zbl 0148.02903
[26] He, X. F.; Yan, S. C.; Hu, Y. X.; Niyogi, P.; Zhang, H. J., Face recognition using Laplacianfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 3, 328-340 (2005)
[27] J. Sun, W. Zhao, J. Xue, Z. Shen, Y. Shen, Clustering with feature order preferences, in: Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, Springer, Hanoi, Vietnam, 2008.; J. Sun, W. Zhao, J. Xue, Z. Shen, Y. Shen, Clustering with feature order preferences, in: Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, Springer, Hanoi, Vietnam, 2008.
[28] Lee, K. C.; Ho, J.; Kriegman, D. J., Acquiring linear subspaces for face recognition under variable lighting, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 5, 684-698 (2005)
[29] Martinez, A. M.; Kak, A. C., PCA versus LDA, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 2, 228-233 (2001)
[30] Cai, D.; He, X. F.; Han, J. W.; Zhang, H. J., Orthogonal Laplacianfaces for face recognition, IEEE Transactions on Image Processing, 15, 11, 3608-3614 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.