Large-scale Multi-label Learning with Missing Labels

By Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, Inderjit S. Dhillon. International Conference on Machine Learning, 2013

515 citations recorded by the source corpus.

The multi-label classification problem has generated significant interest in recent years. However, existing approaches do not adequately address two key challenges: (a) scaling up to problems with a large number (say millions) of labels, and (b) handling data with missing labels. In this paper, we directly address both these problems by studying the multi-label problem in a generic empirical risk minimization (ERM) framework. Our framework, despite being simple, is surprisingly able to encompass several recent label-compression based methods which can be derived as special cases of our method. To optimize the ERM problem, we develop techniques that exploit the structure of specific loss functions - such as the squared loss function - to obtain efficient algorithms. We further show that our learning framework admits excess risk bounds even in the presence of missing labels. Our bounds are tight and demonstrate better generalization performance for low-rank promoting trace-norm regularization when compared to (rank insensitive) Frobenius norm regularization. Finally, we present extensive empirical results on a variety of benchmark datasets and show that our methods perform significantly better than existing label compression based methods and can scale up to very large datasets such as a Wikipedia dataset that has more than 200,000 labels.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/a9c6fe887d12dab7610836de128f6961bae8f86f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking & Other Missing Label Applications (2016, methodology): “Other baseline algorithms include 1-vs-All [16], LEML [48], WSABIE [45], CPLST [10], CS [18], ML-CSSP [7] and LPSR [46].”
Multi-label Learning with Missing Labels Using Mixed Dependency Graphs (2018, methodology): “Both MC models and LEML are based on the low rank assumption of the whole label matrix.”
Max-Margin DeepWalk: Discriminative Learning of Network Representation (2016, unknown): “In practice, we factorize M instead of log M , since log M has much more non-zero entries than M and the complexity of matrix factorization is proportional to the number of non-zero entries [Yu et al., 2014].”
From Facial Expression Recognition to Interpersonal Relation Prediction (2016, background): “Although there are several algorithms [2,87,83] that perform training on heterogeneous datasets, most of these”
Structured Prediction Energy Networks (2015, methodology): “Correlations between labels can be modeled explicitly using models with low-dimensional embeddings of labels (Ji & Ye, 2009; Cabral et al., 2011; Yu et al., 2014; Bhatia et al., 2015).”
Semi-Supervised Multi-Label Learning with Incomplete Labels (2015, methodology): “We measure the classification results in terms of two standard multi-label evaluation criteria: micro-F1 measure and macro-F1 measure, which take both precision and recall into 0.1 0.2 0.3 0.4 0.5 0 0.1 0.2 0.3 0.4 0.5 0.6 msrc missing label proportion Micro−F1 Score Proposed MLR−GL FastTag LEML BR ”
Sparse Local Embeddings for Extreme Multi-label Classification (2015, methodology): “The state-of-the-art LEML algorithm [9] directly optimizes for U † , V using a regularized least squares objective.”
A network integration approach for drug-target interaction prediction and computational drug repositioning from heterogeneous information (2017, background): “This lowrank constraint not only alleviates the overfitting problem but also computationally benefits the optimization process [78].”
Dropping Convexity for Faster Semi-definite Optimization (2015, background): “• Approximate rank-r optimum: In many learning applications, such as localization [43] and multilabel learning [78], the true X (cid:63) emerges as the superposition of a low rank latent matrix plus a small perturbation term, such that X − X (cid:63)r F is small. noise—often (cid:107) (cid:107)…”
Differentially Private Matrix Completion, Revisited (2017, background): “One can also enhance this formulation using side-information like userfeatures or item-features (Yu et al., 2014).”
Towards Scalable and Reliable Capsule Networks for Challenging NLP Applications (2019, methodology): “Baselines We compare our approach to the following baselines: CNN + LR (Yu et al., 2014b) using unigrams and bigrams, CNN (Severyn and Moschitti, 2015) using additional bilinear similarity features, CNTN (Qiu and Huang, 2015) using neural tensor network, LSTM (Tay et al., 2017) us-ing single and…”
Inductive matrix completion for predicting gene–disease associations (2014, methodology): “LEML (Yu et al., 2014) Implemented identical to IMC, but does not use disease features.”
The Emerging Trends of Multi-Label Learning (2020, methodology): “Then, LEML [11] generalizes this paradigm to a flexible empirical risk minimization framework.”
Adversarial Multi-label Prediction for Spoken and Visual Signal Tagging (2019, background): “Low rank empirical risk minimization for multi-label classification (LEML) [7] considers missing labels could be linearly spanned by known labels and recovers unknown labels by low rank optimization [8].”
Multi-Label Learning with Global and Local Label Correlation (2017, methodology): “Low-rank empirical risk minimization for multi-label learning (LEML) [18] is very efficient, which also relies on a lowrank structure, and works in an inductive learning setting.”
Network Representation Learning with Rich Text Information (2015, methodology): “Therefore researchers resort to finding matrices W ∈ R k×b and H ∈ R k×d to minimize the loss function L(M, W T H) with a trace norm constraint, which is further removed by adding a penalty term to the loss function [Yu et al., 2014].”
Leveraging Uncertainty to Rethink Loss Functions and Evaluation Measures for Egocentric Action Anticipation (2018, background): “Moreover, in certain cases, some labels can be missing in the training set, which yields the problem of multi-label learning with missing labels [36].”
Learning Deep Latent Spaces for Multi-Label Classification (2017, methodology): “…is also a popular technique for multi-label classiﬁcation (Balasubramanian and Lebanon 2012; Tai and Lin 2012; Chen and Lin 2012; Bi and Kwok 2013; Hsu et al. 2009; Zhang and Schneider 2012; Zhou, Tao, and Wu 2012; Lin et al. 2014; Yu et al. 2014; Li and Guo 2015; Bhatia et al. 2015).”
Temporal Regularized Matrix Factorization for High-dimensional Time Series Prediction (2016, methodology): “Furthermore, when features are known for the time series, we can make use of interaction models such as those in [6, 24, 25].”