# PICO: CONTRASTIVE LABEL DISAMBIGUATION FOR PARTIAL LABEL LEARNING

**Haobo Wang[1]** **Ruixuan Xiao[1]** **Yixuan Li[2]** **Lei Feng[34]**

**Gang Niu[4]** **Gang Chen[1]** **Junbo Zhao[1][∗]**

1Zhejiang University 2University of Wisconsin-Madison
3Chongqing University 4RIKEN


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. Code and data
[available: https://github.com/hbzju/PiCO.](https://github.com/hbzju/PiCO)

1 INTRODUCTION

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) (H¨ullermeier & 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 dependent 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

_∗Correspondence to j.zhao@zju.edu.cn._


-----

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, that
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)}i[n]=1[, where each tuple comprises of an image][ x][i][ ∈X]_
and a candidate label set Yi . Identical to the supervised
learning setup, the goal of PLL is to obtain a functional mapping ⊂Y
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 labelinvisible to the learner. For this reason, the learning process can yi is concealed in its candidate set, i.e., yi ∈ _Yi, and is_
suffer from inherent ambiguity, compared with the supervised
learning task with explicit ground-truth.


Figure 1: An input image with three
candidate labels, where the groundtruth is Malamute.


The key challenge of PLL is to identify the ground-truth label from the candidate label set. During
training, we assign each imageentries denote the probability of labels being the ground-truth. The total probability mass of 1 is xi a normalized vector si ∈ [0, 1][C] as the pseudo target, whose
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:


_C_
cls(f ; xi, Yi) = s.t.
_L_ _j=1_ _[−][s][i,j][ log(][f][ j][(][x][i][))]_
X


_Yi,_ (1)
_j_ _Yi_ _[s][i,j][ = 1][ and][ s][i,j][ = 0][,][ ∀][j /]∈_
_∈_


-----

Figure 2: Illustration of PiCO. The classifier’s output is used to determine the positive peers for contrastive
learning. The contrastive prototypes are then used to gradually update the pseudo target. The momentum
embeddings are maintained by a queue structure. ’//’ means stop gradient.

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.

3 METHOD

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.

3.1 CONTRASTIVE REPRESENTATION LEARNING FOR PLL

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 a 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,


exp(q[⊤]k+/τ ) (3)
**_k+_** _P (x)_ [log]
_∈_ **_k[′]_** _A(x)_ [exp(][q][⊤][k][′][/τ] [)] _[,]_

_∈_

P


_Lcont(g; x, τ, A) = −_


_|P_ (x)|


-----

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 classi-_
fier. 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.

3.2 PROTOTYPE-BASED LABEL DISAMBIGUATION

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 =_ _|Y1 |_ [I][(][j][ ∈] _[Y][ )][. We then iteratively update it by the following moving-average mechanism,]_

1 if c = arg maxj _Y q[⊤]µj,_
**_s = φs + (1_** _φ)z,_ _zc =_ _∈_ (6)
_−_ 0 else


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.


-----

Table 1: Accuracy comparisons on benchmark datasets. Bold indicates superior results. Notably, PiCO

|comparable resu|ults to the fully superv|vised learning (less than 1% in accuracy with ≈1 false ca|
|---|---|---|
|Dataset|Method|q = 0.1 q = 0.3 q = 0.5|
|CIFAR-10|PiCO (ours) LWS PRODEN CC MSE EXP Fully Supervised|94.39 ± 0.18% 94.18 ± 0.12% 93.58 ± 0.06% 90.30 ± 0.60% 88.99 ± 1.43% 86.16 ± 0.85% 90.24 ± 0.32% 89.38 ± 0.31% 87.78 ± 0.07% 82.30 ± 0.21% 79.08 ± 0.07% 74.05 ± 0.35% 79.97 ± 0.45% 75.64 ± 0.28% 67.09 ± 0.66% 79.23 ± 0.10% 75.79 ± 0.21% 70.34 ± 1.32% 94.91 ± 0.07%|
|Dataset|Method|q = 0.01 q = 0.05 q = 0.1|
|CIFAR-100|PiCO (ours) LWS PRODEN CC MSE EXP Fully Supervised|73.09 ± 0.34% 72.74 ± 0.30% 69.91 ± 0.24% 65.78 ± 0.02% 59.56 ± 0.33% 53.53 ± 0.08% 62.60 ± 0.02% 60.73 ± 0.03% 56.80 ± 0.29% 49.76 ± 0.45% 47.62 ± 0.08% 35.72 ± 0.47% 49.17 ± 0.05% 46.02 ± 1.82% 43.81 ± 0.49% 44.45 ± 1.50% 41.05 ± 1.40% 29.27 ± 2.81% 73.56 ± 0.10%|



3.3 SYNERGY BETWEEN CONTRASTIVE LEARNING AND LABEL DISAMBIGUATION

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.

4 EXPERIMENTS

4.1 SETUP

**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 ̸= y to false positive labels with a probability q = P (¯y ∈ _Y |y¯ ̸= 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).

4.2 MAIN EMPIRICAL RESULTS

**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 pointing out that previous


-----

(a) Uniform features (b) PRODEN features (c) PiCO features (ours)

Figure 3: T-SNE visualization of the image representation on CIFAR-10 with q = 0.5. Different colors
represent the corresponding classes.

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 pro-**
duced 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.

4.3 ABLATION STUDIES

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: 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.


Figure 4: Performance of PiCO with
varying φ on CIFAR-100 (q = 0.05).


**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 moving-P_
average 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.


-----

|Table 2: Ablation study o|on CIFAR-10 with q = 0.5 and CIF|FAR-100 with q = 0.05.|
|---|---|---|
|Ablation|Lcont Label Disambiguation|CIFAR-10 CIFAR-100 (q = 0.5) (q = 0.05)|
|PiCO PiCO w/o Disambiguation PiCO w/o Lcont|✓ Ours ✓ Uniform Pseudo Target  Uniform Pseudo Target|93.58 72.74 84.50 64.11 76.46 56.87|
|PiCO with φ = 0 PiCO with φ = 0 PiCO|✓ Soft Prototype Probs ✓ One-hot Prototype ✓ MA Soft Prototype Probs|91.60 71.07 91.41 70.10 81.67 63.75|


**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 targets at the early stage is
crucial in obtaining superior performance. At the other extreme value φ = 1, uniform pseudo targets
are used, and PiCO demonstrates a degenerated performance and severe overfitting phenomena. In
general, PiCO performs well when φ ≈ 0.9.

4.4 FURTHER EXTENSION: FINE-GRAINED PARTIAL LABEL LEARNING

Recall the dog example highlighted in Section 2, Table 3: Accuracy comparisons on fine-grained
where semantically similar classes are more likely classification datasets.
to cause label ambiguity. It begs the question of CUB-200 CIFAR-100-H
whether PiCO is effective on the challenging fine- (q = 0.05) (q = 0.5)
grained image classification tasks. To verify this,we conduct experiments on two datasets: 1) CUB-200 dataset (Welinder et al., 2010) contains 200 PRODENPiCOLWS **72.1739.7462.56 ± ± ± 0.72% 0.47% 0.10%** **72.0457.2560.89 ± ± ± 0.31% 0.02% 0.03%**

|Method|CUB-200 (q = 0.05)|CIFAR-100-H (q = 0.5)|
|---|---|---|

bird species; 2) CIFAR-100 with hierarchical labels CC 55.61 ± 0.02% 42.60 ± 0.11%
(CIFAR-100-H), where we generate candidate labels MSE 22.07 ± 2.36% 39.52 ± 0.28%
that belong to the same superclass[1]. We set q = 0.05 EXP 9.44 ± 2.32% 35.08 ± 1.71%
for CUB-200 and q = 0.5 for CIFAR-100 with hi
|PiCO LWS PRODEN CC MSE EXP|72.17 ± 0.72% 39.74 ± 0.47% 62.56 ± 0.10% 55.61 ± 0.02% 22.07 ± 2.36% 9.44 ± 2.32%|72.04 ± 0.31% 57.25 ± 0.02% 60.89 ± 0.03% 42.60 ± 0.11% 39.52 ± 0.28% 35.08 ± 1.71%|
|---|---|---|

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.

5 WHY PICO IMPROVES PARTIAL LABEL LEARNING?

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 lens 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,


log exp(q[⊤]k+/τ )
**_k+X∈P (x)_** **_k[′]∈A(x)_** [exp(][q][⊤][k][′][/τ] [)]
P


˜cont(g; τ, ) = [1]
_L_ _D_ _n_

= [1]




[−]




[−]


_|P_ (x)|

1

_|P_ (x)|


**_x∈D_**

**_xX∈D_**


(8)


+ [1]


= [1] 1 (q[⊤]k+/τ ) + [1] exp(q[⊤]k[′]/τ ) _._

_n_  _P_ (x)  _n_  

**_xX∈D_**  _|_ _|_ **_k+X∈P (x)_**  **_xX∈D_**  **_k[′]∈XA(x)_** 

[−] (a)  [log] (b) 

| {z } | {z }

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_

1X
_≈_ 2τn


**_k+∈P (x)[(][||][q][ −]_** **_[k][+][||][2][ −]_** [2)][/][(2][τ] [)]


_|P_ (x)|


**_x∈D_**


1 1

(9)

_≈_ 2τn _Sj_ _∈DC_ _|Sj|_ **_x,x[′]∈Sj_** _[||][g][(][x][)][ −]_ _[g][(][x][′][)][||][2][ +][ K]_

X X

= [1]

_τn_ _Sj_ _∈DC_ **_x∈Sj_**

X X _[||][g][(][x][)][ −]_ **_[µ][j][||][2][ +][ K,]_** 1 1 1

where K is a constant and µj is the mean center of Sj. Here we approximate _Sj_ _Sj_ 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 yi in the candidate label set have the same probability of generating Yi,**
_function making it a valid probability distribution.but no label outside of Yi can generate Yi, i.e. P_ (Yi|yi) = ℏ(Yi) if yi ∈ _Yi else 0. Here ℏ(·) is some_

Then, we show that the PiCO implicitly maximizes the likelihood as follows,

**E-Step. First, we introduce some distributions over all examples and the candidates πi[j]**

_[≥]_ [0][ (][1][ ≤]
_i ≤_ _n, 1 ≤_ _j ≤_ _C) such that πi[j]_ [= 0][ if][ j /]∈ _Yi and_ _j∈Yi_ _[π]i[j]_ [= 1][. Let][ θ][ be the parameters of][ g][. Our]

goal is to maximize the likelihood below,

_n_ _n_ _n_

argmax [P]
_θ_ _i=1_ [log][ P] [(][Y][i][,][ x][i][|][θ][) =argmax]θ _i=1[log]_ _yi_ _Yi_ _[P]_ [(][x][i][, y][i][|][θ][)+] _i=1[log(][ℏ][(][Y][i][))]_

_∈_

X Xn X _P_ (xi, yiXθ)

=argmaxθ _i=1_ [log] _yi∈Yi_ _[π]i[y][i]_ _πi[y][i]_ _|_ (10)

Xn X

_≥_ argmaxθ _i=1_ _yi∈Yi_ _[π]i[y][i]_ [log][ P] [(][x]π[i][, y]i[y][i] _[i][|][θ][)]_ _._

X X

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][ (][x]π[i]iyi[,y][i][|][θ][)]_ is some constant. Therefore,

_P_ (xi, yi _θ)_ _P_ (xi, yi _θ)_
_πi[y][i]_ = _yi∈Yi_ _[P]_ [(][x]|[i][, y][i][|][θ][) =] _Cyi=1_ _[P]_ [(][x][i]|[, y][i][|][θ][)] = _[P]P[(][x](x[i][, y]i|θ[i][|])[θ][)]_ = P (yi|xi, θ), (11)

which is the posterior class probability. In PiCO, it is estimated by using the classifier’s output.P P

To estimate P (yi **_xi, θ), classical unsupervised clustering methods intuitively assign the data exam-_**
_|_
ples 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. Based 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 ˜yi = arg maxj _Y f_ _[j](xi)_
_∈_
since each example inherently belongs to exactly one label and hence, we have πi[j] [=][ I][(˜]yi = j).

**M-Step. At this step, we aim at maximizing the likelihood under the assumption that the poste-**
rior 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 d-**
_variate 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._

_nj_ _nj_

_R1 =_ (12)

_Sj_ _∈DC_ _n_ _Sj_ _∈DC_ _n_

_[||][µ][j][||][2][ ≤]_ _[||][µ][j][||][ =][ R][2][.]_

X X

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).

6 RELATED WORKS

**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 averagebased methods (H¨ullermeier & 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 false positive labels. To disambiguate the ground-truth from the candidates, identificationbased 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 has 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 unifor_mity, 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.

7 CONCLUSION

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.


-----

ACKNOWLEDGMENTS

HW, RX, GC and JZ are supported by the Key R&D Program of Zhejiang Province (Grant No.
2020C01024). JZ would also like to thank the Fundamental Research Funds for the Central Universities. YL is supported by Wisconsin Alumni Research Foundation (WARF), Facebook Research
Award, and funding from Google Research. FL is supported by the National Natural Science Foundation of China (Grant No. 62106028).

REFERENCES

Sercan Omer Arik and Tomas Pfister. Attention-based prototypical learning towards interpretable,[¨]
confident and robust deep neural networks. CoRR, abs/1902.06292, 2019.

Arindam Banerjee, Inderjit S. Dhillon, Joydeep Ghosh, and Suvrit Sra. Clustering on the unit hypersphere using von mises-fisher distributions. J. Mach. Learn. Res., 6:1345–1382, 2005.

L´eon Bottou and Yoshua Bengio. Convergence properties of the k-means algorithms. In Gerald
Tesauro, David S. Touretzky, and Todd K. Leen (eds.), NIPS, pp. 585–592. MIT Press, 1994.

Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.
Unsupervised learning of visual features by contrasting cluster assignments. In NeurIPS, 2020.

Ching-Hui Chen, Vishal M. Patel, and Rama Chellappa. Learning from ambiguously labeled face
images. IEEE Trans. Pattern Anal. Mach. Intell., 40(7):1653–1667, 2018.

Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for
contrastive learning of visual representations. In ICML, volume 119 of Proceedings of Machine
_Learning Research, pp. 1597–1607. PMLR, 2020._

Timoth´ee Cour, Benjamin Sapp, and Ben Taskar. Learning from partial labels. J. Mach. Learn. Res.,
12:1501–1536, 2011.

Ekin D. Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V. Le. Randaugment: Practical data
augmentation with no separate search. CoRR, abs/1909.13719, 2019.

Lei Feng, Takuo Kaneko, Bo Han, Gang Niu, Bo An, and Masashi Sugiyama. Learning with multiple
complementary labels. In ICML, volume 119 of Proceedings of Machine Learning Research, pp.
3072–3081. PMLR, 2020a.

Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. In NeurIPS, 2020b.

Tao Han, Junyu Gao, Yuan Yuan, and Qi Wang. Unsupervised semantic aggregation and deformable
template matching for semi-supervised learning. In NeurIPS 2020, 2020.

Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick. Momentum contrast for
unsupervised visual representation learning. In CVPR, pp. 9726–9735. IEEE, 2020.

Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution
examples in neural networks. In ICLR. OpenReview.net, 2017.

Eyke H¨ullermeier and J¨urgen Beringer. Learning from ambiguously labeled examples. Intell. Data
_Anal., 10(5):419–439, 2006._

Rong Jin and Zoubin Ghahramani. Learning with multiple labels. In NeurIPS, pp. 897–904. MIT
Press, 2002.

Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron
Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. In NeurIPS, 2020.

Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.
2009.


-----

Junnan Li, Caiming Xiong, and Steven C. H. Hoi. Comatch: Semi-supervised learning with contrastive graph regularization. CoRR, abs/2011.11183, 2020.

Junnan Li, Caiming Xiong, and Steven C. H. Hoi. Mopro: Webly supervised learning with momentum prototypes. In ICLR. OpenReview.net, 2021a.

Junnan Li, Pan Zhou, Caiming Xiong, and Steven C. H. Hoi. Prototypical contrastive learning of
unsupervised representations. In ICLR. OpenReview.net, 2021b.

Li-Ping Liu and Thomas G. Dietterich. A conditional multinomial mixture model for superset label
learning. In NeurIPS, pp. 557–565, 2012.

Jie Luo and Francesco Orabona. Learning from candidate labeling sets. In NeurIPS, pp. 1504–1512.
Curran Associates, Inc., 2010.

Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. In ICML, volume 119 of Proceedings of Machine
_Learning Research, pp. 6500–6510. PMLR, 2020._

Gengyu Lyu, Songhe Feng, Tao Wang, Congyan Lang, and Yidong Li. GM-PLL: graph matching
based partial label learning. IEEE Trans. Knowl. Data Eng., 33(2):521–535, 2021.

Nam Nguyen and Rich Caruana. Classification with partial labels. In SIGKDD, pp. 551–559. ACM,
2008.

Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar.
A theoretical analysis of contrastive unsupervised representation learning. In ICML, volume 97
of Proceedings of Machine Learning Research, pp. 5628–5637. PMLR, 2019.

Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning. In
_NeurIPS, pp. 4077–4087, 2017._

Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning
with consistency and confidence. In NeurIPS, 2020.

A¨aron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. CoRR, abs/1807.03748, 2018.

Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine
_learning research, 9(11), 2008._

Deng-Bao Wang, Li Li, and Min-Ling Zhang. Adaptive graph guided disambiguation for partial
label learning. In SIGKDD, pp. 83–91. ACM, 2019.

Haobo Wang, Yuzhou Qiang, Chen Chen, Weiwei Liu, Tianlei Hu, Zhao Li, and Gang Chen. Online
partial label learning. In ECML PKDD, volume 12458 of Lecture Notes in Computer Science, pp.
455–470. Springer, 2020.

Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In ICML, volume 119 of Proceedings of Machine Learn_ing Research, pp. 9929–9939. PMLR, 2020._

P. Welinder, S. Branson, T. Mita, C. Wah, F. Schroff, S. Belongie, and P. Perona. Caltech-UCSD
Birds 200. Technical Report CNS-TR-2010-001, California Institute of Technology, 2010.

Hongwei Wen, Jingyi Cui, Hanyuan Hang, Jiabin Liu, Yisen Wang, and Zhouchen Lin. Leveraged weighted loss for partial label learning. In ICML, volume 139 of Proceedings of Machine
_Learning Research, pp. 11091–11100. PMLR, 2021._

Zhi-Fan Wu, Tong Wei, Jianwen Jiang, Chaojie Mao, Mingqian Tang, and Yu-Feng Li. NGC: A
unified framework for learning with open-world noisy data. CoRR, abs/2108.11035, 2021.

Ning Xu, Jiaqi Lv, and Xin Geng. Partial label learning via label enhancement. In AAAI, pp. 5557–
5564. AAAI Press, 2019.


-----

Wenjia Xu, Yongqin Xian, Jiuniu Wang, Bernt Schiele, and Zeynep Akata. Attribute prototype network for zero-shot learning. In Advances in Neural Information Processing Systems 33: Annual
_Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12,_
_2020, virtual, 2020._

Min-Ling Zhang and Fei Yu. Solving the partial label learning problem: An instance-based approach. In IJCAI, pp. 4048–4054. AAAI Press, 2015.

Min-Ling Zhang, Bin-Bin Zhou, and Xu-Ying Liu. Partial label learning via feature-aware disambiguation. In KDD, pp. 1335–1344. ACM, 2016.

Yuhang Zhang, Xiaopeng Zhang, Robert. C. Qiu, Jie Li, Haohang Xu, and Qi Tian. Semi-supervised
contrastive learning with similarity co-calibration. CoRR, abs/2105.07387, 2021.

A THEORETICAL ANALYSIS

**Derivation of Eq. (9).** We provide the derivation of the second equality in Eq. (9). It suffices to
show that LHS = 2n1 _j_ **_x,x[′]_** _Sj_ **_x_** _Sj_

_∈_ _∈_

_[||][g][(][x][)][ −]_ _[g][(][x][′][)][||][2][ =][ P]_ _[||][g][(][x][)][ −]_ **_[µ][j][||][2][ =][ RHS. We have,]_**
P 1

LHS = ( _g(x)_ 2g(x)[⊤]g(x[′]) + _g(x[′])_ )

2nj _||_ _||[2]_ _−_ _||_ _||[2]_

**_xX∈Sj_** **_xX[′]∈Sj_**

= [1] (nj _g(x)[⊤](_ _g(x[′])))_

_nj_ **_xX∈Sj_** _−_ **_xX[′]∈Sj_** (13)

= [1] (nj _g(x)[⊤](njµj)))_

_nj_ **_xX∈Sj_** _−_

= nj ( _g(x))[⊤]µj) = nj(1_ **_µj_** ).
_−_ **_xX∈Sj_** _−||_ _||[2]_

On the other hand,

RHS = (||g(x)||[2] _−_ 2g(x)[⊤]µj + ||µj||[2])

**_xX∈Sj_**

= (nj − 2(xX∈Sj _g(x))[⊤]µj + nj||µj||[2])_ (14)

= nj(1 **_µj_** ) = LHS.
_−||_ _||[2]_

**Proof of Theorem 1.** By regarding πi[j] [as constants w.r.t][ θ][, we can get the following derivation]
from Eq. (10),


_yXi∈Yi_ _πi[y][i]_ [log][ P] [(][x]π[i][, y]i[y][i] _[i][|][θ][)]_ = arg maxθ

= arg max
_θ_

= arg max
_θ_

= arg max
_θ_

= arg max


_πi[y][i]_ [log][ P] [(][x][i][|][y][i][, θ][)][P] [(][y][i][)]
_yXi∈Yi_

I(˜yi = yi) log P (xi|yi, θ)
_yXi∈Yi_


arg max


_i=1_


_i=1_

_n_

_i=1_

X


(15)


log P (x|y = j, θ)
**_xX∈Sj_**


_Sj_ _∈DC_

_SjX∈DC_


= arg max (κµ¯ _[⊤]j_ _[g][(][x][) + log(][c][d][(][κ][)))]_
_θ_

_SjX∈DC_ **_xX∈Sj_**

_nj_

= arg max
_θ_ _n_

_SjX∈DC_ _[||][µ][j][||]_

equality. In the last equality, we use the fact thatwhere nj = |Sj|. Here we ignore the constant factor µj = −n1[P]j _i[n]=1x∈PSjy[g]i∈[(]Y[x]i[)][π][ and]i[y][i]_ [log][ ¯]µj[ π] is the unit directionali[y][i] [w.r.t.][ θ][ in the first]

P


-----

vector of µj. From Eq. (9), we have that,


_g(x)_ **_µj_** = arg min ( _g(x)_ 2g(x)[⊤]µj + **_µj_** )
_||_ _−_ _||[2]_ _θ_ _||_ _||[2]_ _−_ _||_ _||[2]_
**_xX∈Sj_** _SjX∈DC_ **_xX∈Sj_**

= arg min (nj _nj_ **_µj_** )
_θ_ _SjX∈DC_ _−_ _||_ _||[2]_

_nj_

= arg max
_θ_ _n_

_SjX∈DC_ _[||][µ][j][||][2][.]_

(16)


arg min


_Sj_ _∈DC_


Note that the contrastive embeddings are distributed on the hypersphere S[d][−][1] and thus **_µj_**
_||_ _|| ∈_

[0, 1]. It can be directly derived that,


_nj_

_n_

_[||][µ][j][||][2][ ≤]_


_nj_

_n_ (17)

_[||][µ][j][||][ =][ R][2][.]_


_R1 =_


_Sj_ _∈DC_


_Sj_ _∈DC_


Therefore, maximizing the intraclass covariance in Eq. (9) is equivalent to maximizing a lower
bound of the likelihood in Eq. (10). It can also be shown that (R2)[2] _≤_ _R1 followed by the convexity_
of the squared function. Since arg max R2 = 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
_κ_ _−_ valid for large **_µj_** _,_ (18)
_≈_ 2(1 **_µj_** ) _[,]_ _||_ _||_

_−||_ _||_

_d_ _d[2](d + 8)_
_κ_ _d_ **_µj_** 1 + _,_ valid for small **_µj_** _._ (19)
_≈_ _||_ _||_ _d + 2_ _[||][µ][j][||][2][ +]_ (d + 2)[2](d + 4) _[||][µ][j][||][4]_ _||_ _||_
 


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 a regularizer and typically leads to better representation. Finally, we use two copies of data examples such that data are also aligned in its local


-----

Figure 5: A large norm of Euclidean’s mean vector also leads to a strong concentration of unit vectors to its
mean direction.

Figure 5:

A large norm of Euclidean’s mean vector also leads to a strong concentration of unit vectors to its


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.

B ADDITIONAL EXPERIMENTAL SETUPS AND RESULTS

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. Empirically, we find that even weak augmentation for key embeddings also leads to
good results. 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


-----

95

90

85

80

75

70

65


92.5

90.0

87.5

85.0

82.5

80.0

77.5

75.0

72.5

10 2 10 1 10[0] 10[1]

|Col1|Col2|Col3|Col4|Col5|Col6|
|---|---|---|---|---|---|
|||||||
|||||||
|||||||
||||||CIFAR-10|
||||||CIFAR-100|
|||||||
|||||||
|||||||
|||||||
|||||||


(log scale)


0.0 0.2 0.4 0.6 0.8 1.0

|Col1|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|
|---|---|---|---|---|---|---|---|---|
||||||||||
||||||||||
||||CIFAR-1|0|||||
||||CIFAR-1|00|||||
||||||||||
||||||||||
||||||||||



(a) Ablation φ


(b) Ablation λ


Figure 6: More ablation results on CIFAR-10 (q = 0.5) and CIFAR-100 (q = 0.05). (a) Performance of PiCO
with varying φ. (b) Performance of PiCO with varying λ.

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.


Table 4: Performance of PiCO with varying γ on CIFAR-10 and CIFAR-100.


|Dataset|γ = 0.1 γ = 0.5 γ = 0.9 γ = 0.99 γ = 0.999|
|---|---|

|CIFAR-10 (q = 0.5) CIFAR-100 (q = 0.05)|93.61 93.51 93.52 93.58 93.66 72.87 73.09 72.54 72.74 67.33|
|---|---|


**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 the 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.

Table 5: Training accuracy of pseudo targets on CIFAR-10 and CIFAR-100.


|Dataset|CIFAR-10 q = 0.1 q = 0.3 q = 0.5|CIFAR-100 q = 0.01 q = 0.05 q = 0.1|
|---|---|---|


|Accuracy|98.28 98.26 96.79|99.06 96.27 90.58|
|---|---|---|


**The disambiguation ability of PiCO. Finally, we evaluate the disambiguation ability of the pro-**
posed 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,


-----

1.0

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2


1.0

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2


|Col1|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|
|---|---|---|---|---|---|---|---|---|
||||||||||
||||||||||
||||||||||
||||||||||
|||||PiC On|O e-Ho|t Prot|otype||
||||||||||
|||||So|ft Pro|totyp|e Pro|bs|
||||||||||
|||||MA|Soft|Proto|type|Probs|
||||||||||
||||||||||
||||||||||
||||||||||


PiCO
One-Hot Prototype
Soft Prototype Probs
MA Soft Prototype Probs

100 200 300 400 500 600 700 800

Epoch

(a) CIFAR-10 (q = 0.5)


|Col1|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|
|---|---|---|---|---|---|---|---|---|
||||||||||
||||||||||
||||||||||
||||||||||
|||||Pi O|CO ne-Ho|t Prot|otype||
||||||||||
|||||So|ft Pro|totyp|e Pro|bs|
||||||||||
|||||M|A Soft|Proto|type|Probs|
||||||||||
||||||||||
||||||||||
||||||||||


PiCO
One-Hot Prototype
Soft Prototype Probs
MA Soft Prototype Probs

0 100 200 300 400 500 600 700 800

Epoch

(b) CIFAR-100 (q = 0.05)


Figure 7: The mean max confidence curves of different label disambiguation strategies.

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. Combined with the fact that
the mean max confidence score of the pseudo target is close to 1, the training examples finally
become 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
set the input image resolution as 224 × 224 and 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 CIFAR100-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 _[|]Y[Y]i[i][∩]Y[Y]j[j]_ _[|]_

_|_ _∪_ _|_ _[≤]_ _[ρ][ (][ρ][ = 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 re-_
_≤_
move 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

-----

Table 6: Accuracy comparisons on fine-grained datasets. Bold indicates superior results.

|Dataset|Method|q = 0.1 q = 0.5 q = 0.8|
|---|---|---|
|CIFAR-100-H|PiCO (ours) LWS PRODEN CC MSE EXP|73.41 ± 0.27% 72.04 ± 0.31% 66.17 ± 0.23% 62.41 ± 0.03% 57.25 ± 0.02% 20.64 ± 0.48% 62.91 ± 0.01% 60.89 ± 0.03% 43.64 ± 1.82% 50.40 ± 0.20% 42.60 ± 0.11% 37.80 ± 0.09% 46.05 ± 0.17% 39.52 ± 0.28% 15.18 ± 0.73% 45.73 ± 0.22% 35.08 ± 1.71% 22.31 ± 0.39%|
|Dataset|Method|q = 0.01 q = 0.05 q = 0.1|
|CUB-200|PiCO (ours) LWS PRODEN CC MSE EXP Fully Supervised|74.14 ± 0.24% 72.17 ± 0.72% 62.02 ± 1.16% 73.74 ± 0.23% 39.74 ± 0.47% 12.30 ± 0.77% 72.34 ± 0.04% 62.56 ± 0.10% 35.89 ± 0.05% 56.63 ± 0.01% 55.61 ± 0.02% 17.01 ± 1.44% 61.12 ± 0.51% 22.07 ± 2.36% 11.40 ± 2.42% 55.62 ± 2.25% 9.44 ± 2.32% 7.3 ± 0.99% 76.02 ± 0.19%|



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 Table 7: Accuracy comparisons with different
the true label than others, which makes their prob- data generation processes on CIFAR-10.
ability of label flipping q larger than others. In Method Case (1) Case (2)
other words, the data generation procedure is non
|Method|Case (1)|Case (2)|
|---|---|---|

uniform. In Section 4.4, we have shown one such _±_ _±_
case on CIFAR-100-H, where semantically similar LWS 90.78 ± 0.01% 68.37 ± 0.04%
labels have a larger probability of being a false posi-tive. Moreover, we follow (Wen et al., 2021) to con- PRODENMSECC 90.5375.8168.11 ± ± ± 0.01% 0.13% 0.23% 87.0266.5139.49 ± ± ± 0.02% 0.11% 0.41%
duct empirical comparisons on data with alternative EXP 71.62 ± 0.79% 48.87 ± 2.32%
generation processes. In particular, we test two com
|PiCO LWS PRODEN CC MSE EXP|94.49 ± 0.08% 90.78 ± 0.01% 90.53 ± 0.01% 75.81 ± 0.13% 68.11 ± 0.23% 71.62 ± 0.79%|94.11 ± 0.25% 68.37 ± 0.04% 87.02 ± 0.02% 66.51 ± 0.11% 39.49 ± 0.41% 48.87 ± 2.32%|
|---|---|---|

monly used cases on CIFAR-10 with the following flipping matrix, respectively:

1 0.5 0 _· · ·_ 0 1 0.9 0.7 0.5 0.3 0.1 0 _· · ·_ 0

(1) =  0. 1 0.5 _· · ·_ 0.  (2) =  0. 1 0.9 0.7 0.5 0.3 0.1 _· · ·_ 0. 

. . . .

0..5 0 _· · ·0_ 1.  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 THE 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.


Table 8: Training time (min/epoch) and accuracy of
different prototype calculation methods.

|Dataset|Method|Time Accuracy|
|---|---|---|



|CIFAR-10 (q = 0.5)|PiCO Re-Compute|0.94 93.58 1.39 93.55|
|---|---|---|

|CIFAR-100 (q = 0.05)|PiCO Re-Compute|0.96 72.74 1.40 72.35|
|---|---|---|


-----

**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 embeddings generation

**4** _Bq =_ **_qi = g(Augq(xi))_** **_xi_** _B_
_{_ _|_ _∈_ _}_

**5** _Bk =_ **_ki = g[′](Augk(xi))_** **_xi_** _B_

**6** _A = B {q_ _Bk_ queue _|_ _∈_ _}_

**7** **for x// classifier predictioni ∈ ∪B do ∪**


**8** _y˜i = arg maxj∈Yi f_ _[j](Augq(xi))_
// momentum prototype updating

**9** **_µc = Normalize(γµc + (1 −_** _γ)qi), if ˜yi = c_

// positive set generation

**10** _P_ (xi) = **_k[′]_** **_k[′]_** _A(xi), ˜y[′]_ = ˜yi
_{_ _|_ _∈_ _}_

**11** **end**
// prototype-based label disambiguation

**12** **for qi ∈** _Bq do_

**13** **_zi = OneHot(arg maxj∈Yi qi[⊤][µ][j][)]_**

**14** **_si = φsi + (1 −_** _φ)zi_

**15** **end**
// contrastive loss calculation


1 1 exp(qi[⊤][k][+][/τ] [)]
**16** _Lcont(g; τ, A) =_ _|Bq_ _|_ **_qi∈Bq_** _−_ _|P (xi)|_ **_k+∈P (xi)_** [log] **_k[′]_** _∈A(xi_ ) [exp(][q]i[⊤][k][′][/τ] [)]

 

// classification loss calculationP P P

**17** _Lcls(f_ ; B) = _|B1_ _|_ **_xi∈B_** _Cj=1_ _[−][s][i,j][ log(][f][ j][(][Aug]q[(][x][i][)))]_

// network updating

P P

**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**

C PSEUDO-CODE OF PICO

We summarize the pseudo-code of our PiCO method in Algorithm 1.

D THE LITERATURE OF PROTOTYPE LEARNING

Prototype learning (PL) aims to learn a metric space where examples are enforced to be closer to its
class prototype. 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.


-----

