nips nips2002 nips2002-19 nips2002-19-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Gunnar Rätsch, Sebastian Mika, Alex J. Smola
Abstract: In this paper we consider formulations of multi-class problems based on a generalized notion of a margin and using output coding. This includes, but is not restricted to, standard multi-class SVM formulations. Differently from many previous approaches we learn the code as well as the embedding function. We illustrate how this can lead to a formulation that allows for solving a wider range of problems with for instance many classes or even “missing classes”. To keep our optimization problems tractable we propose an algorithm capable of solving them using twoclass classifiers, similar in spirit to Boosting.
[1] E.L. Allwein, R.E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113–141, 2000.
[2] K.P. Bennett, A. Demiriz, and J. Shawe-Taylor. A column generation algorithm for boosting. In P. Langley, editor, Proc. 17th ICML, pages 65–72, San Francisco, 2000. Morgan Kaufmann.
[3] B. Caputo and G. R¨ tsch. Adaptive codes for visual categories. November 2002. Unpublished a manuscript. Partial results presented at NIPS’02.
[4] K. Crammer and Y. Singer. On the learnability and design of output codes for multiclass problems. In N. Cesa-Bianchi and S. Goldberg, editors, Proc. Colt, pages 35–46, San Francisco, 2000. Morgan Kaufmann.
[5] O. Dekel and Y. Singer. Multiclass learning by probabilistic embeddings. In NIPS, vol. 15. MIT Press, 2003.
[6] T.G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Aritifical Intelligence Research, 2:263–286, 1995.
[7] V. Guruswami and A. Sahai. Multiclass learning, boosing, and error-correcting codes. In Proc. of the twelfth annual conference on Computational learning theory, pages 145–155, New York, USA, 1999. ACM Press.
[8] S. Har-Peled, D. Roth, and D. Zimak. Constraint classification: A new approach to multiclass classification and ranking. In NIPS, vol. 15. MIT Press, 2003.
[9] T.J. Hastie and R.J. Tibshirani. Classification by pairwise coupling. In M.I. Jordan, M.J. Kearnsa, and S.A. Solla, editors, Advances in Neural Information Processing Systems, vol. 10. MIT Press, 1998.
[10] R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In A. J. Smola, P. L. Bartlett, B. Sch¨ lkopf, and D. Schuurmans, editors, Advances in o Large Margin Classifiers, pages 115–132, Cambridge, MA, 2000. MIT Press.
[11] R. Jin and Z. Ghahramani. Learning with multiple labels. In NIPS, vol. 15. MIT Press, 2003.
[12] S. Nash and A. Sofer. Linear and Nonlinear Programming. McGraw-Hill, New York, NY, 1996.
[13] G. R¨ tsch, A. Demiriz, and K. Bennett. Sparse regression ensembles in infinite and finite a hypothesis spaces. Machine Learning, 48(1-3):193–221, 2002. Special Issue on New Methods for Model Selection and Model Combination.
[14] G. R¨ tsch, M. Warmuth, S. Mika, T. Onoda, S. Lemm, and K.-R. M¨ ller. Barrier boosting. In a u Proc. COLT, pages 170–179, San Francisco, 2000. Morgan Kaufmann.
[15] R.E. Schapire. Using output codes to boost multiclass learning problems. In Machine Learning: Proceedings of the 14th International Conference, pages 313–321, 1997.
[16] B. Sch¨ lkopf, A. Smola, R.C. Williamson, and P.L. Bartlett. New support vector algorithms. o Neural Computation, 12:1207 – 1245, 2000.
[17] N. Sloane. Personal homepage. http://www.research.att.com/˜njas/.
[18] W. Utschick. Error-Correcting Classification Based on Neural Networks. Shaker, 1998.
[19] W. Utschick and W. Weichselberger. Stochastic organization of output codes in multiclass learning problems. Neural Computation, 13(5):1065–1102, 2001.
[20] V.N. Vapnik and A.Y. Chervonenkis. A note on one class of perceptrons. Automation and Remote Control, 25, 1964.
[21] J. Weston and C. Watkins. Multi-class support vector machines. Technical Report CSD-TR-9804, Royal Holloway, University of London, Egham, 1998.