Progressive Purification for Instance-Dependent Partial Label Learning
Authors: Ning Xu
Biao Liu
Jiaqi Lv
Congyu Qiao
Xin Geng
Venue: Submitted to ICLR 2023 (2023)
Keywords: Partial label learning

Abstract: Partial-label learning (PLL) aims to train multi-class classifiers from instances with partial labels (PLs)---a PL for an instance is a set of candidate labels where a fixed but unknown candidate is the true label. In the last few years, the instance-independent generation process of PLs has been extensively studied, on the basis of which many practical and theoretical advances have been made in PLL, while relatively less attention has been paid to the practical setting of instance-dependent PLs, namely, the PL depends not only on the true label but the instance itself. In this paper, we propose a theoretically grounded and practically effective approach called progressive purification (POP) for instance-dependent PLL: in each epoch, POP updates the learning model while purifies each PL by progressively moving out false candidate labels for the next epoch of the model training. Theoretically, we prove that POP enlarges the region where the model is reliable by a promising rate, and eventually approximates the Bayes optimal classifier with mild assumptions; technically, POP is flexible with arbitrary losses and compatible with deep networks, so the previous advanced PLL losses can be embedded in it and the performance is often significantly improved.

Under review as a conference paper at ICLR 2023
PROGRESSIVE PURIFICATION FOR DEPENDENT PARTIAL LABEL LEARNING
INSTANCE-
Anonymous authors Paper under double-blind review
ABSTRACT
Partial label learning (PLL) aims to train multi-class classifiers from instances with partial labels (PLs)a a PL for an instance is set of candidate labels where a fixed but unknown candidate is the true label. In the last few years, the instance- independent generation process of PL.s has been extensively studied, on the ba- sis of which many practical and theoretical advances have been made in PLL,, whereas relatively less attention has been paid to the practical setting of instance- dependent PLs, namely, the PL depends not only on the true label but the instance itself. In this paper, we propose a theoretically grounded and practically effective approach called PrOgressive Purification (POP) for instance- dependeet PLL: in each epoch, POP updates the learning model while purifying each PL for the next epoch of the model training by progressively moving out false candidate labels. Theoretically, we prove that POP enlarges the region appropriately fast where the model is reliable, and eventually approximates the Bayes optimal classifier with mild assumptions; technically, POP is flexible with arbitrary losses and compatible with deep networks, so that the previous advanced PLL losses can be embedded in it and the performance is often significantly improved.
INTRODUCTION
Over-paran veeepparaettriieed deep neural networks owe their popularity much to their ability to (nearly) per- fectly memorize large numbers of training examples, and the memorization is known to decrease the generalization error Feldman (2020). On the other hand, scaling the acquisition of examples for training neural networks inevitably introduces non-fully supervised data annotation, typical example among which is partial label Nguyen & Caruana (2008); Cour et al. (201 1): Zhang et al.
2016 2017b); Feng & An (2018); Xu et al. 20199; Yao et al. (020b): Lv et al. (2020); Feng et al. set of candidate labels where fixed but unknown candidate the true label. Partial label learning (PLL) trains multi-clase classifiers from instances that are associated with partial labels. It is therefore apparent that some techniques should be applied to prevent memorizing the false candidate labels when PLL resorts to deep learn- ing, and unfortunately, empirical evidence has shown general -prppsse regularization cannot achieve that goal Ly et al. (2021).
2020b); Wen et al. (2021)
partial label for instance
A large number of deep PLL algorithms have recently emerged that aimed design regularizers Yao let al. (2020a b); Lyu et al. (2022) or network architectures Wang et al. (2022a) for PLL data. Further, there are some PLL works that provided theoretical guarantees while making their methods compat- ible with deep networks Lv et al. (020); |Feng et al. (2020b); Wen et al. (02TT); ); Wu & Sugiyama (202T). We observe that these existing theoretical works have focused on the instance-ine -indeeedden setting where the generation process of partial labels is homogeneous across training examples. With an explicit formulation of the generation process, the asymptotical consistency Mohri al. (2018) of the methods, namely, whether the classifier learned from partial labels approximates the Bayes optimal classifier, can be analyzed.
However, the instance-indeepeddet process cannot model the real world well since data labeling is prone to different levels of error in tasks of varying difficulty. Intuitively, instance-depe -deenddnd (ID) partial labels should be quite realistic some poor-quality ambiguous instances are more difficult to be labeled with an exact true label. Although the instance- indeeeedende setting has been extensively studied, the basis of which many practical and theoretical advances have been made

---

Under review as a conference paper at ICLR 2023
in PLL, relatively less attention has been paid the practically relevant setting of ID partial labels. Very recently, one solution has been proposed Xu et al. (2021) which learned directly from ID partial labels, nevertheless, it is still unclear in theory whether the learned classifier is good. Motivated by the above observations, we set out to investigate II) PL. with the aim of proposing a learning approach that is model-indeeendent and theoretically explain when and why the proposed method works.
In this paper, we propose PrOgressive Purification (POP), theoretically grounded PLL framework for ID partial labels. Specifically, we use the observed partial labels to pretrain a randomly initialized classifier (deep network) for several epochs, and then we update both partial labels and the classifier for the remaining epochs. In each epoch, we purify each partial label by moving out the candidate labels for which the current classifier has high confidence of being incorrect, and subsequently we train the classifier with the purified partial labels in the next epoch. As a consequence, the false candidate labels are gradually sifted out and the classification performance of the classifier is improved. We justify POP and outline the main contributions below:
We propose a novel approach named POP for the ID PLL problem, which purifies the partial labels and refines the classifier iteratively. Extensive experiments validate the effectiveness of POP.
We prove that POP can be guaranteed enlarge the region where the model is reliable by promising rate, and eventually approximates the Bayes optimal classifier with mild assumptions. This proof process does not rely on the assumption of the instance-independent setting. To the best of our knowledge, this is the first theoretically guaranteed approach for the general ID PLL problem.
POP is flexible with respect to losses, so that the losses designed for the mustance-independeer PLL problems can be embedded directly. We empirically show that such embedding allows advanced PLL losses can be applied to the ID problem and achieve state-of-the-a learning performance.
2 RELATED WORK
In this section, we briefly go through the seminal works in PLL, focusing on the theoretical works and discussing the underlying assumptions behind them.
Non-deep PLL
There have been substantial non-deep PLL algorithms from the pioneering work Jin & Ghahramani (2003). From a practical standpoint, they have been studied along two different research routes: the identification-bast based strategy purifies each partial label and extracts the true label heuristically in the training phase, Feng so as identify the true labels Chenn et al. (2014); Zhang et al. (2016); Tang & Zhang [ & An (2019): Xu et al. (2019). On the contrary, the average-based strategy treats all candidates equally Hüllermeeer & Beringer (2006); Cour al. (201T); [hang & Yu (015)). On the theoretical side, Liu and Dietterich/Liu & Dietterich 2012) analyzed the lcarnability of PLL by making small ambignity degree condition assumption, which ensures classification errors on any instance have a probability of being detected. And Cour et al. [Corr et al.) (2011) proposed a consistent approach under the small ambiguity degree condition and dominance assumption on data distribution (Proposition 5 in Cour et al. (201I)). Liu and Dietterich Liu & Dietterich
strategy and the average-basee strategy. The identification-
(2012) proposed a Logistic Stick- Breaking Conditional Multinomial Model to portray the mapping between instances and true labels while assuming the generation of the partial label is independent of the instance itself. It should be noted that the vast majority of non-deep PLL works have only empirically verified the performance of algorithms on small data sets, without formalizing the statistical model for the PLL problem, and therefore even less so for theoretical analysis of when and why the algorithms work.
Deep PLL In recent years, deep learning has been applied to PLI. and has greatly advanced the practical application of PL... Yao et al. Yao et al. (2020a b) and Lv et al. Lv et al. (0220) proposed learning objectives that are compatible with stochastic optimization and thus can be implemented by deep networks. Soon Feng et al. Feng et al. (2020b) formalized the first generation process for PLL. They assumed that given the latent true label, the probability of all incorrect labels being added into the candidate label set is uniform and independent of the instance. Thanks to the uniform generation process, they proposed two provably consistent algorithms. Wen et al. /Wen et al. (202T) extended the uniform one to the class-dependent case, but still keep the instance-independent
2

---

Under review as a conference paper at ICLR 2023
sumption unchanged. In addition, ;0077;: Yu et al. (2018); Ishida et al. (2019) Feng et al. (2020a) has been proposed that learns from instances equipped with a complementary label. A complementary label specifies the classes to which the instance does not belong, so it can be considered to be an inverted PLL problem. How- ever, all of them made the intaance-nndeeedeent assumption for analyzing the statistic consistency. Wu and Sugiyama Wu & Sugiyamal (2021) proposed a framework that unifies the formalization of multiple generation processes under the instance-independent assumption. Wang et al. Wang et al. (022a) proposed data-au teitt--ugmmntation-banne bbaded framework to disambiguate partial labels with con- trastive learning. Zhang et al. (Zhang et al.] (2021a) exploited the class activation value to identify the true label in candidate label sets.
paradigm called complementary label learning Ishida al.
Very recently, some researchers are beginning to notice a more general setting-II PI... Learning with the ID partial labels is challenging, and all instance-independent approaches cannot handle the ID PLL problem directly. Specifically, the theoretical approaches mentioned above utilize mainly the loss correction technique, which corrects the prediction or the loss of the classifier using prior or estimated knowledge of data generation processes, i.c., a set of parameters controlling the probability of generating incorrect candidate labels, it is often called transition matrix Patrini et al. (017)). The transition matrix can be characterized fixedly in the instance- independent setting since it does not need include instance-level information, condition that does not hold in ID PLL.. Furthermore, it is ill-posed to estimate the transition matrix by only exploiting partially labeled data, i... the transition matrix is unidentifiable Xia et al. (2020). Therefore, some new methods should be proposed to tackle this issuc. Xu et al. Xu et al. (2021) introduced a solution that infers the latent label posterior via variational inference methods Blei et al. (2017), nevertheless, its effectiveness would be hardly guaranteed. In this paper, we propose POP for the ID PLL problem and theoretically prove that the learned classifier approximates well to the Bayes optimal.
PROPOSED METHOD
3.1 PRELIMINARIES
First of all, we briefly introduce some necessary notations. Consider multi-class classification problem of classes. Let X' = R2 be the g-dimensional instance space and y {1.2..... c} be the label space with e class labels. In supervised learning, let p(x, y) be the underlying "clean" distribution generating (ær, y²*) E X' x y from which i.i.d. samples ((.,, y² )]= are drawn.
In PLL. there is partial label space S == (S|S C V.S * 0) and the PLL training set 'D ((x,, S.)[1 S i S n) is sampled independently and identically from a "corrupted" density p(2r, S) over X x S. It is generally assumed that p(æ, y) and p(x, S) have the same marginal distribution of instances p(æ)). Then the generation process of partial labels can thus be formalized as p(S]æ)) = E, p(5|zz v))( We define the probability that, given the instance and its class label y", j-label being included in its partial label as the flipping probability:
şd (0)) = plj S|az, ",,, Vj V,
The key definition in PLL that the latent true label of an instance is always one of its candidate label, i.e., e² (x) 1.
We consider use deep models by the aid of an inverse link function Reidand & Williamson (2010) Φ IR" - where - denotes the c-dimensional simplex, for example, the softmax, as learning model in this paper. Then the goal of supervised multi-class classification and PLL is the same: a scoring function f f X + e-1 that can make correct predictions on unseen inputs. Typically, the classifier takes the form:
h(x) arg max (z). jEy
The Bayes optimal classifier h+ (learned using supervised data) is the one that minimizes the risk w.r. the 0-1 loss (or some classification-calibatee loss Bartlett et al. (2006)), i.e.,
h = arg min Roi arg min E. ((xY))=v (x),)))))))
(x(X)
For strictly proper losses Gneiting & Raftery 2007). the scoring function f recovers the class- posterior probabilities, i.e., (x) ply ))) Ve E X. When the supervision information available
3

---

Under review as a conference paper at ICLR 2023
is partial label, the PLL risk under p(x, S) w.r.t. suitable PLL loss C C: R x - R is defined as
R = E S)>p(( (()(
Minimizing R. induces the classifier and it is desirable that the minimizer approach h². In addition,
let arg max ply = j](²) be the class label with the second highest posterior possibility among all labels.
3.2 OVERVIEW
In the latter part of this section, will introduce a concept pure level set the region where the model is reliable. We prove that given a tiny reliable region, one could progressively enlarge this region and improves the model with sufficient rate by disambiguating the partial labels. Motivated by the theoretical results, we propose an approach PoP that works by progressively purifying the partial labels to move out the false candidate labels, and eventually the learned classifier could approximate the Bayes optimal classifier.
POP employs the observed partial labels to pre-train randomly initialized classifier for several epochs, and then updates both partial labels and the classifier for the remaining epochs. We start with warm-up period, in which we train the predictive model with a well-defined PLL loss Lv al. (2220) This allows us to attain reasonable predictive model before it starts fitting incorrect labels Zhang et al. (2017a). After the warm-up carm-uppeee period, we iteratively purify each partial label by moving out the candidate labels for which the current classifier has high confidence of being incorrect, and subsequently we train the classifier with the purified partial labels in the next epoch. After the model has been fully trained, the predictive model can perform prediction for unseen instances.
3.3 THE POP METHOD
We assume that the hypothesis class H. is sufficiently complex (and deep networks could meet this condition), such that the approximation error equals zero, i.c., arg min, R = arg mingew R and we have enough training data i.c., n + co. The classifier is able at least approximate the Bayes optimal classifier h* and the gap between the learned fxx and the the scoring function f faxx) cor- responding to h* is determined by the inconsistency between incorrect candidate labels and output of the Bayes optimal classifier.
For two instance x and z that satisfy p(y²(z) p(olz) > p(y" p(o|z)) i.e., the margin between the posterior of ground-truth label p(u* 2)) and the second high- est posterior possibility p(o]z)
larger than that point a, the indicator function (o))))=)) p(v"(=)- - p(olz) 2 p(y"|z) p(o[x), j E Sz] equals 1 if the candidate label j of is inconsistent with the output of the optimal Bayes classifier h² (z). Then, the gap between (x) and 1 (a:) i.e., the approximation error of the classifier, could be controlled by the inconsistency between the incorrect candidate labels and the output of the Bayes optimal classifier h² for all the instances z. Therefore, we assume that there exist constants a, E < 1, such that for f(x),
1z()))ff(a)) (E( (GVA)(=)) p(u²lz) p((0))) p(v))z) p(o]æ), JE Sz
+
(1)
where the scoring function f" corresponding to on strictly proper losses Gneiting & Raftery 2007] recovers the class-posterio probabilities, i.e., (zx = ply = j|æ)). In addition, for the probability density function d(u) of cumulative distribution function Duu) = P Pa-pp(a,)) (u(x))
(u(x: < u)
where 0 < < 1 and the margin u(x) ply" x)) -(ol==) we assume that there exist constants C., e* > such that c, < d() c*. Then, the worst-case density-imbalann
ratio is denoted by I = E. As the flipping probability of the incorrect label in the instance- dentene- generation process is related to its posterior probability, we assume that there exists a constant > 0 such that:
e (a) S ply = j(z)).
Motivated by the pure level set in binary classification Zhang et al. (202b)) we define the pure level set in instance-dependent PL.., i.e., the region where the model is reliable:
4

---

Under review as a conference paper at ICLR 2023
Definition 1 (Pure (e, fllvell set). A set L(e) == ( p(ol2)) 12 e} is pure for if y" = arg max, (z) ) for all æ E L(e).
Assume that there exists set L(e) for all æ E [(e) which satisfies y= arg max, fy fz)), we have
(0)))))))) ((x.s)))(..S)
[
p(y [2) 2) 2 ply m+) - p(olar), S= =
(3)
which means that there a tiny region L(e) == (0 p(o/2)) 12 e) where the model f reliable.
Let Cnew be the new boundary and Gla (z()"|z)) probability density function d((u) of the margin v(x)) = p(y*(z) p(( is bounded by
S e Cnew S 31a (p(8 e). As the
d(u) c², we have the following result for x that satisfies > ply x:) - p(olar) 2 know !
[ (O (x)) p(y5(=) - p(ol=) p(y" - p(ol2r), j jE Sz S 30
(4)
Combining Eq. ① and Eq. there is
1)(x))17(()) fzx -
(5)
Denote by m arg max, f, (z)) the label with the highest posterior probability for the current prediction. If fm) fj (x) 2 e c, we have |
p(y (x) 2 p(y= = j|)) +e
(6)
which means that the label j is incorrect label. Therefore, we could move the label j out from the candidate label set to disambiguate the partial label, and then refine the learning model with the
partial label with less ambiguity. In this way, we would move one step forward by trusting the model with the tiny reliable region with following theorem.
We start with a warm-up period, as the classifier is able to attain reasonable outputs before fitting label noise Zhang al. (2017a). Note that the warm-up training is employed find tiny reliable region and the ablation experiments show that the performance of POP does not rely on the warm-up strategy. The predictive model 0 could be trained on partially labeled examples by minimizing any PLL loss function. Here we adopt PRODEN loss Lv et al. 2020) to to find a tiny reliable region:
CPLL
wiy (m)))))
Here, is the cross-entropy loss and the weight wij initialized with with uniform weights and then could be tackled simply using the current predictions for slightly putting more weights more possible labels Lv et al. (2020):
Wij =
fs (xx) ( (a:)/Ejes, fo (ax))
if E St otherwise
Theorem Assume that we have enough training data(n - oo) and there is a pure (e, leeeel set where E Mee) can be correctly classified by For each x and Vj. S and j & m, if Im (x:) fx(x) 2 e + we move out label j from the candidate label set and then update the candidate label set as Snew- Then the new classifier fne trained on the updated data with the new distribution p(x, Snow). Let knew be the minimum boundary that L(enew) is pure for fnow. Then,
we have
p(y (x) Cnew 2 (1 + - (p(x e).
6ad
The detailed proof can be found in Appendix A. Theorem 1 shows that the purified region
ply æ)) - e would be enlarged by at least constant factor with the given purification strategy.
Moor details could be found in Appendix A.1. More details could be found in Appendix A.2.
5

---

After the warm-up period, the classifier could be employed for purification. According to Theorem 1. we could progressively move out the incorrect candidate label with the continuously strict bound, and subsequently train an effective classifier with the purified labels with the PLL loss Lv et al. (220)) since the PLL loss Lv et al. (2020) is model--ndeepnneet and could operates in mini- batched training manner to update the model with the Sabeling-confidence weight. Specifically, set a high threshold en and calculate the difference fm (x:) fx,) for each candidate label. there is label for H; satisfies fm (x,) (x;)) 2 co. move out it from the candidate label set Under review as a conference paper at ICLR 2023
Algorithm POP Algorithm
Input: The PLL training set D {(11, S1), (Zn, Sn)). initial threshold co, end threshold Cend. total round
R. step-size ex;
1: Initialize the predictive model 0 by warm-up training with the PL. loss Eq. and threshold eos
2: for r 1,.... R do
3: Train the predictive model f on D;
for: = 1..... do
5: for j S. S.Sdo do
6:
if fm, (m:) (a,) 2 e then
Purify incorrect jabel by removing from candidate lahel set St;
8:
end if end for
9:
10:
end for
11: e fend and there is no purification for any candidate lahel set then
12:
Decrease with step-size e;;
13:
end if end for
Output: The final predictive model f
and update the candidate label set. We depart from the theory by reusing the same fixed dataset over and over, but the empiries reasonable.
there no purification for all partial labels, we begin to decrease the threshold e and continue the purification for improving the training of the model. In this way, the incorrect candidate labels are progressively removed from the partial label round by round, and the performance of the classifier continuously improved. The algorithmic description of POP is shown Algorithm IT
Then we prove that if there exists a pure level set for an initialized model, our proposed approach can purify incorrect labels and the classifier will finally match the Bayes optimal classifier h after sufficient rounds R under the instance-dependent PLL setting
Theorem For any flipping probability of each incorrect label gd (x), define eg = (1++)a++ And 1+a
for a given function fo there exists level set L(eo) which is pure for fo- If one runs purification in Theorem 7 with enough traing data (n 50) starting with fo and the initialization: (1) eo Z
(1+t)++f
(2) R2RC2 61 log( 1- (3)eend 2 then we have:
1ta
Pa Pa-D Se-DlUSymmatee h" (x)) 2-
The proof of Theorem is provided in Appendix A.3. According to Theorem 2 the learned clas- sifier under the instance-dependent PLL setting will be consistent with the Bayes optimal classifier eventually. Theorem 2 shows that the classifier can be guaranteed eventually approximate the Bayes optimal classifier.
4 EXPERIMENTS
4.1 DATASETS
We adopt five widely used benchmark datasets including MNIST LeCun et al. (1998), Kuzushiji- ANIST'Clanuwar al. 2018), Fashion-MNIST Xiao et al. (017). CIFAR- 10 Krizhevsky & Hinton

---

Under review as a conference paper at ICLR 2023
Table 1: Classification accuracy (mean-sst)) of each comparing approach on benchmark datasets corrupted by the ID generation process.
MNIST
Kuzushiji-MNIS
Fashion-MNIST
CIFAR-I0
CIFAR- 100
POP
99.28=0.002%
91.09=0.14%
96.93=0.075
93.00:10.265
71.82:10.089 %
VALEN
99.03100.021
90.15 90.1510.022%
96.31 10.1%
71.48_0.12%
RCR
98.81=0.07%%
90.62=#0.225
96.64=0.115%
86,11
71.07=0.25%
PICO
98.76=0.004%
88.8 88.87=00.06%
94.83=0.117 17%
89.35 17%
66.30=0.24%
PRODEN
99.0110.02%%
90. 90.48.10.143
96.14.10.0%%
15.87.0.26%%
55.59_0..88%
99.09=0.09%%
90.56.20.14%
96.17:10.08%
80.13-10, 14%
56.41=0.17%
CC
99.08=0.10%
90.40:0.20%%
96.12=0.11%%
76.17=0.11%
56.48=0.06%
Lw
9
89.82.10.2%
93.23.10.08%
43.16100.3%
49.63_0.12%
CAVL
9..5%%
87.65%0006%%
95,84
75.41
58.17=0.11%
CLPL
98.83=0.05%%
90.21=0.08%
93.18=0.008%
51.61
30.84=0.40%
Table 2: Classification accuracy (mean--std) of each comparing approach the real-world datasets.
Lost
BirdSong
MSRCv2
Mirflickr
Malagasy
Soccer Player
Yahoo!News
PoP
78.57.10.45%
1..77:10.36%
40.26
61.09:00.105
12.29:00339%
54.48 0.10%
66.38 : 0.07%
VALEN
76.87:00869%
73. 13.39:+0.2665
49.97-:0433%
59 13::0.122 12%
69 4.%%0.00%
55.81=01108
66. 66.266::. 13%
PRODEN
75.47:1..25%
73.44:1.112 12%
15.10%0.166%
39.59=0.522%
69.3410.09%
54.05=0.15%
66.1411.109
RC
76.26:10.46%%
69.33:10.325%
49.47=:043%%
38.9310.10%%
70.69:10.14%
56.02.10.59%
63.51:10.200
6.590
69.53:10345%
49.07 0.36%
54.8610.488
Lw
73.13110.22%
51.45:10.200 0...0...66 26%
49.85=:0499%
04.5010.81%%
59.3410.25%%
50.24=0.45%
48.211:0.29
CaVL
73.96.10.51%%
69.63.10.93%%
46.62.1 1.29%
57.13:10.10%
65.82.10.06%
0.40%%
60.97.10.13%
CLPII
63.39-H0.12%
6..90-+3.333%
37.8+0.711%
58.87++0.10%
64.25-+:.29%
48.23-0.03%
49.42:+0.13%
2009 CIFAR- Krizhevsky & Hinton (009). These datasets are manually corrupted into ID partially labeled versions. Specifically, we set the flipping probability each incorrect label corre- sponding to an instance æ by using the confidence prediction of neural network trained using su-
pervised data parameterized by Ô Xu et al. 2021) The flipping probability (xx)
(w:0)
maxjcy fo (w:"))
where Y, is the of all incorrect labels except for the true label of z;- The average number of candidate labels (avg. #CLs) for each benchmark dataset corrupted by the ID generation process is recorded in Appendix A.4.
In addition, five real-world PL. datasets which are collected from different application domains are used, including Lost Lost Cour et al. (201T), ), Soccer Player Zeng et al.) (203)), Yahoo!News Guillaumin et al. (2010), MSRCv2 & Dietterich] (2012). and BirdSong Briggs et al. (2012). The average number of candidate labels (avg. #CLs) for each real-world PLL dataset is also recorded in Appendix A.4.
4.2 BASELINES
The performance of POP is compared against five deep PLL approaches:
Proden Lv et (200): A progressive identification approach which approximately minimizes a risk estimator and identifies the true labels in a seamless manner;
RC Feng et al. (220bb;: A risk-consistent approach which employs the loss correction strategy to establish the true risk by only using the partially labeled data;
CC Feng et al. (2020b): A classifier-comsistent approach which also uses the loss correction strat-
egy learn the classifier that approaches the optimal one;
VALEN Yao et al. (2020a): An ID PI.. approach which recovers the latent label distribution via
variational inference methods;
Lw Wen al. 2021): A risk-consistent approach which proposes leveraged weighted loss to trade off the losses on candidate labels and non-candidate ones.
CAVI. Zhang et al. (2021a): A progressive identification approach which exploits the class activa- tion value to identify the true label in candidate label sets.
CLPL Cour et al. 2011: A avearging- brased disambiguation approach based on a convex learning formulation.

---

Under review as a conference paper at ICLR 2023
Table 3: Classification accuracy (mean-std) of each comparing approach on benchmark datasets corrupted by the ID generation process.
MNIST
Kuzushiji MNIST
Fashion MNIST
CIFAR 10
CIFAR 100
PRODEN PRODEX+POP
97.70=0.03%
87.60=0.2346
87.21=0.11%
76.77=0.63%
15.1220.128
97.87-00.04%
88. 38.70+-0.02%
87.62-0.0449
79 79.00++0.28%
57.68-0.144 14%
97.72=0.02%%
87.25:0.066%
87.06=0.1498
76.49:0.5225
55.18=0.70%
RC+PoP
98.08=0.03%
87.78 09%
87.45=0.05%
78. 08.8990.115 17%
57.66=0.118
CC
97.25-0.111%
1.000%%
72.87:10.88
55.56110.23%
CC+POP
97.99:00.06%
83.98 I-0. 10%
86.32 0.06%
77.03-1-058840
56,18:00.069
Lw Lw4PoP
96,80=0.07%
84,46+0
86.25=0.01% %
16.77=00666%
48 18.00=0.106
97.47=0.06%
84,71 +00.0%
86, 86.40-0.068 0.05%
48. 08.54++0.0444
49.61=0022%%
CAVL
96.25=00:40%
79.38:20.6999 6.99
84,66 84.66=0.05%
62.69=: 6655%
47.35=0016%
CAVL+POP
96.71=0.11% %
79.83+t0. 12%
85,04=0. 10%
63.12=00.299
40.61=0.006
CLPL
96.11:10.21%
83.31 1.0.24%
83.16-0.255%
53.61110.31%
22.31
CLPL4POP
96.51-0.22%
83.63--0.11
83.71
54.22++0.51%
23.37+-0.29%
Table 4: Classification accuracy (mean:istd) of each comparing approach the real-world datasets.
Lost
BirdSong
MSRCv2
Malagasy
Soccer Player
Yahoo!News
PRODEN
76.47:10.25%
73.4410..28
45.10:0..1
09.59
69.34-0..9%%
54.05:10.15%
66.14:10.1
PRODEN+POP
78.57:0.45%
74.47110.66%
45.86:10.88 28%
61.0910.000 10%
72.29=0.33%
54.48:20110
66.38:10.07%
RC
76,2620.466
69.33:40.322 32%
49.4740.44 43%
58.9340.1 10%
70.69=0.149%
56.02=00.59%
63.51=0,2000
RC+PoP
0..56:
70.77.10.66%
71.04:0..10%
56.49-10.039
63.86
CC
63.54.1..55%
69.901005889
41.50:10.44%
58.81110.54%
69.53-00.44%
49.07.0.366%
54,86.10.48%
CC+POP
65.47:0093%%
71.50+000664
43.21 43%
59.8 $9,8940.44 48%
71.190044%
49. 49.36=0.0299
55.22:40.05%
Lw
73.13:00.32%
51.45:10.26%
49.85:0.499
04.5010.811
59.34:0.25%%
50.24:2045%%
48.21:10.9%%
Lw+PoP
75.30=+0.266
52.35:4:02665
52.42.0..8 86%
35.46+0.27%%
60.85+00577
50.94=0.4799
08.66..122
CAVI.
73.96
69.63-40.33%
46.62-4 2.2%
57.134-0.108
65 65.82::0.00%
52.92 0.40%
60.97 -770 1.
CAvl+Pop
15.32:20.11%
70.13::0.2%%
46.92:10.144
58.6310.48%
67.70=0.19%%
53.44:0.100 10%%
61.37:10.118 11%
CLPL
63,39:0. 12%
62, 02.90433.333
37 37..%%0711%
58.87=0.1100 10%
64.25=0.225 29%
48. 48.23=00.0%%
49.42:20. 13%
CLPL+POP
64.7
64.06:10.48%
39.32:10.4%%
60.311:.22%%
66.04=0.25%%
49.11=0.21%
50.33:10.18%
PICO Wang al. (2022b): tat-aaammnaationaaaeeeeee method which identifies the true label via contrastive-learning with learned prototypes for image datasets.
suugeenattion-aasee method which identifies the true label via con- sistency regularization with random augmented instances for image datasets.
RCR Wu et al. (2022): :
For the benchmark datasets, we use the same data augmentation strategy for the data-aug augmentation- free methods (VALEN, PRODEN, RC, CC, LW and CAVL. to make fair comparisons with the data- augmentation-baser methods (PICO and RCR). However, data augmentation cannot be employed on the realworld datasets that contain extracted feature from audio and video data, we just compared methods with the aata--ugmentttion free methods realworld datasets.
For the deep approaches, We used the same training/validation setting, models, and optimizer for fair comparisons. Specifically, 5-layer LeNet is trained MNIST, Kuzushiji-MNIST and Mushion-MNiS' the and CIFAR-100, and the linear model is trained on real-world PLL datasets, respectively. The hyper- parameters are selected so as to maximize the accuracy on a validation set (10% of the training set). We run trials the benchmark datasets and the real-world PI.I. datasets. The mean accuracy as well as standard deviation are recorded for all comparing approaches. All the comparing methods implemented with PyTorch
28-2 Zagoruyko & Komodakis (2016) is trained on CIFAR-10
4.3 EXPERIMENTAL RESULTS
Table and Table report the classification accuracy of each approach on benchmark datasets corrupted by the ID generation process and the real-world PLL datasets, respectively. Due to the inability of data augmentation to employed on extracted feature, we didn' compare our methods with PICO and RCR realworld datasets. The best results are highlighted in bold. We observe
8

---

Under review as a conference paper at ICLR 2023
Te AeTte scie
Figure 1: Estimated purified region on Lost.
Figure Syper-parameter sensitivity on CIFAR-10.
that POP achieves the best performance against other approaches most cases and the performance advantage of POP over comparing approaches is stable under varying the number of candidate labels.
In addition, to analysis the purified region in Theorem [ we employ the confidence predictions of (ar 0) (the network Section 4.1 as the posterior and plot the curve of the estimated purified region in every epoch on Lost in Figure [ We can see that although the estimated purified region would be not accurate enough, the curve could show that the trend continuous increase for the purified region.
4.4 FURTHER ANALYSIS
As the framework of Pop is flexible for the loss function, we integrate the proposed method with the previous methods for instance-independen PLL including PRODEN, RC, CC, Lw, CAVL and CL.PI. In this subsection, we empirically prove that the previous methods for instance-independent PLL could be promoted to achieve better performance after integrating with POP.
Tad report the classification accuracy of each method for instance- indeeeedenn PLL and its variant integrated with POP on benchmark datasets corrupted by the ID generating proce- dure and the real-world datasets, respectively. We didn't 't use any data augmentation on benchmark datasets in this part of experiments. As shown in Table TableBannd and Table 4 the approaches integrated with POP including PRODEN+POP. RC+POP, CC+POP LW+POP, CAVL+POP and CLPL+POP achieve superior performance against original method, which clearly validates the usefulness of PoP frame- work for improving performance for ID PI...
Figure illustrates the variant integrated with POP performs under different hyper-paramette figurations on CIFAR-10 while similar observations are also made on other data sets. The hyper- parameter sensitivity other datasets could be founded in Appendix A.4. As shown in Figure 3 obvious that the performance of the variant integrated with POP is relatively stable across broad range of each typer--arametee This property is quite desirable PoP framework could achieve robust classification performance.
CONCLUSION
In this paper, the problem of partial label learning is studied where novel approach POP is proposed. approach, which could
we consider partial label learning and propose a poooreticall-gguaranti train the classifier with progressive purification of the candidate labels and is theoretically guaran- teed to eventually approximates the Bayes optimal classifier for ID PLL. Experiments on benchmark and real-world datasets validate the effectiveness of the proposed method. If PLL methods become very effective, the need for exactly annotated data would be significantly reduced. As a result, the employment of data annotators might be decreased which could lead to negative societal impact.

---

Under review as a conference paper at ICLR 2023
REFERENCES
L.. Bartlett, M. I. Jordan, a.d D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138716,, 2006.
D. M. Blei, A. Kucukelbir, and J. D. McAuliffe. Variational inference: A review for statisticians. Journal of the American Statistical Association, (122518):55--777
F. Briggs, X. Z. Fern, and R. Raich. Rank-loss support instance machines for miml instance anno- tation. In Proceedings of 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'1 12), pp. 534-542, 2012.
Y. Chen, V. M. Patel, J. K. Pillai, R. Chellappa, and P. J. Phillips. Ambiguously labeled learning using dictionaries. IEEE Transactions on Information Forensics and Security, 9(12):20762 2014.
T. Clanuwat, M. Bober-Irizar A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha. Deep learning for classical japanese literature. arXiv preprint arXiv:1812.0177 2018.
Cour, B. Sapp, and B. Taskar. Learning from partial labels. Journal of Machine Learning Re- search, 12(5):1501-1536, 2011.
V. Feldman. Does learning require memorization? short tale about long tail. In Proccedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC'20), pp. 954-959, 2020.
L. Feng and B. An. Leveraging latent label distributions for partial label learning. In Proceedings of 27th International Joint Conference on Artificial Intelligence (IJCAI' 18), pp. 2107-2113, 2018.
L. Feng and B. An. Partial label learning with self- self-guided retraining. In Proceedings of 33rd AAAI Conference on Artificial Intelligence (AAAI'19)
3542-3549, 2019.
L. Feng. T. Kaneko, B. Han, G. Niu, B. An, and M. Sugiyama. Learning with multiple complemen- tary labels. In Proceedings of 37th International Conference on Machine Learning (ICMI. 20)), pp. 3072-3081 2020a.
L. Feng. J. Lv, B. Han, M. Xu, G. Niu, X. Geng, B. An, and M. Sugiyama. Provably consistent partial-label learning. Advances in Neural Information Processing Systems (Neur pp. 10948-10960, 2020b.
Dan Garrette and Jason Baldridge. Learning part-of-speech tagger from two hours of annotation. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 138 147,147,11 2013.
Tilmann Gneiting and Adrian E Raftery. Strietly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-37, 2007.
M. Guillaumin, Jakob Verbeek, and Cordelia Schmid. Multiple instance metric learning from auto- matically labeled bags of faces. In Proceedings of 11th European Conference on Computer Vision 10), volume 6311, I, pp. 634-647, 2010.
Mark J Huiskes and Michael S Lew. The mir flickr retrieval evaluation. In Proceedings of the 1st
ACM international conference on Multimedia information retrieval, pp. 39-43, 2008
E. Hüllermeier and J. Beringer. Learning from ambiguously labeled examples. Intelligent Data Analysis, 199-:499,, 2006.
T. Ishida, G. Niu, W. Hu, and M. Sugiyama. Learning from complementary labels. In Advances in Neural Information Processing Systems 30 (NewrIPS' pp. 5639-5649, 2017.
Ishida, G. Niu, A. K. Menon, and M. Sugiyama. Complementary-late learning for arbitrary losses and models. In Proceedings of 36th International Conference Machine Learning (ICML'19) 19), pp. 2971-2980, 2019.
R. Jin and Z. Ghahramani. Learning with multiple labels. In Advances in Neural Information Processing Systems 16 (NeurIPS 03), pp. 921-928, 2003.
10

---

Under review as a conference paper at ICLR 2023
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11):22782222) 1998.
L. Liu and T. G. Dietterich, A conditional multinomial mixture model for superset label learning. In Advances in Neural Information Processing Systems 25 (NIPS' 12), pp. 548-556, 2012.
J. Lv, M. Xu, L.. Feng, G. Niu, X. Geng, and M. Sugiyama. Progressive identification of true labels for partial-label learning. In Proceedings of 37th International Conference on Machine Learning (ICML'200 20), pp. 6500-6510, 10, 2020.
J. Lv, L. Feng, M. Xu, B. An, G. Niu, X. Geng, and M. Sugiyama. On the robustness of average losses for partial-label learning. arXiv preprint arXiv:2106.000 06.52,2,.066...... 2021.
G. Lyu, Y. Wu, and S. Feng. Partial label learning by semantic difference maximization. In Pro- ceedings of st International Joint Conference Artificial Intelligence, 2022.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
N. Nguyen and R. Caruana. Classification with partial labels. In Proceedings of 14th ACM SIGKDD Conference Knowledge Discovery and Data Mining (KDD'8)) pp. 551-559, 2008
G. Patrini, Rozza, K. Menon, R. Nock, and L. Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of 30th IEEE Conference on Computer Vision and Pattern Recognition (CVPR'I7) 17), pp. 1944 1952, 2017.
M. D. Reidand and R. C. Williamson. Composite binary losses. The Journal of Machine Learning Research, 1 1:2387-2422. 2010.
C. Tang and M. Zhang. Confidence-ruud discriminative partial label learning. Proceedings of 31st AAAI Conference on Artificial Intelligence (AAAI' 17), pp. 261 1617,2617, 2017.
H. Wang, R. Xiao, Y. Li, L. Feng, G. Niu, G. Chen, and J. Zhao. Pico: Contrastive label disam- biguation for partial label learning. In International Conference on Learning Representations, 2022a.
Haobo Wang. Ruixuan Xiao, Yixuan Li, Lei Feng, Gang Niu, Gang Chen, and Junbo Zhao. Pico: Contrastive label disambiguation for partial label learning. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022, 2022b.
H. Wen, J. Cui, H. Hang. J. Liu, Y. Wang, and Z. Lin. Leveraged weighted loss for partial label learning. In Proceedings of 36th International Conference Machine Learning (ICML'21), pp- 11091-11100, 2021.
Dong-Dong Wu, Deng-Bao Wang, and Min-Ling Zhang. Revisiting consistency regularization for deep partial label learning. In International Conference on Machine Learning, pp. 24212-24225. PMLR, 2022.
Z. Wu and M. Sugiyama. Learning with proper partial labels. arXiv preprint 12..v:2112.123003 2021.
X. Xia, T. Liu, B. Han, N. Wang, M. Gong, H. Liu, G. Niu, D. Tao, and M. Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. In Advances Neural Information Process- ing Systems 33 (NeurIPS 20), pp. 7597-7610, 2020.
H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747 2017.
N. Xu, J. Lv, and X. Geng. Partial label learning via label enhancement. In Proceedings of 33rd AAAI Conference on Artificial Intelligence (AAA/'/9), pp. 5557-5564, 2019.
N. Xu, C. Qiao, X. Geng, and M. Zhang. Instance-dependent partial label learning. Advances in Neural Information Processing Systems 34 (NeurIPS 2021.
2021.
11

---

Under review as a conference paper at ICLR 2023
Y. Yao, C. Gong, J. Deng, X. Chen, J. Wu, and J. Yang. Deep discriminative with temporal en- sembling for ambiguously-labelec image classification. In Proceedings of 34th AAAI Conference on Artificial Intelligence (AAAI20), pp. 12666,, 2020a.
Y. Yao, C. Gong, Deng, and J. Yang. Network cooperation with progressive disambiguation for partial label learning. In The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), pp. 4714474146 2020b.
X. Yu, T. Liu, M. Gong, and D. Tao. Learning with biased complementary labels. In Proceedings of 15th European Conference on Computer Vision (ECCV' pp. 68-83, 2018.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016.
Wide residual networks.
arXiv preprint
Z. Zeng, S. Xiao, K. Jia, T. Chan, S. Gao, D. Xu, and Y. Ma. Learning by associating ambigu- ously labeled images. In Proceedings of 26th IEEE Conference on Computer Vision and Pattern Recognition (CVPR' 13), pp. 708-7 718-715,27 2013.
C. Zhang, S. Bengio, M. Hardt, Recht, and Or. Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017a.
F. Zhang, L. Feng, B. Han, T. Liu, G. Niu, T. Qin, and M. Sugiyama. Exploiting class activation value for partial-labe learning. In International Conference on Learning Representations, 2021a.
M. Zhang and F. Yu. Solving the partial label learning problem: An instance-based approach. In Proceedings of 24th International Joint Conference on Artificial Intelligence (IJCAI 15), pp. 4048-4054, 2015.
M. Zhang. B. Zhou, and X. Liu. Partial label learning via feature-aware disambiguation. In Proceed- ings of 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD' 16), pp. 1335-1344, 2016.
M. Zhang, F. Yu, and C. Tang. Disambiguation-free partial label learning. JEEE Transactions on Knowledge and Data Engineering. 29(10):2155-216; 2017b.
Y. Zhang, S. Zheng, P. Wu, M. Goswami. and C. Chen. Learning with feature-dependent label noise: progressive approach. In Proceedings of 9th International Conference on Learning Representations (ICLR'21), 2021b.
A APPENDIX
A.1 PROOFS OF THEOREM
Assume that there exists set L(e) for all x E I(e) which satisfies y = arg max, fz(x) and p(y" x) p(ol==) 2 e, we have
B(,,S)~((e.Smw)
(oot p()=l2) - p(ol2) p(y²(())) -p(o(t) jE Sz2] =0
(9)
Let Cnew be the new boundary and probability density function d(u) of the margin u(x=) p(y*(z)) ((ooz)) bounded by c.
- e) s c Cnew S 3te - (p(x" e). As the
12

---

Under review as a conference paper at ICLR 2023
d(u) <t', we have the following result for that satisfies p(y (x) p(o/x))
2
coew
((x ((
Sx.ply p(o|=) ply -
1 (() - p -((}))) p(o
=Ps j # h² p p
Ps li + h- |
- Fx [ -l0)) -
F- li h (2) Curw < <((v -(( <e
P= [p(y* - 2 -((]]]
Pz plo
p(o[z)
P= [j A hn()))
Ps
P= p(o))
Pz 1p(y" b>) p(o[z) 2 p(y p(0
(10)
P= [ # 16" (2), Cnow
Cnew S p(y p(o]=) <
P= 1p(y*12 (2) p(o 2) 2 p() p[o[=)]
P- [p((")== c
= 8)=
1 ( (()ā p(ol=) 2
P2 - 2 p(u a)) p()
=00Acconling to Ee
Pz li + U² , Feew S p(y
<]
+ Ps p((r= -
Ps (enww 12) p(oo=)) x(opx)
Px [2( 2)
p(o|z) 2 p(v*(0) p()
c² (E Cnew)
(p(y* (x) e)
Due to that 6la (p(y") -) Se- Cnew S sia (p() - e) holds, we can further relax Eq. 10) as follows:
e
B(z.8))((Z,Simn) [1oPareen Sz, p(s 22) - p(o|z) 2 p(2" xx) p(o|z))
(e (new)
(p(y
(11)
c. (ply (x) e) 3la (p() e)
3a
Then, we can find that the assumption that the gap between [5(x)) and fJ should be controlled by the risk at point z implies:
(x) (z)
[ (( p((+1z) (1(0))))))p((((1))) - p(olz) 2 ply ar) p(o/zz)) - + 6
< Ox (x ((ec
(12)
e
a +
3a
2
Hence, for x s.t. p<)= - p(o|2)) 2 Cnew. according to Eq. 12 we have
fg=(x)
f (x) Z (p(y 1 ()) ) (p(y j|z) + ?
(
puy y" xx) ply j|æ) e
> plu v" x)) p(o/z)
(13)
know
2 0,
Details of Eq. (3) in the paper submission
13

---

Under review as a conference paper at ICLR 2023
Figure 3:
sensitivity on Lost.
which means that (xx) will be the same label h+ and thus the level set [(enew) is pure for f.
Meanwhile, the choice of Cnew ensures that
ply
Enew 2 p(y xx) (e
6la (p(v*xz) -e))
p(y" (z) e 6la (x()))x) e)
(14)
= (1 Me(v" - e).
Gla
Here, the proof of Theorem has been completed.
A.2 DETAILS OF EQ. (5)
fm. (2) - fjmm 2 e + c, according to Eq.
12
we have:
(z) 2 ply = m [x)
ply [z) + p(y m m|x) ply j j|
2 p(y = j | + p(y = m ()) ply = jØ)
2 p(y 5|²=) + (f 9) (f)()) 2
(15)
p(y = 1|0) + (Jm [1(x)) -
2 p(y j|z) + (c+
p(y j|æ)) +
A.3 PROOPS OF THEOREM 2
To begin with, we prove that there exists least a level set I(ea) pure fo. Considering æ
satisfies p(y*)a) (r) p(o|æ)) 2 co. have P- + h (=)) Sz, 12) p(o|2) 2 c0
p(v=1z) eo + (z).
Due to the assumption (f)())
fz()) S
(LE(2.))~((E.S) (1x4)0(0))) j (..Sp((((() - p(o|z) 2 p(y*(z) - p(o x))
5. suffices
satisfy a(p()*(a:) - co + + + S ep to ensure that fa( has the same prediction with h* when p(y*(x) xx) p(oo=) 2 en- Since we have (x) < p(y = j(m)( S p2), by choosing (1+1)++ (1+)) co Ita
ensure that initial fo has pure L(ev)-level set.
Then in the rest of the iterations ensure the level set -() is pure. We decrease by a reasonable factor to avoid incurring too many corrupted labels while ensuring enough progress in label purification, i.e. af. (p e) Cnew & sia (p(y (m)) e), such that in the
14

---

Under review as a conference paper at ICLR 2023
Table 5: Characteristic of the benchmark datasets corrupted by the ID generation process.
Dataset
#Train
#Test
#Features
#Class Labels
avg. #CLs
MNIST
60000
10000
784
10
8.71
Aishion-MNIST
60,000
10,000
784
10
3.46
KuzushijiMNNIST
60,000
10,000
784
10
3.87
CIFAR-10
50,000
10,000
3,072
10
3.68
CIFAR-100
50,000
10,000
3,072
100
4.64
Table Characteristic of the real-world PLL datasets.
Dataset
#Train
#Test
#Features
#Class Labels
avg. #CL.
Task Domain
Lost
898
224
108
16
2.23
automatic face naming Cour al
201
MSRCV2
object classification Liu Dietterich
2012
Mirflickr
2224
556
1536
2.76
weh image classification Huiskes & Lew 2008
BirdSong
3,998
1,000
38
13
2.18
bird song classihcation Briggs et 2012
Malagasy
POS Tagging Garrette Buldridge 2013
Soccer Player 13,978
3,494
279
171
2.09
automatic face naming Zeng Zaming et al
2013
Yahoo! News 18,393
4,598
163
219
1.91
automatic face naming Guillaumin
2010
level set pz) p(olz) > Enew have (z) - (a)) < 5. This condition ensures the correctness of flipping when e 2 E. The the purified region cannot be improved once e < e since there is no guarantee that f, (z) has consistent label with ht when p(y x>) p(o x) (z) - fj (a) I 5. To get the largest purified region, we can set Eead = e. Since the probability
and
density function d(u) the margin u(x) = p(y* p(o]z) is bounded by c. S d(u) I c*, we have:
PA~ Pa-DDyJffmatte (()) # ht1 S Plp(y (x) p(o x) eand]
P pp (x) p(o|x) e]
(16)
Seee.
Then Pan-Dlyf h*] F mlytt + h*] 2 c²c. log(
The rest of the proof is the total round Rt 2 Ga! round of label flipping improves the the purified region by a factor of (1 + st.) ):
_ which follows from the fact that each
c
(1
=
n
(p(2* 2) eo) 2 p(y"
6la
-
+ _ R p(y*(x)- -E
p xx) - 6p
(1+ e ) log
p110 (2z)
Rlog
(17)
p(y² x))
p(y (x)
R 6la
> Rlog
1 bla
> log
p x) - Eg
6la
ply x))
6la log E0
R log
>
((y*12)
co
A.4 DETAILS OF EXPERIMENTS
We collect four widely used benchmark datasets including MNIST LeCun et al. (1998), Kuzushiji- MNIST Clanuwat et al. (2018) B, Mashion-MNIST Xiao et al. a (017)). CIFAR- 10 Krizhevsky & Hinton 2209),, CIFAR- 100 Krizhessky & Hinton (209)). In addition, five real-world PLL datasets are adopted, which are collected from several application domains including Lost Cour et al. (2011), Soccer Player Zeng et al. (2013) and Yahoo News Guillaumin et al. (001)) for automatic face naming from images videos, MSRCv2 Liu & Dietterich (2012) for object classification, and
15

---

Under review as a conference paper at ICLR 2023
BirdSong Briggs et al. (0112) for bird song classification. Figure CalurtBiilusttatees the variant integrated with POP performs under different haper-parameter configurations on Lost.
The average number of candidate labels (avg. #CLs) for each benchmark dataset corrupted by the ID generation process is recorded in Table and the average number candidate labels (avg. #CLs)
for each real-world PLL dataset is recorded in G
16


Reviews:
[{"review_id": "Gf5A2I2Oyif", "reviewer": "Reviewer_T9T6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a theoretically grounded and practically effective approach to deal with the instance-dependent partial label learning problem. This paper updates the learning model while purifying each PL for the next epoch of the model training by progressively moving out false candidate labels. Theoretically, the authors prove that the proposed approach enlarges the region appropriately fast where the model is reliable, and eventually approximates the Bayes optimal classifier with mild assumptions. In addition, the proposed approach is flexible with arbitrary losses and compatible with deep networks, so that the previous advanced losses for partial label learning can be embedded in it and the performance is often significantly improved. Experimental results on various datasets validate the effectiveness of the proposed method. ", "summary_of_the_review": "This paper is novel and solid, and the theoretical guarantee is a nice result.", "strength_and_weaknesses": "Strengths:\n1. This paper provides a new perspective on improving the accuracy of instance-dependent partial label learning. \n2. The proposed approach can be guaranteed to enlarge the region and approximates the Bayes optimal classifier with mild assumptions, which is the first theoretically guaranteed approach for instance-dependent partial label learning. \n3. The proposed approach is flexible with arbitrary losses and compatible with deep networks, so that the previous advanced losses for partial label learning can be embedded in it and the performance is often significantly improved. \n4. The theoretical justifications and empirical validations are strong. I believe this work is solid.\n\nWeaknesses:\n1. This paper could give more discussion about the reason why adopt the PLL loss in Eq. (7) to initialize the model.\n2. It would be nice to validate the proposed method on more real-world partial label learning datasets.\n3. The authors should give more details about how to estimate the purified region in every epoch in Figure 1. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "F0hQzrdTQa", "reviewer": "Reviewer_K87B", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors propose and test an algorithm for the instance-dependent partial label learning setting.", "summary_of_the_review": "It needs a significant rewrite and Theorem 1 coupled with Algorithm 1 is, as stated, incorrect.", "strength_and_weaknesses": "This paper presumably has multiple good ideas embedded in it, but the exposition is so poor that this reviewer just gave up trying to understand it.\n\nThe trouble really starts in section 3.3:\n  * the indicator function is introduced as equivalent to \"inconsistent with the Bayes classifier\" but it is unclear what this means.\n  * then equation (1) is presented, which is highly confusing.\n    * On the left hand side is \"f^j\" (also sometimes called \"f_j\" in the text ...), but what is \"f\"?  The reader can eventually deduce, if they make it as far as equation (6), that \"f\" means \"the prediction of some model in the model class which is the resulting of training on the data\".\n    * On the right hand side are quantities that are problem dependent but not current model dependent.  (I think?  It's hard to tell ...)\n    * So, without remark, equation (1) appears to require a strong uniform property over the hypothesis class.\n  * then we have some unclear terminology on \"density of the margin\" leading to a bound on a heretofore undefined quantity \"density-imbalance ratio\" (what is that?)\n  * finally we arrive at Definition 1, which is the first clear thing said in section 3.3.  \n  * **constructive feedback**: rewrite all of section 3.3 to be as clear as definition 1, don't try to save space, and get some help from somebody with good english language writing skills to proofread.\n\nThen there's Theorem 1.  It talks about an updated data distribution, but the associated Algorithm 1 reuses the same data set.  Only the first pass over this data set can be considered an IID sample from the true distribution.  Every subsequent pass is a data-dependent quantity and no longer IID.  **constructive feedback**: 1) rewrite algorithm 1 assuming access to more data and then consume the data as a stream and filter it using the current margin condition so that it really is an IID draw from a distribution and 2) modify theorem 1 to align with the modified algorithm 1 and then 3) if you don't want to redo all your experiments just say \"we depart from the theory by reusing the same fixed dataset over and over, but the empirics are reasonable\".  (The truth is, experiments often depart from the theory in some way, as long as you are clear on this it doesn't bother this reviewer).\n\nAt this point the reviewer just stopped (actually truthfully I peeked at Tables 1 and 2 and the lifts seemed rather modest and then stopped).  The meta-feedback is, if you don't have clarity, you will lose the modern reviewer, because the quantity of papers to review has gone up and the quality has gone down, so patience is at a historic minimum.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6UeiW71y6hz", "reviewer": "Reviewer_T1k7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors have proposed a method for instance-dependent partial-label learning with theoretical guarantees. The method progressively moves out false candidate labels during the training. The experimental results demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "My largest concern is the assumption used for theoretical analysis. It would be great if the authors can make some justification for the assumption that that when will exist a boundary $e$ for all $x$ which satisfies $y^x$ = $\\arg\\max_j f_j(x)$ and $p(y^x|x)− p(o|x) \\geq e$.", "strength_and_weaknesses": "Strength:\n+ The research problem is important and may have many practical applications. The generative of partial labels in real-world datasets may depend on instances. How to improve the robustness of learning models in this setting can be a challenging and important research problem.\n+ The authors have shown that the proposed estimator can approximate the Bayes optimal classifier under some assumptions.\n+ This paper generally is well-written and easy to follow.\nWeakness:\n+ The theoretical guarantee rely on the assumption that there exists a boundary $e$ for all $x$ which satisfies $y^x$ = $\\arg\\max_j f_j(x)$ and $p(y^x|x)− p(o|x) \\geq e$. It seems that this assumption can be a little bit strong. I think it would be great to add some justification.\n+ The empirical improvement of the proposed method on real-world datasets seems not large. \n+ It seems that this paper is related to the paper: “Progressive Identification of True Labels for Partial-Label Learning”. It would be great to provide some justifications from the perspective of the major technical contribution.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0H1V8RyZG4", "reviewer": "Reviewer_s5av", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is proposed to achieve better performance both practically and theoretically on the problem of Instance-Dependent Partial Label Learning. To be more detailed, a purification strategy is proposed in this paper. This method works in an alternative update manner on both model and dataset: in each round, the model is first updated using the partially labeled dataset, and then a purification strategy is applied to remove labels that are regarded as 'incorrect' in each data point' partial label set. With mild assumptions, the authors show that their method is statistically consistent. Experimental results also show the efficiency of their method. ", "summary_of_the_review": "This paper proposed a method for instance-dependent partial-label learning that is valid both theoretically and practically.", "strength_and_weaknesses": "Strengths:\n1. The implementation of the proposed method is described in detail and all the claims in this paper are provided with theoretical justification. Experimental results also show that it can enhance the performance of existing PLL methods.\n2. The proposed Pop method focuses on updating the partial-label set, which does not rely on the update of the model. This indicates that it can be combined with any partial-label learning method.\n\nWeaknesses:\n1. In Section 3.1, it is indicated that a score-based classifier $h(x)$ that achieves the best accuracy can recover the class-posterior probability after a softmax transformation. It is not true if there are no restrictions on the type of used surrogate loss. \n\n2. In Section 2, the related works are split into two different categories: deep and non-deep PLL. However, I think the method CLPL [1] can also be combined with deep models since it makes no assumption on the type of model. I think the authors should discuss more CLPL and add the experimental results of it as in the previous work of deep PLL [2].\n\n[1]. T. Cour, B. Sapp, and B. Taskar. Learning from partial labels. Journal of Machine Learning Research, 12(5):1501–1536, 2011.\n\n[2]. L. Feng, J. Lv, B. Han, M. Xu, G. Niu, X. Geng, B. An, and M. Sugiyama. Provably consistent partial-label learning. In Advances in Neural Information Processing Systems 33 (NeurIPS’20),pp. 10948–10960, 2020b. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject