›› 2010, Vol. 25 ›› Issue (4): 699-708.doi: 10.1007/s11390-010-1054-y

• Special Section on Advances in Machine Learning and Applications • Previous Articles     Next Articles

Ordinal-Class Core Vector Machine

Bin Gu1(顾 彬), Jian-Dong Wang1(王建东), and Tao Li2(李 涛)   

  1. 1. Department of Computer Science and Engineering, Nanjing University of Aeronautics and Astronautics Nanjing 210016, China
    2. College of Electronic and Information Engineering, Nanjing University of Information Science and Technology Nanjing 210044, China
  • Received:2009-04-05 Revised:2010-01-18 Online:2010-07-09 Published:2010-07-09
  • About author:
    Bin Gu is currently a Ph.D. candidate in computer science in Nanjing University of Aeronautics and Astronautics. He received the B.S. degree in 2005 from Nanjing University of Aeronautics and Astronautics. In the same year, he was admitted to study for an M.Sc. degree in Nanjing University of Aeronautics and Astronautics without entrance examination. His research interests focus on machine learning and data mining.
    Jian-Dong Wang graduated from Radio Department of Shanghai Jiaotong University in 1967. He is now a professor and Ph.D. supervisor of the College of Information Science and Technology, NUAA. His research interests include machine learning, data mining and information security.
    Tao Li is currently a Ph.D. candidate in in computer science in Nanjing University of Aeronautics and Astronautics. He received his B.S. degree in computer science and M.S. degree in system analysis and integration from Nanjing University of Information Science and Technology, in 1999 and 2002 respectively. His research interests include recommender system and machine learning.
  • Supported by:

    This work was supported by the National High-Tech Research and Development 863 Program of China under Grant No. 2006AA12A106.

Ordinal regression is one of the most important tasks of relation learning, and several techniques based on support vector machines (SVMs) have also been proposed for tackling it, but the scalability aspect of these approaches to handle large datasets still needs much of exploration. In this paper, we will extend the recent proposed algorithm Core Vector Machine (CVM) to the ordinal-class data, and propose a new algorithm named as Ordinal-Class Core Vector Machine (OCVM). Similar with CVM, its asymptotic time complexity is linear with the number of training samples, while the space complexity is independent with the number of training samples. We also give some analysis for OCVM, which mainly includes two parts, the first one shows that OCVM can guarantee that the biases are unique and properly ordered under some situation; the second one illustrates the approximate convergence of the solution from the viewpoints of objective function and KKT conditions. Experiments on several synthetic and real world datasets demonstrate that OCVM scales well with the size of the dataset and can achieve comparable generalization performance with existing SVM implementations.


[1] Chu W, Keerthi S S. New approaches to support vector ordinal regression. In Proc. the 22nd International Conference on Machine Learning (ICML,2005), Bonn, Germany, Aug. 7-11, 2005, pp.145-152.

[2] Herbrich R, Graepel T, Obermayer K. Support vector learning for ordinal regression. In Proc. the International Conference on Artificial Neural Networks, Edinburgh, UK, Sept. 7-10, 1999, pp.97-10.

[3] Kou Y, Shen D, Yu G, Nie T. Combining local scoring and global aggregation to rank entities for deep web queries. J. Comput. Sci. Technol., 2009, 24(4): 626-637.

[4] Amnon S, Anat L. Taxonomy of large margin principle algorithms for ordinal regression problems. Technical Report 2002-39, Leibniz Center for Research, School of Computer Science and Eng., the Hebrew University of Jerusalem.

[5] Cardoso J S, Pinto da Costa J F, Cardoso M J. Modelling ordinal relations with SVMs: An application to objective aesthetic evaluation of breast cancer conservative treatment. Neural Networks, 2005, 18(5/6): 808-817.

[6] Michael A M, Konstantinos G Z. Airport capacity vs. demand: Mismatch or mismanagement? Transportation Research Part A, 2008, 42(1): 203-226.

[7] Michael V M, Hanif D S, Antonio A T. A probabilistic framework for weather-based rerouting and delay estimations within an airspace planning model. Transportation Research Part C, 2008, 16(4): 410-431.

[8] Vapnik V. Statistical Learning Theory. New York: Wiley, 1998.

[9] Cardoso J S, Costa J F P. Learning to classify ordinal data: The data replication method. Journal of Machine Learning Research, 2007, 8: 1393-1429.

[10] B\v adoiu M, Clarkson K L. Optimal core-sets for balls. Computational Geometry: Theory and Applications, 2008, 40(1): 14-22.

[11] Kumar P, Mitchell J S B, Yildirim E A. Approximate minimum enclosing balls in high dimensions using core-sets. J. Exp. Algorithmics, January 2003, 8: Article No.1.1.

[12] Tsang I W, Kwok J T, Cheung P M. Core vector machines: Fast SVM training on very large data sets. Journal of Machine Learning Research, 2005, 6: 363-392.

[13] Asharaf S, Murty M N, Shevade S K. Multiclass core vector machine. In Proc. the 24th International Conference on Machine Learning, Corvallis, USA, June 20-24, 2007, pp.41-48.

[14] Tsang I W, Kwok J T, Zurada J M. Generalized core vector machines. IEEE Transactions on Neural Networks, 2006, 17(5): 1126-1140.

[15] Tsang I W, Kwok J T, Lai K T. m Core vector regression for very large regression problems. In Proc. the 22nd International Conference on Machine Learning, Bonn, Germany, Aug. 7-11, 2005, pp.913-920.

[16] Tsang I W, Kocsor A, Kwok J T. Simpler core vector machines with enclosing balls. In Proc. the 24th International Conference on Machine Learning (ICML), Corvallis, Oregon, USA, June 20-24, 2007, pp.911-918.

[17] Shevade S, Chu W. Minimum enclosing spheres formulations for support vector ordinal regression. In Proc. the 6th International Conference on Data Mining, Hong Kong, China, Dec. 18-22, 2006, pp.1054-1058.

[18] Platt J C. Fast Training of Support Vector Machines Using Sequential Minimum Optimization. Advances in Kernel Methods--Support Vector Learning, Sch\"olkopf B, Burges C, Smola A (eds.), Cambridge MA: MIT Press, 1999, pp.169-184.

[19] Li L, Lin H T. Ordinal regression by extended binary classification. In Proc. the Conference on Neural Information Processing Systems 19, Vancouver, Canada, Dec. 3-6, 2007, pp.865--72.

[20] Liu T Y, Xu J, Qin T, Xiong W, Li H. Letor: Benchmark dataset for research on learning to rank for information retrieval. In \emphProc. the Learning to Rank Workshop in the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR,2007), Amsterdam, Netherland, June 23-27, 2007, pp.3-10.

[21] Boyd S, Vandenberghe L. Convex optimization. Stanford University, Department of Electrical Engineering, 2003.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved