Maximum Margin Output Coding

Abstract

In this paper we study output coding for multi-label prediction. For a multi-label output coding to be discriminative, it is important that codewords for different label vectors are significantly different from each other. In the meantime, unlike in traditional coding theory, codewords in output coding are to be predicted from the input, so it is also critical to have a predictable label encoding. To find output codes that are both discriminative and predictable, we first propose a max-margin formulation that naturally captures these two properties. We then convert it to a metric learning formulation, but with an exponentially large number of constraints as commonly encountered in structured prediction problems. Without a label structure for tractable inference, we use overgenerating (i.e., relaxation) techniques combined with the cutting plane method for optimization. In our empirical study, the proposed output coding scheme outperforms a variety of existing multi-label prediction methods for image, text and music classification.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (1)

• Multi-Label Prediction via Compressed Sensing

Cited by in corpus (8)

• The Emerging Trends of Multi-Label Learning
• Multi-Target Regression via Random Linear Target Combinations
• Target-Embedding Autoencoders for Supervised Representation Learning
• Prototypical Networks for Multi-Label Learning
• Learning Max-Margin Tree Predictors
• Fast Multi-label Learning
• Correlated Logistic Model With Elastic Net Regularization for Multilabel Image Classification
• Distribution-based Label Space Transformation for Multi-label Learning