Constraint Classification: A New Approach to Multiclass Classification
and Ranking
Sariel Har-Peled,
Dan Roth,
and Dav Zimak
We introduce constraint classification, a framework
capturing many flavors of multiclass classification
including multilabel classification and ranking, and
present a meta-algorithm for learning in this framework.
We provide generalization bounds when using a collection
of k linear functions to represent each hypothesis.
We also present empirical and theoretical evidence that
constraint classification is more powerful than existing
methods of multiclass classification.