Maximum Margin Output Coding
This work addresses multi-label prediction, a common challenge in machine learning applications like image and text classification, but it is incremental as it builds on existing output coding techniques.
The paper tackles the problem of designing output codes for multi-label prediction that are both discriminative and predictable, proposing a max-margin formulation and achieving improved performance over existing methods in image, text, and music classification.
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.