Exclusivity Regularized Machine: A New Ensemble SVM Classifier

1 Introduction

Classification is a major task in machine learning and pattern recognition. In binary classification, a hypothesis is constructed from a feasible hypothesis space based on the training set {(xi, yi)}Ni=1 , where {xi}Ni=1 is a set of data points with xi ∈ Rd sampled i.i.d. under a distribution from an input subspace, and {yi}Ni=1 with yi ∈ {-1,+1} is the corresponding label set. The obtained hypothesis, also known as classifier, is "good" when it is capable to generalize well the "knowledge" learned from the training data to unseen instances. Multi-class cases can be analogously accomplished by a group of binary classifiers.

Over the past decades, numerous classifiers have been devised. The k-nearest neighbor (k-NN) [Altman, 1992] is an intuitive and simple one. However, its performance heavily depends on the selection of k and is sensitive to noisy data, making k-NN vulnerable in practice. Decision tree (DT) learning is to construct a tree by partitioning the source set into subsets according to a feature test. CART [Breiman et al., 1984] and C4.5 [Quinlan, 1993] are two examples of DT. The main drawbacks of decision trees are their sub-optimality and overfitting problems. Support vector machine (SVM) [Vapnik, 1995], as one of the most robust and accurate approaches, aims to find a hyperplane with the maximum margin between classes. Besides, linear discriminant analysis [Fisher,

1936] and naive Bayes [Domingos and Pazzani, 1997] are other classic classifiers.

As has been well recognized, a combination of various classifiers can improve predictions. Ensemble approaches, with Boosting [Freund and Schapire, 1997] and Bagging [Breiman, 1996] as representatives, make use of this recognition and achieve strong generalization performance [Zhou, 2012]. The generalization error of ensemble mainly depends on two factors, formally expressed as E = ¯E - ¯ A, where E is the mean-square error of the ensemble, ¯E represents the average mean-square error of component learners and ¯ A stands for the average squared difference (diversity) between the ensemble and the components. Error-Ambiguity decomposition [Krogh and Vedelsby, 1995], Bias-VarianceCovariance decomposition [Ueda and Nakano, 1996] and Strength-Correlation decomposition [Breiman, 2001] all confirm the above principle. Specifically, Boosting is a family of ensemble learning meta-algorithms, which improves the classification performance through letting the subsequent base learner pay more attention on data that have been wrongly grouped by the previous bases. AdaBoost is probably the most prominent Boosting scheme. While Bagging represents another category that tries to train a set of diverse weak classifiers by utilizing the bootstrap sampling technique. Several specific algorithms, such as random subspace [Ho, 1998], random forest [Breiman, 2001] and rotation forest [Rodriguez et al., 2006], have been proposed to further enforce the diversity of ensemble members. Certainly, both Boosting and Bagging can be applied to (most of) the conventional classifiers, e.g. DT and SVM.

Considering the popularity of SVM and the potential of ensemble, it would be beneficial to equip SVM with ensemble thoughts. Employing SVM as the base learner of Bagging or Boosting is a natural manner. Alternatively, this work provides a model to train a set of SVMs and integrate them as a homogeneous ensemble. The model jointly minimizes the training error and maximizes the diversity of base learners. Different from Bagging, our method does not rely on sampling schemes to achieve the diversity, although it is flexible to embrace such schemes. Additionally, the proposed method simultaneously trains all the base learners unlike Boosting methods doing the job sequentially. Concretely, the contribution of this paper can be summarized as follows: 1) we define a new measurement, namely (relaxed) exclusivity, to manage the diversity between base learners, 2) we propose a novel ensemble, called Exclusivity Regularized Machine (ExRM), which concerns the training error and the diversity of components simultaneously, and 3) we design an Augmented Lagrange Multiplier based algorithm to efficiently seek the solution of ExRM. Theoretical analysis on convergence, global optimality and linear complexity of the proposed algorithm is also provided.

2 Our Method

2.1 Preliminary

Arguably, SVM [Vapnik, 1995][Keerthi and DeCoste, 2005] is one of the most popular classifiers due to its promising performance. In general, the primal SVM (PSVM) can be modeled as follows:

where f(·) is a penalty function, Ψ(w) performs as a regularizer on the learner w and b is the bias. The function φ(·) is to map xi from the original D-dimensional feature space to a newM-dimensional one. Moreover, λ is a non-negative coefficient that provides a trade-off between the loss term and the regularizer. If PSVM adopts the hinge loss as penalty, the above (1) turns out to be:

where the operator (u)+ := max(u, 0) keeps the input scalar u unchanged if u is non-negative, returns zero otherwise, the extension of which to vectors and matrices is simply applied element-wise. Furthermore, p is a constant typically in the range [1, 2] for being meaningful. In practice, p is often selected to be either 1 or 2 for ease of computation, which correspond to ℓ1 -norm and ℓ2 -norm loss PSVMs, respectively. As for the regularization term, Ψ(w) := 1 2 ‖w‖22 (ℓ2 regularizer) and Ψ(w) := ‖w‖1 (ℓ1 regularizer) are two classical options.

2.2 Exclusivity RegularizedMachine

It is natural to extend the traditional PSVM (2) to the following ensemble version with C components as:

where W ∈ RM×C := [w1,w2, ...,wC] and b ∈ RC := [b1, b2, .., bC]T . Suppose we simply impose 12 ‖W‖2F or ‖W‖1 on W, all the components (and the ensemble) will have no difference with the hypothesis directly calculated from (2) using the same type of regularizer. 1 From this view, Ψ(W) is critical to achieving the diversity.

1 We note that splitting the training data into C sub-sets, like the bootstrap sampling, and training C classifiers separately on the subsets would lead to some difference between the components. However, this strategy does not essentially advocate the diversity of base learners. Although how to sample training subsets is not the focus of this work, our model has no difficulties to adopt such sampling strategies.

Prior to introducing our designed regularizer, we first focus on the concept of diversity. Although the diversity has no formal definition so far, the thing in common among studied measurements is that the diversity enforced in a pairwise form between members strikes a good balance between complexity and effectiveness. The evidence includes Q-statistics measure [Kuncheva et al., 2003], correlation coefficient measure [Kuncheva et al., 2003], disagreement measure [Ho, 1998], double-fault measure [Giacinto and Roli, 2001], k-statistic measure [Dietterich, 2000], mutual angular measure [Yu et al., 2011; Xie et al., 2015b; 2015a] and competition measure [Du and Ling, 2014]. These measures somehow enhance the diversity, however, most of them are heuristic. One exception is Diversity Regularized Machine [Yu et al., 2011], which attempts to seek the globally-optimal solution. Unfortunately, it often fails because the condition required for the global optimality, say ‖wc‖2 = 1 for all c, is not always satisfied. Further, Li et al. proposed a pruning scheme to improve the performance of DRM [Li et al., 2012]. But, DRM requires too much time to converge, which limits its applicability. Below, we define a new measure of diversity, i.e. (relaxed) exclusivity.

Definition 1. (Exclusivity) Exclusivity between two vectors u ∈ Rm and v ∈ Rm is defined as X (u, v) := ‖u ⊙ v‖0 = ∑mi=1 u(i) · v(i) ̸= 0, where ⊙ designates the Hadamard product, and ‖ · ‖0 is the ℓ0 norm.

From the definition, we can observe that the exclusivity encourages two vectors to be as orthogonal as possible. Due to the non-convexity and discontinuity of ℓ0 norm, we have the following relaxed exclusivity.

Definition 2. (Relaxed Exclusivity) The definition of relaxed exclusivity between u ∈ Rm and v ∈ Rm is given as Xr(u, v) := ‖u ⊙ v‖1 = ∑mi=1 |u(i)| · |v(i)|, where |u| is the absolute value of u. The relaxation is similar with that of the ℓ1 norm to the ℓ0 norm.

It can be easily verified that ‖u‖0 = X(u, 1), ‖u‖1 = Xr(u, 1) and ‖u‖22 = Xr(u, u), where 1 ∈ Rm is the vector with all of its m entries being 1.

Instead of directly employing ∑1≤˜ c̸=c≤C Xr(wc, w˜ c) as the final Ψ(W), we adopt the following:

The main reasons of bringing 12 ‖W‖2F into the regularizer are: 1) it essentially enhances the stability of solution, 2) it tends to mitigate the scale issue by penalizing large columns, and 3) as the relaxed exclusivity itself is non-convex, the introduction guarantees the convexity of the regularizer. Finally, the proposed Exclusivity Regularized Machine (ExRM) can be written in the following shape:

Remarks As expressed in Eq. (4), we have motivated the ℓ1,2 regularizer from a novel perspective. It has been verified that, as one of mixed norms, the ℓ1,2 is in nature able to capture some structured sparsity [Kowalski, 2009]. In general, the regression models using such mixed norms can be solved by a modified FOCUSS algorithm [Kowalski, 2009]. Zhou et al. [Zhang et al., 2010] introduced the ℓ1,2 regularizer into a specific task, i.e. multi-task feature selection, and used the subgradient method to seek the solution of the associated optimization problem. The responsibility of the ℓ1,2 regularizer is to enforce the negative correlation among categories [Zhang et al., 2010]. Recently, Kong et al. [Kong et al., 2014] utilized ℓ1,2 norm to bring out sparsity at intra-group level in feature selection, and proposed an effective iteratively re-weighted algorithm to solve the corresponding optimization problem. In this work, besides the view of motivating the ℓ1,2 regularizer, its role in our target problem, say constructing an ensemble of SVMs, is also different with the previous work [Kowalski, 2009; Zhang et al., 2010; Kong et al., 2014]. The functionalities of [Zhang et al., 2010] and [Kong et al., 2014] are the intra-exclusivity of multiple hypotheses (tasks) and the inter-exclusivity of a single hypothesis respectively, while our principle is the diversity of multiple components of a single ensemble hypothesis.

2.3 Optimization

With the trick that 1 - (φ(xi)T wc + bc)yi = yiyi - (φ(xi)T wc + bc)yi = yi(yi - (φ(xi)T wc + bc)), we introduce auxiliary variables eci := yi - (φ(xi)T wc + bc). In the sequel, the minimization of (5) can be converted into:

where X ∈ RM×N := [φ(x1), φ(x2), ..., φ(xN)], ec ∈ RN := [ec1 , ec2 , ..., ecN ]T , E ∈ RN×C := [e1 , e2 , ..., eC ] and y ∈ RN := [y1, y2, ..., yN]T . And each column of Y ∈ RN×C is y. Please note that, the constraint P = W is added to make the objective separable and thus solvable by the ALM framework. It is worth mentioning that, thanks to the convexity of each term in the objective and the linearity of the constraints, the target problem is convex. The Lagrangian function of (6) can be written in the following form:

with the definition Φ(U,V) := µ2 ‖V‖2F + 〈U,V〉, where 〈·, ·〉 represents matrix inner product and µ is a positive penalty scalar. In addition, Q ∈ RM×C and Z ∈ RN×C are Lagrangian multipliers. The proposed solver iteratively updates one variable at a time by fixing the others. Below are the solutions to sub-problems.

W sub-problem With the variables unrelated to W fixed, we have the sub-problem of W:

As observed from the problem (8), it can be split into a set of smaller problems. For each rowW·j, instead of directly optimizing (8), we resolve the following equivalent objective:

where G is formed by:

where ϵ → 0+ (a small constant) is introduced to avoid zero denominators. 2 Since both G and W·j depend on W·j, to find out the solution to (9), we employ an efficient reweighted algorithm to iteratively update G and W·j . As for W·j , with G fixed, equating the partial derivative of (9) with respect toW·j to zero yields:

Then G(k+1) is updated using W(k+1) ·j as in (10). The procedure summarized in Alg. 1 terminates when converged. b sub-problem Dropping the terms independent on b leads to a least squares regression problem:

E sub-problem Similarly, picking out the terms related to E gives the following problem:

where S(t) :=Y-XT P(t) -1b(t+1)T - Z(t) µ(t) . It can be seen that the above is a single-variable 2-piece piecewise function. Thus, to seek the minimum of each element in E, we just need to pick the smaller between the minima when yieci ≥ 0 and yieci < 0. Moreover, we can provide the explicit solution when p := 1 or 2 (for arbitrary p we will discuss it latter). When p := 1:

For p := 2:

where Ω ∈ RN×C := (Y ◦ S(t) > 0) is an indicator matrix, and ¯Ω is the complementary support of Ω. The definition of shrinkage operator on scalars is Sϵ>0[u] := sgn(u) max(|u| - ϵ, 0). The extension of the shrinkage operator to vectors and matrices is simply applied element-wise.

2 The derived algorithm can be proved to minimize ‖WT +ϵ‖21,2. Certainly, when ϵ → 0+, ‖WT + ϵ‖21,2 infinitely approaches to ‖WT ‖21,2.

Algorithm 1: W Solver

Input: W(t) , P(t) , Q(t) , µ(t) . Initial.: k ← 0; H(k) ←W(t) ; for j = 0 : M do while not converged do Update G(k+1) via Eq. (10); Update H(k+1) ·j via Eq. (11); k ← k +1; end end Output: W(t+1) ← H(k)

Algorithm 2: Exclusivity Regularized Machine

Input: Training set {(xi, yi)}Ni=1 , positive integer C and

P sub-problem There are two terms involving P. The associated optimization problem reads:

Its closed-form solution can be obtained by:

where we denote K := (I + XXT )-1 and M := Y - 1b(t+1)T - Z(t) µ(t) .

Multipliers and µ Two multipliers and µ are updated by:

For clarity, the procedure of solving (2) is outlined in Algorithm 2. The algorithm should not be terminated until the change of objective value is smaller than a pre-defined threshold (in the experiments, we use 0.05). Please see Algorithm 2 for other details that we can not cover in the text.

3 Theoretical Analysis

First, we come to the loss term of ExRM (5), which assesses the total penalty of base learners as ∑Cc=1 ∑Ni=1 (1 - (φ(xi)T wc + bc)yi )p+, where p ≥ 1. Alternatively, the loss of the ensemble {we, be} := { 1C ∑Cc=1 wc, 1C ∑Cc=1 bc} is ∑Ni=1 (1 - (φ(xi)T we + be)yi )p+. We have the relationship between the two losses as described in Proposition 1.

Proposition 1. Let {w1, b1},..., {wC, bC} be the component learners obtained by ExRM (Alg. 2), and {we, be} := { 1C ∑Cc=1 wc, 1C ∑Cc=1 bc} the ensemble, the loss of {we, be} is bounded by the average loss of the base learners.

Proof. This can be established by Jensen's inequality.

The proposition indicates that as we optimize ExRM (5), an upper bound of the loss of the ensemble is also minimized. Thus, incorporating with our proposed regularizer, ExRM is able to achieve the goal of simultaneously optimizing the training error of ensemble and the diversity of components.

One may wonder why not minimizing the loss of the ensemble, which seems reasonable, like:

The reason is that the optimal solution of (19) is exactly that of PSVM (2). The solution of (19) satisfies that one entry in the i-th row of W is we(i) and the rest ones are all zero, having the columns of W absolutely independent. But, the exclusivity achieved in this way is meaningless. According to Proposition 1, their equivalence is reached when each wc is identical with we. Based on the analysis above, we can say that, compared with (19), ExRM is more proper, which desires to find a balance between the diversity and consistency (training error) of base learners.

Next, we shall consider the convergence and optimality of the designed algorithms. We first confirm the property of Alg. 1, which is established by Theorem 1.

Theorem 1. The updating rules (10) and (11) for solving the problem (9), i.e. Algorithm 1, converges and the obtained optimal solution is exactly the global optimal solution of the problem (8).

Proof. Algorithm 1 is actually a special case of the algorithm proposed in [Kong et al., 2014]. We refer readers to [Kong et al., 2014] for the detailed proof.

With Theorem 1, we have come to the convergence and optimality of our proposed Algorithm 2.

Theorem 2. The solution consisting of the limit of the sequences {W(t) }, {b(t) } and {E(t) } generated by Algorithm 2, i.e. (W(∞) , b(∞) ,E(∞) ), is global optimal to ExRM (5), and the convergence rate is at least o( 1 µ(t) ).

Proof. Due to space limit, instead of the complete proof, we here only provide the proof sketch including three main steps: 1) (W(t) , b(t) ,E(t) ) approaches to a feasible solution, i.e. limt→∞‖P(t) - W(t) ‖F = 0 and limt→∞‖E(t) - Y + XtP(t) + 1b(t)T ‖F = 0; 2) All of

{P(t) }, {Z(t) }, {Q(t) }, {W(t) }, {b(t) } and {E(t) } are bounded; 3) limt→∞ 12 ‖W(t) ‖21,2 + λ‖(Y ◦ E(t) )+‖pp = limt→∞ Lμ(t-1) (W(t) , b(t) , E(t) , P(t) , Q(t-1) , Z(t-1) ) due to Lμ(t-1)(W(t) , b(t) , E(t) , P(t) , Q(t-1) , Z(t-1) ) = 12 ‖W(t) ‖21,2 + λ‖(Y ◦ E(t) )+‖pp + ‖Q(t) ‖2F -‖Q(t-1) ‖2F 2μ(t-1) + ‖Z(t) ‖2F -‖Z(t-1) ‖2F 2μ(t-1) . Then the conclusion can be drawn with the feasibility of solution by Alg. 2, the convexity of problem (5), and the (descending) property of an ALM algorithm.

In addition, we show the complexity of Alg. 2. Updating each row of W takes O(qC 2 ) and O(qC) for (11) and (10) respectively, where q is the (inner) iteration number of Alg. 1. Please note that, due to the diagonality of G, the inverse of G + μI only needs O(C). Therefore, the cost of Alg. 1 is O(qC 2M ). The b sub-problem requires O(CMN ). The complexity of the E sub-problem is O(CMN ), for both p := 1 and p := 2. Solving P spends O(CMN + CM 2 ). Besides, the update of the multipliers is at O(CMN ) expense. In summary, Alg. 2 has the complexity of O(tCM (qC + N + M )), where t is the number of (outer) iterations required to converge.

4 Experimental Verification

We adopt several popular UCI benchmark datasets for performance evaluation. 3 All experiments are conducted on a machine with 2.5 GHz CPU and 64G RAM.

Parameter Effect Here, we evaluate the training and testing errors of ExRMC (C ∈ {5, 10, 30} means the component number) against varying values of λ in the range [0.05, 4]. All the results shown in this experiment are averaged over 10 independent trials, each of which randomly samples half data from the sonar dataset for training and the other half for testing. The first picture in Fig. 1 displays the training error and testing error plots of L2 loss ExRM with L2 loss PSVM [Nie et al., 2014] (denoted as L2-PSVM) as reference. From the curves, we can observe that, as λ grows, the training errors drop, as well as composing less base learners leads to a smaller training error. This is because more and more effort is put on fitting data. As regards the testing error, the order is reversed, which corroborates the recognition that the predication gains from the diversity of classifiers, and reveals the effectiveness of our design in comparison with L2-PSVM. Besides, the testing errors change very slightly in a relatively large range of λ, which implies the insensitivity of ExRM to λ. The second picture corresponding to p := 1 shows an additional evidence to p := 2. Although the performance gaps between the different cases shrink, the improvement of ExRM is still noticeable. Based on this evaluation, we set λ to 2 for both L1-ExRM and L2-ExRM in the rest experiments.

3 Available at www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets

Convergence Speed & Training Time Although the convergence rate and complexity of the proposed algorithm have been theoretically provided, it would be more intuitive to see its empirical behavior. Thus, we here show how quick the algorithm converges, without loss of generality, on the ijcnn1 dataset. From the third picture in Fig. 1, we can observe that, when p := 2, all the three cases converge with about 30 iterations. The cases correspond to p := 1 take more iterations than p := 2 (about 70 iterations), but they are still very efficient. Please note that, for a better view of different settings, the objective plots are normalized into the range [0, 1]. The rightmost picture in Fig. 1 gives curves of how the CPUtime used for training increases with respect to the number of training samples. Since the training time is too short to be accurately recorded, we carry out each test for 10 independent trials, and report the total training time (in seconds). As can be seen, the training time for both p := 1 and 2 is quasi linear with respect to the size of training data. For all the three cases that correspond to ExRM5, ExRM10 and ExRM30, the choice of p barely brings differences in time. The gaps between the three cases dominantly come from the number of base learners. The PSVM only needs to learn one classifier while ExRM requires to train multiple bases. 4

Performance Comparison This part first compares our proposed ExRM with the classic ensemble models including AdaBoost and Bagging with Tree as the base learner (denoted as AdaTree and BagTree, respectively), and the recently designed DRM. The codes of DRM are downloaded from the authors' website, while those of AdaTree and BagTree are integrated in the Matlab statistics toolbox (fitensemble). The base of DRM, ν-SVM, is from LibSVM.

Table 1 provides the quantitative comparison among the competitors. We report the mean testing errors over 10 independent trials. Since the sizes and distributions of the datasets vary, to avoid the effect brought by the amount of training data and test the generalization ability of the ensembles learned from different types of data, we randomly sample 150 data points from a dataset as its training set and the rest as the testing. AdaTree and BagTree are inferior to ExRM and DRM in most cases. The exception is on the splice dataset. As for our ExRM, we can see that it significantly outperforms the others on australian, sonar, heart and ionosphere, and competes very favorably on the german dataset. On each dataset, we assign ranks to methods. The average ranks (A.R.) of the competitors over the involved datasets are given in the last column of Tab. 1. It can be observed that the top five average ranks are all lower than 5.0, and four of which are from ExRM methods. The best and the second best belong to L2-ExRM30 (A.R.=2.5) and L2-ExRM10 (A.R.=3.4) respectively, while the fourth and fifth places are taken by L1ExRM10 (A.R.=4.8) and L1-ExRM30 (A.R.=4.9) respectively. The third goes to DRM10, the average rank of which is 4.6. The results on the ijcnn1 are not included in the table, as all the methods perform very closely to each other, which may lead to an unreliable rank.

4 In [Nie et al., 2014], the authors have revealed via extensive experiments, that PSVM (SVM-ALM) is much more efficient than SVMperf [Joachims, 2006], Pegasos [Shalev-Shwartz et al., 2007], BMRM [Teo et al., 2010], and TRON [Lin et al., 2008], PCD [Chang et al., 2008] and DCD [Hsieh et al., 2008].

Another issue should be concerned is the efficiency. Table 2 lists the mean training time over all the datasets and each dataset executes 10 runs. From the numbers, we can see the clear advantage of our ExRM. L1-ExRM10 and L2-ExRM10 only spend about 0.05s on training, while the ExRMs with 30 components, i.e. L1-ExRM30 and L2-ExRM30, cost less than 0.14s. Both AdaTree and BagTree are sufficiently efficient, which take less than 0.3s to accomplish the task. But the training uses 16.86s and 59.38s by DRM for the 10-base and 30-base cases respectively. We would like to mention that the core of DRM is implemented in C++, while our ExRM is in pure Matlab. Moreover, as theoretically analyzed and empirically verified, our algorithm is linear with respect to the size of training set.

As aforementioned, employing SVM as the base of AdaBoost or Bagging is a way to construct an ensemble SVM. Here, we repeat the previous experiment to see the difference among AdaBoost plus L2-PSVM (AdaSVM), Bagging plus L2-PSVM (BagSVM), DRM and our L2-ExRM. Please note that L2-ExRM and DRM reduce to PSVM and ν-SVM respectively, when the base number is 1. Table 3 provides the average testing errors over all the datasets (each method runs 10 times). From the numbers, we can observe that both AdaSVM and BagSVM outperform DRM for all the cases, while ExRM shows the best results among the competitors.

5 Conclusion and Discussion

The diversity of component learners is critical to the ensemble performance. This paper has defined a new measurement of diversity, i.e. exclusivity. Incorporating the designed regularizer with the hinge loss function gives a birth to a novel model, namely ExRM. The convergence of the proposed ALM-based algorithm to a global optimal solution is theoretically guaranteed. ExRM can take into account more elaborate treatments for further improvement. For instance, thanks to the relationship ‖u‖1 = Xr(u, 1), the sparsity on W can be promoted by extending ˜W to [W, β1], where β is a weight coefficient of the sparsity. In addition, it is difficult to directly solve the E sub-problem (13) with arbitrary given p. Fortunately, in this work, it is always that p ≥ 1. Thus the partial derivative of (13) with respect to E is monotonically increasing. The binary search method can be employed to narrow the possible range of E by half via each operation. In this work, we did not take any advantages of Boosting and Bagging. It is positive that ExRM is able to act as the base learner for both Boosting and Bagging. By doing so, Boosting ExRM and Bagging ExRM can be viewed as ensembles of ensemble and expected to further boost the performance.

Acknowledgments

Xiaojie Guo is supported by National Natural Science Foundation of China (grant no. 61402467). Haibin Ling is supported by National Natural Science Foundation of China (grant no. 61528204) and National Science Foundation (grant no. 1350521).