Title: SEMI-SUPERVISED BOOSTING VIA SELF LABELLING

Abstract: Attention to semi-supervised learning grows in machine learning as the price to expertly label data increases. Like most previous works in the area, we focus on improving an algorithm's ability to discover the inherent property of the entire dataset from a few expertly labelled samples. In this paper we introduce Boosting via Self Labelling (BSL), a solution to semi-supervised boosting when there is only limited access to labelled instances. Our goal is to learn a classifier that is trained on a data set that is generated by combining the generalization of different algorithms which have been trained with a limited amount of supervised training samples. Our method builds upon a combination of several different components. First, an inference aided ensemble algorithm developed on a set of weak classifiers will offer the initial noisy labels. Second, an agreement based estimation approach will return the average error rates of the noisy labels. Third and finally, a noiseresistant boosting algorithm will train over the noisy labels and their error rates to describe the underlying structure as closely as possible. We provide both analytical justifications and experimental results to back the performance of our model. Based on several benchmark datasets, our results demonstrate that BSL is able to outperform state-of-the-art semi-supervised methods consistently, achieving over 90% test accuracy with only 10% of the data being labelled.

1. INTRODUCTION:

The rise of the Internet has made it easy to collect massive amounts of data to perform machine learning tasks. However, providing quality labels to each of the samples collected within these large datasets is a long and expensive process. There is a rich literature aiming to alleviate this issue, including using techniques from unsupervised machine learning and crowdsourcing. In this paper, we approach the problem by combining concepts from crowdsourcing, learning with noisy data and boosting to propose a novel framework: Boosting via Self Labelling (BSL).

Our aim is to develop and leverage i) machine learning and estimation approaches to create selflabels for unlabelled instances, and ii) a noise-resistant learning procedure to speed up the performance of the seminal AdaBoost algorithm. The framework consists of mainly three steps:

1. Accurately predict labels for the unlabelled part of the data using a set of supervised classifiers trained upon a small labelled dataset. Each classifier in our set is analogous to an agent in a crowdsourcing setting. As a result, an inference method can be used to aggregate each of the classifiers predictions and output an accurate noisy label for each of the unlabelled data points.

2. The second step aims to estimate the noise rate of the generated noisy labels by checking how often the noisy labels generated in step 1 would agree with a particular classifier. This second order statistic suffices to return us the error rates.

3. The third step of our approach looks at producing a robust boosting method that is trained over the generated noisy data. Classically AdaBoost does not perform well under noisy data compounding errors for each point and progressively creating a worse classifier. The third step introduces a noise resistant version of AdaBoost which relies on the noise and error rate estimated in step 2. This results in a final classifier which can be compared against different semi-supervised algorithms.

BSL builds upon mainly two lines of similar works on boosting without cleanly labelled data:

1. Semi-supervised boosting (Fujino et al., 2005; Blum & Mitchell, 1998; Laine & Aila, 2016; Grandvalet & Bengio, 2005) uses semi-supervised algorithms (e.g., clustering) to generate ar-tificial or proxy labels and boost accordingly (which we compare with). Existing methods that apply self-generated labels directly to boosting will fail as the noises in the labels will accumulate while boosting, especially when the noise rates are high -this is what we observed in our experiment results. Our idea is a couple of steps further: we introduce a bias correction procedure into boosting, and explicitly estimate the noises in generated labels. We also introduced an inference framework for generating these labels at first place.

2. Noise resistant boosting (Bootkrajang & Kabán, 2013) addresses boosting algorithms which are susceptible to noisy data and proposing variants which can perform under a certain noisy conditions. A set of noisy labels, as well as the knowledge of the noises, are often assumed to be known. We do not require neither -we will self-generate the labels for unlabelled instances and learn their error rates.

Our contributions summarize as follows:

1. We propose a novel self-labelling boosting algorithm (BSL) which is able to outperform present state-of-the-art semi-supervised algorithms.

2. As two key components of our self-labelling framework, we contribute i) a new formulation of a noise resistant Adaboost algorithm which corrects the noises in the labels -this is important in a boosting process, because otherwise the label noises will accurate while boosting; ii) a label error estimation procedure without accessing the ground truth labels.

3. We offer both theoretical guarantees, as well as experimental evidence to the performance of our framework. We conducted an extensive set of experiments to verify the effectiveness of BSL. In the different datasets we ran our algorithm on, our method consistently outperforms many other algorithms by more than 20%. In the cancer dataset when 10% of the data was labelled, the second best algorithm (Semiboost) under performed our algorithm by 66% (relative performance). Theoretically we are able to show the convergence of our noise-resistant AdaBoost subroutine under symmetric error rate assumption.

The rest of the paper organizes as follows. We survey the most relevant work in the rest of the section. Preliminaries are introduced in Section 2. Section 3 presents a noise-resistant AdaBoost algorithm. Our Boosting via Self Labelling framework is introduced in Section 4. Section 5 presents our experiment results. Section 6 concludes our paper. All missing details can be found in Appendix.

1.1. RELATED WORKS:

Our work has been inspired by three different lines of research:

Semi-Supervised Learning: Research in this avenue looked at creating accurate labels in the presence of limited labelled data. Work started with some basic algorithms (Cortes & Vapnik, 1995; Fujino et al., 2005; Demiriz et al., 1999; Blum & Mitchell, 1998) , but escalated to complex systems (Lee; Miyato et al., 2018; Laine & Aila, 2016; Grandvalet & Bengio, 2005) . A good survey in this area was done by Zhu (Zhu, 2005) .

Crowdsourcing: Inference crowdsourcing methods have played a huge part in uncovering true labels from multiple noisy labels. Work in the area has ranged from EM algorithms (Dawid & Skene, 1979; Raykar et al., 2010; Smyth et al., 1995; Karger et al., 2011) to variational inference methods (Liu et al., 2012; Karger et al., 2014; Whitehill et al., 2009; Welinder et al., 2010; Raykar & Yu, 2012) . (Chon et al., 2012) wrote a good survey for this topic. In an ensemble setting, crowdsourcing has appeared in numerous works include, most famously, (Kim & Ghahramani, 2012) . However, many of these results do not consider the noise present in the final aggregated value, which can lead to accumulated errors in a boosting setting.

Boosting: Starting with the work (Freund & Schapire, 1999) , research in AdaBoost has expanded to all areas of machine learning. Some of the recent work in the area has looked into improving the performance and pitfalls the original algorithm faced (Rätsch et al., 2001; Hastie et al., 2009; Domingo et al., 2000; Schapire, 2013; Bootkrajang & Kabán, 2013) .

Our work builds upon previous work done in these areas, using similar ideas to construct a unique method. One notable piece of work is Semiboost (Zhu, 2005) . This algorithm takes a similar approach, introducing a boosting framework that improves upon existing classifiers to provide a good classifier in the semi-labelled setting. However, Semiboost uses an unsupervised learning approach using a similarity matrix based on labelled points and unlabelled points. Semiboost requires a similarity equation to run, and this can be hard to achieve in practice. Pseudo-labelling is one of many neural network approaches to the limited labelled dataset problem. Pseudo-labelling assigns labels to the unlabelled data and then trains a neural network on the combination of the clean and noisy labels. However, Pseudo-labelling and algorithms like it, face many different requirements. Algorithms in this class require a sufficient amount of supervised data to work optimally. They also need the classes to be clustered within the data, and the labelled data to not adhere to the same distribution as the unlabelled data (Oliver et al., 2018) . Learning in noisy data has also been a research focus that runs parallel to our work. In (Natarajan et al., 2013) , Natarajan et al. propose a noisy learning algorithm which performs significantly better than other noise resistant algorithms. However, the method requires knowledge on the amount of noise inside of the dataset before training and in a limited label dataset, which is hard to get in practice. In contrast to these related works, the algorithm we introduce in this paper does not need prior knowledge about the dataset for it to perform and the number of labelled points does not adversely affect the accuracy of the classifier generated.

2. PRELIMINARY AND PROBLEM FORMULATION:

Assume that D is the underlying true distribution generating n iid examples (x i , y i ) n i=1 , where each example consists of a feature vector

x i = [x i,1 , x i,2 , . . . , x i,d ] ∈ X ⊆ R d ,

and a label y i ∈ {-1, +1} (∼ Y ). We assume the true labels of τ examples is available where τ < n such that

(x i , y i ) τ i=1 , denoted as {(x 1 , y 1 ), (x 2 , y 2 ), • • • , (x |N L | , y |N L | )} := N L ; while the rest of n -τ samples (x i ) n i=τ is unlabelled, {x 1 , x 2 , • • • , x |N U | } := N U .

Let N U and N L be the set of indices that make up N U and N L respectively.

Assume that after an initial classifier f : X → {-1, +1} is trained on N L and applied on the unlabelled dataset such that f

(x i ) → ỹi , x i ∈ N U . Then N Unoisy denotes the noisy data set pro- duced (x i , ỹi ) |N U | i=1 . Let N noisy be the combination of N L and N Unoisy such that for i = 1 to |N noisy |: {(x i , ỹi ), if (x i , ỹi ) ∈ N Unoisy ; (x i , y i ), if (x i , y i ) ∈ N L }.

Let N noisy be the set of all indices within N noisy . Assume that N noisy follows as class-conditional random noise model such that: ∀n = 1, 2, ..., |N noisy |:

P( ỹi = -1|y i = +1, x n ) = ρ + , P( ỹi = +1|y i = -1, x n ) = ρ -and ρ + + ρ -< 1. Our goal is to learn a classifier f : X → {-1, +1} trained on N noisy that minimizes the risk of f w.r.t to the 0-1 loss function R D (f ) = E (xi,yi)∼D [1(f (x i ) = y i )].

2.1. OUR PROBLEM: BOOSTING VIA SELF LABELLING:

We introduce the setting for AdaBoost (Freund & Schapire, 1999) . The key idea is, at step t,

• Maintain a weight D i (t) for each data instance (x i , y i ) ∈ N L .

• Train a weak learner f t according to the weighted data distribution.

• The final hypothesis F is a linear combination of each f t trained at every step t.

Let N miss be the set of all (x i , y i ) ∈ N L , such that f t (x i ) = y i . The goal is to increase the weight of mis-classified points D i (t), (x i , y i ) ∈ N miss to encourage classifier f t+1 (•) to focus on correctly classifying N miss :

D t (i + 1) = D t (i) • exp -α t • f t (x i ) • y i Z t ,

where

Z t = i∈N L D t (i) • exp -α t • f t (x i ) • y i is a normalization factor. AdaBoost creates a final hypothesis in the additive form: F (x i ) = T t=1 α t f t (x i )

, where x i is a test sample. Our goal, and a short coming with AdaBoost, is classifying a dataset where some of the y i in (x i , y i ) ∈ N noisy are noisy. Because AdaBoost uses a exponential loss function it is inherently susceptible to noisy labels. We propose a new loss function that removes bias:

D t+1 (i) = D t (i) • exp -α t • ˜ (x i , ỹi ) Z t , ∀i ∈ N noisy

Our goal is to define a function ˜ (•) that can help us evaluate an unlabelled instance. This function ˜ (•) will allow us to adjust to noisy labels within N noisy . Our algorithm runs in two main stages. It first applies noisy labels for unlabelled instances in our dataset, and then creates a final hypothesis F using a noise-resistant variant of AdaBoost where we define ˜ (•) .

3. NOISE-RESISTANT ADABOOST:

We first extend a learning with noisy data approach to the boosting setting, following the work in (Natarajan et al., 2013) . Suppose the examples have the following homogeneous error rates:

ρ + := P xi (ỹ i = -1|y i = +1

), ρ -:= P xi (ỹ i = +1|y i = -1) Suppose we know these error rates in this section. Boosting over the above noisy examples will lead to a biased training process when the label noises are sufficiently large. Our approach is a straightforward adaptation from a noise correction mechanism adopted in supervised learning (Natarajan et al., 2013) : defining surrogate loss function ˜ on noisy labels (for an arbitrary loss function )

EQUATION

EQUATION

A nice property of above estimator is its unbiasedness (Natarajan et al., 2013) :

E ỹi|yi [ ˜ (f (x i ), ỹi )] = (f (x i ), y i ).

We adapt this idea to AdaBoost. Replace (•) with the following loss measure as adopted in AdaBoost:

EQUATION

and ˆ t := max{ˆ + t , ˆ - t } and the following α t s

EQUATION

Then update D i (t) as follows:

D i (t + 1) := D i (t) • exp -α sign(ỹi) t ˜ (f (x i ), ỹi ) Z t (5)

where Z t is again the normalization factor. The reason that we need to define two learning rate α t s is because the losses are weighted differently for the noisy labels. and ω := max{ω + , ω -},

γ t := 1 2 -ˆ t , and (δ, n, ρ + , ρ -) := ω • n ln 2 δ 2 .

Since we have defined two α t s on the training data based on the noisy labels, we define α t :=

α + t +α - t 2

, and let the final output classifier be F (x) = sign T t=1 αtft(x) T > 0 . We prove the following performance guarantee when ρ + = ρ -:

Theorem 1 With probability at least 1 -δ, i∈Nnoisy 1(F (x i ) = y i ) ≤ exp -2 T t=1 γ 2 t + (δ, N, ρ + , ρ -).

Though our above results are proved under the symmetric error setting, we experimentally verified the performance of our error-resistant boosting procedure.

4. A SELF LABELLING FRAMEWORK FOR BOOSTING:

We now introduce our Self Labelling framework for boosting. The framework can be broken into two major components: the noisy label generation and the noisy Adaboost algorithm. Section 3 already described the formation and proof of the noisy Adaboost algorithm. In the next two sections go into detail over i) the inference method to generate noisy label and ii) the procedure to estimating the noise levels within the generated labels as inputs into the Adaboost algorithm. More specifically, Section 4.1 delves deeper into detailing the processes of noisy label generation particularly addressesing matrix L and the aggregation inside of L that forms the noisy dataset. While Section 4.2 explores how the noise levels within the dataset (ρ -,ρ + ) is calculated and used as inputs to the noisy Adaboost algorithm.

Algorithm 1 Boosting via Self Labelling 1: Input: Labelled Data N L , unlabelled Data N U 2: Output: Final Hypothesis F (x)

3: For i = 1, • • • , M : • Train f i on (x i , y i ) ∈ N L • Get hypothesis h t = f i (x i ) → {-1, +1} |N U | , ∀x i ∈ N U

• Add h t to matrix L 4: Run inference method to generate noisy labels for N U : I(L) → {-1, +1} |N U | . Denote the noisy dataset as N Unoisy . Let N noisy = N L ∪ N Unoisy . 5: Estimate (ρ + , ρ -) using Eqn. (6, 7). 6: Initialize:

D i (1) = 1/N for i ∈ N noisy 7: for t = 1, • • • , T :

• Train weak classifier g t on data distribution D(t)

• Get weak hypothesis h t :=g t (x, i), (x i , ỹi ) ∈ N noisy → {-1, +1}

• Get weighted error + , -using Eqn.

(3)

• Calculate ω + , ω -and α + t , α - t (Eqn.( 4)), using estimated ρ+ , ρ-.

• Compute α t := α + t +α - t 2 .

• For i ∈ N U : Update weight D i (t + 1) according to Eqn.(5). Else for i ∈ N L , update weight D i (t + 1) according to Eqn.( 5) with ρ + = ρ -= 0. 8: Final Hypothesis: 

EQUATION

}; ∀i ∈ N U for each f j (•) s.t. L i,j = f j (x i ) = ỹi,j . Assuming f j (•) = f k (•); ∀j, k ∈ M s.t. j = k each f j (•)

will learn a different distribution. This will allow for a variation that gives a better prediction on the underlying structure of N U allowing for some f j (•) to be closer to capturing the true underlying distribution of N U compared to others. Assigning weight q j to each f j (•) according to its perceived accuracy in respect to other classifiers allows for a more accurate aggregation of all f j (•) responses. More formally, in step 4 in Algorithm 1, for each of the M classifiers {f 1 (•), f 2 (•), . . . , f M (•)}, I (variational inference method) assigns an optimal weight {q 1 , q 2 , . . . , q M } such that taking the aggregation of each classifiers prediction for point x i ∈ N U against its respective weight q j will result in a value ỹi that will be as close as possible to the unknown true label y i . The set of x i and aggregated ỹi ∀i ∈ N U will form N Unoisy .

Conceptually, I uses q j to classify f j (•) as an expert if q j > 0.5, a spammer if q j ≈ 0.5 or an adversary if q j < 0.5. If f j (•) is designated a spammer then f j (•) is randomly guessing and does not provide any useful prediction. If f j (•) is denoted as an adversary, f j (•) is believed to be "purposely" picking the incorrect label and ỹi,j = f j (x i ). As the number of labelled data gets smaller, the number of spammers and adversaries found in M classifiers increases.

Assuming conditional independence among classifiers I can predict the optimal weight as following: If P(f j (x), f k (x)|y) = P(f j (x)|y)P(f k (x)|y) where j, k ∈ |M|s.t.j = k (treating each classifier as an independent labeler), we can apply inference approaches to aggregate and infer the true label: q = arg max log P(q|L, θ) = log y P(q, y|L, θ)

Expectation maximization can be used to solve for this maximum a posteriori estimator q by treating the true labels y i as the hidden variable. Assuming a Beta(σ, β) distribution, an EM can be formulated as follows:

E Step: µ i (y i ) ∝ j∈Mi qδi,j j (1 -qj ) 1-δi,j M Step: qj = i∈Nj µ i (L i,j ) + σ -1 |N j | + σ + β -2

where δ i,j = I[L i,j = y i ] and ỹi is estimated by ỹi = arg max yi µ i (y i ) given µ i is the estimated likelihood of y i . N j stands for all labels observed by classifier j:

N j = ({f j (x i )}, ∀i ∈ 1 • • • |N U |).

Finally, step 5 of Algorithm 1 shows the noisy dataset (x i , ỹi ), ∀i ∈ N noisy where ỹi is the noisy label provided by the inference algorithm if x i ∈ N U , else ỹi = y i if (x i , y i ) ∈ N L . N noisy then feeds into the Noisy Adaboost Algorithm introduced in Section 3.

4.2. ERROR ESTIMATION:

Let A(.) represent the noise resistant AdaBoost algorithm we introduced in section 3. Let I represent the inference method we will use to aggregate matrix L. Inference method I outputs a noisy labelled data set: N Unoisy = {x i , ỹi }, ∀x i ∈ N U . In order to run A we need to accurately estimate the error rates ρ -, ρ + : ρ -= (ỹ i = +1|y i = -1), ρ + = (ỹ i = -1|y i = +1) within N Unoisy . Assuming homogeneous error rates, we can derive an accurate estimation for the error rates of N Unoisy from the confusion matrices of the the classifiers f j ∈ M.

Denote the false positive and false negative of f j (•) by ρ +,fj and ρ -,fj respectively. The inference algorithm I will output ρ -,fj and ρ +,fj for each f i ∈ M by comparing {x i , f j (x i )} against the aggregated label from the inference algorithm. P(y i = -1) and P(y i = +1) are the marginal distribution of positive and negative labels within the dataset. If P(y i = -1) and P(y i = +1) are known we show the below equation uniquely identify the error rates given any f j ∈ M:

Lemma 1 ρ + , ρ -can be determined by the following set of equations:

ρ + = (ρ -,fj P(ỹ i = 1) -P(y i,fj = ỹi = 1)

EQUATION

ρ -= -P(ỹ i = 1)(1 -ρ +,fj ) + P(y i,fj = ỹi = 1) -P(y i = +1)(1 -ρ +,fj ) + P(y i = -1)(ρ -,fj )

In practice we can balance the dataset to make P(y i = -1) = P(y i = +1) = 0.5. The probability terms P(ỹ i = 1) and P(y i,fj = ỹi = 1)n can be estimated through the data. The estimated parameters are plugged into Eqn.(6,7) to approximate ρ+ , ρ-. Note this estimation is done without using ground truth labels.

5. EXPERIMENTAL RESULTS:

The focus of BSL is to provide a framework which can generate an accurate classifier given very little labelled data. In this section, we conduct extensive experiments to verify the effectiveness of BSL and compare with benchmark algorithms.

5.1. DATASETS:

8 UCI datasets were used to evaluate Boosting via Self-Labelling (BSL). Since Boosting via Self-Labelling works on binary classification problems, we chose datasets which only contained two class labels or turned linear regression datasets into binary labels. The first column of Table 1 has the name of the dataset used and the percentage of data labelled. The Cancer dataset had 567 samples and 30 features. The Diabetes dataset had 768 samples and 8 features. The Thyroid dataset had 215 samples and 5 features. The Heart dataset had 303 samples and 13 features. The German dataset has 1000 samples and 20 features. The Image dataset has 2310 samples and 19 features. The Housing dataset has 506 samples and 13 features. And the Sonar dataset has 208 samples and 60 features.

5.2. EXPERIMENTAL SETUP:

The goal of our experiments was to show the performance improvement we achieved by using the BSL compared to other semi-supervised algorithms. We use classification error rate (measuring the fraction of mis-classified sample points) each model faced as the evaluation measure. Table 1 reports the mean of 20 different runs of the experiment. To measure the performance of each trial, we split the data into 40% test and 60% train. We then broke up the training into increasing percentages of unlabelled/labelled data points. Table with all results can be found in Appendix.

The pre-processing step started by taking out any points that had missing features or missing labels in the entire dataset. As a result, the dataset was completely labelled and each sample had all of its features. Before creating the unlabelled dataset, we split the data into testing and training set. The unlabelled data was created by removing the labels from a designated percentage of the training set. Each of the features was normalized between 0 and 1 to allow for a better approximation of the data.

At the end of the pre-processing step, three separate lists were outputted: the testing set, the set that contained the unlabelled data points and the set that contained the labelled data points.

During the first step of our framework, the labelled data was passed to a set of supervised machine learning algorithms. Although the number of classifiers could have been theoretically infinite, we chose to limit the number to 10. As a result, the experiment was able to be conducted in a reasonable time. The supervised algorithms were all implemented using the Scikit-learn (Pedregosa et al., 2011) and consisted of KNN, Decision Tree, Gaussian Mixture Model, Naive Bayes, SVM and Logistic Regression. Some of the models were repeated in their use but took on different initialization values to create different classifiers.

The second step of the framework called a basic inference algorithm abbreviated (D&S) (Dawid & Skene, 1979) . The crowdsourcing algorithm outputted the noisy labels for each of the unlabelled data points.

The final part of the framework, our noise-resistant variant of the AdaBoost algorithm is used. The alpha value for each classifier was optimised to compensate for the increase in values from the loss functions. We limited the algorithm to running only 20 decision stumps as the base classifier.

Table 1 shows the performance of BSL compared to other state of the art algorithms which try to create optimised classifiers within the label limited dataset. Table 1 only reports the classification errors for 10% of the training data labelled. Each algorithm bench marked a different part of the framework. C-SVM (Liu et al.) showed the improvement noise resistant version of AdaBoost gave over other noise-resistant algorithms. Semiboost, S3VM, Label Propagation, NN, and Logitboost tested against the final classifier produced by the framework. CSVM, Semiboost, S3VM, and Logitboost were all implemented using different external libraries. Label Propagation was implemented using Scikit-Learn (Pedregosa et al., 2011) And the Supervised Neural Network (NN) was was implemented with Keras (Chollet et al., 2015) .

5.3. RESULTS:



Performance Comparison of BSL with Benchmark Algorithms:

We compared BSL's performance to seven benchmark algorithms, specifically: DS+AdaBoost, Semiboost, S3VM, CSVM, Label Propagation, NN, Logitboost. DS + AdaBoost applied inference method to assign noisy labels to the unlabelled data and used a standard AdaBoost algorithm (Pedregosa et al., 2011) to create a final classifier. The Supervised Neural Network (NN) is a sequential model with two hidden layers each with 100 nodes. If DS was not specified then the model performed without any noise labelled data outputted by the crowdsourcing algorithm. BSL's improvement in performance compared to the other algorithms is significant. BSL consistently had a 20% -30% increase in performance compared to most of the competing algorithms. While BSL is able to outperform most of the algorithms on each of the 8 datasets, it was outperformed by the DS + AdaBoost for trials in the thyroid and sonar dataset. Semiboost was also able to produce better results against BSL in the image dataset. It is important to note that although DS+AdaBoost and Semiboost outperform BSL, the difference in improvement was not significant. This shows that the loss function that we introduced to the noise resistant algorithm might overfit on the data by taking out more noise than was necessary. The loss of performance could also indicate that the error rates passed into the algorithm were not always close to the actual noise in the dataset or were too high to be effective. Table 2 (located in the Appendix) shows the estimated error rate the inference crowdsourcing method outputted for each experiment. It is important to notice the noise that exists within the dataset after the crowdsourcing step. Our handling of this noise allows our algorithm to perform on average better than the other benchmark algorithms. When noise was close to 50%, the noise resistant Adaboost loss function becomes unbounded and this creates unstable classifications. Similarly, the low error rates present within the thyroid dataset allowed for a non-noise resistant version of Adaboost to outperform BSL.

Performance with increment in the percentage of unlabelled data With Figure 1 (located in the Appendix), we also show the performance of BSL on 4 UCI datasets we used to compare framework against the baseline algorithms with increasing amount of unlabelled data instances. In the experiment, we increase the percentage of unlabelled data one at each step, starting from 50% going up to 99% (or as far as possible). Under each step of the experiment, we ran BSL 20 times randomising at every turn which points were used in training, testing, being labelled or unlabelled. The solid line shows the mean of running the algorithm 20 times at each step. The graph shows that despite the decrease of labelled data available to train on, the framework can maintain relatively similar classification error rate. This feature is significant because it shows that having a lot of unlabelled data does not restrict the performance of the framework and therefore is not a prerequisite for it to perform well. One can note that all the graphs don't go to 0.99% unlabelled data. Since the UCI datasets were not significantly big, the closer we are to 0.99% our training data became single-classed labelled. As a result, our framework could not create a final classifier as the ensemble we used was not able to train on the single-classed dataset. As a result, we stopped the experiment at the points where we started getting a lot of single-class labelled data warnings. 

6. DISCUSSION AND CONCLUDING REMARKS:

Our goal in this paper is to present a novel and efficient boosting algorithm for semi-labelled datasets and show its effectiveness in providing an accurate classifier. The usefulness of BSL stems in its ability to produce high-quality noisy labels to unlabelled instances and its ability to handle the noises in labels, despite having severely limited amount of labelled data.

Our results over the 8 UCI datasets reveal the performance improvement BSL brings compared to other algorithms currently in use. Our experiments also show how impervious BSL can be to noise by showing constant performance despite increases in unlablled data. A natural direction would be considering datasets that are fully unlabelled. Instead of having an ensemble of supervised classifiers BSL could consider using a consensus clustering approach and view each clustering algorithm as a potential agent within the crowdsource setting. Another important extension of this project would be using a more proficient inference method to extract the labels less nosier than those produced during our experiments. It is also a very interesting question to further study the theoretical guarantees of BSL in more sophisticated settings. Finally, another aspect of the paper we wish to further pursue is looking at non-homogeneous error rates.

Now we prove that:

Z ≤ exp -2 T t=1 γ 2 t

First we notice the following: at time t

EQUATION

Then when ỹi = +1, taking derivatives of

EQUATION

Here we have defined four sets:

A + := the set of correctly classified data when ỹi = +1, (20) A -:= the set of correctly classified data when ỹi = -1,

and Ā+ , Āare their complement sets. Set derivative in Eqn. ( 19) to 0 we have

α t = 1 2ω + ln 1 -ˆ t ˆ t

where ˆ t is defined as follows: ˆ + t := P ỹ=+1 (f t (x) = ỹ) Similarly when ỹi = -1 ˆ - t := P ỹ=-1 (f t (x) = ỹ)

Define ˆ t = max{ˆ + t , ˆ - t } and when ρ + = ρ -, we have ω + = ω -. And consequently, α t = α + t = α - t Next follows standard argument in boosting we are ready to prove

Z t ≤ ˆ t (1 -ˆ t )

Without loss of generality, consider the negative label case ỹi = -1. Then

Z t =ˆ - t 1 -ˆ t ˆ t + (1 -ˆ - t ) ˆ t 1 -ˆ t ≤ˆ t 1 -ˆ t ˆ t + (1 -ˆ t ) ˆ t 1 -ˆ t = ˆ t (1 -ˆ t )

The inequality is due to the fact 1-ˆ t ˆ t > ˆ t

1-ˆ t . Therefore

Z t ≤ ˆ t (1 -ˆ t ) = 1 -4γ 2 t , γ t := 1 2 -ˆ t Further 1 -4γ 2 t ≤ exp(-2γ 2 t )

This completes the proof.

PROOF FOR LEMMA 1

Given ỹi,fj = f j (x i ) ∈ {±1}, x i ∈ N U , y i is true labels of x i ∈ N U , and y i ∈ (x i , y i ) ∈ N Unoisy .

P(y i,fj = ỹi = 1) =P(y i,fj = ỹi = 1, y i = 0) + P(y i,fj = ỹi = 1, y i = 1) =P(y i,fj = ỹi = 1|Y = 0) • P(y i = 0) + P(y i,fj = ỹi = 1|y i = 1) • P(y i = 1) =P(y i,fj = 1|y i = 0)P • ( ỹi = 1|y i = 0) • P(y i = 0) + P(y i,fj = 1|y i = 1) • P( ỹi = 1|y i = 1) • P(y i = 1) =P(y i = 0) • ρ -• ρ -,fj + P(y i = 1) • (1 -ρ + ) • (1 -ρ +,fj )

Further we have P(ỹ i = 1) = P(y i = 0) • ρ -+ P(y i = 0)(1 -ρ + )

Solving above linear equations completes the proof. 

ADDITIONAL EXPERIMENTAL RESULTS:



:



Figures and Tables:

labels for the unlabelled dataset via a crowdsourcing perspective based on the works of(Dawid & Skene, 1979; Liu et al., 2012). On line 3 in Algorithm 1, M classifiers {f 1 (•), f 2 (•), ...., f M (•)} are trained on labelled data N L = {x 1 , x 2 , . . . , x |N L | }, with the goal to classify all N U data points, {x 1 , x 2 , . . . , x |N U | } as closely as possible to their true unknown binary labels {y 1 , y 2 , . . . , y |N U | } ∈ {-1, +1}. Each data point x i ∈ N U will receive a noisy label ỹi,j which denotes classifier f j (•) ∈ M prediction on x i .Let each row in matrix L ∈ {-1, +1} |N U |×M , in the final step on line 3, represent {ỹ i

Figure 1: Top left: Cancer Dataset, Top Right: Diabetes Dataset, Bottom Left: Heart Dataset, Bottom Right: Thryoid Dataset. All these graphs represent an increasing % of unlabelled data within the dataset.

Classification Error Rate of BSL and the seven benchmark algorithms. The first column shows the dataset and percent of data labelled. The columns D&S+CSVM, Semiboost, S3VM and LP (label propagation), Logitboost, NN show the performance of the six benchmark algorithms. Each entry shows the mean classification error rate over 20 trials. Full table available in the Appendix.

Table content: <table><tr><td>% Labelled</td><td colspan="5">D&amp;S+AdaB BSL D&amp;S+CSVM Semiboost S3VM</td><td>LP</td><td>NN Logitboost</td></tr><tr><td>Cancer -10%</td><td>39.1</td><td>10.22</td><td>38.16</td><td>29.65</td><td colspan="3">37.63 32.68 35.94</td><td>34.65</td></tr><tr><td>Diabetes -10%</td><td>30.19</td><td>27.79</td><td>34.98</td><td>32.97</td><td colspan="3">33.9 35.24 35.63</td><td>31.90</td></tr><tr><td>Thyroid -10%</td><td>14.51</td><td>23.94</td><td>31.32</td><td>30.83</td><td colspan="3">27.21 27.91 35.18</td><td>24.25</td></tr><tr><td>Heart -10%</td><td>32.82</td><td>23.21</td><td>45.05</td><td>35.25</td><td colspan="3">47.05 29.47 35.38</td><td>29.81</td></tr><tr><td>German -10%</td><td>27.5</td><td>26.75</td><td>32.25</td><td>32.25</td><td colspan="3">32.25 32.49 35.82</td><td>30.28</td></tr><tr><td>Image -10%</td><td>27.99</td><td>27.06</td><td>26.17</td><td>25.31</td><td colspan="3">29.74 42.98 41.71</td><td>37.28</td></tr><tr><td>Housing -10%</td><td>29.00</td><td>24.35</td><td>27.31</td><td>26.08</td><td colspan="3">26.50 34.74 42.14</td><td>27.13</td></tr><tr><td>Sonar -10%</td><td>25.60</td><td>26.24</td><td>40.42</td><td>40.53</td><td colspan="3">38.19 44.68 48.81</td><td>45.12</td></tr></table>

Estimated noise within the dataset and the actual noise found within the dataset

Table content: <table><tr><td colspan="3">% Unlabelled Estimated Noise Rate Actual Noise Rate</td></tr><tr><td>Cancer -10%</td><td>5.57</td><td>9.68</td></tr><tr><td>Cancer -20%</td><td>3.51</td><td>5.79</td></tr><tr><td>Cancer -30%</td><td>3.22</td><td>4.17</td></tr><tr><td>Cancer -40%</td><td>2.93</td><td>3.64</td></tr><tr><td>Diabetes -10%</td><td>27.39</td><td>30.38</td></tr><tr><td>Diabetes -20%</td><td>23.47</td><td>25.88</td></tr><tr><td>Diabetes -30%</td><td>20.00</td><td>19.03</td></tr><tr><td>Diabetes -40%</td><td>22.39</td><td>27.46</td></tr><tr><td>Thyroid -10%</td><td>8.52</td><td>6.15</td></tr><tr><td>Thyroid -20%</td><td>7.75</td><td>9.55</td></tr><tr><td>Thyroid -30%</td><td>4.65</td><td>6.75</td></tr><tr><td>Thyroid -40%</td><td>4.51</td><td>8.63</td></tr><tr><td>Heart -10%</td><td>17.67</td><td>16.03</td></tr><tr><td>Heart -20%</td><td>14.91</td><td>13.86</td></tr><tr><td>Heart -30%</td><td>15.81</td><td>17.20</td></tr><tr><td>Heart -40%</td><td>14.91</td><td>18.52</td></tr><tr><td>German -10%</td><td>24.83</td><td>25.81</td></tr><tr><td>German -20%</td><td>24.16</td><td>21.56</td></tr><tr><td>German -30%</td><td>18.16</td><td>20.84</td></tr><tr><td>German -40%</td><td>15.83</td><td>16.09</td></tr><tr><td>Image -10%</td><td>66.01</td><td>57.57</td></tr><tr><td>Image -20%</td><td>57.50</td><td>65.23</td></tr><tr><td>Image -30%</td><td>50.43</td><td>53.72</td></tr><tr><td>Image -40%</td><td>42.71</td><td>41.04</td></tr><tr><td>Housing -10%</td><td>25.74</td><td>26.92</td></tr><tr><td>Housing -20%</td><td>14.15</td><td>9.57</td></tr><tr><td>Housing -30%</td><td>5.61</td><td>8.81</td></tr><tr><td>Housing -40%</td><td>4.62</td><td>8.82</td></tr><tr><td>Sonar -10%</td><td>23.78</td><td>28.26</td></tr><tr><td>Sonar -20%</td><td>26.61</td><td>29.69</td></tr><tr><td>Sonar -30%</td><td>20.53</td><td>19.35</td></tr><tr><td>Sonar -40%</td><td>15.32</td><td>10.62</td></tr></table>

Classification Error Rate of BSL and the seven benchmark algorithms. The first column shows the dataset and percent of data labelled. The columns D&S+CSVM, Semiboost, S3VM and LP (label propagation), Logitboost, NN show the performance of the six benchmark algorithms. Each entry shows the mean Classifcation error rate over 20 trials.

Table content: <table/>

Peer review (iclr2020):
The paper proposed a method combining boosting with semi-supervised learning to handle classification problems when only partial data points have labels available. The method first trains a classifier with the true labels, and predicts labels for unlabeled data (with some error rate), then a bias boosting method is applied on the larger dataset to construct the final classifier. I find the topic interesting but I*m concerned about the novelty level of the paper. Here some further comments. 1. Theorem 1 seems interesting and it will form a strong result if the assumption hp_{+{ = ho_{-} is removed. 2. Lemma 1 *in practice ...*, how to balance the dataset to make sure the two class have similar size? The labeled data can be tailored to ensure this, but one cannot make it happen for the unlabeled data. 3. In the experiments, UCI datasets seem not comprehensive to demonstrate the advantage of the proposed method. More datasets with higher volume could be better. Also, how is the result compared to the case when all the training data labels are known? What is the gap like? 4. Some typos and writing issues, like equation (6) unbalanced brackets.