Improving the Generalization Performance of Multi-class SVM via Angular Regularization

1 Introduction

Multi-class classification, which classifies a data sample x into one of K > 2 classes, is a fundamental task in machine learning. Among the various methods developed to accomplish this task, multi-class support vector machine (MSVM) [Weston and Watkins, 1998; Crammer and Singer, 2001; Shalev-Shwartz et al., 2011; Kumar et al., 2012] is a premier model that possesses both empirical efficacy and sound theoretical properties. At the core of MSVM is the principle of maximum margin learning [Crammer and Singer, 2001], encouraging the margin - which in the multi-class case is defined as the difference between the classification score w⊤ y x corresponding to the true label y and the largest score of other classes maxy′ ̸=yw⊤ y′x - to be large, such that different classes can be well discriminated.

In training multi-class classification models, one typical problem is overfitting where the model performs well on training data but poorly on testing data. To improve the generalization performance on unseen samples, a number of regularization methods have been studied, such as ℓ2-norm [Vapnik and Vapnik, 1998] encouraging large margin, ℓ1-norm [Bradley and Mangasarian, 1998; Wang and Shen, 2012] promoting sparsity and trace norm [Amit et al., 2007] encouraging low-rankness. While their effectiveness have been widely demonstrated, there is still much room for improvement. As an example, Table 1 shows the classification accuracy of ℓ2regularized MSVM on several datasets, where the gap between training and testing accuracy are still substantial.

Figure 1: (a) Without angular regularization, the small angle between the green and blue lines narrows the decision region C3, which is consequently unable to accommodate unseen samples; (b) with angular regularization, the angle between the two lines is enlarged, which subsequently widens C3, that is more flexible to accommodate unseen data.

In this paper, we study a new type of regularizer that encourages the coefficient vectors (equivalently, the hyperplanes parameterized by them) in MSVM to have large angles, for the purpose to control overfitting. Fig. 1 illustrates the idea. Without regularization (Fig. 1(a)), the two hyperplanes denoted by the green and blue lines share a small angle, generating a narrow decision region C3 which is supposed to accommodate data samples of class 3 (denoted by triangles). While C3 successfully accommodates most training samples (denoted by filled triangles), many test samples (denoted by void triangles) fall out of C3 and get misclassified due to the narrowness of this region, incurring severe overfitting. To alleviate this problem, an angular regularizer can be applied to enlarge the angle between these two hyperplanes, which consequently widens C3, enabling it to successfully accommodate unseen samples. Previously, anglebased regularizers have been studied in other contexts, such as ensemble learning [Guo, 2016] and latent variable modeling [Xie et al., 2015a; Xie, 2015]. To our best knowledge, our work represents the first one introducing angular regularization into multi-class SVM. While the existing angular regularizers have shown promising results, they bear certain limitations, for instance, not amenable for theoretical analysis or optimization. We define a new angular regularizer based on the singular values of the coefficient matrix. These singular values are encouraged to approach uniformity, which reduces the correlation among different classes. Decreasing this regularizer can effectively enlarge the angles between coefficient vectors. In analysis, it is proved that decreasing the regularizer can reduce generalization error. In experiments on various datasets, we demonstrate the efficacy of this regularizer in preventing overfitting.

The major contributions of this paper are:

• We introduce the angular regularization into MSVM to improve its generalization performance.
• We propose a new angular regularizer that is amenable for optimization and theoretical analysis.
• Theoretically, we analyze how the angular regularizer affects the generalization performance.
• Empirically, we evaluate the effectiveness of the regularizer in control overfitting on various datasets.

The rest of this paper is organized as follows. Section 2 introduce the angular regularizer, which is applied to MSVM. Section 3 and 4 present the theoretical analysis and experimental results. Section 5 reviews related works and Section 6 concludes the paper.

2 Methods

In this section, we develop a new angular regularizer and apply it to regularize MSVM.

2.1 Multi-class Support Vector Machine (MSVM)

MSVM [Crammer and Singer, 2001; Weston and Watkins, 1998; Guermeur and Monfrini, 2011] is a well-established method for K-class classification. Given a set of training samples S = {(x1, y1), . . . , (xm, ym)}, each represented with a feature vector x ∈ RD and a class label y ∈ Y = {1, . . . ,K}, MSVM aims to learn a coefficient vector w for each class to separate the K classes apart. At the core of MSVM is the large margin principle [Crammer and Singer, 2001]: given a sample (x, y), the classification score w⊤ y x of the true label y is preferred to be larger than the scores of other classes with a certain margin (typically set to 1), namely

where r = argmaxk∈Y,k̸=y w⊤ k x. Let W ∈ RD×K denote the coefficient matrix where the k-th column vector belongs to class k, MSVM solves the following optimization problem

where the first term is a hinge loss encouraging large margin and the second term is an ℓ2 regularizer.

2.2 ANewAngular Regularizer

We propose to use an angular regularization to improve the generalization performance of MSVM. Previous angular regularizers [Yu et al., 2011; Bao et al., 2013; Xie et al., 2015a] either are not amenable for optimization or do not facilitate theoretical analysis. In this section, we aim to define a new angular regularizer that overcomes these limitations.

Given K coefficient vectors {wk}Kk=1 , we first measure the pairwise angles between them:

Similar to [Xie et al., 2015a], we place an absolute value over w⊤ i wj to make θij insensitive to vector flip (fromw to -w). Then a straightforward angular regularizer R(W) can be defined as the negative of the minimum angle

Minimizing R(W) encourages these coefficient vectors to have larger angles. As will be discussed later, this definition facilitates theoretical analysis. However, it is not amenable for optimization since it is non-smooth. To address this issue, we use a smooth function ̂R(W) to approximate R(W) and perform optimization over ̂R(W) instead.

A Decorrelation Regularizer To define ̂R(W), we begin with interpreting the angles from a statistical perspective. For the ease of presentation, we impose a constraint over W:

where 1 ∈ RD is a vector whose elements are all 1. This constraint ensures the row vectors of W sum to 0. We will remove this constraint later on. Given two classes i and j, together with their coefficient vectors wi and wj , we can treat i and j as two random variables and {win}Dn=1 , {wjn}Dn=1 as samples drawn from them. The empirical correlation of these two random variables are defined as

where ¯wi = 1n ∑Dn=1 win and ¯wj = 1n ∑Dn=1 wjn. According to the constraint in Eq.(5), we have ¯wi = 0 and ¯wj = 0, then ρij = cos(θij), which indicates that to encourage the angle to be larger, we can equivalently suppress the correlation.

Based on this idea, we define a regularizer ̂R(W) that encourages small correlation. First we compute the K × K Gram matrix G = W⊤W, where Gij = w⊤ i wj. Suppose W is a column full-rank matrix and K < D, then G is a full-rank matrix with rank K. Let G= ∑Ki=1 λiuiu⊤i be the eigen-decomposition where λi is an eigenvalue and ui is the associated eigenvector. To understand the geometry meanings of these eigenvalues and eigenvectors, we can take a row view (Fig. 2) of W. Different from the column view where each column vector is a D-dimensional coefficient vector, in the row view, each row vector can be treated as a sample of a K-dimensional random vector by regarding the classes as random variables. According to Eq.(5), these samples have zero mean.

Under this view, G can be thought of as an empirical covariance matrix of the random vector. Consider a point cloud formed by the D samples in the K-dimensional space, as is well known in Principle Component Analysis [Jolliffe, 2002], an eigenvector ui of G represents a principal direction of the point cloud and the associated eigenvalue λi tells the variability of points along that direction. As shown in Fig. 3, the larger λi is, the more spread out the points along the direction ui. The level of disparity among eigenvalues indicates the level of correlations among the K dimensions. The more different the eigenvalues are, the higher the correlation is. In Fig. 3(a), the two eigenvalues have a large discrepancy and the two dimensions are strongly correlated. In contrast, in Fig. 3(b) where λ1 and λ2 are close, the correlation between the two dimensions is minimal. To reduce correlation, we encourage the eigenvalues to be uniform. We first transform the eigenvalues {λi}Ki=1 into a probability distribution p(X) through normalization

then encourage p(X) to be close to a uniform distribution q(X = i) = 1K , where the "closeness" is measured using Kullback-Leibler divergence

Note that the i-th eigenvalue λi of W⊤W is the square of the i-th singular value of W. Hence, KL(q||p) is essentially defined over the singular values of W. Using the two facts

we have

KL(q||p) = log tr(W⊤W) - 1K log det(W⊤W) - log K. Dropping the constant, we define a decorrelation regularizer

subject to W⊤1 = 0. From now on, we drop this constraint, which does not affect theoretical results given in next section. ̂R(W) is a smooth function that is much easier to optimize than R(W). Next, we show that ̂R(W) can achieve similar effect as R(W): enlarging angles between vectors inW.

Connection between ̂R(W) and R(W) The following theorem states that ̂R(W) is closely aligned with R(W).

Theorem 1. Let ∇̂R be the gradient of ̂R(W) w.r.t W. ∃κ > 0, such that ∀ η ∈ (0, κ), R(W- η∇ ̂R) ≤ R(W).

Proof Due to space limit, we present the proof sketch of Theorem 1, and the following lemma is needed.

Lemma 1. (Extension of Lemma 2 in [Xie et al., 2015a]) Let the weight vector wk of hyperplane k be decomposed into wk = xk + lkek, where xk = ∑Kj=1,j̸=k αjwj lies in the subspace L spanned by {w1, . . . ,wK}\{wk}, ek is in the orthogonal complement of L, ‖ek‖ = 1, ek · wk > 0, lk is a positive scalar. Then the gradient of ̂R(W) w.r.t wk is pkxk + qkek, where pk is a positive scalar .

Some of the proof techniques are borrowed from [Xie et al., 2015a]. Let s(W) = cos(-R(W)) = cos(θi∗j∗). If s(W) = 0, then s(W- η∇̂R) - s(W) = |(pi∗ + pj∗)s(W) + o(η)|[1 + f(η) + o(η)] = o(η), such that limη→0 s(W-η∇ ̂R)-s(W) η = 0. Otherwise, if s(W) ̸= 0, then s(W-η∇̂R) s(W) = 1 + ψi∗j∗η + o(η), where ψi∗j∗ = -[ pi∗l2 i∗-qi∗li∗ ‖wi∗‖2 + pj∗l2 j∗-qj∗lj∗ ‖wj∗‖2 ]. We have pi∗l2 i∗-qi∗li∗ ‖wi∗‖2 = li∗ K(ei∗·wi∗)‖wi∗‖2 > 0 and pj∗l2 j∗-qj∗lj∗ ‖wj∗‖2 > 0, so ψi∗j∗ < 0. Thus, limη→0 s(W-η∇ ̂R)-s(W) η = s(W) · limη→0 s(W-η∇̂ R) s(W) -1 η = s(W)ψi∗j∗ < 0. Overall, ∃κ > 0, such that ∀η ∈ (0, κ), we have s(W-η∇̂R)-s(W) η ≤ 0, i.e. R(W - η∇ ̂R) ≤ R(W). □

From Theorem 1, we can see the negative gradient of ̂R(W) is a descent direction of R(W). Hence these two regularizers have closely-aligned shape and the same local optimal points. ̂R(W) can be utilized as a close approximation of R(W). Decreasing ̂R(W) effectively decreases R(W), which enlarges the angles.

MSVM with Angular Regularization Given ̂R(W), we can utilize it to enlarge the angles between coefficient vectors in MSVM, for the sake of reducing overfitting. An angleregularized MSVM (AR-MSVM) problem can be defined as:

where β is the regularization parameter. We use a stochastic sub-gradient method [Shalev-Shwartz et al., 2011; Wang et al., 2010] to solve the AR-MSVM problem. The gradient of

̂R(W) is

The subgradient of the hinge loss L = max(0, 1 +w⊤ ri xi - w⊤ yi xi) is a zero matrix if w⊤ yi -w⊤ ri xi > 1. Otherwise, the k-th column vector of the sub-gradient matrix is xi if k ̸= yi and is -xi if k = yi.

3 Analysis

In this section, we analyze how the angular regularizer R(W) affects the generalization performance of MSVM. We begin with a recap of basic terminologies. Let L(h) = E(x,y)∼D[l(x, y)] be the true risk of a hypothesis h, where D represents the true distribution and l(x, y) is the loss function. Let ̂L(h) = 1m ∑mi=1 l(xi, yi) denote the empirical risk. Let h∗ ∈ argminh∈H L(h) and ˆh ∈ argminh∈H ̂L(h) be the true and empirical risk minimizer respectively. The generalization error is defined as L(ˆh)-L(h∗ ) which measures how well the hypothesis ˆh learned on the training data generalizes on the unseen data.

In the analysis of AR-MSVM, the hypothesis set is defined as H = {h|h(x, y) = w⊤ y x, x ∈ RD , y ∈ Y = {1, . . . ,K}}. Let H1 be the best-case hypothesis set where different classes can be perfectly separated: ∀(x, y), r ∈ Y\{y},w⊤ y x ≥ w⊤ r x. For each hypothesis h ∈ H, its multi-class margin for the input-output pair (x, y) is ρh(x, y) = h(x, y) -maxk̸=y h(x, k). And the loss set is defined as A = {l|l(x, y) = Φp(ρh(x, y))} , where Φp(x) = max(0, 1 - x/p) is a p-margin hinge loss. In addition, we assume ‖x‖2 ≤ C1 and ‖w‖2 ≤ C2.

The generalization error bound of AR-MSVM is given in the following theorem.

Theorem 2. Fix p > 0. Then, for any δ > 0, with probability at least 1 - δ, the following multi-class classification genralization bound holds for all h ∈ H ⇝ H1 :

With the objective function in Eq.(10) decreasing, the maximum margin principle encourages H approaching H1 . As can be seen, the generalization error bound is an increasing function of the angular regularizer R(W). Hence decreasing R(W) can reduce the error bound and improve the generalization performance.

3.1 Proof Sketch

Inspired by [Xie et al., 2015b], we bound L(ˆh)-L(h∗ ) using Rademacher complexity Rm(A) = E[supl∈A 1m ∑mi=1 σi · l(xi, yi)] , where σi is uniform over {-1, 1}.

Lemma 2. [Percy, 2015] Fix p > 0. Then, for any δ > 0, with probability at least 1 - δ

Then we bound Rm(A). Let ˜H = {z = (x, y) ↦→ ρh(x, y)} be an auxiliary hypothesis set, we have

Lemma 3. For a fixed p > 0, we have

The R‖m(A) denotes Rm(A)'s absolute form [Bartlett and Mendelson, 2002]. The second inequality is from the following proposition and the Lipschitz condition of p-margin hinge loss.

Proposition 1. (Extension of Theorem 1 in [Cortes et al., 2013]) For any fixed y ∈ Y, HX only takes x into consideration. From ˜H, the empirical Rademacher complexity has

Next we bound B with the same Lipschitz condition and analyze ρh(x, y)'s distribution w.r.t H. The key step is making use of R(W) to upper bound ‖W‖op (operator norm).

Lemma 4. Fix p > 0. Then, for any hypothesis set H, |l(x, y)| can be bounded as |l(x, y)| ≤ 2p C1C2 + 1.

When H ⇝ H1 , a tighter bound is acquired

Putting the pieces together 1 , we can obtain Theorem 2.

4 Experiments

In this section, we present experimental results.

4.1 Experimental Setup

We evaluated our method on ten datasets. Table 2 summaries their statistics. The regularization parameters λ and β are tuned in the range [2-20 , 2-19 , . . . , 220 ] via 5-fold cross validations. In the stochastic sub-gradient descent algorithm, the mini-batch size and number of epochs are set to 20 and 50 respectively. The learning rate is set according to ADADELTA [Zeiler, 2012] in all methods. All the experiments are conducted over 10 random train/test splits and the results are averaged over the 10 runs. We compare AR-MSVM with the following baselines: (1) C-SVC [Chang and Lin, 2011]: performing multi-class classification using an one-against-one strategy. (2) AMM [Wang et al., 2011]: a multi-class classification method based on adaptive multi-hyperplanes; (3) MSVM-ℓ1 [Shalev-Shwartz and Tewari, 2011]: ℓ1-regularized MSVM; (4) CS-MSVM:

1 For more details, please refer to the complementary document at http:// act.buaa.edu.cn/ lijx/ pubs/ ijcai17-2077-supply.pdf .

MSVM regularized by a cosine similarity regularizer [Yu et al., 2011]; (5) IC-MSVM: MSVM regularized by an incoherence regularizer [Bao et al., 2013]; (6) Div-MSVM: MSVM regularized by a diversity-promoting regularizer [Xie et al., 2015a]; (7) MSVM-Struct [Tsochantaridis et al., 2004]: ℓ2regularized MSVM solved with a cutting plane algorithm; (8) MSVM-ℓ2 [Wang et al., 2010]: ℓ2-regularized MSVM solved with a stochastic gradient descent algorithm; Two metrics are used for evaluation: accuracy (Acc) and F-measure (F).

4.2 Results

Table 3 shows the classification results on six datasets, from which we observe that: (1) AR-MSVM greatly improves upon vanilla MSVM methods, including MSVM-ℓ2 and MSVM-Struct. Comparing the last two columns, we can see AR-MSVM outperforms MSVM-ℓ2 (which works better than MSVM-Struct) on all the datasets. This demonstrates that the angular regularizer can effectively improve the generalization performance on test data. (2) AR-MSVM achieves better performance than CS-MSVM, IC-MSVM and Div-MSVM. These three methods use previously proposed regularizers to encourage large angles as well. But the incoherence (IC) regularizer and diversity-promoting (Div) regularizer are non-smooth, bringing in difficulty for optimization, which we conjecture is the major reason being inferior to the angular regularizer proposed in this paper. The cosine similarity (CS) regularizer can encourage the sum of angles to increase, but cannot guarantee each individual angle is increased. The AR regularizer we proposed strictly increases the minimal angle, hence ensuring all angles are increased. (3) AR-MSVM outperforms MSVM-ℓ1, demonstrating that angular regularization is more effective in control overfitting than ℓ1 regularization. (4) AR-MSVM outperforms two non-MSVM methods: C-SVC and AMM, demonstrating its competitive performance in solving multi-class classification problems. (5) AR-MSVM achieves better improvement on Fmeasure than on accuracy. Accuracy is biased toward classes with larger number of samples. F-measure aims to reduce this bias and is more suitable to measure the performance on small-sample classes. This indicates AR-MSVM's ability to better classify small-sample classes.

To verify the ability of AR in enlarging angles, we plot how the minimal angle changes as the algorithm proceeds. Fig. 4(a) shows the curve on the New-thyroid dataset with β ≈ 0.02. It can be seen that the minimal angle consistently increases, which demonstrates that AR is able to drive the angles to become large.

4.3 Parameter Sensitivity

We study the sensitivity of AR-MSVM to the regularization parameter β. Fig. 4(b) shows how accuracy varies as β increases on the New-thyroid dataset. Initially, increasing β improves accuracy, because a larger β results in larger angles that help prevent overfitting. However, further increasing β causes the accuracy to drop. That is because, if β is too large, the regularizer dominates the hinge loss and impairs the largemargin learning.

4.4 Imbalanced Classification

Inspired by the study in [Xie et al., 2015a] that large-angle regularizer can effectively capture infrequent patterns when the frequency of patterns is imbalanced, we are interested in how the AR helps with imbalanced classification [Wang and Yao, 2012] where the number of samples of different classes is imbalanced. In Table 4, we compare with state-of-theart methods dealing with class imbalance, including GlobalCS, CS, Static-SMT, SL-SMT and AdaB.NC (summarized in [Fern´aNdez et al., 2013]). As can be seen, on three datasets, our method achieves the best accuracy, demonstraing its ability to handle imbalanced classification. To further verify this, we measure the per-class accuracy on the Page-Blocks dataset in Table 5. On small classes (2-5), AR-MSVM performs much better than MSVM. On large class (1), they are comparable. This indicates that AR-MSVM is able to improve the performance on small classes without sacrificing that on large classes.

4.5 Computational Time

We evaluate how much extra time is incurred after adding the angular regularizer to MSVM. The algorithms were implemented in MATLAB and the experiments were run on a Linux machine with a 2.00GHz Xeon CPU and 256G memory. A comparison of runtime is shown in Fig. 5. As can be seen, the runtime of AR-MSVM is close to MSVM. The extra time cost is moderate.

5 RelatedWork

5.1 Multi-class Classification

Many works [Lee et al., 2004; Guermeur and Monfrini, 2011] have been proposed for multi-class classification. A detailed comparison is provided in [Wang and Xue, 2014]. Wang et al. [2011] proposed an Adaptive Multi-hyperplane Machine (AMM) algorithm that consists of a set of hyperplanes (weights), each assigned to one of the multiple classes, and predicts based on the associated class of the weight that provides the largest prediction. Lapin et al. [2015] proposed a top-k multiclass SVM that directly optimizes the top-k performance in image classification, to deal with class ambiguity. This method generalizes multiclass SVM based on a tight convex upper bound of the top-k error.

To avoid overfitting, several regularizers have been proposed. The ℓ2-norm [Vapnik and Vapnik, 1998] penalizes the magnitude of coefficients while encouraging large margin. The ℓ1-norm [Bradley and Mangasarian, 1998; Wang and Shen, 2012], which promotes sparsity, can effectively control overfitting in high dimensional feature spaces. Amit et al. [2007] uses trace norm to encourage low-rankness on the coefficient matrix, for the sake of capturing common structure shared by different classes. Guo [2016] proposed an angle-based regularization method in the ensemble learning of multiple binary SVMs.

5.2 Angular Regularizers

Several regularizers have been proposed to control the angles (equivalently, the cosine similarity) between vectors, in the context of ensemble learning, latent variable modeling and deep learning. Yu et al. [2011] computes the pairwise cosine similarity sij between K vectors and defines the regularizer as ∑1≤i<j≤K (1 - sij). Similarly, Bao et al. [2013] aggregates the cosine similarity scores into a regularizer -log( 1 K(K-1) ∑1≤i<j≤K β|sij|) 1β where β > 0. In [Xie et al., 2015a], the regularizer is defined as mean of arccos(|sij|) minus the variance of arccos(|sij|). The variance term is utilized to encourage the vectors to evenly spread out to different directions. These regularizers have two limitations. First, they are not amenable for theoretical analysis. Second, some of them are non-smooth functions that present great challenges for optimization.

Another closely related regularizer is Determinantal Point Process (DPP) [Kulesza et al., 2012]. Given K vectors {wi}Ki=1 , DPP defines a probability distribution p({wi}Ki=1 ) ∝ det(G). G is a K × K kernel matrix where Gij = k(ai, aj) with k(·, ·) as a kernel function. det(·) denotes the determinant of a matrix. Under a linear kernel, the DPP regularizer is analogous to ̂R(W) in Eq.(9). The shortcoming of DPP is that it is sensitive to vector scaling, which can be overcome by the log tr(W⊤W) term in ̂R(W).

6 Conclusion

In this paper, we introduce a new regularization method - angular regularization - into multi-class SVM, to improve its generalization performance. This regularizer encourages the coefficient vectors to have larger angles such that the decision regions can be widen to flexibly accommodate unseen data. We define a novel angular regularizer by encouraging the singular values of the coefficient matrix to approach evenness and prove its effectiveness. We analyze how this regularizer influences the generalization performance of MSVM and the results indicate that decreasing the regularizer can reduce the generalization error bound. The evaluation on a number of datasets demonstrate the capability of this regularizer in reducing overfitting.

Acknowledgements

This work is supported by China 973 Fundamental R&D Program (No.2014CB340300), NSFC program (No.61472022, 61421003), SKLSDE-2016ZX-11, and partly by the Beijing Advanced Innovation Center for Big Data and Brain Computing. The corresponding author is Jianxin Li.