TR announcement: A fast algorithm for SVM classifier design

[Chiranjib Bhattacharya]

We have recently developed a fast and simple algorithm for Support Vector 
Machine classifier design using geometric ideas involving convex polytopes.
Details are given in the Technical Report mentioned below. For soft copies 
please email:
    ssk at csa.iisc.ernet.in

Comments are welcome.

A Fortran code implementation will be made available on request.

----------------------------------------------------------------------------

           A Fast Iterative Nearest Point Algorithm for
             Support Vector Machine Classifier Design

 
     S.S. Keerthi, S.K. Shevade,  C. Bhattacharya and  K.R.K. Murthy

                       Intelligent Systems Lab 
              Dept. of Computer Science and Automation 
                      Indian Institute of Science 
                          Bangalore - 560 012 
                                 India 


                  Technical Report TR-ISL-99-03



                            Abstract

In this paper we give a new, fast iterative algorithm for support
vector machine (SVM) classifier design. The basic problem treated is
one that does not allow classification violations. The problem is
converted to a problem of computing the nearest point between two
convex polytopes. The suitability of two classical nearest point
algorithms, due to Gilbert, and Mitchell, Dem'yanov and Malozemov,
is studied. Ideas from both these algorithms are combined and modified
to derive our fast algorithm. For problems which require classification
violations to be allowed, the violations are quadratically penalized
and an idea due to Friess is used to convert it to a problem in which
there are no classification violations. Comparitive computational
evaluation of our algorithm against powerful SVM methods such as
Platt's Sequential Minimal Optimization shows that our algorithm is
very competitive.