Learning From Biased Soft Labels
Authors: Hua Yuan
Yu Shi
Ning Xu
Xu Yang
Xin Geng
Yong Rui
Venue: NeurIPS 2023 poster (2023)
Keywords: Soft label; knowledge distillation; weakly-supervised learning; Machine learning.

Abstract: Since the advent of knowledge distillation, many researchers have been intrigued by the $\textit{dark knowledge}$ hidden in the soft labels generated by the teacher model. This prompts us to scrutinize the circumstances under which these soft labels are effective. Predominant existing theories implicitly require that the soft labels are close to the ground-truth labels. In this paper, however, we investigate whether biased soft labels are still effective. Here, bias refers to the discrepancy between the soft labels and the ground-truth labels. We present two indicators to measure the effectiveness of the soft labels. Based on the two indicators, we propose moderate conditions to ensure that, the biased soft label learning problem is both $\textit{classifier-consistent}$ and $\textit{Empirical Risk Minimization}$ (ERM) $\textit{learnable}$, which can be applicable even for large-biased soft labels. We further design a heuristic method to train Skillful but Bad Teachers (SBTs), and these teachers with accuracy less than 30\% can teach students to achieve accuracy over 90\% on CIFAR-10, which is comparable to models trained on the original data. The proposed indicators adequately measure the effectiveness of the soft labels generated in this process. Moreover, our theoretical framework can be adapted to elucidate the effectiveness of soft labels in three weakly-supervised learning paradigms, namely incomplete supervision, partial label learning and learning with additive noise. Experimental results demonstrate that our indicators can measure the effectiveness of biased soft labels generated by teachers or in these weakly-supervised learning paradigms.

Learning From Biased Soft Labels
Hua Yuan 1.2 Yu Shil.?, Ning Xul 1.2 Xu Yang! 12 Xin Gengl.2. 1.2- Yong Rui
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China Key Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications (Southeast University), Ministry of Education, China
Lenovo Research, Beijing 100085, China kyunnhua,seushiv xninhhiyy,,xiing..ooo xuyang-paar palm, Xseng edu. cn, vongrui@lenov..oo
Abstract
Since the advent of knowledge distillation, many researchers have been intrigued by the dark knowledge hidden in the soft labels generated by the teacher model. This prompts to scrutinize the circumstances under which these soft labels are effective. Predominant existing theories implicitly require that the soft labels are close to the ground-truth labels. In this paper, however, biased soft labels are still effective. Here, bias refers to the discrepancy between indicators measure
investigate whether
the soft labels and the ground-truth labels. We present the effectiveness of the soft labels. Based on the two indicators, we propose moderate conditions ensure that, the biased soft label learning problem is both classifie--oonsittrr and Empirical Risk Minimization (ERM) learnable, which can be applicable even for large-biased soft labels. We further design a heuristic method to train Skillful but Bad Teachers (SBTs), and these teachers with accuracy less than 30% can teach students to achieve 90% accuracy on CIFAR-10 10, which is comparable to models trained on the original data. The proposed indicators adequately measure the effectiveness of the soft labels generated in this process. Moreover, our theoretical framework can be adapted to elucidate the effectiveness soft labels in three weakly-supervised learning paradigms, namely incomplete supervision, partial label learning and learning with additive noise. Experimental results demonstrate that our indicators can measure the effectiveness of biased soft labels generated by teachers in these
learning paradigms.
Introduction
17 20 has achieved remarkable achievements in a wide range of applica- tions. It has emerged as popular paradigm for model compression [22] 211 and transfer learning [1 34 by distilling knowledge from the big model (teacher) to the small model (student). Students inherit the knowledge of the teacher by imitating the soft labels generated by the teacher model. Many experiments show that learning from soft labels can be very effective, even surpassing learning from ground-truu labels 2 17 33]. However, there are still many mysteries why these soft labels are effective. Most existing theories do not apply to soft labels that significantly deviate from the ground-truth labels and lack explicit indicators to evaluate the soft labels (39 58 (35). In this paper, we mainly focus on the effectiveness of the biased soft labels, especially large-biased soft labels.
Knowledge distillation 2
It significant study the effectiveness of biased soft labels. Firstly, expert-labeled annotation typically requires a substantial investment of manpower and time. But the soft labels in weakly supervised learning could be cheap and biased (59]46) 46). Evaluating the biased soft labels instructive for weakly supervised learning. Secondly, these biased soft labels can apply for privacy protection
"Correponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.0
1,0
cras
0.6
0.6
120
3
indexes
(a)
(b)
(c)
Figure 1: (a) Images of the birds in CIFAR-10. (b) An example of the soft label for "Bird" in Yuan et al. [53] (c) An example of the large-biased soft label for "Bird". Compared with Yuan et al. [53], the value of the ground truth label (Bird) in the large-biased biased soft label is probably much smaller, and is likely not the top of the targe-biased soft label.
15 When they are employed for subsequent training, they can conceal the ground-trun -ruth labels. is consistent with the requirements of privacy and utility privacy protection [27].
After realizing the significance of biased soft labels, we study the biased soft labels and reveal that large-biased soft labels can also teach good students. This phenomenon inspire to seek indicators to measure the effectiveness of soft labels. As result, we propose two intuitive indicators, namely unreliability degree and ambiguity degree. The intuition behind them to convert the soft label into a top-k set (A: is a constant), which contains the top-k labels of the soft label. Unreliability degree is the probability that the ground-truth label
in the top-k set while ambiguity degree the upper bound of the probability that the incorrect label and the correct label co-occur in the top-k set.
Furthermore, based the proposed indicators, present moderate conditions ensure that, the biased soft label learning problem is (ERM) learnable [6]. The former guarantees that the learners can converge the optimal solution as learning from original labeled data. The latter implies that learners' performance can generalize to the entire data distribution. Our theory not only guarantees the effectiveness of biased soft labels, but also provides explicit indicators to evaluate the soft labels.
28 and Empirical Risk Minimization
Biased soft labels are prevalent in weakly supervised learning 24 44 [5]] and our theory can offer theoretical insights for these paradigms. In detail, we apply the theory to three classic weakly- supervised learning paradigms: incomplete supervision [3), partial label learning [5] and learning with additive noise [10]. In these wrekkl--supervisee learning paradigms, soft labels are biased and
provide theoretical guarantee for the learners in these fields. In other words, we prove that the biased soft labels in the three paradigms are effective to train a good model.
It is important to note that, Yuan et al. 53 argues that poorly-trained teachers can teach good students. In fact, their soft labels are mixture of the teacher's outputs and the ground-truth labels with ratio of 0.1 0.9, which makes the soft labels close to the ground-truth labels as illustrated in Figure bb) Differently, our experiments reveal that large-biased soft labels can also teach good students. Furthermore, the effectiveness of these soft labels can be measured by unreliability degree and ambiguity degree. In addition, experiments on three superviseeee learning paradigms also demonstrate that biased soft label learning problem is learnable and the proposed indicators effective. Our contributions can be summarized as follows:
We find that learning from biased soft labels may also achieve comparable performance and intend to explore the underlying mechanisms behind the effectiveness of the biased soft labels.
Two indicators have been proposed to measure the effectiveness of soft labels. Based on the indicators, we present moderate conditions to guarantee the effectiveness of the soft labels. It is proved that the biased soft label learning problem is classifier- and ERM learnable.
A heuristic method is designed to train skillful but bad teachers, i.e., teachers with low accuracy but who can teach good students. We can explain this phenomenon with unreliability degree and ambiguity degree.
The theory provides theoretical view for the learners in three -sueri--upereiieed learning paradigms. Specifically, we provide theoretical guarantees for the learnability of these paradigms from the perspective of soft labels. Experimental results are consistent with our theory.

---

2 Related Work
Knowledge Distillation and Label Smoothing Knowledge Distillation (KD) was initially proposed
in model compression [22 21 and then applied to transfer learning 41 34 There is growing interest in why distilling can transfer information and what the dark knowledge hidden in the soft labels is. Furthermore, the dark knowledge also exists in the variants of knowledge distillation, which are introduced in the appendix [ Label Smoothing (LS) (38 is a regularization method to improve performance by mixing the uniform noise into the ground-truth label. It is convinced that soft labels can restrain overconfidence of the student model. Essentially, both KD and LS can be unified as learning from soft labels Yuan al. (53
Label Enhancement Label Distribution Learning (LDL) [3] was proposed to exploit the label distribution to mirror the relationship between the label and the instance, where the formalization of the label distribution is identical to the soft labels mentioned above. In the remainder of the paper, we use nomenclature soft labels. Due to the high cost of labeling the soft labels, Label Enhancement (LE) [48] was proposed to recover the soft label from the logical label by exploiting the implicit correlation among different labels. Numerous novel algorithms have been designed in recent years that aim to improve the predictive model with the soft labels [4 57 Wang and Geng [42 applied the margin theory the soft labels and designed the adaptive margin loss.
In fact, most existing explanations of the soft labels are empirically and experimentally validated, while the rigorous theoretical analyses usually have strong assumptions regarding the model or data distribution. Phuong and Lampert (55) explored the mechanism of distillation where the teacher model and the student model are linear. Allen-Zhu and Li (I supposed that the instance could be decomposed into multiple independent features and had a linear relationship with the sample, and then proved the effectiveness of the soft labels. Wang and Yoon 43] solved the objective functional problem of self-distillation with the Green's 's function, which assumes that the network can reach the optimal solution. Menon et al. (31) and Zhou and Song (58] regarded the generated soft labels the posterior probability and assumed the existence of the Bayes probability. There is also some work analyzing soft labels from the perspective of transfer risk [9, [8. Most existing theories suggest that students can achieve good performance only when the soft labels are close to the ground-truth labels, and lack explicit indicators measure the effectiveness of the soft labels.
3 Methodology
3.1 Preliminary
Let X' be the instance space, y f1,2..... be the label space with classes and A be the soft-label space over V i.e., A = {d E R E.Ey d, = 1, d, 2 0 for all i E y}. Define D as the data distribution over X' x y and H. as the hypothesis space from X' to V. Each h H. is called the learner or hypothesis. When h E H is a neural network, it often employs a softmax function in the final layer and takes the highest value the prediction. Slightly abusing notation, we use h((:)) E A to denote the soft label generated by model h. and h(x) E 3 represent the model's prediction.
Next, we introduce some important concepts in the Probably Approximately Correct (PAC) learn- ing 40 The Natarajan dimension [32] was proposed to characterize the capacity of multiclass hypothesis spaces and we denote dx as the Natarajan dimension of H. The expected classifica- tion error of hypothesis h H is defined as (ry x (Th(ar) # v)]. where T(.) is the indicator function. Given a finite dataset z, the empirical classification error is defined as Err, & (h) = _ Σm I(h(z) # y). The Empirical Risk Minimization (ERM) leamne ERM is defined
as h FRMM_ = arg min Err (hl while the optimal learner h² is defined as h = arg min Errp (h).
NEW
Considering that this study involves two models: generating soft labels and learning from the soft labels. To avoid ambiguity, we use f to represent the model generating soft labels (teacher) and h to denote the model trained with soft labels (student). It should be noted that f E H can be neural network or a map based on certain rules, such as label smoothing.
In order to gain a deeper insight into the concept of biased soft labels, we have provided precise definitions for relevant terms below. These definitions may not have direct correlation with the theoretical analysis presented in section 3.2 but they serve to elucidate the boundaries of our research.
3

---

Definition 1 (Bias of soft labels), Give dataset DD consisting of n. samples. the feature vector for the i-th sample denoted as 2, and the corresponding label is denoted as ys. Let represent model or a mapping rule. The bias of the soft labels generated by I on dataset D is
1 T2 E (x.)).
Bias( (fas(f D)
where f,, (xx.) refers to the component of the soft label f(x;) that corresponds the true label yı- Definition Laarge-biased soft labels). Soft labels generated by I on dataset 'D is called biased soft labels when Bias f, D) > O and called large-biased soft labels when Bias f, D) 2 1.
The bias, as defined here, essentially represents the disparity between the soft label and the true label. Here, we employ the Manhattan distance, also referred to as LI-norm, although other metries can also be suitable. A threshold of Bias 2 is employed to categorize soft labels "large-biased.' In practical scenarios, the choice the threshold can be adapted based on specific contexts. After establishing the concept of large-biase biased soft labels, we proceed to define "bad teachers."
Definition 3 (Bad teachers). We define f as bad teacher if the soft labels it generates on dataset 'D are large-biased. Typically, 'D is the training set for f.
The definition of the bad teachers is based on the definition of large- biased soft labels. Similarly, here we adapt as the boundary value for bad teachers. It's important to note that when we use "good/bad"" to describe teachers, we are referring to the performance of teachers on the dataset D. the other hand, when we say teachers are "skillful," we are emphasizing that they are adept at instructing students, leading to excellent student performance. Due to the fact that the performance of the student model contingent on both the model structure and the complexity of the dataset, we unable to establish precise boundaries for "skillfuul teachers." In this context, 'skillful' merely signifies that the teacher produces students with acceptable performance.
3.2 Theoretical Analysis of Soft Labels
In this subsection, we define two indicators, unreliability degree and ambiguity degree, to measure the effectiveness of soft labels. Based on these indicators, we present moderate conditions to ensure that the biased soft label learning problem is classifer-consistentt and Empirical Risk Minimization (ERM) learnable. The underlying intuition behind the indicators is to convert the soft label into a set. Let (d) {i E y/ ranks top-k in d} be the set of top k labels in the soft label d. Here, & is constant ranging in {1, c 1}. When & = 1, S2 (d) has only one element, i.c., the prediction. For soft labels generated by teacher we define the unreliability degree as,
na (f) = PI(m.))~xxx(( (y/ & (f))))
However, it is not enough to measure the soft labels by merely unreliability degree. For example, for images whose ground-truth labels are 1, if label 2 always appears in (d), then the student model unable distinguish label from label Therefore, we introduce the ambiguity degree and extend it to more general soft labels (induced by teacher f)
Y% (f) max (X(ma))xxXxxx1 (f(x))) .E
(2) Ambiguity degree bound the probability of co-occurrence. In other words, if a model f is with v, S (f()). The smaller or y is, the
ambiguity degree (f), then Pr(i E (x(f(=))) & more effective the soft labels are. However, when k increases, will decrease and is inverse, which means should be selected cautiously.
Theorem 1. Training with soft labels generated by the teacher model J. if < 1 mc( then the optimal student model h" H. satisfies h" arg min Errp(h)f).
I-me(h)
NEW
The proof can be found in A.2 Theorem ensures that the student model h learning from the teacher can converge to the optimal learner over the entire data distribution. This property is known as classifir-consisteenyy [12. However, it does not provide the sample complexity bounds of the learning problem. In other words, does not establish a connection between the generalization bound and the number of training samples.

---

Next, we provide our main result, a sufficient condition for the ERM learnability of the biased soft label learning problem. In the previous subsection. we presented the definition of expected classification error and empirical classification error, which are based on the label space y: Here, given the soft label generating model f. we define the soft label-based expected error
Err ff = (z [()()))))))))) $ Su (f()))))
and the soft label-based empirical error on dataset z (1.,, 9:)
1 n2 Σ I h (x:) & Oa(f))))))
Err (m(f) (
In the above equations, the set 94 (fx;)) is determined by the soft label f(x,). We denote H, as the set of teacher models whose generated soft labels are with unreliability degree 1), i.e., H, = { m: (J) 7) With such soft labels, analyze the performance of the ERM learners (students). The definition of the ERM learner is provided in the preliminary. Specifically, based on the unreliability degree in (1) and the ambiguity degree in (2), we provide sufficient condition ensure that, the biased soft label learning problem is ERM learnable.
Theorem 2 (Main theory). For k E f1.2.....c. ........-.. 1}, assume the unreliability degree (f( and the ambiguity degree "/o (f( of the soft labels generated by teacher model f, denoted concisely Tr and The and satisfy O < Tj, 7k < and тe + 7 < 1. Let 0g log 2(1-76). and suppose the Natarajan dimension of the hypothesis space is dx. Define
{
2
no (H,
min kE(1,2.....-
(dx((og(2dx)
Bye 2
+ log 2 2-2m
2 log L) + +og + 11}
log OuE log 2-2ma
2
Then when n. > no, the ERM learner satisfies (h (f) < e with probability 5.
The proof can be divided into lemmas. Let define H. be the set of hypotheses with emror least e, i.e, H = {h E H (rr f) 2 E}. Our target is to bound the probability Pr(h E H2), which measures the generalization of the learner h. Since the entire soft label space is inaccessible, Hg is evaluated by the mediator Rn,e as follows:
R {z (X 31"h 3h H3, ( 0}
Then, our goal is to prove that Pr(z E Ru,s E H,,) S 6. In other words, given dataset 2, the student model h has the generalization bound greater than with probability at most 8. Since the teacher model f is intractable and the soft label space A is unknown, it is very difficult directly calculate the conditional probability Pr(z E RY,s f E Hn). We bound it by introducing a testing set z'. Lemma I is adapted from [19] Lemma 11.1.5] and [[16], Corollary 2.6].
Lemma 1. For a testing set z' E (X x y)", we can define the set Sn,e as
Sn.s = (z,,z') E (X x 2) 3h E He, EIT (N).f) = 0, ErT. (hl 2
E
2
Then, we have Pr((z,z') Sn,e If H.)) ž Pr(z R f H.
8 8log
The proof of Lemma I can be found in appendix A.3 With lemma | we just need to estimate Pr((z, z') E Sn.e / E Hy)) It seems more complicated to introduce the testing set z' but we can swap training/testing instance pairs, which is classic method in the proof of learnability, to refine the data distribution on x y into each single instance.
Lemma 2. On the same condition of theorem
2 we have
noe
Pr ((z,z') Sn,e E Hl) < (2n) 2dn exp
2
The proof of Lemma can be found in appendix A.4 Thcorem 2 which is detailed in the appendix A.5
With Lemma Tand Lemma we can prove
5

---

In this section, we establish two essential properties of the soft labels. Classifier-consiserni guaran- tees the effectiveness of the soft labels macroscopic perspective, and ERM learability provides a microcosmic generalization bound for the student model h. The corresponding threshold conditions are presented to ensure the student model can learn from the soft labels. The theory is applicable to all biased soft labels. This inspires us to consider that accuracy alone may not be a sufficient measure of a teacher's 's teaching ability. In the section5.11 we design a simple heuristic algorithm to generate such skillful but bad teachers, i.e., teachers with low accuracy but can teach good students. These results are illustrative for the comprehension and development of the soft label based algorithms.
Biased Soft Labels in ReakklySupervised Learning
The labels in reakly-supervised learning (WSL) could be incomplete, inexact, inaceurate [59] because accurate annotation is often expensive and difficult to obtain. Soft labels are widely used in WSL. Many weakly-supervised learning paradigms can be transformed into learning from soft labels. Due to the lack of the supervisory information, the soft labels could be large-biased but the model can still learn from them. In this section, our theory is adapted three classic weakly-supervised learning paradigms and can provide theoretical guarantee for the learnability of these problems. These findings reflect that the theory is promising and extensible.
4.1 Incomplete Supervision
In incomplete supervision, there are labeled data and unlabeled data. A common approach is to use the model label the unlabeled data and then learn with all data iteratively. The soft labels of the unlabeled data are probably biased but make a significant contribution to the training process. We propose an ideal accuracy function and, based on supervision from the perspective of soft labels. Suppose there are labeled data and M unlabeled data sampled from X' x V. The predictive model h is an ERM learner on both labeled data and unlabeled data. The label of unlabeled data will be updated iteratively.
provide theoretical analysis on incomplete
Assumption 1. For labeled data and M unlabeled data whose soft labels have unreliability degree n and ambiguity degree % the ERM learner h has deterministic accuracy funtion p(n, 7). the probability that h predict correctly. The model architecture, data distribution and optimization implicitly included in p(n:"))
Assumption 2. Given that smaller values of n or 7i result in more supervised information in the soft labels, we assume p(]], 7) decreases with r) and y.
We suppose that the incorrect labels share the equal probability to appear in the top-k set. The distribution of the incorrect labels can be characterized a more refined manner. For instance, assume that there is a upper bound of p())) p(]=) j, E V,i,j + y # j. We employ simplified assumptions because they can still capture and reflect this process. Based on the ideal p(n), 7), we delineate the progressive performance of h. Let Pt. denote the accuracy of h at epoch and we have
c c-k Pt
Pr+1 2 p(1 Pt:
In practice, as learner h learns from labeled data and unlabeled data, the performance of h will improve and the soft labels of the unlabeled data will be more effective. Consequently, h and the soft labels may achieve dynamic equilibrium.
Theorem 3. Based the ideal accuracy function p( 7), with a moderate initial state Tjo To satisfying Theorem 2 if final accuracy of Pjmmal exists, il can be calculated by the following fixed point equation:
= p(1
C
where k accords with the top-k set in y and 7/, e is the number of class labels. If Pf 7)) is k, Lipschitz continuous (kr, < 1 - -. then Pfinal exists and is unique.
The proof is detailed in A.6 In fact, the deterministic p(n,, 7) is unattainable due to the indeterminacy of the optimization and the potential uncertainty the data distribution. An intuitive extension is to assume p(1z, 7) is probability distribution related to the training specifics, which can be

---

further investigated. Theorem 3 is coarse yet in agreement with the general intuition. The model h improves as the soft labels envolve and finally reach the bottleneck restricted by the model, data and optimization.
In this section, we demonstrate the potential benefits of our theory in several classic weakly-supervised learning paradigms, There remain numerous domains associated with soft labels. It is essential to possess an appropriate theory to analyze the soft labels for the corresponding algorithms. Our theory can be instrumental for comprehending and constructing the soft label based algorithms.
4.2 Partial Label Learning
In Partial Label I Learning (PLL), each instace is typically assigned set of possible labels, i.e., the
candidate label set 8 [28 46, 49). The corresponding candidate label space denoted by S, i.e. the non-empty power set of V. Traditional PI.L assumes the ground-truit truth label must be in the candidate label set. But recently, Lv et al. [29 considers that ground-trute truth label could be not in the candidate label set, which is named as Unreliable Partial Label Learning (UPLL).
In UPLL, there are two basic concepts, partial rate v and unreliable rate μ. Partial rate v is the ratio of incorrect labels in the candidate label set to total labels. A lower partial rate usually indicates better performance of the model. Unreliable rate μ the probability of ground-truth label y not in the candidate label set, which can be formally stated as
μ (.(x...))) $ 8).
The discrete candidate label set can be transformed into the soft label by
E
|
i
where [s] is the cardinality of set s. So PLL also can be viewed as learning from biased soft labels. Then we have the following corollary.
Corollary For UPLL with partial rate v and unreliable rate μ. regard the generated soft labels as teacher. Then, we have I and v. With the same conditions in Theorem 2 UPLL is ERM learnable and the sample complexity remains unchanged.
This corollary show that UPLL is ERM learnable under a moderate condition. We provide new insights from the perspective of soft labels.
4.3 Learning with Additive Noise
is an important methodology for differential privacy. Specifically, Laplace noise or Gaussian noise is added to data for protecting privacy. The privacy budget can be controlled by adjusting the scale of the noise. After normalization, the noisy labels are also biased soft labels in nature. In fact, given the probability density function of noise, can calculate the corresponding unreliability degree and ambiguity degree order to measure the effectiveness of the noisy labels. With the biased soft labels. the task is to train a utility model with strong privacy guarantees. Our theory can guarantee the utility of such soft labels.
Additive noise mechanism 30 14
To calculate unreliability degree and ambiguity degree, we refer to order statistic 8 Order statistic analyze the ith-smallest value of random samples from a continuous distribution. We denote the order distribution Order(d, dd, i) as the ith-smallest value of samples from distribution d. The software Mathematics [45] provide an efficient API for estimating the order distribution.
Corollary 2. Let d denote the noise distribution (e.g. Laplace noise and Gaussian noise) and regard the noisy soft labels as the teacher. With the in Eq and the total classes e, for k I we can compute the and y as
1 Pr -.. (1 yy+ x), and
k 1
With the same conditions Theorem the problem learning with additive noise is ERM learnable and the sample complexity remains unchanged.
7

---

22
74
60
Proposed Indd catorn
Acc0l)
Acc200
40
80
18
30
70-
Ade
Adg
0.71
Accuracy
Accuracy
(8)
(a)
(b)
Acc ofe student (8)
55
40
indicatoro (4)
35
50
30
25
45
20
31
33
34
Accuracy of the soft labels teachers (%)
(c)
Figure 2: Indicators of soft labels generated by SBTs on CIFAR-IO (a), CIFAR-100 (b) and Tiny ImageNet (c), Acc represents the accuracy of the student model trained with the biased soft labels. Unreliability degree (J) and ambiguity degree (f) are the two indicators proposed in our study.
As the scale of the noise increases, 77 and y will increase, i.e., the effectiveness of the soft labels will decrease. This result agrees with the practical situation.
5
Experiments
Our experimentally investigate whether biased soft labels are still effective and whether the proposed indicators can measure the effectiveness of these soft labels, which consist of three parts. Firstly, we design simple heuristic algorithm to generate Skillful but Bad Teachers (SBTs), which have low accuracy (less than 35%) but can teach good students. Secondly, experimental results demonstrate that students learning from SBTs can achieve comparable performance as models trained on the original data. We can explain these phenomenons with unreliability degree and ambiguity degree. Thirdly, we conduct experiments in weakly-supervin unreliability degree and ambiguity degree can reflect the effectiveness of the biased soft labels. Due to space limitations, we present a part of experimental results the appendix. Additionally, we provide the details of the experiment setup in appendix A.7
learning paradigms, and the results also confirm that
5.1 Skillful but Bad Teachers
In this subsection, we introduced the design of the SBTs. The intuition behind SBTs, inspired by Theorem
2 is to inhibit correct predictions and reduces the unreliability degree and ambiguity degree simultaneously. So we design some heuristic loss functions and have some hyperparameters that qualitatively control the unreliability degree and ambiguity degree. More specifically, the designed loss functions are intended to keep the ground-truth label within the top-k set of the soft labels, without necessarily requiring it to be at the top. Here, k is an empirical constant, which we have set to in training SBTs.
Firstly, SBTs will punish those correctly predicted instances as
L (z. y) - ((argmax(d.)) y)((f(m))))
jEy

---

100
50
100
Proposed Indi cators (10)
30
Ass2%)
60
85
45
28
40
Ado [V71
Adc
0671
Gaussian
Variance the Gaussian
(a)
(b)
Figure 3: Indicators of learning with Gaussian noise on CIFAR-I0 (a) and CIFAR-100 (b).
where -):-) is the cross entropy loss function. In practice, the value of the ground-truth label decreases significantly, which causes the ground-truth label to fall out of the top-k set, i.e., large V)--
So the ground-truth label y is compensated when y & 9 (fx)))
Coump (z, 3) Myy & (f((())))(((())
(6)
The compensation term is designed improve the top-k accuracy of SBTs, which keeps the statistical effectivenees of the soft labels generated by SBTs. In practice, we found there was a strong correlation among the top-k labels, which leaded to the confusion between the ground -ruth label and similar labels, i.e., large "/k- To decrease this correlation, we propose an effective method to make the labels in 22 (f (a:) as independent as possible. We randomly select k labels except the ground-trute label Then the selected k 1 labels are employed as the learning objectives:
(x, y) {(f(x), Sma)).
where Smd is the set of the k - random labels excluding y. Consequently, the total objective of SBTs as follows:
C( v) Lee (x,, (x, u) + ai (ar v) + or2 Com (20 v) mm y)
(8)
where (a y) the vanilla cross-entropy loss between the output the model and the ground-truth label, and 01, a2 are the trade-off parameters.
5.2 Effectiveness of the Proposed Indicators
In this subsection, our aim is to demonstrate that, despite the soft labels generated by SBTs large-biased, students still achieve high accuracy. As outlined Ta the appendix, we adapt four different classic metrics: Chebyshev distance, KL divergence, Manhattan distance, and Euclidean distance. These metrics are employed to measure the discrepancies between the aargebiassed soft labels generated by SBTs and the ground-trute truth labels. The soft labels generated by SBTs exhibit substantial differences when compared to those from normally trained teachers. Nevertheless, they remain effective in instructing good students. It should be noted that the accuracy of the students mirrors the effectiveness of the soft labels. However, accuracy is an indirect measure contingent on the student model. The proposed unreliability degree and ambiguity degree directly measure the effectiveness of these soft labels. The smaller the unreliability degree and ambiguity degree, the more effective the soft labels, and subsequently, the students' accuracy tends be higher. This phenomenon is illustrated in Figure which agrees with our expectations.
In the experiments, set 1 4 for unreliability degree Th and ambiguity degree ?x((f) (I in the indicators can be different from & in training SBTs). Since mh (f) and (x()) are probabilities over the entire data distribution X' ) and difficult to compute, the generated soft labels on the test data. Note that training with the ground-truth labels can achieve accuracy 95. 29% CIFAR- 10, 78. 13.%% CIFAR- 100 and 72.53% Tiny ImageNet. We find many interesting results in Figure 2
estimate them empirically by the
When these soft labels are generated by SBTs with accuracy less than 30%, which means they are quite different from the ground-truth labels, the students can still achieve accuracy much higher than the teachers.

---

As (f) and (f) decrease, Acc (i.e., accuracy of the student) increases. The proposed indicators exhibit an inverse correlation with the students' accuracy, which reflects the effectiveness of the proposed indicators.
For the more complicated dataset like CIFAR-100 and Tiny ImageNet, accuracy (Acc) is more sensitive to (f) and (fx( This implies that, for more complex tasks, the quality of the annotation is more crucial.
The hyperparameters in Eq. are pivotal in controlling the indicators of these soft labels, which is elucidated in A.8 Furthermore, we conducted experiments to investigate whether the effectiveness of soft labels influenced by different model backbones, as detailed A.9 We tested a range of architectures including wideresnet 28x2, 28x4, 40x2, and 40x4. The four distinct backbones exhibited consistent patterns, indicating that the proposed indicators are effective across different backbones. In addition, we present the overall distribution of these soft labels in A.10 The experimental results demonstrate that biased soft labels can also teach good students and the proposed indicators can measure the effectiveness of these soft labels, which confirm the validity of our theory.
5.3 Biased Soft Labels in Weakly-Superviee Learning
The aforementioned weakly-superviiet learning paradigms have engendered a lot of specialized algorithms. The intention of this paper is not to devise more efficacious algorithms, but to evaluate the effectiveness of the soft labels in the weakly-supervised learning paradigms by unreliability degree and ambiguity degree. The results of partial label learning shown in Ta- [ while the results of learning with additive noise are shown in Figure 3 Due to space lim- itations, the results of incomplete supervision are shown in I] From the three experiments, we can observe that the accuracy of the students decrease when unreliability degree and ambigu- ity degree increase. All the results reflect that these indicators can measure the effectiveness of the soft labels well, which is consistent with our theory. In addition, since the soft labels in partial label learning and learning with additive noise are generated by a mapping rule rather than neural network, the results of these experiments are more stable and smooth.
Table 1: Students learning from partial labels.
Dataset
7k(F)
ma(F)
Student
0.1
0.1
93.98
0.1
0.3
93.38
0.1
0.5
91.94
0.3
0.1
90.38
CIFAR-10
0.3
0.3
88.59
0.3
0.5
86.
0.5
0.1
85.11
0.5
0.3
82.05
0.5
77.95
0.01
74.19
0.01
0.3
73.16
0.01
0.5
72. 29
0.05
0.1
68.08
CIFAR-100
0.05
0.3
66.28
0.05
0.5
63.69
0.1
0.1
61.18
0.1
0.3
58.6
0.1
0.5
52.41
6 Conclusion
In this paper, we find that even large-biased soft labels can teach a good student and focus on the effectiveness of the biased soft labels. It motivates us to rethink when the biased soft labels (or teachers) are effective. We propose two indicators, unreliability degree and ambiguity degree, to measure the effectiveness of soft labels. Based on the proposed indicators, conditions that guarantee the classifier-consistenny and ERM Icarnability of the biased soft label learning problem. Our theoretical framework can be adapted elucidate the effectiveness of soft labels in three weakly-superrised learning paradigms, incomplete supervision, partial label learning and learning with additive noise. We design a heuristic method to train Skillful but Bad Teachers (SBTs), which validate that large-biased soft labels can teach good students. Besides, the effectiveness of both soft labels generated by SBTs and soft labels in the weakly-supervised learning paradigms can be measured by the proposed indicators well, which is consistent with our theory.
provide moderate
10

---

Acknowledgement
This work was supported by the National Key Research & Development Plan of China (No. 20 2018AAA0100104), National Science Foundation of China (62125602, 62076063, 62206048), Natu- ral Science Foundation of Jiangsu Province (BK20220819), and Young Elite Scientists Sponsorship Program of Jiangsu Association for Science and Technology Tj-2022-027.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self- distillation in deep learning. CoRR, abs/2012.09816, 2020.
[2] Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 535 5511, 2006.
[3] Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-supervised learning (chapelle, al., eds.; 2006)[book reviews]. JEEE Transactions on Neural Networks, 20(3):542 542, 2009.
[4] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 201
[5] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2.1
[6] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwarle Multiclass learnability and the erm principle. In Proceedings the 24th Annual Conference Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
[7] Tri Dao, Govinda M Kamath, Vasilis Syrgkanis, and Lester Mackey. Knowledge distillation semipara- metric inference. International Conference on Learning Representutions, 2020.
[8] HA David and HN Nagaraja. Order statistics. Encyclopedia Statistical Sciences, 2004.
[9] Richard M Dudley, H Kunita, F Ledrappier, and RM Dudley, A course on empirical processes. In Ecole d' ééééé de probabilités de Saint-Flour XII-1982, pages 1-142. Springer, 1984.
[10] Cynthia Dwork, Frank McSherry, Kohhi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptogruphy Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[12] Lei Feng. Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning, Advances Neural Information Processing Systems, 33:10948-10960. 2020.
[13] Xin Geng. Label distribution learning. IEEE Transactions Knowledge and Data Engincering, 28(7): 1734-1748, 2016.
[14] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi. and Chiyuan Zhang. Deep learning with label differential privacy. Advances Neural Information Processing Systems, 34:27131-271455 2021.
[15] Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. Advances neural information processing systems, 34:27131-27144 145,, 2021.
[16] Evarist Giné and Joel Zinn. Some limit theorems for empirical processes. The Annals of Probability, pages 929 9899 1984.
[17] Geoffrey Hinton, Oriol Vinyals, Jeff Dean, et al. Distilling the knowledge in neural network. CoRR, Abs/1503.02531, 2015.
[18] Daniel Hsu, Ziwei Ji. Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. arXiv preprint 214.00064444 2021.
[19] Guangda Ji and Zhanxing Zhu. Knowledge distillation in wide neural networks: Risk bound, data efficiency and imperfect teacher. Advances in Neural Information Processing Systems, 13:20823-20833, 2020.

---

[20] Zhong Ji, Jingwei Ni, Xiyao Liu, and Yanwei Pang. Teachers cooperation: team-knowledge distillation for multiple cross-domain few-shot learning. Frontiers of Computer Science, 17(2):172312, 2023.
[21] Qing Jin, Jian Ren, Oliver J Woodford, Jiazhuo Wang. Geng Yuan, Yanzhi Wang, and Sergey Tulyakov. Teachers more than teach: Compressing -mage-to-image models. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13600-13611 2021.
[22] Jangho Kim, ScongUk Park, and Nojun Kwak. Paraphrasing complex network: Network compression via factor transfer. Advances in neural information processing systems, 31, 2018.
[23] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[24] Dong-Ilyun Lee et al. Pseudo-label: The simple and efficient seni-superrised learning method for deep neural networks. In Workshup challenges in representation learning, ICML, volume 3, page 896, 2013.
[25] Hankook Lee, Sung Ju Hwang, and Jinwoo Shin. Rethinking data augmentation: Self-supervision and self aaff-ditillattion CoRR, abs/1910.05872. 2019.
[26] Liping Liu and Thomas Dietterich. Learnaillity of the superset label learning problem. In International Conference on Machine Learning, pages 1629-1637. PMLR, 2014.
[27] Milan Lopuhaä-ZZakkenbrrg Zwakenberg, Boris Škorić, and Ninghui Li. Fisher information as a utility metric for frequency estimation under local differential privacy. In Proceedings of the 21 Workshop on Privacy in the Electronic Society, pages 41-53, 2022.
[28] Jiaqi Lv, Miso Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. In International Conference Muchine Learning, pages 6500-6510. 6010. PMLR, 2020.
[29] Jiaqi Lv, Biao Liu, Lei Feng, Ning Xu, Miao Bo An, Gang Niu, Xin Geng, and Masashi Sugiyama. On the robustness of average losses for partial-label learning. CoRR, abs/2106.061122 2021.
[30] Mani Malck Esmacili, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer. Antipodes of label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34:6934-694 6944,, 2021.
[31] Aditya K Menon, Ankit Singh Rawat, Sashank Reddi, Seungyeon Kim, and Sanjiv Kumar. A statistical perspective on distillation. In International Conference on Machine Learning, pages 7632-7642. PMIR, 2021.
[32] Balas K Natarajan. On learning sets and functions. Muchine Learning, 4:67-97, 1989.
[33] Balas K Natarajan. On learning sets functions. Machine Learning, 4(1):67 997, 1989.
[34] Mehdi Noroozi, Ananth Vinjimoor, Paolo Favaro, and Hamed Pirsiavash. Boosting self-supervised learning via knowledge transfer. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages
2018.
[35] Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In International Conference on Machine Learning, pages 5142-5151. PMLR, 2019.
[36] Herbert Robbins and Sutton Monro. A stochastic approximation method, The annals of mathematicul statistics, pages 400-407, 1951.
[37] Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang. Carlo Gatta, and Yoshua Bengio. Fitnets: Hints for thin deep nets. arXiv preprint arXiv:1412.6550, 2014.
[38] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zhigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818-2826, 2016.
[39] Jiaxi Tang, Rakesh Shivanna, Zhe Zhao, Dong Lin, Anima Singh, Ed H Chi, and Sagar Jain. Understanding and improving knowledge distillation. CoRR. abs/2002.03532. 2020.
[40] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(1 1144- 1984.
[41] Vladimir Vapnik, Rauf Izmailov, et al. Learning using privileged information: similarity control and knowledge transfer. J. Mach. Learn. Res., 16(1):2023 2049,,2299922 2015.
12

---

[42] Jing Wang and Xin Geng. Label distribution learning machine. In Internationall Conference on Machine Learning, pages 10749-10759. PMLR, 2021.
[43] Lin Wang and Kuk-Jin Yoon. Knowledge distillation and student-teacher learning for visual intelligence:
A review and outlooks. IEEE Transactions Pottern Analysis and Machine Intelligence, 2021.
[44] Yude Wang, Jie Zhang, Meina Kan, and Shiguang Shan. Learning pseudo labels for wemi-and-weakly supervised semantic segmentation. Pattern Recognition, 132:108925, 2022.
[45] Alfred North Whitehead, An introduction to mathematics. Courier Dover Publications, 2017.
[46] Dong-Dong Wu, Deng-Bao Wang, and Min-Ling Zhang, Revisiting consistency regularization for deep partial label learning. In International Conference on Machine Learning, pages 24212-24225 PMLR, 2022.
[47] N. Xu, J. Shu, R. Zheng, X. Geng, D. Meng, and M. Zhang. Variational label enhancement. IEEE Transactions Puttern Analysis &amp; Machine Intelligence, (01):1-15, sep 2022. ISSN 1939-3539, doi: 10. 11110//TAMM.2222..000000
[48] Ning Xu, Yun-Peng Liu, and Xin Geng. Label enhancement for label distribution learning. IEFE Transactions on Knowledge and Data Engineering, 33(4):1632-16433 2019.
[49] Ning Xu, Congyu Qiao, Xin Geng, and Min-Ling Zhang. Instance-dependent partial label learning. Advances Neural Information Processing Systems, 34:27119-27133 2021.
[50] Junxiao Xue, Shibo Huang, Huawei Song, and Lei Shi. Fine-grained eqquence-to-sqqueee lip reading based on self-attention and self-distillation. Frontiers of Computer Science, 17(6):176344, 2023.
[51] Anbang Yao and Dawei Sun. Knowledge transfer via dense cross-layer mutual-distillation. In European Conference on Computer Vision, pages 294-311. Springer, 2020.
[52] Shan You, Chang Xu, Chao Xu, and Dacheng Tao. Learning from multiple teacher networks. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1285-1294, 2017.
[53] Li Yuan, Francis EH Tay, Guilin Li, Tao Wang, and Jiashi Feng. Revisiting knowledge distillation via label smoothing regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3903-3911, 2020.
[54] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. CoRR, 0///1605.077 146, 2016.
[55] Linfeng Zhang, Jicbo Song, Anni Gao, Jingwei Chen, Chenglong Bao, and Kaisheng Ma. Be your own teacher: Improve the performance of convolutional neural networks via self distillation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3713-3722, 2019.
[56] Ying Zhang, Tao Xiang, Timothy M Hospedales, and Huchuan Lu. Deep mutual learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4320 2018.
[57] Xingyu Zhao, Yuexuan An, Ning Xu, and Xin Geng. Fusion label enhancement for multi-label learning. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 3773-3779. ijeai.org, 2022.
[58] Helong Zhou and Liangehen Song. Rethinking soft labels for knowledge distillation: A viriinae tradeoff perspective. In Proceedings of International Conference on Learning Representations (ICLR), 2021.
[59] Zhi-Hua Zhou. brief introduction weakly supervised learning. National science review, 5(1):44-53, 2018.
[60] Xiatian Zhu, Shaogang Gong, et al. Knowledge distillation by on-the-fly native ensemble, Advances neural information processing systems, 31, 2018.
13

---

A Appendix
A.1 Variants of Knowledge Distillation
Self-distillation [55 25 50 treats the mixture of the outputs and the ground-truth labels as target soft labels, and the proportion is iteratively adjusted during the training. Ensemble KD [52] 60) employs the ensemble of the soft labels (teachers) to improve generalization. Besides, in mutual learning [56 51, there no explicit teacher network and multiple students learn from each other by synthesizing soft labels of other students. Soft labels play an important role in all these variants.
A.2 Proof of Theorem 1
For simplification, we denote the probability of event A as p(4).
Ehrp(h))) - -xxx))>xx>1 min ((h(z),)) p( E (x(((x))) [f]
(f()()())
-B(a,))~xxd (E(((f(=))
min (((h(z), (((()))()))) y Rx(/(z))) e E Rx(s(x)) (
+ +((h(x))i)) p(i E (f(x))) v (x((()))) ply & (x((())) [
The coefficient of ((h()).)) is: Coff(e(h(z)))) v)1 =ply (f(())) v (f(xl)))) plu (x(f(=)) If)
=1 =1-1 n
For * y, there is Coff(e(h(z)).) =pli E (f()))) y Qx((x))) ply e l+(f(=)) (f)
+ p(i (z)()))) y $ (x(())))) ply & (x(f(=)) f)
ST - 11) +
Therefore, when - 1 (1 - 17) + 7/, i.e.
< 1 - 7 T-nj
we have h² = arg min Errp (h))).
hEH
A.3 Proof of Lemmal
Let z, z' be the training and the testing set, and each of them is of size n. Define H(z) {h H: Err (h) ff = 0} as the set of zero-empirical-risk hypotheses. We can bound Pr (z Rn,s f Hn)
with Pr ([z, z') E Sn,e I E H,) as follows
Pr ((2, 2') E Sn.z
E Hn)
Pr ((z, z') E Sn,e
z E Rn,rr f E Hg)
= Pr ((3 E H n (z). Err. (hlf) 2 E _ | 2
Rn,s, E Hn))
2 Pr h E He n (z), EIT. (hl 2 2
8
z E Rn.e, E Hn)
en
21 - exp (- :
When n >
8 2 we have Pr (Zz,z') E Sn,e f E Hn) 2 Pr Rn,e If E Hy), which com- pletes the proof.
A.4 Proof of Lemma 2
We follow the methodology of proving the ERM learnability in [66] Here we need to bound Pr (Sm,e f E H. The key behind the proof is refine Err (his) and Err (hlf). ) We use classic method, i.e., swap, to refine the probability of a single instance. A swap o oz, z') = (z". z²²) means exchanging some instances between the training set z and testing set x' while keeping size unchanged. Each (x, v) E is training instance while each (x. v) E 2 is testing instance. There are 2n different swaps in total and we define as the set of all swaps. Firstly, we use swap to describe Pr (Sn.s f H)).
14

---

2n Pr ((z,z') E Sn,e If Hn) =
Σ [rr((z,z)) E Sn,e /., v.f Hq))
oEG
E [[r((o(z,z'' E Sn,e L Hy))
dEG
=B
Pr(o(zz,') E Sn.e I,,. f Hn)
DEG
Here, the expectations with respect to (zz, y, ,'). To further refine Sn,s, define 8 for certain classifier as
- = [z.zz) Erg. (hlf) 0, Err. (Nlf) 2 2
Let H (xr,x") be the hypothesis space that have different prediction for instances (I, Next, we have the bound
Σ Pr(a((z,2)) z') E Sn,e j... v/, H,) S oEG
Σ Pr(a(zz,2)) E Sh 1x,,,'' v' Hg).
(x,"( DEG
By 33 the complexity of the hypothesis space H (2r, x²) can be bounded as
H. (z,x²) S (2m) dn 2dd
Let d2, = f(x) be the soft label of æy induced by model f and Qu (dz,) be the top-k set of the soft
label. Then,
Pr (z(z,z) Sh
x. I,,y, 20 VV. .f f Hn)
=I Errz (h|s) 2
f E H,) Pr (h(xz) E
,,, E Ha)
2
-I1 EErzzo (hls)
I f E Hn)
I[ (M(x)) E (u , , E Hn)
For the pair of (v.y, v,,',,,, y'), we consider the number of instances of all cases. Specifically, let ui U2 and ug represent
number both incorrectly predicted instances, one incorrectly predicted instances and both correctly predicted instances. Besides, we define u, as the number of instances where (x", (z) is incorrectly predicted while (x'a, y²") ) correctly predicted. Afterwards, the number of incorrectly predicted instances in the testing set is in + U2 Ug.
E E Hn)
=I(u1 + U2 Uk 2 8 nn)
T Errgie (MI)) 2 2
<I(u + 02 2 E
5"
n).
For Pr (h(aT) E (d(,), x=" .8. H,y). we count instances which have been swapped. On the one side, there are u2 + ug Uo instances are correctly predicted (h(x²) u where we have On the other side, there are bn + instances are incorrectly predicted (h(x?) # vf ). where we have Pr (M(az) E S4 (dz.) 1 Hr) S by (2) So, we have
Pr (M(x?) E (dd.)) 1f HHH)) = 1 by I1
Pr (Mxx²) E Rp(dd,)) ,,","", , H,)) < - (1-1))u2te ()) tuo
And then, the conditional probability can be bounded as follow:
Pr (o z') Sh 1.,,,', "y.''./l ./) s Il U1 u2 2 2n (1 17) u2 tuutu--uu uo of tur
15

---

There are 2" different swaps and we sum all.
Σ EEG
u1 u2 2 2 (1
17) u2 uo 70 paattn
22
<2
11 I]
u2 2
Σ
1/2
(1 11)
j=0
42
=2n-wg_ .n - (7)
111 + U2 z 2n1
Σ
u2
( ?
)
j=0
=2n-u, - 17) nu 72l I 111 + u2 2 (n)
(1 +
yu2 1/ + ? y02
1
=I U1 + U2 2 2 - (1 11) m-
us M/
7
=I 11 + U2 2 2n) (2 27)"
. 7 )u
17 + 7 )02.
2(1 17
where U1 + U22 u3. The tus in the first step means ways of swapping both correct instances and both incorrect instances. The index of j equals u2 different swaps of one correctly predicted instances. According to the assumption 1/ + S 1, we have < - < 1-ntz < 1. For
3(-M)
W1 + U2 2 n., when in = 0 and u2 n,, the right side reaches its maximum as follows:
1 1- +7
Pr If H,) S (2n)du L 2dd (2 22n))"
2(1 1
We have proved the Lemma
A.5
Proof of Theorem 2
With Lemma
D and Lemma 2 we have
Pr Is E Hn) s 2dut1 nn 2d (2 - 2
( 111++ 7
1-
- )
2(1 11)
We set
2(1 - 17)
0 = log 1- -1
Since 17 + < get O. We need bound Pr (Bn.s I E H,) with y, which means
Pen
(dn + log 2 + du logn + 2d log L + n log (2 - 2n))
S log 7).
2
de lorl bm) dh
Note that the function f(x) = log 1 + az - --1 121100 0. Let a inferred that
and x = n. It can be
88 2
log( 2m) log
8e 2
log( 2n
log I
1.
dh
dp
With the bound of log n. get the linear inequality of n. Since the aforementioned results hold for
all k E 21,2.... 21....... - 1}, Let
{
2 (dx (log((()))
no (H,
min ke(1,2....e11)
8y5 2
+ log 2 2-2m
llg B.E + log
2 log L) + log - + 11}
1
2-2na
When > no. we get Pr (Rn,s If Hn) < 1) and the proof is finished.
16

---

1
0.18
10
20
30
3-
40
4-
-..14
50
5
0.10
0..12
60
6-
7-
80
0.005
8-
90
0.08
10
30
(a)
(b)
Figure 4: Average of the soft labels in CIFAR-10 (a) and CIFAR-100 (b).
A.6 Proof of Theorem
Generally, for epoch t, we denote т and "r as the the unreliability degree and ambiguity degree of the the soft labels of the unlabeled data. The model will achieve the accuracy epoch t, p(1), 7t). We refer to it as Ps for simplicity. Then, for next epoch t + 1, the unreliability degree and ambiguity degree of next epoch can be estimated M bit more complicated. Incorrect label share equal probability 7++1 because we assume the noise is uniformly distributed. Then we have
Pe- The estimation of ambiguity degree a little
Me+1 + (c 1)7++1 k.
Further,
C
7+1 <
For p(n:7) 7) monotonically decreases, with the upper bounds on 7)+1 and 7411, we can get lower bound on Pt+1
Pr+1 p(16+11 I++1)
2 p(1 Pt. c c- k- -t)
Plinal lim Pt exists, it must satisfy the fix point equation,
p(1 k
Next, we prove that if p(n, 7) is htw.-iipschizz.coninooon (kzz < 1 2 define
then Plinal exists and is unique.
p(n. 7) vb (n. 7) + (1- 7), c-
where (1,, 7) E [0, 1J2 nnomm is employed as the norm on [0, 1J2 and denote d(-,-) as the distance function. We want show that contraction mapping. For (m 71), (12, 72) E [0, 1Ja.
dm 71), (/2 (2))
=(1 + Hp(n, m) - p(112
<(1 + kk.d((n. (12 (2))
where (1+ --1)= 1 ky E [0, 1). So e is contraction mapping and there is a unique fixed point (17, 7)
that v'(7,)) 7) (17, 7). That means Pinall exists and is unique.
17

---

Table 2: Different metrics of soft labels.
Dataset
Setting Supervised
Acc(Teacher)
Cheby
KI
Manhattan
Euclidean
Atc(Stud)nt)
95.29
0.0630
0.3335
0.1259
0.1728
95.68
19.07
0,8323
1.9295
1.6646
0.9093
88.53
20.98
0.8312
1.9619
1.6625
0,9129
88.85
22.00
0.8348
1.1997
1 1.6696
0,9078
89.32
CIFAR-I0
22.95
0.8213
L8781
I L6427
0,9008
89.57
24.73
0.8357
L8968
L6715
0,9058
90.22
SBTs
26.54
0.8396
1.9110
1.6768
0.9076
90.43
28.07
0.8390
1,9099
L.6489
0.9150
90.58
Supervised
78.13
0.1998
1.3763
0.3996
0.2630
79.01
21.85
0.9145
3.4739
L82290
0,9467
68.42
22,74
0.9078
3.3814
1.8166
0.9391
69.28
24.55
0.9093
3.3457
1.1887
0.9392
69.55
CIFAR-100
25.35
0,9064
3.3299
L8129
0.9370
69.88
26.53
0.9008
3.2921
1,8016
0.9320
71.22
SBTs
27.22
0.9046
3.2858
1 1.8092
0.9329
71.34
28.05
0.9009
3.2560
1.8018
0.9302
72.08
A.7 Experiment Setup
We consider three benchmark image datasets CIFAR-10, CIFAR-100 23 and Tiny ImageNet, and generate the soft labels with different hyperparameters of the teacher model. The student model is trained with the generated soft labels and aims to distinguish the ground-truth label. The accuracy of the student model employed to measure the effectiveness of the soft labels. Datasets are divided into training, validation, testing set in the ratio of 4:1:1. For the fairness of the experiments, all student models are WideResNet28 x architecture [54] on each dataset. In all experiments, we use mini-batch SGD (36) with batch size of 128 and momentum of 0.9. Each model is trained with maximum epochs = 200 and employs early stopping strategy with patience 20. We report final performance using the test accuracy corresponding the best accuracy on validation set. For the all experiments, we employ a basic re- re-weight strategy to train the student model. Specifically, in each epoch, train the student model and update the soft labels with the softmax outputs of it.
learning For PLL, we employ a common strategy to zeroize the soft labels that not in the candidate set. For learning with unlabeled data, we warm-up the model for epochs. Then, we train with all data every epoch and label the unlabeled data with the model every epochs. Each dataset divided into labeled set, unlabeled set, testing set in the ratio of 1:19:4.
Weakky-suuerrve
A.8 Hyperparameters in 8
We set the number of the random labels (in 7 as 3 while in TJs and as 4 in all experiments. The punishment factor an ranges from to 0.4 and the compensation factor 02 ranges from 0.9 to 1.3. The weight of the random labels ag is from 1.6 to 2.3. In detail, we observe the following phenomenons:
As mentioned in 1 cannot take the accuracy of the teacher the sole criterion evaluate the pedagogical efficacy. y defined in (2) can be seen as the coarse measure of the imbalance of the label. For the student model, the smaller 7 could mean the better performance if the number of random labels is fixed.
Both the punishment and the random labels are applied to decrease the top-1 accuracy within reasonable range. For the simple dataset, large punishment are needed to protect privacy and for the complicated dataset like 100, we enhance the ratio of random labels to reduce the effect of similar labels.
These soft labels are very different from the ground-truth labels, which means low accuracy. In these soft labels, the average degree of the ground-truth labels is around 0.2.
18

---

40
35
70
Proposs Indicatoo
Aoc%%
15
30
25
50
75
100 Epochs
125
150
175
200
Figure 5: The curve of the indicators in incomplete supervision.
92-
Acc of the student (1)
Acc of the student 1%
73-
72-
70
WRN-28-4
WRN-284
WRN-40-2
WRN402
WRN-004
20
22
24
26
28
22
23
24
25
26
27
28
Accuracy
(%)
Accuracy labels
(%)
(b)
Figure 6: The experiments of 4 different backbones: WRN x2, WRN x8x4, WRN 40x2, WRN 40 On the left are the experiments conducted on CIFAR- 10, while on the right are those performed on CIFAR-100.
A.9 Experiments of different backbones
F demonstrates whether the effectiveness of soft labels is influenced by different backbones. We experimented with wideresnet 28x2, 28x4, 40x2, and 40x4. In the Figure 2, we omitted the Unreliability degree and Ambiguity degree, which are the same the that of Figure in the paper, for clarity. The four distinct backbones displayed consistent trends, further suggesting that the proposed indicators are effective across different backbones.
A.10 Overall distribution of the Soft Labels Generated by SBTs
As illustrated in Figure the horizontal axis represents the ground-truth label while the vertical axis represents the mean of the soft labels. The diagonal can be seen the degree of correctly predicted labels. We can see that the ground-truth label is dominant in the soft labels. On the other side, the figure can be
simple measure of the similarity between labels.
A.11 Experiments of Incomplete Supervision
The predictive model label the unlabeled data and then learn with all data alternately. As shown in Figure [5] Acc (the accuracy of the model) improves the soft labels evolve. Accordingly, unreliability degree (f)( decreases and ambiguity degree (f)()) remain unchanged, which means the soft labels of the model are more effective. The figure shows the dynamics in the training with
unlabeled data, which is consistent with the theory 4.1 Furthermore, we find that the soft labels of unlabeled data exhibit high ambiguity degree "xa())) indicating that some categories may be very similar and difficult for the model to distinguish.
19


Reviews:
[{"review_id": "yS5ffzY83y", "reviewer": "Reviewer_XfEm", "summary": "This paper explores the concept of learning from weak, or \"soft,\" labels that may be biased or diverge from the ground truth labels in a dataset. In contrast to existing theories that focus on the importance of close alignment between soft and ground truth labels, the authors probe the efficacy of learning from significantly biased soft labels. They introduce two indicators to gauge the effectiveness of these soft labels and propose conditions under which learning from such labels can be successful, including large-biased labels.\n\nThe authors further devise a heuristic method for training what they call Skillful but Bad Teachers (SBTs), referring to models with relatively low accuracy that can nevertheless effectively train high-performing student models. They show that these teachers can achieve up to 90% accuracy on the CIFAR-10 dataset, demonstrating the validity of their approach.\n\nAdditionally, the authors adapt their theoretical framework to examine the utility of soft labels in three specific weakly-supervised learning paradigms: incomplete supervision, partial label learning, and learning with additive noise. Experimental results are presented to support the proposed indicators and the viability of biased soft labels in these scenarios.\n\nKey contributions include:\n\n    Discovery that learning from largely biased soft labels can achieve comparable performance, and an exploration of the mechanisms behind this phenomenon.\n    The proposal of two indicators to evaluate the effectiveness of soft labels and conditions to ensure their usefulness.\n    A heuristic method to train SBTs, using new concepts of unreliability degree and ambiguity degree.\n    A theoretical framework that illuminates the role of soft labels in three weakly-supervised learning paradigms, accompanied by theoretical guarantees for their learnability and supporting experimental results.", "questions": "It's mentioned that the soft labels generated by SBTs are large-biased, which could potentially impact the model's ability to generalize to new, unseen data. While the authors note that students still have good accuracy despite the bias, how does the authors propose the current approach tackles this situation? \n\n", "limitations": "The process of inhibiting correct predictions, reducing unreliability and ambiguity degrees, and randomly selecting k-1 labels for each training instance could increase the computational complexity and time required to train the models.\n\nThe evaluation is mainly based on the accuracy of the student models, which might not be the most comprehensive measure. There could be other performance metrics that are important in the context of this problem.\n\n", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Theoretical Analysis: The paper provides a comprehensive theoretical framework for analyzing the effectiveness of soft labels, which are often employed in the realm of machine learning for teaching student models.\n\nDefinitions and Indicators: The paper introduces and defines new concepts like unreliability degree and ambiguity degree, and relates them to the effectiveness of soft labels. This could provide valuable insight for the development of future machine learning models.\n    \nExtension to Weakly-Supervised Learning (WSL): The research effectively applies the theoretical findings to weakly-supervised learning paradigms, thus demonstrating the applicability and extensibility of their findings.", "weaknesses": "Selective Conditions: While the paper provides conditions for classifier-consistency and ERM learnability, it doesn't clearly outline how to meet these conditions in a real-world context. Furthermore, the condition of balancing unreliability degree and ambiguity degree might be challenging to achieve in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your constructive feedback. We appreciate the time and effort you took to review our paper, and we value the insights you've provided.\n\nYour acknowledgment of our paper's strengths, especially the theoretical analysis, the introduction of new indicators, and the extension to weakly-supervised learning, is both encouraging and motivating. It reinforces our belief in the significance of our contributions and provides us with valuable insights for further refinement. We would like to address the concerns and questions you raised:\n\n**Q1. Conditions in Theorem 1 and 2 might be challenging to achieve in practice.**\n\n* In fact, for models that are trained normally, the conditions we described (i.e. $\\gamma_k(f)<1-\\frac{\\eta_k(f)}{1-\\eta_k(f)}$ and $\\eta_k + \\gamma_k<1$) are easily met. It only requires the existence of a specific 'k' such that both delta and gamma are satisfied. To further illustrate this point, when we set $k=4$ and use a normally trained resnet-50 as an example, we obtained the following results:\n  - CIFAR10: Accuracy (ACC): 95.29%; $\\eta$: 2.63\\%; $\\gamma$: 20.12\\%.\n  - CIFAR100: Accuracy (ACC): 78.13%; $\\eta$: 6.55; $\\gamma$: 21.01\\%.\n  - Tiny-Imagenet: Accuracy (ACC): 60.63%; $\\eta$: 13.55; $\\gamma$: 24.67\\%.\n\n  They all easily satisfy the requirements stipulated in Theorem 1 and Theorem 2.\n\n**Q2. How does the proposed algorithm make it possible for bad teachers to teach good students?**\n\n* The algorithm proposed in Section 5.1 is inspired by our Theorem 1 and 2. While the soft labels generated by SBTs are large-biased, they exhibit a lower unreliability degree and ambiguity degree, as elaborated in Section 5.1. Theorems 1 and 2 offer assurances for the effectiveness of such large-biased soft labels, thereby enabling the effective training of competent students.\n\n**Q3. The proposed algorithm increase the computational complexity and time in training the models.**\n\n* Based on the logs from our experiments, our method operates within 10% slower than normally trained models. Moreover, the GPU memory consumption is almost identical. Thus, the computational complexity and time required for our approach should be considered acceptable.\n\n**Q4. Evaluation is mainly based on the accuracy of the student models.**\n\n* As illustrated in Table 1 of the Author Rebuttal, we tested four different metrics — Chebyshev distance, KL divergence, Manhattan distance, and Euclidean distance — to measure the discrepancies between the large-biased soft labels generated by SBTs and the ground-truth labels. Furthermore, we also test soft labels generated by a teacher trained under full supervision. What we observed was that, based on these four classical metrics, the soft labels generated by SBTs differ significantly from those of the normally trained teacher. Yet, they still manage to train good students. These classic metrics do not adequately capture the teaching capabilities inherent in soft labels, nor do they reflect the performance of the student models. This finding accentuates our claim that the indicators we introduced are more indicative of the teaching capabilities of soft labels compared to these classic metrics.\n\nYour constructive feedback is instrumental in refining our paper, and we are committed to making the necessary improvements. Once again, thank you for your valuable insights."}, {"review_id": "kxWh8QtgnK", "reviewer": "Reviewer_M44N", "summary": "This paper aims to study the effectiveness of biased soft labels for knowledge distillation. They propose two indicators to measure the effectiveness of the biased soft labels: unreliability degree and ambiguity degree.  They provide a theoretical guarantee that the biased soft labels are effective in training a good student in three weakly-supervised learning paradigms: incomplete supervision, partial label learning, and learning with additive noise.  Their experiments reveal that largely biased soft labels can also teach good students and the proposed indicators are effective in measuring the effectiveness of soft labels. ", "questions": "* Does the proposed indicators work well across other benchmark datasets?", "limitations": "The authors did not address the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The motivation of the paper is original and novel. It is intriguing to see that learning from largely biased soft labels can achieve comparable performance, and the proposed indicators can be a valuable contribution to measuring their effectiveness in learning a good student for downstream tasks.\n* The paper provides an in-depth theoretical guarantee of the biased soft labels in three weakly supervised learning settings.\n* The experiment results validate that the proposed indicators (unreliability and ambiguity degree) are indeed effective in measuring the effectiveness of the soft labels (i.e. high accuracy of students) across the three weakly supervised learning paradigms. \n* Overall, the paper sufficiently informs the readers of technical and implementation details. ", "weaknesses": "* The paper shows limited experiment results on CIFAR-10 and CIFAR-100 (Figure 2). The authors should perform experiment on a wider range of benchmark datasets to validate the generality of the method. Are the proposed indicators effective in more complex datasets as the authors suggested?\n* The introduction could be better organized. The paper should clearly present the definition of a large-biased soft label and better motivate the readers on why utilizing them is valuable. \n* The paper exceeds the nine page limit.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you for your constructive feedback. We appreciate the time and effort you took to review our paper, and we value the insights you've provided.\n\nFirst and foremost, we would like to express our sincere gratitude for your positive remarks on the originality, theoretical depth, and experimental validation of our work. Your recognition of the novelty of our motivation, the in-depth theoretical guarantees provided, and the effectiveness of our proposed indicators is truly encouraging and reinforces our belief in the significance of our contributions. We would like to address the concerns you raised:\n\n**Q1. Experiments on more complex datasets.**\n\n- A: We have supplemented our research with experiments on the Tiny-ImageNet dataset, and the results are illustrated in the PDF of Author Rebuttal.\n\n**Q2. Definition of a large-biased soft labels.**\n\n- A: We apologize for any confusion caused by the term \"large-biased soft labels\" mentioned in the paper. Here, we provide a rigorous definition for \"large-biased soft labels\" to clarify its meaning.\n\n  > Definition 1. (Bias of soft labels) Give a dataset $D$ consisting of $n$ samples, the feature vector for the $i$-th sample is denoted as $\\boldsymbol{x}_i$ and the corresponding label is denoted as $y_i$. Let $f$ represent a model or a mapping rule (e.g. label smoothing). The bias of the soft labels generated by $f$ on dataset $D$ is\n\n  \\begin{aligned}\n  Bias(f, D)=\\frac{1}{n} \\sum_{i=1}^n [1-f_{y_i} (\\boldsymbol{x}_i)],\n  \\end{aligned}\n\n  where $f_{y_i} (\\boldsymbol{x}_i)$ refers to the component of the soft label $f(\\boldsymbol{x}_i)$ that corresponds to the true label $y_i$.\n\n  > Definition 2. (Large-biased soft labels) Soft labels generated by $f$ on dataset $D$ is called biased soft labels when $Bias(f, D) \\textgreater 0$ and called large-biased soft labels when $Bias(f, D) \\geq 0.5$.\n\n**Q3. The paper exceeds the nine page limit.**\n\n- A: We apologize for the oversight regarding the page limit. We will carefully revise the paper to ensure it adheres to the limit while retaining the essential content and contributions.\n\nYour constructive feedback is instrumental in refining our paper, and we are committed to making the necessary improvements. Once again, thank you for your valuable insights and for considering our paper for acceptance."}, {"review_id": "UdVZVlUDP9", "reviewer": "Reviewer_mHw2", "summary": "The authors propose a clever theoretical framework for studying learnability under supervision with imperfect soft labels.", "questions": "See weaknesses section.", "limitations": "- The authors have listed both limitations and assumptions, though I think the assumptions may be more of a limitation than suggested.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- Learning from imperfect soft labels is an important and interesting area that is prevalent not only in knowledge distillation but also in cognitive science, human-AI interaction, and pretty much any modeling that aim to take into account noise and uncertainty. \n- The authors conduct a promising theoretical analysis of this setting by recasting it as a noisy top-k oracle problem (where teachers provide a set of k labels which with some probability contains the true label).", "weaknesses": "- Clarity could be improved by providing more intuitions and explanations for terminology throughout. For example, \"biased soft label\" is never formally defined, and the implied definition (based on the notions of ambiguity and unreliability) does not fully agree with what I would normally think of when thinking of statistical notions of bias. Some additional editorial revision (fixing typos, etc.) would also be helpful, but I am not taking that into account in my score. \n- I think the assumptions are not quite as moderate as the authors imply and would like some more clarification about these. For example, one of the assumptions seem to be that labels occur in the top-k with equal probability, but this is clearly not the case in practice (e.g. you may believe a picture of a dog could be a wolf, but certainly not an airplane) which the authors mention when designing their experiments as they find that the top-k labels are correlated. The experiments are then designed to satisfy this assumption which means there is very little evidence that the proposed theory describes a realistic setting.  Another assumption (Assumption 2 in 4.1) seems to pre-assume that the metrics considered by the authors are inversely correlated with accuracy which feels circular since I believe this is one of the things the authors want to claim. \n- As mentioned in the section above, the empirical results are currently unconvincing. In addition to the assumption mentioned above, it seems like in both experiments, the true label has the highest probability in >15% of the cases. For CIFAR10 this is reasonable since random chance is 10%, but for CIFAR100, this is quite high. Is there a disconnect between the theory setting and the experimental setting, in that the theory is focused on learning from the top-k set where all top-k labels are treated equally while in the experimental setting, learning still takes into account the actual probabilities? Perhaps a more compelling experiment would be to isolate various top-k cases and show that the curves are robust to changes in k?\n- There are a number of existing papers that study the informativeness of soft labels. It would be great to see some discussion of how this study fits into that literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\n**Q1. Clairty and defination.**\n\n- A: We apologize for any confusion caused by the term \"large-biased soft labels\" mentioned in the paper. Here, we provide a rigorous definition for \"large-biased soft labels\" to clarify its meaning.\n\n  > Definition 1. (Bias of soft labels) Give a dataset $D$ consisting of $n$ samples, the feature vector for the $i$-th sample is denoted as $\\boldsymbol{x}_i$ and the corresponding label is denoted as $y_i$. Let $f$ represent a model or a mapping rule (e.g. label smoothing). The bias of the soft labels generated by $f$ on dataset $D$ is\n\n  \\begin{equation}\n  Bias(f, D)=\\frac{1}{n} \\sum_{i=1}^n [1-f_{y_i} (\\boldsymbol{x}_i)],\n  \\end{equation}\n\n  where $f_{y_i} (\\boldsymbol{x}_i)$ refers to the component of the soft label $f(\\boldsymbol{x}_i)$ that corresponds to the true label $y_i$.\n\n  > Definition 2. (Large-biased soft labels) Soft labels generated by $f$ on dataset $D$ is called biased soft labels when $Bias(f, D) \\textgreater 0$ and called large-biased soft labels when $Bias(f, D) \\geq 0.5$.\n\n**Q2. About the assumption \"labels occur in the top-k with equal probability\".**\n\n- A: The assumption \"incorrect labels occur in the top-k with equal probability\", mentioned in line 212 (Section 4.1), is solely in service of Theorem 3. I have also articulated that this assumption can be relaxed, mentioned in lines 213-215, for instance, by considering an upper bound of $\\frac{p(i|x)}{p(j|x)}$. This does not impact our understanding of Incomplete Supervision from the perspective of soft labels.\n\n**Q3. The designed experiments reflect the assumption is not realistic.**\n\n- A: In fact, for models that are trained normally, the conditions we described (i.e. $\\gamma_k(f)<1-\\frac{\\eta_k(f)}{1-\\eta_k(f)}$ and $\\eta_k + \\gamma_k<1$) are easily met. It only requires the existence of a specific 'k' such that both delta and gamma are satisfied. To further illustrate this point, when we set $k=4$ and use a normally trained resnet-50 as an example, we obtained the following results:\n\n  - CIFAR10: Accuracy (ACC): 95.29%; $\\eta$: 2.63\\%; $\\gamma$: 20.12\\%.\n  - CIFAR100: Accuracy (ACC): 78.13%; $\\eta$: 6.55; $\\gamma$: 21.01\\%.\n  - Tiny-Imagenet: Accuracy (ACC): 60.63%; $\\eta$: 13.55; $\\gamma$: 24.67\\%.\n\n  They all easily satisfy the requirements stipulated in Theorem 1 and Theorem 2.\n\n**Q4. (Assumption 2 in 4.1) Assume that the metrics are inversely correlated with accuracy.**\n\n- A: In Assumption 2, we indeed ideally posit a inverse correlation between the proposed metrics and accuracy, using this to prove Theorem 3. Operating under the ideal assumption, we can justifiably explain both the dynamic process and the final performance of Incomplete Supervision. This indicates that our theory does not contradict practical observations, further validating the reasonableness and practicability of our theoretical framework.\n\n**Q5. The accuracy of the teacher is much higher than 1% on CIFAR100.**\n\n- A: Theoretically, the accuracy on CIFAR100 can be even lower. However, in practice, the accuracy being above 15% is constrained by the size of the dataset. As seen in Theorem 2, the smaller the unreliability degree, the larger the required dataset size. If there are more CIFAR100 training samples, we believe the accuracy could indeed be lower.\n\n**Q6. Top-k labels and the actual probabilities of the soft labels.**\n \n- A: It's important to clarify that our study consistently focuses on learning from soft labels, rather than from top-k sets. The indicators we proposed facilitate theoretical analysis by transforming soft labels into top-k sets. However, the conclusions are universally valid for all soft labels. While in practice experiments are indeed influenced by the “actual probabilities,” our theory merely provides a guarantee in the worst-case scenario.\n\n**Q7. About the choice of k.**\n\n- A: It's evident that when k=1 or k=c−1 (where c is the total number of classes), the supervision information suffers significant loss, resulting in poor performance by the student model. In practice, we observed that the student performs well when k=3, 4, 5. Our experimental results are based on a fixed k=4.\n\n**Q8. How this study fits into related literature.**\n\n- A: To the best of our knowledge, teacher models in the current domains of knowledge distillation and label enhancement aim to mimic true labels while adding some regularization terms. Such teacher models typically produce soft labels that closely resemble the true labels. There are many existing explanations for these types of soft labels, such as they act as a form of regularization, they approximate Bayesian prior probabilities, they prevent excessive overconfidence, etc (see lines 80-84, 100-101). However, it seems that these theories cannot account for the observation that \"large-biased soft labels can also work\". Our research serves as a complement and refinement to the existing theories on soft labels.\n\nThank you for your valuable feedback. We will make revisions to our paper based on your suggestions."}, {"review_id": "irInLM6QUW", "reviewer": "Reviewer_vNqZ", "summary": "This paper studies the effectiveness of biased soft labels in knowledge distillation and weakly-supervised learning. The paper introduces two indicators to measure the effectiveness of soft labels, and proposes moderate conditions to ensure that biased soft label learning is classifier-consistent and ERM learnable. The paper also presents a heuristic method to train skillful but bad teachers, and shows that they can teach students to achieve high accuracy on CIFAR-10/100. The paper applies the theoretical framework to three weakly-supervised learning paradigms, and validates the indicators with experiments.", "questions": "1. In the introduction, the paper claims that “Empirical Risk Minimization (ERM) learners’ performance can generalize to the entire data distribution.”\n    However, previous studies have pointed out the drawbacks of ERM, such as (1) neural networks trained with ERM change their predictions drastically when evaluated on examples just outside the training distribution[1], also known as adversarial examples; (2) ERM allows large neural networks to memorize (instead of generalize from) the training data even in the presence of strong regularization, or in classification problems where the labels are assigned at random [1]. \n    In general, using ERM for optimization may affect the generalization ability of the model. Does this contradict the conclusion of this paper? Does the conclusion of this paper have any prior studies or experiments to support it?\n[1]Zhang, Hongyi, et al. \"mixup: Beyond empirical risk minimization.\" *arXiv preprint arXiv:1710.09412* (2017).\n\n2. The paper mentioned “skillful but bad teachers”. How to define the skillfulness of the bad teachers? \n3. As you mentioned in Section 5.3, is your main contribution the two methods of evaluating soft labels (unreliability degree and ambiguity degree), rather than the heuristic method of “bad teacher can teach good student”? \n4. The conclusion that “the accuracy of the students decrease when unreliability degree and ambiguity degree increase” does not seem to be obvious in Figure 2(b). Also, in Figure 3 (a) and (b), the ambiguity degree γ does not change much as the student accuracy increases. The same situation also occurs in Figure 5 in the appendix, which seems to not support the effectiveness of the ambiguity degree γ indicator in these weakly-supervised settings.", "limitations": "Some of the paper’s experimental results show that the two indicators proposed by the paper cannot well characterize the effectiveness of soft labels in all weakly-supervised settings. For example, under some of the weakly-supervision settings, the paper shows that the indicators are not consistent with the performance of the student model. The paper does not provide sufficient explanation or analysis for this phenomenon, and does not discuss how to improve or modify the indicators to better capture the effectiveness of soft labels.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and a pleasure to read.\n2. The paper provides thorough theoretical analysis for three different weak supervision settings.", "weaknesses": "1. The paper only conducts experiments on CIFAR-10/100 datasets, and does not provide experiments on larger and mainstream datasets, such as ImageNet. The paper also does not compare the proposed method with other state-of-the-art weakly-supervised methods, especially those based on knowledge distillation.\n2. The paper is suggested to provide more visualizations of the the prediction results (class probabilities) of large-biased soft labels (generated by SBTs) and good student.\n3. The paper does not provide experiments on different backbones, and cannot demonstrate the effectiveness of the proposed indicators and method on different architectures. The paper also does not discuss how the choice of the backbone affects the performance and robustness of the method.\n4. The paper exceeds the page limit. The paper is suggested to be shortened to meet the page limit requirement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\n**Q1. Experiments on Tiny-ImageNet.**\n\n- A: We have added experiments on Tiny-Imagenet, which can be found in the PDF attached to the rebuttal.\n\n**Q2. Why not compare the proposed method with other state-of-the-art weakly-supervised methods.**\n\n- A: Our primary contribution is the discovery that large-biased soft labels can also produce competent student models and that we provide explanations and theoretical proofs for the underlying phenomenon. The algorithm we designed (see Section 5.1) primarily serves to validate our theory. The aim of the weakly-supervised experimentation was not to train the state-of-the-art student model. To the best of our knowledge, this phenomenon hasn't been studied previously, which is why we did not design comparative experiments. \n\n**Q3. Visualizations of the class probabilities of large-biased soft labels.**\n\n- A: We have provided the visualizations of the class probabilities of large-biased soft labels (generated by SBTs) in the appendix (see Figure 4). We did not include it in the main text due to space constraints. \n\n**Q4. Experiments on different backbones.**\n\n- A: We have added experiments on different backbones (Figure 2 in the PDF of Author Rebuttal).  We experimented with wideresnet 28x2, 28x4, 40x2, and 40x4. In the Figure 2, we omitted the Unreliability degree and Ambiguity degree (which is the same the that of Figure 2 in the paper) for clarity. The four distinct backbones displayed consistent trends, further suggesting that the proposed indicators are effective across different backbones. For the same teacher model, the better the student model's fitting capacity, the better student's performance tends to be.\n\n**Q5. The paper exceeds the page limit.**\n\n- A: We sincerely apologize for this oversight. We will make the necessary adjustments to condense the length of our paper.\n\n**Q6. ERM learner cannot generalize well.**\n\n- A: The expected classification error defined in section 3.1 indicates the performance (or generalization ability) of the model with respect to the original data distribution. This conclusion is widely accepted in the machine learning community, as evidenced by [1,2]. Peter L. Bartlett also stated, 'The performance of such a model selection scheme critically depends on how well the error bounds match the true error (i.e., expected classification error).' As for the model's performance on adversarial examples, it falls outside the scope of our study. The generalization ability mentioned in mixup refers to situations outside the training distribution, and there's no contradiction between the two. Thank you for the excellent idea regarding the student model's performance on adversarial examples, and we will consider the feasibility of this direction in our future work.\n\n  > [1] Bartlett, Peter L., and Shahar Mendelson. \"Rademacher and Gaussian complexities: Risk bounds and structural results.\" Journal of Machine Learning Research 3.Nov (2002): 463-482.  \n  > [2] Daniely, Amit, et al. \"Multiclass learnability and the erm principle.\" Proceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 2011.\n\n**Q7. Definition of skillfulness of the bad teachers.**\n\n- A: We apologize for any confusion caused by the term \"skillfulness of the bad teachers\" mentioned in the paper. Here, we provide a rigorous definition for \"skillfulness of the bad teachers\" to clarify its meaning.\n\n  > Definition 1. (Bias of soft labels) Give a dataset $D$ consisting of $n$ samples, the feature vector for the $i$-th sample is denoted as $\\boldsymbol{x}_i$ and the corresponding label is denoted as $y_i$. Let $f$ represent a model or a mapping rule (e.g. label smoothing). The bias of the soft labels generated by $f$ on dataset $D$ is\n\n  \\begin{equation}\n  Bias(f, D)=\\frac{1}{n} \\sum_{i=1}^n [1-f_{y_i} (\\boldsymbol{x}_i)],\n  \\end{equation}\n\n  where $f_{y_i} (\\boldsymbol{x}_i)$ refers to the component of the soft label $f(\\boldsymbol{x}_i)$ that corresponds to the true label $y_i$.\n\n  > Definition 2. (Large-biased soft labels) Soft labels generated by $f$ on dataset $D$ is called biased soft labels when $Bias(f, D) \\textgreater 0$ and called large-biased soft labels when $Bias(f, D) \\geq 0.5$.\n\n  > Definition 3. (Bad teachers) We define $f$ as a bad teacher if the soft labels it generates on dataset $D$ are large-biased. Typically, $D$ is the training set for $f$.\n\n- We cannot provide a precise definition for 'skillful teachers' as the performance of the student is contingent upon the architecture of the model and the complexity of the dataset. In this context, 'skillful' merely signifies that the teacher produces students with acceptable outcomes.\n\n**Q8. Main contribution.**\n\n- A: We discover that 'large-biased soft labels can produce competent student models' and then introduced two indicators (unreliability degree and ambiguity degree) and provided theoretical guarantees for them. The heuristic approach of 'bad teacher can teach good student' serves to empirically validate the existence of the phenomenon and the soundness of our theory.\n\n**Q9. The conclusion that “the accuracy of the students decrease when unreliability degree and ambiguity degree increase” does not seem to be obvious.**\n\n- A: We sincerely apologize for any confusion caused by our statement 'the accuracy of the students decrease when unreliability degree and ambiguity degree increase'. What we intended to convey was that when one remains unchanged and the other increases, the accuracy of the students will decrease. Both indicators together are necessary to assess the efficacy of soft labels, and one should not be analyzed based solely on individual trends. This applies to Figure 2(b), 3(a), and 3(b) alike.\n\nThank you for your valuable feedback. We will make revisions to our paper based on your suggestions."}, {"review_id": "PvMQCEols7", "reviewer": "Reviewer_HDpR", "summary": "The authors analyse the learnability properties of (biased) soft labels, e.g., originating from a teacher model in a student-teacher setup, with respect to classifier consistency and ERM learnability. To this end, two indicator measures of the quality of the proxy labels are suggested, which are used in a theoretical analysis to derive bounds about the aforementioned quality dimensions. Moreover, a heuristic loss for training skillful but bad teachers is developed.", "questions": "- How did you determine the hyperparameters being used in the experiments? Did you repeat the experiments multiple times with different seeds? How about the standard deviations?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Investigates a highly relevant matter\n- Technically sound and valid theoretical results\n- Covers multiple special cases of weakly-supervised learning as a practically relevant problem setup\n", "weaknesses": "Major:\n- I find the distinction between incomplete supervision and partial label learning confusing. Typically, incomplete supervision and partial label learning are more or less the same thing. What the authors here refer to in the case of incomplete supervision is semi-supervised learning, which is a special case of partial label learning, namely that you can either observe a precise (i.e., unambiguous) label, or no label at all resp. the complete target space. In order to preserve consistency with related literature on this (e.g., as in your reference [58]), I would recommend sticking to this ontology.\n- The empirical analysis of SBTs does not contain any baseline. Overall, it is hard to judge the appropriateness of the developed indicators and the SBT loss proposals, perhaps the experimental setup can be overhauled.\n- It is hard to assess the looseness resp. tightness of the bound in Theorem 2. I would love to see the authors elaborating on this matter, e.g., by putting individual term components in a context, comparing it to “classical” bounds in multi-class learning, potentially with respect to label noise.\n\nMinor:\n- The page limit for submissions was 9 pages, but there is content on page 10.\n- I think there is a missing $\\max$ (or a different aggregator) in Eq. (1), right?\n- Also, “ambiguity degree” is a term that is already being used in the PLL literature, as also indicated by referring to [5]. This is not precisely an equivalent ambiguity degree formulation, so it should be distinguished.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe are truly grateful for your comprehensive review and the positive recognition of our work's relevance, technical soundness, and valid theoretical results. Your feedback provides us with valuable insights that will undoubtedly enhance the quality of our paper. We would like to address the concerns you raised:\n\n**Q1. Incomplete supervision and partial label learning.**\n\n* A: Incomplete supervision (semi-supervised learning) is training with labeled data and unlabeled data (i.e. the dataset are partially labelled). In partial label learning, each instance is ambiguously labeled with a labels set and the ground-truth label is in the set (i.e. each instance are partially labelled). There is not a direct correlation between incomplete supervision and partial label learning.\n\n**Q2. The baseline of the empirical analysis of SBTs.**\n\n* A: Our primary contribution is the discovery that large-biased soft labels can also produce competent student models and that we provide explanations and theoretical proofs for the underlying phenomenon. The algorithm we designed (see Section 5.1) primarily serves to validate our theory. To the best of our knowledge, this phenomenon hasn't been studied previously, which is why we did not design comparative experiments.\n\n**Q3. The looseness resp. tightness of the bound in Theorem 2.**\n\n* A: Suppose the Natarajan dimension of the hypothesis space $\\mathcal{H}$ is $d_\\mathcal{H}$.\nIn the multi-class learning, a classic sample complexity for the ERM learners is $\\mathcal{O}(\\frac{d_{\\mathcal{H}} \\log \\frac{1}{\\varepsilon} + \\log \\frac{1}{\\delta} }{\\varepsilon})$ [1]. This bound is based on a fully supervised scenario, whereas weakly supervised problems introduce a great deal more complexity. In this context, we refer to a theory on partial label learning [2] and describe its bound based on the proposed indicators: $\\mathcal{O}(\\frac{d_{\\mathcal{H}} \\log d_{\\mathcal{H}} + \\log \\frac{1}{\\theta \\varepsilon} + \\log \\frac{1}{\\delta} }{\\theta \\varepsilon})$, where $\\theta = \\log \\frac{2}{1+\\gamma}$. The bound in Theorem 2 (ours) is $\\mathcal{O}(\\frac{d_{\\mathcal{H}} \\log d_{\\mathcal{H}} + \\log \\frac{1}{\\theta \\varepsilon} + \\log \\frac{1}{\\delta} }{\\theta \\varepsilon})$, where $\\theta = \\log \\frac{2(1-\\eta)}{1-\\eta+\\gamma}$. The bound in Theorem 2 is of the same order of magnitude as that in [2]. The difference between the two lies in the value of $\\theta$. When the unreliability degree $\\eta>0$, more samples are required, almost increasing in proportion to $\\frac{1}{\\theta}$.\n\n  >[1] Ben-David, Shai, Nicolo Cesa-Bianchi, and Philip M. Long. \"Characterizations of learnability for classes of {O,…, n}-valued functions.\" Proceedings of the fifth annual workshop on Computational learning theory. 1992.  \n  >[2] Liu, Liping, and Thomas Dietterich. \"Learnability of the superset label learning problem.\" International Conference on Machine Learning. PMLR, 2014.\n\n**Q4. Exceed the page limit.**\n\n* A: We sincerely apologize for this oversight. We will make the necessary adjustments to condense the length of our paper.\n\n**Q5. Is there a missing $\\max$ (or a different aggregator) in Eq. (1)?**\n\n* A: Thank you for your kind reminder. We have revisited and reflected upon the definition of $\\eta$.\nAggregation based on inter-class max is better, with $\\eta= max_{(\\boldsymbol{x}, y) \\sim \\mathcal{X} \\times \\mathcal{Y}} \\operatorname{Pr}(y \\notin \\Omega_k(f(x)))$. The form in Eq. (1) implies that all samples have the same unreliability degree, which is right but more stringent.\n\n**Q6. The term “ambiguity degree” in the PLL literature should be distinguished.**\n\n* A: As explained in lines135-136, the ambiguity degree is inspired by PLL and extends it to soft labels. In fact, if PLL is transformed into the form of soft labels, two kinds of ambiguity degree are identical. To be more precise, the ambiguity degree in this paper refers to the ambiguity degree of soft labels.\n\n**Q7. How to choose hyperparameters?**\n\n* A: We have provided a detailed description of our experimental setup in Appendix A.7. Additionally, we've outlined the range and rationale behind our hyperparameter design in Appendix A.9.\n\n**Q8. Repeat the experiments multiple times with different seeds.**\n\n* A: Due to the limited time for the rebuttal, we replicated our experiments on CIFAR10/CIFAR100 using three different seeds. In each experiment, while using the same teacher, we varied the seed during student training. As a result, we observed a standard deviation of 1.113 in accuracy on CIFAR10 and 1.215 on CIFAR100.\n\nYour constructive feedback is instrumental in refining our paper, and we are committed to making the necessary improvements. Once again, thank you for your valuable insights and for considering our paper for acceptance."}]

Author rebuttal:
We provided three supplementary experiments in the PDF:

* In Figure 1, we show efectiveness of the proposed indicators on Tiny-Imagenet. As $\eta_k(f)$ and $\gamma_k(f)$ decrease, Acc (i.e., accuracy of the student) increases. The experiments on Tiny-Imagenet demonstrate a trend similar to that on CIFAR-10 and CIFAR-100.

* Figure 2 demonstrates whether the effectiveness of soft labels is influenced by different backbones. We experimented with wideresnet 28x2, 28x4, 40x2, and 40x4. In the Figure 2, we omitted the Unreliability degree and Ambiguity degree (which is the same the that of Figure 2 in the paper) for clarity. The four distinct backbones displayed consistent trends, further suggesting that the proposed indicators are effective across different backbones.

* In Table 1, we tested four different metrics — Chebyshev distance, KL divergence, Manhattan distance, and Euclidean distance — to measure the discrepancies between the large-biased soft labels generated by SBTs and the ground-truth labels. Furthermore, we also test soft labels generated by a teacher trained under full supervision. What we observed was that, based on these four classical metrics, the soft labels generated by SBTs differ significantly from those of the normally trained teacher. Yet, they still manage to train good students. These classic metrics do not adequately capture the teaching capabilities inherent in soft labels, nor do they reflect the performance of the student models. This finding accentuates our claim that the indicators we introduced are more indicative of the teaching capabilities of soft labels compared to these classic metrics.

Meta-review: The paper starts with an interesting and original motivation, defines relevant definitions like "unreliability degree" and "ambiguity degree" on the way, and finally provides a comprehensive theoretical framework with applications to weakly-supervised learning. There are certain limitations, such as increased computational complexity and limited validation on CIFAR-10/100, that remain. However, as reviewers have acknowledged, the authors have effectively addressed the most critical concerns. There's no major con against accepting the paper.
Decision: Accept (poster)