Shuffle to Learn: Self-supervised learning from permutations via differentiable ranking
Authors: Andrew N Carr
Quentin Berthet
Mathieu Blondel
Olivier Teboul
Neil Zeghidour
Venue:  (2021)

Abstract: Self-supervised pre-training using so-called "pretext" tasks has recently shown impressive performance across a wide range of tasks. In this work we advance self-supervised learning from permutations, that consists in shuffling parts of input and training a model to reorder them, improving downstream performance in classification. To do so, we overcome the main challenges of integrating permutation inversions (a discontinuous operation) into an end-to-end training scheme, heretofore sidestepped by casting the reordering task as classification, fundamentally reducing the space of permutations that can be exploited. These advances rely on two main, independent contributions. First, we use recent advances in differentiable ranking to integrate the permutation inversion flawlessly into a neural network, enabling us to use the full set of permutations, at no additional computing cost. Our experiments validate that learning from all possible permutations (up to $10^{18}$) improves the quality of the pre-trained representations over using a limited, fixed set. Second, we successfully demonstrate that inverting permutations is a meaningful pretext task in a diverse range of modalities, beyond images, which does not require modality-specific design. In particular, we also improve music understanding by reordering spectrogram patches in the frequency space, as well as video classification by reordering frames along the time axis. We furthermore analyze the influence of the patches that we use (vertical, horizontal, 2-dimensional), as well as the benefit of our approach in different data regimes. 

Under review as a conference paper at ICLR 2021
SHUFFLE TO LEARN: SELF-SUPERVISED LEARNING FROM PERMUTATIONS VIA DIFFERENTIABLE RANKING
Anonymous authors Paper under double-blind review
ABSTRACT
Self-supervised pre-training using so-called "pretext" tasks has recently shown impressive performance across a wide range of tasks. In this work, we advance self-supervised learning from permutations, that consists in shuffling parts of in- put and training model to reorder them, improving downstream performance in classification. To do so, we overcome the main challenges integrating permu- tation inversions (a discontinuous operation) into an end-to-end training scheme, heretofore sidestepped by casting the reordering task as classification, fundamen- tally reducing the space of permutations that can be exploited. We make two main contributions. First, we use recent advances in differentiable ranking to integrate use the
the permutation inversion flawlessly into neural network, enabling full set of permutations, at no additional computing cost. Our experiments validate that learning from all possible permutations improves the quality of the pre-trained representations over using a limited, fixed set. Second, we successfully demon- strate that inverting permutations a meaningful pretext task in a diverse range of modalities, beyond images, which does not require modality-speciiff design. In particular, we improve music understanding by reordering spectrogram patches in the fime-frequency space, as well as video classification by reordering frames along the time axis. We furthermore analyze the influence of the patches that we use (vertical, horizontal, 2-dimensional), well as the benefit of our approach in different data regimes.
INTRODUCTION
Supervised learning has achieved important successes on large annotated datasets (Deng et al., 2009; Amodei et al., 2016). However, most available data, whether images, audio, or videos are unlabelled. For this reason, pre-training representations in an unsupervised way, with subsequent fine-tuning on labelled data, has become the standard to extend the performance of deep architectures to applica- tions where annotations are scarce, such as understanding medical images (Rajpurkar et al., 2017), recognizing speech from under-resourced languages (Rivière et al., 2020; Conneau et al., 2020), or solving specific language inference tasks (Devlin et al., 2018). Among unsupervised training schemes, self-supervised learning focuses on designing proxy training objective, that requires no annotation, such that the representations incidentally learned generalize well to the task of inter- est, limiting the amount labeled data needed for fine-tuning, Such "pretext" tasks, term coined by Doersch et al. (2015), include learning to colorize an artificially gray-scaled image (Larsson et al., 2017), inpainting removed patches (Pathak al., 2016) or recognizing with which angle an original image was rotated (Gidaris et al., 2018). Other approaches for self supeevupervii include classification to original images after data augmentation (Chen al., 2020) and clustering (Caron al., 2018).
In this work, we consider the pretext task of reordering patches of an input, first proposed for images by Noroozi & Favaro (2016), the analogue of solving jigsaw puzzle. In this setting, we first split an input into patches and shuffle them by applying random permutation. We train a neural network to predict which permutation was applied, taking the shuffled patches as inputs. We then use the inner representations learned by the neural network as input features to low-capacity supervised classifier (see Figures and 2 for illustration). We believe that permutations provide promising avenue for self- supervseeei learning, as they conceptually general enough to be applied across large range of modalities, unlike colorization (Larsson et al., 2017) or rotations (Gidaris et al., 2018) that are specific to images. The idea of using permutations was also explored in Santa Cruz et al.

---

Under review as a conference paper at ICLR 2021
"teee
"cartoon"
Took
TTesk
Upstream reordering task
Downstream tasks
Figure I: Permutations as a self-supervised technique can handle a variety modalities with mini- mal changes the network architecture. Dotted layers indicate weight sharing across input patches. The learned embeddings can be used for several downstream tasks. The inputs for the upstream task permuted, while the inputs for the downstream task are not.
(2018) where they use bi level optimization scheme which leverages sinkhorn iterations to learn visual reconstructions. Their method resorts to approximating the permuation matrix with such continuous methods. Our method relies all possible permutations. Moreover, the encouraging results of Noroozi & Favaro (2016) when transferring learned image features for object detection and image retrieval inspire to advance this method step forward. However, including permutations into an end-to-end differentiable pipeline challenging. permutations this issue by using a fixed set of permutations and casting the permutation prediction problem as classification one. Given that the number of possible permutations of patches is n!, this approach cannot scale to exploiting the full set of permutations, even when n is moderately small.
such approximations and can efficiently represent
discontinuous operation. Noroozi & Favaro (2016) circumvent
In this work, leverage recent advances in differentiable ranking (Berthet al., 2020; Blondel et al., 2020b) to integrate permutations into end-to-end neural training. This allows us to solve the permutation inversion task for the entire of permutations, removing a bottleneck that was heretofore sidestepped in manners that could deteriorate downstream performance. Moreover, we successfully demonstrate for the first time the effectiveness of permutations multiple modalities with minimal modality-specific adjustments. In particular, we improve music understanding by learning to reorder spectrogram frames, over the time and frequency axes. also improve video understanding by reordering video frames along time.
a pretext task on
To summarize, we make the following two contributions.
We integrate differentiable ranking into end-to-end neural network training for representation learning. This provides efficient manner to learn reordering tasks for all permutations, for larger numbers of patches. We show that this drastic increase in the number of permutations improves the quality of learned representations for downstream tasks.
We successfully demonstrate for the first time the effectiveness of permutations general pur- pose self-supervision method, efficient on multiple modalities with extremely minimal modifi- cations to the network. Additionally, the pre-trained representations perform well across diverse
2

---

Under review as a conference paper at ICLR 2021
(.91
upstream
6.7
task
4.6
Original image
permutation label y (4.722.0..3.8...))
encoder
downstream tasks
upstream
ranking loss
Figure 2: Data processing and upstream training procedures. All permutations are sampled on the fly, during training. To obtain embeddings reusable for downstream tasks, truncate the network by removing the last few layers. This truncation depends on the task and explained in Section 3.
tasks of the same modality. We purposefully divert from domain-specifia transformations, of- ten inspired by data augmentation techniques, as predicting the permutation applied input patches is not restricted either domain, nor modality or dimensionality. This also creates opportunities for applications beyond the scope of what we illustrate our work.
The rest of the paper organized as follows. In Section we present the problem formulation and the methods used. In Section 3 we demonstrate the effectiveness of our experiments audio, video, and image tasks. Further details can be found in the Appendix.
2
METHODS
2.1 GENERAL METHODOLOGY
To efficiently leverage the existence of large amounts of unlabeled data, we present self-supervised pretext task that predicts the permutation applied to patches of input. We do so manner that removes existing bottleneck, and allows to use all possible permutations targets during training. This pretext task performed upstream and the internal representation learned by the pretext neural network can then be transferred and used secondary downstream tasks
Figures 1 and 2.
In the upstream task, for each data point, n patches, sub-parts æ1...., 2n of of identical dimensions d are extracted. Their exact structure depend naturally on the modality: e.g. horizontal bands of an image, frequency bands spectrogram, frames video. Accordingly, the dimensions in d can represent height, width, channels, etc. These patches are then permuted randomly, and organized in a tensor X; of dimension d (see Figure 2), which is paired to the applied permutation as label y: (see Section 2.2 for details on permutation encoding).
We then train the weights w of a neural network to minimize the loss between its output far (X;), of size n, and the encoding Y/ E IR" of the permutation applied to the patches (see Figure 2). Note that the last operation of the network is differentiable ranking operator y This operator, the encoding of the permutations for the labels, and the loss used in this upstream task are detailed in Section 2.2 below. The network, and the details of the data- nata-processing pipeline generating the patches, are detailed in Section 2.3.
After upstream training on the initial dataset, the upstream network weights can be used to generate representations. By truncating the network, removing some of the last layers, we can extract an embedding of any input vector. These representations can be used in downstreum task to train new network, with its own weights, minimizing a loss (typically classification or regression) between its output and the downstream task labels (see Figures and 2).
We mostly evaluate our methods on downstream performance: the accuracy after training of the downstream network, reordering task can be of interest in and of itself, as in learning-to-rant problems (Liu, 201 1), and also report generalization performance in this task.
task that is unknown during upstream training. However, the pretext
As an aside, in the Jigsaw puzzle reassembly task, Noroozi & Favaro (2016) show that the choice of permutation matters when it comes to performance. They make of the Hamming distance
3

---

Under review as a conference paper at ICLR 2021
choose a permutation set that it maximally separated. This permutation set is diverse but is not close to covering the entire permutation space. By supporting the full set of permutations, our approach does not suffer from this issue.
The downstream tasks are dataset detanet-dependent. However, the network in the upstream reordering task requires minimal modification across tasks and modalities (see Section 3 for details). In this work, we demonstrate the effectiveness of our method on audio, video, and images, across several classification and regression tasks.
2.2 DIFFERNTTAALEY RANKING METHODOLOGY
Our methodology for representation learning relies importantly on the ability to incorporate ordering or ranking operations in an end-to-end differentiable pipeline. During training for the upstream task, the last two layers of the network consist of: a vector of score values O. (X) E IR", and network outputs (X) = vE (X)) E RR", using differentiable ranking operator v that we detail here. The goal of the upstream task is to find good parameters w such that the network outputs fw (X) correctly recover the label y representing the permutation applied to the patches in X.
In earlier works using permutations as pretext task (Noroozi & Favaro, 2016; Lee et al., 2017), train- ing with permutation labels is achieved by reducing the permutation inversion task to classification. More specifically, it is encoding a fixed number of permutations I, < n!! as classes. Each class is represented by a one-hot vector, and network outputs are logits (x) of size L, leading to a predic- tion by taking softmax among these L classes. This approach is obviously limited: representing all the permutations requires in principle n! classes, which is quickly not manageable, even for small values of n. Further, this does not take into account the similarity between permutations: with this encoding, permutations are orthogonal, no matter how similar they are.
We address these issues by having network outputs 0u (x) of size only n, and interpreting their relative orders as the predicted permutation (e.g. y (0, 1, 2, 3) if they are in decreasing order, predicting the identity permutation). The pretext labels also encode the permutations in this manner. This gives unique encoding to each permutation, operates in dimension n. and can be computed with sorting operations in time (n log nt). Further, small distances in these encodings naturally represent similar permutations.
However, applying directly ranking operator y on the last layer of the network would not allow for backpropagation of gradients: the function of the weights w + Lyy (0 (Ox))) is piece-wise constant. Small changes in the weights w induce either large jumps or no change in value at all, its gradients are 0 almost everywhere, and undefined otherwise. In order to overcome this matter, we consider instead two differentiable ranking operations, one using stochastic perturbations, intro- duced in Berthet et al. (2020) and another one using regularization (Blondel et al., 2020b). These operations, denoted here by y.. map any vector of values to a point in the convex hull of per- mutation encodings in dimension l (c.g. (0.1, 0.9, 2.2, 2.8) over 4 elements). They be thought of analogous to the softmax operator for ranking. They share some of its properties: good approx- imation of the original function, differentiability in the input values 0 with non-zero derivatives everywhere, ease of computation, and tuning by a temperature parameter E (see Appendix A. for further details).
Adjusting the network parameters to requires a notion of loss function between y (0) and y. For the version of y: (0) based stochastic perturbations (Berthet et al., 2020), we use the associated Fenchel- Penchel-Young loss (Blondel et al., 2020a), that act directly on 0 = e. (X) (outputs of the vector, and inputs of the sorting operations). written here as LFY y) (see Appendix A.I). This loss is convex in 0 smooth, equal to 0 if and only if (0) y. Its gradients are given by V V VeLFY (0; = y2 (0) y. We call this loss "Perturbed F-Y" in our empirical results. For the regularized version of (0) (Blondel et al., 2020b), we use
2 vz (8) 2/
We call this loss "Fast Soft Ranking (FSR)" in our empirical results. We opt for these two losses for their good theoretical properties and O(n l) complexity. Other choices (Mena et al., 2018; Cuturi et al., 2019; Vlastelica et al., 2019; Rolínek et al., 2020; Grover et al., 2019) are also possible, potentially with higher computational cost, or regions with zero gradient.
4

---

Under review as a conference paper at ICLR 2021
2.3 IMPLEMENTATION AND ARCHITECTURE
Pata-processing When constructing the self-supervised task, inputs that can be treated as images (i.e. with width and height) are sliced into patches. This slicing controlled by two variables nh and By. determining respectively the number of columns and rows used. In Noroozi & Favaro (2016), 9 square patches are used. Across modalities. different slicing scheme can lead to better performance. In video analysis, there is only one axis along which to permute: time. In audio processing, the downstream task may benefit from the pretext task using frequency slices of the spectrogram instead of time slices (see Figure for illustration). We explore these questions Section 3.
Upstream task. For the reordering pretext task, performed upstream, we use a Context Free Net- work (CFN) from Noroozi & Favaro (2016). This network uses an AlexNet (Krizhevsky al., 2012) backbone which processes each patch individually while sharing weights across all patches as shown in Figure By processing each patch independently, but with shared weights, the network cannot rely on global structure. After the shared backbone, the patches are passed together through two fully connected layers. The layer represents the predicted ranks of the input permutation. Although CFN was originally designed for images, one of our empirical contributions is to show its applica- tion a number of separate modalities without any change to the training mechanism (Figure 1). In particular, we show important performance gains on audio tasks.
Downstream task. For the downstream task, we use classifiers with low capacity: a 3-layer multi- layer perceptron (MLP) for audio and video task, and linear classifier for images. It is trained on embeddings extracted at the first aggregate fully connected layer of the pretext network (whose weights frozen during this part). The MLP's output layer is task dependent. For regression downstream task, the output of the MIP is a single scalar and the downstream model is trained to minimize mean-squared error. On the other hand, for downstream classification task, the output of the MLP is softmax over the class logits, and we train the downstream model by minimizing the cross-entropy between the predictions and the true labels.
EXPERIMENTS
In this section, we demonstrate the effectiveness of permutation-basse self-supervised learning as measured by the test accuracy in downstream tasks across several modalities. All experiments were carried out Tensorflow (Abadi et al., 2016) and run on single P100 GPU. For all modalities, in addition to the downstream task, we also report the performance on the upstream task using partial ranks, the proportion of patches ranked in the correct position. We will open-source our codebase for reproducibility and reusability.
3.1 AUDIO
Experimental setup. The NSynth dataset (Engel et al., 2017) offers about 300,000 audio sam- ples of musical notes, each with unique pitch, timbre, and envelope recorded from 1,006 different instruments. The recordings, sampled at 16kHz, are 4 seconds long and can be used for 3 down- stream classification tasks: predicting the instrument itself (1,006 classes) the instrument family (11 classes) and predicting the pitch of the note (128 classes). Since the pitch estimation is regression task, we report our results the mean squared error (MSE) for this task.
Audio processing systems usually take as input log-comper ce-ppeeeeee spectrogram of the recordings rather than the raw waveform, since it a convenient and compact time- frequeeyy representation of the input signal. Moreover, the 2D structure of the spectrogram allows us to use the 2D convolutional network as for images and videos.
We train our CFN with an AlexNet backbone on the upstream task of predicting the applied permu- tation for 1000 epochs, over mini batches of size 32 and with an Adam optimizer (Kingma & Ba, 2014) with a learning rate of 10-6, After convergence, we evaluate the downstream generalization performance over the NSynth tasks, by replacing the last layers of the network by a 3-layer MLP and replacing the random permutation by the identity. To understand the quality of the produced embeddings, we vary the number of examples used to train train the downstream task and report the results for different data regimes.
5

---

Under review as a conference paper at ICLR 2021
-6- Durs With Pretzaming
MSE With Pratrainingg
XE With Preizaining
Withuut Pratreiring
Instrument Family
Instrument Label
Pitch
0.9
0.8
accuracy
0.
MSE
0.0
0.5
0.2
200
0.4
0.0
1880
3000
5000
10000
1880
3000
5000
10000
1880
3000
5000
10000 0
# of data points
# of data points
# of data points
Figure 3: Performance of permutation-basee pretraining over 3 audio tasks when varying the
number of data points in the downstream task.
Task
Random Embedding
Fixed
Fast
Perturbed F-Y
MSE
Permutation Soft Ranking
Instr. Family (ACC)
0.46 +0.01
0.75 #0.02
0.84
0.85 =0.00 0.79 40.02
Instr. Label (ACC)
0.35 20.04
0.70 20:03
0.72 20.03
0.76 20.00
0.71
10.03
Pitch (MSF)
258.76 a3
144.48 218
133.85 119
124.6
114
156.08
#21
Partial Ranks Accuracy
0.57
0.58 #0.0 0.51 #0.0
Table 1: Performance on three downstream tasks with 1000 downstream data points taken from NSynth. ACC stands for accuracy, and MSE for mean squared error.
We compare the different variants of our method (number and nature of the patches) with 2 baseline alternatives: i) training the downstream architecture on an untrained encoder (referred to as Random Embedding) and ii) solving the same upstream task but using instead finite set of 100 permutations as proposed by Noroozi & Favaro (2016) (Fixed Permutation).
Lastly, we compare different losses to train the permutation pretext task: cross entropy (XE) when learning over 100 permutations, b) MSE loss (MSE), c) soft ranking via perturbations (Perturbed F- Y) and d) soft ranking (Fast Soft Ranking).
Empirical results. First, we compare the different methods for different data regimes in the down- stream task and report graphically the results in Figure choosing the accuracy for the classification tasks and MSE for the regression one. We observe that in the low data regime our method strongly outperforms fully supervised model trained end-to-end rather than a fixed embedding. More- over, even though the margin closes when adding more data, we observe that the features obtained greatly assist in the downstream learning process. We also observed that pretraining particularly impactful for pitch estimation which aligns with results found by Gfeller et al. (2020).
We report in Table the results for 1000 downstream examples (see 5 and in the Appendix A.2 for 500 and 5000). Those experiments were run using 10 frequency bands, which corresponds to 10! permutations. This number of potential classes discards the use of classification loss: from very practical point of view, such huge number of classes would create a weight matrix the last dense layer that would not in memory.
We first observe that random embeddings performs poorly but does represent good baseline to be compared to. Second, when training the encoder with the fixed set of permutations, we observe a significant increase in performance that confirms experimentally the results reported by (Noroozi & Favaro, 2016). In the first three rows of Table 1, we report the results of our methods in the downstream metrics. We first observe that even with a mean squared error loss, the performance

---

Under review as a conference paper at ICLR 2021
Downstream Instrument Label
Downstream Instrument Family
Downstream Pitch
0.7
0.8
700
0.6
0.5
500
0.5
400
Perturbed F-Y
300
Cross entropy
0.4
Cross entrapy
Parturbed F-Y
Purturbed F-Y
10
100
7
30
12
Namber of Eequericy bands (paiches)
Number of frequeecyy bands (pelchen)
Number of frequenccy bands (paiches)
Figure 4: Performance on the NSynth dataset's downstream tasks, function of the number of frequency bands used for the pretext task on the audio experiment. With lower number of patches, the upstream task can become too easy lead to good feature learning, risking overfitting.
Task
Frequency
Time
Lime-Frequency
Instr. Family (ACC) 0.82 =0.003
0.79 =0 004
0.73 =0 000
Instr. Label (ACC)
0.75 =0.01
0.68 =0 002
0.45 =0.01
Pitch (MSE) 136.68 112.03
206.11 47.09
137.81 213.02
Table Slicing biases on Nsynth downstream tasks.
on the downstream task is comparable better than the fixed permutation method and we show that using a ranking loss further increases the performance. Those results tend to confirm that i) permutation is an interesting pretext task, ii) considering all possible permutation helps building better representations and iii) the use of a ranking loss is the right choice of loss for such a task.
Furthermore, Fig.4 shows the effect of the number of frequency bands on the downstream perfor- mance. It shows that, as the number of permutations grows, the performance over the downstream task increases, providing better representations. However, eventually stops increasing or can even decrease the performance.
We report in the last row of Table 1 performance in the pretext task. Good performance on the downstream task is often connected to good performance on the pretext task. Here, we measure per- formance by the ability of the CFN network to reorder the shuffled inputs, reporting the proportion of items ranked in the correct position.
Time-frequency structure and permutations. Unlike images, the horizontal and vertical dimen- sions of a spectrogram are semantically different, respectively representing time and frequency. While Noroozi & Favaro (2016) only exploited square patches, experimenting with audio allows exploring permutations over frequency bands (horizontal patches), time frames (vertical patches) or square time-frequency patches, and comparing the resulting downstream performance Table reports a comparison between these three settings. Overall, shuffling along the frequency axis only is the best pre-training strategy. These results illustrate a particularity of the dataset: our inputs single notes, many of them having harmonic structure. In this context, learning the relation between frequency bands is meaningful both to recognize which instrument is playing, as well as which note (pitch). This also explains the poor performance of slicing along the time axis. Pitch is iime-independent characteristic, so the time structure is not relevant for this task. Moreover, musical notes have an easily identifiable time structure (fast attack and slow decay), which may make the task of reordering time frames trivial. We hypothesize that signals with a richer, non-stationary time structure, such as speech, would benefit more from shuffling time frames.
3.2 VIDEO
Experimental setup. Another modality where shuffling can assist learning is in video classifi- cation, as done by Lee et al. (2017). this case, instead of slicing single image with multiple patches, a time frame is treated as a patch and multiple frames are permuted. We sample these frames uniformly along the video, and use 20 frames. We experiment on the sameehing-sometthin dataset (Goyal et al., 2017), dataset of videos labelled with 174 actions. We choose this dataset as many labels incorporate information about the dynamics (e.g. "Pulling something from right to left"), that classification can be improved by learning the natural order of frames.
7

---

Under review as a conference paper at ICLR 2021
Task Fixed Permutation Perturbed F-Y Fast Soft Ranking MSE
(ACC) 0.13 1201
0.19 g0:c0
20
0.12 20
Partial Ranks
0.27 10.00
0.29
0.17
Table 3: Up and downstream performance for video experiments.
Task
Fixed
Perturbed F-Y FSR
MSE
Label 1000 (AUC Upper) 0.81 20.04 0.84 10.02
0.84 10.03 0.84 10.04
Label 1000 (AUC Lower)
0.80 +0.03 0.82 40.02
0.82 +0.04 0,82 +0.05
Label 3000 (AUC Upper)
0.83 #0.03
0.85 #0.02
0.85 #0.02 0.85 +0.02
Label -300 (AUC Lower) 0.82 #0.02 0.84 +0.02
0.84 #0.02 0.84 40.02
Partial Ranks
0. #0.02
0.14 #0.02 0.14 +0.03
Table 4: Upstream training on the ImageNet dataset with downstream task performance evaluated on Pascal VOC 2012 where performance is measured using Mean AUC.
Experimental results. We report in Table 3 results on self-supervised learning with permutations on frames of video. Competitive standards for fully supervised performance (using the whole video) on this dataset are around 0.65. Our method, with drastically reduced amount of training data (3000 videos, 1.4% of the dataset), operating on 20 frames, still reaches 0.21. Interestingly, when using fewer frames than 20, the downstream performance does not improve above random chance. Hence, scaling to more patches is required to in this setting, which makes using a fixed number of permutations challenging. This may explain the poorer performance of the Fixed Permutation baseline on this task, and points to permutations as a promising avenue of exploration for self- supervised learning on videos.
In addition to the potential for self-supervised learning, performance on permutation task itself is interesting in the context of videos. We also report experimental results on the upstream reordering task itself in Table 3. In this case, the permutations acts on 20 frames, with an order of 2.10 pos- sible permutations. Our results show that significant fraction of elements are correctly reordered, even though this particular permutation has in all likelihood not been observed during training.
interesting to note that the methods that perform best on the pretext task also generally perform best on the downstream tasks. For example, we observe that our methods get higher performance than the MSE on the Jigsaw puzzle reassembly task. Correspondingly, our methods also achieve higher performance on the downstream tasks.
3.3 IMAGES
Experimental setup. We also applied our methodology to images, using the ImageNet and Pascal VOC 2012 datasets. In this experiment, we trained our CFN network on 128 x 128 images with 3 x patches. We used learning rate of 10 batch size of 32, and the Adam optimizer. We trained the same CFN network the jigaw reassembly task using the ImageNet dataset. We then evaluated the quality of the embeddings via downstream classification task on the PASCAL VOC 2012 dataset. We use the mean AUC metric to measure performance of our method which is appropriate due to the nature of the Pascal VOC classification task.
Experimental results. Consistent with the other results, we find performance of the two differ- entiable ranks methods to be consistently higher than learning reordering with classification over fixed permutations, however performance is consistent with MSE although the differentiable rank- ing methods have slightly lower variance. Additionally, upstream network learns the permutation inversion task. The results in Table 4 show the efficacy of method 1000 and 3000 downstream data points.
highlight the efficiency with which the
8

---

Under review as a conference paper at ICLR 2021
4 CONCLUSION
We present in this paper a general self-supervised learning method that uses permutations to learn high-quality representations. We demonstrate that our method outperforms previous permutation learning schemes by incorporating fully differentiable ranking as a pretext loss, enabling us to take advantage of all n! permutations, instead of small fixed set. particular, we show significant improvements in low data regimes. We also demonstrate that our method can be applied seamlessly to improved downstream performance of several classification and regression tasks across audio, videos, and images.
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: system for large- scale machine learning. In 12th {USENIX) symposium operating systems design and imple- mentation ({OSDI) 16), pp. 265-283, 2016.
Dario Amodei, Sundaram Ananthanarayanan, Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, al. Deep speech End-to- end speech recognition in english and mandarin. In International conference machine learning, pp. 173-182, 2016.
Quentin Berthet, Mathicu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable perturbed optimizers. arXiv preprint (rXxx:0002.08676 2020.
Mathieu Blondel, André FT Martins, and Vlad Niculae. Learning with fenchel-young losses. Jour- nal of Machine Learning Research, 21(35):1-69) 2020a.
Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. arXiv preprint arXiv:2002. 08871, 2020b.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 132-149, 2018.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXiv:2002.05709, 2020.
Alexis Conneau, Alexei Baevski, Ronan Collobert, Abdelrahman Mohamed, and Michael Auli. Unsupervised cross-lingual representation learning for speech recognition. arXiv preprint arXiv:2006. 13979, 2020.
Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. In Advances in Neural Information Processing Systems, pp. 6861-6871, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 255. Ieee, 2009.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1rXiv:1810.04880. 2018.
Carl Doersch, Abhinav Gupta, and Alexei A Efros. Unsupervised visual representation learning by context prediction. Proceedings of the IEEE international conference on computer vision, pp- 1422-1430, 2015.
Jesse Engel, Cinjon Resnick, Adam Roberts, Sander Dieleman, Douglas Eck, Karen Simonyan, and Mohammad Norouzi. Neural audio synthesis of musical notes with wavenet autoencoders, 2017.
Beat Gfeller, Christian Frank, Dominik Roblek, Matt Sharifi, Marco Tagliasacchi, and Mihajlo Ve- limirović. Spice: Self-supervised pitch estimation. JEEE/ACM Transactions on Audio, Speech, and Language Processing, 28:1 18-1128, 2020.

---

Under review as a conference paper at ICLR 2021
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint 18X3::280..0778, 2018.
Raghav Goyal, Samira Ebrahimi Kahou, Vincent Michalski, Joanna Materzynska, Susanne West- phal, Heuna Kim, Valentin Haenel, Ingo Fruend, Peter Yianilos, Moritz Mueller-Freitag, et al. The "something something" video database for learning and evaluating visual common sense. In ICCV, volume 1, pp. 5, 2017.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. arXiv preprint arXiv: 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6990, 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Gustav Larsson, Michael Maire, and Gregory Shakhnarovich. Colorization as proxy task for visual understanding. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6874-6883, 2017.
Hsin Ying Lee, Jia-Bin Huang, Maneesh Singh, and Ming- Hsuan Yang. Unsupervised represen- tation learning by sorting sequences. In Proceedings of the IEEE International Conference on Computer Vision, pp. 667-676, 2017.
Tie-Yan Liu. Learning rank for information retrieval. Springer Science & Business Media, 2011.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel-sinkhorn networks. arXiv preprint 1802.08800006666 2018.
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European Conference on Computer Vision, pp. 69-84. Springer, 2016.
Deepak Pathak, Philipp Krahenbubl, Jeff Donahue. Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2536-2544, 2016.
Pranav Rajpurkar, Jeremy Irvin, Kaylie Zhu, Brandon Yang, Hershel Mehta, Tony Duan, Daisy Ding, Aarti Bagul, Curtis Langlotz, Katie Shpanskaya, al. Chexnet: Radiologist-level pneumo- nia detection chest x-rays with deep learning. arXiv preprint 17Xiv:1711.000 0.225, 2017.
Morgane Rivière, Armand Joulin,
Mazaré, and Emmanuel Dupoux. Unsupervised pretraining transfers well across languages. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 7414-7418. IEEE, 2020.
Michal Rolínek, Vít Musil, Anselm Paulus, Marin Vlastelica, Claudio Michaelis, and Georg Mar- tius. Optimizing rank-based metrics with blackbox differentiation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 7620-7630, 2020.
Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould. Visual permutation learning. IEEE transactions pattern analysis and machine intelligence, 41(12):3100-311 2018.
Marin Vlastelica, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolínek. Differentiation of blackbox combinatorial solvers. arXiv preprint arXiv: 191.0015 2019.
10

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A. DIFFERENTIABLE RANKING AND FENCHEL- YOUNG LOSSES
The differentiable operators for ranking that we consider map vector of values the convex hull of ranking vectors i.e. vector whose entries are 1 to n. This set C. is referred to as the permutahedron (see, e-g.. Blondel al. (2020b)). Both our approaches rely on the fact that for a vector 0 E IR", the vector of ranks of 0 in ascending order is given by
y (0) = arg max (y, 0)
The two variations on differentiable ranking that we introduce are based modifications of this formulation. The approach in Berthet et al. (2020) is to introduce random perturbations Z tuned by > 0 to the vector of values
ve (0) = E Blarg max I + =Z)].
VEC
Its value well its derivatives be approximated by Monte-Carle (MC) schemes (see Berthet et al., 2020, for details). In this work, we use a normal distribution for Z, and learning experi- ments 0.1 and average 10 MC samples. If denote by (0) the expectation of the maximum (rather than the argmax), and &Ω its Fenchel dual over TR", we also have that
y (0) arg max (y, 0) =[t(y))
yЕC
This is the approach favored in Blondel et al. (2020b), where the function 52 is not defined as the dual of an expectation, but instead as an explicit convex regularizer over C. In this paper, we use (yy) 2 || The corresponding Fenchel- Young loss (Blondel et al., 2020a), whose definition extends other problems than ranking, defined for such convex regularized problems by
LEY y) Fe( + e l(y) (0,y)
where we recall that F. = (=52)* (Fenchel dual). As described in the main text, its gradient over the parameter 0 given by
VOLFY(O; v (0) y
Stochastic gradients can therefore be obtained by Monte-Cario approximation, which we use to minimize this loss in this work.
A.2 ADDITIONAL EXPERIMENTAL RESULTS
Appendix Tables for additional information the audio task (see next page).

---

Under review as a conference paper at ICLR 2021
Task
Random Embedding Fixed Permutation Fast Soft Ranking Perturhed F-Y MSE
Instr. Family (ACC)
0.44
+0.04
0.64 +0.44
0.73 +0.05
0.71 =0.06
0.62 +0.05
Instr. Label (ACC)
0123 19.04
0.52 19.06
0.56
0.55 20.00
0.47 20.05
Pitch (MSE) 256.20
188.37
186.03
183.96
276.59
Performance three downstream tasks the NSynth dataset, with 500 downstream data points. ACC stands for accuracy, and MSE for mean squared error.
Table 5:
Task
Random Embedding Fixed Permutation Fast Soft Ranking Perturbed F-Y MSE
Instr. Family (ACC)
0.59
20.02
0.91 10.01
0.93 20.01
0.94 20.01
0.90 20.05
Instr. Label (ACC)
0.49
#0.04
0.89 #0.01
#0.01
0.91 =0.01
#0.01
Pitch (MSE)
251.44 15.36
83.71 18:38
97.98 _ 36
108.46 112.38
Table 6: Performance on three downstream tasks on the NSynth dataset, with 5000 downstream data points. ACC stands for accuracy, and MSE for mean squared error.
12


Reviews:
[{"review_id": "z-0dWMsSkki", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper proposes to use differentiable ranking techniques to predict correct permutations. It can be applied to audio, video and images. It is quite obvious from the experiments that using differentiable ranking is more powerful to learn representations compared to fixed permutation in various applications.\n\nStrengths:\n\n- The idea is interesting and general to apply to different modalities.\n- It is well written and easy to follow.\n\nConcerns:\n\n- Lack of comparison with state-of-the-art methods. \n- In downstream tasks, there are always labels available, it is common to test on unsupervised setting as well.\n- In Section 3.3, the experiment is conducted on MNIST, it would be more convincing to show results on larger datasets, since it is quite common to apply it on ImageNet. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7QDcoieE_bF", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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 applied differentiable ranking operator on unsupervised learning framework that uses permutation based pretext task. They evaluated the proposed approach in audio, video, and image classification tasks. The results show that the proposed differentiable ranking operator is showing better performance than the pre assigned fixed permutation.\n\nOverall, the contribution of the paper is limited in applying the soft ranking loss (or perturbed FY) on permutation based unsupervised learning framework. I think there can be two factors that can improve the performance of the proposed approach to the baseline approach (fixed permutation). The first one can be related to the soft ranking (or perturbed FY) loss itself (unlike the classification of permutation cases or regression) and the second one can be related to the use of the number of permutation cases. By using the the soft ranking type loss, they could tackle the latter factor by using any permutation cases in the training phase. However, to verify where the performance gain come from, the authors can make an another comparison that is based on classification type loss (classification on N! permutation cases). It may be hard to deal with extremely large number of class labels, but at least some comparison table can be added with small sub dataset to verify the distinction between the two factors.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-PTkDWBKfm", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a self-supervised learning task of shuffling input patches and demanding the network to learn to unshuffle. A related prior work, Noorozi and Favaro (2016) uses a fixed set of permutations to do this task for a given number of patches, and the current paper argues to expand this idea for the full set of permutations. To this end, the paper encodes a permutation as a number tuple, with the goal of the network to learn to produce the correct tuple that has the numbers in order. As the numbers are discrete and thus non-differentiable, the paper suggests differentiable soft-variants using stochastic perturbations and regularizations (Fenchel-Young loss). Experiments are provided on audio and video tasks and show promise over the method of Noorozi and Favaro (2016).\n\nPros\n1. A relatively simple self-supervised task with simple regularizations.\n2. Experiments show some promise. \n\nCons: \n1. Since the work of Noorozi and Favaro (2016), there have been several similar approaches to self-supervised learning that are not covered by the paper, either in the related work or in the experimental comparisons. A very reated work is \n[a] Visual Permutation Learning, Santa Cruz et al., TPAMI 2018\nthat attempts to tackle the very specific problem of fixed set of permutations used in Noorozi and Favaro (2016). They also propose an end-to-end neural network for solving the the permutation finding task. The paper should contrast against this work both technically and in experiments. \n\n[2] The experiments are rather weak in my opinion. As noted above, there are several prior papers (see the papers that cite the above paper) that attempts the unshuffling task in various ways, while the paper only makes comparison to the 2016 baseline paper. More recent baselines should be included in the comparisons and the advantages of the specific approach needs to be convincingly established. \n\nOverall, while the idea is interesting, the paper does not place its contributions within recent prior works.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is clear consensus on this submission. Reviewers cite a lack of comparison
with recent state-of-the-art methods and experiments on more realistic datasets.
Though the reviewers find aspects of the approach interesting, the decision is
to reject.

Decision: Reject