On the algorithmic implementation of multiclass kernel-based vector machines Export

@article{crammersvm, abstract = {In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion we cast multiclass categorization problems as a constrained optimization problem with a quadratic objective function. Unlike most of previous approaches which typically decompose a multiclass problem into multiple independent binary classification tasks, our notion of margin yields a direct method for training multiclass predictors. By using the dual of the optimization problem we are able to incorporate kernels with a compact set of constraints and decompose the dual problem into multiple optimization problems of reduced size. We describe an efficient fixed-point algorithm for solving the reduced optimization problems and prove its convergence. We then discuss technical details that yield significant running time improvements for large datasets. Finally, we describe various experiments with our approach comparing it to previously studied kernel-based methods. Our experiments indicate that for multiclass problems we attain state-of-the-art accuracy.}, address = {Cambridge, MA, USA}, author = {Crammer, Koby and Singer, Yoram}, citeulike-article-id = {3921992}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=944813}, issn = {1533-7928}, journal = {J. Mach. Learn. Res.}, keywords = {crammer, svm}, pages = {265--292}, posted-at = {2009-02-19 10:40:40}, priority = {2}, publisher = {MIT Press}, title = {On the algorithmic implementation of multiclass kernel-based vector machines}, url = {http://portal.acm.org/citation.cfm?id=944813}, volume = {2}, year = {2002} }

TY - JOUR ID - crammersvm L3 - citeulike-article-id:3921992 N2 - In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion we cast multiclass categorization problems as a constrained optimization problem with a quadratic objective function. Unlike most of previous approaches which typically decompose a multiclass problem into multiple independent binary classification tasks, our notion of margin yields a direct method for training multiclass predictors. By using the dual of the optimization problem we are able to incorporate kernels with a compact set of constraints and decompose the dual problem into multiple optimization problems of reduced size. We describe an efficient fixed-point algorithm for solving the reduced optimization problems and prove its convergence. We then discuss technical details that yield significant running time improvements for large datasets. Finally, we describe various experiments with our approach comparing it to previously studied kernel-based methods. Our experiments indicate that for multiclass problems we attain state-of-the-art accuracy. JF - J. Mach. Learn. Res. SN - 1533-7928 AD - Cambridge, MA, USA EP - 292 TI - On the algorithmic implementation of multiclass kernel-based vector machines PB - MIT Press VL - 2 SP - 265 KW - crammer KW - svm AU - Crammer, Koby AU - Singer, Yoram PY - 2002/// UR - http://portal.acm.org/citation.cfm?id=944813 ER -