[ Overview | Participants | Funding ]
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 multilable 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 classifer in high dimension and can also be viewd as a network of properly trained linear classifiers in a low dimension. We also study distribution independent bounds for many multiclass learning algorithms, including winner-take-all (WTA) as well as margin-based generalization bounds.