Abstract
In this paper, we propose two new algorithms for transductive multi-label learning from missing data. In transductive matrix completion (MC), the challenge is prediction while the data matrix is partially observed. The joint MC and prediction tasks are addressed simultaneously to enhance accuracy in comparison with separate tackling of each. In this setting, the labels to be predicted are modeled as missing entries inside a stacked matrix along the feature-instance data. Assuming the data matrix is of low rank, we propose a new recommendation method for transductive MC by posing the problem as a minimization of the smoothed rank function with non-affine constraints, rather than its convex surrogate. We provide convergence analysis for the proposed algorithms and illustrate their low computational complexity and robustness in comparison with other methods. The simulations are conducted on well-known real datasets in two different scenarios of randomly missing pattern with and without block-loss. The simulations reveal our methods accuracy is superior to state-of-the-art methods up to 10% in low observation rates for the scenario without block-loss. The accuracy of the proposed methods in the scenario with block-loss is comparable to the state-of-the-art while the complexity is reduced up to four times.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alameda-Pineda X, Yan Y, Ricci E, Lanz O, Sebe N (2015) Analyzing free-standing conversational groups: a multimodal approach. In: Proceedings of the 23rd ACM international conference on multimedia
Aste M, Boninsegna M, Freno A, Trentin E (2015) Techniques for dealing with incomplete data: a tutorial and survey. Pattern Anal Appl 18(1):1–29
Bertsekas DP (1999) Nonlinear programming. Athena Scientific, Belmont
Birgin EG, Martínez JM, Raydan M (2000) Nonmonotone spectral projected gradient methods on convex sets. SIAM J Optim 10(4):1196–1211
Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Found Comput Math 9(6):717
Dvijotham K, Fazel M (2010) A nullspace analysis of the nuclear norm heuristic for rank minimization. In: IEEE international conference on acoustics speech and signal processing (ICASSP)
Elisseeff A, Weston J (2002) A kernel method for multi-labelled classification. In: Advances in neural information processing systems, pp 681–687
Farhangfar A, Kurgan L, Dy J (2008) Impact of imputation of missing values on classification error for discrete data. Pattern Recognit 41(12):3692–3705
Goldberg A, Recht B, Xu J, Nowak R, Zhu X (2010) Transduction with matrix completion: three birds with one stone. In: Advances in neural information processing systems, pp 757–765
Kiasari MA, Jang G-J, Lee M (2017) Novel iterative approach using generative and discriminative models for classification with missing features. Neurocomputing 225:23–30
Lin Z, Ding G, Hu M, Wang J, Ye X (2013) Image tag completion via image-specific and tag-specific linear sparse reconstructions. In: IEEE conference on computer vision and pattern recognition (CVPR)
Little RJA, Rubin DB (2014) Statistical analysis with missing data, vol 333. Wiley, New York
Liu Y, Wen K, Gao Q, Gao X, Nie F (2018) SVM based multi-label learning with missing labels for image annotation. Pattern Recognit 78:307–317
Liu Z, Pan Q, Dezert J, Martin A (2016) Adaptive imputation of missing values for incomplete pattern classification. Pattern Recognit 52:85–95
Luo Y, Liu T, Tao D, Xu C (2015) Multiview matrix completion for multilabel image classification. IEEE Trans Image Process 24(8):2355–2368
Malek-Mohammadi M, Babaie-Zadeh M, Amini A, Jutten C (2014) Recovery of low-rank matrices under affine constraints via a smoothed rank function. IEEE Trans Signal Process 62(4):981–992
Marvasti F (2012) Nonuniform sampling: theory and practice. Springer, Berlin
Moradipari A, Shahsavari S, Esmaeili A, Marvasti F (2017) Using empirical covariance matrix in enhancing prediction accuracy of linear models with missing information. In: 2017 International conference on sampling theory and applications (SampTA)
Natarajan N, Dhillon IS (2014) Inductive matrix completion for predicting gene disease associations. Bioinformatics 30(12):i60–i68
Shang F, Jiao LC, Liu Y, Tong H (2013) Semi-supervised learning with nuclear norm regularization. Pattern Recognit 46(8):2323–2336
Song Y, Zhang C, Lee J, Wang F, Xiang S, Zhang D (2009) Semi-supervised discriminative classification with application to tumorous tissues segmentation of MR brain images. Pattern Anal Appl 12(2):99–115
Trohidis K, Tsoumakas G, Kalliris G, Vlahavas IP (2008) Multi-label classification of music into emotions. In: ISMIR, vol 8
Tu W, Sun S (2013) Semi-supervised feature extraction for EEG classification. Pattern Anal Appl 16(2):213–222
Turnbull D, Barrington L, Torres D, Lanckriet G (2008) Semantic annotation and retrieval of music and sound effects. IEEE Trans Audio Speech Lang Process 16(2):467–476
Wang Q, Ruan L, Zhang Z, Si L (2013) Learning compact hashing codes for efficient tag completion and prediction. In: Proceedings of the 22nd ACM international conference on information and knowledge management
Wu B, Lyu S, Ghanem B (2016) Constrained submodular minimization for missing labels and class imbalance in multi-label learning. In: AAAI
Xu M, Jin R, Zhou Z-H (2013) Speedup matrix completion with side information: application to multi-label learning. In: Advances in neural information processing systems, pp 2301–2309
Funding
F Marvasti would like to thank Iran National Science Foundation (INSF) for supporting him through grants #930027 and #93010264.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Esmaeili, A., Behdin, K., Fakharian, M.A. et al. Transductive multi-label learning from missing data using smoothed rank function. Pattern Anal Applic 23, 1225–1233 (2020). https://doi.org/10.1007/s10044-020-00869-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10044-020-00869-6