Robust Softmax Regression for Multi-class Classification with Self-Paced Learning

1 Introduction

Classification typically involves a supervised learning scenario which studies a model based on the training data samples with known labels and then make predictions on new data (test data). In the past couple of decades, a large number of classification models have been proposed, such as support vector machines (SVM) [Hsu and Lin, 2002], decision tree [Krawczyk et al., 2014], naive Bayes [Farid et al., 2014], neural network [Anand et al., 1993], and so on. Even so, logistic regression (LR) is one of the most widely used methods for binary classification task due to its ease of understanding and implementation, good performance, and high efficiency [Freedman, 2009; Cox, 1958; Walker and Duncan, 1967]. For multi-class classification, LR usually applies the one-vs-all strategy that trains K (the number of classes) binary classification models, each treating the instances in one class as positive and all the other instances as negative. Each model provides a predicted probability of a test data instance and this instance will be assigned to the class that gives the largest probability.

By contract, softmax regression (SR) [Bishop, 2006; Bhning, 1992], also known as multi-class logistic regression, can also be used to solve multi-class classification tasks. In multi-class classification, the classes are usually mutually exclusive. Thus, it is better to use SR instead of building K separate LR models. SR is also less time consuming than LR because SR only needs to train the classification model once. SR has also been widely used in many machine learning applications. However, noisy data and outliers can significantly affect the performances of both LR and SR. To enhance the effectiveness of LR, several robust methods of LR have been proposed recently [Shafieezadeh-Abadeh et al., 2015; Tibshirani and Manning, 2014; Feng et al., 2014]. However, as far as we know, none of work has been done to improve the performance of SR for multi-class classification from the perspective of self-paced learning.

Recently, a new machine learning framework named selfpaced learning (SPL) [Kumar et al., 2010] has attracted a lot of attentions. The idea comes from the fact that people usually learn better when they start with simple knowledge and then gradually consider complex knowledge. To formalize this strategy in machine learning, [Bengio et al., 2009] proposed curriculum learning (CL). After that, [Kumar et al., 2010] proposed SPL to achieve the curriculum designing's goal by adding an SPL regularization term into the objective function. Concretely, SPL trains the classification model on "easy" instances first, and then gradually adds "complex" instances to train. The learning difficulty of an instance (whether the instance is "easy" or "complex") is decided by its loss according to the current parameter value. It has been empirically demonstrated that SPL has the ability of avoiding bad local minima and thus has better generalization ability [Kumar et al., 2010; 2011; Jiang et al., 2015; Tang et al., 2012]. Therefore, SPL is typically used to find better solutions for non-convex problems where multiple local minima exist.

Since SR solves a convex optimization problem and can find a global optimum, applying the original SPL model to SR will obtain the same solution as SR. Lately, several variations of SPL were developed to not only select samples to train but also assign a weight to each selected sample. The key step is to apply the soft weighting scheme instead of the hard one in the traditional SPL [Jiang et al., 2014; Zhao et al., 2015; Pi et al., 2016]. In this paper, we utilize such soft weighting technique of SPL to evaluate the importance of each data sample and propose robust softmax regression (RoSR), in which each data sample participates in the training process according to its weight. Typically, noisy data and outliers obtain small weights and their influence will be significantly reduced.

Moreover, in each iteration of SPL, the weights of data instances are determined by those loss values and a global controlling parameter, this might cause that data points of some classes obtain relatively small weights. Hence, these classes have smaller influence than others in the training process and the learned model parameter will be biased. To alleviate this, we propose two novel soft weighting schemes to evaluate weights of data instances locally for each class. This ensures that none of the classes is ignored in the training process and the resulting method is abbreviated to RoSR-L ("L" denotes "Locally").

The main contributions of this work are summarized as follows:

1. To the best of our knowledge, this is the first work to incorporate soft weighting of SPL into softmax regression. The proposed RoSR can significantly reduce the negative influence of noisy data and outliers.
2. ii) Two soft weighting schemes are developed. The proposed RoSR-L can avoid the situation that some classes are neglected in training and can further improve the performance of RoSR. The methods and experience presented in this paper can be easily used for other classification methods.
3. iii) Experiments on simulated data show how RoSR and RoSR-L work and extensive experiments on real data are concluded to demonstrate their effectiveness.

2 RelatedWork

[Kumar et al., 2010] proposed SPL to formulated the curriculum learning's idea as an optimization model by adding a regularization term. SPL learns easy samples first, and then add more samples to training by gradually increasing the controlling parameter. Then, an SPL strategy for the specific-class segmentation task was developed in [Kumar et al., 2011]. [Lee and Grauman, 2011] developed a self-paced discovery framework for visual category discovery tasks. [Tang et al., 2012] formulated a self-paced domain adaptation approach by training target domain knowledge starting with easy samples in the source domain. [Supan ˇCi ˇC and Ramanan, 2013] designed an SPL method for long term tracking by setting smallest increase in the SVM objective as the loss function. [Jiang et al., 2014] discovered that pseudo relevance feedback is a type of self-paced learning which explains the rationale of this iterative algorithm starting from the easy examples. [Jiang et al., 2015] proposed self-paced curriculum leaning (SPCL), which makes use of prior knowledge in SPL. [Ren et al., 2017] made use of SPL to solve the non-convex problem caused by feature corruption techniques. Traditional SPL methods usually use the hard weighting method, while some work [Jiang et al., 2014; Zhao et al., 2015; Pi et al., 2016] has been done to apply soft weighting schemes. However, all of these existing soft weighting schemes do not consider the difference among the classes and may suffer from the imbalanced class influence problem.

There exists several robust methods of LR have been proposed. Concretely, a distributionally robust method to LR has been developed in [Shafieezadeh-Abadeh et al., 2015]. [Tibshirani and Manning, 2014] presented a novel robust LR approach which adds a term reflecting the possibility of mislabelling in the objective function. [Feng et al., 2014] proposed a robust extension of LR which considers LR with arbitrary outliers in the covariate matrix. To illustrate the influence of robustness, [Feng et al., 2016] proposed robust support vector classifiers (RSVC) for classification problems. Similar with our work, RSVC also tries to reduce the negative influence of noisy data from a weighted viewpoint. The difference is that RSVC aims at solving binary classification problems and the idea of weighting scheme comes from M-estimation in statistic, while our work targets for multi-class classification problems and evaluates the weights of data points via SPL technology.

Although a large amount of work has been presented to address the robustness problem in the presence of noisy data and outliers in binary classification tasks, e.g., LR and support vector machine, none of work has been done to refine SR for multi-class classification from the view of SPL. This work fills the gap by applying the soft weighting scheme of SPL into SR and develops RoSR. Two novel soft weighting scenarios are also developed to further enhance the performance of RoSR.

3 Preliminaries

Let X = {(x(1) , y(1) ), . . . , (x(n) , y(n) )} be the data set where x(i) ∈ Rd is the i-th instance, and y(i) ∈ {1, . . . ,K} represents its label where K ≥ 2 is the number of classes. x(i) j is the j-th feature of sample x(i) 1 . The cost between the ground truth label y(i) and the estimated label g(x(i) , θ) is computed by loss function L(y(i) , g(x(i) ; θ)) ≥ 0 (abbreviated to li). θ is the model parameter.

3.1 Self-Paced Learning

The goal of self-paced learning (SPL) is to jointly learn θ and the latent weight variable v = [v1, . . . , vn]T by minimizing:

When fix v, Eq. (1) is a traditional classification problem. When fix θ, the solution of v depends on the definition of the SPL regularization term f(λ, v) and the range of values of v. [Kumar et al., 2010] lets v ∈ {0, 1}n and defines f(λ, v) as

1 The intercept term 1 is added for every instance. Hence, x(i) 1 = 1, ∀i = 1, . . . , n.

The optimal v∗ can be calculated by

Since vi (i = 1, . . . , n) should be equal to either 1 or 0, this method introduced in [Kumar et al., 2010] is considered as hard weighting. λ > 0 is initially set to a small value, then only those samples with small loss values are selected to train. As λ grows iteratively, more samples will be added until all the samples are chosen.

3.2 Softmax Regression

Let 1{·} be the indicator function, so that 1{a true statement} = 1, and 1{a false statement} = 0. Then the cost function of softmax regression [Bishop, 2006; Bhning, 1992] is

where the loss function of x(i) is defined as below:

The regularization term is

and µ is the coefficient. Note that θk denotes the parameter vector of the k-th class and θkj is the j-th item of θk. As is well-known, SR is a convex model which can find a global optimal solution.

4 Robust Softmax Regression

4.1 ProblemFormulation

As mentioned before, the performance of SR is sensitive to the presence of noisy data and outliers. This will be empirically verified later in this paper. To address this, in this work, we introduce Robust Softmax Regression (RoSR) model whose main idea is to make use of soft weighting of SPL. The resulting model is actually a weighted version of SR. The common optimization model of RoSR is defined as follows:

where v ∈ [0, 1]n evaluates the weights of data instances, µ is the regularization coefficient, li and r(θ) are defined in Eqs. (5) and (6), respectively. If f(λ, v) is defined by Eq. (2), then vi is either 1 or 0. Then, the optimal solution of Eq. (7) is the same as that of SR. The reason is that once all the data instances are selected, vi = 1 (∀i = 1, . . . , n) and f(λ, v) is a constant. Thus, the solution of Eq. (7) is the same as minimizing Eq. (4), since both of them can find a global optimum. Thus, in order to make Eq. (7) a weighted version of SR (i.e., let vi ∈ [0, 1]), we should use some other definitions of f(λ, v).

4.2 Optimization

We use the alternative search strategy to solve Eq. (7). Concretely, we iteratively optimize one of the two parameters θ and v while keeping the other one fixed. The main task contains the following two steps.

Step 1: Fix θ, update v. With the fixed θ, li and µr(θ) in Eq. (7) are constant terms. Then, the weight vector v can be updated by solving:

RoSR In [Jiang et al., 2014; Zhao et al., 2015; Pi et al., 2016], vi is allowed to take any value in [0, 1]. The corresponding methods are considered as soft weighting. Here, we use two types of soft weighting methods (i.e., liner weighting and mixture weighting [Jiang et al., 2014]) in RoSR. The experimental results will show that different soft weighting methods perform comparably with each other. The definition of f(λ, v) and the corresponding optimal v∗ of linear weighting [Jiang et al., 2014] are given in Eqs. (9) and (10), respectively.

[Jiang et al., 2014] defines f(λ, v) of mixture weighting as

where an extra SPL parameter ζ > 0 is introduced in addition to λ. Then, the corresponding optimal v∗ is given by [Jiang et al., 2014]:

For simplicity, we do not tune the parameter ζ and always set ζ = 0.5 × λ no matter which value of λ is taken. Eqs. (10) and (12) tell us that points with small loss values are assigned with large weights. Noisy data points and outliers, and those points locate in the overlapped regions among the classes, typically have large loss values and will gain small weights. In this way, their influence is significantly reduced.

RoSR-L We can observe from Eqs. (10) and (12) that RoSR chooses instances based on their loss values and a global λ. This may suffer from the imbalanced class influence problem. Concretely, in a certain iteration, the situation probably happens that instances from some classes obtain small loss values and will obtain higher weights. Then, these instances will have more influence in learning the model parameter θ. By contract, most instances from some other classes might have relatively large loss values and will obtain lower weights (even equal to 0). A a result, these classes contribute little in learning θ. If so, the learned θ is heavily biased and will bring negative influence for the following training process.

To alleviate this, we consider assigning weights and selecting instances locally from each class. To this end, we set controlling parameters λk for the k-th class and define two novel SPL regularization terms, shown in Eqs. (13) and (17), respectively. The resulting method is named RoSR-L ("L" means "Locally").

The first regularization term proposed here is

where Sk denotes the set of indices of data points in the k-th class. If x(i) belongs to the t-th class, then the optimal v∗ i is given by

Eq. (14) is similar with Eq. (10) and is also considered as linear weighting. λk controls the weights of instances and the number of selected instances in the k-th class. The proof of Eq. (14) is given by Theorem 1.

Theorem 1. If f(λ, v) is defined by Eq. (13), the optimal v∗ is given by Eq. (14).

Proof. Substituting Eq. (13) in Eq. (8), we obtain

By setting the partial derivative of the cost function in Eq. (15) w.r.t. vi to 0 and suppose x(i) belongs to the t-th class, we have

Then, we can easily obtain the optimal v∗ i = - li λt +1. Recall that vi ∈ [0, 1] and li ≥ 0, we can obtain that the optimal v∗ can be calculated by Eq. (14).

The second proposed regularization term is defined as

The optimal v∗ is computed by (suppose xi is a member of the t-th class)

For simplicity and fair comparison, we always set ζk = 0.5× λk in our experiments. Eq. (18) is similar with Eq. (12) and is considered as mixture weighting. The proof of (18) is shown in Theorem 2.

Theorem 2. If f(λ, v) is defined by Eq. (17), the optimal v∗ is given by Eq. (18).

Proof. Similarly with Theorem 1, we substitute Eq. (17) in Eq. (8) and set the partial derivative of the corresponding cost function w.r.t. vi to 0. Then, we have

proved that xi belongs to the t-th class. Then, it can be easily obtained that the optimal v∗ i = ζt/li -ζt/λt. Note again that vi ∈ [0, 1] and li ≥ 0, we can find that the optimal v∗ is given by Eq. (18).

Step 2: Fix v, update θ. When v is fixed, f(λ, v) in Eq. (7) is a constant and we can update θ by solving:

Eq. (20) is actually a weighted version of Eq. (4). We use gradient-descent method [Amari et al., 1996] to solve Eq. (20). Then, θk (k = 1, . . . ,K) is iteratively updated by:

where ∇θk li and ∇θk r(θ) can be easily observed. α is the learning rate. The iteration stops when it converges or reaches the maximum number of iterations, which is set to 250 in our experiments. The L-BFGS method 2 is used for this optimization.

Step 1 and step 2 are iteratively implemented. In each iteration, we increase λk to select more samples to train. In the model, we set λk (k = 1, . . . ,K) such that half the instances (whose weights are bigger than 0) from the k-th class are selected in the first iteration. Then, in every following iteration, we increase λk to add 10% more instances from the k-th class. As a consequence, λk (k = 1, . . . ,K) are automatically determined and µ is the only parameter in Eq. (7). Our model stops when all the instances are chosen. Then, the corresponding learned θ and v are the final model parameter and weight vector, respectively.

5 Experiments

5.1 Experimental Setup

We first conduct experiments on toy examples to show how the proposed methods work. The original toy example (which is shown in Fig. 1 (a)) consists of 3 classes, each providing 150 data points. Thirteen real data sets from different sources are tested in our experiments. The characteristics of these data sets are shown in Table 1. 10digits collects instances for digits 0-9, and each instance is represented by a 28*28 image. CinC (CinC ECG torso) is a UCR time series data set 3 . IJCNN1, Seismic, and Vowel are available at https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/. Prostate is a gene expression data set 4 . Balance (Balance Scale), Biodeg (QSAR biodegradation), Haberman (Haberman's Survival), Letter (Letter Recognition), Musk1 (MuskVersion 1), Skin (Skin Segmentation), and Spambase are all UCI data sets 5 . For each data set, each feature is normalized to have zero mean value and unit variance.

2 http://www.cs.ubc.ca/∼schmidtm/Software/minFunc.html

3 www.cs.ucr.edu/∼eamonn/time series data/

4 http://stat.ethz.ch/∼dettling/bagboost.html

The following six methods are tested in our experiments:

• LR: Logistic regression with L2 norm.
• SR: Softmax regression [Bhning, 1992].
• RoSR-Lin: RoSR with linear soft weighting.
• RoSR-Mix: RoSR with mixture weighting.
• RoSR-L-Lin: RoSR-L with linear soft weighting.
• RoSR-L-Mix: RoSR-L with mixture weighting.

5 http://archive.ics.uci.edu/ml/index.html

For RoSR and RoSR-L methods, we first run SR on the whole training data set for 5 iterations to obtain an initialization of the model parameter θ. Actually, each of the six comparing methods has only one regularization coefficient µ needed to be tuned. We tune µ for each method on each data set, where µ ∈{1e-5, 3e-5, 1e-4, 3e-4, 1e-3, 3e-3, 1e-2, 3e-2, 0.1, 0.3, 1}. For each method, we perform a 10-fold cross validation on each data set ten times and report the average results. We utilize t-test to assess the statistical significance of the results at 5% significance level.

5.2 Results on Toy Examples

Fig. 1(a)-(c) show the three versions of the simulated data set, i.e., the original toy example, the toy example with fifteen noisy data points (those points locate in the area of the cyan "∗" class but are labeled as the magenta "△" class), and the toy example with five outliers (the top five points labeld as the magenta "△" class), respectively. In this subsection, the regularization coefficient µ is always set to 1e-3. We train SR on the three data sets and report the corresponding results. Take Fig. 1(a) as example, we obtain three learned model parameter vectors θi ∈ R3 , i = 1, 2, 3 by SR. Then, we plot θTi x = 0 (note that x = [1, x1, x2] in this case) using a dashed line. The dashed line with a specified color corresponds to the class with the same color. We can observe from Fig. 1(a) that SR works well on the original simulated data set because the three classes are well separated and none of noisy points and outliers exists. However, as shown in Fig. 1(b)-(c), the learned parameters shift a lot when only a small number of noisy data points or outliers exist, indicating the performance of SR is easily affected by noisy data or outliers.

The results of RoSR-Mix and RoSR-L-Mix on toy examples are shown in Figs. 2 and 3, respectively. As expected, Figs. 2 and 3 show that RoSR-Mix and RoSR-L-Mix perform much better than SR in the presence of noisy data and outliers. In Fig. 2, the data points whose weight values assigned by RoSR-Mix are less than 1 are highlighted with squares. It is interesting that all the noisy data and outliers are found. In this manner, the proposed RoSR can also be used for anomaly and mislabelled data detection. Similarly, we highlight those points whose weights are less than 1 with squares in Fig. 3. We can find that more points are highlighted by RoSR-L-Mix than RoSR-Mix. This exactly show the different behaviors between RoSR-L-Mix and RoSR-Mix. RoSR-Mix assigns weights to instances based on their weights globally, while RoSR-L-Mix does this locally for each class, leading to that some points in every class are assigned with lower weights by RoSR-L-Mix. Thus, besides noisy data and outliers, those points in overlapping regions among the classes also play smaller role in the learning process of RoSR-L.

Both RoSR-Mix and RoSR-L-Mix work well on the original toy example. Similar results can also be obtained when applying RoSR and RoSR-L with linear weighting scheme. The corresponding results are not reported due to limited space.

5.3 Results on Real Data Sets

In this subsection, we evaluate the performances of all the comparing classification methods. Table 2 gives the results. In each row, we highlight the best and comparable results in boldface. The first observation from Table 2 is that SR performs comparably with LR on those data sets with only two classes. Besides, SR always achieves higher accuracies than LR. Especially, SR improves upon LR upon by a large margin on 10digits, Balance, Letter, and Vowel. We also find that SR is much faster than LR (the results are not reported due to space limitation) for K-class classification (K ≥ 3) tasks.

Another observation is that RoSR-Lin and RoSR-Mix always achieve higher accuracies than SR on all the data sets except for Balance, IJCNN1, Prostate, and Skin. This demonstrates the effectiveness of applying SPL with soft weighting schemes in SR. On Prostate, RoSR-Lin performs comparably with SR, while the accuracy achieved by RoSR-Mix is slightly larger than that achieved by SR. Both RoSR-Lin and RoSR-Mix lose to SR on Balance, IJCNN1, and Skin. The main reason is that some classes might be neglected in certain iterations of SPL.

Finally, we can see from Table 2 that RoSR-L-Lin and RoSR-L-Mix perform the best in most cases. The reason for this is two-fold: 1) The RoSR-L methods can significantly reduce the negative influence caused by noisy data and outliers. 2) The SPL strategy that chooses instances to train separately for each class guarantee that all the classes participate in the training process and none of them is neglected in each iteration of SPL.

6 Conclusion and FutureWork

In this work we propose robust softmax regression (RoSR) for multi-class classification. RoSR makes use of the soft weighting scheme of self-paced learning to evaluate the importance of each data sample. It can perform well in the presence of noisy data and outliers. Moreover, to alleviate the imbalanced class influence problem, we propose RoSR-L which estimates the weights and selects data samples locally for each class to further enhance the performance of RoSR. Correspondingly, two novel soft weighting schemes are developed. The effectiveness of the proposed methods is demonstrated by experimental results on both synthetic and real data. We are interested in extending the framework proposed in this paper to other machine learning methods in our future work, e.g., kernel methods and neural networks.

Acknowledgments

This paper was in part supported by Grants from the Natural Science Foundation of China (No. 61572111), the National High Technology Research and Development Program of China (863 Program) (No. 2015AA015408), a Project funded by China Postdoctoral Science Foundation (No. 2016M602674), a 985 Project of UESTC (No. A1098531023601041), and two Fundamental Research Funds for the Central Universities of China (Nos. ZYGX2016J078 and ZYGX2016Z003).