  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.
