Diversity Regularized Machine

1 Introduction

Ensemble methods, such as AdaBoost [Freund and Schapire, 1997], Bagging [Breiman, 1996] and Random Forests [Breiman, 2001], are among the state-of-the-art learning approaches. Ensemble methods train a number of component learners for a learning task, and combine them to achieve a strong generalization performance. It has been widely accepted that to achieve a good ensemble, the component learners should be accurate and diverse. This recognition was first theoretically justified by the error-ambiguity decomposition [Krogh and Vedelsby, 1995] for regression tasks as E = ¯E - ¯ A, where E is the mean-square error of the ensemble, ¯E is the average mean-square error of component learners, and ¯ A is the average difference between the ensemble and the component learners. This decomposition implies that, as long as ¯E is fixed, a higher difference among the component learners leads to a better ensemble. Later results achieved by the bias-variancecovariance decomposition [Ueda and Nakano, 1996], the strength-correlation decomposition [Breiman, 2001], and the information-theoretical decompositions [Brown, 2009; Zhou and Li, 2010] all confirmed that the diversity among the component learners is a key to the ensemble performance.

∗The research was supported by NSFC (60975043), JiangsuSF (BK2008018) and 973 Program (2010CB327903).

Though it remains an open problem on how to measure and evaluate diversity [Brown, 2009; Zhou and Li, 2010], many effective ensemble methods have already been developed. These methods employ different mechanisms to create diverse component learners, mostly using randomization strategies by smart heuristics [Ho, 1998; Breiman, 2000; 2001; Dietterich, 2002; Zhou and Yu, 2005; Brown et al., 2005].

In this paper, we propose to managing the diversity among component learners in a deterministic mathematical programming framework, resulting in the diversity regularized machine (DRM) which generates an ensemble of SVMs [Vapnik, 1995] with an imposed diversity constraint. Theoretical analysis in the PAC learning framework [Valiant, 1984] discloses that the diversity constraint used in DRM can effectively reduce the hypothesis space complexity. This implies that the diversity control in ensemble methods plays the role of regularization as in popular statistical learning approaches. Experiments show that DRM can improve both the training and generalization accuracy of SVM, and is superior to some state-of-the-art SVM ensemble methods.

The rest of this paper is organized as follows. Section 2 presents the DRM, which is then theoretically analyzed in Section 3 and experimented in Section 4. Section 5 concludes.

2 DRM

Consider an input space, X and an underlying distribution D over X. A hypothesis, or a learner, is a function h : X → {-1, 1}, and a concept c is an underlying hypothesis. A training set is a set of m examples S = {(xi, yi)}mi=1 , where xi ∈ X are drawn i.i.d. under D and yi = c(xi). A learning algorithm is to select a hypothesis h from a feasible hypothesis space H according to the given training set. For an integer number n, we denote [n] as the set {1, 2, . . . , n}.

2.1 DiversityMeasure

We consider linear classification model w ∈ Rd , which classifies an instance by the inner product w⊤φ(x), where φ(x) is a feature mapping of the instance x. Note that the model can be viewed as equivalent to the commonly used model w⊤φ(x)+b , since by extending the mapping φ(x) to one extra dimension with a constant value, the extended w absorbs the functionality of b.

We note that, though there is no agreement on what form diversity should be defined in, the studied measures of diversity usually can be in a pairwise form, i.e., the total diversity is the sum of a pairwise difference measure, measuring classification effectiveness. Such diversity measures include Qstatistics measure [Kuncheva et al., 2003], correlation coefficient measure [Kuncheva et al., 2003], disagreement measure [Ho, 1998], double-fault measure [Giacinto and Roli, 2001], κ statistic measure [Dietterich, 2000], etc. Thus we also consider a form of diversity based on pairwise difference. Given a pairwise diversity measure div in a metric space of hypotheses, we consider the total diversity in norm p of the set of hypotheses H = {h1, . . . , hT } as

Notice that each hypothesis hi is a linear learner without the bias term, thus the direction of the linear learner effects the classification most. Thus, for a pair of linear learners w1 and w2, we measure their diversity using the angle between them,

so that the larger value of div, the larger angle between the linear learners.

2.2 Learning with Diversity Constraint

The training of multiple diverse linear learners can be formulated as an optimization framework that minimizes a loss function with a constraint of diversity. The framework for training T linear learners, w1, . . . ,wT , can be described as:

where θ is the capacity control for each linear model, divp is the p-norm diversity measure, q is the minimum amount of the diversity required, φ is a feature mapping induced by kernel k, ℓ is a loss function (e.g., hinge loss for classification problem or square loss for regression problem). After the training, the combined model is wc = 1 T ∑Tt=1 wt, which is still a linear learner.

Specifically, for classification problem, we implement the framework with the 1-norm diversity measure div1 and follow the ν-SVM framework [Sch¨olkopf et al., 2000] with square hinge loss. Thus, the framework is implemented as:

where μ corresponds to q in Eq.(1), ξt = [ξt,1, . . . , ξt,n]⊤ is a vector of slack variables, ν is the parameter to trade-off the ρ-margin and the slack variables.

2.3 Optimization

Under some conditions, which will be discussed later, the solution of Eq.(2) satisfies ‖wt‖2 = 1 for all t. Using this equation, the diversity term w⊤ t wt′ ‖wt‖‖wt′‖ is then simplified as w⊤ t wt′ . Further note that adding a constant ‖wt‖22 + ‖wt′‖22 (that is 2) will not change the optimal solution of Eq.(2), thus the diversity term can be replaced by ‖wt +wt′‖22 . We then have the following relaxed convex optimization problem:

Since the constraints in Eq.(3) is naturally separable for each learner, instead of directly solving the large-scale quadratically constrained quadratic program (QCQP) problem of Eq.(3), we employ an efficient alternating optimization technique [Luo and Tseng, 1992]. The alternating optimization sequentially solves small QCQP problems with variables {wt, ρt, ξt} while fixing the other variables {wt′ , ρt′ , ξt′} for all t′ ̸= t as constants. Mathematically, in each step we are solving the following small QCQP problem for each t:

Further, the above QCQP problem can be addressed via sequential quadratic programming efficiently. Introducing the Lagrange multipliers αt and λt for the constraints in Eq.4, we have:

where αt = [αt,1, . . . , αt,n]. Setting the partial derivations w.r.t. {wt, ρt, ξt} to zeros, we have:

Let ˆwt = ∑t′ ̸=t wt′ , we then obtain the solution of wt as:

and thus the dual of Eq.(4) can be cast as:

which is jointly-convex for {αt, λt} [Boyd and Vandenberghe, 2004]. We further employ the alternating optimization technique to achieve the global optimal solution of the dual of Eq.(4) [Luo and Tseng, 1992]. Specifically, when λt is fixed, αt can be solved via:

where K is the kernel matrix of φ(x) and ⊙ is the entry-wise product, and r is a vector with components:

Noted that Eq.6 is a convex quadratic programming problem involving only one equality constraint, this is similar to the dual problem of SVM which can be efficiently solved by state-of-the-art SVM solver, such as Libsvm using SMO algorithm [Chang and Lin, 2001].

When αt is fixed, λt can be solved in a closed-form, i.e.,

2

Algorithm 1 presents the pseudocode of the DRM. It is worth noticing that, when the optimal solution of all λt's are non-zeros, according to KKT condition, the optimal solution {w∗ t , ρ∗t , ξ∗ t }Tt=1 obtained by DRM according to Eq.(3) satisfies ‖w∗ t ‖22 = 1, thus is also the optimal solution of Eq.(2).

3 Theoretical Analysis

3.1 Preliminaries

Probabilistic Approximately Correct (PAC) learning [Valiant, 1984] is a powerful tool for analyzing learning algorithms. There has been much development of the theory, however, we choose to use the simple results for the clarity of presenting our core idea, instead of proving the tightest results. Comprehensive introductions to learning theory can be found in textbooks such as [Anthony and Bartlett, 1999].

Noted that y ∈ {-1, +1} and h ∈ [-1, +1], the margin of h on an instance is yh(x). The training error with margin γ of a hypothesis h is defined as

where I is the indicator function that outputs 1 if its inner expression is true and 0 otherwise. Define the generalization error, or true error, as

Algorithm 1 DRM

Input: Training set S = {(xi, yi)}mi=1 and kernel matrix K, parameters T and μ Process: 1: λt ← 1 and wt ← 0, ∀t ∈ [T ] 2: while not converged yet do 3: for t = 1, . . . , T do 4: while not converged yet do 5: αt ← solutions returned by Eq. (6) 6: λt ← solutions returned by Eq. (7) 7: end while 8: set wt ← according to Eq. (5) 9: end for 10: end while Output: wc = 1 T ∑Tt=1 wt

It is well known that, the generalization error of a learning algorithm A can be bounded using its empirical error and the complexity of its feasible hypothesis space. For linear learners, its hypothesis space is uncountable, thus we measure that using covering number as the definition below.

Definition 1 (Covering Number) Given m samples S = {x1, . . . , xm} and a function space F, characterize every f ∈ F using a vector vS(f ) = [f (x1), . . . , f (xm)] in a metric space Bm with metric ρ. The covering number Np(F, γ, S) is the minimum number l of vectors u1, . . . , ul ∈ Bm such that, for all f ∈ F there exists j ∈ {1, . . . , l},

Lemma 1 [Bartelett, 1998] Consider the learning algorithm A selecting a hypothesis from space H according to m random examples. For all γ > 0, with probability at least 1 - δ, the generalization error is bounded as

where N∞ is the covering number with infinity norm.

Lemma 1 indicates that the generalization error is bounded by two factors, one is the performance on the training set, and the other is the hypothesis space complexity. A good learning algorithm should balance the two factors well.

3.2 Analysis of DRM

First, we look into the loss term of DRM in Eq.(2), which evaluates the loss of each hypothesis (linear learner) as:

where ξt,i ≥ ρt - yiw⊤ t φ(xi)(∀i ∈ [m]) by the constraints. We concern about the loss of the combined hypothesis wc = 1 T ∑Tt=1 wt with ρc = 1 T ∑Tt=1 ρt:

where ξi ≥ ρc - yiw⊤ c φ(xi)(∀i ∈ [m]). We then have the following proposition.

Proposition 1 Let w1, . . . ,wT be the component hypotheses solved by DRM, and wc = 1 T ∑Tt=1 wt be the combined hypothesis, the loss of wc is bounded as

Proof. Notice that, for a training instance x, the classification margin yw⊤ c φ(x) can be expanded as y 1 T ∑Tt=1 w⊤ t φ(x), which is no larger than 1 T ∑Tt=1 ρt - 1 T ∑Tt=1 ξt by the constraints in Eq.(2). Since ρc = 1 T ∑Tt=1 ρt, the proposition is then proved by that ∑Tt=1 ξ 2 t ≥ ( 1 T ∑Tt=1 ξt)2 .

The proposition shows that, as we optimize the loss of component hypotheses, we also optimize an upper bound of the loss of the combined hypothesis. Keeping the proposition in mind, we then focus on the hypothesis space complexity.

We conceptively distinguish the hypothesis space of the component hypothesis and that of the combined hypothesis. Let w1, . . . ,wT be hypotheses from space H, and the combined wc be in space Hc. We will use Lemma 2.

Lemma 2 [Zhang, 2002] If H is a space such that for all w ∈ H, it holds ‖w‖2 ≤ a, then for any ϵ > 0,

where C1 and C2 are constants.

We then consider if maximizing the diversity, can lead to constraining the norm of wc, which results Theorem 1.

Theorem 1 Let H be a space such that for all w ∈ H, it holds ‖w‖2 ≤ a. If Hc is a space such that for all wc ∈ Hc there is a set H = {w1, . . . ,wT} ∈ HT satisfying wc = 1 T ∑Ti=1 wi and div∞(H) > q, then for any ϵ > 0,

where C1 and C2 are constants.

Proof. Since wc = 1 T ∑Ti=1 wi, we explicitly write wc as w = [ 1 T ∑Ti=1 wi,1, . . . , 1 T ∑Ti=1 wi,d]. By the constraint div∞(H) > q, we have, for all i, j, 1 - w⊤ i wj ‖wi‖·‖wj‖ ≥ q, so that

Therefore,

Applying Lemma 2, the theorem is proved.

From the proof, it can be observed that, by summing up vectors, the norm of the combined vector is decomposed into the sum of norm of every vector and the inner product between every different vectors, which is interestingly in a similar form to the error-ambiguity decomposition.

It is more interesting to connect maximum diversity principle to maximum entropy principle. The entropy of a vector defined as follows can lead to a bound of covering number.

Definition 2 [Zhang, 2002] The (uniform) entropy of a vector w is defined as

Lemma 3 [Zhang, 2002] If H is a space such that for all w ∈ H, it holds w has no negative entries, ‖w‖1 ≤ a, and entropy(w) ≤ c, then for any ϵ > 0,

where C1 and C2 are constants.

Lemma 4 Given H = {w1, . . . ,wT} be a set of T vectors in Rd , let wc = 1 T ∑Ti=1 wi. If div∞(H) > q, then entropy(wc) ≤ ‖wc‖1 ln d ≤ √ 1 T a + (1 - q)a2 ·√d ln d.

Lemma 4 is proved by the relationship between 1-norm and the diversity. Besides, we can have an intuitive explanation. The entropy measures the uniformness of a vector. When two vectors are with a large angle, their large components are likely to be in different locations, so that their average leads to a more uniform vector, i.e., large entropy. The proof of Theorem 2 follows Lemma 3 and Lemma 4, and is ignored due to limited page space.

Theorem 2 Let H be a space such that for all w ∈ H, it holds w has no negative entries and ‖w‖1 ≤ a. If Hc is a space such that for all wc ∈ Hc there is a set H = {w1, . . . ,wT } ∈ HT satisfying wc = 1 T ∑Ti=1 wi and div∞(H) > q, then for any ϵ > 0,

where C1 and C2 are constants.

Remark. Both Theorems 1 and 2 disclose that constraining a large diversity can lead to a small hypothesis space complexity. Notice that the training performance is optimized. According to Lemma 1, a good generalization performance can be expected. It should also be noted that Theorems 1 and 2 do not mean that diversity maximization equals norm constraint or entropy maximization, here we only use them as the bridging techniques for the proofs.

4 Experiments

Fifteen UCI data sets are employed to conduct the experiments. All features are normalized into the interval [0, 1].

SVM and DRM share the same RBF kernel with the width being the average distance among training instances, and the same parameter ν determined through 5-fold cross-validation on the training set. DRM has two more parameter, μ, controlling the amount of diversity, and T , the number of component learners. μ is also selected by 5-fold cross validation on training sets. We consider three ensemble sizes, that is, 21, 51 and 101. For comparison, we also evaluate the performance of Bagging (abbreviated as Bag) and AdaBoost (abbreviated as Ada). We perform 20 times hold-out tests with random data partitions, half data for training and the other half for testing. Table 1 summarizes the comparison results. On each data set, we assign ranks to methods. The best method receives the rank 1, and the worst the rank 10. The last row of Table 1 presents the average ranks. A two-tail pair-wise t-test with 95% significance level is employed to compare every pair of the evaluated approaches, and the win/tie/loss counts are summarized in Table 2.

It can be observed from the last row of Table 1 that the average ranks of DRM methods are all lower than 5, while the ranks of the other methods are above 5. From Table 2, by the t-test, DRM is never worse than SVM, while Bagging and AdaBoost are worse than SVM on some data sets. Comparing with Bagging which always makes marginal improvement, DRM can have much larger improvement. Comparing with AdaBoost which is, sometimes, much worse than SVM, DRM is more robust. The t-test shows that DRM has more wins than losses comparing to Bagging, and is comparable with AdaBoost. Moreover, by comparing DRM with difference ensemble size, it can be observed that the size does not have a significant impact on its performance. The observations suggest that DRM has a comparable overall performance with Bagging and AdaBoost, but is more robust.

Figure 1 plots the effect of μ against the training and testing errors on four data sets, where, for a clear view, we don't show the curves in a high error range. First, it can be observed that, when the training error of DRM is not larger than that of SVM, DRM generally has a smaller testing error. This also validates our setting of μ value according to the training error. Second, plots (a) and (b) show that DRM can reduce both the training and test error from SVM, while plots (c) and (d) show that DRM can still reduce the test error even when the training error is higher than SVM. Moreover, it can be observed from plots (b) to (d) that DRM can have a smaller generalization gap (i.e., the gap between training and testing error) than SVM. Particularly, in plot (b), the generalization gap closes to zero when log10 μ is around -2.

5 Conclusion

Diversity has been recognized as the key to the success of ensemble methods. In contrast to previous methods which encourage diversity in a heuristic way, in this paper, we propose the DRM approach based on mathematical programming framework, which explicitly controls the diversity among the component learners. Theoretical analysis on DRM discloses that the hypothesis space complexity can be effectively reduced by the diversity constraint. The analysis suggests that the diversity control in ensemble methods plays a role similar to the regularization; this provides an explanation to why diversity is important for ensemble methods. Experiment shows that DRM can significantly improve the generalization performance, and is superior to some state-of-the-art ensemble methods. Comparing with Bagging which always makes marginal improvement, DRM can lead to much larger improvement; comparing with AdaBoost which is sometimes much worse than single learner, DRM never loses to single learner in our experiments.

In our analysis, we try to perform simple derivations in order to clarify the main idea. Incorporating more elaborate treatments (e.g. [Smola et al., 2000]) may result in tighter bounds. Moreover, we only concern diversity and leave the consideration of the combination scheme for future work.

Acknowledgement

The authors want to thank the reviewers for their helpful comments, and thank Min-Ling Zhang and Sheng-Jun Huang for their suggestions to improve the paper.