Fast SVM Trained by Divide-and-Conquer Anchors

1 Introduction

Supporting vector machine (SVM) [Cortes and Vapnik, 1995] can be considered as the most popular classifier in machine learning tasks. Due to its importance, optimization methods for SVM have been widely studied [Li et al., 2015; Tsang et al., 2005; Liu and Tao, 2016; Gu et al., 2015; Li and Guo, 2013; Xu et al., 2015; Luo et al., 2016], and efficient libraries such as LIBSVM [Chang and Lin, 2011] and SVM light [Joachims, 1999] are well developed. However, its application on real-world datasets is limited due to the training time which will increase tremendously as the size of training set becomes large. For example, training time complexity for SVMs with non-linear kernels is typically quadratic in the size of the training dataset [Shalev-Shwartz and Srebro, 2008].

A great number of works have been made to accelerate the training procedure in this literature [Fan et al., 2008; Hsieh et al., 2014; Shalev-Shwartz et al., 2011]. The SVM primal problem is a convex optimization problem with strong duality, thus its solution can be arrived at by solving its dual formulation [Boyd and Vandenberghe, 2004].

Training set selection methods attempt to reduce the SVM training time by optimizing over a selected subset of the training set. Several distinct approaches have been used to select the subset. A core set is defined as the subset of X and its solution of an optimization problem has a solution similar to that for the entire data set [Clarkson, 2010]. In [Tsang et al., 2005], core vector machine (CVM) is proposed which can approximately solve the L2-SVM formulation using core sets, and proved that L2-SVM is a reformulation of the minimum enclosing ball problem for some kernels. Ball vector machine (BVM) further improves CVM by focusing on the enclosing ball [Tsang et al., 2007].

Another type of approximate SVM algorithms is based on the geometric property of data distributions. [Bennett and Bredensteiner, 2000] developed an intuitive geometric interpretation of the standard support vector machine classification of both linearly separable and inseparable data, and proved that finding the maximum margin between the two sets is equivalent to finding the closest points in the smallest convex hulls that contain each class for the separable case. However, Early work [Chazelle, 1993] proved that the calculation complexity of obtaining an exact convex hull is unacceptable in real applications. [Zhou et al., 2013] developed a divide-and-conquer algorithm to obtain the approximate convex hull.

Inspired by recent developments on obtaining representative points, we propose a fast SVM algorithm based on the anchors of approximate convex hull obtained by NMF, and prove that our algorithm can yield an approximate solution close to the primal SVM. We conduct the experiments both on synthetic and multiple real datasets. The results show that our DCA-SVM outperforms the state-of-the-art algorithms, and validate the efficiency and significance of our method.

2 RelatedWork and Preliminaries

Given a binary-class dataset X with n vectors xi ∈ Rm, its corresponding labels Y = {yi : y ∈ {-1, 1}, i = 1, · · · , n}. The primal SVM can be represented as follows:

where ℓ(w, b, φ(xi)) is the hinge loss of xi. The penalty parameter C is divided by n, which has been frequently used. The optimization of the objective function (1) requires n samples. The training time of traditional SVM can be decreased by reducing the size of the training set.

Among a large number of works focusing on obtaining representative subsets, obtaining the geometry convex hull of X is one of the most popular methods. First, let's make a brief revisit on the geometric properties of a set of data. Given a set of points R = {ri}ki=1 , its cone cone(R) is defined as the conical combinations of k points.

Similarly, a simplex is a non-empty convex set that is closed with respect to convex combinations of its elements. Given a set of points V = {vi}ki=1 , a simplex ∆(V ) can be defined as follows:

For a given dataset X, let ∆(X) denote its convex hull and XA be anchors (vertices) of the convex hull ∆(X). Therefore, all points of X can be represented by following convex combination:

where 0 ≤ hi,t ≤ 1, ∑xt∈∆(X) hi,t = 1 and hi,t indicates the convex combination coefficient of anchor xt for point xi. Figure 1 shows examples of conical hull and convex hull.

Although the anchors on the convex hull can fully represent the property of all points, the computational complexity of exact convex hull for high-dimensional datasets can be extremely cumbersome. It was proved in [Chazelle, 1993] that the calculation complexity of obtaining an exact convex hull of n vectors of m features is O(n⌈m/2⌉ +n log n). One example shown in Figure 2 indicates one extreme situation where all points are in the convex hull. Therefore, the approximate yet representative subset of points is needed.

2.1 Approximate Convex Hull of NMF

Non-negative matrix factorization (NMF) decomposes a matrix X ∈ Rn×m + which contains n non-negative mdimensional vectors {xi}ni=1 into the form of X = HW, where H ∈ Rn×k + , W ∈ Rk×m + and k ≪ min{n,m}. The rows of W are composed of k non-negative basis vectors representing all the samples, while the n rows of H are nonnegative weight vectors [Zheng et al., 2015].

Many additional assumptions are further imposed on the H and W to transform the original NP-hard NMF problem into tractable [Vavasis, 2009]. For example, an early work in [Donoho and Stodden, 2003] gives a separability assumption and prove that a uniqueness of NMF solution can be achieved under this additional assumption. Therefore, the geometric concepts of cone, conical hull, simplex and convex hull can be defined both geometrically and algebraically under the separability assumption. We can also know that a separable matrix is one that admits a non-negative factorization where X = HX(:,K), i.e., W just consists of a subset of the columns of X. The index set K of columns are called extreme columns. Namely, in separable NMF, X = HX(:,K) implies that all columns of X lie in the cone generated by the columns indexed by K. For any k ∈ K, {αX(:, k)|α ∈ R+} is an extreme ray of this cone. Computing K is reduced to finding the extreme rays of a cone.

Besides, a near-separable matrix is one where X = HX(: ,K) + N, where N is the noise matrix. Determining K is reduced to finding the extreme points of a convex hull.

Separability assumption selects a few data points to represent the other data points in the whole dataset. This constraint is more than merely an artificial trick: it is favored and justified by various practical applications. For example, in big data challenges, it is more natural, interpretable and efficient to represent high-dimensional data by a few actual data points selected from a huge dataset rather than artificial basis vectors. The separability assumption allows the anchors such data expresses itself assumption has become a popular trend in the recent study of other related matrix factorization [Zhou et al., 2013].

Although traditional methods such as linear programming (LP) and greedy pursuit methods can pick out the anchors from noisy data and results in a near-separable NMF, their efficiency could be seriously weakened in high dimensions. Recent work [Zhou et al., 2013] presents a quite efficient divide-and-conquer anchoring (DCA) framework to address near-separable NMF problem by solving several independent sub-problems in low-dimensional spaces, and then obtain an approximate convex hull from the large-scale data in high-dimensional space. Specifically, DCA is a divideand-conquer framework [Liu et al., 2011] for near-separable NMF and with two steps: the divide step equals applying near-separable NMF to data random projections in multiple subspaces, whilst the conquer step is a fast hypothesis testing based on statistics of the low-dimensional anchors achieved in the divide step.

In each sub-problem of the divide step, DCA projects all the row vectors in X to a randomly generated d-dimensional hyperplane P = P(B), where B denotes a subspace B = [η1; · · · ; ηd] ∈ Rd×m spanned by d random vectors {ηi}di=1 uniformly sampled from the unit hypershere Sm-1 in Rm. The projections of X on P is Y = XBT . Since the geometry of conical hull cone(XA) is partially preserved in Y , the output of separable NMF in i-th subproblem is the lowdimensional anchors's indexes can be represented as follows:

The conquer step of DCA is composed of a hypothesis testing that accepts or rejects each data point associated with a detected low-dimensional anchor (from the s subproblems) as an anchor. Since the anchors are usually detected in sub-problems with higher probability than non-anchors, the hypothesis testing can then be reduced to picking out the k data points whose random projections are most frequently selected as anchors in all the sub-problems. The anchor number k can be predetermined or determined automatically. Let I(i ∈ ¯ Aj ) : i → {0, 1} be an indicator function for the event that data index i is within the ¯ Aj of the jth sub-problem. For predetermined k, DCA selects the top k largest ∑sj=1 I(i ∈ ¯ Aj ). In some applications, the rank k is unknown and needs to be determined automatically. When the noise is not overwhelming, a large gap can be observed between anchor and non-anchor on their statistics ∑sj=1 I(i ∈ ¯ Aj ).

Hence, a tolerance µ can be pre-defined to detect such gap in the sorted ∑sj=1 I(i ∈ ¯ Aj ) of all data points and automatically identify k. Let p be the new index set after sorting ∑sj=1 I(i ∈ ¯ Aj ) of all i ∈ [n] in descending order. By defining g(pl) ∑sj=1 I(pl ∈ ¯ Aj ), anchor set A can be estimated without knowing k by

DCA can be further accelerated by projecting vectors onto extremely low-dimensional space, such as 1D or 2D space. By this means, DCA gets a promising approximate convex hull. Based on this development, we propose to use the approximate convex hull to be further applied in the SVM training to reduce the training time.

3 Fast SVMTrained on Anchors

In this section, we will introduce the proposed fast SVM trained on anchors, named DCA-SVM. We use the anchors of approximate convex hulls obtained by the divide-and-conquer NMF framework to train the approximate SVM. Figure 3 shows the illustration of our method. The objective function of our method can be written as follows:

where βt = ∑ni=1 hi,t is the sum of weights for vector xi, and Cn is the same penalty parameters in problem (1).

3.1 Getting Anchors

To obtain the anchors of the approximate convex hull, it is required to first rearrange X according to their labels as X = {X+,X-}. The divide-and-conquer methods [Xu et al., 2016] which pursue the anchor points are conducted on X+ and X- separately. For simplicity, we use the form of the explicit representation of transformed data vectors in the kernel space:

3.2 Defining Convex Combination Coefficients

After getting the anchors XA of the original dataset X, we need to determine the coefficients of the anchors corresponding to other points by following equations,

Where H is the coefficient matrix. Since most of the points are inner points, their convex combination coefficients can be quickly obtained. More specifically, for each point xi, it required to be determined whether it can be fully represented by the anchors,

where ‖φ(xi) - ∑xt∈XA hi,tφ(xt)‖2 = K(xt, xt) + ∑t=1 ∑r=1 hi,thi,rK(xt, xs)-2 ∑t=1 K(xi, xt). In order to solve this quadratic optimization problem, we set a threshold ξ > 0, if f(xi,XA) ≤ ξ, xi is considered as an inner point of the convex hull XA, otherwise, xi will be considered as an outer point of the convex hull. In this way, the weight coefficients for each xi can be calculated separately, which can be accelerated by coordinate descent algorithms.

Algorithm 1 Approximate SVM trained on divide-andconquer anchors, where the anchor number k is determined automatically.

Input: training data X, sub-problem number s, random vector number d.

Output: Parameters of DCA-SVM for classification Split training set into X+ and X- according to their labels;

(1) Divide and Conquer Step:

generate random projection matrix B;

obtain anchors Ai of X(Bi )T by SNMF in Eq. (5).

end for

combing anchors to get X+ A and XA by Eq. (6);

(2) Coefficients Learning Step:

Determining the weight matrices F ± and noise matrices N ± of X± = FX± A +N ± .

(3) Training procedure:

train SVM using anchors X+ A and XA according to Eq. (7).

After getting the coefficient parameters, all points can be presented as follows:

where τi is a vector indicates the representation error between f (xi, XA),

After getting the coefficients hi,t(1 ≤ t ≤ k) for point xi, for an anchor xt(1 ≤ t ≤ k), we then obtain its compound coefficient βt = ∑ni=1 hi,t, which will be used in the objective function of DCA-SVM in Eq. (7). Further, the proposed DCA-SVM can be solved by standard SVM solver such SMO algorithm.

3.3 Computational Complexity

The computation complexity of Algorithm 1 mainly consists of two parts: finding out the anchors for two classes and training SVM on the representative subsets. In the practical calculation, the complexity of getting anchor by DCA-1D or DCA-2D is O(nk log k); For the proposed approximate SVM algorithm, its input number of vectors is reduced from n to ρk, where ρ is a constant value. The computational complexity of our approximate SVM algorithm is equal to the primal SVM with same number of reduced training samples.

Let (w∗ 1 , b∗1 ) and (w∗ 2 , b∗2 ) be the optimal solution of J1(w, b) and J2(w, b), respectively. The following theorem proved that our SVM can yield an approximate solution close to the primal SVM by thresholding the value of noise.

Theorem 1. Let J1(w, b) and J2(w, b) be the objective functions of primal SVM and DCA-SVM, Then,

where τi is the noise for vector xi. Due to limited space, the proof of Theorem 1 is not presented here. In a nutshell, the proof process is straightforward by taking the weighting coefficients of anchors into Eq. (7).

4 Experiments

In this section, we will present the experimental results on synthetic datasets and popular real datasets. We perform all compared algorithms on three real-world datasets: KDD99Lite, UCI Forest 1 and IJCNN1 2 . KDD99Lite is a simplified version of KDD99 3 by removing the repeated data vectors as described in [Tavallaee et al., 2009]. KDD99Lite consists of a training set with 1,074,974 vectors and a test set with 77,216 vectors of 41 features. UCI Forest dataset has 581,012 vectors with 54 features, and it is used to classify the areas of forest cover into one of seven types. We follow the settings of [Tavallaee et al., 2009] to obtain as a classification the 2nd forest cover type and the other types. For IJCNN1, its training set and testing set have 49,990 and 91,701 vectors, respectively. All vectors of IJCNN1 have 22 features. Table 1 summarizes the information of three datasets.

For the sake of accuracy of the experiment, we partitioned the data randomly for five-fold cross-validation. The parameter C varies in the range {2-6 , 2-5 , . . . , 25 , 26 }.

Our proposed DCA-SVM will be compared with AESVM, CVM, BVM, SVM perf and LIBSVM. These algorithms can be summarized as follows:

• AESVM: reduces the excessive training time by selecting the approximate extreme points according to Euclidean distance between each point within a divide-andconquer framework. We set the parameter ϵ = 10-2 when using AESVM [Nandan et al., 2014].
• CVM: core vector machine, approximately solves the L2-SVM formulation using core sets, which is a subset of the original entire dataset [Clarkson, 2010].
• BVM: ball vector machine, a simplified version of CVM, only utilizes the points lying on the enclosing ball [Tsang et al., 2007].
• SVM perf : an implementation of the SVM formulation for optimizing multivariate performance measures [Joachims, 2005]. We set the given number of support vectors as 1000 in our experiments.
• LIBSVM: a widely used implementation of SVM based SMO algorithm [Chang and Lin, 2011].

In addition to classification accuracy, we use other measures to evaluate the performances of these methods, which are expected training time speedup Tte, overall training time speedup Tto, expected classification time speedup Tce and classification time speedup for optimal hyper-parameters Tco as described in [Nandan et al., 2014]. Denoting F as any concrete SVM algorithm such as DCA-SVM, AESVM and CVM. Four time-related measures are represented as follows.

1 https://archive.ics.uci.edu/ml/datasets/Covertype

2 http://www.csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/datasets/ binary.html\#ijcnn1

3 http://archive.ics.uci.edu/ml/datasets/KDD+Cup+1999+Data

Expected training time speedup Tte stands for the expected speedup time in training procedure:

where TLrs and TF rs stand for the training times of LIBSVM and given algorithm F in the sth cross-validation fold with the rth set of hyper-parameters of grid search.

Overall training time speedup Tto represents the overall training time including the time spent on calculating the representative subset such as in DCA-SVM and AESVM.

where TX∗ notes the time used to obtain the subset.

Expected classification time speedup Tce is indicated as follows:

where NLrs and NF rs represent the numbers of support vectors in the solution of LIBSVM and F, respectively.

Classification time speedup for optimal hyper-parameters Tco chooses the corresponding optimal classification accuracy results of LIBSVM and given F in grid search:

4.1 Experimental Study on Synthetic Data

For illustrative purpose, we conduct our first on the synthetic dataset. Two sets of vectors X+ and X- are generated according to X± = FX± A + N ±. The noise matrices N + and N - both are generated by i.i.d Gaussian distribution N(0, σ2 ) where σ represents the noise level. The number of anchors for each class is fixed as 20. After setting noises of different levels, we get two sets of points. The number of points for each set is 1000 and the feature number is 10000. As elaborated in Figure 4, different noise levels will bring different changes to the anchors of convex hull.

Figure 5 shows the results of the proposed DCA-SVM compared with three popular approximate SVM algorithms: AESVM, CVM and BVM. Their results are evaluated in terms of three measures: anchor index recovery rate representing the ratio of the observed number of original anchors to the total number, overall training time consisting of the time of determining representative subsets, and overall training time. It can be observed that most algorithms are able to find out the original anchors when the noise level is close to 1 where the original convex hull remains its shape. Moreover, the numbers of points in the representative subsets obtained by four algorithms have large difference. DCA-SVM aims to find the approximate convex hull, thus its point numbers are less than the other three algorithms. It is worth noting that DCA-SVM uses the least training time. Their property on classification accuracy will be further studied on real datasets in the rest of this section.

4.2 Comparision on Real Datasets

We evaluate the classification performance of DCA-SVM, AESVM, CVM, BVM and LIBSVM. We follow the same experimental settings in [Nandan et al., 2014]. There are two notable kinds of parameters, classification accuracy and training time. The classification accuracy is defined as the ratio of the number of correct classifications to the total number of samples involved in training procedure, while the training time consists of four time measures mentioned above.

Table 2 shows the classification results of DCA-SVM, AESVM, CVM, BVM, SVM perf and LIBSVM on KDD99Lite, UCI Forest and IJCNN1. These results are evaluated in terms of four time measures and three accuracy-related measures. We can observe that: (1) Most approximate SVM algorithms achieve faster overall training time Tto than LIBSVM on KDD99Lite and UCI Forest datasets, while these approximate SVM algorithms run much slower on IJCNN1 except DCA-SVM and AESVM. This is because the sizes of training sets of KDD99Lite and UCI Forest are much larger than IJCNN1, which makes the training time on the whole original training sets become tremendous. (2) The proposed DCA-SVM outperforms other algorithms notably on expected training time speedup Tte and overall training time speedup Tto. Specifically, the Tte of DCA-SVM is 1712.2 times faster than LIBSVM on KDD99Lite dataset and nearly twice as fast as the competitive AESVM on IJCNN1 dataset. (3) All algorithms produce similar accuracy performances on three datasets. The proposed DCA-SVM achieves decent accuracy which is only 0.2% less than the largest accuracy on KDD99Lite dataset. In short, our method outperforms most of the compared methods on speed and produce fairly good classification accuracy results.

5 Conclusions

In this paper, we propose to train an approximate SVM by using the anchors obtained from non-negative matrix factorization (NMF) in a divide-and-conquer framework. To be specific, the weighting coefficients of the anchors corresponding to other points are used in the training procedure of the approximate SVM. Our theoretical analysis shows that the solving the DCA-SVM can yield an approximate solution close to the primal SVM. Experimental results on the synthetic datasets and multiple real-world datasets show that the proposed DCA-SVM is faster than other state-of-the-art algorithms, and does not lead to a notable decrease in the accuracy of classification results, which validate the efficiency and significance of our method.

Acknowledgements

This research is partially supported by grants from NSFC 61375026 and 2015BAF15B00, and Australian Research Council Projects FT-130101457, DP-140102164, LP150100671.