Low-rank graph optimization for multi-view dimensionality reduction

English version

Autoři: Youcheng Qian ^aff001; Xueyan Yin ^aff003; Jun Kong ^aff004; Jianzhong Wang ^aff004; Wei Gao ^aff001
Působiště autorů: Key Laboratory for Applied Statistics of MOE, School of Mathematics and Statistics, Northeast Normal University, Changchun, Jilin, China ^aff001; School of Science, Jilin Institute of Chemical Technology, Jilin, China ^aff002; School of Computer Science and Technology, Dalian University of Technology, Dalian, Liaoning, China ^aff003; School of Information Science and Technology, Northeast Normal University, Changchun, Jilin, China ^aff004
Vyšlo v časopise: PLoS ONE 14(12)
Kategorie: Research Article
prolekare.web.journal.doi_sk: https://doi.org/10.1371/journal.pone.0225987

Souhrn

Graph-based dimensionality reduction methods have attracted substantial attention due to their successful applications in many tasks, including classification and clustering. However, most classical graph-based dimensionality reduction approaches are only applied to data from one view. Hence, combining information from different data views has attracted considerable attention in the literature. Although various multi-view graph-based dimensionality reduction algorithms have been proposed, the graph construction strategies utilized in them do not adequately take noise and different importance of multiple views into account, which may degrade their performance. In this paper, we propose a novel algorithm, namely, Low-Rank Graph Optimization for Multi-View Dimensionality Reduction (LRGO-MVDR), that overcomes these limitations. First, we construct a low-rank shared matrix and a sparse error matrix from the graph that corresponds to each view for capturing potential noise. Second, an adaptive nonnegative weight vector is learned to explore complementarity among views. Moreover, an effective optimization procedure based on the Alternating Direction Method of Multipliers scheme is utilized. Extensive experiments are carried out to evaluate the effectiveness of the proposed algorithm. The experimental results demonstrate that the proposed LRGO-MVDR algorithm outperforms related methods.

Klíčová slova:

Principal component analysis – Computer and information sciences – Algorithms – Optimization – Linear discriminant analysis – Eigenvectors – Attention – Spectral clustering

Zdroje

1. Xu C, Tao D, Xu C. A survey on multi-view learning. arXiv:1304.5634. [Preprint]. 2013 [cited 2013 April 20]. Available from: https://arxiv.org/abs/1304.5634.

2. Xu C, Tao D, Xu C. Large-margin multi-view information bottleneck. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2014;36(8):1559–1572. doi: 10.1109/TPAMI.2013.2296528 26353338

3. Gheyas IA, Smith LS. Feature subset selection in large dimensionality domains. Pattern recognition. 2010;43(1):5–13.

4. De la Torre F. A least-squares framework for component analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012;34(6):1041–1055. doi: 10.1109/TPAMI.2011.184 21911913

5. Ni J, Qiu Q, Chellappa R. Subspace interpolation via dictionary learning for unsupervised domain adaptation. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR); 2013. p.692-699.

6. Song D, Tao D. Biologically inspired feature manifold for scene classification. IEEE Transactions on Image Processing. 2010;19(1):174–184. doi: 10.1109/TIP.2009.2032939 19783505

7. Xu C, Tao D, Xu C, Rui Y. Large-margin weakly supervised dimensionality reduction. In: International Conference on Machine Learning (ICML); 2014. p.865-873.

8. Sugiyama M. Local fisher discriminant analysis for supervised dimensionality reduction. In: International Conference on Machine Learning (ICML); 2006. p.905-912.

9. Xu D, Yan S, Tao D, Lin S, Zhang H-J. Marginal fisher analysis and its variants for human gait recognition and content-based image retrieval. IEEE Transactions on Image Processing. 2007;16(11):2811–2821. doi: 10.1109/tip.2007.906769 17990757

10. Zhang Y, Zhou Z-H. Multilabel dimensionality reduction via dependence maximization. ACM Transactions on Knowledge Discovery from Data. 2010;4(3):14.

11. Yan S, Xu D, Zhang B, 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. 2007;29(1):40–51. doi: 10.1109/TPAMI.2007.12 17108382

12. Wang J, Zhang B, Qi M, Kong J. Linear discriminant projection embedding based on patches alignment. Image Vision Computing. 2010;28(12):1624–1636.

13. Turk M, Pentland A. Eigenfaces for recognition. Journal of cognitive neuroscience. 1991;3(1):71–86. doi: 10.1162/jocn.1991.3.1.71 23964806

14. Belhumeur PN, Hespanha JP, Kriegman DJ. Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1997;19(7):711–720.

15. Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science. 2000;290(5500):2323–2326. doi: 10.1126/science.290.5500.2323 11125150

16. Tenenbaum JB, De Silva V, Langford JC. A global geometric framework for nonlinear dimensionality reduction. Science. 2000;290(5500):2319–2323. doi: 10.1126/science.290.5500.2319 11125149

17. Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 2003;15(6):1373–1396.

18. Donoho DL, Grimes C. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Sciences. 2003;100(10):5591–5596.

19. Zhang Z, Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. SIAM journal on scientific computing. 2004;26(1):313–338.

20. Kumar A, Daumé H. A co-training approach for multi-view spectral clustering. In: International Conference on Machine Learning (ICML); 2011. p.393-400.

21. Xia T, Tao D, Mei T, Zhang Y. Multiview spectral embedding. IEEE Transactions on Systems, Man, Cybernetics, Part B. 2010;40(6):1438–1446.

22. Shu L, Latecki LJ. Integration of single-view graphs with diffusion of tensor product graphs for multi-view spectral clustering. In: Asian Conference on Machine Learning; 2016. p.362-377.

23. Bisson G, Grimal C. Co-clustering of multi-view datasets: a parallelizable approach. In: International Conference on Data Mining (ICDM); 2012. p.828-833.

24. Tzortzis G, Likas A. Kernel-based weighted multi-view clustering. In: International Conference on Data Mining (ICDM); 2012. p.675-684.

25. De Sa VR, Gallagher PW, Lewis JM, Malave VL. Multi-view kernel construction. Machine learning. 2010;79(1–2):47–71.

26. De Sa VR, Ballard DH. Category learning through multimodality sensing. Neural Computation. 1998;10(5):1097–1117. doi: 10.1162/089976698300017368 9654768

27. Li Y, Nie F, Huang H, Huang J. Large-Scale Multi-View Spectral Clustering via Bipartite Graph. In: Association for the Advancement of Artificial Intelligence (AAAI); 2015. p.2750–2756.

28. Zong L, Zhang X, Yu H, Zhao Q, Ding F. Local linear neighbor reconstruction for multi-view data. Pattern Recognition Letters. 2016;84:56–62.

29. Liu G, Lin Z, Yu Y. Robust subspace segmentation by low-rank representation. In: International Conference on Machine Learning (ICML); 2010. p.663-670.

30. Ye G, Liu D, Jhuo I-H, Chang S-F. Robust late fusion with rank minimization. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR); 2012. p.3021-3028.

31. Pan Y, Lai H, Liu C, Tang Y, Yan S. Rank Aggregation via Low-Rank and Structured-Sparse Decomposition. In: Association for the Advancement of Artificial Intelligence (AAAI); 2013.

32. Xia R, Pan Y, Du L, Yin J. Robust Multi-View Spectral Clustering via Low-Rank and Sparse Decomposition. In: Association for the Advancement of Artificial Intelligence (AAAI); 2014. p.2149–2155.

33. Hong C, Yu J, Wan J, Tao D, Wang M. Multimodal deep autoencoder for human pose recovery. IEEE Transactions on Image Processing. 2015;24(12):5659–5670. doi: 10.1109/TIP.2015.2487860 26452284

34. Zhuge W, Hou C, Jiao Y, Yue J, Tao H, Yi D. Robust auto-weighted multi-view subspace clustering with common subspace representation matrix. PloS one. 2017;12(5):e0176769. doi: 10.1371/journal.pone.0176769 28542234

35. Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning. 2011;3(1):1–122.

36. Ahmadian A, Mostafa A. An efficient texture classification algorithm using Gabor wavelet. In: IEEE engineering in medicine and biology society (IEEE Cat No 03CH37439); 2003. p.930–933.

37. Wang J, Zhao R, Wang Y, Zheng C, Kong J, Yi Y. Locality Constrained Graph Optimization for Dimensionality Reduction. Neurocomputing. 2017;245:55–67.

38. Zhang H, Zhuang Y, Wu F. Cross-modal correlation learning for clustering on image-audio dataset. In: ACM international conference on Multimedia; 2007. p.273-276.

39. Nie F, Huang H, Cai X, Ding CH. Efficient and robust feature selection via joint l2,1-norms minimization. In: Conference on Neural Information Processing Systems (NIPS); 2010. p.1813-1821.

40. Fazel M. Matrix rank minimization with applications: PhD thesis, Stanford University; 2002.

41. Candès EJ, Recht B. Exact matrix completion via convex optimization. Foundations of Computational mathematics. 2009;9(6):717.

42. Candès EJ, Tao T. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory. 2010;56(5):2053–2080.

43. Recht B, Fazel M, Parrilo PA. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review. 2010;52(3):471–501.

44. Fazel M, Hindi H, Boyd SP. A rank minimization heuristic with application to minimum order system approximation. In: American control conference; 2001. p.4734–4739.

45. Ramirez C, Kreinovich V, Argaez M. Why l1 is a good approximation to l0: A geometric explanation. Journal of Uncertain Systems. 2013;7(3):203–207.

46. Zhou D, Huang J, Schölkopf B. Learning from labeled and unlabeled data on a directed graph. In: International Conference on Machine Learning (ICML); 2005. p.1036-1043.

47. Wu J, Lin Z, Zha H. Essential tensor learning for multi-view spectral clustering. IEEE Transactions on Image Processing. 2019.

48. Groetsch C. The theory of tikhonov regularization for fredholm equations. 104p, Boston Pitman Publication. 1984.

49. Li P, Bu J, Chen C, He Z, Cai D. Relational multimanifold coclustering. IEEE Transactions on cybernetics. 2013;43(6):1871–1881. doi: 10.1109/TSMCB.2012.2234108 23757578

50. Cai J-F, Candès EJ, Shen Z. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization. 2010;20(4):1956–1982.

51. Lin Z, Chen M, Ma Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv:10095055 [Preprint]. 2010 [cited 2010 Sept.26]. Available from: https://arxiv.org/abs/1009.5055

52. Duchi J, Shalev-Shwartz S, Singer Y, Chandra T. Efficient projections onto the l1-ball for learning in high dimensions. In: International Conference on Machine Learning (ICML); 2008. p.272-279.

53. Boyd S, Vandenberghe L. Convex optimization: Cambridge university press; 2004.

54. Geng B, Tao D, Xu C, Yang L, Hua X-S. Ensemble manifold regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012;34(6):1227–1233. doi: 10.1109/TPAMI.2012.57 22371429

55. Shen J, Deng C, Gao X. Attraction recommendation: Towards personalized tourism via collective intelligence. Neurocomputing. 2016;173:789–798.

56. Bai S, Zhou Z, Wang J, Bai X, Jan Latecki L, Tian Q. Ensemble diffusion for retrieval. In: IEEE International Conference on Computer Vision (ICCV); 2017. p.774-783.

57. Xiu Y, Shen W, Wang Z, Liu S, Wang J. Multiple graph regularized graph transduction via greedy gradient Max-Cut. Information Sciences. 2018;423:187–199.

58. Hong C, Yu J, You J, Chen X, Tao D. Multi-view ensemble manifold regularization for 3D object recognition. Information sciences. 2015;320:395–405.

59. Tao D, Jin L, Yuan Y, Xue Y. Ensemble manifold rank preserving for acceleration-based human activity recognition. IEEE transactions on neural networks and learning systems. 2016;27(6):1392–1404. doi: 10.1109/TNNLS.2014.2357794 25265635

60. Kumar A, Rai P, Daume H. Co-regularized multi-view spectral clustering. In: Conference on Neural Information Processing Systems (NIPS); 2011. p.1413-1421.

61. Xie X, Sun S. Multi-view clustering ensembles. In: International Conference on Machine Learning and Computing (ICMLC); 2013. p.51-56.

62. Fei-Fei L, Fergus R, Perona PJCv, understanding I. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. Computer vision and Image understanding. 2007;106(1):59–70.

63. Pereira JC, Coviello E, Doyle G, Rasiwasia N, Lanckriet GR, Levy R, et al. On the role of correlation and abstraction in cross-modal multimedia retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence machine intelligence. 2014;36(3):521–535.

64. Cai D, He X, Hu Y, Han J, Huang T. Learning a spatially smooth subspace for face recognition. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR); 2007. p.1-7.

65. Bisson G, Grimal C. An architecture to efficiently learn co-similarities from multi-view datasets. In: International Conference on Neural Information Processing (ICNIP); 2012. p.184-193.

66. Sindhwani V, Niyogi P, Belkin M. Beyond the point cloud: from transductive to semi-supervised learning. In: International Conference on Machine Learning (ICML); 2005. p.824-831.

67. Ng AY, Jordan MI, Weiss Y. On spectral clustering: Analysis and an algorithm. In: Conference on Neural Information Processing Systems (NIPS); 2002. p.849-856.

68. Lovász L, Plummer MD. Matching theory: American Mathematical Soc.; 2009.

69. Yadav S, Shukla S. Analysis of k-fold cross-validation over hold-out validation on colossal datasets for quality classification. In: International Conference on Advanced Computing (IACC); 2016. p.78-83.

70. Kanno Y, Kitayama S. Alternating direction method of multipliers as a simple effective heuristic for mixed-integer nonlinear optimization. Structural and Multidisciplinary Optimization. 2018;58(3):1291–1295.

Low-rank graph optimization for multi-view dimensionality reduction

Souhrn

Klíčová slova:

Zdroje

PLOS One

Aktuální možnosti diagnostiky a léčby litiáz