Developing parallel sequential minimal optimization for fast training support vector machine

Abstract

A parallel version of sequential minimal optimization (SMO) is developed in this paper for fast training support vector machine (SVM). Up to now, SMO is one popular algorithm for training SVM, but it still requires a large amount of computation time for solving large size problems. The parallel SMO is developed based on message passing interface (MPI). Unlike the sequential SMO which handle all the training data points using one CPU processor, the parallel SMO first partitions the entire training data set into smaller subsets and then simultaneously runs multiple CPU processors to deal with each of the partitioned data sets. Experiments show that there is great speedup on the adult data set, the MNIST data set and IDEVAL data set when many processors are used. There are also satisfactory results on the Web data set. This work is very useful for the research where multiple CPU processors machine is available.

Introduction

Recently, a lot of research work has been done on support vector machines (SVMs), mainly due to their impressive generalization performance in solving various machine learning problems [1], [2], [15]. Given a set of data points {(X_i,y_i)}_i¹ (X_i∈R^d is the input vector of ith training data pattern; $y_i\in \{-1,1\}$ is its class label; l is the total number of training data patterns), training an SVM in classification is equivalent to solving the following linearly constrained convex quadratic programming (QP) problem.

$$\mathrm{maximize}:R({\alpha }_i)=\sum _{i=1}^l{\alpha }_i-\frac{1}{2}\sum _{i=1}^l\sum _{j=1}^l{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(X_i,X_j)$$

$$\mathrm{subject}\mathrm{to}:\sum _{i=1}^l{\alpha }_i{y}_i=0\text{,}$$

$$0⩽{\alpha }_i⩽C,i=1,\cdots ,l\text{,}$$

where K(X_i,X_j) is the kernel function. The mostly widely used kernel function is the Gaussian function $\mathrm{e}-||X_i-X_j|{|}^2/{\sigma }^2$, where σ² is the width of the Gaussian kernel. α_i is the Lagrange multiplier to be optimized. For each of training data patterns, one α_i is associated. C is the regularization constant pre-determined by users. After solving the QP problem (1), the following decision function is used to determine the class label for a new data pattern:

$$f(X)=\sum _{i=1}^l{\alpha }_i{y}_{i}K(X_i,X)-b\text{,}$$

where b is obtained from the solution of (1). A detailed description of Eq. (3) can be referred to our previous work [7].

So the main problem in SVM is reduced to solving the QP problem (1), where the number of variables α_i to be optimized is equal to the number of training data patterns l. For small size problems, standard QP techniques such as the projected conjugate gradient can be directly applied. But for large size problems, standard QP techniques are not useful as they require a large amount of computer memory to store the kernel matrix K as the number of elements of K is equal to the square of the number of training data patterns.

For making SVM more practical, special algorithms are developed, such as Vapnik's chunking [14], Osuna's decomposition [10] and Joachims's SVM^light [8]. They make the training of SVM possible by breaking the large QP problem (1) into a series of smaller QP problems and optimizing only a subset of training data patterns at each step. The subset of training data patterns optimized at each step is called the working set. Thus, these approaches are categorized as the working set methods.

Based on the idea of the working set methods, Platt [12] proposed the sequential minimal optimization (SMO) algorithm which selects the size of the working set as two and uses a simple analytical approach to solve the reduced smaller QP problems. There are some heuristics used for choosing two α_i to optimize at each step. As pointed out by Platt, SMO scales only quadratically in the number of training data patterns, while other algorithms scales cubically or more in the number of training data patterns. Later, Keerthi et al. [9] ascertained inefficiency associated with Platt's SMO and suggested two modified versions of SMO that are much more efficient than Platt's original SMO. The second modification is particular good and used in popular SVM packages such as LIBSVM [3]. We will refer to this modification as the modified SMO algorithm.

Recently, there are few works on developing parallel implementation of training SVMs [4], [6], [16]. In [4], a mixture of SVMs are trained in parallel using the subsets of a training data set. The results of each SVM are then combined by training another multi-layer perceptron. The experiment shows that the proposed parallel algorithm can provide much efficiency than using a single SVM. In the algorithm proposed by Dong et al. [6], multiple SVMs are also developed using subsets of a training data set. The support vectors in each SVM are then collected to train another new SVM. The experiment demonstrates much efficiency of the algorithm. Zanghirati and Zanni [16] also proposed a parallel implementation of SVM^light where the whole quadratic programming problem is split into smaller subproblems. The subproblems are then solved by a variable projection method. The results show that the approach is comparable on scalar machines with a widely used technique and can achieve good efficiency and scalability on a multiprocessor system.

This paper proposes a parallel implementation of the modified SMO based on the multiprocessor system for speeding up the training of SVM, especially with the aim of solving large size problems. In this paper, the parallel SMO is developed using message passing interface (MPI) [11]. Unlike the sequential SMO which handles the entire training data set using a single CPU processor, the parallel SMO first partitions the entire training data set into smaller subsets and then simultaneously runs multiple CPU processors to deal with each of the partitioned data sets. On the adult data set the parallell SMO using 32 CPU processors is more than 21 times faster than the sequential SMO. On the web data set,the parallel SMO using 30 CPU processors is more than 10 times faster than the sequential SMO. On the MNIST data set the parallel SMO using 30 CPU processors on the averaged time of “one-against-all” SVM classifiers is more than 21 times faster than the sequential SMO.

This paper is organized as follows. Section 2 gives an overview of the modified SMO. Section 3 describes the parallel SMO developed using MPI. Section 4 presents the experiment indicating the efficiency of the parallel SMO. A short conclusion then follows.