We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Zhi Han, De-Yu Meng, Zong-Ben Xu, Nan-Nan Gu. Incremental Alignment Manifold Learning[J]. Journal of Computer Science and Technology, 2011, 26(1): 153-165. DOI: 10.1007/s11390-011-1118-7
Citation: Zhi Han, De-Yu Meng, Zong-Ben Xu, Nan-Nan Gu. Incremental Alignment Manifold Learning[J]. Journal of Computer Science and Technology, 2011, 26(1): 153-165. DOI: 10.1007/s11390-011-1118-7

Incremental Alignment Manifold Learning

Funds: This work was supported by the National Basic Research 973 Program of China under Grant No. 2007CB311002 and the National Natural Science Foundation of China under Grant No. 60905003.
More Information
  • Author Bio:

    Zhi Han received the B.Sc. and M.S. degrees in applied mathematics from Xi'an Jiaotong University (XJTU), China in 2005 and 2007, respectively. He is currently a Ph.D. candidate of applied mathematics in XJTU, and a joint Ph.D. candidate of statistics in University of California, Los Angeles, USA. His current research interests include nonlinear dimensionality reduction, manifold learning, computer vision and video representation.

    De-Yu Meng received the B.Sc., M.Sc., and Ph.D. degrees in 2001, 2004, and 2008, respectively, all from XJTU, China. He is currently a lecturer with the Institute for Information and System Sciences, Faculty of Science, XJTU. His current research interests include priciple component analysis, nonlinear dimensionality reduction, feature extraction and selection, compressed sensing, and sparse machine learning methods.

    Zong-Ben Xu received the M.Sc. degree in mathematics and the Ph.D. degree in applied mathematics from XJTU, China, in 1981 and 1987, respectively. In 1988, he was a postdoctoral researcher with the Department of Mathematics, The University of Strathclyde, Glasgow, U.K. He was a research fellow with the Information Engineering Department, the Center for Environmental Studies, and the Mechanical Engineering and Automation Department, The Chinese University of Hong Kong, China, and the Department of Computing, Hong Kong Polytechnic University, China. He is currently a professor with the Institute for Information and System Sciences, Faculty of Science, XJTU. His current research interests include manifold learning, neural networks, evolutionary computation, and multiple-objective decision-making theory.

    Nan-Nan Gu received the B.Sc. degree in information and computing science from XJTU, China in 2006, and the M.Sc. degree in applied mathematics from XJTU, in 2009. Currently, she is working toward the Ph.D. degree in pattern recognition in the Institute of Automation, Chinese Academy of Sciences, Beijing, China. Her research interests include theory and application of manifold learning and nonlinear dimensionality reduction.

  • Received Date: March 02, 2010
  • Revised Date: November 01, 2010
  • Published Date: December 31, 2010
  • A new manifold learning method, called incremental alignment method (IAM), is proposed for nonlinear dimensionality reduction of high dimensional data with intrinsic low dimensionality. The main idea is to incrementally align low-dimensional coordinates of input data patch-by-patch to iteratively generate the representation of the entire dataset. The method consists of two major steps, the incremental step and the alignment step. The incremental step incrementally searches neighborhood patch to be aligned in the next step, and the alignment step iteratively aligns the low-dimensional coordinates of the neighborhood patch searched to generate the embeddings of the entire dataset. Compared with the existing manifold learning methods, the proposed method dominates in several aspects: high efficiency, easy out-of-sample extension, well metric-preserving, and averting of the local minima issue. All these properties are supported by a series of experiments performed on the synthetic and real-life datasets. In addition, the computational complexity of the proposed method is analyzed, and its efficiency is theoretically argued and experimentally demonstrated.
  • [1]
    Donoho D L. High-dimensional data analysis: The curses and lessings of dimensionality. American Math. Society Lecture, atch Challenges of the 21st Century, 2000.
    [2]
    Roweis S T, Saul L K. Nonlinear dimensionality reduction y locally linear embedding. Science, Dec. 2000, 290(5500): 323-2326.
    [3]
    Tenenbaum J B, de Silva V, Langford J C. A global geometric ramework for nonlinear dimensionality reduction. Science, Dec. 2000, 290(5500): 2319-2323.
    [4]
    Bachmann C M, Ainsworth T L, Fusina R A. Exploiting manfold geometry in hyperspectral imagery. IEEE Trans. Geocience and Remote Sensing, Mar. 2005, 43(3): 441-454.
    [5]
    Lee J G, Zhang C S. Classification of gene-expression data: he manifold-based metric learning way. Pattern Recogniion, Dec. 2006, 39(12): 2450-2463.
    [6]
    Shin Y. Facial expression recognition of various internal states ia manifold learning. Journal of Computer Science and echnology, Jul. 2009, 24(4): 745-752.
    [7]
    Belkin M, Niyogi P. Laplacian eigenmaps for dimensionalty reduction and data representation. Neural Computation, 2003, 15(6): 1373-1396.
    [8]
    Zhang Z, Zha H. Principal manifolds and nonlinear dimenion reduction via local tangent space alignment. SIAM J. cientific Computing, 2005, 26(1): 313-338.
    [9]
    Donoho D L, Grimes C. Hessian eigenmaps: New locally linar embedding techniques for high-dimensional data. Proc. he National Academy of Sciences, 2003, 100(10): 5591-5596.
    [10]
    Weinberger K, Saul L. Unsupervised learning of image maniolds by semidefinite programming. In Proc. IEEE Int. Conf. omputer Vision and Pattern Recognition, Washington DC, SA, Jun. 27-Jul. 2, 2004, pp.988-995.
    [11]
    Lee J A, Lendasse A, Verleysen M. Nonlinear projection with urvilinear distances: ISOMAP versus curvilinear distance nalysis. Neurocomputing, Mar. 2004, 57: 49-76.
    [12]
    Hinton G, Roweis S. Stochastic neighbor embedding. In Proc. IPS 2002, Vancouver, Canada, Dec. 9-14, 2002, pp.833-840.
    [13]
    Agrafiotis D K, Xu H. A self-organizing principle for learning onlinear manifolds. Proceedings of the National Academy of Sciences, 2002, 99(25): 15869-15872.
    [14]
    Yang L. Alignment of overlapping locally scaled patches for ultidimensional scaling and dimensionality reduction. IEEE rans. Pattern Analysis and Machine Intelligence, Mar. 008, 30(3): 438-450.
    [15]
    de Silva V, Tenenbaum J B. Global versus local methods in onlinear dimensionality reduction. In Proc. NIPS 2003, ancouver and Whistler, Canada, Dec. 8-13, 2003, pp.705- 12.
    [16]
    Lin T, Zha H. Riemannian manifold learning. IEEE Trans. Pattern Analysis and Machine Intelligence, May, 2008, 30(5): 96-809.
    [17]
    Roweis S T, Saul L K, Hinton G E. Global coordination of ocal linear models. In Proc. NIPS 2001, Vancouver, Canada, Dec. 3-8, 2001, pp.889-896.
    [18]
    Verbeek J. Learning nonlinear image manifolds by global lignment of local linear models. IEEE Trans. Pattern Analsis and Machine Intelligence, Aug. 2006, 28(8): 1236-1250.
    [19]
    Bachmann C M, Alinsworth T L, Fusina R A. Exploiting anifold geometry in hyperspectral imagery. IEEE Trans. eoscience and Remote Sensing, Mar. 2005, 43(3): 441-454.
    [20]
    Teh Y W, Roweis S T. Automatic alignment of hidden repreentations. In Proc. NIPS 2002, Vancouver, Canada, Dec. 9- 4, 2002, pp.841-848.
    [21]
    Verveek J, Roweis S, Vlassis N. Non-linear CCA and PCA by lignment of local models. In Proc. NIPS 2003, Vancouver nd Whistler, Canada, Dec. 8-13, 2003, pp.297-304.
    [22]
    Zhang T, Yang J, Zhao D, Ge X. Linear local tangent space lignment and application to face recognition. Neuralcomputng, 2007, 70(7-9): 1547-1553.
    [23]
    Cox T, Cox M. Multidimensional Scaling. Chapman and Hall, 994.
    [24]
    Law M H C, Zhang N, Jain A K. Nonlinear manifold learning or data stream. In Proc. SIAM Data Mining, Orlando, USA, pr. 22-24, 2004, pp.33-44.
    [25]
    Law M H C, Jain A K. Incremental nonlinear dimensionality eduction by manifold learning. IEEE Trans. Pattern Analsis and Machine Intelligence, Mar. 2006, 28(3): 377-391.
    [26]
    Kouropteva O, Okun O, PietikÄainen M. Incremental locally inear embedding. Pattern Recognition, 2005, 38(10): 1764- 767.
    [27]
    Kouropteva O, Okun O, PietikÄainen M. Incremental locally inear embedding algorithm. In Proc. Fourteenth Scaninavian Conference on Image Analysis, Joensuu, Finland, Jun. 19-22, 2005, pp.521-530.
    [28]
    Bengio Y, Paiement J F, Vincent P, Delalleau O, Le Roux N, uimet M. Out-of-sample extensions for LLE, Isomap, MDS, igenmaps, and spectral clustering. In Proc. NIPS 2003, ancouver and Whistler, Canada, Dec. 8-13, 2003, pp.177- 84.
    [29]
    Zhao D, Yang L. Incremental isometric embedding of high diensional data using connected neighborhood graphs. IEEE rans. Pattern Analysis and Machine Intelligence, 2009, 1(1): 86-98.
    [30]
    Jolliffe I T. Principal Component Analysis. Springer-Verlag, 986.
    [31]
    Yang J, Zhang D, Frangi A, Yang J. Two-dimentional PCA: new approach to appearance-based face representation and ecognition. IEEE Trans. Pattern Analysis and Machine Inelligence, Jan. 2004, 26(1): 131-137.
    [32]
    Meng D, Leung Y, Fung T, Xu Z. Nonlinear dimensionality eduction of data lying on the multi-cluster manifold. IEEE rans. Systems, Man and Cybernetics, Part B, Aug. 2008, 8(4): 1111-1122.
    [33]
    Meng D, Leung Y, Xu Z, Fung T, Zhang Q. Improving eodesic distance estimation based on locally linear assumpion. Pattern Recognition Letters, May 2008, 29(7): 862-870.
    [34]
    Lee J A, Verleysen M. Nonlinear dimensionality reduction of ata manifolds with essential loops. Neurocomputing, 2005, 7: 29-53.
    [35]
    Saul L K, Roweis S T. Think globally, fit locally: Unsuperised learning of low dimensional manifold. Journal Machine earning Research, 2003, 4: 119-155.
    [36]
    Friedman J H, Bentley J L, Finkel R A. An algorithm for findng best matches in logarithmic expected time. ACM Transctions on Mathematical Software, 1977, 3(3): 209-226.
    [37]
    Nocedal J, Wright S J. Numerical Optimization, 2nd Ed. erlin, New York: Springer-Verlag, 2006, p.24.
    [38]
    de Silva V, Tenenbaum J B. Global versus local methods in onlinear dimensionality reduction. In Proc. NIPS 2002, ancouver, Canada, Dec. 9-14, 2002, pp.705-712.
  • Related Articles

    [1]Tong Lin, Yao Liu, Bo Wang, Li-Wei Wang, Hong-Bin Zha. Nonlinear Dimensionality Reduction by Local Orthogonality Preserving Alignment[J]. Journal of Computer Science and Technology, 2016, 31(3): 512-524. DOI: 10.1007/s11390-016-1644-4
    [2]Young-Suk Shin. Facial Expression Recognition of Various Internal States via Manifold Learning[J]. Journal of Computer Science and Technology, 2009, 24(4): 745-752.
    [3]XI Haifeng, LUO Yupin, YANG Shiyuan. An Approach to Active Learning for Classifier Systems[J]. Journal of Computer Science and Technology, 1999, 14(4): 372-378.
    [4]Ma Jiyong, Gao Wen. The Supervised Learning Gaussian Mixture Model[J]. Journal of Computer Science and Technology, 1998, 13(5): 471-474.
    [5]Dong Yunmei. An Interactive Learning Algorithm for Acquisition of Concepts Represented as CFL[J]. Journal of Computer Science and Technology, 1998, 13(1): 1-8.
    [6]Yao Shu, Zhang Bo. The Learning Convergence of CMAC in Cyclic Learning[J]. Journal of Computer Science and Technology, 1994, 9(4): 320-328.
    [7]Ma Zhifang. DKBLM——Deep Knowledge Based Learning Methodology[J]. Journal of Computer Science and Technology, 1993, 8(4): 93-98.
    [8]Wu Xindong. Inductive Learning[J]. Journal of Computer Science and Technology, 1993, 8(2): 22-36.
    [9]Harald E. Otto. UNDO, An Aid for Explorative Learning?[J]. Journal of Computer Science and Technology, 1992, 7(3): 226-236.
    [10]Hayong Zhou. Analogical Learning and Automated Rule Constructions[J]. Journal of Computer Science and Technology, 1991, 6(4): 316-328.

Catalog

    Article views (26) PDF downloads (2176) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return