Date Added: Jun 2009
The authors consider multi-label prediction problems with large output spaces under the assumption of output sparsity - that the target (label) vectors have small support. They 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. They 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.