Multi-Label Prediction via Compressed Sensing

By Daniel J. Hsu, Sham M. Kakade, J. Langford, Tong Zhang. 2009

443 citations recorded by the source corpus.

We consider multi-label prediction problems with large output spaces under the assumption of output sparsity - that the target (label) vectors have small support. We develop a general theory for a variant of the popular error correcting output code scheme, using ideas from compressed sensing for exploiting this sparsity. The method can be regarded as a simple reduction from multi-label regression problems to binary regression problems. We show that the number of subproblems need only be logarithmic in the total number of possible labels, making this approach radically more efficient than others. We also state and prove robustness guarantees for this method in the form of regret transform bounds (in general), and also provide a more detailed analysis for the linear prediction setting.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Management Science and Operations Research

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

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Management Science and Operations Research

Citations in the corpus

Elucidating image-to-set prediction: An analysis of models, losses and datasets (2019, background): “Multi-label classification has been a long lasting problem in computer vision [72, 21, 73, 67] tackled by a wide variety of methods, such as, decomposing the problem into independent single-label classification problems [44, 72], exploiting label co-occurrences [1, 56, 34], introducing priors such a”
DeCAF: A Deep Convolutional Activation Feature for Generic Visual Recognition (2013, background): “…important when one considers classiﬁcation into a larger number of categories or with larger hidden-layer sizes, suggesting that certain sparse approaches such as Bayesian output coding (Hsu et al., 2009) may be necessary to carry out classiﬁcation into even larger number of object categories.”
Evaluation of output embeddings for fine-grained image classification (2014, methodology): “In order to collect relationships independently of data, compressed sensing [21] uses random projections whereas Error Correcting Output Codes [9] builds embeddings inspired from information theory.”
Structured Prediction Energy Networks (2015, methodology): “Motivated by recent compressed sensing approaches to multi-label classification (Hsu et al., 2009; Kapoor et al., 2012), we further assume that the first layer of the network performs a small set of linear projections of the prediction variables.”
Label-Embedding for Image Classification (2015, background): “[52], is another example of data-independent embeddings where ’ corresponds to random projections.”
Large Margin Metric Learning for Multi-Label Prediction (2015, methodology): “Besides PLST (Tai and Lin 2012), CCA (Zhang and Schneider 2011) and MMOC (Zhang and Schneider 2012) have also been shown to outperform the original compressed-sensing-based method (Hsu et al. 2009), thus we make no comparison with Hsu et al.”
Efficient max-margin multi-label classification with applications to zero-shot learning (2012, methodology): “In regression methods (Hsu et al. 2009; Ji et al. 2008; Tsoumakas and Katakis 2007), the label space is mapped onto a vector space (which might sometimes be a shared subspace of the feature space) where regression techniques can be applied straightforwardly.”
Multilabel Classification using Bayesian Compressed Sensing (2012, methodology): “In particular, experiments show that the method significantly outperforms ML-CS based method by [1] and also obtains accuracies matching 1-vs-all SVM while projecting onto Kdimensional space that is typically less than half the total number of labels.”
Multilabel Classification with Principal Label Space Transformation (2012, background): “Such a possibility allows compressive sensing (CS; Hsu et al., 2009) to reduce the number of subtasks in binary relevance to be computationally feasible for data sets with a large K.”
Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking & Other Missing Label Applications (2016, methodology): “Extreme multi-label learning algorithms typically follow a tree [4, 34, 46] or an embedding based approach [5, 6, 7, 10, 11, 14, 18, 20, 22, 27, 32, 36, 43, 45, 48, 50].”
Label Embedding Trees for Large Multi-Class Tasks (2010, methodology): “We also show that our label embedding approach outperforms other recently proposed label embedding approaches such as compressed sensing [17].”
Two-Stage Label Embedding via Neural Factorization Machine for Multi-Label Classification (2019, methodology): “Embedding method (Hsu et al. 2009; Cao et al. 2016; Yang et al. 2018; Deng et al. 2018a) is one of the most popular frameworks to learn label and feature correlations and has shown promising results.”
Towards Scalable and Reliable Capsule Networks for Challenging NLP Applications (2019, methodology): “Label embedding models (Balasubramanian and Lebanon, 2012; Chen and Lin, 2012; Cisse et al., 2013; Bi and Kwok, 2013; Ferng and Lin, 2011; Hsu et al., 2009; Ji et al., 2008; Kapoor et al., 2012; Lewis et al., 2004; Yu et al., 2014a) address the data sparsity issue with two steps: compression and dec”
Label-Embedding for Attribute-Based Classification (2013, unknown): “[12], where φ corresponds to random projections.”
Large-scale Multi-label Learning with Missing Labels (2013, methodology): “Recently, techniques have been developed that either reduce the dimension of the labels, such as the Compressed Sensing Approach (Hsu et al., 2009), PLST (Tai & Lin, 2012), CPLST (Chen & Lin, 2012), and Bayesian CS (Kapoor et al.”
Efficient Multi-label Classification with Many Labels (2013, methodology): “Label Transformation Hsu et al. (2009) proposed a three-step approach to address classification problems with a large number of labels.”