Compositional metric learning for multi-label classification

Abstract

Multi-label classification aims to assign a set of proper labels for each instance, where distance metric learning can help improve the generalization ability of instance-based multi-label classification models. Existing multi-label metric learning techniques work by utilizing pairwise constraints to enforce that examples with similar label assignments should have close distance in the embedded feature space. In this paper, a novel distance metric learning approach for multi-label classification is proposed by modeling structural interactions between instance space and label space. On one hand, compositional distance metric is employed which adopts the representation of a weighted sum of rank-1 PSD matrices based on component bases. On the other hand, compositional weights are optimized by exploiting triplet similarity constraints derived from both instance and label spaces. Due to the compositional nature of employed distance metric, the resulting problem admits quadratic programming formulation with linear optimization complexity w.r.t. the number of training examples.We also derive the generalization bound for the proposed approach based on algorithmic robustness analysis of the compositional metric. Extensive experiments on sixteen benchmark data sets clearly validate the usefulness of compositional metric in yielding effective distance metric for multi-label classification.

Keywords

machine learning / multi-label learning / metric learning / compositionalmetric / positive semidefinite matrix decomposition

References

[1] Zhang M L, Zhou Z H. A review on multi-label learning algorithms. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1819–1837

[2] Gibaja E, Ventura S. A tutorial on multilabel learning. ACM Computing Surveys, 2015, 47(3): 52

[3] Briggs F, Lakshminarayanan B, Neal L, Fern X Z, Raich R, Hadley S J, Hadley A S, Betts M G. Acoustic classification of multiple simultaneous bird species: a multi-instance multi-label approach. Journal of the Acoustical Society of America, 2012, 131(6): 4640–4650

[4] Cabral R, DelaTorre F, Costeira J P, Bernardino A. Matrix completion for weakly-supervised multi-label image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(1): 121–135

[5] Liu J, Chang W C, Wu Y, Yang Y. Deep learning for extreme multi-label text classification. In: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2017, 115–124

[6] Pan X, Fan Y X, Jia J, Shen H B. Identifying RNA-binding proteins using multi-label deep learning. Science China Information Sciences, 2019, 62: 19103

[7] Sun L, Ge H, Kang W. Non-negative matrix factorization based modeling and training algorithm for multi-label learning. Frontiers of Computer Science, 2019, 13(6): 1243–1254

[8] Bellet A, Habrard A, Sebban M. Metric learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2015, 9(1): 1–151

[9] Wang F, Sun J. Survey on distance metric learning and dimensionality reduction in data mining. Data Mining and Knowledge Discovery, 2015, 29(2): 534–564

[10] Liu W, Tsang I W. Large margin metric learning for multi-label prediction. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 2800–2806

[11] Goukand H, Pfahringer B, Cree M. Learning distance metrics for multilabel classification. In: Proceedings of the 8th Asian Conference on Machine Learning. 2016, 318–333

[12] Zhang Y, Schneider J. Maximum margin output coding. In: Proceedings of the 29th International Conference on Machine Learning. 2012, 1575–1582

[13] Verma Y, Jawahar C V. Image annotation by propagating labels from semantic neighbourhoods. International Journal of Computer Vision, 2017, 121(1): 126–148

[14] Gouk H, Pfahringer B, Cree M. Learning similarity metrics by factorising adjacency matrices. 2015, arXiv preprint arXiv: 1511.06442

[15] Ni J, Liu J, Zhang C, Ye D, Ma Z. Fine-grained patient similarity measuring using deep metric learning. In: Proceedings of the 26th ACM International Conference on Information and Knowledge Management. 2017, 1189–1198

[16] Shi Y, Bellet A, Sha F. Sparse compositional metric learning. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2014, 2078–2084

[17] St. Amand J, Huan J. Sparse compositional local metric learning. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 1097–1104

[18] Zhou Z H, Zhang M L, Huang S J, Li Y F. Multi-instance multi-label learning. Artificial Intelligence, 2012, 176(1): 2291–2320

[19] Zhang ML,Wu L. LIFT:multi-label learning with label-specific features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(1): 107–120

[20] Huang J, Li G, Huang Q, Wu X. Learning label-specific features and class-dependent labels for multi-label classification. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(12): 3309–3323

[21] Weinberger K Q, Saul L K. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 2009, 10: 207–244

[22] Huang S J, Zhou Z H. Multi-label learning by exploiting label correlations locally. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence. 2012, 949–955

[23] Zhu Y, Kwok J, Zhou Z H. Multi-label learning with global and local correlation. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(6): 1081–1094

[24] Yuan G X, Ho C H, Lin C J. An improved GLMNET for L1-regularized logistic regression. Journal of Machine Learning Research, 2012, 13: 1999–2030

[25] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. Siam Journal on Imaging Sciences, 2009, 2(1): 183–202

[26] Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific Journal of Optimization, 2010, 6(3): 615–640

[27] Bellet A, Habrard A. Robustness and generalization for metric learning. Neurocomputing, 2015, 151(14): 259–267

[28] Read J, Pfahringer B, Holmes G, Frank E. Classifier chains for multi-label classification. Machine Learning, 2011, 85(3): 333–359

[29] Zhang M L, Zhou Z H. ML-kNN: a lazy learning approach to multi-label learning. Pattern Recognition, 2007, 40(7): 2038–2048

[30] Rong J, Wang S, Zhou Z H. Learning a distance metric from multiinstance multi-label data. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2009, 896–902

[31] Verma Y, Jawahar C V. A robust distance with correlated metric learning for multi-instance multi-label data. In: Proceedings of the 24th ACM International Conference on Multimedia. 2016, 441–445

[32] Zhang M L, Li Y K, Liu Y Y, Geng X. Binary relevance for multi-label learning: an overview. Frontiers of Computer Science, 2018, 12(2): 191–202

[33] Wu Y, Lin Y, Dong X, Yan Y, Bian W, Yang Y. Progressive learning for person re-identification with one example. IEEE Transactions on Image Processing, 2019, 28(6): 2872–2881

[34] Sun L, Ji S, Ye J. Multi-label Dimensionality Reduction. London: Chapman and Hall/CRC, 2013

[35] Pereira R B, Plastino A, Zadrozny B, Merschmann L H C. Categorizing feature selection methods for multi-label classification. Artificial Intelligence Review, 2018, 49(1): 57–78

[36] Zhang J, Li C, Cao D, Lin Y, Su S, Dai L, Li S. Multi-label learning with label-specific features by resolving label correlations. Knowledge-Based Systems, 2018, 159: 148–157

[37] Chen Z S, Zhang M L. Multi-label learning with regularization enriched label-specific features. In: Proceedings of the 11th Asian Conference on Machine Learning. 2019, 411–424

[38] Yang Y, Gopal S. Multilabel classification with meta-level features in a learning-to-rank framework. Machine Learning, 2012, 88(1–2): 47–68

[39] Canuto S, Gonçalves M A, Benevenuto F. Exploiting new sentimentbased meta-level features for effective sentiment analysis. In: Proceedings of the 9th ACM International Conference on Web Search and Data Mining. 2016, 53–62

[40] Zhu X, Li X, Zhang S. Block-row sparse multiview multilabel learning for image classification. IEEE Transactions on Cybernetics, 2016, 46(2): 450–461

[41] Zhang C, Yu Z, Hu Q, Zhu P, Liu X, Wang X. Latent semantic aware multi-view multi-label classification. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018, 4414–4421

[42] Wu X, Chen Q G, Hu Y, Wang D B, Chang X, Wang X, Zhang M L. Multiview multi-label learning with view-specific information extraction. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 3884–3890

[43] Zhang R, Nie F, Li X, Wei X. Feature selection with multi-view data: a survey. Information Fusion, 2019, 50: 158–167

[44] Zhou Z H. Abductive learning: towards bridging machine learning and logical reasoning. Science China Information Sciences, 2019, 62: 076101

[45] Yang Y, Ma Z, Hauptmann A G, Sebe N. Feature selection for multimedia analysis by sharing information among multiple tasks. IEEE Transactions on Multimedia, 2013, 15(3): 661–669

[46] Zhang R, Nie F, Li X. Self-weighted supervised discriminative feature selection. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(8): 3913–3918

[47] Zhang R, Nie F, Wang Y, Li X. Unsupervised feature selection via adaptive multimeasure fusion. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(9): 2886–2892

RIGHTS & PERMISSIONS

Higher Education Press