--- title: "Generalization Guarantees of Self-Training of Halfspaces under Label Noise Corruption" authors: - "Lies Hadjadj" - "Massih-Reza Amini" - "Sana Louhichi" doi: "10.24963/ijcai.2023/420" url: "https://ijcai.org/proceedings/2023/420" pdf: "https://ijcai.org/proceedings/2023/0420.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "3777-3785" track: "Main Track" keywords: - "Machine Learning: ML: Semi-supervised learning" - "Machine Learning: ML: Learning theory" --- # Generalization Guarantees of Self-Training of Halfspaces under Label Noise Corruption Lies Hadjadj, Massih-Reza Amini, Sana Louhichi *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 3777-3785. DOI: [10.24963/ijcai.2023/420](https://doi.org/10.24963/ijcai.2023/420) ## Abstract We investigate the generalization properties of a self-training algorithm with halfspaces. The approach learns a list of halfspaces iteratively from labeled and unlabeled training data, in which each iteration consists of two steps: exploration and pruning. In the exploration phase, the halfspace is found sequentially by maximizing the unsigned-margin among unlabeled examples and then assigning pseudo-labels to those that have a distance higher than the current threshold. These pseudo-labels are allegedly corrupted by noise. The training set is then augmented with noisy pseudo-labeled examples, and a new classifier is trained. This process is repeated until no more unlabeled examples remain for pseudo-labeling. In the pruning phase, pseudo-labeled samples that have a distance to the last halfspace greater than the associated unsigned-margin are then discarded. We prove that the misclassification error of the resulting sequence of classifiers is bounded and show that the resulting semi-supervised approach never degrades performance compared to the classifier learned using only the initial labeled training set. Experiments carried out on a variety of benchmarks demonstrate the efficiency of the proposed approach compared to state-of-the-art methods. ## Full text ## 1 Introduction In recent years, several attempts have been made to establish a theoretical foundation for semi-supervised learning. These studies are mainly interested in the generalization ability of semi-supervised learning techniques [Rigollet, 2007; Maximov et al., 2018] and the utility of unlabeled data in the training process [Castelli and Cover, 1995; Singh et al., 2009; Li and Zhou, 2011; Wei et al., 2021]. The majority of these works are based on the concept called compatibility in [Balcan and Blum, 2006], and try to exploit the connection between the marginal data distribution and the target function to be learned. The common conclusion of these studies is that unlabeled data will only be useful for training if such a relationship exists. The three key types of relations considered in the literature are cluster assumption, manifold assumption, and lowdensity separation [Zhu, 2005; Chapelle et al., 2006]. The cluster assumption states that data contains homogeneous labeled clusters, and unlabeled training examples allow to recognize these clusters. In this case, the marginal distribution is viewed as a mixture of class conditional distributions, and semi-supervised learning has been shown to be superior to supervised learning in terms of achieving smaller finitesample error bounds in some general cases, and in some others, it provides a faster rate of error convergence [Castelli and Cover, 1995; Rigollet, 2007; Maximov et al., 2018; Singh et al., 2009]. In this line, [Ben-David et al., 2008] showed that the access to the marginal distribution over unlabeled training data would not provide sample size guarantees better than those obtained by supervised learning unless one assumes very strong assumptions about the conditional distribution over the class labels. Manifold assumption stipulates that the target function is in a low-dimensional manifold. [Niyogi, 2013] establishes a context through which such algorithms can be analyzed and potentially justified; the main result of this study is that unlabeled data may help the learning task in certain cases by defining the manifold. Finally, low-density separation states that the decision boundary lies in low-density regions. A principal way, in this case, is to employ a margin maximization strategy which results in pushing away the decision boundary from the unlabeled data [Chapelle et al., 2006]. Semi-supervised approaches based on this paradigm mainly assign pseudo-labels to high-confident unlabeled training examples with respect to the predictions and include these pseudo-labeled samples in the learning process. [Wei et al., 2020] demonstrated that, under the expansion assumption stipulating that a low-probability subset of data must grow to a neighborhood mostly surely regaring the subset, selftraining will reach high accuracy with regard to ground-truth labels. In this line, [Frei et al., 2021] showed that a strong classifier may be learned from a weaker one in the context of general mixture models with benign concentration and anticoncentration properties. However, [Chawla and Karakoulas, 2011] investigated empirically the problem of label noise bias introduced during the pseudo labeling process in this case and showed that the use of unlabeled examples could have a minimal gain or even degrade performance, depending on the generalization ability of the initial classifier trained over the labeled training data. In this paper, we study the generalization ability of a selftraining algorithm with halfspaces that operates in two steps. In the first step, halfspaces are found iteratively over the set of labeled and unlabeled training data by maximizing the unsigned-margin of unlabeled examples and then assigning pseudo-labels to those with a distance greater than a found threshold. These pseudo-labels are supposed to be corrupted by label noise and pseudo-labeled examples are added to the training set, and a new classifier is then learned. This process is repeated until there are no more unlabeled examples to pseudo-label. In the second step, pseudo-labeled examples with an unsigned-margin greater than the last found threshold are removed from the training set. Our contribution is twofold: (a) we present a first generalization bound for self-training with halfspaces in the case where class labels of examples are supposed to be corrupted by a Massart noise model; (b) we show that the use of unlabeled data in the proposed self-training algorithm does not degrade the performance of the first halfspace trained over the labeled training data. In the remainder of the paper, Section 2 presents the definitions and the learning objective. In Section 3, we present in detail the adaptation of the self-training algorithm for halfspaces with a preliminary analysis in Section 4. Section 5 presents a bound over the misclassification error of the classifier outputted by the proposed algorithm and demonstrates that this misclassification error is upper-bounded by the misclassification error of the fully supervised halfspace. In Section 6, we present experimental results, and we conclude this work in Section 7. ## 2 Framework and Notations We consider binary classification problems where the input space X is a subset of Rd , and the output space is Y = {-1,+1}. We study learning algorithms that operate in hypothesis space Hd = {hw : X → Y} of centered halfspaces, where each hw ∈ Hd is a Boolean function of the form hw(x) = sign(〈w, x〉), with w ∈ Rd such that ‖w‖2 ≤ 1. Our analysis succeeds the recent theoretical advances in robust supervised learning of polynomial algorithms for training halfspaces under large margin assumption [Diakonikolas et al., 2019; Montasser et al., 2020; Diakonikolas and Kane, 2020; Johnson et al., 2020; Diakonikolas et al., 2021], where the label distribution has been corrupted with the Massart noise model [Massart and N´ed´elec, 2006]. These studies derive a PAC bound for generalization error for supervised classifiers that depends on the corruption rate of the labeled training set and shed light on a new perspective for analyzing the self-training algorithm. Similarly, in our analysis, we suppose that self-training can be seen as learning with an imperfect expert. Whereat at each iteration, labels of the pseudo-labeled set have been corrupted with a Massart noise [Massart and N´ed´elec, 2006] oracle defined as: Definition 2.1 ([Massart and N´ed´elec, 2006] noise oracle). Let C = {f : X → Y} be a class of Boolean functions over X ⊆ Rd , with f an unknown target function in C, and 0 ≤ η < 1/2. Let η(x) : X → [0, η] be an unknown parameter function, and Dx any marginal distribution over X. The corruption oracle O(f, Dx, η) works as follow: each time O(f, Dx, η) is invoked, it returns a pair (x, y) where x is generated i.i.d. from Dx; y = -f(x) with probability η(x) and y = f (x) with probability 1 - η(x). Let D denote the joint distribution over X × Y generated by the above oracle with an unknown parameter function η(0) defined as η(0) (x) : X → [0, η]. We suppose that the training set is composed of l labeled samples Sℓ = (xi, yi)1≤i≤l ∈ (X × Y)l and u unlabeled samples Xu = (xi)l+1≤i≤l+u ∈ X u , where l << u. Furthermore, we suppose that each pair (x, y) ∈ X × Y is i.i.d. with respect to the probability distribution D, we denote by Dx the marginal of D on x, and Dy(x) the distribution of y conditional on x. Finally, for any integer d, let [d] = {0, ..., d}. ## 3 Self-Training with Halfspaces Given Sℓ and Xu drawn i.i.d. from a distribution D corrupted with O(f,Dx, η(0) ). Algorithm 1 learns iteratively a list of halfspaces Lm = [(w(1) , γ (1) ), ..., (w(m) , γ (m) )] with each round consisting of exploration and pruning steps. The goal of the exploration phase is to discover the halfspace with the highest margin on the set of unlabeled samples that are not still pseudo-labeled. This is done by first, learning a halfspace that minimizes the empirical surrogate loss of RD(w) = E(x,y)∼D[ℓ(y, hw(x))] over a set of labeled and already pseudo-labeled examples S(k) from Sℓ and Xu: At round k = 0, we have S(0) = Sℓ. Once the halfspace with parameters w(k) is found, a threshold γ (k) , defined as the highest unsigned-margin in S(k) , is set such that the empirical loss over the set of examples in S(k) with unsignedmargin above γ (k) , is the lowest. In the pseudo-code of the algorithm, S(k) ≥i refers to the subset of examples in S(k) having an unsigned margin greater or equal to ω × i. Unlabeled examples x ∈ Xu that are not pseudo-labeled are assigned labels, i.e., y = sign(〈w(k) , x〉) iff |〈w(k) , x〉| ≥ γ (k) . These pseudo-labeled examples are added to S(k) and removed from Xu, and a new halfspace minimizing Eq. (1) is found. Examples in S(k) are supposed to be misclassified by the oracle O(f,Dx, η(k) ) following Definition 2.1 with the parameter function η(k) that refers to the conditional probability of corruption in S(k) defined as η(k) (x) = Py∼S(k) y (x) [f(x) ̸= y] ≤ η(k) . Once the halfspace with parameters w(k) and threshold γ (k) are found such that there are no more unlabeled samples having an unsigned-margin larger than γ (k) , the pair (w(k) , γ (k) ) is added to the list Lm, and samples from S(k) having an unsigned-margin above γ (k) are removed (pruning ## Algorithm 1 Self-Training with Halfspaces Input : Sℓ = (xi, yi)1≤i≤l, Xu = (xi)l+1≤i≤n, p: number of threshold tests set to 5. while |S(k) | ≥ ℓ do Let w a random vector in Rd such that ‖w‖2 ≤ 1, and let the cost function defined ˆRS(k)(w) = 1 |S(k) | ∑(x,y)∈S(k) [ℓp(y, hw(x))]; Run projected SGD on ˆRS(k)(w) to obtain w(k) such that ‖w(k) ‖2 ≤ 1; phase). Remind that γ (k) is the largest threshold above which the misclassification error over S(k) increases. The self-training algorithm 1, takes as input the labeled set Sℓ, the unlabeled set Xu and p, which refers to the number of tests for threshold estimation, set to 5. After finding the weight vector w(k) at round k, with projected SGD (step 4 - 5), we order the labeled set S(k) (with S(0) = Sℓ) by decreasing order of unsigned-margin to w(k) . The threshold γ (k) is defined as the largest margin such that the error of examples in S(k) with an unsigned-margin higher than γ (k) increases (step 8 - 9). At this stage, observations x ∈ Xu with an unsigned-margin greater than γ (k) (step 10 - 14), are pseudo-labeled and added to the labeled set S(k) and they are removed from the unlabeled set. This exploration phase of finding a halfspace with the largest threshold γ (k) is repeated until there are no more unlabeled samples with an unsigned-margin larger than this threshold. After this phase, the pruning phase begins by removing examples in S(k) with an unsigned-margin strictly less than γ (k) (step 15-18). The parameters of the halfspace and the corresponding threshold are added to the list of selected classifiers Lm and the procedure is repeated until that the size of the labeled set becomes less than l. To classify an unknown example x, the prediction of the first halfspace with normal vector w(i) in the list Lm, such that the unsigned-margin |〈w(i) , x〉| of x is higher or equal to the corresponding threshold γ (i) , is returned. By abuse of notation, we note that the prediction for x is Lm(x) = hw(i)(x). If no such halfspace exists, the observation is classified using the prediction of the first classifier hw(1) that was trained over all the labeled and the pseudolabeled samples without pruning. ## 4 Theoretical Analyses Our goal is to find a hypothesis hw ∈ Hd such that with high probability, the misclassification error P(x,y)∼D[hw(x) ̸= y] is minimized, and, that with high probability the performance of the found solution is better or equal to any hypothesis in Hd obtained only from the labeled training set, Sℓ. ## 4.1 Learning Objective We denote by ηw(x) = Py∼Dy(x)[hw(x) ̸= y] the conditional misclassification error of a hypothesis hw ∈ Hd with respect to D, and w∗ the normal vector of hw∗ ∈ Hd that achieves the optimal misclassification error; η ∗ = min w,‖w‖2≤1 P(x,y)∼D[hw(x) ̸= y]. By considering the indicator function 1π defined as 1π = 1 if the predicate π is true and 0 otherwise; we prove in the following lemma that the probability of misclassification of halfspaces over examples with an unsigned-margin greater than a threshold γ > 0 is bounded by the same quantity 0 < η < 1 that upper-bounds the misclassification error of these examples. Lemma 4.1. For all hw ∈ Hd , if there exist η ∈]0, 1[ and γ > 0 such that Px∼Dx [|〈w, x〉| ≥ γ] > 0 and that Ex∼Dx [(ηw(x) -η)1|〈w,x〉|≥γ] ≤ 0, then P(x,y)∼D[hw(x) ̸= y∣∣|〈w, x〉| ≥ γ] ≤ η. Proof. For all hypotheses hw in Hd, we know that the error achieved by hw in the region of margin γ from w satisfies Ex∼Dx [(ηw(x) -η)1|〈w,x〉|≥γ] ≤ 0; by rewriting the expectation, we obtain the following Ex∼Dx [ηw(x)1|〈w,x〉|≥γ ] - ηPx∼Dx [|〈w, x〉| ≥ γ] ≤ 0. We have then Ex∼Dx [ηw(x)1|〈w,x〉|≥γ] Px∼Dx [|〈w,x〉|≥γ] ≤ η and the result follows from the equality: Suppose that there exists a pair (˜w, ˜ γ) minimizing: By defining ˜ η as: The following inequality holds: This inequality paves the way for the following claim, which is central to our self-training strategy. Claim 4.2. Suppose that there exists a pair (˜w, ˜ γ) satisfying the minimization problem (2) with Px∼Dx [|〈˜w, x〉| ≥ ˜ γ] > 0 , then P(x,y)∼D[h˜w(x) ̸= y∣∣|〈˜w, x〉| ≥ ˜ γ] ≤ η ∗ . Proof. The requirements of Lemma 4.1 are satisfied with (w, γ) = (˜w, ˜ γ) and η = ˜ η. This claim is then proved using the conclusion of Lemma 4.1 together with the fact that ˜ η ≤ η∗ . The claim above demonstrates that for examples generated by the probability distribution D, there exists a region in X on either side of a margin ˜ γ to the decision boundary defined by ˜w solution of (Eq. 2); where the probability of misclassification error of the corresponding halfspace in this region is upper-bounded by the optimal misclassification error η∗ . This result is consistent with semi-supervised learning studies that consider the margin as an indicator of confidence and search the decision boundary on low-density regions [Joachims, 1999; Amini et al., 2009]. ## 4.2 ProblemResolution We use a block coordinate minimization method for solving the optimization problem (2). This strategy consists in first finding a halfspace with parameters ˜w that minimizes Eq. (2) with a threshold γ = 0, and then by fixing ˜w, finds the threshold ˜ γ for which Eq. (2) is minimum. We resolve this problem using the following claim, which links the misclassification error ηw and the perceptron loss ℓp(y, hw(x)) : Y × Y → R+; ℓp(y, hw(x)) = -y〈w, x〉1y〈w,x〉≤0. Claim 4.3. For a given weight vector w, we have: Proof. For a fixed weight vector w, we have that: E(x,y)∼D[ℓp(y, hw(x))] = E(x,y)∼D[-y〈w, x〉1y〈w,x〉≤0]. As we are considering misclassification errors, i.e., -y〈w, x〉1y〈w,x〉≤0 = 1y〈w,x〉≤0|〈w, x〉|, it comes that E(x,y)∼D[ℓp(y, hw(x))] = E(x,y)∼D[|〈w, x〉|Py∼Dy(x) [-y〈w, x〉 > 0]]. The result then follows from the definition of the misclassification error, i.e., ηw(x) = Py∼Dy(x) [-y〈w, x〉 > 0]. This claim shows that the minimization of the generalization error with ℓp is equivalent to minimizing Ex∼Dx [|〈w, x〉|ηw(x)]. Hence, the minimization of Ex∼Dx [ℓp(y, hw(x))] cannot result in bounded misclassification error, as the distribution of margins |〈w, x〉| might vary widely between samples in X. In the following lemma, we show that it is possible to achieve bounded misclassification error under margin condition and L2-norm constraint. Lemma 4.4. For a fixed distribution D, let R = max x∼Dx ‖x‖2 We then have: Proof. From the condition |〈 ˜w, x〉| ≥ γ, we have: Applying the definition of ˜w to the right-hand side of the above inequality gives: Using the Cauchy-Schwarz inequality and the definition of R, we get: Then from the definition of w, we know: Dividing the two inequalities above by R gives the result. Lemma 4.4 guarantees that the approximation of the perceptron loss to the misclassification error is more accurate for examples that have a comparable distance to the halfspace. This result paves the way to our implementation of the selflearning algorithm. The proposed self-training algorithm operates iteratively, where at each round k only points with a large margin found at the previous iteration are considered for the minimization of RD(w) = E(x,y)∼D[Relu(-y〈w, x〉)] using the structural Risk Minimization (SRM) principle. ## 5 Corruption Noise Modeling and Generalization Guarantees In the following, we relate the process of pseudo-labeling to the corruption noise model O(f,Dx, η(k) ) for all pseudolabeling iterations k in Algorithm 1, then we present a bound over the misclassification error of the classifier Lm outputted by the algorithm and demonstrate that this misclassification error is upper-bounded by the misclassification error of the fully supervised halfspace. Claim 5.1. Let S(0) = Sℓ be a labeled set drawn i.i.d. from D = O(f,Dx, η(0) ) and U(0) = Xu an initial unlabeled set drawn i.i.d. from Dx. For all iterations k ∈ [K] of Algorithm 1; the active labeled set S(k) is drawn i.i.d. from D = O(f, Dx, η(k) ) where the corruption noise distribution η(k) is bounded by: The proof is provided in the supplementary material. We can now bound the generalization error of the classifier Lm outputted by Algorithm 1 with respect to the optimal misclassification error η∗ in the case where projected SGD is used for the minimization of Eq. (1). Note that in this case the time complexity of the algorithm is polynomial with respect to the dimension d, the upper bound on the bit complexity of examples, the total number of iterations, and the upper bound on SGD steps. Theorem 5.2. Let Sℓ be a set of i.i.d. samples of size ℓ drawn from a distribution D = O(f, Dx, η(0) ) on Rd × {-1, +1}, where f is an unknown concept function and η(0) an unknown parameter function bounded by 1/2, let Xu be an unlabeled set of size u drawn i.i.d. from Dx. Algorithm 1 terminates after K iterations, and outputs a non-proper classifier Lm of m halfspaces such that with high probability: where I is the set of rounds k ∈ [K] at which the halfspaces were added to Lm, ϵ(k) is the projected SGD convergence error rate at round k, and πK+1 a negligible not-accounted mass of Dx. The proof of Theorem 5.2 is based on the following property of projected SGD. Lemma 5.3 (From [Duchi, 2016]). Let ˆR be a convex function of any type. Consider the projected SGD iteration, which starts with w(0) and computes for each step. w(t+ 1 2 ) =w(t) -α(t) g(t) ;w(t+1) = argmin w:||w||2≤1 ||w - w(t+ 1 2 ) ||2. Where g(t) is a stochastic subgradient such that Ex∼Dx [g(w, x)] ∈ ∂ ˆR(w) = {g : ˆR(w′ ) ≥ ˆR(w) + 〈E[g], w′ - w〉 for all w′ } and Ex∼Dx [||g(w, x)||22 ] ≤ M 2 . For any ϵ, δ > 0; if the projected SGD is executed T = Ω(log(1/δ)/ϵ2 ) times with a step size α(t) = 1 M√t , Proof of Theorem 5.2. We consider the steps of Algorithm1. At iteration k of the while loop, we consider the active training set S(k) consisting of examples not handled in previous iterations. We first note that the algorithm terminates after at most K iterations. From the fact that at every iteration k, we discard a non-empty set from S(k) when we do not pseudolabel or from U(k) when we pseudo-label, and that the empirical distributions Sℓ and Xu are finite sets. By the guarantees of Lemma 5.3, running SGD (step 4) on ˆRS(k) for T = Ω(log(1/δ)/ϵ2 ) steps, we obtain a weight vector w(k) such that with probability at least 1 - δ: From Claim 4.3, we derive with high probability: Then the margin γ (k) is estimated minimizing Eq. (2) given w(k) , following Lemma 4.4 with R(k) = max x∼Dx ‖x‖2 the radius of the truncated support of the marginal distribution Dx at iteration k, we can assume that γ (k) R(k) ≈ 1, ∀k ∈ [K], one may argue that the assumption is unrealistic knowing that the sequence of (γ (k) )mk=1 decreases overall, but as we show in the supplementary, we prove in Theorem A.1 that under some convergence guarantees of the pairs {(w(k) ,w(k+1) )}m-1 k=1 , one can show that the sequence {R(k) }mk=1 decreases as a function of γ (k) respectively to k. As a result, we can derive with high probability: From Claim 4.2 and giving the pair (w(k) , γ (k) ), we obtain with high probability that at round k: When the while loop terminates, we have accounted m ≤ K halfspaces in the list Lm satisfying Eq. (4). For all k ∈ I, every classifier hw(k) in Lm has guarantees on an empirical distribution mass of at least ˜κ = min k∈I Px∼S(k) [|〈w(k) , x〉| ≥ γ (k) ]; the DKW (Dvoretzky-Kiefer-Wolfowitz) inequality [Dvoretzky et al., 1956] implies that the true probability mass κ = min k∈I Px∼Dx [|〈w(k) , x〉| ≥ γ (k) ] of this region is at least k∈I The pruning phase in the algorithm ensures that these regions are disjoint for all halfspaces in Lm, it follows that using the Boole-Fr´echet inequality [Boole, 2015] on the conjunctions of Eq. (4) overall rounds k ∈ [I], implies that Lm classifies at least a (1 -mκ)-fraction of the total probability mass of D with guarantees of Eq. (4) with high probability, let πK+1 = Px∼Dx [x ∈ S(K+1) ] be the probability mass of the region not accounted by Lm. We argue that this region is negligible from the fact that |S(K+1) | < ℓ and ℓ ≪ u, such that setting ϵ = max k∈I ϵ(k) +πK+1 provides the result. □ In the following, we show that the misclassification error of the classifier Lm output of Algorithm 1 is at most equal to the error of the supervised classifier obtained over the labeled training set Sℓ, when using the same learning procedure. This result suggests that the use of unlabeled data in Algorithm 1 does not degrade the performance of the initial supervised classifier. Theorem 5.4. Let Sℓ be a set of i.i.d. samples of size ℓ drawn from a distribution D = O(f, Dx, η(0) ) on Rd × {-1, +1}, where f is an unknown concept function and η(0) an unknown parameter function bounded by 1/2, let Xu be an unlabeled set of size u drawn i.i.d. fromDx. Let Lm be the output of Algorithm1 on input Sℓ and Xu, and let hw(0) be the halfspace of the first iteration obtained from the empirical distribution S(0) = Sℓ, there is a high probability that: Proof. By the guarantees of Lemma 5.3, the classifier hw(0) obtained on running SGD on ˆRS(0) with projection to the unit l2-ball for P (0) steps satisfies : Let k be the iteration at which the first pair (w(1) , γ (1) ) is added to Lm. The first pruning phase in Algorithm 1 results in a set S(k) ⊆ Sℓ ∪ ⋃k-1 i=1 S(i) u . Claim 5.1 ensures that the probability of corruption in the pseudo-labeled set ⋃k-1 i=1 S(i) u is bounded by max j∈[k] η(j) ≤ η∗ + ϵ. In other words, the weight vector w(1) is obtained from an empirical distribution that includes both the initial labeled set Sℓ and a pseudo-labeled set from Xu. Particularly, if this pseudo-labeled set is not empty, then its pseudo-labeling error is nearly optimal, which implies that P(x,y)∼D[hw(1) (x) ̸= y] ≤ P(x,y)∼D[hw(0) (x) ̸= y]. Ultimately, Lm classifies a large fraction of the probability mass of D with nearly optimal guarantees (e.i., Eq. (4) in proof of Theorem 5.2) and the rest using hw(1) with an error of misclassification at most equal to P(x,y)∼D[hw(0) (x) ̸= y]. ## 6 Empirical Results Datasets. We mainly consider data sets from [Chapelle et al., 2006]. Some of these collections such as baseball-hockey, pc-mac and religion-atheism are binary classification tasks extracted from the 20-newsgroups data set. We used tf-idf representation for all textual data sets above. spambase is a collection of spam e-mails from the UCI repository [Dua and Graff, 2019]. one-two, odd-even are handwritten digits recognition tasks originally from optical recognition of handwritten digits database also from UCI repository, one-two is digits "1" versus "2"; odd-even is the artificial task of classifying odd "1, 3, 5, 7, 9" versus even "0, 2, 4, 6, 8" digits. weather is a data set from Kaggle which contains about ten years of daily weather observations from many locations across Australia, and the objective is to classify next-day rain target variable. We have also included data sets from extreme classification repository [Bhatia et al., 2015] mediamill2 and delicious2 by selecting the label which gives the best ratio in class distribution. The statistics of these data sets are given in Table 1. Baseline methods. We implemented the halfspace or Linear Threshold Function (LTF) using TensorFlow 2.0 in python aside with Algorithm 1 1 (Lm), we ran a Support Vector Machine (SVM) [Cortes and Vapnik, 1995] with a linear kernel from the LIBLINEAR library [Fan et al., 2008] as another supervised classifier. We compared results with a semisupervised Gaussian naive Bayes model (GM) [Chapelle et al., 2006] from the scikit-learn library. The working hypothesis behind (GM) is the cluster assumption stipulating that data contains homogeneous labeled clusters, which can be detected using unlabeled training samples. We also compared results with label propagation (LP) [Zhu and Ghahramani, 2002] which is a semi-supervised graph-based technique. We used the implementation of LP from the scikit-learn library. Table 1: data set statistics, -1 and +1 refer to the size of negative and positive class respectively, and test is the size of test set. | data set | d | -1 | +1 | ℓ +u | test | |------------------|------|-------|-------|--------|--------| | one-two | 64 | 177 | 182 | 251 | 108 | | banknote | 4 | 762 | 610 | 919 | 453 | | odd-even | 64 | 906 | 891 | 1257 | 540 | | pc-mac | 3868 | 982 | 963 | 1361 | 584 | | baseball-hockey | 5724 | 994 | 999 | 1395 | 598 | | religion-atheism | 7829 | 1796 | 628 | 1696 | 728 | | spambase | 57 | 2788 | 1813 | 3082 | 1519 | | weather | 17 | 43993 | 12427 | 37801 | 18619 | | delicious2 | 500 | 9610 | 6495 | 12920 | 3185 | | mediamill2 | 120 | 15969 | 27938 | 30993 | 12914 | This approach follows the manifold assumption that the decision boundary is located on a low-dimensional manifold and that unlabeled data may be utilized to identify it. We also included entropy regularized logistic regression (ERLR) proposed by [Grandvalet and Bengio, 2005] from [Krijthe, 2017]. This approach is based on low-density separation that stipulates that the decision boundary lies on low-density regions. In the implementation of [Krijthe, 2017], the initial supervised classifier is a logistic regression that has a similar performance to the SVM classifier. We evaluated these methods using relatively small labeled training sets ℓ ∈ {10, 50, 100}, and for all methods, we used the default hyper-parameters as cross-validation methods would not be effective in this case. Experimental Setup. In our experiments, we have randomly chosen 70% of each data collection for training and the remaining 30% for testing. We randomly selected sets of different sizes (i.e., ℓ ∈ {10, 50, 100}) from the training set as labeled examples; the remaining was considered as unlabeled training samples. Results are evaluated over the test set using the accuracy measure. Each reported performance value is the average over the 20 random (labeled/unlabeled/test) sets of the initial collection. All experiments are carried out on a machine with an Intel Core i7 processor, 2.2GhZ quad-core, and 16Go 1600 MHz of RAM memory. Analysis of Results. Table 2 summarizes the results. We used boldface (resp. underline) to indicate the highest (resp. the second-highest) performance rate, and the symbol ↓ indicates that performance is significantly worse than the best result, according to a Wilcoxon rank-sum test with a p-value threshold of 0.01 [Wolfe, 2012]. From these results, it comes out that the proposed approach (Lm) consistently outperforms the supervised halfspace (LTF). 1 Implementation available for research purpose at this address: https://github.com/Lies0zeta/Self-Training-of-Halfspaces. Table 2: Mean and standard deviations of accuracy on test sets over the 20 trials for each data set. The best and the second-best performance are respectively in bold and underlined. ↓ indicates statistically significantly worse performance than the best result, according to a Wilcoxon rank-sum test [Wolfe, 2012] with (p < 0.01). | Dataset | ℓ | SVM | LTF | LP | GM | ERLR | Lm | |---------------------------------|--------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------| | | 10 | 61.38±13.71↓ | 70.87±13.24↓ | 48.61±3.98↓ | 75.09±1.30 | 53.65±10.65↓ | 77.77±1.75 | | one-two | 50 | 92.77±3.05 | 88.00±3.24↓ | 49.35±4.20↓ | 84.67±4.98↓ | 75.78±8.74↓ | 91.34±3.21 | | | 100 | 96.15±1.38 | 92.50±1.43↓ | 67.82±12.99↓ | 86.52±3.26↓ | 79.25±6.87↓ | 94.62±2.46 | | | | 57.50±7.21↓ | 69.40±5.53↓ | 55.98±2.00↓ | 69.04±4.60↓ | 56.71±4.53↓ | 77.24±3.81 | | banknote | | 61.67±4.86↓ 71.65±6.24↓ | 82.31±2.13↓ 89.38±3.24 | 56.28±1.89↓ 57.20±2.19↓ | 75.48±5.30↓ 77.56±4.34↓ | 65.95±2.01↓ 70.95±3.24↓ | 85.64±5.36 90.82±3.31 | | odd-even pc-mac baseball-hockey | 10 50 100 10 50 100 10 50 100 10 50 100 10 | 53.45±4.80↓ 64.75±5.65↓ 75.89±6.25↓ 51.00±3.22↓ 58.85±5.09↓ 64.57±4.42↓ 51.57±2.98↓ 58.66±6.90↓ 68.40±4.65↓ 67.30±6.95 74.61±1.62 74.66±1.59 | 58.20±4.71↓ 76.84±2.99↓ 77.68±4.56↓ 54.92±2.00↓ 61.78±2.86↓ 67.98±2.37 55.41±3.16↓ 69.29±4.32 76.25±2.41↓ 57.30±4.89↓ 71.79±1.98↓ 73.67±1.76 | 50.37±1.95↓ 50.37±1.95↓ 53.37±1.95↓ 50.93±1.59↓ 50.83±2.08↓ 50.76±2.26↓ 56.53±5.18 50.11±1.84↓ 49.97±1.82↓ 67.59±6.36 67.43±6.05↓ 62.84±19.33↓ | 60.69±7.48 62.67±5.82↓ 64.25±8.18↓ 54.76±3.42↓ 58.78±4.31↓ 62.49±1.88↓ 49.86±1.77↓ 66.76±5.40↓ 71.12±5.06↓ 60.67±16.37↓ 69.16 ± 7.88 70.45±4.39↓ | 50.40±2.21↓ 53.17±4.80↓ 59.23±6.28↓ 50.14±2.06↓ 49.71±1.99↓ 50.36±2.19↓ 49.88±1.89↓ 50.16±1.90↓ 50.35±1.89↓ 71.95±5.03 74.16±1.88 | 63.21±7.51 80.61±3.10 84.58±2.12 57.75±3.19 64.31±3.55 68.15±5.66 56.47±5.50 72.85±6.52 79.48±4.36 64.25±7.24↓ 72.47±2.00 73.77±1.82 | | religion-atheism | 50 100 10 50 | 61.20±5.15↓ 62.59±9.42↓ | 57.80±5.29↓ | 60.82±0.84↓ 61.15±0.86↓ | 74.41±6.64 | 73.21±1.75 | 68.92±5.83↓ | | | | 69.43±10.19↓ | 74.99±6.04 | | 78.25±2.62 | 53.38±11.23↓ 53.63±9.86↓ | 76.13±3.08 | | spambase | 100 | | 80.07±4.08 | 61.24±10.26↓ | 79.08±2.83↓ | | 81.93±2.46 | | weather | 10 50 75.79 | 74.85±0.51 ± 0.28 | 68.09±1.73↓ 75.30±3.85 76.27±3.64 | 75.49±0.34 77.99±0.31 77.99±0.25 | 75.02±2.79 75.68±2.78 | 58.21±6.34↓ | | | | 100 10 | 77.99±0.25 51.83±9.88 | 50.59±2.65↓ 54.78±2.57↓ | 59.87±0.67 | 74.92±1.92 49.41±3.83↓ | 40.35±17.29↓ 41.55±27.39↓ 46.00±24.87↓ | 75.08±4.18 75.34±3.80 77.28±2.99 | | delicious2 | 50 | 60.04±0.62 | 56.04±1.83↓ | 60.02±0.61 60.00±0.59 | 48.35±1.31↓ | 51.83±10.42↓ 53.48±8.66↓ | 51.08±1.80↓ 55.37±3.33↓ | | | 100 | 58.88±3.70 62.54±2.62↓ | 60.98±6.85↓ 60.88±7.45↓ | 36.35±0.15↓ 36.36±0.15↓ | 48.92±0.94↓ | 54.43±7.27↓ | 56.54±1.87↓ | | mediamill2 | | 63.64±0.15↓ | | | 63.92±1.71 65.98±3.32 | | 64.31±3.14 65.41±4.83 | | | | | | | | 58.58±11.88↓ | | | | 50 | | | | | | | | | | | | | | 47.24±14.08↓ | | | | 10 | | | | | | | | | | 63.64±0.15↓ | 64.26±4.79 | 36.37±0.15↓ | 67.34±0.73 | 63.64±0.16↓ | | | | 100 | | | | | | 67.80±2.21 | Furthermore, compared to other techniques, Lm generally performs the best or the second-best. We also notice that in some cases, LP, GM, and ERLR outperform the supervised approaches, SVM and LTF (i.e., GM on spambase for ℓ ∈ {10, 50}), but in other cases, they are outperformed by both SVM and LTF (i.e., GM on religion-atheism). These results suggest that unlabeled data contain useful information for classification and that existing semi-supervised techniques may use it to some extent. They also highlight that the development of semi-supervised algorithms following the given assumptions is necessary for learning with labeled and unlabeled training data but not sufficient. These results underline the need of developing theoretically sound semi-supervised algorithms that show the method's ability to generalize and to better understand the value of unlabeled training data in the learning process. ## 7 Conclusion We presented a first bound over the misclassification error of a self-training algorithm that iteratively finds a list of halfspaces from partially labeled training data. Each round consists of two steps. The exploration phase's purpose is to determine the halfspace with the largest margin and assign pseudo-labels to unlabeled observations with an unsignedmargin larger than the discovered threshold. The pseudolabeled instances are then added to the training set, and the procedure is repeated until there are no more unlabeled instances to pseudo-label. In the pruning phase, the last halfspace with the largest threshold is preserved, ensuring that there are no more unlabeled samples with an unsigned-margin greater than this threshold and pseudo-labeled samples with an unsigned-margin greater than the specified threshold are removed. We ultimately show that the use of unlabeled data in the proposed self-training algorithm does not degrade the performance of the initially supervised classifier. An interesting future direction would be to quantify the real gain of learning with unlabeled and labeled training data compared to a fully supervised scheme. ## References 1. [Amini et al., 2009] Massih R. Amini, Nicolas Usunier, and Franc ¸ois Laviolette. A transductive bound for the voted classifier with an application to semi-supervised learning. In Advances in Neural Information Processing Systems, pages 65-72, 2009. 2. [Balcan and Blum, 2006] Maria-Florina Balcan and Avrim Blum. An augmented PAC model for semi-supervised learning. In Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien, editors, Semi-Supervised Learning, pages 396-419. The MIT Press, 2006. 3. [Ben-David et al., 2008] Shai Ben-David, Tyler Lu, and Dávid Pál. Does unlabeled data provably help? worst- case analysis of the sample complexity of semi-supervised learning. In Proceedings of the The 21st Annual Confer- ence on Learning Theory (COLT-08), pages 33-44, 2008. 4. [Bhatia et al., 2015] Kush Bhatia, Himanshu Jain, Purushot- tam Kar, Manik Varma, and Prateek Jain. Sparse local embeddings for extreme multi-label classification. In Ad- vances in Neural Information Processing Systems, vol- ume 28, 2015. 5. [Boole, 2015] G. Boole. An Investigation of the Laws of Thought: On Which Are Founded the Mathematical Theo- ries of Logic and Probabilities. Creative Media Partners, LLC, 2015. 6. [Castelli and Cover, 1995] Vittorio Castelli and Thomas M. Cover. On the exponential value of labeled samples. Pat- tern Recognit. Lett., 16(1):105-111, 1995. 7. [Chapelle et al., 2006] Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien, editors. Semi-Supervised Learning. The MIT Press, 2006. 8. [Chawla and Karakoulas, 2011] Nitesh Chawla and Grigoris Karakoulas. Learning from labeled and unlabeled data: An empirical study across techniques and domains. Journal of Artificial Intelligence Research -JAIR, 23, 09 2011. 9. [Cortes and Vapnik, 1995] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Mach. Learn., 20(3):273-297, September 1995. 10. [Diakonikolas and Kane, 2020] Ilias Diakonikolas and Daniel M. Kane. Hardness of learning halfspaces with massart noise. CoRR, abs/2012.09720, 2020. 11. [Diakonikolas et al., 2019] Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution- independent pac learning of halfspaces with massart noise. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 4749-4760. 12. Curran Associates, Inc., 2019. 13. [Diakonikolas et al., 2021] Ilias Diakonikolas, Russell Im- pagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, and Christos Tzamos. Boosting in the presence of massart noise. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1585-1644. PMLR, 15-19 Aug 2021. 14. [Dua and Graff, 2019] Dheeru Dua and Casey Graff. UCI machine learning repository. https://archive.ics.uci.edu/ ml, 2019. Accessed: 2023-06-27. 15. [Duchi, 2016] John C. Duchi. Introductory lectures on stochastic convex optimization. Park City Mathematics Series, Graduate Summer School Lectures, 2016. 16. [Dvoretzky et al., 1956] A. Dvoretzky, J. Kiefer, and J. Wol- fowitz. Asymptotic Minimax Character of the Sample Dis- tribution Function and of the Classical Multinomial Esti- mator. The Annals of Mathematical Statistics, 27(3):642 - 669, 1956. 17. [Fan et al., 2008] Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. J. Mach. Learn. Res., 9:1871-1874, June 2008. 18. [Frei et al., 2021] Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners to strong learners in mixture models. CoRR, abs/2106.13805, 2021. 19. [Grandvalet and Bengio, 2005] Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimiza- tion. In L. Saul, Y. Weiss, and L. Bottou, editors, Ad- vances in Neural Information Processing Systems, vol- ume 17, pages 529-536. MIT Press, 2005. 20. [Joachims, 1999] Thorsten Joachims. Transductive inference for text classification using support vector machines. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML '99, page 200-209, San Fran- cisco, CA, USA, 1999. 21. [Johnson et al., 2020] David S. Johnson, Lee Breslau, Ilias Diakonikolas, Nick Duffield, Yu Gu, MohammadTaghi Hajiaghayi, Howard J. Karloff, Mauricio G. C. Resende, and Subhabrata Sen. Near-optimal disjoint-path facility location through set cover by pairs. Oper. Res., 68(3):896- 926, 2020. 22. [Krijthe, 2017] Jesse H. Krijthe. Rssl: Semi-supervised learning in r. In Bertrand Kerautret, Miguel Colom, and Pascal Monasse, editors, Reproducible Research in Pat- tern Recognition, pages 104-115, Cham, 2017. Springer International Publishing. 23. [Li and Zhou, 2011] Yu-Feng Li and Zhi-Hua Zhou. To- wards Making Unlabeled Data Never Hurt. In Proceedings of the 28th International Conference on Machine Learn- ing, pages 1081-1088, 2011. 24. [Massart and Nédélec, 2006] Pascal Massart and Elodie Nédélec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326-2366, 10 2006. 25. [Maximov et al., 2018] Yury Maximov, Massih-Reza Amini, and Zaïd Harchaoui. Rademacher complexity bounds for a penalized multi-class semi-supervised algorithm. Journal of Artificial Intelligence Research, 61:761-786, 2018. 26. [Montasser et al., 2020] Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learning ad- versarially robust halfspaces with noise. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th Interna- tional Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 7010- 7021. PMLR, 13-18 Jul 2020. 27. [Niyogi, 2013] Partha Niyogi. Manifold regularization and semi-supervised learning: Some theoretical analyses. Journal of Machine Learning Research, 14(1):1229-1250, 2013. 28. [Rigollet, 2007] Philippe Rigollet. Generalization error bounds in semi-supervised classification under the clus- ter assumption. Journal of Machine Learning Research, 8:1369-1392, 2007. 29. [Singh et al., 2009] Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn't. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, edi- tors, Advances in Neural Information Processing Systems, volume 21. 30. Curran Associates, Inc., 2009. 31. [Wei et al., 2020] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. CoRR, abs/2010.03622, 2020. 32. [Wei et al., 2021] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In 9th International Conference on Learning Representations, ICLR 2021, Vir- tual Event, Austria, May 3-7, 2021, 2021. 33. [Wolfe, 2012] Douglas A. Wolfe. Nonparametrics: Statisti- cal Methods Based on Ranks and Its Impact on the Field of Nonparametric Statistics, pages 1101-1110. Springer US, Boston, MA, 2012. 34. [Zhu and Ghahramani, 2002] Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical report, CMU-CALD- 02-107, Carnegie Mellon University, 2002. 35. [Zhu, 2005] Xiaojin Zhu. Semi-supervised learning litera- ture survey. Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, 2005.