Semi-Supervised Boosting via Self Labelling
Authors: Akul Goyal
Yang Liu
Venue:  (2020)
Keywords: semi-supervised learning
boosting
noise-resistant

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 noise-resistant 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.

Under review as a conference paper at ICLR 2020
SEMI-SUPERVISS BOOSTING VIA SELF LABELLING
Anonymous authors Paper under double-blind review
ABSTRACT
Attention semi-supervised learning grows in machine learning the price expertly label data increases. Like most previous works in the area, we focus on improving an algorithm's ability discover the inherent property of the entire dataset from a few expertly labelled samples. In this paper we introduce Boosting via Self Labelling (BSL), solution semi-supervised boosting when there is only limited access to labelled instances. Our goal is to learn classifier that is trained on data set that is generated by combining the generalization of different algorithms which have been trained with limited amount of supervised training samples. Our method builds upon a combination of several different components. First, an inference aided ensemble algorithm developed on set of weak classifiers will offer the initial noisy labels. Second, an agreement based estimation approach will return the average resistant boosting algorithm will train over the noisy labels and their error rates to describe the underlying structure closely as possible. We provide both analyti- cal justifications and experimental results to back the performance our model. Based on several benchmark datasets, our results demonstrate that BSL is able outperform state-of-the-art semi-supervised methods consistently, achieving over 90% test accuracy with only 10% of the data being labelled.
rates of the noisy labels. Third and finally, noise-
INTRODUCTION
The rise of the Internet has made 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 propose novel framework: Boosting via Self Labelling (BSL).
Our aim to develop and leverage i) machine learning and estimation approaches to create self- labels for unlabelled instances, and ii) a noise-resistant learning procedure to speed up the perfor- mance 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 set is analogous to agent in crowdsourcing setting. As a result, an inference method can be used to aggregate each of the classifiers predictions and output 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 would agree with a particular classifier. This second order statistic suffices to return 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 worse classifier. The third step introduces noise resistant version of AdaBoost which relies on the noise and error rate estimated in step 2. This results in 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- supervied boosting (Fujino et al. 2005 Blum & Mitchell, 1998 Laine & Aila 2016 Grandvalet & Bengio, 2005) uses semi-supervised algorithms (e.g., clustering) generate

---

Under review as a conference paper at ICLR 2020
tificial proxy labels and boost accordingly (which 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 ment results. Our idea 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.
observed in experi-
2. Noise resistant boosting (Bootkrajang & Kabán, 2013) addresses boosting algorithmss which are susceptible noisy data and proposing variants which can perform under a certain noisy con- ditions. 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 novel self-labelling boosting algorithm (BSL) which is able outperform present state-of-the semi- coni-supervised algorithms.
2. As two key components of our self-labelling framework, we contribute i) a new formulation of noise resistant Adaboost algorithm which corrects the noises in the labels this is important in 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, well as experimental evidence the performance of our framework. We conducted an extensive set of experiments to verify the effectiveness of BSL. In the different datasets 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.
our algorithm on, our method consistently outperforms
The rest of the paper organizes follows. We survey the most relevant work in the rest of the section. Preliminaries are introduced in Section g Section 33 presents a noise-resistant AdaBoost algorithm. Our Boosting via Self Labelling framework is introduced in Section Section our experiment results. Section conclude 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:
Superiuueee 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 al.] 22055; Demiriz al. 1999; Blum & Mitchell 1998), but escalated 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 the area has ranged from EM algorithms (Dawid & Skene 1979
Raykar et al. 2010 Smyyh et al., 1995] Karger et al.] 2011) to variational inference methods (Liu
20122 Karger et al., [2144] Whitehill et al. 2009 Welinder et al.) 2010 Raykar & Yu 2012).
(Chon et al. (2012) wrote good survey for this topic. In an ensemble setting, crowdsourcing has appeared in numerous works include, most famously, (Kim & Ghahramani] (012)). 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] BBotkrajang & Kabán 2013).
Our work builds upon previous work done in these areas, using similar ideas to construct a unique method. One notable piece work is Semiboost (Zhul (005). This algorithm takes a similar ap- proach, introducing boosting framework that improves upon existing classifiers to provide good
2

---

Under review as a conference paper at ICLR 2020
classifier in the semi- setting. However, Semiboost uses an unsupervised learning approach using a similarity matrix based on labelled points and unlabelled points. Semiboost requires a sim- ilarity equation to run, and this 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 unlahelled data and then trains a neural network the combination of the clean and noisy labels. However, Pseudo-labelling and algorithms like it, face many different requirements. Algo- rithms in this class require a sufficient amount of supervised data 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.) 20188) 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 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 lim- ited 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.
PRELIMINARY AND PROBLEM FORMULATION
Assume that D is the underlying true distribution generating n iid examples (I,, Vo where each example consists of feature vector x; = [ ,, Fi,al E X S R and a label E {-1,+1} (~ Y). We assume the true labels of r examples available where T < n such that (ri, (1.,11)=11 denoted as M1), (22,12), v2),... (x Nx. NrI.)(N,)) == Nr. while the rest of n samples (2x) is unlabelled, (x1, "2."" ; == No. Let No and N2. be the set of indices that make up No Mr respectively.
Assume that after an initial classifier f X - (-1,+1) is trained on Ny and applied on the unlabelled dataset such that f(x;) + Ws, 2i E No. Then Nummay denotes the noisy data set pro- 1 to
duced (zt, 9i) 31)mml Nol. Let Nnoisy be the combination of NE, and Nu such that for [Nnoisyl: {(T., M.). if (Ii, Vi) E NNunoiagi (Zi,3i), if (Ii, 3i) E NNt. Let Naoisy be the set of all indices within N Nnnosyy Assume that Nnoisy follows as class-conditional random noise model -
such that: Vn 1, .... |Nnoisy|: P(:: 11 = +1, )n) pt. P(j. +1/y, = 11 = p- and pt + p- < Our goal is to learn a classifier f:X X - {-1,+ +13 trained on Nnnisy that minimizes the risk of f w.r./ to the 0-1 loss function (D( = (a. (J(z;) # v:)].
2.1
OUR PROBLEM: BOOSTING VIA SELF LABELLING
We introduce the setting for AdaBoost (Freund & Schapire 1999). The key idea is, step t,
Maintain weight (t) for each data instance (rt, v:) E NN.
Train a weak learner ft according to the weighted data distribution.
The final hypothesis F is linear combination of each fü trained at every step t.
Let Wiiis be the set of all (x,, vi) E NL such that fe(x;) * ys- The goal is to increase the weight of mis-classified points (t),), (Ni, ye) E Amiss to encourage classifier f++1(-) to focus correctly classifying Nmissi
Di Dr(i)= exp( -ap-aa.-1 fe(x))
Z,
where Z, = -iEN, D.(1) exp(-ox (x()) ((r.))))))) vi) is normalization factor. AdaBoost creates final hypothesis in the additive form: F(x;) = Σt= se(z)) where x; is a test sample.
Our goal, and short coming with AdaBoost, is classifying dataset where some of the yi in (5) E Wnossy are noisy. Because AdaBoost uses a exponential loss function it is inherently susceptible to noisy labels. We propose new loss function that removes bias:
Di( exp(-ax, E(x,, W:)) Vi Nuoisy
Di-(
Z,
Our goal is to define function ē(-) that can help evaluate unlabelled instance. This function ?(-) will allow us adjust noisy labels within Nnoisy- Our algorithm runs in two main stages. It
3

---

Under review as a conference paper at ICLR 2020
first applies noisy labels for unlabelled instances in our dataset, and then creates final hypothesis F using noisc-resistant variant of AdaBoost where define e(-)
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:
= 22 (ū: - 1ly = +1): P- == (ū: = +1 = -1)
Suppose we know these error rates in this section. Boosting over the above noisy examples will lead to biased training process when the label noises are sufficiently large. Our approach is a straight- forward adaptation from a noise correction mechanism adopted in supervised learning (Natarajan al. 2013): : defining surrogate loss function é on noisy labels (for an arbitrary loss function 8)
(1 - 1-p-))(((m)) (I.)) +1) p+ ((,(()
((r() 0: = +1) =
(1)
0+ P- (1 (1- p+) (1-++)(((z;)) -1) (f((),),
(((()). = -1) =
(2)
0+ P-
A nice property of above estimator is its unbiasedness Natarajan al. 2013): : Bgg by (z;). ūc) ((f(x)) ys). We adapt this idea to AdaBoost. Replace E(-) with the following loss measure as
adopted in AdaBoost: (f) U4) = fa(x)) yı. Define Wi = 1-p -PI
1-p-
t- and
1-p P1
tt P (f(((()) # ū), & = P P2 (J((z) # 0).
and & == max t and the following 04
1
E
1 &
at
In
o = 2w- &
In
(4)
2w4
Then update Di(t) as follows:
D,(++1) (t( exp( a sign(s)) {(f(z)),
a,
(5)
where Ze is again the normalization factor. The reason that we need to define two learning rate 0gS is because the losses are weighted differently for the noisy labels. and w [ax,
V' == 1/2 &. and e(6, n, P+. P-) = w | Since we have defined two a,s on the training
2
data based on the noisy labels, we define Og a +o and let the final output classifier be F(x)
sign( ET_ asf((z) > 0). We prove the following performance guarantee when p+ = p-:
T
Theorem
With probability at least 6,
T Σ 1=1
Σ 1(F(z.) + v.) S exp
-2
iENootay
Though our above results are proved under the symmetric error setting, we experimentally verified the performance of our error-resistant boosting procedure.
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 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 specifi- cally, 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 (p_, is calculated and used as inputs to the noisy Adaboost algorithm.
4

---

Under review as a conference paper at ICLR 2020
Algorithm Boosting via Self Labelling
Input: Labelled Data Ni, unlabelled Data No
2: Output: Final Hypothesis F(x)
3: For 1, .M:
Train f. on (I,, M1) E NE
Get hypothesis he fi(t)) + {-1,+11 Vx, E No
Add h2 to matrix L
4: Run inference method generate noisy labels for Ny: I(C) + {-1, [-1,+1))No)
Denote the
noisy dataset as Ne Let N Wnoisy=Nr UN
5: Estimate (p+. P-) using Eqn. 66
6: Initialize: D.(1) = 1/N for i E moisy
7: for /. 1, ,,,., T::
Train weak classifier Is on data distribution D(t)
Get weak hypothesis h4 (x, a), (I ū:) E Nonssyy + +
Get weighted error et, e using Eqn.(3)
Calculate w+, and af ot (Eqn. (4. using estimated P+:
Compute 0t := titar
For E Ny Update weight Dz(L + 1) according to Eqn. 5).
Else for i E Nr. update
weight D1 + 1) according Eqn. with e+ p_ 0.
8: Final Hypothesis:
Lt=1 f(
> >0)
F(x) sign
T
4.1 SELF LABELLING
We generate noisy labels for the unlabelled dataset via crowdsoureing perspective based on the works of (Dawid & Skene 1979; Liu et al. 2012). On line 3 in Algorithm 1, M classifiers are trained on labelled data Ng {m1, " N with the goal to classify all W data points, { 2
(fi()), fa.))....,,,
closely as possible their true unknown binary labels {yr, V2..... No. {-1, +1). Each data point z; .Ng will receive noisy label yi which denotes classifier f-)-) M prediction on z4.
Let each row in matrix L {-1, +13 NNl in the final step on line 3, represent (ū.): No for each f-(-) s.f. L,, = (x,) = M... Assuming f-(+ * fx(-); Vj, & E M s.t. j * each (-) will learn different distribution. This will allow for variation that gives a better prediction the underlying structure of No allowing for some (.) to be closer to capturing the true underlying distribution of Ny compared to others. Assigning weight qj each f-)) according to its perceived accuracy in respect to other classifiers allows for a more accurate aggregation of all fz(-) responses. More formally, step 4 in Algorithm for each of the M classifiers (fi (-i(), (-),))2(( (2()),.., ())), I (variational inference method) assigns an optimal weight {91 ................................ add such that taking the aggregation of each classifiers prediction for point I; E Ny against its respective weight z will result in value ÿJ that will be close possible to the unknown true label yı- The set of and aggregated in Vi E Ny will form U
Conceptually, I uses Gj to classify fz(+) as an expert if qj 0.5. spammer if qj 0.5 or an adversary if gj < 0.5. If f-(-) is designated a spammer then fz(-) is randomly guessing and does not provide any useful prediction. If f)(-) is denoted as adversary, fz(+) is believed to be "purposely" picking the incorrect label and Tiy = fT())). 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 IP fa (x) IP (x)lv))P (f) (x)lg) where 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 IP(g] C, 0) log Σ C(
5

---

Under review as a conference paper at ICLR 2020
Expectation maximization be used to solve for this maximum posteriori estimator é by treat- ing the true labels y/ as the hidden variable. Assuming Beta(o, 3) distribution, an EM can be formulated as follows:
M Step: 9 = EiEN, p4(Li.) +a-1 1N + a + -
E Step: pe(si) x II (1-11))) ( JEM,
where dú, = Ci = Yel and y is estimated by ü = arg max,, (v())) given p is the estimated likelihood of y/. N₂ stands for all labels observed by classifier j: N, = (11)))))) Vi 1... (.u..)N
Finally, step 5 of Algorithm shows the noisy dataset (æ,, ūi), E Nuoisyy where 9: is the noisy label provided by the inference algorithm if NNu, else i/ ys if (24,34) NN Nnoisy then feeds into the Noisy Adaboost Algorithm introduced in Section 3.
4.2 ERROR ESTIMATION
Let A(.) represent the noise resistant AdaBoost algorithm introduced in section 3. Let represent the inference method we will use to aggregate matrix L. Inference method / outputs a noisy labelled data set: NU , }. Ya, Ny. In order
A we need accurately estimate the error
= (ū, = -11y- +1) within Nunaray Assuming homogeneous error rates, we can derive an accurate estimation for the error rates of NU from the confusion matrices of the the classifiers f, E .M.
rates P+: = ( = +1 yi = 1),
Denote the false positive and false negative of f-() by p+.f, and p-.f, respectively. The inference algorithm / will output P--fi and p+.f, for each ʃi E M by comparing {at, Jj (ar:)} against the aggregated label from the inference algorithm. P(y: = -1) and PP(y; = +1) are the marginal distribution of positive and negative labels within the dataset. If P( -1) and Ply +1) are known we show the below equation uniquely identify the error rates given any f, E M:
Lemma P+r p- can be determined by the following set of equations:
(p-,1, = 1) - P U. = 1]
P+ Ply -1 ply = 1p
(6)
-P(ýi -1)(1-t+s) P(y,, 1/: =
P_ = -P(y = +1)(1 -P+.,)))) ) + Plyi = -1)
(7)
In practice we can balance the dataset make P(y; - Ply = +1) = 0.5. The probability
terms P( = 1) and P(yr,,, = U/ 1)n can be estimated through the data. The estimated
parameters are plugged into Eqn. approximate ë+. p_ Note this estimation done without using ground truth labels.
EXPERIMENTAL RESULTS
The focus of BSL is to provide framework which can generate an accurate classifier given very little labelled data. In this section, we conduct extensive experiments verify the effectiveness of BSI. and compare with benchmark algorithms.
5.1 DATASETS
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 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.

---

Under review as a conference paper at ICLR 2020
5.2 EXPERIMENTAL SETUP
The goal of our experiments was show the performance improvement achieved by using the BSL compared to other cemi-supereieed algorithms. We use classification error rate (measuring the fraction of mis-classified sample points) each model faced 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 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 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 result, the experiment was able to be conducted in reasonable time. The supervised algorithms were all implemented using the Scikit-learn (Pedregosa et al. 201T) 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 running only 20 decision stumps as the base classifier.
Table 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 only reports the classification errors for 10% of the training data labelled. Each algorithm bench marked a different part of the framework. C-S al.)) showed the improvement noise resistant version of AdaBoost gave over other noise-resistant algorithms. Semiboost, S3VM, Label Propagation, NN, and Logithoost tested against the final classifier produced by the framework. CSVM, Semiboost, S3VM, and Log- itboost were all implemented using different external libraries. Label Propagation was implemented using Scikit-Learn (Pedregosa et al. 201T) And the Supervised Neural Network (NN) was was im- plemented with Keras (Chollet et al.
2015)
5.3 RESULTS
Performance Comparison of BSL with Benchmark Algorithms We compared BSL's perfor- mance to seven benchmark algorithms, specifically: DS+AdaBoost, Semiboost, S3VM, CSVM, Label Propagation, NN, Logitboost. DS + AdaBoost applied inference method to assign noisy la- bels to the unlabelled data and used a standard AdaBoost algorithm (Pedregosa et al. (01 to create final classifier. The Supervised Neural Network (NN) is 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 crowdsoureing algorithm. BSL's improvement in performance compared the other algorithms is significant. BSL consistently had 20% 30% increase in performance com- pared 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. is important to note that although Ada 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 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 the actual noise in the dataset or were too high be effective. Table 2 (located in the
7

---

Under review as a conference paper at ICLR 2020
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 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 pereentage of unlabelled data With Figure I (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 experi- ment, we increase the percentage of unlabelled data one at each step, starting from 50% going up to 99% (or far possible). Under each step of the experiment, at every turn which points were used 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 classifi- cation error rate. This feature is sigmificant because shows that having 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 la- belled. As a result, our framework could not create a final classifier as the ensemble we used was not able to train the single-classed dataset. As result, stopped the experiment at the points where we started getting lot of single-class labelled data warnings.
BSL 20 times randomising
% Labelled
D&S+AdaB
BSL
D&S+CSVM
Semiboost
S3VM
LP
NN
Logitboost
Cancer 10%
39.1
10.22
38. 16
29.65
37.63
32.68
35.94
34.65
Diabetes 10%
30.19
27.79
34.98
32.97
33.9
35.24
35.63
31,90
Thyroid 10%
14.51
23.94
31.32
30.83
27.21
27.91
35.18
24.25
Heart- 10%
32.82
23.21
45.05
35.25
47.05
29.47
35.38
29.81
German 10%
27.5
26.75
32.25
32.25
32.25
32.49
35.82
30.28
Image- 10%
27.99
27.06
26.17
25.31
29.74
42.98
41.71
37.28
Housing- 10%
29.00
24.35
27.31
26.08
26.50
34.74
42.14
27.13
Sonar 10%
25.60
26.24
40.42
40.53
38.19
44.68
48.81
45.12
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 Ap- pendix.
Table 1:
DISCUSSION AND CONCLUDING REMARKS
Our goal in this paper is to present 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 produce high-quality noisy labels to unlabelled instances and its ability 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. 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 experiments. It is also 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 non-homogeneous error rates.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training, In Pro- ceedings of the eleventh annual conference on Computational learning theory, pp. 92-100. ACM, 1998.
Jakramate Bootkrajang and Ata Kabán. Boosting in the presence of label noise. arXiv preprint arXiv:1309.681 2013.
François Chollet et al. Keras. https: pttpps//keras..ie 2015.
Yohan Chon, Nicholas D Lane, Fan Li, Hojung Cha, and Feng Zhao. Automatically characterizing places with opportunistic crowdsensing using smartphones. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 481-490. ACM, 2012.
Corinna Cortes and Vladimir Vapnik. Support- vector networks. Machine learning, 20(3):273-297, 1995.
Alexander Philip Dawid and Allan M Skene. Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Society: Series C (Applied Statistics), 28 (1):20-28, 1979.
Ayhan Demiriz, Kristin P Bennett, and Mark Embrechts. Semi-supervised clustering using genetic algorithms. 1999.
Carlos Domingo, Osamu Watanabe, al. Madaboost: A modification of adaboost. In COLT, pp- 180-189, 2000.
Yoav Freund and Robert Schapire. A short introduction to boosting. Journal-Japaness Society For Artificial Intelligence, 14(771-780):1612, 1999.
Akinori Fujino, Naonori Ueda, and Kazumi Saito. A hybrid generatieediscriminattee approach to semi-supervised classifier design. In Proceedings the National Conference on Artificial Intelligence, volume 20, pp. 764. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Ad- vances in neural information processing systems, pp. 529-536, 2005.
Trevor Hastie, Saharon Rosset, Zhu, and Hui Zou. Multi-class adaboost. Statistics and its Inter- face, 2(3):349-360, 2009.
David R Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing systems. In Advances in neural information processing systems, pp. 1953-1961, 2011.
David R Karger, Sewoong Oh, and Devavrat Shah. Budget-optimal task allocation for reliable crowdsourcing systems. Operations Research, 62(1):1 22, 2014.
Hyun-Chul Kim and Zoubin Ghahramani. Bayesian classifier combination. In Artificial Intelligence and Statistics, pp. 619-627, 2012.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint drX1v:1610.02242, 2016.
Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.
Bing Liu, Yang Dai, Xiaoli Li. Wee Sun Lee, and S Yu Philip. Building text classifiers using positive and unlabeled examples. Citeseer.
Qiang Liu, Jian Peng, and Alexander Ihler. Variational inference for crowdsourcing. In Pereira, C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Process- ing Systems 25, pp. 692-700. Curran Associates, Inc.. 2012. URL http::ttppppppeeee nips. ccc/paper/4627-var
0ttaper/4627-aoo itw.:aiiiioiaiiineeeeeeeee for- org.

---

Under review as a conference paper at ICLR 2020
Takeru Miyato, Shin-ichi Maeda, Shin Ishii, and Masanori Koyama. Virtual adversarial training: regularization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 2018.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pp. 1196-1204, 2013.
Avital Oliver, Augustus Odena, Colin Raffel, Ekin Dogus Cubuk, and lan Goodfellow. Realistic evaluation of semi-supervised learning algorithms. 2018. URL htt.httss///rxii.rrr////
1804. 09170. pd.f
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-leam: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Gunnar Rätsch, Takashi Onoda, and K-R Müller. Soft margins for adaboost. Machine learning, 42 (3):287-320, 2001.
Vikas C Raykar and Shipeng Yu. Eliminating spammers and ranking annotators for crowdsourced labeling tasks. Journal of Machine Learning Research, 13(Fcb):491-518 2012.
Vikas C Raykar, Shipeng Yu, Linda H Zhao, Gerardo Hermosillo Valadez, Charles Florin, Luca Bogoni, and Linda Moy. Learning from crowds. Journal of Machine Learning Research, 11 (Apr):1297-1322, 2010.
Robert E Schapire. Explaining adaboost. Empirical inference, pp. 37-52. Springer, 2013.
Padhraic Smyth, Usama M Fayyad, Michael C Burl, Pietro Perona, and Pierre Baldi. Inferring ground truth from subjective labelling of venus images. In Advances in neural information pro- cessing systems, pp. 1085-1092, 1995.
Peter Welinder, Steve Branson, Pietro Perona, and Serge J Belongie. The multidimensional wisdom of crowds. In Advances in neural information processing systems, pp. 2424-2432, 2010.
Jacob Whitchill, Ting-fan Wu, Jacob Bergsma, Javier R Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In Advances in neural information processing systems, pp. 2035 2043, 2009.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Technical report, University of Wisconsin- Wisconsin-Madison Madison Department of Computer Sciences, 2005.
10

---

Under review as a conference paper at ICLR 2020
A
PROOF FOR THEOREM
1
For our error-corrected AdaBoost we first prove
T
Z
Z Σ
exp(-e(F(I:)). 1.))
(8)
NENnois
Following standard argument of AdaBoost:
Di = D(t))xx(-ar(((((t))))
Z
D,(t - 1eex-( 1)exx((aa(((((()))) 9:) ag ((f(-1 B.)
1ilr-1
E, Uz))
Since ((fo(zs), (1) is linear in fa we know
(x:() 56) = -8 ar (1ii)))) (((((x)).)))
Therefore
EiE D.(1) exp( -;-- ((F(2.))0))
Σ 11(1+1)=
iENnoisv
Multiple Z on both sides, we have proved Eqn. (8)
Define
((f(z)) = +1) - * -1)
+ +1)
(9)
1-P4 P-
{(f()).)) = 11) (1-+))((s(x)) + 11)-p11(((r) +1)
(10)
1 1 PP
Next we show that
Σ exp(-((((ax)..))) 2
Σ ((F(x)))
iEN NENoos
16 NoNnn
When F(z;) 0. +1, ((F(()). 1 wi 0, but
9:)) > 0. When
F(x;) = -1 0: = +1, (F.())) 0i) = w1, but exp( (FF((F) 0()) > exp(wi) > W1. The case for
1 is symmetric.
Via Hoeffding inequality we know that with high probability at least 1 -
Σ
((F(<:): Z
Σ 1(f(x;) # vi) c p...N.
iENnovy
where ((,,N, == max(w4, w-) v
N 2
Therefore
1(f(x;) # y1)
(11)
iE NNoiii
((F(x:) 1.) p(..N.
(12)
cxp(-((((z.).))) p6..N,
(13)
iENnotay
7 (6,,N,p-,P..
(14)
11

---

Under review as a conference paper at ICLR 2020
Now prove that
Z S exp( -2
71
1=1
First we notice the following: at time
{(f(x,) +1 +1) exp(-w+ar)
(15)
((f(x;) - -1, +1) = exp(w+ar)
(16)
((((x;) - -1,8; 1) = exp( exp(-w-a1)
(17)
((J(x,) +1 -1) exp(w-ai) at)
(18)
Then when Sr +1, taking derivatives of Ze w.r.t. oz.
OZ.
-w,exp(-w+ork + Σ w+exp(w+or)
(19)
don =
Here we have defined four sets:
A+ == the set of correctly classified data when ÿ +1,
(20)
A_ == the set of correctly classified data when Ø = -1,
(21)
and A,, A_ are their complement sets. Set derivative in Eqn. 19 to O we have
1 1 è at 2wit
In
8c
where é, is defined as follows:
+ = (==+1(fe(z)) +
Similarly when 0J =
&7 = P= + ÿ)
Define é max ( and when #+ p_, we have W+ = w.. And consequently, at or Next follows standard argument in boosting we are ready to prove
Z, S (
Without loss of generality, consider the negative label case J -1. Then
E2
2, =
+ (1 E7
èt
Ee
<b
+ (1 εt)
1
=Ve(1=
Ee)
The inequality is due the fact
1-t
Therefore
Ee
1-
1
Z, (1((1-e)
-e) V 47,
2
Further
1 - 4/ < exp(-22 -272)
This completes the proof.
12

---

Under review as a conference paper at ICLR 2020
PROOF FOR LEMMA
1
Given fi.f, = fy( E (+ I2 E Nu. Yi is true labels of x; ENu, and ys E (x., vi) E NN
P(u.,f = y/ = 1)
=P(YL,; = '/ = 1, = =0) + P(u.J, 51 = 1, =
-P(Uk,, = yi = =1 = 0) Ply = =0)
P(yi,, = 51 1 = 1) P(y: 1)
=P(yk,,, =1yy: 0)P (ý 1ly, 0) Ply = =
P(yi,, 1yy 1)- P) 1yy 1) P(y: 1)
= -1( 0) p- P-- P(y 1) (1-p+) p+,)))
Further we have
P(ū = 1) = P(y = 0) p- + P(y = 0)(1 - p+)
(22)
Solving above linear equations completes the proof.
ADDITIONAL EXPERIMENTAL RESULTS
0.25
0.30
020
0.55
0.35
0.85
5.80
0.00
Percent
8.5
0:00
Erroraac Rate
0.35
0.10
0.05
0.80
Figure 1: Top left: Cancer Dataset, Top Right: Diabetes Dataset, Bottom Left: Heart Dataset, Bottom Right: Thryoid Dataset. All these graphs represent increasing % of unlabelled data within the dataset.
13

---

Under review as a conference paper at ICLR 2020
% Unlabelled
Estimated Noise Rate
Actual Noise Rate
Cancer 10%
5.57
9.68
Cancer 20%
3.51
5.79
Cancer 30%
3.22
4.17
Cancer 40%
2.93
3.64
Diabetes 10%
27.39
30.38
Diabetes 20%
23.47
25.88
Diabetes 30%
20.00
19.03
Diabetes 40%
22.39
27.46
Thyroid- 10%
8.52
6.15
Thyroid 20%
7.75
9.55
Thyroid 30%
4.65
6.75
Thyroid 40%
4.51
8.63
Heart 10%
17.67
16.03
Heart 20%
14.91
13.86
Heart 30%
15.81
17.20
Heart 40%
14.91
18.52
German 10%
24.83
25.81
German 20%
24.16
21.56
German 30%
18.16
20.84
German 40%
15.83
16.09
Image 10%
66.01
57.57
Image- 20%
37.50
65.23
Image 30%
50.43
53.72
Image 40%
42.71
41.04
Housing 10%
25.74
26.92
Housing- 20%
14.15
9.57
Housing 30%
5.61
8.81
Housing 40%
4.62
8.82
Sonar 10%
23.78
28.26
Sonar 20%
26.61
29.69
Sonar 30%
20.53
19.35
Sonar 40%
15.32
10.62
Table 2: Estimated noise within the dataset and the actual noise found within the dataset
14

---

Under review as a conference paper at ICLR 2020
% Labelled
D&S+AdaB
BSL
D&S+CSVM
Semiboost
S3VM
LP
NN
Logitboost
Cancer 10%
39.1
10.22
38.16
29.65
37.63
32.68
35.94
34,65
Cancer 20%
33.42
8.9
37.81
19.65
37.81
29.08
31.62
31.82
Cancer 30%
36.73
9.34
37.02
10.92
38.03
21.56
30.97
26.53
Cancer 40%
35.42
9.17
39.25
10.75
36.84
18.68
28.03
17.81
Diabetes 10%
30.19
27.79
34.98
32.97
33.9
35.24
35.63
31.90
Diabetes 20%
28.18
26.69
35.63
33.18
32.92
32.92
31.91
28.29
Diabetes 30%
27.27
25.32
34.09
33.86
35.32
30.71
31.38
27.39
Diabetes 40%
27.96
26.61
34.33
31.94
34.68
30.31
30.43
28.81
Thyroid 10%
14.51
23.94
31.32
30.83
27.21
27.91
35.18
24.25
Thyroid- 20%
10.51
2T.09
30.74
29.84
32.09
26.74
34.31
25.34
Thyroid- 30%
9.49
20.58
31.05
30.08
29.53
25.58
26.82
27.46
Thyroid 40%
8,91
21.12
31.63
30
30.7
22.09
23.41
29.78
Heart 10%
32.82
23.21
45.05
35.25
47.05
29.47
35.38
29.81
Heart 20%
26.23
20.49
44.26
29.51
45.9
29.26
34.40
30.56
Heart 30%
25.41
20.49
45.08
27.05
43.74
27.88
23.87
36.67
Hcart 40%
20.49
15.57
43.86
22.95
45.9
26.31
23.82
41.32
German 10%
27.5
26.75
32.25
32.25
32.25
32.49
35.82
30.28
German 20%
26.5
25.8
27.00
27.00
27.00
26.24
31.33
29.12
German 30%
24.25
22.47
26.54
25.42
27.18
26.34
29.17
28.55
German 40%
24.75
20.59
25.5
25.11
25.39
28.11
27.31
Image 10%
27.99
27.06
26. 17
25.31
29.74
42.98
41.71
37.28
Image 20%
27.75
26.48
24.17
24.67
28.44
37.38
38.22
36.19
Image 30%
25.10
25.83
23.85
22.83
25.15
35.06
31.06
33.45
Image 40%
23.53
24.64
24.80
21.94
22.87
32.51
27.57
29.44
Housing 10%
29.00
24.35
27.31
26.08
26.50
34.74
42.14
27.13
Housing 20%
21.64
20.42
23.31
25.96
24.50
35.35
39.45
25.62
Housing 30%
21.64
19.64
23.41
25.53
23.41
36.79
31.87
25.29
Housing 40%
20.16
19.16
22.09
24.34
21.04
33.89
26.71
23.48
Sonar 10%
25.60
26,24
40.42
40.53
38.19
44.68
48.81
45.12
Sonar 20%
16.60
18.39
36.87
33.94
37.73
38.07
31.72
31.69
Sonar 30%
13.34
14.1
29.00
27.87
30.32
33.33
25.83
25.88
Sonar 40%
10.63
13.43
26.17
25.78
26.17
26.24
21.64
24.68
Table 3: 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.
15


Reviews:
[{"review_id": "rkluCySRYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n1. Theorem 1 seems interesting and it will form a strong result if the assumption \\rhp_{+{ = \\rho_{-} is removed.\n\n2. 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.\n\n3. 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?\n\n4. Some typos and writing issues, like equation (6) unbalanced brackets.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlClhzCtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nMy suggestion is to reject the paper, with the following key reasons.\n\n(1) Contribution is insufficient, or perhaps not well-highlighted. For the three pieces of contribution, Section 4.1 (self-labeling, which is highlighted within the title) seems to be a trivial borrowing of an existing idea in crowd sourcing from 1979. It is not clear whether Section 4.2 (error estimation) is an original contribution or not, but even if it is original Lemma 1 seems marginally trivial. Section 3 (noise-resistant AdaBoost) plugs a known surrogate loss for noisy labels into AdaBoost. But despite the ugly math, the results seem to be equivalent to a heuristically-shrunk alpha_t for AdaBoost. None of the pieces seem to make a solid contribution to the problem of interest.\n\n(2) Assumptions are not reasonable. Section 3 and Sections 4.2 both rely on \"homogeneous error rates\" which does not seem to be the case when the noise is generated from classifier-target mismatch. In particular, the noisy will only happen in mismatch areas, and not happen in other areas, making it non-homogeneous. The authors did not discuss the rationality of this assumption and/or how it affects the designed approach. In Section 4.2, there is another assumption that \"in practice we can balance the dataset\", which might be true for the labeled part through sampling, but not necessarily true for the unlabeled part. So it is not clear whether this assumption can be met. Section 4.2 also assumes that \"the probability can be estimated through the data\" but did not mention how large the data needs to be for an accurate estimation.\n\n(3) Experiments cannot be easily replicated. To begin with, the authors claim to use 10 classifiers from scikit-learn as the initial labeler, but the exact 10 (including parameters) are not pinged down. In the data sets, there is a procedure \"or turned linear regression datasets into binary labels\" that does not seem sufficiently clear for replication. It is not clear whether \"feature normalization\" considers only the training set or the whole training+test set.\n\nHaving said that, there are some other suggestions:\n\n(4) Writing needs improvement. Many of the parts contains unnecessarily ugly math notations without motivation. Even the core Section 3 looks like a LaTeX math demo than a clear illustration of scientific ideas.\n\n(5) It is not clear what the importance of Theorem 1 is. There doesn't seem to be a guarantee of gamma_t > 0 given the authors' definition of hat{epsilon}_t (worse case error of the two classes), and then the first part of Theorem 1 is not fast decreasing. It is not clear whether the N in the second term is N_noisy. In any case, the theorem is not clearly described enough to help understand the contribution of the paper.\n\n(6) A baseline that should be considered is to treat the noisy labels as \"soft labels\" and then apply confidence-based boosting.\n\nImproved Boosting Algorithms Using Confidence-rated Predictions, Schapire and Singer 1999.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlqncT3KH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nMajor Comments\n\nAs a non-expert in this area, I had trouble identifying the novel contributions of this work. For example, many of the results in Section 3 (noise-resistant AdaBoost) seem to replicate, or follow closely, the results of [Natarajan et al., 2013]. Similarly, using EM to assign pseudo-labels has been extensively studied in the literature [Lee, WREPL 2013; Chapelle and Zien, AISTATS 2005; Kang et al., ECCV 2018; Rottman et al., ICMLA 2018]. \n\n\nThe experiments are very poorly described, so it is difficult to gauge if they are valid:\n\nMost importantly, the authors point out that the estimated error rates do not always match the actual error rates. Since this seems to be one of the most important factors of the proposed approach, further investigation should be performed to answer questions like: why is the error rate not estimated well? on what type of datasets? can more/better supervised learners help? In some cases (Diabetes, Thyroid, Heart), the actual noise rate increases with more labeled samples. What does that mean?\n\nSecond, the proposed approach seems to have a number of important hyperparameters, including the number of supervised models trained and their hyperparameters, the parameters of the Beta distribution used as a prior on the noise estimation, and the hyperparameters of the AdaBoost algorithm. Likewise, all of the competing algorithms also have hyperparameters which are known to affect performance (e.g., learning rate for NNs). The paper does not mention how (or if) a validation set was used to select these.\n\nThird, while the caption of Table 1 mentions that 20 trials were used, it is not clear if this was some sort of k-fold cross validation, Monte Carlo, cross validation, the same splits but with different random seeds, etc. Additionally, the variance across the different trials should be given; otherwise, it is not possible to tell if any of the empirical results are significant.\n\nMinor Comments:\n\nThe references are not consistently formatted.\n\nThis paper is very notation heavy. It would be helpful to include a “table of symbols” for the reader in an appendix.\n\nAdditionally, the notation in the paper is not consistent. For example, both “$M$” and “$\\mathcal{M}$ are used to indicate the number of models trained on the labeled data. Later on, “$\\mathcal{M}$” is also used to refer to the set of trained classifiers. The first bullet point in Step 3 of the pseudocode seems to suggest that each classifier is trained on a single labeled data point. The equation at the bottom of Page 5 used \\theta, but it does not seem to be defined.\n\nThe discussion on experts, spammers, and adversaries could be helpful if this terminology were used throughout the paper; however, it is used in only one paragraph. \n\nThe main body of the paper should mention that proofs are given in the appendices.\n\nFor context, if may be helpful to mention that graph convolutional networks and other representation learning techniques are commonly used for semi-supervised learning (e.g., [Kipf and Welling, ICML 2016]). Those approaches are quite different (and lack any sort of theoretical guarantees, for the most part), though, so empirical comparisons may not be so meaningful.\n\nIt would be helpful to give a sentence or two on the intuition behind what the proofs are showing. For a non-expert, they are very difficult to follow.\n\nDo the various proofs still hold when the datasets are artificially balanced (with respect to the last paragraph in Section 4)?\n\nIt would be helpful to include the performance using the complete labeled dataset for comparison.\n\nStratified sampling could be used to ensure both classes are present in the training data. Also, “0.99%” -> “99%”.\n\nBesides accuracy, some measure like AuROC or the F1 score which account for class imbalance should be given.\n\nTypos, etc.\n\n“Logitboost tested against” -> “Logitboost were tested against”\n\n\n“therefore is not” -> “therefore, having a lot of labeled data is not”\n\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new semi-supervised boosting approach. 

As reviewers pointed out and AC acknowledge, the paper is not ready to publish in various aspects: (a) limited novelty/contribution, (b) reproducibility issue and (c) arguable assumptions.

Hence, I recommend rejection.
Decision: Reject