Overview:

We develop a new view of multiclass classification and introduce the constraint classification problem, a generalization that captures many flavors of multiclass classification. In particular, our framework captures multiclass classification, ranking problems, and multi-label classification and winner-take-all (WTA) algorithms. We study both algorithmic issues and theoretical issues, such as sample bounds. Algorithmically, based on our view, we develop a learning algorithm that learns via a single linear classifier in high dimensionality that also can be viewed as a network of properly trained linear classifiers in a low dimensionality. We also study distribution independent bounds for many multiclass learning algorithms, including winner-take-all (WTA) as well as margin-based generalization bounds.