Part of Advances in Neural Information Processing Systems 15 (NIPS 2002)
Sariel Har-Peled, Dan Roth, Dav Zimak
The constraint classiﬁcation framework captures many ﬂavors of mul- ticlass classiﬁcation including winner-take-all multiclass classiﬁcation, multilabel classiﬁcation and ranking. We present a meta-algorithm for learning in this framework that learns via a single linear classiﬁer in high dimension. We discuss distribution independent as well as margin-based generalization bounds and present empirical and theoretical evidence showing that constraint classiﬁcation beneﬁts over existing methods of multiclass classiﬁcation.