--- title: "Multi-Class Support Vector Machine via Maximizing Multi-Class Margins" authors: - "Jie Xu" - "Xianglong Liu" - "Zhouyuan Huo" - "Cheng Deng" - "Feiping Nie" - "Heng Huang" doi: "10.24963/ijcai.2017/440" url: "https://ijcai.org/proceedings/2017/440" pdf: "https://ijcai.org/proceedings/2017/0440.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "3154-3160" track: "Main track" keywords: - "Machine Learning: Classification" - "Machine Learning: Semi-Supervised Learning" --- # Multi-Class Support Vector Machine via Maximizing Multi-Class Margins Jie Xu, Xianglong Liu, Zhouyuan Huo, Cheng Deng, Feiping Nie, Heng Huang *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 3154-3160. DOI: [10.24963/ijcai.2017/440](https://doi.org/10.24963/ijcai.2017/440) ## Abstract Support Vector Machine (SVM) is originally proposed as a binary classification model, and it has already achieved great success in different applications. In reality, it is more often to solve a problem which has more than two classes. So, it is natural to extend SVM to a multi-class classifier. There have been many works proposed to construct a multi-class classifier based on binary SVM, such as one versus all strategy, one versus one strategy and Weston's multi-class SVM. One versus all strategy and one versus one strategy split the multi-class problem to multiple binary classification subproblems, and we need to train multiple binary classifiers. Weston's multi-class SVM is formed by ensuring risk constraints and imposing a specific regularization, like Frobenius norm. It is not derived by maximizing the margin between hyperplane and training data which is the motivation in SVM. In this paper, we propose a multi-class SVM model from the perspective of maximizing margin between training points and hyperplane, and analyze the relation between our model and other related methods. In the experiment, it shows that our model can get better or compared results when comparing with other related methods. ## Full text ## 1 Introduction Support Vector Machine (SVM) is originally proposed as a binary classifier [Cortes and Vapnik, 1995] which has achieved great success in many different applications, such as handwritten digit recognition [Lauer et al., 2007; Maji and Malik, 2009], speaker identification [Kamruzzaman et al., 2010; Campbell et al., 2006], event recognition [Chang et al., 2016a; 2016b], feature selection [Cai et al., 2011], action recognition [Yang et al., 2017], and text categorization [Pil´aszy, 2005; Joachims, 1999; Nie et al., 2014]. To apply SVM model to practical multi-class classification problems, many researchers tend to extend SVM to be a multi-classification classifier. Existing multi-class SVM models can be mainly divided into two types [Hsu and Lin, 2002]. The first type is splitting the multi-class classification problem into multiple binary classification subproblems, like OvsR multi-class SVM Figure 1: We train a multi-class Support Vector Machine model by maximize the margin between every two classes pair. In this three classes case, we need three parameters w1,w2,w3, and use w1 and w2 to form a maximum-margin hyperplane for class 1 and 2. ![Image](https://ijcai.org/proceedings/2017/fulltext/440/image_000000_822430a990471eaf594f0c1d913e1355b28cd300bf73901ab35fb2db0325d97b.png) and OvsO multi-class SVM. OvsR splits a c class classification problem to c binary classification subproblems, and OvsO strategy splits it to c(c-1) 2 binary classification subproblems. The second type is to solve multi-class classification problem in a single optimization model, like Weston's multiclass SVM [Weston and Watkins, 1998], Crammer multiclass SVM [Crammer and Singer, 2002], and regression-like formulation [Nie et al., 2017]. However, none of them follow the motivation in SVM which is maximizing the margin between training points and hyperplane. In this paper, we will propose a novel multi-class Support Vector Machine model. Figure 1 presents the motivation of our model. It is derived by maximizing the margin between each two classes pair and the relationships between this model and other related multi-class SVM methods are also analyzed in this paper. We also extend our model to solve semisupervised problems. Stochastic gradient descent with variance reduction algorithm (SVRG) is used to optimize this model, and it is proved to have faster convergence rate and reach better local optimum. Experiments on benchmark datasets show that our model can get equal or better results than other related methods. ## 2 Multi-Class Support Vector Machine Although SVMmodel is a binary classifier, researchers works to extend it to solve multi-class classification problems. The earliest attempt is one versus all (one versus rest) strategy. Suppose there are n training data in the form of (xi, yi), and c classes in total, we need to build c binary SVM models. When we train jth SVM model, we define class j as positive and the rest classes as negative. If the number of training data in each class is balanced, this subproblem is an unbalanced binary classification problem, and can be represented as, A new sample xi is belonged to the class j which has the largest decision function value, As we mentioned, the main defect of this strategy is that each binary classification is unbalanced. This property may affect the performance of one versus rest strategy on multi-class classification problem. One versus one strategy solves this problem by training more binary SVMmodels. In this strategy, we will train one binary SVM model for each two classes, so there are c(c-1) 2 models in total. For class j and k, the maximum-margin hyperplane between them is wjkxi + bjk = 0, and it can be learned through the problem as follows, Voting strategy is used in testing, if sign(wjkxi + bjk) says xi is in class j, then the vote for class j is added by one, otherwise vote for class k is added by one. Final prediction class is the class which has the largest vote. Instead of handing multi-class classification by solving multiple subproblems, Weston proposed to use one single objective function [Weston and Watkins, 1998], Predicting class for a new sample is same as one versus rest method, and it is classified to be the class which has the largest value of decision function. Moreover, Crammer et al. proposed a new model as follows [Crammer and Singer, 2002], Different from problem (4), it just considers one slack variable ξi for each sample xi. Guermeur developed a theoretical framework for multi-class SVMs [Guermeur, 2002] and proposed a model, In that paper, Guermeur also pointed out that its formulation is equal to the model proposed in [Bredensteiner and Bennett, 1999], ## 3 MaximizingMulti-Class Margins for SVM The forthright methods to solve multi-class problems are one versus rest and one versus one strategy. However, one versus rest strategy has a drawback that the training data of each subproblem is unbalanced, which will affect the performance of each binary classifier. While for one versus one strategy, space and time consumption are two big problems, since we have to train c(c-1) 2 binary SVMmodel for c classes. To address this issue, we propose a novel multi-class SVM model. In our model, we build a classifier for every two classes, however, different from one versus one strategy which stores c(c-1) 2 models wjk, we propose to use c vectors to simulate all these binary classifiers, for example a classifier between class j and k, wjk = wj -wk. In this way, our space consumption equals to the space consumption of one versus rest strategy, and avoid unbalanced training data subproblem at the same time. In the following section, we also prove that we just need to compute c decision functions in testing, and do not need to use vote strategy like one versus one strategy. To solve the binary classification subproblem between class j and k, and maximize the margin between their data, soft margin objective function for this problem is, where xi ∈ Rd , non-negative slack variable ξ jk i is introduced to handle the data that are not linearly separable. ∑yi∈{j,k} ξ jk i is the penalty term, and is able to reduce the number of training errors. Parameter C is a balance between training error and regularization term ‖wj -wk‖22 . fjk(xi) = (wj -wk)T xi +(bj -bk) is the decision function, and yjk i = { 1 if yi = j -1 if yi = k . There are c(c-1) 2 binary classifiers in total, and all of them are essentially correlated. Then we build a multi-class SVM model as follows, There should be only one optimal solution. As we can see, if W ∈ Rd×c and b ∈ Rd is the optimal solution, let ˜W = W+11T and ˜b = b+1, then it is easy to know that wj-wk = ˜wj - ˜wk and bj -bk = ˜bj -˜bk, their objective function values are the same. There are multiple optimal solutions, and this is not what we want. Therefore, two more constraints should be imposed on problem (9), and the final objective function is as follows, where decision function fjk(xi) = (wj -wk)T xi +(bj -bk) and yjk i = { 1 if yi = j -1 if yi = k . When we use this model to classify a new sample, we use the same voting strategy as in one versus one strategy multiclass SVM. If sign ((wj - wk)T xi + bj - bk ) = 1, then vote for class j is added by one. It is easy to find out that the more k that satisfies wTj xi +bj > wTk xi +bk, the more votes j will get. It is easy to know that the predicted class should have the largest decision function value, In this way, we do not need to use vote strategy and compute decision function c(c-1) 2 times, we just need to compute decision function c times, and find the largest value. ## 4 Connections to Other SVMalgorithms In this section, we analyze the relations between our model and other multi-class SVM models. According to problem (10), we use hinge loss to replace all slack variable ξ jk i , and our problem becomes, where decision function fjk(xi) = (wj -wk)T xi +(bj -bk) and yjk i = { 1 yi = j -1 yi = k . Proposition 4.1. Our model can be transformed to the objective function (15) proposed in [Bredensteiner and Bennett, 1999] excluding term 1 2 c∑ j=1 b2j . Proof. First, we have Then, our objective function (12) can be transformed to an equivalent formation as follows, We introduce a slack variable ξ in the function above, and problem (12) can be represented as, Therefore, our model can be transformed to be the objective function proposed in [Bredensteiner and Bennett, 1999]. Proposition 4.2. Our objective function (10) has the same optimal solution as problem (6) proposed in [Guermeur, 2002]. Proof. To handle the constraints in objective function, we transform the primal problem (10) to a lagrangian dual problem, where αjk i ≥ 0 and βjk i ≥ 0. Then we take derivative of L(W, b, γ, λ) with respect to each wj and bj respectively, where wj is column j of matrixW, and bj is entry j in vector b, and set them to zero. We obtain the following two equations, where 0 is a vector in Rd . These two equations hold when we get the optimal solution, and then we sum up all the derivatives on wj, and get the following equation, In second term of the function above, whenever there is αkj i ykj i xi term, it will always be balanced out by another term -αkj i ykj i xi, therefore it is easy to know that, Therefore, equation holds that, Same as the derivation about parameter wj above, when we sum up all derivatives on bs, we get an equation Above all, two constraints on W and b in problem (6) do not affect the optimal solution, and they share same formulation now. So, it is true that these two models have the same optimal solution. Proposition 4.3. Our objective function (10) has the same optimal solution as problem (4) proposed in [Weston and Watkins, 1998]. Proof. As per the proof in Proposition 4.2, we have the equation that, where wj are optimal solutions of the original problem. It also implies that, Above all, our objective function (10) has the same optimal solution as problem (4). ## 5 Optimization Algorithm In this section, we are going to use stochastic gradient descent with variance reduction to solve this nonconvex and nonsmooth problem. Problem (10) can be rewritten as: where W ∈ Rd×c , b ∈ Rc , decision function fjk(xi) = (wj - wk)T xi + (bj - bk). ˜ yjk i is the predicted class for unlabeled data, and ˜ yi = arg max j wTj xi+bi. In this function, L denotes the samples which are labeled. C is the weight of unlabeled training data. Usually, C = 1 |U| . In each iteration, we select a xi ∈ Rd sample in training data randomly, and the objective function with respect to this sample can be represented as: When sample is from U, ˜ yi is computed through function (11). Then we take derivative of the above function with respect to wj, and there are two different cases: when j = yi, its subgradient is: the other case is when j ̸= yi, its subgradient is as follows: We also need to take derivative with respect to bj and get the subgradient, there are two cases j = yi and j ̸= yi The optimization algorithm to solve problem (25) is summarized in Algorithm 1. ## Algorithm 1 SVRG to solve problem (25) Initialize: ˜W 0 ∈ Rd×c , ˜b0 ∈ Rc , learning rate η and s = 0. while not converge do end for Randomly pick it ∈ {1, 2, ..., n} and update parameters for j=1,2...,c do end for end for end while ## 6 Experiments There are two main goals in our experiment, firstly, we will show that our model get the best or comparable performance compared with other related SVM models via computing classification accuracy; secondly, by looking at convergence figures, we will show that stochastic gradient descent method will get faster convergence rate on supervised learning task and even semi-supervised learning task which is a non-convex problem. Six multi-class classification datasets from UCI machine learning repository are used in our experiment [Lichman, 2013], main information are listed in Table 1. In this experiment, we compared our method with 3 traditional multi-class support vector machine models, OvsR in (1), OvsO in (3) and Crammer in (5). We use 5 times 5-fold cross validation and compute average accuracy for each method as final performance. In all experiments, we automatically tune the parameters by selecting among the values {10r , r ∈ {-5, ..., 5}}. We compare the convergence rate of our method with stochastic gradient descent algorithm with constant learning rate and decreasing learning rate. We select the largest learning rate for Figure 2: Suboptimality vs epochs. Suboptimality equals current objective function value minus optimal objective function value. The optimal objective function value is obtained by running our methods for a long time. ![Image](https://ijcai.org/proceedings/2017/fulltext/440/image_000001_8b7dc43cd7a17644bd220cc8b67ee83b009bb96e13fbcd55ef241dbe42e89be6.png) Table 1: Experiment datasets description. | Dataset | #Sample | #Attribute | #Class | |-------------|-----------|--------------|----------| | iris | 150 | 4 | 3 | | dermatology | 366 | 34 | 6 | | satimage | 4435 | 36 | 6 | | svmguide2 | 391 | 20 | 3 | | usps5 | 5427 | 256 | 5 | | waveform | 2746 | 21 | 3 | each method and ensure that objective function value is decreasing during optimization. We plot a figure of suboptimality versus epoch, and suboptimality equals current value of objective function minus optimal value of objective function. As shown in Table 2, we can see that our model can get always better or compared accuracy than other methods except OvsO multi-class SVM. It is normal because OvsO method has more parameters than our method. Figure 2 presents the convergence rate of three different stochastic gradient descent, constant learning rate, decreasing learning rate and stochastic gradient descent with variance reduction. It is clear that our method has much faster convergence rate after 10 epochs. Stochastic gradient descent method with constant learning rate and decreasing learning rate either has lower convergence rate or stop to converge because of decreasing learning rate. Table 2: Classification accuracy for all compared methods. | Dataset | OvsO | OvsR | Crammer | Proposed | |-------------|--------|--------|-----------|------------| | iris | 92.67 | 93.33 | 98.00 | 98.67 | | dermatology | 96.71 | 96.99 | 95.07 | 96.99 | | satimage | 82.64 | 87.24 | 85.68 | 86.02 | | svmguide2 | 80.00 | 82.56 | 81.03 | 82.31 | | usps5 | 97.75 | 97.95 | 97.55 | 97.80 | | waveform | 86.56 | 86.12 | 86.60 | 87.27 | ## 7 Conclusion In this paper, we follow the idea of maximizing margin between two classes and propose a novel multi-class SVM model. Analysis of the relation between our model and other related multi-class SVM models is also illustrated in the paper. Experiment results show that our model can get better or compared results than other related supervised and semisupervised SVM models. ## Acknowledgements This work was partially supported by the National Natural Science Foundation of China (61572388 and 61402026), and U.S. NIH R01 AG049371, NSF IIS 1302675, IIS 1344152, DBI 1356628, IIS 1619308, IIS 1633753. ## References 1. [Bredensteiner and Bennett, 1999] Erin J Bredensteiner and Kristin P Bennett. Multicategory classification by support vector machines. In Computational Optimization, pages 53-79. Springer, 1999. 2. [Cai et al., 2011] Xiao Cai, Feiping Nie, Heng Huang, and Chris Ding. Multi-class l2,1-norm support vector machine. In IEEE International Conference on Data Mining (ICDM 2011), pages 91-100, 2011. 3. [Campbell et al., 2006] William M Campbell, Joseph P Campbell, Douglas A Reynolds, Elliot Singer, and Pe- dro A Torres-Carrasquillo. Support vector machines for speaker and language recognition. Computer Speech & Language, 20(2):210-229, 2006. 4. [Chang et al., 2016a] Xiaojun Chang, Yao-Liang Yu, Yi Yang, and Eric P Xing. Semantic pooling for complex event analysis in untrimmed videos. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016. 5. [Chang et al., 2016b] Xiaojun Chang, Yao-Liang Yu, Yi Yang, and Eric P Xing. They are not equally reliable: Semantic event search using differentiated concept classi- fiers. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1884-1893, 2016. 6. [Cortes and Vapnik, 1995] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-297, 1995. 7. [Crammer and Singer, 2002] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. The Journal of Machine Learning Research, 2:265-292, 2002. 8. [Guermeur, 2002] Yann Guermeur. Combining discriminant models with new multi-class svms. Pattern Analysis & Applications, 5(2):168-179, 2002. 9. [Hsu and Lin, 2002] Chih-Wei Hsu and Chih-Jen Lin. A comparison of methods for multiclass support vector machines. Neural Networks, IEEE Transactions on, 13(2):415-425, 2002. 10. [Joachims, 1999] Thorsten Joachims. Transductive inference for text classification using support vector machines. In ICML, volume 99, pages 200-209, 1999. 11. [Kamruzzaman et al., 2010] SM Kamruzzaman, ANM Ka- rim, Md Islam, Md Haque, et al. Speaker identification using mfcc-domain support vector machine. arXiv pre- print arXiv:1009.4972, 2010. 12. [Lauer et al., 2007] Fabien Lauer, Ching Y Suen, and Gérard Bloch. A trainable feature extractor for handwritten digit recognition. Pattern Recognition, 40(6):1816-1824, 2007. 13. [Lichman, 2013] M. Lichman. UCI machine learning repo- sitory, 2013. 14. [Maji and Malik, 2009] Subhransu Maji and Jitendra Malik. Fast and accurate digit classification. EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS- 2009-159, 2009. 15. [Nie et al., 2014] Feiping Nie, Yizhen Huang, and Heng Hu- ang. New primal svm solver with linear computational cost for big data classifications. In The 31st International Conference on Machine Learning, pages 505-513, 2014. 16. [Nie et al., 2017] Feiping Nie, Xiaoqian Wang, and Heng Huang. Multiclass capped lp-norm svm for robust clas- sifications. In Thirty-First AAAI Conference on Artificial Intelligence, pages 2415-2421, 2017. 17. [Pilászy, 2005] István Pilászy. Text categorization and sup- port vector machines. In The proceedings of the 6th inter- national symposium of Hungarian researchers on compu- tational intelligence. Citeseer, 2005. 18. [Weston and Watkins, 1998] Jason Weston and Chris Wat- kins. Multi-class support vector machines. Technical re- port, Citeseer, 1998. 19. [Yang et al., 2017] Yanhua Yang, Cheng Deng, Dapeng Tao, Shaoting Zhang, Wei Liu, and Xinbo Gao. Latent max- margin multitask learning with skelets for 3-d action re- cognition. IEEE transactions on cybernetics, 47(2):439- 448, 2017.