Local Label Propagation for Large-Scale Semi-Supervised Learning
Authors: Chengxu Zhuang
Chaofei Fan
Xuehao Ding
Divyanshu Murli
Daniel Yamins
Venue:  (2020)

Abstract: A significant issue in training deep neural networks to solve supervised learning
tasks is the need for large numbers of labeled datapoints. The goal of semisupervised learning is to leverage ubiquitous unlabeled data, together with small quantities of labeled data, to achieve high task performance. Though substantial recent progress has been made in developing semi-supervised algorithms that are effective for comparatively small datasets, many of these techniques do not scale readily to the large (unlabeled) datasets characteristic of real-world applications. In this paper we introduce a novel approach to scalable semi-supervised learning, called Local Label Propagation (LLP). Extending ideas from recent work on unsupervised embedding learning, LLP first embeds datapoints, labeled and otherwise, in a common latent space using a deep neural network. It then propagates pseudolabels from known to unknown datapoints in a manner that depends on the local geometry of the embedding, taking into account both inter-point distance and local data density as a weighting on propagation likelihood. The parameters of the deep embedding are then trained to simultaneously maximize pseudolabel categorization performance as well as a metric of the clustering of datapoints within each psuedo-label group, iteratively alternating stages of network training and label propagation. We illustrate the utility of the LLP method on the ImageNet dataset, achieving results that outperform previous state-of-the-art scalable semi-supervised learning algorithms by large margins, consistently across a wide variety of training regimes. We also show that the feature representation learned with LLP transfers well to scene recognition in the Places 205 dataset.

Under review as a conference paper at ICLR 2020
LOCAL LABEL PROPAGATION FOR LARGE-SCALE SEMI-SUPERVISED LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
A significant issue in training deep neural networks to solve supervised learning tasks is the need for large numbers of labeled datapoints. The goal of semi- supervised learning is to leverage ubiquitous unlabeled data, together with small quantities of labeled data, to achieve high task performance. Though substantial recent progress has been made in developing semi-supervised algorithms that are effective for comparatively small datasets, many of these techniques do not scale readily to the large (unlabeled) datasets characteristic of real-world applications. In this paper we introduce a novel approach to scalable semi- semi-supervised learn- ing, called Local Label Propagation (LLP). Extending ideas from recent work unsupervised embedding learning, LLP first embeds datapoints, labeled and other- wise, in a common latent space using deep neural network. It then propagates pseudolabels from known to unknown datapoints in a manner that depends on the local geometry of the embedding, taking into account both inter-point distance and local data density as weighting on propagation likelihood. The parameters of the deep embedding are then trained to simultaneously maximize pseudolabel categorization performance well as metric of the clustering of datapoints within each psuedo-label group, iteratively alternating stages of network training and label propagation. We illustrate the utility of the LLP method on the ImageNet dataset, achieving results that outperform previous state-of-the-ee scalable semi-supervised learning algorithms by large margins, consistently across wide variety of training regimes. We also show that the feature representation learned with LLP transfers well scene recognition in the Places 205 dataset.
INTRODUCTION
Deep neural networks (DNNs) have achieved impressive performance tasks across variety of domains, including vision (Krizhevsky et al. 2012, Simonyan & Zisserman 2014 He et al. 2016a 2017), speech recognition (Hinton et al. 2012 Hannun et al. [014
al. 2013 Noda et al. 2015), and natural language processing Young et al. 2018 Hirschberg & Manning. 2015 Conneau al. 2016 Kumar al., (2166). However, these achievements often heavily rely large-scale labeled datasets, requiring burdensome and expensive annotation efforts. This problem is especially acute in specialized domains such as medical image processing, where annotation may involve performing an invasive process on patients.
Semi-supervised learning (SSL) seeks learn useful representations from limited amounts of labeled data, leveraging it in conjunction with extensive unlabeled data. SSL has shown significant
promise (Liu et al. 2018 Iseen et al.. 2019 Zhai et al. 2019 9 Miyato et al. 2018 Tarvainen & Valpola, 2017 Lee 2013] Grandvalet & Bengio 2005 Qiao et al. [018]] Xie et al. 2019). However, gaps to supervised performance levels still remain significant, and many recent SSL methods rely on techniques whose efficiency scales poorly with dataset size and thus cannot be readily applied to many real-world machine learning problems (Liu et al. 2018) Iscen et al. 2019).
Here, we propose novel SSL algorithm that is specifically adapted for use with large sparsely-labeled datasets. This algorithm, termed Local Label Propagation (LLP), learns a nonlinear embedding of the input data, and exploits the local geometric structure of the latent embedding space help infer useful pseudo-labels for unlabeled datapoints. LLP borrows the framework non- non-parametric embedding learning, which has recently shown utility in unsupervised learning (Wu et al. 2018b

---

Under review as a conference paper at ICLR 2020
Zhuang et al. 2019), to first train deep neural network that embeds labeled and unlabeled examples into a diwesssil latent space. LLP then propagates labels from known examples to unknown datapoints, weighting the likelihood of propagation by the local density of known examples. The neural network is then optimized to categorize all datapoints according to their pseudo-labelt (with stronger emphasis true known labels), while simultaneously encouraging datapoints sharing the same (pseudo-)labels to aggregate in the latent embedding space. The resulting embedding thus gathers both labeled images within the same class and unlabeled images sharing statistical similarities with the labeled ones. Through iteratively applying the propagation and network training steps, the LLP algorithm builds good underlying representation for supporting downstream tasks, and trains an accurate classifier for the specific desired task.
We apply I.I. the context of object categorization in the ImageNet dataset (Deng et al. 2009). learning
network while discarding most of the labels. We show that LLP substan- tially outperforms previous scalable semi-supervised algorithms (Zhai et al. 2019 Miyato et al. 20188] Tarvainen & Valpola 2017: Lee 2013 Grandvalet & Bengio, 2005 Qiao et al. 2018) across wide
variety of training regimes, and that LLP-trained features support improved transfer to Places205, a large-scale scene-re recognitonn task. We also present analyses that provide insights into the learning
procedure and justification of key parameter choices.
2 RELATED WORK
Below we describe conceptual relationships between our work and recent related approaches, and identify relevant major alternatives for comparison.
Deep Label Propagation. Like LLP, Deep Label Propagation (Iscen et al. 2019 (DLP) also iterates between steps of label propagation and neural network optimization. In contrast to LLP, the DLP label propagation scheme based on computing pairwise similarity matrices of learned visual features across all (unlabeled) examples. Unlike in LLP, the DLP loss function is simply classification with respect to pseudo-labels, without any additional aggregation terms ensuring that the pseudo- labeled and true-labeled points have similar statistical structure. The DLP method is effective on comparatively small datasets, such as CIFARIO and Mini- Mini-ImageNet. However, DLP is challenging to apply to large-scale datasets such as ImageNet, since its label propagation method is O(N") in the number N of datapoints, and is not readily parallelizable. In contrast, L.P is O(N M). where M is the number of labeled datapoints, and is easily parallelized. making its effective complexity O(N M (P), where P is the number of parallel processes. In addition, DLP uniformly propagates labels across the embedding space, while LLP's use of local density-driven propagation weights specifically exploits the geometric structure in the space, improving pseudo-label inference.
Deep Metric Transfer and Pseudolabels. The Deep Metric Transfer (Liu et al., 2018) (DMT) and Pseudolabels (Lee) 2013) methods both use non-iterative two-stage procedures. In the first stage, the representation is initialized either with self- task such non-parametric instance recognition (DMT), or via direct supervision on the known labels (Pseudolabels). In the second stage, pseudo-labels are obtained either by applying label propagation algorithm (DMT) or naively from the pre-trained classifier (Pseudolabels), and these are then used to fine-tune the network. As in DLP, the label propagation algorithm used by DMT cannot be applied to large-scale datasets, and does not specifically exploit local statistical features of the learned representation. While more scalable, the Pseudolabels approach achieves comparatively poor results. A key point of contrast between LLP and the two-stage methods is that in LLP, the representation learning and label propagation processes interact via the iterative training process, an important driver of L.PP's improvements.
Seff-Supervised Semi-Supervised Learning. Self-Supervised Semi-Supervised I Learning (Zhai et al. 2019) (S*L) co-trains a network using self-superviser methods on unlabeled images and traditional classification loss on labeled images. Unlike LLP, S'L simply "copies" self-supervised learning tasks as parallel co- co-training loss branches. In contrast, LLP involves a nontrivial interaction between known and unknown labels via label propagation and the combination of categorization and aggregation losses, both factors that are important for improved performance.
Consistency-bases regularization. Several recent semi-supervised methods rely data- consistency regularizations. Virtual Adversarial Training (VAT) (Miyato et al. 2018) adds small input perturbations, requiring outputs be robust this perturbation. Mean Teacher (MT) (Tarvainen &
2

---

Under review as a conference paper at ICLR 2020
C. Embedding
d. Pseudolabels
b. ConvNet
Oroan Funvey
a. Input
Paus Getageiation
Viow
Approricc
Figure 1: Schematic of the Local Label Propagation (LLP) method. a.-b. We deep convolu- tional neural networks to simultaneously generate a lower-dimensional embedding and a category prediction for each input example. If the embedding of the input (denoted by *) is unlabeled, identify its close labeled neighbors (colored points), and infer * pseudo-label by votes from these neighbors, with voting weights jointly determined by their distances from * and the density of their local neighborhoods (the highlighted circular areas). d. The pseudo-labels thereby created (colored points) come equipped with a confidence (color brightness), measuring how accurate the pseudo- is likely to be. The network in b. is optimized (with per-example confidence weightings) so that its category predictions match the pseudo-labels, while its embedding attracted (++) toward other embeddings sharing the same pseudo-label and repelled (a-o) by embeddings of other pseudo-labels.
Valpola 2017) requires the learned representation to be similar to its exponential moving average during training. Deep Co-Training (DCT) (Qiao et al. 2018) requires the outputs of two views of the same image to be similar, while ensuring outputs vary widely using adversarial pairs. Very recently, Unsupervised Data Augmentation (UDA) (Xie et al.) 2019) achieves state-of-the
performance
by incorporating substantially framework, and employing computationally expensive hut practically impactful details such as the use of very large batch size during optimization. These methods all use unlabeled data in a "point-wise" fashion, applying the proposed consistency metric separately on each. They thus differ significantly from (and are thus likely complementary to) LLP, or indeed any method that explicitly relates unlabeled to labeled points. LLP benefits from training shared embedding space that aggregates statistically similar unlabeled datapoints together with labeled (putative) counterparts. As a result, adding more unlabeled images consistently increases the performance of LLP, unlike for (e.g.) MT.
complex data augmentation scheme into the data-consistency
METHODS
We first give an overview the LLP method. At high level, LLP learns model (-) from labeled examples X,, = {ø1,... ............ TMM. ). their associated labels Y, {vi..... . ymr) }. and unlabeled examples Xu = ( NN). fo(.) is realized via a deep neural network whose parameters 0 are network weights. For each input x. f=( generates two outputs (Fig. 1: an "embedding output", realized as a vector e in a D-dimensional sphere, and a category prediction output ÿ. In learning fe(-), the LLP procedure repeatedly alternates between two steps: label propagation and representation learning. First, known labels Yr. are propagated from X₁, to Xts, creating pseudo-labels Yú = {UM+1,... yN Then, network parameters 0 are updated to minimize loss function balancing category prediction accuracy evaluated on the outputs, and a metric of statistical consistency evaluated on the e outputs.
In addition to pseudo-labels, the label propagation step also generates [-,lld confidence scores c for each example x,, For labeled points, confidence scores Cz {c1, CMr are automatically set to I, while for lseudo-labeled examples, confidence scores Ct: (cM CM ..., eN) are computed from the local geometric structure of the embedded points, reflecting how close the embedding vectors of the pscudo-labeles points are to those of their putative labeled counterparts. The confidence values are then used as loss weights during representation learning.
Representation Learning. Assume that datapoints X = Xu XL. labels and pseudo-labels Y = Yú U U,, and confidences C = Cy Cr, given. Let V (Vi,..., uN) denote the set of corresponding embedded vectors, and Y (ύ1: -.1.....a .N) denote the set of corresponding category
3

---

Under review as a conference paper at ICLR 2020
prediction outputs. In the representation learning step, we update the network embedding parameters by simultaneously minimizing the standard cross-entropy loss Io(Y, Y) between predicted and propagated pseudo-labels, while maximizing a global aggregation metric (V(Y)) to enforce overall consistency between known labels and pseudo-labels.
The definition of (V is based on the non- non--araman pana-aaaatric softmax operation proposed in (Wu et al. 2018b a). Specifically, we define the joint probability of any two embedding vectors v2 and by as:
P(u, 12) exp(v; UŞ/T)
exp(ee DE (V(/)
where temperature E (0, 1] is a fixed hyperparameter. Using this definition, can get the probability of o; and the conditional probability of vy given U; as:
P(o)) = ((),,);)= Σ cpp(o? Uz/T) P(oyle)) P(u, exply v,/T)
(2)
Z
P(m()) En explo? vi/T)
1=1
Additionally, for S X, its probability given v, is P(S -Eo,es P(ullv,). We then define the aggregation metric as the (negative) log likelihood of the examples whose pseudo-labels are also y, the pseudo-label of the current example (v) = -log( P(A[=)), where A= for ly, = y). Optimizing L (v) encourages the embedding corresponding to given datapoint to selectively become close to embeddings of other datapoints with the same pseudo-label (Fig. D
The cross-entropy and aggregation loss terms are scaled on a per-example basis by the confidence score, and an L2 weight regularization penalty is added. Thus, the final loss for example is: [(x10) [To(v: 9) + [v)] + >110112. where À is regularization hyperparameter.
Label Propagation. To understand how LLP generates pseudo-labels Yu and confidence scores Cu. it is useful start from the weighted N-Neahost-Neighbor classification algorithm (Wu al. 2018b), in which a "vote" is obtained from the top K nearest labeled examples for each unlabeled example x, denoted (x). The vote of each x; E NNx P(e.lu). Assuming S classes, the total weight for apeudo-labeled v as class j is thus:
weighted by the corresponding probabilities
wwy(1) Σ P(u,lu), where f(r) {ilor, E (K) y }} (ETU)
Therefore, the probability (v) that datapoint æ is of class j. the associated inferred pscudo- label y. and the corresponding confidence c, may be defined as: (,(1) wy(v)/ Σ (x(v). = arg max, (w). and (v). Although intuitive, weighted-KNN introduces a positive correlation between the local density of labeled example and the number of unlabeled examples whose pscudo-labels are propagated from this labeled example. Moreover, if the labeled examples within one category have higher densities than other categories, there will be more unlabeled examples pseudolabled as this category. To avoid this correlation, we additionally penalize the labeled examples with higher densities through dividing the KNN weight of a labeled example by its local density. To formalize this penalization, we divide P(vlle) in the definition of wy weighted probability:
(1) with local density-
pt (w;lu) = P(vslu)/((;:) where p(v:) = Σ P(uj.vs)
(4)
jENz(u)
where (v.) are T nearest unlabeled examples and denominator p(v)) is measure of the local embedding density. For consistency, we replace (x) with (v). which contains the K labeled neighbors with highest locally-weighted weighted probability, to ensure that the votes come from the most relevant labeled examples. The final form of the LLP propagation weight equation is thus:
P(u,lu)
wy(w)=
SE/Ú) ExENS(O.) P(u,, v;)) where r(] {ili E ( y: =
Σ
(5)
The intuition behind the local density weighting idea is further quantitatively explored in
Memory Bank. Both described steps implicitly require access to all the embedded vectors V at every step. However, recomputing V becomes intractable for bigger dataset. We address this issue by approximating realtime V with memory bank V that keeps a running average of the embeddings. As this procedure is taken from Wu et al. (0188), refer readers there for detailed description.
4

---

Under review as a conference paper at ICLR 2020
Table 1: Top-1 accuracy (%) of ResNet-18 on ImageNet with varying p and g 100
Method
p 1
p =
p 5
p 10
Supervised
17.35
28.61
36.01
47.89
DCT (Qiao al. 2018)
53.50
MT (Tarvainen & Valpola 2017)
16.91
40.81
48.34
56.70
LLP (ours)
27.14
53.24
57.04
61.51
LLP + RJ (ours)
33.55
55,30
58.92
63.20
Table 2: Top-5 accuracy (%) of ResNet-50 on ImageNet with = (1, 10) and = 100
p
Supervised
Pseudolabels
VAT-EM
S $
MT
LLP (ours)
LLP + RJ (ours)
48.43
51.56 82.41
46.96
53.37
40.54
61.89
72.20
10
80.43
83.39
83.82
85,42
88.53
89.55
RESULTS
We first evaluate the L.P method on visual object categorization in the large-scale ImageNet dataset (Deng et al., 2009), under variety of training regimes. We also illustrate transfer learning to Places 205 (Zhou et al. 2014). large-scale scene-recognition dataset.
Experimental settings. We follow Wu et al. (2018)) 8b) for most of our hyperparameters and optimiza- tion settings. In the label propagation step. we set K 10 and T 25 (these choices are justified in Section (5). We use ResNet-18v2 and ResNet-50v2 (He et al. 2016b). We find "rate-jump" phase beneficial: after the initial schedule for the learning rate, increasing and dropping it again improves the performance. We think this is because larger learning rate is needed leverage the better embedding space in the later training, especially given that the performance usually has big jumps after dropping the learning rate and the dropped learning rate already too small to exploit the improved quality. To clearly show the effect of this phase, we list the performance after applying it using "LLP RJ" in Table 2 We also apply this phase to supervised learning and Mean Teacher and their performances are not changed. More details are in Appendix A We train on ImageNet with p% labels and 4% total images available, meaning that M ~ p% 1.2M, N 9% 1.2M. Different regimes are defined by {1,3, 5, 10} and y {30, 70, 100}. Results are shown in Tables I Due to the inconsistency of reporting metries across different papers, we alternate between comparing topl and top5, depending which was reported in the relevant previous work.
The results show that: 1. LLP significantly outperforms previous state-of-the-arl methods by large margins within all training regimes tested, regardless of network architectures, p. and q. 2. When compared to the very recent UDA approach (Xie et al., 2019) for ResNet-50 with p = 10 and q 100, LLP achieves better top5 (89.55 v.s. 88.52, LLP UDA) and topl (70.85 v.s. 68.66). Moreover, LLP has the potential to achieve even higher performance if trained with the complex preprocessing pipeline and large batch size used in UDA (15360 for UDA 64 for L.PP here, chosen due to computational resource limitations), as these details have been shown to mcaningfully improve performance; LLP shows especially large improvements to other methods when p small. For example. R trained using LLP with p = 1 surpasses MT by 16.64% % in topl and our ResNet-50 with p surpasses S'L by 18.83 top5 (UDA does not report for less than 10% labels).
Leveraging additional unlabeled images. To examine how good LLP at using unlabeled images, we first vary the value of while p remains at 10. As shown in 3 LLP consistently benefits from additional unlabelled images and is not yet saturated using the whole ImageNet, unlike Mean Teacher, where the number of unlabelled images appears essentially irrelevant.
To further assess how LLP might behave in noisier real-world settings, we additionally performed a preliminary exploration using the YFCC100M (Thomee et al.) 2015) dataset as source of augmenta-
For 5" L, list their s* I.-Rotation performance, which is their best reported performance using ResNet- 50. Note that although model with higher performance is reported by S T., that model uses much more complex architecture than ResNet-50.
5

---

Under review as a conference paper at ICLR 2020
Table Top-1 accuracy (%) of ResNet-188 on ImageNet with p = 10 and varying p. "FT" means the fine-tuning process used in YFCC100M experiments, which is the same as the "rate-jump" phase.
ImageNet
ImageNet YFCCIOOM q 100+FAR q = 100R
Method
q =0
q 70
q 100
g 100+ FT
MT
56.07
55.59
55.65
LLP (ours)
58.62
60.27
61.51
63.20
63.14
63.53
Table 4: ResNet-50 transfer learning Top-1 accuracy (%) Places205 using weights pretrained on ImageNet with p = (1, 10). Most numbers are from Zhai et al. (019)) Produced by us.
# labels
Supervised
Pseudolabels
VAT
VAT-EM
SLL
MT
LLP (ours)
LA*
10%
44.7
48.2
45.8
46.2
46.6
46.4
50.4
48.3
1%
36.2
41.8
35.9
36.4
38.0
31.6
48.5
tion. However, because YFCC100M drawn from a very different distribution than ImageNet, we select subset of images that are more similar to ImageNet using the pipeline proposed by (Yalniz al. 2. This pipeline is applied to two randomly chosen subsets of YFCC100M with 5M and 1OM images, respectively, creating two selected training subsets each of roughly 480K images denoted FAR and NEAR differing how close to the ImageNet distribution the sets are. We then combine each selected set with ImagetNet of p 10 and q 100 and train LLP. After this training, we finetuned the model with only ImagetNet data using LLP, following the procedure (Yalniz let al. 2019). Please refer to Appendix B for more details of the selection and fine-tuning processes.
The results in Table show that even with this very preliminary attempt, LLP achieves 2.02% performance improvement with augmentation of images chosen from the NEAR augmentation, compared to the 61.51% % baseline (though the fine-tuning process likely accounts for part of this improvement). Almost certainly, such augmentations would be substantially greater if larger number of images from a better-matched distribution were available and a better network is used for selecting the images (Yalniz et al., 2019). Unfortunately, direct comparison between LLP and Yalniz et al. (2019) is not presently possible as their ResNet18 result uses the entire labeled ImageNett and all of YFCC100M select matched augmentation images, both of which require significantly more computation resources than are available to us. However, it is worth noting that LLP benefits even from selecting the matched dataset from 10M YFCC images, while Yalniz et al. 2019 needs more than 20M images to achieve a similar gain.
Transfer learning to Scene Recognition. To evaluate the quality of our learned representation in other downstream tasks besides ImageNet classification, we assess its transfer learning performance to the Places205 (Zhou et al., 2014) dataset. This dataset has 2.45M images total in 205 distinct scene categories. We fix the nonlinear weights learned on ImageNet, add another linear readout layer on top of the penultimate layer, and train the readout using cross-entropy loss using SGD as above. Please refer to Appendix for other details. We only evaluate our ResNet-50 trained with p = {1, 10), as /Zhii et al. (2019) reported performance with this setting. Table 4 show that LLP again significantly outperforms previous state-of-the-ar results. It is notable that when trained with = 1, only LLP shows slightly better performance to Places205 than the Local Aggregation (LA)
method, the current state-of-the-ar unsupervised learning method (Zhuagg et al. 2019)
5 ANALYSES
Emerging clusters during training. Intuitively, the aggregation term (v(v) should cause embed- ding outputs with the same label, whether known or propagated, to cluster together during training. Fig. D shows clustering becoming more pronounced along the training trajectory both for labelled and unlabelled datapoints, while unlabelled datapoints surround labelled datapoints increasingly densely. A simple metric measuring the aggregation of group of embedding vectors is the L2 norm of the group mean, which, since all embeddings lie in the 128-D unit sphere, is inversely related to the group dispersion. Computing this metric for each category and averaging across categories, we obtain a guantitative description of aggregation over the learning timecourse (Fig. PPg. further supporting the conclusion that I.I. embeddings become increasingly clustered. We also investigate how network

---

Under review as a conference paper at ICLR 2020
a.
Epoch 20
Epoch 40
Epoch 100
Epoch 230
Epoch 280
0.74
ResNet-50
Restes:00
Monarch
Nom
ResNet-18
0.4
20
Epoch
320
18
0.5
Veeow labs"
Labrador
20 Classes
Spatula
Figure 2: MDS embeddings of 128-D embedding outputs 100 random images from each of five random ImageNet categories, from the beginning to the end LLP training. Larger points with black borders are images with known labels. b. Trajectory of cross-category average of 1.2-norms of category embedding vectors. Sudden changes are due to learning rate drops. c. Histogram of the L2-norm metries for each category, for fully-trained ResNet-18 18 and ResNet-50 networks. d. Scatter plot of L2-norm metric for ResNet- 18 (z-axis) and ResNet-50 (y-axis). Each dot represents one category. e.-g. MDS embeddings and exemplar images for images of "Monarch", "Spatula", and "Labrador". For each category, MDS embedding is computed from 700 random images.
Correlation: 0.39
Correlation:
b.
Correlation d.
No. images
1500-
clasges
50
0.4
1000-
1000
50
500
500
1500
20
170
320
Density (x107)
No. images
Epoches
Figure 3: Density weighting analysis. Orange color is for "NoDW" model and blue color is for LLP model. a, Scatter plot of ImageNet classes. Each dot represents one class. For class i, X-axis is D; and Y-axis is Q, Both models are fully trained. c. Histogram plot of classes showing the distribution of Q. d. The trajectory of Pearson correlation between {D,} and {Q.) during training.
architecture influences learning trajectory and the final representation, comparing ResNet-50 and ResNet-18 18 trained with 10% labels (Fig. Dp-d). The more powerful ResNet-50 achieves more clustered representation than 18, across timepoints and categories.
Category structure analysis: successes, failures, and sub-category discovery. It instructive to systematically analyze statistical patterns on a per-category basis. To do this, we visualize the embeddings for three representative categories with 2D multi-dimensional scaling (MDS). For an "casy" category with a high aggregation score (Fig. 2 ) the LLP embedding identifies images with strong semantic similarity, supporting successful image retrieval. For "hard" category with low score (Fig. 2), image statistics vary much more and the embedding fails to properly cluster examples together. Most interestingly, for multi-modal categories with intermediate scores (Fig, 22), the embedding can reconstruct semantically meaningful sub-clusters even when these are not present in the labelling e.g. the "labrador" category decomposing into "black" and "yellow" subcategories.
Comparison to global propagation in the small-dataset regime. To understand how LLP com- pares to methods that use global similarity information, but therefore lack scalability to large datasets, test several such methods on ImageNet subsets (see Appendix for details). Table 5 shows that LLP can be effective even in this regime, as it is comparable to the global propagation algorithm used in DMT (Liu et al. 2018) and only slightly lower than DLP (Iscen et al. 2019).
Sshlos
Ablation studies. To illustrate the importance of key design choices in LLP, we conduct a series of ablation studies exploring the following alternatives, using: 1. Different K's (experiments Top50,

---

Under review as a conference paper at ICLR 2020
Table 5: Label propagation performance on ImageNet subsets. LS: Label Spreading (Zhou al.
2004). LP: Label Propagation (Zhu & Ghahramani 2002). LP PPDDMT the method in DMT (Liu et al.
2018 LP PLP.: the method in DLP (Iscen et al.
2019). Standard deviations are across 10 subsets.
Method
LS
LP
LP_DMT
LP_DLP
LLP (ours)
Perf.
84.6 i 3.4 87.7 + 2.2
88.2 + 2.3 89.2 + 2.4 88.1 t 2.3
Table 6: Top1 accuracy (%) for ResNet-18 and ResNet-50 trained with p 10, 100 and other settings. "TopX" means training with =X. "NoC" does not weight the loss by confidence. "NoDW" means the KNN weight is not weighted by densities.
Model
Top50
Top20
Top5
NoC
NoDW
LLP
Res18 Perf.
61.07
61.48
60.90
55,88
58.41
61.51
Res50 Perf.
64.01
66.41
68.90
Top20, and Top5 in Table or not (NoDW). Tahle the contributions of each design choice, indicating that hoth confidence weighting and density weighting lead significant performance gains, across architectures.
6 2. Confidence weighting, not (NoC); 3. Density- probability,
Understanding density weighting. To better explain why the density weighting method is useful, compute two measures for each class the average density of its labeled examples, denoted D;; and the number of unlabeled examples pseudolabled as i, denoted Qi Formally, these are defined by: where L, = { E Xx, ; i). and Q, [K]] E yy.y/ 1)-1 Fig. illustrates the strong positive correlation between D. and Q: for the unweighted NoDW model, which leads to an imbalanced distribution of Q, shown in Fig. 3.. After applying density weighting, Dj and Q; become decorrelated (Fig. Bp), creating an empirically accurate balanced pseudo-label class distribution, throughout optimization (Fig. 3d.. Another potential method to enforce an empirically correct Q; distribution would be reweight KNN coefficients Jo directly reflect the empirical label ratio, replacing (v://u) in eq. 4 with P ("("sl)) = P(u; x
D, LjLL Zp(w;)//l
Luz AF M
However, this simple "ratio- based" scheme does not expiciilyy address the local correlation of Q2 and Dj- Indeed, an experiment with p p0(vvlv in place of P'(y/lu) using ResNet-16 18 on 10% labeled IetgeNet only achieves top1 59.4%, substantially worse than LLP,, further supporting the effectiveness of the more sophisticated local density weighting approach.
6 CONCLUSION
In this work, we presented LLP, a method for semi-supervised deep neural network training that efficiently propagates labels from known unknown examples common embedding space, ensuring high-quality propagation by exploiting the local structure of the embedding. The embedding itself is simultaneously co-trained to achieve high categorization performance while enforcing statistical consistency between real and pseudo-labels. LLP achieves state-of ofute-of-the-ar the-arte semi-superee cemi-supervised learning results across all tested training regimes, including those with very small amounts of labelled data, and transfers effectively to other non-trained tasks.
In future work, we seek to improve LLP by better integrating with state of-----ttthhrrr-r unsupervised learning methods (e.g. Zhuang et al, (2019)) This is especially relevant in the regime with very-low fractions of known labelled datapoints (e.g. <1% of ImageNet labels), where the best unsupervised methods outperform state-of-ft thehehrt semi-supervised methods. Combining LLP with the very distinct point-wise methods in MT or UDA is also of interest, as would be the effective use of larger computational resources enable conceptually simple but practically important optimization details such as (e.g.) significantly larger batch size in UDA. In addition, in its current formulation, LLP may be less effective on small datasets than alternatives that exploit global similarity structure (e.g. [[cee] eet al. (2019);] Liu et al. (2018)). We thus hope to improve upon LLP by identifying methods of label propagation that can take advantage of global structure while remaining scalable.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alexis Conncau, Holger Schwenk, Lote Barrault, and Yann Lecun. Very deep convolutional networks for natural language processing. arXiv preprint urXiv:1606.01781, 2, 2016.
Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. 2009.
Li Deng, Geoffrey Hinton, and Brian Kingsbury. New types of deep neural network learning for speech recognition and related applications: An overview. 2013 IEEE International Conference Acoustics, Speech and Signal Processing, pp. 8599 8603, IEEE, 2013.
Yves Grandvalct and Yoshua Bengio. Semi-supervised leamning by entropy minimization. In Advances in neural information processing systems. pp. 529-536, 2005.
Awni Hannun, Carl Case, Jared Casper, Bryan Catanzaro, Greg Diamos, Erich Elsen, Ryan Prenger, Sanjeev Satheesh, Shubho Sengupta, Adam Coates, al. Deep speech: Scaling up end-to-end speech recognition. arXiv preprint arXiv:1412.5567, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 201
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645. Springer, 2016b.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE international conference on computer vision. pp. 2961-2969, 2017.
Geoffrey Hinton, Li Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Brian Kingsbury, al. Deep neural networks for acoustic modeling in speech recognition. IEEF Signal processing magazine, 29, 2012.
Julia Hirschberg and Christopher D Manning. Advances in natural language processing. Science, (69644 261-266, 2015.
Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi-supervised learning. arXiv preprint arXiv:1904.00 04717, 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Ankit Kumar, Ozan Issoy, Peter Ondruska, Mohit Iyyer, James Bradbury, Ishaan Guirajani, Victor Zhong, Romain Paulus, and Richard Socher. Ask me anything: Dynamic memory networks for natural language processing. In International Conference on Machine Learning, pp. 1378-1387, 2016.
Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on Challenges in Representation Learning, ICML, volume 3. pp. 2013.
Bin Liu, Zhirong Wu, Han Hu, and Stephen Lin. Deep metric transfer for label propagation with limited annotated data. arXiv preprint arXiv:18/2.0877 2018.
Takeru Miyato, Shin-ichi Maeda, Shin Ishii, and Masanori Koyama. Virtual adversarial training: regularization method for supervised and semi-superrised learning. IEEE transactions on pattern analysis and machine intelligence, 2018
Kuniaki Noda, Yuki Yamaguchi, Kazuhiro Nakadai, Hiroshi G Okuno, and Tetsuya Ogata, Audio-visual speech recognition using deep learning. Applied Intelligence, 42(4):722-737, 2015.
Siyuan Qiao, Wei Shen, Zhishuai Zhang, Bo Wang, and Alan Yuille. Deep co-training for semi-supervised image recognition. In Proceedings of the European Conference Computer Vision (ECCV), pp. 135-152, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1xXiv:1409.155 1556, 2014.
Antt Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results. In Advances in neural information processing systems, pp. 1195-1204, 2017.
Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li. 100m The new data in multimedia research. arXiv preprint 153.v::500001 2015.
9

---

Under review as a conference paper at ICLR 2020
Zhirong Wu, Alexei A Efros, and Stella X Yu. Improving generalization via scalable neighborhood component analysis. In Proceedings of the European Conference Computer Vision (ECCV), pp. 685-701, 2018a.
Zhirong Wu, Yuanjun Xiong. Stella X Yu, and Dahua Lin. Unsupervised feature learning via non non-parametric instance discrimination. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 3733-3742, 2018b.
Qizhe Xie, Zihang Dai, Eduard Hovy, Minh Minh-Thang Luong, and Quoe Le. Unsupervised data augmentation for consistency training. arXiv preprint arXiv:1904. 12848, 2019.
Zeki Yalniz, Hervé Jégou, Kan Chen. Manohar Paluri, Dhruv Mahajan. Billion-scale cuni-supervised learning for image classification. arXiv preprint arXi: (tti:1905.00000 2019.
Tom Young, Devamanyu Hazarika, Soujanya Poria, and Erik Cambria. Recent trends in deep learning based natural language processing. ieee Compitational intelligenCe magazine, 13(3):55-75 75, 2018.
Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S41: Self-supervised semi-supervised learning. arXiv preprint Xrv:: 0367000 2019.
Bolei Zhou, Agata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva. Learning deep features for scene recognition using places database. In Advances in neural information processing systems, pp. 487-495, 2014.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in neural information processing systems, pp. 321-328, 2004.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. Technical report, Citeseer, 2002.
Chengxu Zhuang, Alex Lin Zhai, and Daniel Yamins. Local aggregation for unsupervised learning of visual embeddings. arXiv preprint 1903. 2019.
10

---

Under review as a conference paper at ICLR 2020
A IMAGENET EXPERIMENT DETAILS
Following Wu et al. (2018b) Zhuang et al. 2019). r 0.07 and D = 128. Optimization uses SGD with momentum of 0.9, batch size of 128, and weight-decay parameter À 0.0001. Learning rate is initialized to 0,03 and then dropped by a factor of 10 whenever validation performance saturates. Depending on the training regime specifics (how many labelled and unlabelled examples), training takes 200-400 epochs, comprising three learning rate drops. After that, the learning rate is increased to 0.003 and dropped for two more times as a "relearning" phase. This additional phase can take around 200 more epochs. During training, pseudolabels are updated every step for the current examples after the gradient updates. The density estimate p(v;) recomputed for labelled images at once at the end of every epoch. For the network architectures, alongside the standard softmax categorization layer to generate the embedding output. Although the aggregation loss requires the computation of Plv), which involves getting the dot product results of v and all vectors stored memory bank, we find this operation can be efficiently executed through GPUs, which makes the noise-contrastive estimation in Wu et al. (2018b) unnecessary. Our algorithm only adds a little extra computation time compared to purely supervised training regime. As reference, ResNet-1 18ve trained two Titan-Xps requires around 10 days to be fully-trained after 400 epochs. This time can be further reduced to less than one week through using NVIDIA DALI preprocessing library. We use DALI for all of our main experiments except those with p
add additional fully connected layer
B IMAGENET + YFCC100M EXPERIMENT DETAILS
To select images that are more similar ImageNet, we apply a LLP trained ResNet-18 model on ImageNet with 10% labels to each image, predict its class confidence score, and retain P classes with highest scores for this image. Then for each class, we select the top images by confidence. Following Yalniz et al. 2019), we set P = 10. K is heuristically set to be 500, based the explorations done Yalniz et al. (2019). more thorough parameter search on and may lead to even better results than reported here.
For the fine-tuning process, we take the fully trained models and restart the LLP training with learning rate 0.003. We then keep the training for two more learning drops.
C PLACES205 EXPERIMENT DETAILS
Learning rate is initialized at 0.01 and dropped by factor of 10 whenever validation performance on Places205 saturates. Training requires approximately 500,000 steps, comprising two learning rate drops.
D PROPAGATION THE SMALL-DATASET REGIME
ImageNet subsets constructed through randomly sampling 50 categories from ImageNet and 50 images from each category. For each category selected, we choose images to be labelled. For all methods, embedding outputs of our trained ResNet-50 with p 10 data features.


Reviews:
[{"review_id": "rkxJ5NAgqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a local label propagation approach for large-scale semi-supervised learning. The approach learns a representation that tries to minimize a combination of the cross-entropy loss on the labeled data and a negative inner-product-based likelihood between the propagated pseudo-label and other examples with the same true label. The pseudo-labels on the unlabeled data are then calculated with a weighted k-NN scheme, where the weights take a heuristic correction of a soft similarity. Some further computational speedup is done with a memory cache described in an earlier work (Wu 2018b). Experimental results seem significantly superior to the competitors. The design choices are mostly justified with ablation studies.\n\nThe whole idea is interesting and the results are promising. From the current manuscript, my remaining concerns are\n\n(1) How much contribution has readily been done by (Wu 2018a, b), and how much is the original design of the authors? From Section 3 (and without reading (Wu 2018a, b)), I cannot find a clear answer to this question. Currently it appears that the additional contribution over Wu's works is marginal.\n\n(2) It is not clear to me how the proposed approach reaches the asserted efficiency over global label propagation approaches. In particular, each P(v_i)*Z in Equation (2) is O(N) to compute. Each w_j(v) in Equation (5) is O(K) to compute after getting all P(v_i)*Z, and then there are N (or at least N-M) such w_j(v) needed. So the total complexity is naively O(N (N-M) K). Even ignoring the K as a small constant, I cannot see how LLP is O(NM). Some running time profiling of LLP versus global LP might be helpful.\n\n(3) For label propagation methods, it is important to understand whether the pseudo-labels are accurate and/or whether the methods might be mis-guided by the pseudo-labels. Is there any evidence on whether the pseudo-labels are accurate (absolutely, or with respect to the confidence)?\n\n(4) For hyper-parameter selection, there is a \"Learning rate is initialized to 0.03 and then dropped by a factor of 10 whenever validation performance saturates.\" But it is not clear how the validation set is formed, and what performance is measured. Is it a performance based on a labeled validation set (and if so, how large is the set) or unlabeled one?\n\nI read the rebuttal. While it does not change my assessment, I thank the authors for clarifying some issues.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygZ1_JaFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces an approach for semi-supervised learning based on local label propagation. The idea is to leverage the geometric structure in the embedding space, such that data near to each other in the embedding space should have the same labels. The labels of the K-nearest labeled examples are weighted to form the propagated pseudo label of the data point. And the objective aims to match the propagated pseudo label and the predicted label from the classification model. An extra term is added to the objective to force data points with similar pseudo labels to get close to each other in the embedding space. The local propagation strategy makes the method scalable compared to similar methods in the literature. The method is tested on different experimental setups and show superior performance than the state of the art baselines. \n\nI like the idea of learning a consistent embedding space for prediction and label propagation seems interesting and novel to my knowledge. However, the paper uses the technique of local aggregation in [2] to replace the label propagation in [1], which makes it less novel.\n\nAlso, the experiments seem to be extensive with additional analysis to the behavior of the proposed method. I noticed that the authors used the unsupervised training proposed in [2] for the first 10 epochs. I wonder how important it is to have this initialization and would like to see ablation studies on whether using this as initialization or not.\n\n[1]Iscen, Ahmet, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. \"Label propagation for deep semi-supervised learning.\" In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5070-5079. 2019\n[2]Zhuang, Chengxu, Alex Lin Zhai, and Daniel Yamins. \"Local aggregation for unsupervised learning of visual embeddings.\" arXiv preprint arXiv:1903.12355 (2019).", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeRWfSG9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper discusses a new strategy for deep semi-supervised learning that seems related to the deep label propagation method of Iscen et al. 2019, but is more scalable and has a different loss function. \n\nEach example is associated with a representation vector v_i and a label y_i. The authors' approach essentially works by alternating between two steps:\n\n(1) Representation learning: Updating the v_i (and other model parameters) where the loss is an addition of two terms: \n-standard supervised loss\n-term that encourages points with similar labels to have similar v_i\n\n(2) Label Propagation: Uses the representations v_i to compute nearest neighbors and propagate labels. The authors approach takes O(NM) where N is total number of points and M is number of labeled points and can be parallelized to O(NM/P).  This is in contrast to Iscen et al. 2019 which takes O(N^2). \n\nExperiments show that the authors' approach performs consistently better on ImageNet than existing approaches. With suboptimal preprocessing, it also performs comparable / slightly better than UDA (Xie et al. 2019) (The authors speculate it could do better with the preprocessing that UDA uses)\n\nI am not from this area but found the paper well written and easy to understand. \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces an approach for semi-supervised learning based on local label propagation. While reviewers appreciate learning a consistent embedding space for prediction and label propagation, a few pointed out that this paper does not make it clear how different it is from preview work (Wu et al, Iscen et al., Zhuang et al.), in addition to complexity calculation, or pseudo-label accuracy. These are important points that weren’t included to the degree that reviewers/readers can understand, and reviewers seem to not change their minds after authors wrote back. This suggests the paper can use additional cycles of polishing/editing to make these points clear. We highly recommend authors to carefully reflect on reviewers both pros and cons of the paper to improve the paper for your future submission. 

Decision: Reject