Multi-Label Prediction via Compressed Sensing

Abstract

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.

References in corpus (11)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements

Cited by in corpus (66)

• Label-Embedding for Image Classification
• Beyond One-hot Encoding: lower dimensional target embedding
• Large-scale Multi-label Learning with Missing Labels
• Block-Sparse Recovery via Convex Optimization
• Multi-view Vector-valued Manifold Regularization for Multi-label Image Classification
• Multi-Target Regression via Random Linear Target Combinations
• Two are better than one: Fundamental parameters of frame coherence
• Kernel Belief Propagation
• The Landmark Selection Method for Multiple Output Prediction
• Learning Deep Latent Spaces for Multi-Label Classification
• Orthogonal Matching Pursuit with Replacement
• Maximum Margin Output Coding
• Logarithmic Time Online Multiclass prediction
• DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification
• Label Embedding Network: Learning Label Representation for Soft Training of Deep Networks
• Towards Scalable and Reliable Capsule Networks for Challenging NLP Applications
• PECOS: Prediction for Enormous and Correlated Output Spaces
• Cell Detection in Microscopy Images with Deep Convolutional Neural Network and Compressed Sensing
• Random forests with random projections of the output space for high dimensional multi-label classification
• Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
• Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products
• Structured Prediction Energy Networks
• Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation
• Taming Pretrained Transformers for Extreme Multi-label Text Classification
• Streaming Label Learning for Modeling Labels on the Fly
• Towards Label Imbalance in Multi-label Classification with Many Labels
• Error-Correcting Tournaments
• Label-aware Document Representation via Hybrid Attention for Extreme Multi-Label Text Classification
• Elucidating image-to-set prediction: An analysis of models, losses and datasets
• LdSM: Logarithm-depth Streaming Multi-label Decision Trees
• ShareBoost: Efficient Multiclass Learning with Feature Sharing
• Expressive recommender systems through normalized nonnegative models
• Locally Non-linear Embeddings for Extreme Multi-label Learning
• Deep Extreme Multi-label Learning
• DocTag2Vec: An Embedding Based Multi-label Learning Approach for Document Tagging
• Getting deep recommenders fit: Bloom embeddings for sparse binary input/output networks
• Privileged Multi-label Learning
• Sparse Recovery with Orthogonal Matching Pursuit under RIP
• Recommender systems inspired by the structure of quantum theory
• Sparse Signal Processing with Frame Theory
• Crowd Scene Analysis by Output Encoding
• Improving Pairwise Ranking for Multi-label Image Classification
• Infinite-Label Learning with Semantic Output Codes
• Federated Multiple Label Hashing (FedMLH): Communication Efficient Federated Learning on Extreme Classification Tasks
• Extreme Classification in Log Memory
• RIPML: A Restricted Isometry Property based Approach to Multilabel Learning
• Aggressive Sampling for Multi-class to Binary Reduction with Applications to Text Classification
• LightMC: A Dynamic and Efficient Multiclass Decomposition Algorithm
• Fast Label Embeddings via Randomized Linear Algebra
• Block-wise Partitioning for Extreme Multi-label Classification
• Learning Contextualized Music Semantics from Tags via a Siamese Network
• Online Multi-Label Classification: A Label Compression Method
• Collaborative Filtering and Multi-Label Classification with Matrix Factorization
• Similarity-based Multi-label Learning
• Correlated Logistic Model With Elastic Net Regularization for Multilabel Image Classification
• MUTE: Data-Similarity Driven Multi-hot Target Encoding for Neural Network Design
• Compact Learning for Multi-Label Classification
• Multi-Label Learning from Single Positive Labels
• LLC: Accurate, Multi-purpose Learnt Low-dimensional Binary Codes
• Training Convolutional Neural Networks and Compressed Sensing End-to-End for Microscopy Cell Detection
• Group Preserving Label Embedding for Multi-Label Classification
• Improving Multi-label Learning with Missing Labels by Structured Semantic Correlations
• Improving Imprecise Compressive Sensing Models
• Learning Contextualized Semantics from Co-occurring Terms via a Siamese Architecture
• On Learning Vector Representations in Hierarchical Label Spaces
• SHOE: Supervised Hashing with Output Embeddings