{'fraction_non_alphanumeric': 0.04087696178267641, 'fraction_numerical': 0.008530010782317, 'mean_word_length': 4.438623924941361, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Supervising Unsupervised Learning

We introduce a framework to leverage knowledge acquired from a repository of (heterogeneous) supervised datasets to new unsupervised datasets. Our perspective avoids the subjectivity inherent in unsupervised learning by reducing it to supervised learning, and provides a principled way to evaluate unsupervised algorithms. We demonstrate the versatility of our framework via simple agnostic bounds on unsupervised problems. In the context of clustering, our approach can help choose the number of clusters, the clustering algorithm, and provably circumvents Kleinberg's impossibility result. Experimental results across hundreds of problems demonstrate improved performance on unsupervised data with simple algorithms, despite the fact problems come from different domains. Additionally, a deep learning algorithm learns common features from many small datasets across multiple domains.


Introduction
Unsupervised Learning (UL) is an elusive branch of Machine Learning (ML), including problems such as clustering and manifold learning, that seeks to identify structure among unlabeled data. UL is notoriously hard to evaluate and inherently undefinable. To make this point as simply as possible, consider clustering the points on the line in Figure 1 (left). One can easily justify 2, 3, or 4 clusters. As Kleinberg argues [6], it is impossible to give an axiomatically consistent definition of the "right" clustering. However, now suppose that one can access a bank of prior clustering problems, drawn from the same distribution as the current problem at hand, but for which ground-truth labels are available. In this example, evidence may favor two clusters since the unlabeled data closely resembles two of the three 1-dimensional clustering problems, and all the clusterings share the common property of roughly equal size clusters. Given sufficiently many problems in high dimensions, one can learn to extract features of the data common across problems to improve clustering.
We model UL problems as representative samples from a meta-distribution, and offer a solution using an annotated collection of prior datasets. Specifically, we propose a meta-unsupervised-learning (MUL) framework that, by considering a distribution over unsupervised problems, reduces UL to Supervised Learning (SL).
Clustering problem in isolation: Going beyond transfer learning [7] where problems have the same dimensionality or at least the same type of data (text, images, etc.), our framework can be used to improve UL performance for problems of different representations and from different domains. Empirically, we train meta-algorithms on the repository of classification problems from openml.org which has a variety of datasets spanning domains such as NLP, computer vision, and bioinformatics, among others. Ignoring labels, each dataset can be viewed as a UL problem. We take a data-driven approach to quantitatively evaluate and design new UL algorithms, and merge classic ideas like unsupervised learning and domain adaptation in a simple way. This enables us to make UL problems, such as clustering, well-defined.
Our model requires a loss function measuring the quality of a solution (e.g., a clustering) with respect to some conceptual ground truth. Note that we require the ground truth labels for a training repository but not for test data (where they may be impossible to acquire). We suppose that we have a repository of datasets, annotated with ground truth labels, that is drawn from a meta-distribution µ over problems, and that the given data X was drawn from this same distribution (though without labels). From this collection, one could, at a minimum, learn which clustering algorithm works best, or, even better, which type of algorithm works best for which type of data. The same meta-approach could help in selecting how many clusters to have, which outliers to remove, and so forth.
Our theoretical model is a meta-application of Agnostic Learning [5] where we treat each entire labeled problem analogous to a training example in a supervised learning task. We show how one can provably learn to perform UL as well as the best algorithm in certain classes of algorithms. Our work also relates to supervised learning questions of meta-learning, sometimes referred to as auto-ml [e.g. 12; 3], learning to learn [e.g. 14], Bayesian optimization [e.g. 11] and lifelong learning [e.g. 13; 2]. In the case of supervised learning, where accuracy is easy to evaluate, meta-learning enables algorithms to achieve accuracy more quickly with less data. We argue that for unsupervised learning, the meta approach offers a principled means of defining and evaluating unsupervised learning.
Our main contributions are as follows. We show how to adapt knowledge acquired from a repository of small datasets that come from different domains, to new unsupervised datasets. Our MUL framework removes the subjectivity due to rules or thumb or educated guesses, and provides an objective evaluation methodology for UL. We give algorithms for various problems including making an informed decision on the number of clusters, learning common features, choosing amongst clustering algorithms, and removing outliers. Finally, the debate on what characterizes right clustering has not made much headway since Kleinberg's impossibility framework [6] mainly owing to the subjectivity or "artifacts of specific formalisms" [15; 1]. We add a fresh perspective to this debate by designing a meta-clustering algorithm that circumvents the effect of these artifacts by learning across clustering problems, and thus makes good clustering possible.
We experiment with our supervised algorithms for choosing the number of clusters, the clustering algorithm, and the fraction of data to be discarded as outliers to improve the clustering performance. And in a completely different direction, we use deep learning to automate learning of features across problems from different domains and of very different natures. We show that these seemingly unrelated problems can be leveraged to improve average performance across UL datasets. In this way, we effectively unite many "small data" into sufficient "big data" to benefit from a neural network.

Learning Preliminaries
We first define agnostic learning, in general, and then define meta-learning as a special case where the examples are problems themselves. A learning task consists of a universe X , labels Y and a bounded loss function : Y × Y → [0, 1], where (y, z) is the loss of predicting z when the true label was y. A learner L : (X × Y) * → Y X takes a training set T = {(x 1 , y 1 ), . . . (x n , y n )} consisting of a finite number of iid samples from µ and outputs a classifier L(T ) ∈ Y X , where Y X is the set of functions from X to Y. The loss of a classifier c ∈ Y X is µ (c) = E (x,y)∼µ [ (y, c(x))], and the expected loss of L is µ (L) = E T ∼µ n [ µ (L(T ))]. Learning is with respect to a concept class C ⊆ Y X .
Definition 1 (Agnostic learning of C). For countable sets 1 X , Y and : Y ×Y → [0, 1], learner L agnostically learns C ⊆ Y X if there exists a polynomial p such that for any distribution µ over X × Y and for any n ≥ p(1/ , 1/δ), Pr T ∼µ n [ µ (L(T )) ≤ min c∈C µ (c) + ] ≥ 1 − δ. Further, L and the classifier L(T ) must run in time polynomial in the length of their inputs.
PAC learning refers to the special case when µ is additional assumed to satisfy min c∈C µ (c) = 0.
MUL, which is the focus of this paper, simply refers to case where µ is a meta-distribution over datasets X ∈ X and ground truth labelings Y ∈ Y. We use capital letters to represent datasets as opposed to individual examples. A meta-classifier c is a UL algorithm that take an entire dataset X as input, such as clustering algorithms, and outputs Z ∈ Y. As mentioned, true labels need only be observed for the training datasets -we may never observe the true labels of any problem encountered after deployment. This differs from, say, online learning, where it is assumed that for each example, after you make a prediction, you find out the ground truth.
For a finite set S, Π(S) denotes the set of clusterings or disjoint partitions of S into two or more sets, e.g., Π({1, 2, 3}) includes {{1}, {2, 3}} which is the partition into clusters {1} and {2, 3}. For a clustering C, denote by ∪C = ∪ S∈C S the set of points clustered. Given two clusterings Y, Z ∈ Π(S), the Rand Index measures the fraction of pairs of points on which they agree: where for clustering C, we define the distance function d C (a, b) to be 0 if they are in the same cluster, i.e., a, b ∈ R for some R ∈ C, and 1 otherwise. In our experiments, the loss we will measure is the standard Adjusted Rand Index (ARI) which attempts to correct the Rand Index by accounting for chance agreement [4]. We denote by ARI(Y, Z) the adjusted rand index between two clusterings Y and Z. We abuse notation and also write ARI(Y, Z) when Y is a vector of class labels, by converting it to a clustering with one cluster for each class label. We define the loss to be the fraction of pairs of points on which they disagree, assuming the clusterings are on the same sets of points. If, for any reason the clusterings are not on the same sets of points, the loss is defined to be 1.
In Euclidean clustering, the points are Euclidean, so each dataset X ⊂ R d for some d ≥ 1. In meta-Euclidean-clustering, one aims to learn a clustering algorithm from several different training clustering problems (of potentially different dimensionalities d).
Rand Index measures clustering quality with respect to an extrinsic ground truth. In many cases, such a ground truth is unavailable, and an intrinsic metric is useful. Such is the case when choosing the number of clusters. Given different clusterings of size k = 2, 3, . . ., how can one compare and select? One approach is the so-called silhouette score [9], defined as follows for a Euclidean clustering: where a(x) denotes the average distance between point x and other points in its own cluster and b(x) denotes the average distance between x and points in an alternative cluster, where the alternative cluster is the one (not containing x) with smallest average distance to x.

Meta-unsupervised problems
The simplest approach to MUL is Empirical Risk Minimization (ERM), namely choosing the unsupervised algorithm from some family C with lowest empirical error on training set T , which we write as ERM C (T ). The following lemma helps us solve several interesting MUL problems. The learning bounds imply a logarithmic dependence on |C|, as shown in the supplementary material.
Lemma 1. For any finite family C of unsupervised learning algorithms, any distribution µ over problems X, Y ∈ X × Y, and any n ≥ 1, δ > 0, where ERM C (T ) ∈ arg min c∈C T (Y, c(X)) is any empirical loss minimizer over c ∈ C.
Selecting the clustering algorithm/number of clusters. Instead of the ad hoc parameter selection heuristics currently used in UL, MUL provides a data-driven alternative. Suppose one has m candidate clustering algorithms and/or parameter settings C 1 (X), . . . , C m (X) for each data set X. These may be derived from m different clustering algorithms, or alternatively, they could represent the meta-k problem, i.e., how many clusters to choose from a single clustering algorithm where parameter k ∈ {2, . . . , m + 1} determines the number of clusters. In this section, we show that choosing the right algorithm is essentially a multi-class classification problem given any set of problem metadata features and cluster-specific features. Trivially, Lemma 1 implies that with O(log m) training problem sets one can select the C j that performs best across problems. For meta-k, however, this would mean choosing the same number of clusters to use across all problems, analogous to choosing the best single class for multi-class classification.
To learn to choose the best C j on a problem-by-problem basis, suppose we have problem features φ(X) ∈ Φ such as number of dimensions, number of points, domain (text/vision/etc.), and cluster features γ(C j (X)) ∈ Γ which might include number of clusters, mean distance to cluster center, and silhouette score (eq. 2). Suppose we also have a family F of functions f : Φ × Γ m → {1, 2, . . . , m}, that selects the clustering based on features (i.e., any multi-class classification family may be used): The above ERM F is simply a reduction from the problem of selecting C j from X to the problem of multi-class classification based on features φ(X) and γ(C 1 (X)), . . . , γ(C m (X)) and loss as defined in eq. (1). As long as F can be parametrized by a fixed number of b-bit numbers, the ERM approach of choosing the "best" f will be statistically efficient. If ERM f cannot be computed exactly within time constraints, an approximate minimizer may be used.
Fitting the threshold in single-linkage clustering. To illustrate a concrete efficient algorithm, consider choosing the threshold parameter of a single linkage clustering algorithm. Fix the set of possible vertices V. Take X to consist of undirected weighted graphs is again as defined in Eq. (1). Note that Euclidean data could be transformed into, e.g., the complete graph with Single-linkage clustering with parameter r ≥ 0, C r (V, E, w) partitions the data into connected components of the subgraph of (V, E) consisting of all edges whose weights are less than or equal to r. For generalization bounds, we simply assume that numbers are represented with a constant number of bits, as is common today. See the supplementary material for the algorithm and proof: Theorem 1. The class {C r | r > 0} of single-linkage algorithms with threshold r where numbers are represented using b bits, can be agnostically learned. In particular, a quasilinear time algorithm achieves error ≤ min r µ (C r ) + 2(b + log 1/δ)/n, with prob. ≥ 1 − δ over n training problems.
Meta-outlier-removal. For simplicity, we consider learning the single hyperparameter of the fraction of examples, furthest from the mean, to remove. In particular, suppose training problems are classification instances, i.e., X i ∈ R di×mi and Y i ∈ {1, 2, . . . , k i } mi . To be concrete, suppose one is using algorithm C which is, say, K-means clustering. Choosing the parameter θ which is the fraction of outliers to ignore during fitting, one might define C θ with parameter θ ∈ [0, 1) on data x 1 , . . . , x n ∈ R d as follows: (a) compute the data mean µ = 1 n i x i , (b) set aside as outliers the θ fraction of examples where x i is furthest from µ in Euclidean distance, (c) cluster the data with outliers removed using C, and (d) assign each outlier to the nearest cluster center.
We can trivially choose the best θ so as to optimize performance. With a single b-bit parameter θ, Lemma 1 implies that this choice of θ will give a loss within 2(b + log 1/δ)/n of the optimal θ, with probability ≥ 1 − δ over the sample of datasets. The number of θ's that need to be considered is at most the total number of inputs across problems, so the algorithm runs in polynomial time.
Problem recycling. For this model, suppose that each problem belongs to a set of common problem categories, e.g., digit recognition, sentiment analysis, image classification among the thousands of classes of ImageNet [10], etc. The idea is that one can recycle the solution to one version of the problem in a later incarnation. For instance, suppose that one trained a digit recognizer on a previous problem. For a new problem, the input may be encoded differently (e.g., different image size, different pixel ordering, different color representation), but there is a transformation T that maps this problem into the same latent space as the previous problem so that the prior solution can be re-used. In particular, for each problem category i = 1, 2, . . . , N , there is a latent problem space Λ i and a solver S i : Λ i → Y i . Each problem X, Y of this category can be transformed to T (X) ∈ Λ i with low solution loss (Y, S(T (X))). In addition to the solvers, one also requires a (meta)classifier M : X → {1, 2, . . . , N } that, for a problem X, identifies which solver i = M (X) to use. Finally, one has transformers T i : . Lemma 1 implies that if one can optimize over meta-classifiers and the parameters of the meta-classifier are represented by D b-bit numbers, then one achieves loss within of the best meta-classifier with m = O Db/ 2 problems. The possibility of meta-clustering. In this section, we point out how the framing of meta-clustering circumvents Kleinberg's impossibility theorem for clustering [6]. Kleinberg proposed three axioms for clustering. One axiom is scale-invariance which states that if one scales one's problem by a constant factor, the clustering should not change. A second axiom is richness, which states that, for any partition, there is an arrangement of points where that partition is the correct clustering.
For intuition, consider clustering two points where there is a single distance. Should they be in a single cluster or two clusters? By richness, there must be some distances δ 1 , δ 2 > 0 such that if d(x 1 , x 2 ) = δ 1 then they are in the same cluster while if d(x 1 , x 2 ) = δ 2 they are in different clusters. This, however violates Scale-Invariance, since the two problems are at a scale α = δ 2 /δ 1 of each other. In meta-clustering, prior problems can be used to define a scale. We show that a natural meta-version of the axioms is satisfied by a simple meta-single-linkage clustering algorithm where the threshold is chosen to be the minimum distance between any two points in different clusters across all training problems. The statement of this result is made precise in terms of the following Theorem, which is proved in Section A of the supplementary material.
Theorem 2. There is a meta-clustering algorithm that satisfies Meta-Scale-Invariance and whose output always satisfies Richness and Consistency.

Experiments
We conducted several experiments to substantiate the efficacy of the proposed framework under various unsupervised settings. We downloaded all classification datasets from OpenML (http://www.openml.org) that had at most 10,000 instances, 500 features, 10 classes, and no missing data to obtain a corpus of 339 datasets. For our purposes, we extracted the numeric features from all these datasets ignoring the categorical features. We now describe in detail the results of our experiments, highlighting the effects of our meta paradigm.

Selecting an algorithm
As a first step, we consider the question of which of a number of given clustering algorithms to use to cluster a given data set. In this section, we focus on k = 2 clusters. We later experiment with meta-k, the number of clusters. First, one can run each of the algorithms on the repository and see which algorithm has the lowest average error. Error is calculated with respect to the ground truth labels by the ARI (see Section 2). We compare algorithms on the 250 openml binary classification datasets with at most 2000 instances. The ten base clustering algorithms were chosen to be five clustering algorithms from scikitlearn [8]: K-Means, Spectral, Agglomerative Single Linkage, Complete Linkage, and Ward, together with a second version of each in which each attribute is first normalized to have zero mean and unit variance. Each algorithm is run with the default scikit-learn parameters. We implement the algorithm selection approach of Section 3, learning to choose a different algorithm for each problem based on problem and cluster-specific features. Given clustering Π of X ∈ R d×m , the feature vector Φ(X, Π) consists of the dimensionality, number of examples, minimum and maximum eigenvalues of the covariance matrix, and the silhouette score (see Section 2) of the clustering Π: Φ(X, Π) = (d, m, σ min (Σ(X)), σ max (Σ(X)), sil(Π)) , where Σ(X) denotes the covariance matrix of X, and σ min (M ) and σ max (M ) denote the minimum and maximum eigenvalues, respectively, of matrix M . Instead of choosing the clustering with best Silhouette score, which is a standard approach, the meta-clustering algorithm effectively learns terms that can correct for over-or under-estimates, e.g., learning for which problems the Silhouette heuristic tends to produce too many clusters. To choose which of the ten clustering algorithms on each problem, we fit ten estimators of accuracy (ARI, see Section 2) based on these features. That is for each clustering algorithm C j , we fit ARI(Y i , C j (X i )) from features Φ(X i , C j (X i )) ∈ R 5 over problems X i , Y i using ν-SVR regression, with default parameters as implemented by scikit-learn. Call this estimatorâ j (X, C j (X)). To cluster a new dataset X ∈ R d×m , the meta-algorithm then chooses C j (X) for the j with greatest accuracy estimatê a j (X, C j (X)). The 250 problems were divided into train and test sets of varying sizes. The results, shown in Figure 2, demonstrate two interesting features. First, one can see that the different baseline clustering algorithms had very different average performances, suggesting that a principled approach like ours to select algorithms can make a difference. Further, Figure 2 shows that the meta-algorithm, given sufficiently many training problems, is able to outperform, on average, all the baseline algorithms. This is despite the fact that the 250 problems have different dimensionalities and come from different domains. Based on the trend, it is possible that with more training problems it would further surpass the baselines.

Meta-k
For the purposes of this section, we fix the clustering algorithm to be K-means and compare two approaches to choosing the number of clusters, k from k = 2 to 10. First, we consider a standard heuristic for the baseline choice of k: for each cluster size k and each dataset, we generate 10 clusterings from different random starts for K-means and take one with best Silhouette score among the 10. Then, over the 9 different values of k, we choose the one with greatest Silhouette score so that the resulting clustering is the one of greatest Silhouette score among all 90. Similar to the approach for choosing the best algorithm above, in our meta-k approach, our meta-algorithm outputsk as a function of Silhouette score and k by outputting thek with greatest estimated ARI. We evaluate on the same 90 clusterings for the 339 datasets as the baseline. To estimate ARI in this experiment, we used simple least-squares linear regression. In particular, for each k ∈ {2, . . . , 9}, we fit ARI as a linear function of Silhouette scores using all the data from the meta-training set in the partition pertaining to k: each dataset in the meta-training set provided 10 target values, corresponding to different runs where number of clusters was fixed to k. As is standard in the clustering literature, we define the best-fit k * i for dataset i to be the one that yielded maximum ARI score across the different runs, which is often different from k i , the number of clusters in the ground truth (i.e., the number of class labels). We held out 20% of the problems for test and used the remaining for training (see supplementary for other split fractions). We evaluated two quantities of interest: the ARI and the root-mean-square difference betweenk and k * . Both quantities were better for the meta-algorithm than the baseline where we performed 1000 train-test splits to compute the confidence intervals:  Figure 3: Outlier removal results. Removing 1% of the instances as outliers improves on the ARI scores without outlier removal. Interestingly, going beyond 1% decreases the performance to that without outlier removal. Such data dependent observations would be missed by rules of thumb.

Removing outliers
We also experimented to see if removing outliers improved average performance on the same 339 classification problems. Our objective was to choose a single best fraction to remove from all the meta-test sets. For each data set X, we removed a p ∈ {0, 0.01, 0.02, . . . , 0.05} fraction examples with the highest euclidean norm in X as outliers, and likewise for each meta-test set in the partition. The previous section corresponds exactly to the case p = 0. We first clustered the data without outliers, and obtained the corresponding Silhouette scores. We then put back the outliers by assigning them to their nearest cluster center, and computed the ARI score thereof. Then, following an identical procedure to the meta-k algorithm of Section 4.2, we fitted regression models for ARI corresponding to complete data using the silhouette scores on pruned data, and measured the effect of outlier removal in terms of the true average ARI (corresponding to the best predicted ARI) over entire data. Again, we report the results averaged over 10 independent train/test partitions. As shown in Fig. 3, by treating 1% of the instances in each dataset as outliers, we achieved an improvement in ARI scores relative to clustering with all the data as in section 4.2. As the fraction of data considered outlier was increased to 2% or higher, however, performance degraded. Clearly one may try to learn what fraction to remove based on data-specific features, but it is interesting to see that one can even improve performance using this naive approach.

Deep learning a binary similarity function
In this section, we consider a new unsupervised problem of learning a binary similarity function (BSF) that predicts whether two examples from a given problem should belong to the same cluster (i.e., have the same class label). Formally, a problem is specified by a set X of data and meta-features φ. The goal is to learn a classifier f (x, x , φ) ∈ {0, 1} that takes two examples x, x ∈ X and the corresponding problem meta-features φ, and predicts 1 if the input pair would belong to the same cluster (or have the same class labels). In our experiments, we take Euclidean data X ⊆ R d (each problem may have different dimensionality d), and the meta-features φ = Σ(X) consist of the covariance matrix of the unlabeled data. We restricted our experiments to the 146 datasets with at most 1000 examples and 10 features. We normalized each dataset to have zero mean and unit variance along every coordinate (hence, every diagonal element in the covariance matrix was set to 1). We randomly sampled pairs of examples from each dataset to form meta-training and meta-test sets. Each dataset in the first category was used to sample data pairs for both the meta-training and the meta-internal_test (meta-IT) datasets, while the second category did not contribute any training data and was exclusively used to generate only the meta-external_test (meta-ET) dataset. Our procedure ensured a disjoint intersection between the meta-training and the meta-IT data, and resulted in 10 separate (meta-training, meta-IT, meta-ET) triplets. Note that combining thousands of examples from each of hundreds of problems yields hundreds of thousands of examples, turning small data into big data. This provides a means of making DNNs naturally applicable to data sets that might have otherwise been too small. For each meta-training set, we trained an independent deep net model. The details of the entire procedure are given in the Supplementary.
We tested our trained models on meta-IT and meta-ET data. For each feature vector in meta-IT (respectively meta-ET), we computed the predicted same class probability. We added the predicted same class probability for the feature vector obtained with flipped order, as described earlier for the feature vectors in the meta-training set. We predicted the instances in the corresponding pair to be in the same cluster if the average of these two probabilities exceeded 0.5, otherwise we segregated them. We compared the meta approach to a hypothetical majority rule that had prescience about the class distribution.As the name suggests, the majority rule predicted all pairs to have the majority label, i.e., on a problemby-problem basis we determined whether 1 (same class) or 0 (different class) was more accurate and gave the baseline the advantage of this knowledge for each problem, even though it normally wouldn't be available at classification time. This information about the distribution of the labels was not accessible to our meta-algorithm. Fig. 4 shows the average fraction of similarity pairs correctly identified relative to the corresponding pairwise ground truth relations on the two test sets, and the corresponding standard deviations across the 10 independent (meta-training, meta-IT, meta-ET) collections. Clearly, the meta approach outperforms the majority rule on meta-IT, illustrating the benefits of Comparison between the fraction of pairs correctly predicted by the meta algorithm and the majority rule. Recall that meta-ET, unlike meta-IT, was generated from a partition that did not contribute any training data. Nonetheless, the meta approach significantly improved upon the majority rule even on meta-ET.
the meta approach in a multi-task transductive setting. More interesting, still, is the significant improvement exhibited by the meta method on meta-ET, despite having its category precluded from contributing any data for training. The result clearly demonstrates the benefits of leveraging archived supervised data for informed decision making in unsupervised settings such as binary similarity prediction.

A The possibility of meta-clustering
To review, Kleinberg considers clustering finite sets of points X endowed with symmetric distance functions d ∈ D(X), where the set of valid distance functions is: A clustering algorithm A takes a distance function d ∈ D(X) and returns a partition, i.e., A(d) ∈ Π(X).
He defines the following three axioms that should hold for any clustering algorithm A: 1. Scale-Invariance. For any distance function d and any α > 0, A(d) = A(α · d), where α · d is the distance function d scaled by α.

2.
Richness. For any finite X and clustering C ∈ Π(X), there exists a distance d ∈ D(X) such that A(d) = C.
Now, suppose we define the clustering problem with respect to a non-empty training set of clustering problems. So a meta-clustering algorithm takes t ≥ 1 training clustering problems M (d 1 , C 1 , . . . , d t , C t ) = A with their ground-truth clusterings (on corresponding sets X i , i.e., d i ∈ D(X i ) and C i ∈ Π(X i )) and outputs a clustering algorithm A. We can use these training clusterings to establish a scale.
In particular, we will show a meta-clustering algorithm whose output A always satisfies the second two axioms and which satisfies the following variant of Scale-Invariance: 1. Meta-Scale-Invariance. Fix any distance functions d 1 , d 2 , . . . , d t and ground truth clusterings C 1 , . . . , C t on sets X 1 , . . . , X t . For any α > 0, and any distance function With meta-clustering, the scale can be established using training data.

A.1 Proof of Theorem 2
Proof. There are a number of such clustering algorithms, but for simplicity we create one based on single-linkage clustering. Single-linkage clustering satisfies Richness and Consistency (see [6], Theorem 2.2). The question is how to choose it's single-linkage parameter. One can choose it to be the minimum distance between any two points in different clusters across all training problems. It is easy to see that if one scales the training problems and d by the same factor α, the clusterings remain unchanged, and hence the meta-clustering algorithm satisfies meta-scale-invariance.

C Proof of Theorem 1
In this section we prove Theorem 1 of Section 3. For generalization, we assume that numbers are represented using at most b bits. By Lemma 1, we see that with m training graphs and |{C r }| ≤ 2 b , we have that with probability ≥ 1 − δ, the error of ERM is within 2(b + log 1/δ)/n of min r µ (C r ).
It remains to show how one can find the best single-linkage parameter in quasilinear time.
It is trivial to see that one can find the best cutoff for r in polynomial time: for each edge weight r in the set of edge weights across all graphs, compute the mean loss of C r across the training set. Since C r runs in polynomial time, loss can be computed in polynomial time, and the number of different possible cutoffs is bounded by the number of edge weights which is polynomial in the input size, the entire algorithm runs in polynomial time.
For a quasilinear-time algorithm (in the input size |T | = Θ( i |V i | 2 )), run Kruskal's algorithm on the union graph of all of the graphs in the training set (i.e., the number of nodes and edges are the sum of the number of nodes and edges in the training graphs, respectively). As Kruskal's algorithm adds each new edge to its forest (in order of non-decreasing edge weight), effectively two clusters in some training graph (V i , E i , W i ) have been merged. The change in loss of the resulting clustering can be computed from the loss of the previous clustering in time proportional to the product of the two clusters that are being merged, since these are the only values on which Z i changed. Naively, this may seem to take order i |V i | 3 . However, note that, each pair of nodes begins separately and is updated, exactly once during the course of the algorithm, to be in the same cluster. Hence, the total number of updates is O( i |V i | 2 ), and since Kruskal's algorithm is quasilinear time itself, the entire algorithm is quasilinear. For correctness, it is easy to see that as Kruskal's algorithm runs, C r has been computed for each possible r at the step just preceding when Kruskal adds the first edge whose weight is greater than r.  Figure 5: Average ARI scores of the meta-algorithm and the baseline for choosing the number of clusters, versus the fraction of problems used for training. We observe that the best k predicted by the meta approach registered a higher ARI than that by Silhouette score maximizer.

D Additional meta-k results
Our experiments suggest that the meta-k consistently outperforms the Silhouette baseline both in terms of the the ARI (Fig. 5) and the distance between the chosen k and k * (Fig. 6). In both the plots, for every fraction, 95% Confidence intervals were obtained with 1000 random splits of data into training and test sets.
Note again that the simple methods employed here could clearly be improved using more advance methods, but suffice to demonstrate the advantage of the meta approach.  Figure 6: RMSE of distance to the best k, k * , across datasets, i.e., comparing Clearly, the meta-k method outputs a number of clusters much closer to k * than the Silhouette score maximizer.

E Complete details: Deep learning a binary similarity function
We consider a new unsupervised problem of learning a binary similarity function (BSF) that predicts whether two examples from a given problem should belong to the same cluster (i.e., have the same class label). Formally, a problem is specified by a set X of data and meta-features φ. The goal is to learn a classifier f (x, x , φ) ∈ {0, 1} that takes two examples x, x ∈ X and the corresponding problem meta-features φ, and predicts 1 if the input pair would belong to the same cluster (or have the same class labels).
In our experiments, we take Euclidean data X ⊆ R d (each problem may have different dimensionality d), and the meta-features φ = Σ(X) consist of the covariance matrix of the unlabeled data. We restricted our experiments to the 146 datasets with at most 1000 examples and 10 features. We normalized each dataset to have zero mean and unit variance along every coordinate (hence, every diagonal element in the covariance matrix was set to 1).
We randomly sampled pairs of examples from each dataset to form metatraining and meta-test sets as described in the following section. For each pair, we concatenated the features to create data with 20 features (padding examples with fewer than 10 features with zeros). We then computed the empirical covariance matrix of the dataset, and vectorized the entries of the covariance matrix on and above the leading diagonal to obtain an additional 55 covariance features. Concatenating these features with the 20 features formed a 75-dimensional feature vector per pair. Thus all pairs sampled from the same dataset shared the 55 covariance features. Moreover, we derived a new binary label dataset in the following way. We assigned a label 1 to pairs formed by combining examples belonging to the same class, and 0 otherwise.

E.0.1 Sampling pairs to form meta-train and meta-test datasets
We formed a partition of the new datasets by randomly assigning each dataset to one of the two categories with equal probability. Each dataset in the first category was used to sample data pairs for both the meta-training and the meta-internal_test (meta-IT) datasets, while the second category did not contribute any training data and was exclusively used to generate only the meta-external_test (meta-ET) dataset.
We constructed meta-training pairs by sampling randomly pairs from each dataset in the first category. In order to mitigate the bias resulting from the variability in size of the different datasets, we restricted the number of pairs sampled from each dataset to at most 2500. Likewise, we obtained the meta-IT dataset by collecting randomly sampling each dataset subject to the maximum 2500 pairs. Specifically, we randomly shuffled each dataset belonging to the first category, and used the first half (or 2500 examples, whichever was fewer) of the dataset for the meta-training data, and the following indices for the meta-IT data, again subject to maximum 2500 instances. This procedure ensured a disjoint intersection between the meta-training and the meta-IT data. Note that combining thousands of examples from each of hundreds of problems yields hundreds of thousands of examples, turning small data into big data. This provides a means of making DNNs naturally applicable to data sets that might have otherwise been too small.
We created the meta-ET data using datasets belonging to the second category. Again, we sampled at most 2500 examples from each dataset in the second category. We emphasize that the datasets in the second category did not contribute any training data for our experiments.
We performed 10 independent experiments to obtain multiple partitions of the datasets into two categories, and repeated the aforementioned procedure to prepare 10 separate (meta-training, meta-IT, meta-ET) triplets. This resulted in the following (average size +/-standard deviation) statistics for dataset sizes: meta-training and meta-IT : 1.73 × 10 5 ± 1.07 × 10 4 meta-ET : 1.73 × 10 5 ± 1.19 × 10 4 In order to ensure symmetry of the binary similarity function, we introduced an additional meta-training pair for each meta-training pair in the meta-training set: in this new pair, we swapped the order of the feature vectors of the instances while replicating the covariance features of the underlying dataset that contributed the two instances (note that since the covariance features were symmetric, they carried over unchanged).

E.0.2 Training neural models
For each meta-training set, we trained an independent deep net model with 4 hidden layers having 100, 50, 25, and 12 neurons respectively over just 10 epochs, and used batches of size 250 each. We updated the parameters of the model via the Adadelta [16] implementation of the stochastic gradient descent (SGD) procedure supplied with the Torch library 2 with the default setting of the parameters, specifically, interpolation parameter equal to 0.9 and no weight decay. We trained the model via the standard negative log-likelihood criterion (NLL). We employed ReLU non-linearity at each hidden layer but the last one, where we invoked the log-softmax function.
We tested our trained models on meta-IT and meta-ET data. For each feature vector in meta-IT (respectively meta-ET), we computed the predicted same class probability. We added the predicted same class probability for the feature vector obtained with flipped order, as described earlier for the feature vectors in the meta-training set. We predicted the instances in the corresponding pair to be in the same cluster if the average of these two probabilities exceeded 0.5, otherwise we segregated them.

E.0.3 Results
We compared the meta approach to a hypothetical majority rule that had prescience about the class distribution. 3 As the name suggests, the majority rule predicted all pairs to have the majority label, i.e., on a problem-by-problem basis we determined whether 1 (same class) or 0 (different class) was more accurate and gave the baseline the advantage of this knowledge for each problem, even though it normally wouldn't be available at classification time. This information about the distribution of the labels was not accessible to our meta-algorithm. Fig. 4 shows the average fraction of similarity pairs correctly identified relative to the corresponding pairwise ground truth relations on the two test sets, and the corresponding standard deviations across the 10 independent (metatraining, meta-IT, meta-ET) collections. Clearly, the meta approach outperforms the majority rule on meta-IT, illustrating the benefits of the meta approach in a multi-task transductive setting. More interesting, still, is the significant improvement exhibited by the meta method on meta-ET, despite having its category precluded from contributing any data for training. The result clearly demonstrates the benefits of leveraging archived supervised data for informed decision making in unsupervised settings such as binary similarity prediction.