PCPSVM: A parallel cutting plane algorithm for training SVMs

The cutting plane algorithm provides fast training for classification SVMs, but it still suffers from the problem of memory restriction, because the algorithm requires to load all the data to the memory. To overcome this bottleneck, we propose and implement a Parallel Cutting Plane algorithm for training Support Vector Machines (PCPSVM) on distributed computers. The Algorithm uses a row-based storage method to reduce memory requirement and finally can parallelize both data loading and computation. Let l denote the number of training instances, d the dimension of each instance, m the number of machines. We divide the data to m parts, and loads only essential data to each machine to perform parallel computation. The memory requirement can be reduced from O(ld) to O(ld/m). We implement our PCPSVM algorithm in the MPICH platform. Experiments show that the algorithm is effective, memory requirement is reduced and great speed-up is achieved when many processors are used. PCPSVM Open Source is available at http://code.google.com/p/pcpsvm/.