Year: 2021

Abstract:
Partial label learning (PLL) is an important problem that allows each training example to be labeled with a coarse candidate set, which well suits many real-world data annotation scenarios with label ambiguity. Despite the promise, the performance of PLL often lags behind the supervised counterpart. In this work, we bridge the gap by addressing two key research challenges in PLL—representation learning and label disambiguation—in one coherent framework. Specifically, our proposed framework PiCO consists of a contrastive learning module along with a novel class prototype-based label disambiguation algorithm. PiCO produces closely aligned representations for examples from the same classes and facilitates label disambiguation. Theoretically, we show that these two components are mutually beneficial, and can be rigorously justified from an expectationmaximization (EM) algorithm perspective. Extensive experiments demonstrate that PiCO significantly outperforms the current state-of-the-art approaches in PLL and even achieves comparable results to fully supervised learning.

heading: 1 INTRODUCTION
text: The training of modern deep neural networks typically requires massive labeled data, which imposes formidable obstacles in data collection. Of a particular challenge, data annotation in the real-world can naturally be subject to inherent label ambiguity and noise. For example, as shown in Figure 1, identifying an Alaskan Malamute from a Siberian Husky can be difficult for a human annotator. The issue of labeling ambiguity is prevalent yet often overlooked in many applications, such as web mining (Luo & Orabona, 2010) and automatic image annotation (Chen et al., 2018). This gives rise to the importance of partial label learning (PLL) (Hüllermeier & Beringer, 2006; Cour et al., 2011), where each training example is equipped with a set of candidate labels instead of the exact groundtruth label. This stands in contrast to its supervised counterpart where one label must be chosen as the “gold”. Arguably, the PLL problem is deemed more common and practical in various situations due to its relatively lower cost to annotations.
Despite the promise, a core challenge in PLL is label disambiguation, i.e., identifying the groundtruth label from the candidate label set. Existing methods typically require a good feature representation (Liu & Dietterich, 2012; Zhang et al., 2016; Lyu et al., 2021), and operate under the assumption that data points closer in the feature space are more likely to share the same ground-truth label. However, the reliance on representations has led to a non-trivial dilemma—the inherent label uncertainty can undesirably manifest in the representation learning process—the quality of which may in turn prevent effective label disambiguation. To date, few efforts have been made to resolve this.
This paper bridges the gap by reconciling the intrinsic tension between the two highly dependant problems—representation learning and label disambiguation—in one coherent and synergistic framework. Our framework, Partial label learning with COntrastive label disambiguation (dubbed PiCO), produces closely aligned representations for examples from the same classes and facilitates label disambiguation. Specifically, PiCO encapsulates two key components. First, we leverage contrastive learning (CL) (Khosla et al., 2020) to partial label learning, which is unexplored in previous PLL literature. To mitigate the key challenge of constructing positive pairs, we employ the classifier’s output and generate pseudo positive pairs for contrastive comparison (Section 3.1). Second, based on the learned embeddings, we propose a novel prototype-based label disambiguation strategy (Section 3.2). Key to our method, we gradually update the pseudo target for classification, based
on the closest class prototype. By alternating the two steps above, PiCO converges to a solution with a highly distinguishable representation for accurate classification. Empirically, PiCO establishes state-of-the-art performance on three benchmark datasets, outperforming the baselines by a significant margin (Section 4) and obtains results that are competitive with fully supervised learning.
Theoretically, we demonstrate that our contrastive representation learning and prototype-based label disambiguation are mutually beneficial, and can be rigorously interpreted from an ExpectationMaximization (EM) algorithm perspective (Section 5). First, the refined pseudo labeling improves contrastive learning by selecting pseudo positive examples accurately. This can be analogous to the E-step, where we utilize the classifier’s output to assign each data example to one label-specific cluster. Second, better contrastive performance in turn improves the quality of representations and thus the effectiveness of label disambiguation. This can be reasoned from an M-step perspective, where the contrastive loss partially maximizes the likelihood by clustering similar data examples. Finally, the training data will be mapped to a mixture of von Mises-Fisher distributions on the unit hypersphere, which facilitates label disambiguation by using the component-specific label. Our main contributions are summarized as follows:
1 (Methodology). To the best of our knowledge, our paper pioneers the exploration of contrastive learning for partial label learning and proposes a novel framework termed PiCO. As an integral part of our algorithm, we also introduce a new prototype-based label disambiguation mechanism, leverages the contrastively learned embeddings.
2 (Experiments). Empirically, our proposed PiCO framework establishes the state-of-the-art performance on three PLL tasks. Moreover, we make the first attempt to conduct experiments on fine-grained classification datasets, where we show classification performance improvement by up to 9.61% compared with the best baseline on the CUB-200 dataset.
3 (Theory). We theoretically interpret our framework from the expectation-maximization perspective. Our derivation is also generalizable to other CL methods and shows the alignment property in CL (Wang & Isola, 2020) mathematically equals the M-step in center-based clustering algorithms.
2 BACKGROUND
The problem of partial label learning (PLL) is defined using the following setup. Let X be the input space, and Y = {1, 2, ..., C} be the output label space. We consider a training dataset D = {(xi, Yi)}ni=1, where each tuple comprises of an image xi ∈ X and a candidate label set Yi ⊂ Y . Identical to the supervised learning setup, the goal of PLL is to obtain a functional mapping that predicts the one true label associated with the input. Yet differently, the PLL setup bears significantly more uncertainty in the label space. A basic assumption of PLL is that the groundtruth label yi is concealed in its candidate set, i.e., yi ∈ Yi, and is invisible to the learner. For this reason, the learning process can suffer from inherent ambiguity, compared with the supervised learning task with explicit ground-truth.
The key challenge of PLL is to identify the ground-truth label from the candidate label set. During training, we assign each image xi a normalized vector si ∈ [0, 1]C as the pseudo target, whose entries denote the probability of labels being the ground-truth. The total probability mass of 1 is allocated among candidate labels in Yi. Note that si will be updated during the training procedure. Ideally, si should put more probability mass on the (unknown) ground-truth label yi over the course of training. We train a classifier f : X → [0, 1]C using cross-entropy loss, with si being the target prediction. The per-sample loss is given by:
Lcls(f ;xi, Yi) = ∑C
j=1 −si,j log(f j(xi)) s.t. ∑ j∈Yi si,j = 1 and si,j = 0,∀j /∈ Yi, (1)
where j denotes the indices of labels. si,j denotes the j-th pseudo target of xi. Here f is the softmax output of the networks and we denote f j as its j-th entry. In the remainder of this paper, we omit the sample index i when the context is clear. We proceed by describing our proposed framework.

heading: 3 METHOD
text: In this section, we describe our novel Partial label learning with COntrastive label disambiguation (PiCO) framework in detail. In a nutshell, PiCO comprises two key components tackling the representation quality (Section 3.1) and label ambiguity respectively (Section 3.2). The two components systematically work as a whole and reciprocate each other. We further rigorously provide a theoretical interpretation of PiCO from an EM perspective in Section 5.

heading: 3.1 CONTRASTIVE REPRESENTATION LEARNING FOR PLL
text: The uncertainty in the label space posits a unique obstacle for learning effective representations. In PiCO, we couple the classification loss in Eq. (1) with a contrastive term that facilitates a clustering effect in the embedding space. While contrastive learning has been extensively studied in recent literature, it remains untapped in the domain of PLL. The main challenge lies in the construction of positive sample set. In conventional supervised CL frameworks, the positive sample pairs can be easily drawn according to the ground-truth labels (Khosla et al., 2020). However, this is not straightforward in the setting of PLL.
Training Objective. To begin with, we describe the standard contrastive loss term. We adopt the most popular setups by closely following MoCo (He et al., 2020) and SupCon (Khosla et al., 2020). Given each sample (x, Y ), we generate two views—a query view and a key view—by way of randomized data augmentation Aug(x). The two images are then fed into a query network g(·) and a key network g′(·), yielding a pair of L2-normalized embeddings q = g(Augq(x)) and k = g′(Augk(x)). In implementations, the query network shares the same convolutional blocks as the classifier, followed by a prediction head (see Figure 2). Following MoCo, the key network uses a momentum update with the query network. We additionally maintain a queue storing the most current key embeddings k, and we update the queue chronologically. To this end, we have the following contrastive embedding pool:
A = Bq ∪Bk ∪ queue, (2) where Bq and Bk are vectorial embeddings corresponding to the query and key views of the current mini-batch. Given an example x, the per-sample contrastive loss is defined by contrasting its query embedding with the remainder of the pool A,
Lcont(g;x, τ, A) = − 1 |P (x)| ∑ k+∈P (x) log exp(q>k+/τ)∑ k′∈A(x) exp(q >k′/τ) , (3)
where P (x) is the positive set and A(x) = {A\{q}}. τ ≥ 0 is the temperature. Positive Set Selection. As mentioned earlier, the crucial challenge is how to construct the positive set P (x). We propose utilizing the predicted label ỹ = arg maxj∈Y f j(Augq(x)) from the classifier. Note that we restrict the predicted label to be in the candidate set Y . The positive examples are
then selected as follows,
P (x) = {k′|k′ ∈ A(x), ỹ′ = ỹ}. (4)
where ỹ′ is the predicted label for the corresponding training example of k′. For computational efficiency, we also maintain a label queue to store past predictions. In other words, we define the positive set of x to be those examples carrying the same approximated label prediction ỹ. Despite its simplicity, we show that our selection strategy can be theoretically justified (Section 5) and also lead to superior empirical results (Section 4). Note that more sophisticated selection strategies can be explored, for which we discuss in Appendix B.4. Putting it all together, we jointly train the classifier as well as the contrastive network. The overall loss function is:
L = Lcls + λLcont. (5)
Still, our goal of learning high-quality representation by CL relies on accurate classifier prediction for positive set selection, which remains unsolved in the presence of label ambiguity. To this end, we further propose a novel label disambiguation mechanism based on contrastive embeddings and show that these two components are mutually beneficial.

heading: 3.2 PROTOTYPE-BASED LABEL DISAMBIGUATION
text: As we mentioned (and later theoretically prove in Section 5), the contrastive loss poses a clustering effect in the embedding space. As a collaborative algorithm, we introduce our novel prototype-based label disambiguation strategy. Importantly, we keep a prototype embedding vectorµc corresponding to each class c ∈ {1, 2, ..., C}, which can be deemed as a set of representative embedding vectors. Categorically, a naive version of the pseudo target assignment is to find the nearest prototype of the current embedding vector. Notably this primitive resembles a clustering step. We additionally soften this hard label assignment version by using a moving-average style formula. To this end, we may posit intuitively that the employment of the prototype builds a connection with the clustering effect in the embedding space brought by the contrastive term (Section 3.1). We provide a more rigorous justification in Section 5.
Pseudo Target Updating. We propose a softened and moving-average style strategy to update the pseudo targets. Specifically, we first initialize the pseudo targets with a uniform distribution, sj = 1 |Y | I(j ∈ Y ). We then iteratively update it by the following moving-average mechanism,
s = φs+ (1− φ)z, zc = {
1 if c = arg maxj∈Y q>µj , 0 else
(6)
where φ ∈ (0, 1) is a positive constant, and µj is a prototype corresponding to the j-th class. The intuition is that fitting uniform pseudo targets results in a good initialization for the classifier, since the contrastive embeddings are less distinguishable at the beginning. The moving-average style strategy then smoothly updates the pseudo targets towards the correct ones, and meanwhile ensures stable dynamics of training; see Appendix B.2. With more rigorous validation provided later in Section 5, we provide an explanation for the prototype as follows: (i)-for a given input x, the closest prototype is indicative of its ground-truth class label. At each step, s has the tendency to slightly move toward the one-hot distribution defined by z based on Eq. (6); (ii)-if an example consistently points to one prototype, the pseudo target s can converge (almost) to a one-hot vector with the least ambiguity.
Prototype Updating. The most canonical way to update the prototype embeddings is to compute it in every iteration of training. However, this would extract a heavy computational toll and in turn cause unbearable training latency. As a result, we update the class-conditional prototype vector similarly in a moving-average style:
µc = Normalize(γµc + (1− γ)q), if c = arg maxj∈Y f j(Augq(x))), (7)
where the momentum prototype µc of class c is defined by the moving-average of the normalized query embeddings q whose predicted class conforms to c. γ is a tunable hyperparameter.

heading: 3.3 SYNERGY BETWEEN CONTRASTIVE LEARNING AND LABEL DISAMBIGUATION
text: While seemingly separated from each other, the two key components of PiCO work in a collaborative fashion. First, as the contrastive term favorably manifests a clustering effect in the embedding space, the label disambiguation module further leverages via setting more precise prototypes. Second, a set of well-polished label disambiguation results may, in turn, reciprocate the positive set construction which serves as a crucial part in the contrastive learning stage. The entire training process converges when the two components perform satisfactorily. We further rigorously draw a resemblance of PiCO with a classical EM-style clustering algorithm in Section 5. Our experiments, particularly the ablation study displayed in Section 4.3, further justify the mutual dependency of the synergy between the two components. The pseudo-code of our complete algorithm is shown in Appendix C.

heading: 4 EXPERIMENTS

heading: 4.1 SETUP
text: Datasets and Baselines. First, we evaluate PiCO on two commonly used benchmarks — CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2009). Adopting the identical experimental settings in previous work (Lv et al., 2020; Wen et al., 2021), we generate partially labeled datasets by flipping negative labels ȳ 6= y to false positive labels with a probability q = P (ȳ ∈ Y |ȳ 6= y). In other words, all C − 1 negative labels have a uniform probability to be false positive and we aggregate the flipped ones with the ground-truth to form the candidate set. We consider q ∈ {0.1, 0.3, 0.5} for CIFAR10 and q ∈ {0.01, 0.05, 0.1} for CIFAR-100. In Section 4.4, we further evaluate our method on fine-grained classification tasks, where label disambiguation can be more challenging.
We choose the five best-performed partial label learning algorithms to date: 1) LWS (Wen et al., 2021) weights the risk function by means of a trade-off between losses on candidate labels and the remaining; 2) PRODEN (Lv et al., 2020) iteratively updates the latent label distribution in a selftraining style; 3) CC (Feng et al., 2020b) is a classifier-consistent method that assumes set-level uniform data generation process; 4) MSE and EXP (Feng et al., 2020a) are two simple baselines that adopt mean square error and exponential loss as the risks. The hyperparameters are tuned according to the original methods. The detailed implementation of our method PiCO is presented in Appendix B.1. For all experiments, we report the mean and standard deviation based on 5 independent runs (with different random seeds). Source code of PiCO is attached in the Supplementary.

heading: 4.2 MAIN EMPIRICAL RESULTS
text: PiCO achieves SOTA results. As shown in Table 1, PiCO significantly outperforms all the rivals by a significant margin on all datasets. Specifically, on CIFAR-10 dataset, we improve upon the best baseline by 4.09%, 4.80%, and 5.80% where q is set to 0.1, 0.3, 0.5 respectively. Moreover, PiCO consistently achieves superior results as the size of the candidate set increases, while the baselines demonstrate a significant performance drop. Besides, it is worth noting that previous works (Lv
et al., 2020; Wen et al., 2021) are typically evaluated on datasets with a small label space (C = 10). We challenge this by showing additional results on CIFAR-100. When q = 0.1, all the baselines fail to obtain satisfactory performance, whereas PiCO remains competitive. Finally, we observe that PiCO achieves results that are comparable to the fully supervised contrastive learning model, showing that disambiguation is sufficiently accomplished. The comparison highlights the superiority of our label disambiguation strategy.
PiCO learns more distinguishable representations. We visualize the image representation produced by the feature encoder using t-SNE (Van der Maaten & Hinton, 2008) in Figure 3. Different colors represent different ground-truth class labels. We use the CIFAR-10 dataset with q = 0.5. We contrast the t-SNE embeddings of three approaches: (a) a model trained with uniform pseudo targets, i.e., sj = 1/|Y | (j ∈ Y ), (b) the best baseline PRODEN, and (c) our method PiCO. We can observe that the representation of the uniform model is indistinguishable since its supervision signals suffer from high uncertainty. The features of PRODEN are improved, yet with some class overlapping (e.g., blue and purple). In contrast, PiCO produces well-separated clusters and more distinguishable representations, which validates its effectiveness in learning high-quality representation.

heading: 4.3 ABLATION STUDIES
text: In this section, we present part of our ablation results to show the effectiveness of PiCO. We refer readers to Appendix B.2 for more ablation experiments.
Effect of Lcont and label disambiguation. We ablate the contributions of two key components of PiCO: the contrastive learning and prototype-based label disambiguation. In particular, we compare PiCO with two variants: 1) PiCO w/o disambiguation which keeps the pseudo target as uniform 1/|Y |; and 2) PiCO w/o Lcont, which further removes the contrastive learning and only trains a classifier with uniform pseudo targets. From Table 2, we can observe that variant 1 substantially outperforms variant 2 (e.g., +8.04% on CIFAR-10), which signifies the importance of contrastive learning for producing better representations. Moreover, with label disambiguation, PiCO obtains results close to fully supervised setting, which verifies the ability of PiCO in identifying the ground-truth.
Different disambiguation strategy. Based on the contrastive prototypes, various strategies can be used to disambiguate the labels, which corresponds to the E-step in our theoretical analysis. We choose the following variants: 1) One-hot Prototype always assigns a one-hot pseudo target s = z by using the nearest prototype (φ = 0); 2) Soft Prototype Probs follows (Li et al., 2021a) and uses a soft class probability si =
exp(q>µi/τ)∑ j∈Y exp(q >µj/τ) as the pseudo target (φ = 0); 3) MA Soft Prototype
Probs gradually updates pseudo target from uniform by using the soft probabilities in a movingaverage style. From Table 2, we can see that directly using either soft or hard prototype-based label assignment leads to competitive results. This corroborates our theoretical analysis in Section 5, since center-based class probability estimation is common in clustering algorithms. However, MA Soft Prototype Probs displays degenerated performance, suggesting soft label assignment is less reliable in identifying the ground-truth. Finally, PiCO outperforms the best variant by 2% in accuracy on both datasets, showing the superiority of our label disambiguation strategy.
Effect of moving-average factor φ. We then explore the effect of pseudo target updating factor φ on PiCO performance. Figure 4 shows the learning curves of PiCO on CIFAR-100 (q = 0.05). We can see that the best result is achieved at φ = 0.9 and the performance drops when φ takes a smaller value, particularly on the early stage. When φ = 0, PiCO obtains a competitive result, but is much lower than φ = 0.9. This confirms that trusting the uniform pseudo target at the early stage is crucial in obtaining superior performance. At the other extreme value φ = 1, uniform pseudo target is used, and PiCO demonstrates a degenerated performance and severe overfitting phenomena. In general, PiCO performs well when φ ≈ 0.9.

heading: 4.4 FURTHER EXTENSION: FINE-GRAINED PARTIAL LABEL LEARNING
text: Recall the dog example highlighted in Section 2, where semantically similar classes are more likely to cause label ambiguity. It begs the question of whether PiCO is effective on the challenging finegrained image classification tasks. To verify this, we conduct experiments on two datasets: 1) CUB200 dataset (Welinder et al., 2010) contains 200 bird species; 2) CIFAR-100 with hierarchical labels (CIFAR-100-H), where we generate candidate labels that belong to the same superclass1. We set q = 0.05 for CUB-200 and q = 0.5 for CIFAR-100 with hi-
erarchical labels. In Table 3, we compare PiCO with baselines, where PiCO outperforms the best method PRODEN by a large margin (+9.61% on CUB-200 and +11.15% on CIFAR-100-H). Our results validate the effectiveness of our framework, even in the presence of strong label ambiguity.

heading: 5 WHY PICO IMPROVES PARTIAL LABEL LEARNING?
text: In this section, we provide theoretical justification on why the contrastive prototypes help disambiguate the ground-truth label. We show that the alignment property in contrastive learning (Wang & Isola, 2020) intrinsically minimizes the intraclass covariance in the embedding space, which coincides with the objective of classical clustering algorithms. It motivates us to interpret PiCO through the line of the expectation-maximization algorithm. To see this, we consider an ideal setting: in each training step, all data examples are accessible and the augmentation copies are also included in the training set, i.e., A = D. Then, the contrastive loss is calculated as,
L̃cont(g; τ,D) = 1
n ∑ x∈D − 1|P (x)| ∑ k+∈P (x) log exp(q>k+/τ)∑ k′∈A(x) exp(q >k′/τ)  = 1
n ∑ x∈D − 1|P (x)| ∑ k+∈P (x) (q>k+/τ) ︸ ︷︷ ︸ (a) + 1 n ∑ x∈D log ∑ k′∈A(x) exp(q>k′/τ) ︸ ︷︷ ︸ (b) . (8)
We focus on analyzing the first term (a), which is often dubbed as the alignment term (Wang & Isola, 2020). The main functionality of this term is to optimize the tightness of the clusters in the embedding space. In this work, we connect it with classical clustering algorithms. We first split the dataset to C subsets Sj ∈ DC (1 ≤ j ≤ C), where each subset contains examples possessing
1CIFAR-100 dataset consists of 20 superclasses, with 5 classes in each superclass.
the same predicted labels. In effect, our selection strategy in Eq. (4) constructs the positive set by selecting examples from the same subset. Therefore, we have,
(a) = 1
n ∑ x∈D 1 |P (x)| ∑ k+∈P (x) (||q − k+||2 − 2)/(2τ)
≈ 1 2τn ∑ Sj∈DC 1 |Sj | ∑ x,x′∈Sj ||g(x)− g(x′)||2 +K
= 1
τn ∑ Sj∈DC ∑ x∈Sj ||g(x)− µj ||2 +K,
(9)
whereK is a constant andµj is the mean center of Sj . Here we approximate 1|Sj | ≈ 1 |Sj |−1 = 1
|P (x)| since n is usually large. We omitted the augmentation operation for simplicity. The uniformity term (b) can benefit information-preserving, and has been analyzed in (Wang & Isola, 2020).
We are now ready to interpret the PiCO algorithm as an expectation-maximization algorithm that maximizes the likelihood of a generative model. At the E-step, the classifier assigns each data example to one specific cluster. At the M-step, the contrastive loss concentrates the embeddings to their cluster mean direction, which is achieved by minimizing Eq. (9). Finally, the training data will be mapped to a mixture of von Mises-Fisher distributions on the unit hypersphere.
EM Perspective. Recall that the candidate label set is a noisy version of the ground-truth. To estimate the likelihood P (Yi,xi), we need to establish the relationship between the candidate and the ground-truth label. Following (Liu & Dietterich, 2012), we make a mild assumption, Assumption 1. All labels in the candidate label set yi have the same probability of generating Yi, but no label outside of Yi can generate Yi, i.e. P (Yi|yi) = ~(Yi) if yi ∈ Yi else 0. Here ~(·) is some function making it a valid probability distribution.
Then, we show that the PiCO implicitly imizes the likelihood as follows,
E-Step. First, we introduce some distribution over all examples and the candidates πji (1 ≤ i ≤ n, 1 ≤ j ≤ C) such that πji = 0 if j /∈ Yi and ∑ j∈Yi π j i = 1. Let θ be the parameters of g. Our goal is to maximize the likelihood below,
argmax θ ∑n i=1 logP (Yi,xi|θ) =argmax θ ∑n i=1 log ∑ yi∈Yi P (xi, yi|θ)+ ∑n i=1 log(~(Yi))
=argmax θ ∑n i=1 log ∑ yi∈Yi πyii P (xi, yi|θ) πyii
≥argmax θ ∑n i=1 ∑ yi∈Yi πyii log P (xi, yi|θ) πyii .
(10)
The last step of the derivation uses Jensen’s inequality. By using the fact that log(·) function is concave, the inequality holds with equality when P (xi,yi|θ)
π yi i
is some constant. Therefore,
πyii = P (xi, yi|θ)∑
yi∈Yi P (xi, yi|θ) = P (xi, yi|θ)∑C yi=1 P (xi, yi|θ) = P (xi, yi|θ) P (xi|θ) = P (yi|xi, θ), (11)
which is the posterior class probability. In PiCO, it is estimated by using the classifier’s output.
To estimate P (yi|xi, θ), classical unsupervised clustering methods intuitively assign the data examples to the cluster centers, e.g. k-means. As in the supervised learning setting, we can directly use the ground-truth. However, under the setting of PLL, the supervision signals are situated between the supervised and unsupervised setups. Basing on empirical findings, the candidate labels are more reliable for posterior estimation at the beginning; yet alongside the training process, the prototypes tend to become more trustful. This empirical observation has motivated us to update the pseudo targets in a moving-average style. Thereby, we have a good initialization in estimating class posterior, and it will be smoothly refined during the training procedure. This is verified in our empirical studies; see Section 4.3 and Appendix B.2. Finally, we take one-hot prediction ỹi = arg maxj∈Y f j(xi) since each example inherently belongs to exactly one label and hence, we have πji = I(ỹi = j).
M-Step. At this step, we aim at maximizing the likelihood under the assumption that the posterior class probability is known. We show that under mild assumptions, minimizing Eq. (9) also maximizes a lower bound of likelihood in Eq. (10).
Theorem 1. Assume data from the same class in the contrastive output space follow a dvariate von Mises-Fisher (vMF) distribution whose probabilistic density is given by f(x|µ̄i, κ) = cd(κ)e
κµ̄>i g(x), where µ̄i = µi/||µi|| is the mean direction, κ is the concentration parameter, and cd(κ) is the normalization factor. We further assume a uniform class prior P (yi = j) = 1/C. Let nj = |Sj |. Then, optimizing Eq. (9) and Eq. (10) equal to maximize R1 and R2 below, respectively.
R1 = ∑
Sj∈DC nj n ||µj ||2 ≤ ∑ Sj∈DC nj n ||µj || = R2. (12)
The proof can be found in Appendix A. Theorem 1 indicates that minimizing Eq. (9) also maximizes a lower bound of the likelihood in Eq. (10). The lower bound is tight when ||µj || is close to 1, which in effect means a strong intraclass concentration on the hypersphere. Intuitively, when the hypothesis space is rich enough, it is possible to achieve a low intraclass covariance in the Euclidean space, resulting in a large norm of the mean vector ||µj ||. Then, normalized embeddings in the hypersphere also have an intraclass concentration in a strong sense, because a large ||µj || also results in a large κ (Banerjee et al., 2005). Regarding the visualized representation in Figure 3, we note that PiCO is indeed able to learn compact clusters. Therefore, we have that minimizing the contrastive loss also partially maximizes the likelihood defined in Eq. (10).

heading: 6 RELATED WORKS
text: Partial Label Learning (PLL) allows each training example to be annotated with a candidate label set, in which the ground-truth is guaranteed to be included. The most intuitive solution is average-based methods (Hüllermeier & Beringer, 2006; Cour et al., 2011; Zhang & Yu, 2015), which treat all candidates equally. However, the key and obvious drawback is that the predictions can be severely misled by the false positive labels. To disambiguate the ground-truth from the candidates, identification-based methods (Jin & Ghahramani, 2002), which regard the ground-truth as a latent variable, have recently attracted increasing attention; representative approaches include maximum margin-based methods (Nguyen & Caruana, 2008; Wang et al., 2020), graph-based methods (Zhang et al., 2016; Wang et al., 2019; Xu et al., 2019; Lyu et al., 2021), and clustering-based approaches (Liu & Dietterich, 2012). Recently, self-training methods (Feng et al., 2020b; Lv et al., 2020; Wen et al., 2021) have achieved state-of-the-art results on various benchmark datasets, which disambiguate the candidate label sets by means of the model outputs themselves. But, few efforts have been made to learn high-quality representations to reciprocate label disambiguation.
Contrastive Learning (CL) (van den Oord et al., 2018; He et al., 2020) is a framework that learns discriminative representations through the use of instance similarity/dissimilarity. A plethora of works have explored the effectiveness of CL in unsupervised representation learning (van den Oord et al., 2018; Chen et al., 2020; He et al., 2020). Recently, Khosla et al. (2020) propose supervised contrastive learning (SCL), an approach that aggregates data from the same class as the positive set and obtains improved performance on various supervised learning tasks. The success of SCL has motivated a series of works to apply CL to a number of weakly supervised learning tasks, including noisy label learning (Li et al., 2021a; Wu et al., 2021), semi-supervised learning (Li et al., 2020; Zhang et al., 2021), etc. Despite promising empirical results, however, these works, lack theoretical understandings. Wang & Isola (2020) theoretically show that the CL favors alignment and uniformity, and thoroughly analyzed the properties of uniformity. But, to date, the terminology alignment remains confusing; we show it inherently maps data points to a mixture of vMF distributions.

heading: 7 CONCLUSION
text: In this work, we propose a novel partial label learning framework PiCO. The key idea is to identify the ground-truth from the candidate set by using contrastively learned embedding prototypes. Empirically, we conducted extensive experiments and show that PiCO establishes state-of-the-art performance. Our results are competitive with the fully supervised setting, where the ground-truth label is given explicitly. Theoretical analysis shows that PiCO can be interpreted from an EM-algorithm perspective. Applications of multi-class classification with ambiguous labeling can benefit from our method, and we anticipate further research in PLL to extend this framework to tasks beyond image classification. We hope our work will draw more attention from the community toward a broader view of using contrastive prototypes for partial label learning.

heading: A THEORETICAL ANALYSIS
text: Derivation of Eq. (9). We provide the derivation of the second equality in Eq. (9). It suffices to show that LHS = 12nj ∑ x,x′∈Sj ||g(x)− g(x ′)||2 = ∑ x∈Sj ||g(x)− µj || 2 = RHS. We have,
LHS = 1
2nj ∑ x∈Sj ∑ x′∈Sj (||g(x)||2 − 2g(x)>g(x′) + ||g(x′)||2)
= 1
nj ∑ x∈Sj (nj − g(x)>( ∑ x′∈Sj g(x′)))
= 1
nj ∑ x∈Sj (nj − g(x)>(njµj)))
= nj − ( ∑ x∈Sj g(x))>µj) = nj(1− ||µj ||2).
(13)
On the other hand,
RHS = ∑ x∈Sj (||g(x)||2 − 2g(x)>µj + ||µj ||2)
= (nj − 2( ∑ x∈Sj g(x))>µj + nj ||µj ||2)
= nj(1− ||µj ||2) = LHS.
(14)
Proof of Theorem 1. By regarding πji as constants w.r.t θ, we can get the following derivation from Eq. (10),
arg max θ n∑ i=1 ∑ yi∈Yi πyii log P (xi, yi|θ) πyii = arg max θ n∑ i=1 ∑ yi∈Yi πyii logP (xi|yi, θ)P (yi)
= arg max θ n∑ i=1 ∑ yi∈Yi I(ỹi = yi) logP (xi|yi, θ)
= arg max θ ∑ Sj∈DC ∑ x∈Sj logP (x|y = j, θ)
= arg max θ ∑ Sj∈DC ∑ x∈Sj (κµ̄>j g(x) + log(cd(κ)))
= arg max θ ∑ Sj∈DC nj n ||µj ||
(15)
where nj = |Sj |. Here we ignore the constant factor − ∑n i=1 ∑ yi∈Yi π yi i log π yi i w.r.t. θ in the first
equality. In the last equality, we use the fact that µj = 1nj ∑ x∈Sj g(x) and µ̄j is the unit directional vector of µj . From Eq. (9), we have that,
arg min θ ∑ Sj∈DC ∑ x∈Sj ||g(x)− µj ||2 = arg min θ ∑ Sj∈DC ∑ x∈Sj (||g(x)||2 − 2g(x)>µj + ||µj ||2)
= arg min θ ∑ Sj∈DC (nj − nj ||µj ||2)
= arg max θ ∑ Sj∈DC nj n ||µj ||2.
(16)
Note that the contrastive embeddings are distributed on the hypersphere Sd−1 and thus ||µj || ∈ [0, 1]. It can be directly derived that,
R1 = ∑
Sj∈DC
nj n ||µj ||2 ≤ ∑ Sj∈DC nj n ||µj || = R2. (17)
Therefore, maximizing the intraclass covariance in Eq. (9) is equivalent to maximize a lower bound of the likelihood in Eq. (10). It can also be shown that (R2)2 ≤ R1 followed by the convexity of squared function. Since arg maxR2 = arg max(R2)2, we have that the contrastive loss also maximizes an upper bound of R2.
Unfortunately, there is no guarantee that the lower bound is tight without further assumptions. To see this, assume that we have two classes y ∈ {1, 2} with equal-sized samples and their mean vectors have the norm of ||µ1|| = 0.5 and ||µ1|| = 1. We have that R1 = 0.625 and R2 = 0.75, which demonstrates a large discrepancy. It is interesting to see that when the norm of the mean vectors are the same, i.e. ||µj || = ||µk|| for all 1 ≤ j ≤ k ≤ C, we have (R2)2 = R1 by the Jensen’s inequality, making the upper bound tight. But, it is not a trivial condition.
To obtain a tight lower bound, what we need is a rich enough hypothesis space to achieve a low intraclass covariance in Eq. (9), and hence a large R1. We show that it inherently produces compact vMF distributions. To see this, it should be noted that the concentration parameter κ of a vMF distribution is given by the inverse of the ratio of Bessel functions of mean vector µj . Though it is not possible to obtain an analytic solution of κ, we have the following well-known approximation (Banerjee et al., 2005),
κ ≈ d− 1 2(1− ||µj ||) , valid for large ||µj ||, (18)
κ ≈ d||µj || ( 1 + d
d+ 2 ||µj ||2 +
d2(d+ 8)
(d+ 2)2(d+ 4) ||µj ||4
) , valid for small ||µj ||. (19)
The above approximations show that a larger norm of Euclidean’s mean µj typically leads to a stronger concentration on the hypersphere. By Eq. (16), we know that contrastive loss encourages a large norm of µj , and thus also tightly clusters the embeddings on the hypersphere; see Figure 5.
We further note that we do not include a k-means process in our PiCO method. PiCO is related to center-based clustering algorithms in our theoretical analysis. Since we restrict the gold label to be included in the candidate set, we believe that this piece of information could largely help avoid the bad optimum problem that occurs in a pure unsupervised setup. For the convergence properties of our PiCO algorithm, we did not empirically find any issues with PiCO converging to a (perhaps locally) optimal point. However, we want to refer the readers to the proof of k-means clustering in (Bottou & Bengio, 1994) for the convergence analysis.
Discussion. Regarding our empirical results where PiCO does indeed learn compact representations for each class, we can conclude that PiCO implicitly clusters data points in the contrastive embeddings space as a mixture of vMF distributions. In each iteration, our algorithm can be viewed as alternating the two steps until convergence, though different in detail. First, it is intractable to handle the whole training dataset, and thus we accelerate via a MoCo-style dictionary and MAupdated prototypes. Second, the contrastive loss also encourages the uniformity of the embeddings to maximally preserve information, which serves as an regularizer and typically leads to better representation. Finally, we use two copies of data examples such that data are also aligned in its local region. Moreover, our theoretical result also answers why merely taking the pseudo-labels to select
positive examples also leads to superior results, since the selected positive set will be refined as the training procedure proceeds.
Our theoretical results are also generalizable to other contrastive learning methods. For example, the classical unsupervised contrastive learning (He et al., 2020) actually assumes n-prototypes to cluster all locally augmented data; prototypical contrastive learning (Li et al., 2021b) directly assigns the data examples to one cluster to get the posterior, since there are no supervision signals; supervised contrastive learning (Khosla et al., 2020) chooses the known ground-truth as the posterior. In our problem, we follow two extreme settings to progressively obtain an accurate posterior estimation. Finally, it is also noteworthy that the objective in Eq. (9) has a close connection to the intraclass deviation (Saunshi et al., 2019), minimizing which is proven to be beneficial in obtaining tighter generalization error bound on downstream tasks. It should further be noted that our work differs from existing clustering-based CL methods (Caron et al., 2020; Li et al., 2021b), which explicitly involves clustering to aggregate the embeddings; instead, our results are derived from the loss itself.

heading: B ADDITIONAL EXPERIMENTAL SETUPS AND RESULTS
text: B.1 IMPLEMENTATION DETAILS
Following the standard experimental setup in PLL (Feng et al., 2020b; Wen et al., 2021), we split a clean validation set (10% of training data) from the training set to select the hyperparameters. After that, we transform the validation set back to its original PLL form and incorporate it into the training set to accomplish the final model training. We use an 18-layer ResNet as the backbone for feature extraction. Most of experimental setups for the contrastive network follow previous works (He et al., 2020; Khosla et al., 2020). The projection head of the contrastive network is a 2-layer MLP that outputs 128-dimensional embeddings. We use two data augmentation modules SimAugment (Khosla et al., 2020) and RandAugment (Cubuk et al., 2019) for query and key data augmentation respectively. The size of the queue that stores key embeddings is fixed to be 8192. The momentum coefficients are set as 0.999 for contrastive network updating and γ = 0.99 for prototype calculation. For pseudo target updating, we linearly ramp down φ from 0.95 to 0.8. The temperature parameter is set as τ = 0.07. The loss weighting factor is set as λ = 0.5. The model is trained by a standard SGD optimizer with a momentum of 0.9 and the batch size is 256. We train the model for 800 epochs with cosine learning rate scheduling. We also empirically find that classifier warm-up leads to better performance when there are many candidates. Hence, we disable contrastive learning in the first 100 epoch for CIFAR-100 with q = 0.1 and 1 epoch for the remaining experiments.
B.2 ABLATION STUDIES
Moving-average updating factor φ. We first present more ablation results about the effect of pseudo target updating factor φ on PiCO performance. Figure 6 (a) shows the results on two datasets
CIFAR-10 (q = 0.5) and CIFAR-100 (q = 0.05). The overall trends on both datasets follow our arguments in section 4.3. Specifically, performance on CIFAR-100 achieves the best result when φ = 0.7, and slight drops when φ = 0.9. Therefore, in practice, we may achieve a better result with careful fine-tuning on φ value. In contrast, PiCO works well in a wide range of φ values on CIFAR-10. The reason might be that CIFAR-10 is a simpler version of CIFAR-100, and thus the prototypes can be high-quality quickly. But, setting φ to either 0 or 1 leads to a worse result, which has been discussed earlier.
Loss weight λ. Figure 6 (b) reports the performance of PiCO with varying λ values that trade-off the classification and contrastive losses. λ is selected from {0.01, 0.1, 0.5, 5, 50}. We can observe that on CIFAR-10, the performance is stable, but on CIFAR-100, the best performance is obtained at λ = 5. When λ = 50, PiCO shows inferior results on both two datasets. In general, a relatively small λ (< 10) usually leads to good performance than a much larger value. When λ is large, the contrastive network tends to fit noisy labels at the early stage of training.
Prototype updating factor γ. Finally, we show the effect of γ that controls the speed of prototype updating and the results are listed in Table 4. On CIFAR-10 dataset, the performance is stable with varying γ. But, on CIFAR-100, it can be seen that too large λ leads to a significant performance drop, which may be caused by insufficient label disambiguation.
The disambiguation ability of PiCO. Finally, we evaluate the disambiguation ability of the proposed PiCO. To see this, we calculate the max confidence to represent the uncertainty of an example, which has been widely used in recent works (Hendrycks & Gimpel, 2017). If one example is uncertain about its ground-truth, then it typically associates with low max confidence maxj sj . To represent the uncertainty of the whole training dataset, we calculate the mean max confidence (MMC) score. In Figure 7, we plot the MMC scores of different label disambiguation strategies in different training epochs. First, we can observe the MMC score of PiCO smoothly increases and
finally achieves near 1 results, which means most of the labels are well disambiguated. In contrast, the Soft Prototype Probs strategy oscillates at the beginning, and then also increases to a certain value, which means that directly adopting the soft class probability also helps disambiguation. But, it is worth noting that it ends with a smaller MMC score compared with PiCO. The reason might be that the cosine distances to non-ground-truth prototypes are still at a scale. Hence, the Soft Prototype Probs strategy always holds a certain degree of ambiguity. Finally, we can see that the MA Soft Prototype Probs strategy fails to achieve great disambiguation ability. Compared with the non-moving-average version, it fails to get rid of severe label ambiguity and will finally converge to uniform pseudo targets again.
Furthermore, we evaluated the accuracy of the pseudo targets over training examples. From Table 5, we can find that the pseudo targets achieve high training accuracy. Combining with the fact that the mean max confidence score of the pseudo target is close to 1, the training examples finally becomes near supervised ones. Thus, the proposed PiCO is able to achieve near-supervised learning performance, especially when the label ambiguity is not too high. These results verify that PiCO has a strong label disambiguation ability to handle the PLL problem.
B.3 ADDITIONAL RESULTS ON FINE-GRAINED CLASSIFICATION
In the sequel, we show the full setups and experimental results on fine-grained classification datasets. In particular, on CUB-200, we set the length of the momentum queue as 4192. For CUB-200, we select q ∈ {0.01, 0.05, 0.1}. When q = 0.05/0.1, we warm up for 20/100 epochs and train the model for 200/300 epochs, respectively. For CIFAR-100-H, we select q ∈ {0.1, 0.5, 0.8} and warm up the model for 100 epochs when q = 0.8. Other hyperparameters are the same as our default setting. The baselines are also fine-tuned to achieve their best results.
From Table 6, we can observe that PiCO significantly outperforms all the baselines mentioned in section 4 on all the datasets. Moreover, as the size of candidate sets grows larger, PiCO consistently leads by an even wider margin. For example, on CIFAR-100-H, compared with the best baseline, performance improvement reaches 9.50%, 11.15% and 22.53% in accuracy when q = 0.1, 0.5, 0.8, respectively. The comparison emerges the dominance of our label disambiguation strategy among semantically similar classes.
B.4 STRATEGIES FOR POSITIVE SELECTION
While our positive set selection strategy is simple and effective, one may still explore more complicated strategies to boost performance. We have empirically tested two strategies: 1) Filter-based: we set a filter |Yi∩Yj ||Yi∪Yj | ≤ ρ (ρ = 0.5) to remove example pairs who have dissimilar candidate sets at the early stage. 2) Threshold-based: we set a threshold max f j(Augq(x)) ≤ δ (δ = 0.95) to remove those uncertain examples at the end of training, which has been widely used in semi-supervised learning (Sohn et al., 2020). Our basic principle is that contrastive learning is robust to noisy nega-
tive pairs and thus, we can flip those less reliable positive pairs to negative. Unfortunately, we did not observe statistically significant improvement to our vanilla strategy in experiments. These negative results suggest that the proposed PiCO has a strong error correction ability, which corroborates our theoretical analysis.
B.5 THE INFLUENCE OF DATA GENERATION
In practice, some labels may be more analogous to the true label than others, which makes their probability of label flipping q larger than others. In other words, the data generation procedure is nonuniform. In Section 4.4, we have shown one such case on CIFAR-100-H, where semantically similar labels have a larger probability of being false positive. In the sequel, we follow (Wen et al., 2021) to conduct empirical comparisons on data with alternative generation processes. In particular, we test two
commonly used cases on CIFAR-10 with the following flipping matrix, respectively:
(1) =  1 0.5 0 · · · 0 0 1 0.5 · · · 0 ... · · ·
... 0.5 0 0 · · · 1
 , (2) =  1 0.9 0.7 0.5 0.3 0.1 0 · · · 0 0 1 0.9 0.7 0.5 0.3 0.1 · · · 0 ... · · ·
... 0.9 0.7 0.5 0.3 0.1 0 0 · · · 1  where each entry denotes the probability of a label being a candidate. As shown in Table 7, PiCO outperforms other baselines in both cases. It is worth noting that in Case (2), each ground-truth label has a maximum probability of 0.9 of being coupled with the same false positive label. In such a challenging setup, PiCO still achieves promising results that are competitive with the supervised performance, which further verifies its strong disambiguation ability.
B.6 INFLUENCE OF PROTOTYPE CALCULATION
There are several ways to calculate the prototypes and hence, we further test a variant of PiCO that re-computes the prototypes by averaging embeddings of all training examples at the end of each epoch. We train the models using one Quadro P5000 GPU respectively and evaluate the average training time per epoch. From Table 8, we can observe that the Re-Compute variant achieves competitive results, but is much slower than PiCO.

heading: C PSEUDO-CODE OF PICO
text: We summarize the pseudo-code of our PiCO method in Algorithm 1.

heading: D THE LITERATURE OF PROTOTYPE LEARNING
text: Prototype learning (PL) aims to learn a metric space where examples are enforced to be closer to its class prototypes. PL is typically more robust in handling few-shot learning (Snell et al., 2017), zeroshot learning (Xu et al., 2020), and out-of-distribution samples (Arik & Pfister, 2019). Recently, PL has demonstrated promising results in weakly-supervised learning, such as semi-supervised learning (Han et al., 2020), noisy-label learning (Li et al., 2021a), etc. For example, USADTM (Han et al., 2020) shows that informative class prototypes usually lead to better pseudo-labels for semisupervised learning than classical pseudo-labeling algorithms (Sohn et al., 2020) which reuse classifier outputs. Motivated by this, we also employ contrastive prototypes for label disambiguation.
Algorithm 1: Pseudo-code of PiCO (one epoch). 1 Input: Training dataset D, classifier f , query network g, key network g′, momentum queue, uniform
pseudo-labels si associated with xi in D, class prototypes µj (1 ≤ j ≤ C). 2 for iter = 1, 2, . . . , do 3 sample a mini-batch B from D // query and key embegginds generation 4 Bq = {qi = g(Augq(xi))|xi ∈ B} 5 Bk = {ki = g′(Augk(xi))|xi ∈ B} 6 A = Bq ∪Bk ∪ queue 7 for xi ∈ B do
// classifier prediction
8 ỹi = argmaxj∈Yi f j(Augq(xi)) // momentum prototype updating 9 µc = Normalize(γµc + (1− γ)qi), if ỹi = c
// positive set generation 10 P (xi) = {k′|k′ ∈ A(xi), ỹ′ = ỹi} 11 end // prototype-based label disambiguation 12 for qi ∈ Bq do 13 zi = OneHot(argmaxj∈Yi q > i µj) 14 si = φsi + (1− φ)zi 15 end
// contrastive loss calcuation 16 Lcont(g; τ, A) = 1|Bq| ∑ qi∈Bq { − 1|P (xi)| ∑ k+∈P (xi) log exp(q>i k+/τ)∑ k′∈A(xi) exp(q>i k ′/τ) } // classification loss calculation
17 Lcls(f ;B) = 1|B| ∑ xi∈B ∑C j=1−si,j log(f
j(Augq(xi))) // network updating
18 minimize loss L = Lcls + λLcont // update the key network and momentum queue 19 momentum update g′ by using g 20 enqueue Bk and classifier predictions and dequeue 21 end

Review summaries:
The authors present a new technique for partial label learning (PLL). PLL is the task where the labels for each instance include both the ground truth label and a randomly sampled set of distractor labels, and during training the model learns a latent decision for which among this set is the ground truth. The technique presented by the authors uses a combination of momentum (in the representation) and contrastive learning (to augment the label set) that leads to improved PLL results, reaching nearly fully supervised performance.

The paper proposes an innovative approach to partial label learning, where an instance is assigned with some false positive labels besides its true label (due to difficulty in labelling). The approach blends contrastive learning with prototype learning: (i) the former helps to form good clusters for the latter to learn prototype representations (ii) in return the latter helps to select positive samples for the former. Theoretically, the authors prove that the two of them work collaboratively in the EM fashion.   The paper demonstrates the effectiveness of the proposed approach using a typical setting for the task. Specifically, CIFAR 10 and CIFAR 100 were used and each instance was randomly assigned false labels with some probabilities. The proposed approach achieved impressive results, substantially outperforming five recent models in the literature. Moreover, its performance strongly approaches the one of supervised learning.   The paper also presents a much stricter setting when false positive labels are semantically correlated with true labels. The proposed approach also gained impressive results on CUB-200 and CIFAR-100-H datasets. Moreover, the paper shows several in-depth analyses.  

This work approaches the partial label learning problem where each training example is annotated with multiple candidate labels, in contrast to the conventional supervised learning setup that the ground-truth label is provided. The proposed framework comprises two key components: (1) a contrastive learning module that uses the classifier output to select positive pairs and (2) a label disambiguation method that uses the contrastive prototypes to update the pseudo targets in a moving-average style. The experimental results look quite strong, where the performance of PiCO nearly approaches the fully-supervised results.