access icon free Local non-linear alignment for non-linear dimensionality reduction

In manifold learning, alignment is performed with the objective of deriving the global low-dimensional coordinates of input data from their local coordinates. In virtually all alignment processes, the relation between the local and global coordinates is designed intuitively, without mathematical deduction and detailed analysis. In this study, the authors propose a local non-linear alignment manifold learning algorithm (LNA) for non-linear dimensionality reduction, based on the concept of local pullback and the mathematical characteristics of a manifold. According to mathematical manifold theory, a function defined on a manifold cannot be differentiated directly on the manifold directly. Instead, it has to be pulled back to Euclidean space with the help of local homeomorphism between the manifold and Euclidean space, where it is then differentiated. In the authors’ proposed algorithm, the component functions of global homeomorphism are regarded as the functions defined on the manifold and pulled back to the Euclidean space. Then, Taylor expansion is utilised up to the second order to establish the relation between the global and local coordinates. The objective function in LNA is based on the alignment error and can be solved with an eigenvalue problem. The experimental results conducted on various datasets verify the validity of the authors’ method.

Inspec keywords: learning (artificial intelligence); eigenvalues and eigenfunctions

Other keywords: Euclidean space; eigenvalue problem; local pullback concept; manifold learning algorithm; objective function; nonlinear dimensionality reduction; mathematical manifold theory; alignment process; local homeomorphism; Taylor expansion; LNA; local nonlinear alignment

Subjects: Linear algebra (numerical analysis); Knowledge engineering techniques

References

    1. 1)
      • 14. Xiang, S.M., Nie, F., Pan, C.H., et al: ‘Regression reformulations of LLE and LTSA with locally linear transformation’, IEEE Trans. Syst., Man, Cybern. B, Cybern., 2011, 4, (5), pp. 12501262.
    2. 2)
      • 22. Wang, J., Jiang, W.X., Gou, J.: ‘Extended local tangent space alignment for classification’, Neurocomputing, 2012, 77, pp. 261266.
    3. 3)
      • 40. Zhang, T.: ‘Local coordinates alignment (LCA): A novel manifold learning approach’, Int. J. Pattern Recogn. Artif. Intell., 2008, 22, (4), pp. 667690.
    4. 4)
      • 42. Karygianni, S., Frossard, P.: ‘Tangent-based manifold approximation with locally linear models’, Signal Process., 2014, 104, pp. 232247.
    5. 5)
      • 11. Li, X., Lin, S., Yan, S., et al: ‘Discriminant locally linear embedding with high-order tensor data’, IEEE Trans. Syst. Man Cybern. B Cybern., 2008, 38, (2), pp. 342352.
    6. 6)
      • 36. Ma, Z.M., Chen, J.: ‘The Huffman-like alignment in manifold learning’, Int. J. Pattern Recogn., 2014, 28, (4), pp. 125.
    7. 7)
      • 33. Wang, R.P., Shan, S.G., Chen, X., et al: ‘Maximal linear embedding for dimensionality reduction’, IEEE Trans. Pattern Anal. Mach. Intell., 2011, 33, (9), pp. 17761792.
    8. 8)
      • 37. Xiang, S.M., Nie, F.P., Zhang, C., et al: ‘Nonlinear dimensionality reduction with local spline embedding’, IEEE Trans. Knowl. Data. En., 2009, 21, (9), pp. 12851298.
    9. 9)
      • 16. Donoho, D.L., Grimes, C.: ‘Hessian eigenmaps: new locally linear embedding techniques for high-dimensional data’. Proc. Natl Acad. Sci., 2003, pp. 55915596.
    10. 10)
      • 8. Roweis, S.T., Saul, L.K., Hinton, G.E.: ‘Global coordination of local linear models’. Proc. Advances Neural Information Processing Systems, 2001, pp. 889896.
    11. 11)
      • 31. Li, Y.: ‘Alignment of overlapping locally scaled patches for multidimensional scaling and dimensionality reduction’, IEEE Trans. Pattern Anal. Mach. Intell., 2008, 30, (3), pp. 438450.
    12. 12)
      • 24. Belkin, M., Niyogi, P.: ‘Laplacian eigenmaps for dimensionality reduction and data representation’, Neural Comput., 2003, 15, (6), pp. 13731396.
    13. 13)
      • 2. Cox, T., Cox, M.: ‘Multidimensional scaling’ (Chapman and Hall, London, UK, 1994).
    14. 14)
      • 3. Tenenbaum, J.B., de Silva, V., Langford, J.C.: ‘A global geometric framework for nonlinear dimensionality reduction’, Science, 2000, 290, (5500), pp. 23192323.
    15. 15)
      • 29. Lafon, S., Keller, Y., Coifman, R.: ‘Data fusion and multicue data matching by diffusion maps’, IEEE Trans. Pattern Anal. Mach. Intell., 2006, 28, (11), pp. 17841797.
    16. 16)
      • 23. Zhan, Y.B., Yin, J.P.: ‘Robust local tangent space alignment via iterative weighted PCA’, Neurocomputing, 2011, 74, pp. 19851993.
    17. 17)
      • 10. Chen, J., Ma, Z.M.: ‘Locally linear embedding: A review’, Int. J. Pattern Recogn., 2011, 25, (7), pp. 114.
    18. 18)
      • 19. Zhang, Z.Y., Zha, H.Y.: ‘Principal manifolds and nonlinear dimensionality reduction via tangent space alignment’, SIAM J. Sci. Comput., 2005, 26, (1), pp. 313338.
    19. 19)
      • 7. Roweis, S.T., Saul, L.K.: ‘Nonlinear dimensionality reduction by locally linear embedding’, Science, 2000, 290, (5500), pp. 23232326.
    20. 20)
      • 28. Lafon, S., Lee, A.: ‘Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization’, IEEE Trans. Pattern Anal. Mach. Intell., 2006, 28, (9), pp. 13931403.
    21. 21)
      • 35. Hou, Y., Zhang, P., Xu, X., et al: ‘Nonlinear dimensionality reduction by locally linear inlaying’, IEEE Trans. Neural Netw., 2009, 20, (2), pp. 300315.
    22. 22)
      • 26. Belkin, M., Niyogi, P., Sindhwani, V.: ‘Manifold regularization: a geometric framework for learning from labeled and unlabeled examples’, J. Mach. Learn. Res., 2006, 7, pp. 23992434.
    23. 23)
      • 44. Lin, T., Zha, H.: ‘Riemannian manifold learning’, IEEE Trans. Pattern Anal. Mach. Intell., 2008, 30, (5), pp. 796809.
    24. 24)
      • 1. Jolliffe, I.: ‘Principal component analysis’ (Springer-Verlag, New York, 1989).
    25. 25)
      • 27. Niyogi, P.: ‘Manifold regularization and semi-supervised learning: some theoretical analyses’, J. Mach. Learn. Res., 2013, 14, pp. 12291250.
    26. 26)
      • 13. Tiirkan, M., Guillemot, C.: ‘Image prediction based on neighbor-embedding methods’, IEEE Trans. Image Process., 2012, 21, (4), pp. 18851898.
    27. 27)
      • 41. Ma, L., Crawford, M.M., Yang, X., et al: ‘Local-manifold-learning-based graph construction for semisupervised hyperspectral image classification’, IEEE Trans. Geosci. Remote Sens., 2015, 53, (5), pp. 28322844.
    28. 28)
      • 25. Yan, S., Xu, D., Zhang, H.J., et al: ‘Graph embedding and extensions: a general framework for dimensionality reduction’, IEEE Trans. Pattern Anal. Mach. Intell., 2007, 29, (1), pp. 4051.
    29. 29)
      • 12. Pan, Y., Ge, S.S., Al Mamun, A.: ‘Weighted locally linear embedding for dimension reduction’, Pattern Recognit., 2009, 42, (5), pp. 798811.
    30. 30)
      • 43. Xing, X.L., Wang, K.J., Lv, Z., et al: ‘Fusion of local manifold learning methods’, IEEE Singnal Process. lett., 2015, 22, (4), pp. 395399.
    31. 31)
      • 21. Zhang, P., Qiao, H., Zhang, B.: ‘An improved local tangent space alignment method for manifold learning’, Pattern Recognit. Lett., 2011, 32, (2), pp. 181189.
    32. 32)
      • 9. Saul, L.K., Roweis, S.T.: ‘Think globally, fit locally: Unsupervised learning of low dimensional manifold’, J. Mach. Learn. Res., 2003, 4, pp. 119155.
    33. 33)
      • 20. Zhang, Z.Y., Wang, J., Zha, H.Y.: ‘Adaptive manifold learning’, IEEE Trans. Pattern Anal. Mach. Intell., 2012, 34, (2), pp. 253265.
    34. 34)
      • 15. Zhao, D.: ‘Formulating LLE using alignment technique’, Pattern Recogn., 2005, 39, pp. 22332235.
    35. 35)
      • 38. Han, Z., Meng, D.Y., Xu, Z.S., et al: ‘Incremental alignment manifold learning’, J. Comput. Sci. Technol., 2011, 26, (1), pp. 153165.
    36. 36)
      • 5. Zhang, Z., Chow, T.W.S., Zhao, M.: ‘M-Isomap: orthogonal constrained marginal Isomap for nonlinear dimensionality reduction’, IEEE Trans. Cybern., 2013, 43, (1), pp. 180191.
    37. 37)
      • 6. Gashler, M., Ventura, D., Martinez, T.: ‘Manifold learning by graduated optimization’, IEEE Trans. Syst. Man Cybern. B Cybern., 2011, 41, (6), pp. 14581470.
    38. 38)
      • 30. Weinberger, K.Q., Saul, L.K.: ‘Unsupervised learning of image manifolds by semidefinite programming’, Int. J. Comput. Vis., 2006, 70, (1), pp. 7790.
    39. 39)
      • 34. Tyagi, H., Vural, E., Frossard, P.: ‘Tangent space estimation for smooth embeddings of riemannian manifolds’, Inf. Inference, 2013, 2, pp. 69114.
    40. 40)
      • 32. Chen, J., Ma, Z.M., Yang, L.: ‘Local coordinates alignment with global preservation for dimensionality reduction’, IEEE Trans. Neural Netw., 2013, 24, (1), pp. 106117.
    41. 41)
      • 4. de Silva, V., Tenenbaum, J.: ‘Global versus local methods in nonlinear dimensionality reduction’. Proc. Advances Neural Information Processing Systems, 2003, pp. 705712.
    42. 42)
      • 18. Li, H., Hao, J., Barrio, R.: ‘Incremental manifold learning by spectral embedding methods’, Pattern Recogn. lett., 2011, 32, (10), pp. 14471455.
    43. 43)
      • 17. Si, S., Tao, D.C., Chan, K.: ‘Evolutionary cross-domain discriminative Hessian eigenmaps’, IEEE Trans. Image Process., 2010, 19, (4), pp. 10751086.
    44. 44)
      • 39. Lai, Z., Wong, W., Xu, Y., et al: ‘Sparse alignment for robust tensor learning’, IEEE Trans. Neur. Net. Lear., 2014, 25, (10), pp. 17791792.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cvi.2015.0441
Loading

Related content

content/journals/10.1049/iet-cvi.2015.0441
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading