An Efficient Classifier Based on Hierarchical Mixing Linear Support Vector Machines

1 Introduction

Support vector machines (SVMs) have enjoyed excellent performance in many areas due to their great flexibility and good generalization performance. However, they still suffer from a high computational complexity in the classification phase if the number of SVs is large. We want the time for classification to be as short as possible, especially in real-time pattern recognition systems, whereas classification must be performed in a few millionseconds to satisfy the needs of online tasks. The methods for reducing the computational complexity of SVM classification can be divided into following two groups.

One group consists of algorithms to prune the SVs of SVMs. Representative papers include [Schoelkopf et al., 1999; Downs et al., 2001; Nguyen and Ho, 2006; Liang, 2010]. However, these methods need to obtain a standard SVM in advance, and this limits their applications to largescale problems. To address this issue, several methods for selecting a set of basis vectors are proposed. They include sampling from the training set in the Nystrom method [Williams and Seeger, 2001] and variants of the Incomplete Cholesky factorization [Bach and Jordan, 2005], core vector machine (CVM) [Tsang et al., 2005], relevance vector machine (RVM)[Tipping, 2001], and relevance units machine (RUM)[Gao and Zhang, 2009]. Wu et al. [Wu et al., 2006] add one constraint on the number of basis vectors to the standard SVM optimization problem, and then solve this modified nonconvex problem to build sparse kernel learning algorithms (SKLA). Joachims and Yu [Joachims and Yu, 2009] explore a new sparse kernel SVMs via cutting plane training, called cutting-plane subspace pursuit (CPSP).Although the above methods prunes the SVs and reduces computational complexity in classification phase, when a new test sample is introduced, they still need to compare it with these pruned SVs via kernel calculations to predict the label of the test sample. In addition, these methods also have to cache substantial kernel values of the important samples in the training process.

∗Corresponding author

The second group of techniques, exploring the divide-andconquer strategy, are to construct the ensemble models of linear decision functions in the original space, thus avoiding the kernel calculations of the SVs. Classical ensemble methods include bagging [Breiman, 1996], boosting [Pavlov et al., 2000] and random forests [Breiman, 2001]. But these methods tend to use a great amount of linear classifiers to correctly predict the sample label for linearly inseparable datasets, and thus are possibly to increase the computational complexity in classification stage. Bennett and Blue [Bennett and Blue, 1998] propose a primal and dual formulation for SVM approaches to decision trees with three decisions, and claim the method can be applied to trees of any size which needs to be determined beforehand. Fei and Liu [Fei and Liu, 2006] present a binary tree of SVMs for multiclass problems. Fornoni et al.[Fornoni et al., 2011] propose a multi class local classifier based on a latent SVM formulation. Ladicky and Torr [Ladicky and Torr, 2013] learn all the local models in a single optimization problem by using the inverse Euclidean distances as a form manifold learning. In the spirit of the mixture-of-expert framework, Fu et al.[Fu et al., 2010] propose a mixing linear SVMs (MLSVM) model which partitions the feature space into several linearly inseparable subregions based on a probabilistic model of the joint data and label distributions, and the testing samples are classified by the weighted average over the mixture of classifiers. Chen et al. [Cheng et al., 2010] divide the whole training set into several clusters via MagKmeans algorithm, and then train the LSVM classifier in each cluster. Li et al. [Li et al., 2011] propose a piecewise linear classifier named "multiconlitron", which is based on the "convexly separable" concept. Qi et al. [Qi et al., 2011] partition the whole training samples into several local regions by applying the locality-sensitive hashing (LSH) method, and construct the local classifier model in each region.

Motivated by the low classification and training cost of linear SVMs, we continue the fruitful line of the second group and aim to provide a model which generates nonlinear classification boundaries via the ensemble of locally linear SVM (LLSVM). To this end, we propose a novel classifier called HMLSVMs (Hierarchical Mixing Linear SVMs). Specifically, it has a hierarchical tree-like structure with a mixing linear SVM classifier at each node. The main advantages of the proposed classifier are as follows. Firstly, HMLSVMs does not require a large memory to store kernel values because HMLSVMs is composed of LSVMs, and there are very efficient algorithms for training LSVMs [Joachims, 2011; Hsieh et al., 2008]. Secondly, the hierarchical structure makes HMLSVMs predict the labels of new arrived samples via a few of LSVMs, and it is much faster than nonlinear SVMs. Thirdly, we quantify the generalization error bound for the class of LLSVMs based on the Rademacher complexity, and the stop criterion based on minimizing this bound ensures that HMLSVMs can effectively avoid overfitting and have a good classification performance. Hence, HMLSVMs has both the advantage of high speed in the classification stage, comparable to LSVMs, and the advantage of good classification performance comparable to KSVMs.

The remainder of the paper is organized as follows. In Section 2, we present the details of training and testing process of HMLSVMs. In Section 3, we quantify the generalization error bound for HMLSVMs based on the Rademacher complexity. Experimental results and related discussions are given in Section 4. Some conclusions are given in Section 5.

2 Description of the HMLSVMs

Before describing the proposed method, we first introduce the symbols used in the remaining parts of the paper.

• I: a row vector which represents a node in HMLSVMs. I = [0] represents the root node; [I, 1] and [I,-1] are respectively the left and right child nodes of I.
• f (t) : The weighted LSVM (W-LSVM) classifer trained in the t-th iteration of the training process of HMLSVMs.
• fI: the classifier associated to the node I.
• SI: subset of training samples in the node I.
• Ft: HMLSVMs in the t-th iteration.
• V (t) : the evaluations of all training samples in the t-th iteration, and its i-th element is V (t) i = Ft(xi).

2.1 Training Stage of HMLSVMs

Calculation of the weights

There are two major steps in the proposed strategy for calculating the training weights.

Step1: Training center selection Let the evaluation of sample xi be Vi in current iteration, then the "host" training center is defined as:

where Ej=min{1,max{0, 1 - yjVj}}, ˆ S={xi|yiVi < 1}, and Nε(xi) is the set of xi's ε- neighborhoods with the same label as xi. From the definition of xhc in Eq. (1), we can concluded that if a sample is selected as the "host" training center, it must meet two conditions: (1) the sample density of its ε-neighborhoods is high, (2) the samples in its εneighborhoods have large "training errors". Hence, the samples in local set Nε(xhc) are currently misclassified "most". To correctly classify these misclassified samples, we must retrain a LSVM with them. Accordingly, we define the opposite of the "host" training center, which is called as "guest" training center

where ¯Nε(xhc) is the set of xhc's ε- neighborhoods with different labels from xhc. Generally speaking, the "guest" training center is xhc's "nearest" sample with different labels from xhc, and the structural information defined in (2) avoids selecting isolated noisy samples.

Step2: Sample weights calculation The training weights of samples in sets Nε(xhc) and Nε(xgc) are calculated according to the sample similarities to the "host" and "guest" training center:

We assign the largest weights to the samples which are currently misclassified "most". This makes it more likely that the next classifier will correctly classify these samples.

Training Algorithm

The training scheme of HMLSVMs is summarized in Algorithm 1. In Step 7, we find the leaf node I which the "host" training center belongs to. This implies that the samples in set SI are misclassified "most" by current HMLSVMs. Ip is the parent node of I. Il is the last element of I, and Il = 1 (Il=- 1) indicates that the samples in SI are all classified as "positive" samples ("negative samples"). However, there may be some samples are misclassified by the current HMLSVMs. To separate these misclassified samples from SI, we should assign a classifier to the node I to further split SI. We define the classifier of node I by fI = min{f (t) , fIp } if Il = 1 (separate the negative samples from the "positive" samples),

Algorithm 1: Training of HMLSVMs

Input: The set of training samples S = {(xi, yi)}ni=1 .

• 1: Train the standard LSVM classifier f (1) with sample set S, and assign f (1) to the root node, i.e., f[0]=f (1) . Initialize t = 1.
• 2: Let F1 = {f[0]}, and ˜ S1 = {S[0,1], S[0,-1]}, where S[0,1]={x|f[0](x) ≥ 0, (x, y) ∈ S} and S[0,-1] = {x|f[0](x) < 0, (x, y) ∈ S}.
• 3: loop
• 4: Let t = t+1.
• 5: Find the "host" and "guest" training center via Eq. (1) and (2), and calculate the training weights of samples in the local sets Nε(xhc) and Nε(xgc) via Eq. (3) and (4).
• 6: Train the W-LSVM f (t) with the weighted samples in the sets Nε(xhc) and Nε(xgc).
• 7: Find the leaf node which the "host" training center xhc belongs to, and denote by I. Let Il = I(|I|) and Ip = I(1 : |I| - 1), where |I| is the number of elements of I.
• 8: if Il == -1 then
• 9: Let fI = max{f (t) , fIp }.
• 10: else
• 11: Let fI = min{f (t) , fIp }.
• 12: end if
• 13: Let Ft = Ft-1 ∪ {fI}, S[I,1] = {x|fI(x) ≥ 0, x ∈ SI }, S[I,-1] = {x|fI (x) < 0, x ∈ SI }, ˜ St = ( ˜ St-1 ∪ {S[I,1], S[I,-1]}) \ {SI }.
• 14: Update the evaluations of training samples V (t) by using current HMLSVMs.
• 15: end loop

Output: Ft, and ˜ St .

and by fI = max{f (t) , fIp } if Il = -1 (separate the positive samples from the "negative" samples), where f (t) is the W-LSVM classifier trained in the current iteration and fIp is the classifier associated to the parent node of I. This setting method ensures that the classifier associated to node I considers not only the current trained W-LSVM f (t) , but also the classifier associated to its parent node. Therefore, the classifier at each node is a mixture of maximums and minimums of LSVMs associated to its ancestor nodes. In Step 13, fI splits SI into subsets S[I,1] and S[I,-1] to enhance the impurity of current leaf nodes.

The outputs of the training process are Ft and ˜ St. Ft is the set of classifiers associated to the nodes of HMLSVMs. ˜ St includes all subsets in the leaf nodes, and it gives the classification results of training samples. For any SI ∈ ˜ St, if Il = 1, the samples in set SI are classified as positive samples. Otherwise, they are classified as negative samples.

Remark 1. The total number of classifiers at nodes of HMLSVMs is a key parameter which determines the generalization performance for HMLSVMs. We will give a proper stop criterion in Section 3.

2.2 Classification Stage of HMLSVMs

In classification stage, we make the new arrived sample go through from the root node to a terminal node of HMLSVMs. When the sample has arrived at a terminal node, if its H-MLSVMs classifier value is positive, then it is classified as positive sample, otherwise, it is classified as negative sample. Since only the terminal nodes have no classifier, then f[I,1] ∈ Ft (or f[I,-1] ∈ Ft) implies that the testing sample does not arrive at a terminal node of H-MLSVMs. We should continue classifying the sample using the classifier f[I,1] (or f[I,-1]). Otherwise, if f[I,1] /∈ Ft (f[I,-1] /∈ Ft), this implies that x has arrived at a terminal node, then we output the result fI (x).

2.3 Computational Complexity

Before giving the computational complexity, we first introduce the symbols used below. n is the number of samples, d is the dimension of samples, and ¯ p and ¯ q are the average number of elements of ˆ S and ε-neighborhoods Nε(·) in (1)respectively. We assume the total number of classifiers at nodes of HMLSVMs is L, and the average complexity of computing a value of an exponential function exp(·) is a constant. We use the dual coordinate descent (DCD) method [Hsieh et al., 2008] to train LSVMs because it is simple and reaches an ϵ-accurate solution with the computational complexity O(log(1/ϵ)n ¯ d) for n training samples, where ¯ d is the average number of nonzero elements per sample.

Complexity of training: In Step 1, computing the LSVMof the root node takes O(log(1/ϵ)n ¯ d) operations. In Step 2, the complexity of the evaluations of training samples is O(nd). In Step 5, selecting the ε-neighborhoods of the samples in set ˆ S takes O(¯ pnd) operations, and computing the "host" and "guest" center take O(¯ p¯ qd) and O(¯ q2d) operations respectively. Then the complexity of Step 5 is O((¯ pn + ¯ q2 )d) since ¯ q < n. Training the classifier with the samples of the local regions in Step 6 takes O(log(1/ϵ)¯ q ¯ d) operations. From Step 13-14, the complexity is at most O(nd) since we only need to update the evaluations of the training samples in node I. Hence, the complexity of Algorithm 1 is O(log(1/ϵ)n ¯ d + L(¯ pn + ¯ q2 )d). Generally speaking, ¯ p increases with n. Thus the complexity becomes expensive when n is very large. In our experiments, we use the probabilistic speedup method. The idea is to randomly sample a sufficiently large subset ˆ S′ from ˆ S, and select the sample training center xhc in set ˆ S′ instead of ˆ S. This makes the algorithm much faster as | ˆ S′ | ≪ | ˆ S|.

Complexity of classification: Since we classify a sample by making it go through from the root node to a leaf node of H-MLSVMs, and all classifiers associated to the nodes are composed of LSVMs, then only a few hyperplanes need to be evaluated in the classification step, no kernel computation is required. If the tree depth of HMLSVMs is ¯L, then the complexity for classifying a sample is at most O(¯Ld). This guarantees the high speed in the classification phase.

3 Generalization Error Bound for HMLSVMs

For classification problems, we are interested in bounding the difference between empirical and expected risk over some function class. Because HMLSVMs can be consider as an ensemble method of LLSVMs, we will quantify the generalization error bound for the class of LLSVMs based on the Rademacher complexity in this section.

The empirical Rademacher complexity of a class of function F defined on domain Z is

where the elements of T = {z1, · · · , zn} are generated by a distribution D on Z, and σ1, · · · , σn are independent Rademacher variables such that P(σi = 1) = P(σi = -1) = 0.5 for i = 1, · · · , n.

The following theorem states that the difference between the empirical and the true expected value of a function is upper bounded by the empirical Rademacher complexity of the function class.

Theorem 1. (Rademacher theorem) [Bousquet et al., 2004] Let F be a class of functions with domain Z, which map from Z to [0, 1], and {z1, · · · , zn} be generated independently according to a probability distribution D. Then for any fixed real value δ ∈ (0, 1), the following equation is satisfactory with probability at least 1 - δ for every f ∈ F

Assume a LLSVM f defined on the domain Z is composed of κ LSVMs, denoted by

Zt is the subregion to which the LSVM ft(x) = 〈wt, x〉+bt should be applied, such that Z = ∪κt=1Zt and Zi∩Zj = ∅ for i ̸= j. Let FB,κ,Zt be the function class of LLSVM defined by

where ˜wt = [w⊤ t bt]⊤. If we use the soft loss function

then the following theorem gives an generalization error bound for LLSVMs.

Theorem 2. Let FB,κ,Zt be a function class defined by (8), and suppose the training samples xt1, · · · , xtnt are in the subregion Zt for t = 1, · · · , κ. Then for any fixed real value δ ∈ (0, 1), the expected risk of LLSVM f ∈ FB,κ,Zt with probability at least 1 - δ can be bounded by

where L(f) is the expected risk based on the 0/1 loss, Lemp(f) is the empirical risk based on the soft loss (9), and ˜xti = [x⊤ti 1]⊤ for i = 1, · · · , nt and t = 1, · · · , κ.

Proof. Define the function class LB,κ,Zt as

Since |ℓs(f1(x), y) - ℓs(f2(x), y)| ≤ 1r |f1(x) - f2(x)| for ∀ f1, f2 ∈ FB,κ,Zt , i.e., ℓs satisfies Lipschitz condition with constant 1/r, then from Lemma 7 of [Meir and Zhang, 2003], we have

Let σti be the Rademacher variable corresponding to the sample xti, and let σt = [σt1, . . . , σtnt ], then the empirical Rademacher complexity of FB,κ,Zt satisfies

The disappearance of the mixed terms σtiσtj ˜x⊤ti ˜xtj for i ̸= j in Eq. (12) follows from the fact that the four possible combinations of -1 and 1 have equal probability with two of the four having the opposite signs and hence cancelling out. On the other hand,

Theorem 2 gives us an upper bound on the generalization error in terms of the empirical risk and the complexity of the function class FB,κ,Zt , where we measure the complexity of FB,κ,Zt by the minimal "margin" of all LSVMs (2/‖˜wt‖ is the margin of the t-th LSVM in the extended feature space ˜ X = {˜x|˜x = [x⊤1]⊤}) and the partition of the training space. Note that if a LLSVMs partitions the training sample set into a small number of parts (i.e.,κ is small), then the second term in the right hand of Eq. (10) (the complexity of FB,κ,Zt ) is likely small, however, the empirical risk are likely large especially for datasets which are far from being linearly separable. Hence, there is a need to trade off the empirical error with the class complexity. To this end, we use the minimization of

as the stop criterion, where λ is a tunable parameter and the second term in Eq. (13) can be seen as a regularization for the complexity of FB,κ,Zt . In the algorithm of HMLSVMs, we train a series of LSVMs with the total number of classifiers at nodes of HMLSVMs in the increasing order, and the repetition is not stopped until the minimization of the value in (13) is achieved. The regularization term ensures that overfitting can be effectively avoided.

4 Experiments

In this section, HMLSVMs is compared with the ensemble methods of combining linear classifiers, (1) adaboost with decision stump as weak learners (Ada-Stump), (2) adaboost with linear regression as weak learners (Ada-Percep), (3) adaBoost with linear regression as weak learners (Ada-LR), (4) mixing linear SVMs (MLSVM) [Fu et al., 2010], as well as the kernel methods (with RBF kernel k(xi, xj) = e-γ‖xi-xj‖2 ), (5) LIBSVM [Fan et al., 2005], (6) CVM [Tsang et al., 2005], (7) Nystrom method [Williams and Seeger, 2001], and decision tree method (8) CART [Breiman et al., 2004]. The parameters are obtained by using 5-fold cross validation. For Nystrom method, the basis vectors size is set to 200 (except for CBCL Face and EMG database, which is set to 500). For adaboost methods, we fix the number of boosting iterations to 1000 and 200 for synthetic and realworld datasets (except for EMG database, which is set to 1000) respectively, and select the classifier number which has the highest classification accuracy for testing samples. A list of the datasets and the optimal parameters is given in Table 1. We decompose each dataset into two parts: training samples and testing samples, which are independent from each other. 20 independent sets of training and testing samples are generated by running 20 random divisions on data samples in each set with a fixed proportion 8 : 2.

Two synthetic datasets, Spiral and Fourclass datasets, are used to test the above algorithms. These two datasets are often considered to be highly nonlinear datasets. In Fig. 1, from left to right, we show the decision boundaries produced by Ada-LR, CART, MLSVM, LIBSVM, and HMLSVMs respectively. The decision boundaries of HMLSVMs are smoother than that of the ensemble methods and nearly approach that of the kernel methods. The mean number of support vectors used by LIBSVM, CVM and Nystrom, and the mean number of linear classifiers employed by Ada-Stump, Ada-Perceptron, Ada-LR and MLSVM, and the mean number of linear classifiers for CART and HMLSVMs encountered per testing sample are shown in Table 3 1 . Although the number of linear classifiers employed by HMLSVMs for the two synthetic datasets in our experiments are respectively 66 and 25, the mean number of linear classifiers encountered per testing sample are respectively 8.3 and 4.5. This is due to the hierarchical structure of HMLSVMs, which predicts the label of a testing sample by making the sample go through from the root node to a leaf node of HMLSVMs. From the average numbers of SVs or linear classifiers in Table 3, it can be seen that HMLSVMs is orders of magnitude faster than the kernel and ensemble methods. CART achieves the classification cost comparable to that of HMLSVMs, but its testing accuracy is very poor, even lower than that of LSVM on some datasets.

1 The codes of LIBSVM, CVM and Nystrom are implemented in C++ and the codes of Ada-Stump, Ada-Perceptron, Ada-LR, MLSVM, CART and HMLSVMs are implemented in MATLAB, hence we prefer the number of SVs or linear classifiers to the classification time in fairness. Note that the complexity of MLSVM scales with twice the number of linear classifiers, including gate function and classifier evaluations

To further demonstrate the power of HMLSVMs, we also conducted experiments on 12 real-world datasets obtained from sources [Frank and Asuncion, 2010; Chang and Lin, 2001]. From Table 2, it can be seen clearly that CVM and LIBSVM outperform all other methods, however, they are at the cost of generating the largest number of SVs (as shown in Table 3), and this makes them have the highest computational complexity in classification stage. The methods of Nystrom and MLSVM report considerable reductions of the number of SVs or LSVMs, but the numbers are still much higher than that of HMLSVMs. HMLSVMs achieves good classification performance comparable to KSVMs (CVM, LIBSVM, Nystrom). More importantly, it classifies a testing sample only via several (at most 10.4) LSVMs, so the time cost of HMLSVMs in the classification stage is significantly reduced. This is the main focus of HMLSVMs, which is not having the best testing accuracy but provide a method capable of classifying a pattern in a few milliseconds while obtaining a competitive performance. Thanks to the regularization term in (13), this ensures that the HMLSVMs do not fall into overfitting and have the good generalization ability comparable to KSVMs. The hierarchical structure of HMLSVMs makes it achieve the high efficiency in the classification stage.

5 Conclusions

In this paper, we proposed a novel classifier called HMLSVMs by using a greedy strategy, which has a hierarchical structure with a mixture of LSVMs at each node. The hierarchical structure of HMLSVMs and the regularization term in (13) make it have the high speed in the classification stage and the good classification performance comparable to KSVMs. Experiments on both synthetic and real datasets are presented to show the effectiveness of our method. In the future, we will focus on the online learning of HMLSVMs.

Acknowledgement

This work is partly supported by NSFC under Grants 61472285, 6141101224, 61473212, 61100147, 61203241 and 61305035, and partly by the NSF of Zhejiang Province under Grants LY12F03016, LY15F030011 and LQ13F030009, and partly by Project of Science and Technology Plans of Zhejiang Province under Grants 2014C31062.