nips nips2006 nips2006-156 nips2006-156-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ling Li, Hsuan-tien Lin
Abstract: We present a reduction framework from ordinal regression to binary classification based on extended examples. The framework consists of three steps: extracting extended examples from the original examples, learning a binary classifier on the extended examples with any binary classification algorithm, and constructing a ranking rule from the binary classifier. A weighted 0/1 loss of the binary classifier would then bound the mislabeling cost of the ranking rule. Our framework allows not only to design good ordinal regression algorithms based on well-tuned binary classification approaches, but also to derive new generalization bounds for ordinal regression from known bounds for binary classification. In addition, our framework unifies many existing ordinal regression algorithms, such as perceptron ranking and support vector ordinal regression. When compared empirically on benchmark data sets, some of our newly designed algorithms enjoy advantages in terms of both training speed and generalization performance over existing algorithms, which demonstrates the usefulness of our framework. 1
[1] K. Crammer and Y. Singer. Pranking with ranking. In T. G. Dietterich, S. Becker, and Z. Ghahramani, eds., Advances in Neural Information Processing Systems 14, vol. 1, pp. 641–647. MIT Press, 2002.
[2] A. Shashua and A. Levin. Ranking with large margin principle: Two approaches. In S. Becker, S. Thrun, and K. Obermayer, eds., Advances in Neural Information Processing Systems 15, pp. 961–968. MIT Press, 2003.
[3] S. Rajaram, A. Garg, X. S. Zhou, and T. S. Huang. Classification approach towards ranking and sorting problems. In N. Lavraˇ , D. Gamberger, H. Blockeel, and L. Todorovski, eds., Machine Learning: c ECML 2003, vol. 2837 of Lecture Notes in Artificial Intelligence, pp. 301–312. Springer-Verlag, 2003.
[4] W. Chu and S. S. Keerthi. New approaches to support vector ordinal regression. In L. D. Raedt and S. Wrobel, eds., ICML 2005: Proceedings of the 22nd International Conference on Machine Learning, pp. 145–152. Omnipress, 2005.
[5] 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, eds., Advances in Large Margin Classifiers, o chapter 7, pp. 115–132. MIT Press, 2000.
[6] E. Frank and M. Hall. A simple approach to ordinal classification. In L. D. Raedt and P. Flach, eds., Machine Learning: ECML 2001, vol. 2167 of Lecture Notes in Artificial Intelligence, pp. 145–156. SpringerVerlag, 2001.
[7] H.-T. Lin and L. Li. Large-margin thresholded ensembles for ordinal regression: Theory and practice. In J. L. Balc´ zar, P. M. Long, and F. Stephan, eds., Algorithmic Learning Theory: ALT 2006, vol. 4264 of a Lecture Notes in Artificial Intelligence, pp. 319–333. Springer-Verlag, 2006.
[8] Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296, 1999.
[9] V. N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 2nd edition, 1999.
[10] P. Bartlett and J. Shawe-Taylor. Generalization performance of support vector machines and other pattern classifiers. In B. Sch¨ lkopf, C. J. C. Burges, and A. J. Smola, eds., Advances in Kernel Methods: Support o Vector Learning, chapter 4, pp. 43–54. MIT Press, 1998.
[11] J. R. Quinlan. Induction of decision trees. Machine Learning, 1(1):81–106, 1986.
[12] H.-T. Lin and L. Li. Novel distance-based SVM kernels for infinite ensemble learning. In Proceedings of the 12th International Conference on Neural Information Processing, pp. 761–766, 2005.
[13] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/˜cjlin/libsvm.