nips nips2002 nips2002-59 nips2002-59-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sariel Har-Peled, Dan Roth, Dav Zimak
Abstract: The constraint classification framework captures many flavors of multiclass classification including winner-take-all multiclass classification, multilabel classification and ranking. We present a meta-algorithm for learning in this framework that learns via a single linear classifier in high dimension. We discuss distribution independent as well as margin-based generalization bounds and present empirical and theoretical evidence showing that constraint classification benefits over existing methods of multiclass classification.
[AB99] M. Anthony and P. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, England, 1999. [ADW94] C. Apte, F. Damerau, and S. M. Weiss. Automated learning of decision rules for text categorization. Information Systems, 12(3):233–251, 1994. [ASS00] E. Allwein, R.E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. In Proc. 17th International Conf. on Machine Learning, pages 9–16. Morgan Kaufmann, San Francisco, CA, 2000. )&)()(FH (& [BM98] C.L. Blake and C.J. Merz. UCI repository of machine learning databases, 1998. [Bri94] e [BCHL95] S. Ben-David, N. Cesa-Bianchi, D. Haussler, and P. Long. Characterizations of learnability for classes of valued functions. J. Comput. Sys. Sci., 50(1):74–86, 1995. - E. Brill. Some advances in transformation-based part of speech tagging. In AAAI, Vol. 1, pages 722–727, 1994. [CCRR99] A. Carlson, C. Cumby, J. Rosen, and D. Roth. The SNoW learning architecture. Technical Report UIUCDCS-R-992101, UIUC Computer Science Department, May 1999. [CS00] K. Crammer and Y. Singer. On the learnability and design of output codes for multiclass problems. In Computational Learing Theory, pages 35–46, 2000. [CS01] K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. In COLT/EuroCOLT, pages 99–115, 2001. [DB95] T. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1995. [DH73] R. Duda and P. Hart. Pattern Classification and Scene Analysis. Wiley, New York, 1973. [DKR97] I. Dagan, Y. Karov, and D. Roth. Mistake-driven learning in text categorization. In EMNLP-97, The Second Conference on Empirical Methods in Natural Language Processing, pages 55–63, 1997. [EZR01] Y. Even-Zohar and D. Roth. A sequential model for multi class classification. In EMNLP-2001, the SIGDAT Conference on Empirical Methods in Natural Language Processing, pages 10–19, 2001. [HPRZ02] S. Har-Peled, D. Roth, and D. Zimak. Constraint classification: A new approach to multiclass classification. In Proc. 13th International Conf. of Algorithmic Learning Theory, pages 365–397, 2002. [HT98] T. Hastie and R. Tibshirani. Classification by pairwise coupling. In NIPS-10, The 1997 Conference on Advances in Neural Information Processing Systems, pages 507–513. MIT Press, 1998. [Jel98] F. Jelinek. Statistical Methods for Speech Recognition. The MIT Press, Cambridge, Massachusetts, 1998. [LBD 89] Y. Le Cun, B. Boser, J. Denker, D. Hendersen, R. Howard, W. Hubbard, and L. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1:pp 541, 1989. [LS97] D. Lee and H. Seung. Unsupervised learning by convex and conic coding. In Michael C. Mozer, Michael I. Jordan, and Thomas Petsche, editors, Advances in Neural Information Processing Systems, volume 9, page 515. The MIT Press, 1997. [Maa00] W. Maass. On the computational power of winner-take-all. Neural Computation, 12(11):2519–2536, 2000. [Nil65] Nils J. Nilsson. Learning Machines: Foundations of trainable pattern-classifying systems. McGraw-Hill, New York, NY, 1965. [Rot98] D. Roth. Learning to resolve natural language ambiguities: A unified approach. In Proc. of AAAI, pages 806–813, 1998. [Vap98] V. Vapnik. Statistical Learning Theory. Wiley, 605 Third Avenue, New York, New York, 10158-0012, 1998. [WW99] J. Weston and C. Watkins. Support vector machines for multiclass pattern recognition. In Proceedings of the Seventh European Symposium On Artificial Neural Networks, 4 1999.