{'fraction_non_alphanumeric': 0.03694600199708119, 'fraction_numerical': 0.01808894692372686, 'mean_word_length': 4.419146722164412, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Data Transformation Insights in Self-supervision with Clustering Tasks

Self-supervision is key to extending use of deep learning for label scarce domains. For most of self-supervised approaches data transformations play an important role. However, up until now the impact of transformations have not been studied. Furthermore, different transformations may have different impact on the system. We provide novel insights into the use of data transformation in self-supervised tasks, specially pertaining to clustering. We show theoretically and empirically that certain set of transformations are helpful in convergence of self-supervised clustering. We also show the cases when the transformations are not helpful or in some cases even harmful. We show faster convergence rate with valid transformations for convex as well as certain family of non-convex objectives along with the proof of convergence to the original set of optima. We have synthetic as well as real world data experiments. Empirically our results conform with the theoretical insights provided.


Introduction
Labels are a scarce resource for prediction tasks especially when the labeling needs domain expertise to annotate data points. To address the label scarcity issue many machine learning practitioners have taken self-supervised learning (Yengera et al., 2018;Utsumi et al., 2019) approach. The idea is to create labels from the data points implicitly during the training phase of learning by learning robust feature representations (Hendrycks et al., 2019b). A common aspect of self-supervision is to add additional transformed data points to aid in the learning phase (Misra & van der Maaten, 2019;Tian et al., 2019;Ji et al., 2018). This has empirically shown to achieve high accuracy rates for a variety of machine learning tasks such as image recognition (Taha et al., Proceedings of the 37 th International Conference on Machine Learning, Vienna, Austria, PMLR 108, 2020. Copyright 2020 by the author(s). 2018; Singh et al., 2018), clustering (Caron et al., 2018a), classification (Qiu et al., 2009), few-shot learning (Gidaris et al., 2019), semi-supervised learning (Rebuffi et al., 2019), learning to rank (Liu et al., 2019) etc. Though, this aspect of self-supervision has not been studied well theoretically or empirically.
Self-supervision is a promising area of machine learning especially for prediction tasks where getting ground-truth labels is difficult or costly. In a self-supervised method, the learning approach is to get a robust representation learning of the feature set that also helps in implicit labeling (Hendrycks et al., 2019a). The robust feature representation learnt through this approach can be used as an embedding or other intermediate feature for downstream tasks (Halimi et al., 2018). Data augmentation through transforming the original data points have been found to be helpful in such representation learning tasks (Ji et al., 2018;Janner et al., 2017). There have been very few empirical works (Pal et al., 2019) and no theoretical work regarding the type of transforms that help in such representation learning schemes. This work is an attempt to fill this gap by providing empirical and theoretical analysis of data transformations applied to self-supervised representation learning for clustering tasks.
We take the clustering problem, solved via gradient descent schemes, as the main setup for our study. We show that certain set of transformations are helpful in convergence of the learning algorithm. Specifically, our contributions are: • Show that under positive self-supervision, optima remain the same after adding transformed data points to the clustering problem.
• Provide empirical and theoretical insight into the rate of convergence for convex clustering loss augmented with transformed data.
• Show theoretical and empirical evidence of higher rate of convergence to the optima for a sub-family of non-convex clustering loss under graduated descent. The earlier guarantees have been probabilistic in nature (Hazan et al., 2016) .
• Provide insights into the varying degrees of contribution of data transforms during different phases of the arXiv:2002.07384v1 [stat.ML] 18 Feb 2020 learning scheme in a clustering task.
• Contrast examples of bad transforms that harm the learning process while helpful transforms that aid the learning process.
We provide empirical results over synthetic as well as real world datasets under both-convex and non-convex settings. For non-convex settings we use deep learning based clustering method. Our empirical results confirm the theoretical insights we obtain. Arora et al. (2019) provide theoretical analysis of selfsupervision in approaches similar to word2vec embeddings where words closer to target words are treated as "positive" and words farther are treated "negative". The implicit positive and negative example words can be understood to be the self-supervised labels. Pal et al. (2019) provide empirical analysis of transforms in self-supervised image recognition tasks. They work with the hypothesis that transforms that produce data points that can not be predicted by current data points are helpful compared to transforms that produce data points that can be predicted using existing data points. They provide experimental results for CIFAR10, CIFAR100, FMNIST, and SVHN datasets. Wang et al. (2017) propose transitive invariance representation learning by building a graph of visually variant image of same instance. They use a Triplet-Siamese network exploiting this visual-variance graph and apply the learned representations to different recognition tasks. Tian et al. (2019) take image samples from two different distributions or views, and learn representations by contrasting incogurent and congruent views. They use mutual information as the loss objective and maximize the mutual information between similar views. This methods provides good gains on ImageNet (Deng et al., 2009) calssification accuracy as well as on STL10 dataset. Ji et al. (2018) provide a self-supervised classification approach by learning highly pure semantic clusters through maximizing the mutual information between a given image and its transform. They use common transforms such as cropping, rotation, shear etc. and show that maximizing mutual information between original image and its transform results in semantic clusters since the deep network is trained for robust representation learning. They show good gains on STL, CIFAR, MNIST, COCO-Stuff, and Potsdam datasets setting the state of the art for unsupervised clustering and segmentation. Taha et al. (2018) provide a scheme containing two parallel stacked deep learning architecture in a self-supervised setting for action recognition task. They feed the RGB frame to first tower-the spatial tower, and motion stream encoded using stack of differences into second tower-the motion tower.

Related Work
They show good gains on HMDB51, UCF101 and Honda Driving Dataset. Janner et al. (2017) propose image decomposition into underlying intrinsic images (or transforms) and combine them together using reconstruction loss to get robust intermediate representations. This self-supervised scheme is efficient in utilizing large scale unlabeled data for downstream knowledge transfer tasks. Narayanan et al. (2018) combine self-supervised scheme with small number of labels to get good accuracy for driver behavior detection task. Deep-Cluster (Caron et al., 2018a) proposes a scheme where the initial labels for the clustering task come from a k-means run over the data. Then the network learns a feature representation for the clustering task using these labels. This selfsupervised learning scheme extracts useful general purpose visual features resulting in better performance on ImageNet classification as well as standard transfer task.

Background and Definitions
Self-supervised representation learning in clustering is a popular task in machine learning (Sun et al., 2019;Zhang et al., 2019;Du et al., 2013). The clustering objective can be convex (Lashkari & Golland, 2008;Lindsten et al., 2011) as well non-convex (Ji et al., 2018;Janner et al., 2017). This section provides the mathematical setup for clustering loss and additional definitions to work with in case of nonconvex loss.

Problem Setting
The machine learning task is to cluster the given set of data points X ∈ R N ×d into k ∈ N clusters under a given distance metric D. F : R N ×d → R is the clustering objective function which is to be optimized. F may or may not be convex in the estimated parameters space W ∈ R d . X N ×d ∈ R N ×d are the data points where d is the feature dimension and N is the number of training samples. Given X and W , equation 1 below is our objective function to be optimized.
f i (W ) indicates that when optimizing for W each data point i is an additive component of the objective. Following this, the gradient of objective w.r.t. W is of additive form as expressed in equation 2.
With addition of transformed data points into the data sample, the objective function takes the form of equation 3, where g : R d → R d is the transform function and N are the number of transformed data points. We define Equation 4 gives the gradient updates for F + .
For the clustering task, let C i , i ∈ {1 . . . k} are the ground truth cluster centroids w.r.t. distance metric D. In typical self-supervised clustering schemes (Sun et al., 2019;Zhang et al., 2019;Du et al., 2013) adding transformed data points results in objective of form equation 3.

Definitions and Notations
The following definitions and notations will be primarily used for the non-convex clustering loss setting. The notations and definitions follow Hazan et al. (2016), but are modified appropriately to suit our self-supervised representation learning setting.
Notation: We use B, S to denote the unit Euclidean ball/sphere in R d , and also B r (w), S r (w) as the Euclidean r-ball/sphere in R d centered at w. For a set A ⊂ R d , u ∼ A denotes a random variable distributed uniformly over A.
Given a function f , w ∈ R d , and smoothing parameter δ δ-Smoothed Gradient Operator for f at w is defined as

Data Transformation -Analytical Insights
Building on the problem setting in the previous section, we analyze the clustering loss with added transformed data points in self-supervised representation learning. The analysis broadly consists of two parts: 1) convex clustering loss setting, and 2) non-convex clustering loss setting. Each of these subsections have specific set of assumptions independent of the other. We first discuss the global assumptions and theorems that are valid for both convex and non-convex settings.
Assumption 1-A. Positive Self Supervision: As defined in the section 3.1 given distance metric D, and ground truth cluster centroids C i , i ∈ {1 . . . k} : Informally, assumption 1-A implies that the transformed data point maintains the same class/cluster membership as the original data point.
Assumption 1-B implies that there is only one set of parameters W * that is the global optima. Theorem 4.1 (Unchanged Optima). Given assumptions 1- . . k} are cluster centroids, and W * and W * + are optima for objectives F (W ) and F + (W ) respectively then W * = W * + Theorem 4.1 above holds for all positive self-supervised representation learning cases with clustering tasks under assumptions 1-A and 1-B. The next subsection provides guarantees for learning under convex loss.

Convex Loss Settings
Under convex loss, self-supervised representation learning for clustering tasks has faster linear rate of convergence when augmenting the learning scheme with transformed data points. To arrive at this insight we make the following assumptions.
Informally, assumption 2-C implies that the transformed data points are such that the objective is more strongly convex in W than earlier data points. Lemma 4.1 below is used in the proof for Theorem 4.2.
Theorem 4.2 (Faster Convergence). Let assumptions 2-A, 2-B, and 2-C are true. Given initial parameter W 0 ∈ R d and 1 L ≥ η > 0, the iterates converge according to i.e. η = 1 L the iterates enjoy a linear convergence with a rate of (κ + µ)/L instead of µ/L for non-transformed objective F .
Algorithm 1 is a typical gradient descent algorithm for convex loss. Informally, theorem 4.2 states that adding data Query the gradient oracle at w t : Update: w t+1 ← (w t − ηg t ) end for Return: w T transforms that introduce strong convexity lead to faster convergence of algorithm 1 in positive self-supervised representation learning settings for clustering.

Strongly-convex Transform Example
We take the well studied convex clustering loss (Lindsten et al., 2011;Hocking et al., 2011;Sun et al., 2018) and use it to illustrate a real world transform that makes the objective more strongly-convex. The loss objective, Φ is: (12) w i ∈ R d are the cluster centroids and x i ∈ R d are the data. α i,j ∈ R and γ ∈ R are the hyperparameters. We show that the new transformed data points' function component has stronger convexity than the original data points' component (equation 3), and from lemma 4.1 we have the desired stronger-convexity guarantee on the objective. If the hessian of the loss (∇ 2 Φ) has all its eigenvalues (λs) bigger than the earlier loss then the objective is more strongly convex (Boyd & Vandenberghe, 2004). ∇ 2 i,j = ∂φ 2 /∂w i w j = γ j α i,j (w i − w j ), and ∇ 2 i,i = ∂φ 2 /∂w 2 i = 1 + γ j,j =i α i,j . The hessian can be rewritten as where I is identity, A is a diagonal matrix with A i,i = γ j α i,j , and B i,j = α i,j . To construct a valid transform let hyperparameter α can have only two values α 1 , α 2 where α 2 > α 1 . For any existing data point pairs (x i , x j ), assume α i,j = α 1 . We choose the transform g : R d → R d such that it maps x i → x k such that α i,k = α 2 and for any two transformed pair (x k , x l ) α k,l = α 2 . Using equation 13 we can show that ∇ 2 Φ g λ ≥ ∇ 2 Φ λ i.e. eigenvalues of ∇ 2 Φ g are greater than eigenvalues of ∇ 2 Φ. This gives us a valid transform.

Non-Convex Loss Settings
For non-convex setting, we only analyze those problem families that have a unique global optima. They can have multiple local optima but not multiple global optima which is formally captured by assumption 1-B. The other assumption for this case are listed below. Assumption 3-A. Lipschitz Smooth Gradient: This is same as assumption 2-B, though here function F + and F are non-convex.

Algorithm 2 GradOptTransformed
Input: input data X, decision set K Get the transformed data points X X + = {X, X } Choose w 1 ∈ K uniformly at random. Set δ 1 = diam(K) for m = 1 to M do // Perform GradDescent overF + δm Set shrinked decision set, Set gradient oracle forF + δm , Lemma 4.2. Assuming w ∈ R d , δ ≥ 0, and f is L-Lipschitz, GradOp as defined in 3.2 is an unbiased estimate for ∇f δ (w).
Lemma 4.2 informally implies that for all practical purposes of the proofs later, GradOp can be treated as a common gradient operation.

Lemma 4.3 implies that the locally smoothedF + δ can be broken into original and transformed components similar to its non-local counterpart (see equation 3).
Lemma 4.4. Given assumptions 1-B and 3-B, and for every δ > 0 let r δ = 3δ, and w * δ = arg min w∈KF + δ (w), then over B r δ (w * δ ),F + is (µ + κ)-strongly-convex Corollary 4.1. Theorem 4.2 combined with lemma 4.2 implies that in algorithm 2 for Corollary 4.1 states that each internal call to GradDescent in algorithm 2 takes T F + iterations. This fact will be used in the proof of main result for non-convexity, theorem 4.3.
Lemma 4.5. Consider M , K m and w m+1 as defined in Algorithm 2. Also denote by w * m the minimizer ofF + δm in K m . Then the following holds for all 1 ≤ m ≤ M : 1. The smoothed versionF + δm is (µ + κ)-strongly convex over K m , and w * m ∈ K m .
Theorem 4.3 (Non-Convex Convergence). Let ε ∈ (0, 1) and K be a convex set. Applying Algorithm 2, after T total rounds of total internal gradient updates, Algorithm 2 outputs a point w M +1 such that T total 2(ln 6/ ln 1.5) where w * is the global optima for F + .
The theorem above implies that algorithm 2 converges with a linear rate of (µ + κ) instead of µ when the transformed data points are added to the positive self-supervised learning scheme. Figure 1 shows example runs of algorithm 2 over an arbitrary function. The graphs of the function is plotted at different smoothing stages. As the δ values decrease the function gets less smoother and more bumpier revealing more local optima. A point to note is that the change in the optima from one δ to the next is within range δ/2 (assumption 3-B). Hence as seen in the figure 1, discovered optima (red ball) in each phase doesn't change by much.

Data Transform Effect on Learning Stages
Corollary 4.2. Theorem 4.2 combined with lemma 4.2 implies that in algorithm 2 the transform makes the objective F + converge much faster in the initial iterations of the learning scheme than the later i.e.
Corollary 4.2 implies that the transformed data points make the algorithm 2 much more faster in the initial phases than the later. This means that we can use the original and transformed data points in the first k outer iterations of the algorithm 2 in the training phase and then use only the original data points after that to save computation and still get a reasonable speedup.

Data and Experiments
We setup empirical experiments to verify our theoretical analyses for both convex and non-convex loss. We use the setup from Lashkari & Golland (2008) for our convex setting 1 . The objective loss is defined in equation 14 where x i ∈ R d are the data points, q j is the probability of x j being a centroid (cluster-center), and k is the total number of clusters. Our empirical results are reported on the objective in equation 14 with synthetic data. We set k = 4 (four clusters) and d = 2 (two dimensional data points), and cluster centroid coordinates as {(10, 20), (30,20), (20, 10), (20, 30)}. We add zero-mean Gaussian noise to the original data points and add them back as a positive self-supervised transform to illustrate the faster rate of convergence. We change the variance of the Gaussian to illustrate the effects of various transformations ("noisiness" in this case). We keep the optima fixed for the two objectives F and F + given the synthetic data. For various cluster settings we compare the number of iterations taken to converge by F and F + , while constraining the new optima to be close to the original optima by a pre-defined threshold.
For non-convex settings we use DeepCluster (Caron et al., 1 https://github.com/drumichiro/ convex-clustering 2018b). The objective loss for the framework is where x n are the data points, y n ∈ {0, 1} k corresponding labels with k possible classes, f θ is the deep learning (convnet) mapping with parameters θ. g w is the classifier with parameters w that takes feature representation f θ and predicts a class. is the final multinomial logistic loss. We take the opensource code for DeepCluster 2 and run it over random-10 ImageNet (ImageNet-10) data (Deng et al., 2012). We add rotation as a transform to the original data points and add them back to show its convergence impact. In every run of the experiment, we randomly choose 10 classes from ImageNet's original 1000 classes and train for getting representation of each image using DeepCluster algorithm. A point to be noted is that the transformed data points are only added to the training of feature representation extractor, and not to the logistic regression classifier which is the last layer of the deep learning network. This makes our results much more helpful in showing that the transforms are mostly helping the feature representation phase, whose output is an input to the final logistic layer. Learnt representations are used to train a multi-class classification model. We run each experiment four times and show the best accuracy of the model across these four runs. We use 1,300 images per class and for the transformed setup we add equally number of transformed images to the original data per class.

Empirical Insights
Our experimental results conform to the theoretical insights that we provide in the previous sections. We specifically show faster convergence for both convex and non-convex loss settings. Some data transforms are more help than others-in fact some of them harm the learning process as we will see later.   with original data takes around 1000 epochs to converge to global minima but clustering with noisy or transformed data points added at noise level 6 takes around 850 epochs. We also observe that not all transforms help in convergence. In figure 3 some transforms perform worse than the non-noise baseline, especially those with the noise variance between 0 and 6. This conforms to our analytical insight that strongly convex transforms are more helpful in the convergence.

Non-Convex Results
For non-convex case, our experimental results are based on the DeepCluster (Caron et al., 2018b) setup. We take image rotation as the transform. We add the transform only for the feature representation learning phase of DeepCluster. Given that our transformed setup outperforms the baseline non-transformed case, it is clear that the gains from transformation is mostly coming from feature representation learning. Figure 4 shows the number of epochs vs top-1 class classification accuracy on ImageNet-10 dataset. We see that for each epoch the transformed setup consistently outperforms the non-transformed setup. Another notable aspect is that the gains are much superior in the early epochs for transformed setup compared to later epochs which conforms to our corollary 4.2. The transformed setup has a faster convergence rate for top-1 class classification as seen in table 6.2. In fact though transformed setup has twice the number of data points, to reach the accuracy of 60%, baseline setup takes 43 epochs whereas transformed setup takes 2 epochs i.e. it is 21.5 times faster. The baseline never reaches accuracies of 65% or above for top-1 class classification.   Table 6.2 shows the number of epochs taken by transformed and baseline setups. Though transformed setup has twice the number of data points it is twice faster at reaching 91% accuracy. It is four and twenty nine times faster at reaching accuracies of 93% and 95% respectively. Transformed setup reaches an accuracy of 97% in 22 epochs whereas the baseline setup is unable to get there. This strongly suggests that valid transforms do help in reaching optima faster as reported in our analytical insights.
Overall the results imply that model which uses transformations consistently performs better than model that does not. The experiments conform to the theoretical insights obtained. It's a known fact that a well designed data augmentation or transformation significantly improves performance of deep learning (Dvornik et al., 2018). Dvornik et al. (2018) observe that randomly pasting objects in the image hurts the performance of the learning task unless the placement is contextual. We show that one possible and probable explanation is that the transformed data points are making the objective more strongly convex in the parameter space, as hypothesized. This then makes the transformation context and data dependent-i.e. transformations will be helpful or harmful based on the data points. Precisely which transforms are helpful and how much do they make the objective strongly convex, however is beyond the scope of the paper given this is the first theoretical work in this subject matter, as far as we know. We will extend this work along this direction in the extended version of the paper.

Conclusion
The aim of this work is to analyse the effect of transforms in representation learning in the context of self-supervision. We choose clustering as our objective. Our basic insightdata transforms that make the objective strongly convex are useful-implicitly acknowledges that a transform is helpful or harmful depending on the data context. Dvornik et al. (2018) make similar observations in their work and propose an explicit context model to predict whether an image region is suitable for placing a given image object. We also observe in figure 3 that not all transformations are helpful and in the worst case harmful for the learning task. Our analysis also states that transforms are more helpful in the initial phases of the learning process. We observe this phenomenon empirically as well. Hence it is a good idea to augment the learning process with data transforms in the beginning and remove it later to save computation costs. Our work, as far as we know, is the first attempt in self-supervised literature to understand the impact of data transformation in predictive learning, theoretically or empirically. There have been some work in recent times in representation learning to analyze the effect of implicit positive and negative labels in self-supervised settings (Arora et al., 2019). But No works analyzing data transformation effects on self-supervision.
The empirical and theoretical insights presented here open interesting venues of research. Analyzing what other family of transforms besides strongly-convex are helpful in selfsupervision is an important research question. We analyzed a subset of non-convex loss functions-those that obey σniceness. To extend this analysis to other non-convex objectives is worthwhile. Extending the data transformation effects from self-supervision to unsupervised or supervised approaches answers many interesting questions in machine learning. Proof. The proof is by contradiction. Assume that W * = W * + , in that case the centroids for objective F and F + are different since W * and W * + determine the respective optimal centroids and by assumption 1-B they are unique. But if centroids for objectives F and F + are different, it contradicts assumption 1-A. Hence W * = W * + .