Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 & Kabá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.

heading: 1.1 RELATED WORKS
text: 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 (Rätsch et al., 2001; Hastie et al., 2009; Domingo et al., 2000; Schapire, 2013; Bootkrajang & Kabá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.

heading: 2 PRELIMINARY AND PROBLEM FORMULATION
text: Assume that D is the underlying true distribution generating n iid examples (xi, yi)ni=1, where each example consists of a feature vector xi = [xi,1, xi,2, . . . , xi,d] ∈ X ⊆ Rd, and a label yi ∈ {−1,+1} (∼ Y ). We assume the true labels of τ examples is available where τ < n such that (xi, yi) τ i=1, denoted as {(x1, y1), (x2, y2), · · · , (x|NL|, y|NL|)} := NL ; while the rest of n − τ samples (xi)ni=τ is unlabelled, {x1, x2, · · · , x|NU |} := NU . Let NU and NL be the set of indices that make up NU and NL respectively. Assume that after an initial classifier f : X → {−1,+1} is trained on NL and applied on the unlabelled dataset such that f(xi) → ỹi, xi ∈ NU . Then NUnoisy denotes the noisy data set produced (xi, ỹi) |NU | i=1 . Let Nnoisy be the combination of NL and NUnoisy such that for i = 1 to |Nnoisy|: {(xi, ỹi), if (xi, ỹi) ∈ NUnoisy ; (xi, yi), if (xi, yi) ∈ NL}. Let Nnoisy be the set of all indices within Nnoisy . Assume that Nnoisy follows as class-conditional random noise model such that: ∀n = 1, 2, ..., |Nnoisy|: P(ỹi = −1|yi = +1, xn) = ρ+, P(ỹi = +1|yi = −1, xn) = ρ− and ρ+ + ρ− < 1. Our goal is to learn a classifier f : X → {−1,+1} trained on Nnoisy that minimizes the risk of f w.r.t to the 0-1 loss function RD(f) = E(xi,yi)∼D[1(f(xi) 6= yi)].

heading: 2.1 OUR PROBLEM: BOOSTING VIA SELF LABELLING
text: We introduce the setting for AdaBoost (Freund & Schapire, 1999). The key idea is, at step t,
• Maintain a weight Di(t) for each data instance (xi, yi) ∈ NL. • Train a weak learner ft according to the weighted data distribution. • The final hypothesis F is a linear combination of each ft trained at every step t.
Let Nmiss be the set of all (xi, yi) ∈ NL, such that ft(xi) 6= yi. The goal is to increase the weight of mis-classified points Di(t), (xi, yi) ∈ Nmiss to encourage classifier ft+1(·) to focus on correctly classifying Nmiss:
Dt(i+ 1) = Dt(i) · exp
( −αt · ft(xi) · yi ) Zt ,
where Zt = ∑ i∈NL Dt(i) ·exp ( −αt ·ft(xi) ·yi ) is a normalization factor. AdaBoost creates a final
hypothesis in the additive form: F (xi) = ∑T t=1 αtft(xi), where xi is a test sample.
Our goal, and a short coming with AdaBoost, is classifying a dataset where some of the yi in (xi, yi) ∈ Nnoisy 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:
Dt+1(i) = Dt(i) · exp
( −αt · ˜̀(xi, ỹi) ) Zt , ∀i ∈ Nnoisy
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 Nnoisy . 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 ˜̀(·) .

heading: 3 NOISE-RESISTANT ADABOOST
text: 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:
ρ+ := Pxi(ỹi = −1|yi = +1), ρ− := Pxi(ỹi = +1|yi = −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 `)
˜̀(f(xi), ỹi = +1) := (1− ρ−)`(f(xi),+1)− ρ+`(f(xi),−1)
1− ρ+ − ρ− , (1)
˜̀(f(xi), ỹi = −1) := (1− ρ+)`(f(xi),−1)− ρ−`(f(xi),+1)
1− ρ+ − ρ− . (2)
A nice property of above estimator is its unbiasedness (Natarajan et al., 2013): Eỹi|yi [˜̀(f(xi), ỹi)] = `(f(xi), yi). We adapt this idea to AdaBoost. Replace `(·) with the following loss measure as adopted in AdaBoost: `(f(xi), yi) = ft(xi) · yi. Define ω+ := 1−ρ−+ρ+1−ρ−−ρ+ , ω− := 1−ρ++ρ− 1−ρ−−ρ+ and ̂+t := Px|ỹ=+1(ft(x) 6= ỹ), ̂−t := Px|ỹ=−1(ft(x) 6= ỹ), (3) and ̂t := max{̂+t , ̂−t } and the following αts
α+t = 1
2ω+ ln 1− ̂t ̂t , α−t = 1 2ω− ln 1− ̂t ̂t
(4)
Then update Di(t) as follows:
Di(t+ 1) := Di(t) · exp
( −αsign(ỹi)t ˜̀(f(xi), ỹi) ) Zt
(5)
where Zt is again the normalization factor. The reason that we need to define two learning rate αts 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 αts 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 (xi) 6= yi) ≤ exp ( −2 T∑ t=1 γ2t ) + (δ,N, ρ+, ρ−).
Though our above results are proved under the symmetric error setting, we experimentally verified the performance of our error-resistant boosting procedure.

heading: 4 A SELF LABELLING FRAMEWORK FOR BOOSTING
text: 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 NL, unlabelled Data NU 2: Output: Final Hypothesis F (x) 3: For i = 1, · · · ,M :
• Train fi on (xi, yi) ∈ NL • Get hypothesis ht = fi(xi)→ {−1,+1}|NU |, ∀xi ∈ NU • Add ht to matrix L
4: Run inference method to generate noisy labels for NU : I(L) → {−1,+1}|NU |. Denote the noisy dataset as NUnoisy . Let Nnoisy= NL ∪NUnoisy . 5: Estimate (ρ+, ρ−) using Eqn. (6, 7). 6: Initialize: Di(1) = 1/N for i ∈ Nnoisy 7: for t = 1, · · · , T :
• Train weak classifier gt on data distribution D(t) • Get weak hypothesis ht :=gt(x, i), (xi, ỹi) ∈ Nnoisy → {−1,+1} • Get weighted error +, − using Eqn.(3) • Calculate ω+, ω− and α+t , α−t (Eqn.(4)), using estimated ρ̃+, ρ̃−. • Compute αt := α + t +α − t
2 . • For i ∈ NU : Update weight Di(t + 1) according to Eqn.(5). Else for i ∈ NL, update
weight Di(t+ 1) according to Eqn.(5) with ρ+ = ρ− = 0. 8: Final Hypothesis:
F (x) = sign
(∑T t=1 αtft(x)
T > 0
)

heading: 4.1 SELF LABELLING
text: We generate noisy 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 {f1(·), f2(·), ...., fM (·)} are trained on labelled data NL = {x1, x2, . . . , x|NL|}, with the goal to classify all NU data points, {x1, x2, . . . , x|NU |} as closely as possible to their true unknown binary labels {y1, y2, . . . , y|NU |} ∈ {−1,+1}. Each data point xi ∈ NU will receive a noisy label ỹi,j which denotes classifier fj(·) ∈M prediction on xi.
Let each row in matrix L ∈ {−1,+1}|NU |×M , in the final step on line 3, represent {ỹi};∀i ∈ NU for each fj(·) s.t. Li,j = fj(xi) = ỹi,j . Assuming fj(·) 6= fk(·);∀j, k ∈ M s.t. j 6= k each fj(·) will learn a different distribution. This will allow for a variation that gives a better prediction on the underlying structure of NU allowing for some fj(·) to be closer to capturing the true underlying distribution of NU compared to others. Assigning weight qj to each fj(·) according to its perceived accuracy in respect to other classifiers allows for a more accurate aggregation of all fj(·) responses. More formally, in step 4 in Algorithm 1, for each of the M classifiers {f1(·), f2(·), . . . , fM (·)}, I (variational inference method) assigns an optimal weight {q1, q2, . . . , qM} such that taking the aggregation of each classifiers prediction for point xi ∈ NU against its respective weight qj will result in a value ỹi that will be as close as possible to the unknown true label yi. The set of xi and aggregated ỹi ∀i ∈ NU will form NUnoisy . Conceptually, I uses qj to classify fj(·) as an expert if qj > 0.5, a spammer if qj ≈ 0.5 or an adversary if qj < 0.5. If fj(·) is designated a spammer then fj(·) is randomly guessing and does not provide any useful prediction. If fj(·) is denoted as an adversary, fj(·) is believed to be “purposely” picking the incorrect label and ỹi,j = fj(xi). 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(fj(x), fk(x)|y) = P(fj(x)|y)P(fk(x)|y) where j, k ∈ |M|s.t.j 6= 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 yi as the hidden variable. Assuming a Beta(σ, β) distribution, an EM can be formulated as follows:
E Step: µi(yi) ∝ ∏ j∈Mi q̂ δi,j j (1− q̂j) 1−δi,j M Step: q̂j = ∑ i∈Nj µi(Li,j) + σ − 1 |Nj |+ σ + β − 2
where δi,j = I[Li,j = yi] and ỹi is estimated by ỹi = arg maxyi µi(yi) given µi is the estimated likelihood of yi. Nj stands for all labels observed by classifier j: Nj = ({fj(xi)},∀i ∈ 1 · · · |NU |). Finally, step 5 of Algorithm 1 shows the noisy dataset (xi, ỹi),∀i ∈ Nnoisy where ỹi is the noisy label provided by the inference algorithm if xi ∈ NU , else ỹi = yi if (xi, yi) ∈ NL. Nnoisy then feeds into the Noisy Adaboost Algorithm introduced in Section 3.

heading: 4.2 ERROR ESTIMATION
text: LetA(.) 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: NUnoisy = {xi, ỹi},∀xi ∈ NU . In order to run A we need to accurately estimate the error rates ρ−, ρ+: ρ− = (ỹi = +1|yi = −1), ρ+ = (ỹi = −1|yi = +1) within NUnoisy . Assuming homogeneous error rates, we can derive an accurate estimation for the error rates of NUnoisy from the confusion matrices of the the classifiers fj ∈M. Denote the false positive and false negative of fj(·) by ρ+,fj and ρ−,fj respectively. The inference algorithm I will output ρ−,fj and ρ+,fj for each fi ∈ M by comparing {xi, fj(xi)} against the aggregated label from the inference algorithm. P(yi = −1) and P(yi = +1) are the marginal distribution of positive and negative labels within the dataset. If P(yi = −1) and P(yi = +1) are known we show the below equation uniquely identify the error rates given any fj ∈M:
Lemma 1 ρ+, ρ− can be determined by the following set of equations:
ρ+ = (ρ−,fjP(ỹi = 1)− P(yi,fj = ỹi = 1)
P(yi = +1)(1− ρ+,fj )− P(yi = −1)(ρ−,fj ) (6)
ρ− = −P(ỹi = 1)(1− ρ+,fj ) + P(yi,fj = ỹi = 1) −P(yi = +1)(1− ρ+,fj ) + P(yi = −1)(ρ−,fj )
(7)
In practice we can balance the dataset to make P(yi = −1) = P(yi = +1) = 0.5. The probability terms P(ỹi = 1) and P(yi,fj = ỹ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.

heading: 5 EXPERIMENTAL RESULTS
text: 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.

heading: 5.1 DATASETS
text: 8 UCI datasets were used to evaluate Boosting via Self-Labelling (BSL). Since Boosting via SelfLabelling 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.

heading: 5.2 EXPERIMENTAL SETUP
text: 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).

heading: 5.3 RESULTS
text: 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.

heading: 6 DISCUSSION AND CONCLUDING REMARKS
text: 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.

heading: A PROOF FOR THEOREM 1
text: For our error-corrected AdaBoost we first prove
Z := T∏ t=1 Zt = ∑
i∈Nnoisy
exp ( −˜̀(F (xi), ỹi) ) (8)
Following standard argument of AdaBoost:
Di(t+ 1) = Di(t)exp
( −αt ˜̀(ft(xi), ỹi) ) Zt
= Di(t− 1)exp
( −αt ˜̀(ft(xi), ỹi)− αt−1 ˜̀(ft−1(xi), ỹi) ) ZtZt−1
=...
= Di(1)exp
( − ∑ τ ατ ˜̀(fτ (xi), ỹi) )
Z
Since ˜̀(ft(xi), ỹi) is linear in ft we know t∑
τ=1 −αt ˜̀(fτ (xi), ỹi) = −˜̀ ( t∑ τ=1 ατfτ (xi), ỹi ) = −˜̀ ( F (xi), ỹi ) Therefore
1 = ∑
i∈Nnoisy
Di(t+ 1) =
∑ i∈Nnoisy Di(1) · exp ( − ∑t τ=1 ˜̀(F (xi), ỹi) )
Z
Multiple Z on both sides, we have proved Eqn. (8).
Define
ˆ̀ ( f(xi), ỹi = +1 ) :=
(1− ρ−)1(f(xi) 6= +1)− ρ+1(f(xi) 6= −1) 1− ρ+ − ρ− , (9)
ˆ̀ ( f(xi), ỹi = −1 ) :=
(1− ρ+)1(f(xi) 6= −1)− ρ−1(f(xi) 6= +1) 1− ρ+ − ρ− . (10)
Next we show that ∑ i∈Nnoisy exp ( −˜̀(F (xi), ỹi) ) ≥ ∑ i∈Nnoisy ˆ̀ ( F (xi), ỹi ) When F (xi) = ỹi = +1, ˆ̀(F (xi), ỹi) = 1 − ω1 < 0, but exp ( −˜̀(F (xi), ỹi) ) > 0. When
F (xi) = −1, ỹi = +1, ˆ̀(F (xi), ỹi) = ω1, but exp ( −˜̀(F (xi), ỹi) ) > exp(ω1) > ω1. The case for ỹi = 1 is symmetric. Via Hoeffding inequality we know that with high probability at least 1− δ∑ i∈Nnoisy ˆ̀(F (xi), ỹi) ≥ ∑ i∈Nnoisy 1(f(xi) 6= yi)− (δ,N, ρ−, ρ+)
where (δ,N, ρ+, ρ−) := max(ω+, ω−) · √ N ln 2δ 2 . Therefore ∑ i∈Nnoisy 1(f(xi) 6= yi) (11)
≤ ∑
i∈Nnoisy
ˆ̀(F (xi), ỹi) + (δ,N, ρ−, ρ+) (12)
≤ ∑
i∈Nnoisy
exp ( −˜̀(F (xi), ỹi) ) + (δ,N, ρ−, ρ+) (13)
=Z + (δ,N, ρ−, ρ+) (14)
Now we prove that
Z ≤ exp ( −2 T∑ t=1 γ2t )
First we notice the following: at time t
˜̀(f(xi) = +1, ỹi = +1) = exp(−ω+αt) (15) ˜̀(f(xi) = −1, ỹi = +1) = exp(ω+αt) (16) ˜̀(f(xi) = −1, ỹi = −1) = exp(−ω−αt) (17) ˜̀(f(xi) = +1, ỹi = −1) = exp(ω−αt) (18)
Then when ỹi = +1, taking derivatives of Zt w.r.t. αt
∂Zt ∂αt = ∑ x∈A+ −ω+exp(−ω+αt) + ∑ x∈Ā+ ω+exp(ω+αt) (19)
Here we have defined four sets:
A+ := the set of correctly classified data when ỹi = +1, (20) A− := the set of correctly classified data when ỹi = −1, (21)
and Ā+, Ā− 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 := Pỹ=+1(ft(x) 6= ỹ)
Similarly when ỹi = −1 ̂−t := Pỹ=−1(ft(x) 6= ỹ)
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
Zt ≤ √ ̂t(1− ̂t)
Without loss of generality, consider the negative label case ỹi = −1. Then
Zt =̂ − 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
Zt ≤ √ ̂t(1− ̂t) = √ 1− 4γ2t , γt := 1
2 − ̂t
Further √ 1− 4γ2t ≤ exp(−2γ2t )
This completes the proof.
PROOF FOR LEMMA 1
Given ỹi,fj = fj(xi) ∈ {±1}, xi ∈ NU , yi is true labels of xi ∈ NU , and yi ∈ (xi, yi) ∈ NUnoisy .
P(yi,fj = ỹi = 1) =P(yi,fj = ỹi = 1, yi = 0) + P(yi,fj = ỹi = 1, yi = 1) =P(yi,fj = ỹi = 1|Y = 0) · P(yi = 0)
+ P(yi,fj = ỹi = 1|yi = 1) · P(yi = 1) =P(yi,fj = 1|yi = 0)P · (ỹi = 1|yi = 0) · P(yi = 0)
+ P(yi,fj = 1|yi = 1) · P(ỹi = 1|yi = 1) · P(yi = 1) =P(yi = 0) · ρ− · ρ−,fj + P(yi = 1) · (1− ρ+) · (1− ρ+,fj )
Further we have
P(ỹi = 1) = P(yi = 0) · ρ− + P(yi = 0)(1− ρ+) (22)
Solving above linear equations completes the proof.
ADDITIONAL EXPERIMENTAL RESULTS

Review summaries:
In this paper, the authors present an approach for semi-supervised learning which combines noisy labels with boosting. In a first step, the labeled instances are used to train a set of classifiers, and these are used to create noisy labels for the unlabeled instances. Then, an EM procedure is used to estimate the noise level of each instance. Finally, a version of AdaBoost which accounts for instance noise levels is proposed to create a final classifier. A limited set of experiments suggests the proposed approach is competitive with existing approaches.

The authors propose a new semi-supervised boosting approach. The approach takes a set of supervised learning algorithms to simulate "crowd-source" labels of the unlabeled data, which are then used to generate a noisy label per unlabeled instance. The noise level is then estimated with an agreement-based scheme, and fed to a modified AdaBoost algorithm that is more noise-tolerant given the noise level. Some theoretical guarantee of the modified AdaBoost algorithm is derived and promising experiment results are demonstrated.