Self-Paced Boost Learning for Classification

1 Introduction

Effectiveness and robustness are two essential principles of generic supervised learning studies. The effective learning focuses on the discriminativeness of the model to capture the intrinsic data patterns for an accurate prediction. The robust learning typically lies in a distinction of the reliable data from the noisy, confusing data, such that the learning is guided by the reliable samples and less influenced by the confusing ones. The efforts of most approaches for learning from the data generally come down to these two aspects.

For effective learning, the key issue lies in the complex distributions of data with local nonlinear structures. To effectively explore these patterns, the boosting scheme [Zhou, 2012] is developed. Generally, the boosting methods build a strong ensemble model as a combination of multiple weak models, where each weak model focuses on the samples mispredicted by the previous model ensembles. Through this, boosting performs an asymptotic piecewise approximation to the data distributions to fit each sample sufficiently. On the other hand, since only the mispredicted samples are considered in each step, the boosting is sensitive to the noisy and confusing data which greatly affect the optimization, especially at the later learning stage. Figure 1 shows a toy example of the decision boundary of boosting classifier for synthetic data with confusing data points. The boosting scheme is very discriminative while lacking a learning robustness.

¶peterpite, xilizju, zhongfei♦@zju.edu.cn;

dymeng@mail.xjtu.edu.cn;

¶wufei, junx, yzhuang♦@cs.zju.edu.cn.

⇤Corresponding authors

For robust learning, the goal is to relieve the influence of the noisy and confusing data. The confusing data generally correspond to the highly nonlinear local patterns hardly learnable for the model space, and the noisy ones are the outliers that should not be learned. Typically, the learning robustness relies on a sample selection to distinguish the reliable samples from the confusing ones. The recently studied self-paced learning (SPL) [Zhao et al., 2015] is such a representative effort. SPL is a learning paradigm that dynamically incorporates the samples into learning from easy ones to complex ones. With a self-controlled sample selection embedded in learning, the model is calibrated in a pace adaptively controlled by what it has already learned. Thus, SPL smoothly guides the learning to emphasize the patterns of the reliable discriminative data rather than those of the noisy and confusing ones, and obtains the learning robustness.

Based on the above analysis, we notice that boosting and SPL are consistent in basic principles and complementary in methodology. For consistency, both schemes are based on an asymptotic learning process from a weak/simple state to a strong/hard state. On the other hand, boosting and SPL are complementary in three aspects. First, the two schemes are respectively concerned on each of the two essential tasks of machine learning, the effectiveness and the robustness. Second, while boosting imposes a negative suppression on the insufficiently learned samples, SPL positively encourages the easily learned ones in a controlled pace. Third, boosting focuses more on the inter-class margins by striving to fit each sample, while SPL is more concerned with the intra-class variations by dynamically selecting easy samples with different patterns. Thus, boosting tends to reflect the local patterns and is more sensitive to the noisy data, while SPL tends to explore the data smoothly with more robustness. As a result, the two learning schemes are prone to benefit from each other.

To simultaneously enhance the learning effectiveness and robustness, in this paper, we propose a unified framework Self-Paced Boost Learning (SPBL). With an adaptive pace from easy to hard in boosting optimization, SPBL asymptotically guides the learning to focus on the insufficiently learned samples with high reliability. Through this, SPBL learns a model in both directions of positive encouragement (on reliable samples) and negative suppression (on misclassified samples), and is capable of capturing the intrinsic interclass discriminative patterns while ensuring the reliability of the samples involved in learning. Figure 1 further shows the decision boundary of SPBL on the toy dataset, which demonstrates its robustness and effectiveness.

We formulate SPBL as a fully-corrective optimization for classification problem. Note that SPBL is a general framework for supervised learning and could be formulated for other supervised applications. The contributions of this paper are summarized as follows:

1. We propose a unified learning framework SPBL that learns in a joint manner from weak models to strong model and from easy samples to complex ones. To the best of our knowledge, this is the first work that reveals and utilizes the association of boosting and SPL to simultaneously enhance the effectiveness and the robustness for supervised learning.

2. We formulate SPBL as a fully-corrective max-margin boosting optimization with self-paced sample selection for classification task.

2 RelatedWork

We review the literature from the aspects of boost learning and self-paced learning.

Boosting is a family of supervised ensemble learning approaches which convert weak learners to strong ones [Zhou,

2012]. The boosting methods construct a strong (highly accurate) model by iteratively learning and combining many weak, inaccurate models, where each weak model focuses on the samples mispredicted by the previous models. The main variation among different boosting methods is their ways of weighting training samples and weak learners. Examples of boosting methods include Adaboost [Freund and Schapire, 1997], SoftBoost [R¨atsch et al., 2007], TotalBoost [Warmuth et al., 2006], LPBoost [Demiriz et al., 2002], LogitBoost [Friedman et al., 2000], and MadaBoost [Domingo and Watanabe, 2000]. Boosting methods are applied in extensive applications, such as multi-class classification [Shen et al., 2012b; Zhu et al., 2009], regression [Duffy and Helmbold, 2002], metric learning [Shen et al., 2012a], and statistical modeling[Tutz and Binder, 2006; Mayr et al., 2014]. The effectiveness of boosting lies in its piecewise approximation of a nonlinear decision function to sufficiently fit the data patterns [Schapire and Freund, 2012]. However, [Long and Servedio, 2010] indicates that many boosting methods cannot withstand random classification noise.

First proposed by [Kumar et al., 2010], the self-paced learning is inspired by the learning process of humans that gradually incorporates the training samples into learning from easy ones to complex ones. Different from the curriculum learning [Bengio et al., 2009] that learns the data in a predefined order based on prior knowledge, SPL learns the training data in an order from easy to hard dynamically determined by the feedback of the learner itself, which is initially developed for avoiding the bad local minima. SPL is applied in different applications, such as image segmentation [Kumar et al., 2011], multimedia reranking [Jiang et al., 2014a], matrix factorization [Zhao et al., 2015], and multiple instance learning [Zhang et al., 2015]. Variants of SPL are also developed, such as self-paced curriculum learning [Jiang et al., 2015], and SPL with diversity [Jiang et al., 2014b]. Furthermore, [Meng and Zhao, 2015] provides a theoretical analysis of the robustness of SPL, which reveals the consistency of SPL with the non-convex regularization. Such regularization is upperbounded to restrict the contributions of noisy examples to the objective, and thus enhances the learning robustness.

3 Self-Paced Boost Learning

3.1 ProblemFormulation

Let ¶(xi↪ yi)♦ni=1 be a set of n multi-class training samples, where xi 2 Rd is the feature of sample i, yi 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ C♦ is the class label of xi, and C is the number of classes. Based on the standard supervised learning scheme, a classification model lies in learning a score function Fr (·) : Rd ! R for each class with which the prediction is made:

where Fr (x; ⇥) serves as the confidence score of classifying sample x to class r, parameterized by ⇥. Following the maxmargin formulation, the general objective function for multiclass classification is given by:

where ⇢ir is the score margin of xi between its ground truth class yi and class r; L : R!R+ is a loss function; R(⇥) is a regularization for ⇥; ⌫ > 0 is a trade-off hyperparameter. Generally, the loss function L(·) should be convex as a convex surrogate of the 0-1 loss, and be monotonically decreasing for a large margin. The regularization R (⇥) is introduced to impose prior constraints on ⇥ to relieve overfitting.

The two key issues of learning the classifier lie in an effective formulation of the score function Fr (·), and a robust formulation of the loss function L(·). For an effective modeling, we adopt the boosting strategy that learns the classifier Fr (·) from weak models to a strong model. The effectiveness of boosting for classification lies in its asymptotic piecewise approximation for a nonlinear decision function to sufficiently fit the underlying data distributions. Specifically, a strong classifier Fr (·) is formulated as an ensemble of weak classifiers ¶hj (·) 2 H♦kj=1 in the space of weak models H:

where each hj (·) : Rd ! ¶0↪ 1♦ is a binary weak classifier; wrj > 0 is the weight parameter to be learned. Here ⇥ is specified as the weight matrix W, defined as W = [w1↪ · · · ↪wC] 2 Rk⇥C with each wr = [wr1↪ · · · ↪wrk]T .

On the other hand, the learning robustness relies on the formulation of the loss function L(·) to relieve the influence of noisy and confusing data. Instead of directly learning from the whole data batch, we aim to guide the boosting model to learn asymptotically from the easy/faithful samples to the complex/confusing ones in a smooth pace. Therefore, inspired by the self-paced learning (SPL) scheme [Kumar et al., 2010], we reformulate the boosting model with a selfpaced loss formulation, and propose a unified framework, Self-Paced Boost Learning (SPBL).

The general objective of SPBL is formulate as:

where H 2 Rn⇥k is the weak classifiers' responses for the training data with [Hij ] = [hj (xi)], and Hi: is the i-th row of H; vi 2 [0↪ 1] is the SPL weight of sample xi that indicates its learning "easiness"; g (·; λ) : [0↪ 1] ! R is the SPL function that specifies how the samples are selected (the reweighting scheme of v) controlled by the SPL parameter λ > 0.

In Eq. (4), a weight vi is assigned to each sample as a measure of its "easiness". These SPL weights are tuned based on the current losses of samples and the SPL function g (vi; λ) to dynamically select the easily learned samples that are more reliable and discriminative. With a joint optimization of sample selection (for v) and boost learning (for W), the SPBL model gradually incorporates the training samples into learning from easy ones to complex ones, so as to control the pace of boost learning by what the model has already learned.

For a specific formulation of Eq. (4), we specify L(·) as a smooth loss function, the logistic loss, for the convenience of derivation, and specify R(W) as the l2↪1-norm to exploit the group structure of the weak classifier ensembles:

where kWk2↪1 = Pkj=1 kWj:k2 . Note that the above objective is l2↪1-norm regularized to impose a group sparsity constraint on the rows of W. The optimization would encourage the columns of W (each class) to select a relatively concentrated and shared subset of base classifiers, instead of learning them independently. We present the optimization of Eq. (5) and the specification of g (vi; λ) in the next subsection.

3.2 Optimization

We use an alternating optimization to solve Eq. (5), which optimizes each of the two variables with the other one fixed in an alternating manner. For the optimization of v, we have

where li = Pr ln (1 + e-⇢ir ) denotes the loss of sample xi. To solve vi in Eq. (6), the self-paced function g (vi; λ) needs to be specified. [Jiang et al., 2014a] has summarized the general properties of a self-paced function in three aspects. First, g (vi; λ) is convex w.r.t. vi 2 [0↪ 1] to guarantee the uniqueness of v⇤ i . Second, v⇤ i (li; λ) is monotonically decreasing w.r.t. li, which guides the model to select easy samples with smaller losses in favor of complex samples with larger losses. Third, v⇤ i (li; λ) is monotonically increasing w.r.t. λ, which means that a larger λ has a higher tolerance to the losses and can incorporate more complex samples. Several examples of the self-paced function have been listed in [Jiang et al., 2014a], such as hard weighting, linear weighting, and mixture weighting. We specify the self-paced function as the one for mixture weighting, due to its overall better performance in the experiments:

where an extra SPL parameter ⇣ is introduced in addition to λ. The corresponding optimal v⇤ i is given by:

which is a mixture of a hard 0-1 weighting and a soft realvalued weighting.

For the optimization of W, we have

To solve W in Eq. (9), we adopt the column generation method [Demiriz et al., 2002], due to the potentially infinite number of candidate weak models in the H space. The column generation is applied in the dual space of W to maintain a small set of weak models as the active dual constraints. This active set is augmented during optimization until it is sufficient to reach a solution within a tolerance threshold. We check the dual problem of Eq. (9):

where δryi = 1 (r = yi) is an indicator function. U 2 Rn⇥C is the Lagrangian multiplier of the equality constraints of Eq. (9), with a relation to the primal solution:

The derivation of Eqs. (10) and (11) is similar to that of [Shen et al., 2012b].

Based on the column generation, the set of active weak classifiers is augmented by a weak model ˆh (·) that most violates the current dual constraints in Eq. (10):

Then the optimization continues with the new set of active weak models, until the violation score (objective value of Eq. (12)) reaches a tolerance threshold.

Eq. (12) indicates that the matrix U serves as the sample importance for learning a new weak classifier. Moreover, from Eq. (11) we see that U gives high weights to not only the misclassified samples with small margins ⇢ir, but also the easy samples with high SPL weights vi. That means that U is actually a composite measure of learning insufficiency and learning easiness. Since the vi weights are set in the previous iteration, based on Eq. (12), the future weak learners will put emphasis on samples that are both insufficiently learned currently and easily learned previously. The interactions of the update of the model parameters are summarized in Figure 2. As a balance and trade-off between boosting and SPL, the proposed SPBL performs learning in both directions of positive encouragement (on reliability) and negative suppression (on learning insufficiency), and takes both effectiveness and robustness into concern for learning a classification model.

Further, it is easily seen that the multi-class boosting classification model of [Shen et al., 2012b] is a special case of SPBL with all SPL weights v fixed as 1n. By replacing vi in Eq. (11) with 1, the matrix U only emphasizes the misclassified samples with small margins, with the new weak classifier learned accordingly. Thus, the boosting method tends to be sensitive to the noisy and hardly learnable data by striving to correctly classify these samples. Therefore, the proposed SPBL is a robust generalization of boosting models.

We summarize the optimization procedure in Algorithm 1. The algorithm alternates between learning new ˆh (·) (Line 5), updating W (Line 6), updating U (Line 7) and reweighting v in an SPL manner (Line 8). Note that the SPL parameters (λ↪ ⇣) are iteratively increased (annealed) if they are small (Line 10 to 12), so as to introduce more (difficult) samples in the future learning. Furthermore, we adopt an early stopping criterion on a held-out validation set when the iteration number exceeds TES times to maintain a better generalization performance and a reasonable running time.

4 Experiments

We evaluate the performance of SPBL classification on three real-world datasets. The comparative methods include softmax regression (SR), multi-class SVM (MultiSVM), MultiBoost [Shen et al., 2012b], and Multi-class Adaboost (AdaBoost) [Zhu et al., 2009]. SR and MultiSVM are also embedded with a self-paced learning scheme for comparison, denoted as SR-S and MultiSVM-S.

Specifically, the two baseline methods, SR and MultiSVM, are formulated based on a linear classifier, where SR optimizes a log-likelihood and MultiSVM optimizes a hinge-loss. The MultiBoost is a fully-corrective formulation of multiclass boosting classification, which is a special case of SPBL with v fixed as 1n. The Multi-class AdaBoost is a multi-class generalization of AdaBoost as a stagewise additive boosting model. It is worth comparing SPBL with the above methods to verify its effectiveness by learning a classifier in a joint boosting and self-paced manner.

4.1 Dataset Description

Three real-world image datasets are used. We choose the image data for experiments because the underlying patterns of image features tend to have rich nonlinear correlations. The three datasets are Caltech256 1 , AnimalWithAttributes (AWA) 2 , Corel10k 3 . All of them are publicly available and fully labeled with each sample belonging to only one class. The statistics of the datasets are summarized in Table 2.

1 http://www.vision.caltech.edu/Image Datasets/Caltech256/

2 http://attributes.kyb.tuebingen.mpg.de/

3 http://www.ci.gxnu.edu.cn/cbir/dataset.aspx

Algorithm 1: SPBL for Classification

Input : Training set ¶(xi↪ yi)♦ni=1 ; ⌫ > 0; initial SPL parameters λ0↪ ⇣0 > 0; initial SPL weights v0; λmax; TES; θ > 1; ✏ > 0. Output : A set of k weak classifiers ¶hj (·)♦kj=1 ; W. 1 Initialize: v(0) v0; (λ↪ ⇣) (λ0↪ ⇣0); U v(0)1TC ; 2 t 0; 3 repeat 4 t t + 1; Boosting : 5 Learn a newweak classifier: solve Eq. (12) to obtain ¶ht(·)↪ ˆ r♦ based on U; 6 Update W: solve Eq. (9) for W (t) based on v(t-1) ; 7 Update U: compute U by Eq. (11) based on v(t-1) ; SPL : 8 Update v: compute v(t) by Eq. (8) based onW (t) ; Validation: 9 Test ¶hj (·)♦tj=1 andW (t) on the validation set, to obtain the error rate err(t) ; Annealing: 10 if λ < λmax then 11 λ θλ; ⇣ θ⇣; 12 end 13 until Pi [δˆ ryi (Pl Uil) - Uir] ht (xi) < ⌫ + ✏ or t > TES and err(t) > min 16s6t-1 err(s) ; 14 k argmins err(s) ; Return : ¶hj (·)♦kj=1 , W =W (k) .

We use the spatial pyramid features for Caltech256 and Corel10k extracted based on [Lazebnik et al., 2006], and use the available Decaf feature for AWA. We reduce the dimensions of all the features to 512 by PCA.

4.2 Experimental Settings

For a convenience of optimization, we first extend the output of a weak classifier h(·) to real value [0↪ 1]. We assume a logistic linear form for h (·):

We adopt the strategy in [Jiang et al., 2014b] for the annealing of the SPL parameters (λ↪ ⇣) (Line 10 to 12 in Algorithm 1). Specifically, at each iteration, we sort the samples in the ascending order of their losses, and set (λ↪ ⇣) based on the number of samples to be selected by now. Instead of annealing the absolute values of (λ↪ ⇣), we anneal the proportion of the number of selected samples. It is shown in [Jiang et al., 2014b] that such annealing scheme is more stable.

We implement a grid search for the tuning of the hyperparameter ⌫. Further, in order to test the robustness of our model, we manually add label noise into the training set by randomly selecting and relabeling s% of the training samples with the other labels different from the true ones. We conduct experiments with s 2 ¶0↪ 5↪ 10↪ 15♦ for the three datasets.

4.3 Experimental Results

Table 1 shows the error rate performance of SPBL and the comparative methods on the three datasets, with different proportions of noisy samples. The best results are shown in bold face. To give a concise demonstration of the performances, we show in Figure 3 the error rates for three datasets w.r.t. the noise ratio. We see that SPBL has a better overall performance than the comparative methods.

Figure 3 further shows that the performances of boosting methods (MultiBoost, AdaBoost) are sensitive to the noisy data, and that the comparative methods embedded with SPL (SR-S, MultiSVM-S) are more robust than their original counterparts. It is expected, since the suppression effect to noise of a comparative method stems from the self-paced learning scheme. By effectively utilizing the complementarity of boosting and SPL, the proposed SPBL demonstrates a stable performance improvement over the SPL-embedded methods, and an increasing performance improvement over the other comparative methods.

Further, we show in Figure 4 the change of the error rates on the training set and the test set w.r.t. the learning iterations of SPBL and MultiBoost, for s = 0. We see that the test and training error rate curves of SPBL are generally in between the corresponding curves of MultiBoost. Therefore, Figure 4 shows that SPBL relieves the overfitting problem of boosting methods, since it has a smaller gap between the training errors and the test errors. This is due to the smooth learning pace of SPBL based on a self-paced boosting optimization from easy samples to hard ones, instead of learning from the whole data batch as MultiBoost does. Through this, SPBL guides the model to focus on the samples not only insufficiently learned, but also with high confidence of reliability, and thus relieves the overfitting and obtains a better generalization performance.

5 Conclusions

In this work, we propose a unified learning framework, SelfPaced Boost Learning (SPBL), that learns in a joint manner from weak models to a strong model and from easy samples to complex ones, for both effective learning and robust learning. With an adaptive pace from easy to hard in boosting optimization, SPBL asymptotically guides the model to focus on the samples not only insufficiently learned but also with high reliability. Through this, SPBL learns a model in both directions of positive encouragement (on reliable samples) and negative suppression (on misclassified samples), and is capable of capturing the intrinsic inter-class discriminative patterns while ensuring the reliability of the samples involved in learning. To the best of our knowledge, this is the first work that reveals and utilizes the association of boosting and SPL to simultaneously enhance the effectiveness and the robustness for supervised learning. We formulate SPBL as a fully corrective optimization for classification task. The experiments on real-world datasets show the superiority of SPBL in terms of both effectiveness and robustness.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant U1509206, Grant 61472353, and Grant 61572431, the National Basic Research Program of China under Grant 2012CB316400 and Grant 2015CB352300, the Fundamental Research Funds for the Central Universities, Zhejiang Provincial Engineering Center on Media Data Cloud Processing and Analysis, and the equipment donation by Nvidia.