LibCVM Toolkit Version: 2.2 (beta)

Introduction

The LibCVM Toolkit is a C++ implementation of the improved Core Vector Machine (CVM) and recently developed Ball Vector Machine (BVM), which are fast Support Vector Machine (SVM) training algorithms using core-set approximation on very large scale data sets. It is adapted from the LIBSVM implementation (version 2.85). The code has been used on a large range of problems, including network intrusion detection, face detection and implicit surface modeling.

The main features of the toolkit are the following:

• more stable core set selection
• adaptive epsilon approximation solution
• sparse caching of kernel evaluations
• can handle millions of training examples
• supports standard and several other nonlinear kernel functions
• supports dense and sparse vector representations
• supports multiple training data files and label renaming
• supports BVM/CVM/CVM-LS for large-scale classification
• supports Core Vector Data Description (CVDD) for large-scale novelty detection
  
• supports Core Vector Regression (CVR) for large-scale sparse least-squares regression

Pending features:

• multiclass CVM/BVM
• probabilistic output estimation for CVM

If you have any suggestions or bug findings, please email to ivor.tsang@gmail.com. Thank you!

Download

• LibCVM

The toolkit is free for research purpose. The software is not tested under Linux/Unix platform, and the performance under Linux/Unix platform may not be reliable. The software must not be further distributed without prior permission of the authors. The author is not responsible for implications from the use of this software. If you use LibCVM Toolkit in your scientific work, please cite as

• Ivor W. Tsang, James T. Kwok, Pak-Ming Cheung. Core vector machines: Fast SVM training on very large data sets. Journal of Machine Learning Research, 6:363-392, 2005.
• Ivor W. Tsang, Andras Kocsor, James T. Kwok. Simpler core vector machines with enclosing balls. Proceedings of the Twenty-Fourth International Conference on Machine Learning (ICML), Corvallis, Oregon, USA, June 2007.

How to Use

The toolkit consists of two modules, bvm_train for SVM training and bvm_predict for SVM prediction. Since the LibCVM Toolbox is adapted from the LIBSVM, some options are used for LIBSVM only. The options of bvm_train are:

Usage: bvm-train [options] training_set_file [model_file]
options:
-s svm_type : set type of SVM (default 9)
	 0 -- C-SVC
	 1 -- nu-SVC
	 2 -- one-class SVM
	 3 -- epsilon-SVR
	 4 -- nu-SVR
	 5 -- CVDD (Core Vector Data Description for novelty detection)
	      [Tsang, Kwok, Cheung, JMLR 2005]
	 6 -- CVM (sqr. hinge-loss for classification) [Tsang, Kwok, Cheung, JMLR 2005]
	 7 -- CVM-LS (sqr. eps.-insensitive loss for sparse least-squares classification)
	      [Tsang, Kwok, Lai, ICML 2005]
	 8 -- CVR [Tsang, Kwok, Lai, ICML 2005], [Tsang, Kwok, Zurada, TNN 2006]
	 9 -- BVM [Tsang, Kocsor, Kwok, ICML 2007]
-t kernel_type : set type of kernel function (default 2)
	0 -- linear: u'*v
	1 -- polynomial: (gamma*u'*v + coef0)^degree
	2 -- radial basis function: exp(-gamma*|u-v|^2)
	3 -- sigmoid: tanh(gamma*u'*v + coef0)
	4 -- precomputed kernel (kernel values in training_set_file)
	5 -- laplacian: exp(-sqrt(gamma)*|u-v|)
	6 -- normalized poly: ((gamma*u'*v+coef0)/sqrt((gamma*u'*u+coef0)*(gamma*v'*v+coef0)))^degree
	7 -- inverse distance: 1/(sqrt(gamma)*|u-v|+1)
	8 -- inverse square distance: 1/(gamma*|u-v|^2+1)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma in kernel function (default -1, which sets 1/averaged distance between patterns)
-r coef0 : set coef0 in kernel function (default 0)
-c cost : set the regularization parameter C(= cost) of C-SVC, eps.-SVR, nu-SVR, BVM and CVDD/CVM,
          and the regularization parameter C/(mu*m) in CVM-LS s.t. (mu = s_ratio/(cost*m))
          (default 100 for BVM/CVDD/CVM/CVM-LS)
-C s_ratio : set the scale parameter C = s_ratio*max|Y_i| in CVR, 
             and the scale parameter C = s_ratio in CVM-LS (same as the scale parameter in LASSO)
             (default 10000 for CVR/CVM-LS)
-u mu_ratio : set the regularization parameter mu = mu_ratio*max|Y_i| in CVR (default = 0.02)
-n nu : set the parameter nu of nu-SVC, one-class SVM, and nu-SVR (default 0.5)
-p epsilon : set the epsilon in loss function of epsilon-SVR (default 0.1)
-m cachesize : set cache memory size in MB (default 200)
-e epsilon : set tolerance of termination criterion
 (In CVM/BVM, default eps=-1 which sets eps according to the bound |f(x)-f(x)^*|; default 1e-3 for others)
-f max #CVs : MAX number of Core Vectors in binary CVM and BVM (default 50000)
-h shrinking: whether to use the shrinking heuristics, 0 or 1 (default 1)
-b probability_estimates: whether to train a SVC or SVR model for probability estimates, 0 or 1 (default 0)
-wi weight: set the parameter C of class i to weight*C, for C-SVC (default 1)
-v n: n-fold cross validation mode
-a size: sample size for probabilistic sampling (default 60)

Example: Zero/one digit classification using the Gaussian kernel:

    bvm_train -s 9 -t 2 -c 100 zero_one.txt zero_one.model.txt

Example: Forest Cover Type binary class data using the Gaussian kernel:

    bvm_train -s 9 -t 2 -c 10000 -g 1e-4 forest.txt forest.model.txt

Example: KDDCUP-99 Intrusion detection binary class data using the Gaussian kernel:

    bvm_train -s 9 -t 2 -c 1000000 intrusion.txt intrusion.model.txt

Example: Regression using the Gaussian kernel:

    bvm_train -s 8 -t 2 -u 0.01 -C 20000 census.txt census.model.txt

    bvm_train -s 8 -t 2 -u 0.03 -C 100000 cpu.txt cpu.model.txt

Note that -g -1 option can be used to set the width (gamma) of the Gaussian kernel exp(-gamma*|u-v|^2), where

1/gamma = sum ||x_i-x_j||^2/m^2

is the average distance between patterns from a subsampled training set (with 5000 patterns).

The usage of bvm_predict is:

Usage: bvm_predict [options] test_file model_file output_file 

options:

   -b probability_estimates: whether to predict probability estimates, 0 or 1 (default 0); 

      one-class SVM not supported yet

   -r Ranking: whether to output the ranking score or not, 0 or 1 (default 0)

Example: Zero/one digit classification:

    bvm_predict zero_one.test.txt zero_one.model.txt zero_one.output.txt

Example: Forest cover type binary class classification:

    bvm_predict forest.test.txt forest.model.txt forest.output.txt

Example: KDDCUP-99 intrusion detection binary class classification:

    bvm_predict intrusion.test.txt intrusion.model.txt intrusion.output.txt

Example: Regression:

    bvm_predict census.test.txt census.model.txt census.output.txt

    bvm_predict cpu.test.txt cpu.model.txt cpu.output.txt

 

File Format

The LibCVM Toolkit supports both sparse and dense data representations. The sparse format is the same as in SVMlight and LIBSVM. Each line represents one training example and is of the form:

    <line> .=. <target> <feature>:<value> <feature>:<value> ... <feature>:<value>

    <target> .=. <label> | <float> 
    <feature> .=. <unsigned integer>

    <value> .=. <float>

For the dense format, each line represents one training example and is of the form:

    <line> .=. <value>,<value>, ... <value>,<target>

    <target> .=. <label> | <float> 
    <value> .=. <float> 	 

For the multiple training file mode, the input file is started with a header:

#m
N M
<file name 1>
...
<file name N>
<label renaming rule 1>
...
<label renaming rule M>

The label renaming rule is defined as:

<label renaming rule> .=. <original label>><new label>

#m
3 6
usps1.txt
usps2.txt
usps3.txt
0>1
1>-1
2>1
3>-1
4>1
5>-1

Data Files

Some classification and regresssion data sets used in experiments:

Extended MIT face + non-face images data set (Dense format: training 489,410 patterns, testing 24,045 patterns, 361 attributes) (full Sets)

Extended USPS 0/1digit images data set (Sparse format: training 266,079 patterns, testing 75,383 patterns, 676 attributes) (full Sets)

Forest Cover Type binary class data set (Sparse format: training 522,910 patterns, testing 58,102 patterns, 54 attributes)

KDDCUP-99 intrusion detection binary class data set (Sparse format: training 4,898,431 patterns, testing 311,029 patterns, 127 attributes)

Letter data set (Sparse format: training 15,000 patterns, testing 5,000 patterns, 16 attributes)

Reuters (money-fx/non money-fx) data set (Sparse format: training 7,770 patterns, testing 3,299 patterns, 8,315 attributes)

IJCNN1 data set (Sparse format: training 49,990 patterns, testing 91,701 patterns, 22 attributes)

Web data set (Sparse format: training 49,749 patterns, testing 14,951 patterns, 300 attributes)

Census housing regression data set (Sparse format: training 18,186 patterns, testing 2,273 patterns, 121attributes)

Computer activity regression data set (Sparse format: training 6,554 patterns, testing 819 patterns, 21attributes)

Other References for Core-Set Approximation and Minimum Enclosing Balls

1. Mihai Badoiu, Kenneth L. Clarkson. Smaller core-sets for balls. SODA '03: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003.
2. Piyush Kumar, Joseph S. B. Mitchell, and E. Alper Yıldırım. Approximate minimum enclosing balls in high dimensions using core-sets. The ACM Journal of Experimental Algorithmics, Vol. 8, Article 1 (2003).
3. Pankaj K. Agarwal, Sariel Har-Peled and Kasturi R. Varadarajan. Geometric Approximation via Coresets.
4. Piyush Kumar and E. Alper Yıldırım. Minimum volume enclosing ellipsoids and core sets, Journal of Optimization Theory and Applications, 126 (1) pp. 1-21 (2005).
5. Ivor W. Tsang, James T. Kwok, Pak-Ming Cheung. Very large SVM training using core vector machines.. AISTATS, Jan 2005.
6. Ivor W. Tsang, James T. Kwok, Kimo T. Lai. Core Vector Regression for Very Large Regression Problems. Proceedings of the Twentieth-Second International Conference on Machine Learning (ICML-2005), pp.913-920, Bonn, Germany, August 2005.
7. Ivor W. Tsang, James T. Kwok, Jacek M. Zurada. Generalized core vector machines. IEEE Transactions on Neural Networks, 17(5): 1126- 1140, Sept 2006.
8. Rina Panigrahy. Minimum Enclosing Polytope in High Dimensions.
9. Ivor W. Tsang, Andras Kocsor, James T. Kwok. Efficient kernel feature extraction for massive data sets. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'06): pp.724-729, Philadelphia, USA, August 2006.
10. Ivor W. Tsang, Andras Kocsor, James T. Kwok. Diversified SVM ensembles for large data sets. Proceedings of the European Conference on Machine Learning (ECML 2006), pp.792-800, Berlin, Germany, September 2006.
11. S. Asharaf, M. Narasimha Murty, Shirish Krishnaj Shevade. Cluster Based Core Vector Machine. Proceedings of International Conference on Data Mining (ICDM) 2006: 1038-1042, 2006.
12. Yulai Xie, Jack Snoeyink, Jinhui Xu. Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope. Proceedings of the twenty-second annual symposium on Computational geometry, pp: 21 - 29, 2006.
13. Ivor W. Tsang, James T. Kwok. Large-scale sparsified manifold regularization. Proceedings of the Neural Information Processing Systems (NIPS), Vancouver, Canada, December 2006.
14. Ivor W. Tsang, James T. Kwok. Authors' Reply to the "Comments on the Core Vector Machines: Fast SVM Training on Very Large Data Set".
    
15. Sariel Har-Peled, Dan Roth, Dav Zimak. Maximum Margin Coresets for Active and Noise Tolerant Learning. Proceedings of 20th International Joint Conference on Artificial Intelligence (IJCAI) 2007: 836-841
16. Sariel Har-Peled, Akash Kushal: Smaller Coresets for k-Median and k-Means Clustering. Discrete & Computational Geometry 37(1): 3-19 (2007).
17. Seshikanth Varma, S. Asharaf, M. Narasimha Murty. Rough Core Vector Clustering. Pattern Recognition and Machine Intelligence, 2007.
18. Seshikanth Varma, S. Asharaf, M. Narasimha Murty. Core Vector Clustering. Proceedings of the 3rd Indian International Conference on Artificial Intelligence, Pune, India, 565-574, 2007.
19. S. Asharaf, M. Narasimha Murty, S. K. Shevade. Multiclass core vector machine. Proceedings of the 24th international conference on Machine learning (ICML), Corvalis, Oregon, Pages: 41 - 48, 2007.
20. Lessmann, Stefan Li, Ning Voss, Stefan. A Case Study of Core Vector Machines in Corporate Data Mining. Proceedings of the 41st Annual Hawaii International Conference on System Sciences, 78-78, 2008.
    
21. Kenneth L. Clarkson. Coresets, Sparse Greedy Approximation, and Frank-Wolfe Algorithm. SODA '08: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2008.
22. E. Alper Yıldırım. Two algorithms for the minimum enclosing ball problem. SIAM J. Optim. Volume 19, Issue 3, pp. 1368-1391, 2008
23. Ivor W. Tsang, Andras Kocsor, James T. Kwok. Large-Scale Maximum Margin Discriminant Analysis Using Core Vector Machines. IEEE Transactions on Neural Networks, 19(4) 610-624, April 2008
24. Piyush Rai, Hal Daum´e III, Suresh Venkatasubramanian. Streamed Learning: One-Pass SVMs. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI) , 2009
25. Aditya Krishna Menon. Large-Scale Support Vector Machines: Algorithms and Theory. 2009
26. Fu-Lai Chung, Zhaohong Deng, Shitong Wang. From minimum enclosing ball to fast fuzzy inference system training on large datasets. IEEE Transactions on Fuzzy Systems, Volume 17, Issue 1, P. 173 - 184, Feb 2009
27. Di Wanga, Bo Zhanga, Peng Zhanga, and Hong Qiaob. An online core vector machine with adaptive MEB adjustment Pattern Recognition , Volume 43, Issue 10, P. 3468-3482, October 2010
28. Stefano Lodi, Ricardo Nanculef, Claudio Sartori. Single-Pass Distributed Learning of Multi-Class SVMs using Core-Sets. Proceedings of SIAM Data Mining (SDM), 2010
29. Bin Gu, Jian-Dong Wang and Tao Li. Ordinal-Class Core Vector Machine. Journal of Computer Science and Technology , Volume 25, Number 4, 699-708, 2010
30. Yi-Hung Liu, Yan-Chen Liu, Yen-Jen Chen. Fast Support Vector Data Descriptions for Novelty Detection . IEEE Transactions on Neural Networks, Volume 21, Issue 8, P. 1296 - 1313, Aug 2010
31. Kenneth L. Clarkson, Elad Hazan, David P. Woodruff. Sublinear Optimization for Machine Learning. 2010
32. Piyush Kumar and E. Alper Yıldırım. A Linearly Convergent Algorithm for Support Vector Classification with a Core-set Result. INFORMS Journal on Computing, 2010
33. Ankan Saha, S. V. N. Vishwanathan, and Xinhua Zhang. New Approximation Algorithms for Minimum Enclosing Convex Shapes. ACM-SIAM Syposium on Discrete Algorithms (SODA), 2011
34. Dijun Luo and Heng Huang. Ball Ranking Machine for Content-Based Multimedia Retrieval. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 2011
35. Zhaohong Deng, Kup-Sze Choi, Fu-Lai Chung, Shitong Wang. Scalable TSK Fuzzy Modeling for Very Large Datasets Using Minimal-Enclosing-Ball Approximation. IEEE Transactions on Fuzzy Systems, Volume 19, Issue 2, P. 210 -226, April 2011