TinySVM: Support Vector Machines

Last update: $Date: 2000/12/09 06:19:15 $

TinySVM

TinySVM is an implementation of Support Vector Machines (SVMs) [Vapnik 95], [Vapnik 98] for the problem of pattern recognition. Support Vector Machines is a new generation learning algorithms based on recent advances in statistical learning theory. SVMs deliver state-of-the-art performance in real-word applications such as text categorization, hand-written character recognition. TinySVM provides efficient tools and libraries for learning and classification of SVMs.

List of Contents

• What's new
• Features
• libtinysvm Reference Manual
• Using included tools
• Download
  • Sources
  • RPM package for RedHat Linux
  • Binary package for MS-Windows
  • CVS
• Install
• Language Bindings
  • Perl
  • Python
• Questions and Bug Reports
• TODO
• References
• Related Link

What's new

• 2000-12-09: TinySVM 0.0.1 Released
  

Features

• Fast optimization algorithms stemmed from SVM_light,[Joachims/99a].
  • Working set selection based on steepest feasible descent.
  • "Shrinking" (an effective heuristics to reduce working sets dynamically)[Joachims/99a]
  • Uses sparse vector representation
  • Can handle several ten-thousands of training examples, and hundred-thousands of feature dimension.
  • Optimization for handling binary features, twice faster than SVM_light.
• Written in C++ with OOP style. Provides useful class libraries.
• Provides Perl module

Using the included Tools

Format of training data

TinySVM accepts the same representation of training data as SVM_light uses. This format has potential to handle large sparse feature vectors.

(BNF-like representation)
<class> .=. +1 | -1
<feature> .=. integer (>=1)
<value> .=. real
<line> .=. <class> <feature>:<value><feature>:<value> ... <feature>:<value>


Example
+1 201:1.2 3148:1.8 3983:1 4882:1
-1 874:0.3 3652:1.1 3963:1 6179:1
+1 1168:1.2 3318:1.2 3938:1.8 4481:1
+1 350:1 3082:1.5 3965:1 6122:0.2
-1 99:1 3057:1 3957:1 5838:0.3

See tests/train.svmdata and tests/test.svmdata in the package.

svm_learn (simple learner)

"svm_learn" accepts two arguments --- file name of training data stored in the above formats and model file in which the SVs and their weights (alpha) are stored after training. You can also select an appropriate kernel function by giving some options.
Try --help option for finding out other options.

% svm_learn -t 1 -d 2 -c 1 train.svmdata model
TinySVM - tiny SVM package
Copyright (C) 2000 Taku Kudoh All rights reserved.

  1000 examples, cache size: 1524
....................   1000   1000 0.0165 1286/ 64.3%   1286/ 64.3%
............
Checking optimality of inactive variables  re-activated: 0

Done! 1627 iterations

Number of SVs (BSVs)            719 (4)
Empirical Risk:                 0.002 (2/1000)
L1 Loss:                        4.22975
CPU Time:                       0:00:01

% ls -al model
  -rw-r--r--    1 taku-ku  is-stude    26455 Dec  7 13:40

Each learning iterations, TinySVM prints the following messages

....................   1000   1000 2.1540 1924/ 96.2%   1924/ 96.2%
....................   2000   1000 2.1540 2000/100.0%   3924/ 98.1%

This means...
• 1st column: One "." means 50 iterations.
• 2nd column: Represents the total iterations proceeded.
• 3rd column: Represents the size of current working set. It will become smaller during the shrinking process.
• 4th column: Max KKT violation value. If this value reaches termination-criterion (default 0.001), it means that the 1 st stage of the learning process has completed. After that, re-activate all shrinked examples for final check. You can omit final check using -f option.
• 5th column: Cache hit rate during last 1000 iterations.
• 6th column: Cache hit rate during all iterations.

svm_classify (simple classifier)

"svm_classify" accepts two arguments --- file name of test data stored in above formats and model file produced by svm_learn program. "svm_classify" simply outputs the accuracy for test data. You can also employ interactive classification by giving "-" as file name of test example.
Try --help option for finding out other options.

% svm_classify test.svmdata model
Accuracy = 77.8000000000% (389/500)

svm_model (model browser)

"svm_model" shows the estimated margin, VC dimension and number of SVs of given some model file.
Try --help option for finding out other options.

% svm_model model
File Name:                      model
Margin:                         0.181666
Number of SVs:                  719
Estimated VC dimension:         728.219

Download

TinySVM is free software distributed under the GNU Lesser General Public License.

Source

• TinySVM-0.01.tar.gz: HTTP

Binary package for RedHat Linux

• i386: HTTP
• SRPMS: HTTP

Binary package for MS-Windows

• HTTP

CVS

Development of TinySVM uses CVS. So latest developing version is available at CVS.
We are willing to welcome you to join CVS based development.

% cvs -d :pserver:anonymous@chasen.aist-nara.ac.jp:/cvsroot login
CVS password:   # Just hit return/enter.
% cvs -d :pserver:anonymous@chasen.aist-nara.ac.jp:/cvsroot co TinySVM

Install

• UNIX
  

   % ./configure 
   % make
   % make check
   % su
   # make install
  

  You can change default install path by using --prefix option of configure script.
  Try --help option for finding out other options.

• Windows
  If you want to build TinySVM from the source package, you need to prepare the cygwin or Borland Free C++ Builder (BCC32) environments. I think no modifications are required for building under the cygwin environments. You can build TinySVM the same way for UNIX. You can also build TinySVM under the BCC32 environment like the followings:

   cd src;
   make -f ..\Makefile.bcc32
  

  Actually, the binary package of TinySVM is built using BCC32 compiler.

Language Bindings

• Perl: see perl/TinySVM.pm file.
• Python: Under construction.

Questions and Bug Reports

If you find bugs or you have any questions please contact me via email taku-ku@is.aist-nara.ac.jp.
(Japanese mail is also (more) acceptable.)

TODO

• Transductive SVM [Vapnik 98],[Joachims 99]
• MultiClass SVM (one-for-all-others, pairwise)
• Span SVM [Vapnik 2000]
• SVR (Support Vector Regression)
• Ordinal SVR [Herbrich 2000]
• Provide some Wrapper class to handle STRING features.
• Provide DLL (Dynamic Link Libraries) for Windows environment.
• Provide an API for user customizable kernel function.
  I do not want to employ virtual function of C++ because of their poor efficiency. I will provide the API using template. (function object).

References

• [Joachims 99a] T. Joachims, 11 in: Making large-Scale SVM Learning Practical. Advances in Kernel Methods pp.169-
• [Vapnik 95] Vladimir N. Vapnik, The Nature of Statistical Learning Theory. Springer, 1998.
• [Vapnik 98] Vladimir N. Vapnik, The Statisitcal Learning Theory. Springer, 1998.
• [Joachims 99c] T. Joachims, Transductive Inference for Text Classification using Support Vector Machines. International Conference on Machine Learning (ICML), 1999.
• [Vapnik 2000] Vladimir N. Vapnik, 14 in: Bounds on Error Expectation for SVM. in Advances in Large Margin Classifiers. pp. 261-
• [Herbrich 2000] Ralf Herbrich et al, 7 in: Large Margin Rank Boundaries for Ordinal Regression. in Advances in Large Margin Classifiers. pp. 116-

Related Links

• SVM_light Yet another Fast and useful SVM package
• libsvmYet another SVM package.
• Kernel Machine Website
• SVM Application List
• Support Vectors and Kernel Methods
• An introduction to Suppor Vector Machines

$Id: index.html,v 1.5 2000/12/09 06:19:15 taku-ku Exp $;