Pre-trained models can be reused directly or through transfer learning so that the substantial efforts required for collecting and annotating training data on the new problems can be greatly saved [30] . This has motivated a number of model sharing platforms, such as TensorFlow Hub [3], PyTorch Hub [2], and DLHub [1] . However, the selection of proper models for serving is mostly through the intuition of domain experts and trial-error processes. Consider To address such problem, most of the model sharing platforms like DLHub [1] provides a model search tool based on the indexing of model metadata that mostly covers: (1) publication schemas such as author, creation date, description;
(2) model information such as algorithm, software version, network architecture; (3) development provenance such as versions, contributors; (4) training information such as training datasets and training parameters; (5) performance information such as accuracy on benchmark datasets.
However, none of this information can directly tell which model should be selected for inference on a target dataset. The prediction of the serving accuracy of a model in a target dataset is inherently a complex problem. It is related not only to the model architecture, but also to the similarity and relationships between the source and target datasets. The model is the best only if it fits your dataset [13] . However, we observe that existing model serving platforms are lack of the capability to automatically search for a model that is trained on the best fitting dataset. People need to perform a textbased search using keywords, scrutinize each search result, and manually check the similarity of each training dataset to their own dataset. Such human-centered model selection is inefficient, which delays the model deployment and incurs significant human costs. To alleviate this problem, it is critical to automate the model selection process for model serving. The technical challenges include: (1) Storing training datasets with the models incurs significant storage overheads and privacy concerns.
(2) The similarity measurements with all candidate datasets are time-consuming. The computational overhead not only scales to the number of available models in a domain, but also scales to the sizes of the training datasets to be compared. Taking TensorFlow Hub for example, text embedding domain has 134 models, and image feature vector domain has 130 models. In addition, the datasets used by models in TensorFlow Hub may have up to several hundreds of terabytes in size, as illustrated in Fig. 1 , which also significantly slows down similarity measurements.
In this work, we address these two problems using locality sensitive hashing (LSH) for the probability distributions [10, 23] . While LSH is a popular technique to solve nearest neighbor problems, most of existing LSH families, are designed to measure the Hamming distance [12] and Euclidean distance [16] of two vectors with fixed dimensions, or the Jaccard similarity [6] and cosine similarity of two high-dimensional binary vectors [8] . Until very recently, the LSH for measuring similarity of probability distributions is studied [10, 23] . S2JSD-LSH [23] is first proposed to provide LSH functions for a new measurement S2JSD approx new , which is obtained by only keeping the linear terms in the Taylor expansion of the logarithm in the expression of S2JSD, the square root of two times the Jensen-Shannon (JS) divergence. However, their LSH design doesn't provide any bound on the actual JS-divergence. Then Chen et al. [10] propose a new LSH scheme for the generalized JS-divergence through the approximation of the squared Hellinger distance, which is in the form of the L2-LSH family [12] , and called as JS-LSH in this paper.
A significant problem is that JS-divergence is symmetric, however the serving accuracy may not be symmetric. For example, a dataset A may contain only a subset of labels of another dataset B; then supposing we have a model M A that is trained on A, and a model M B that is trained on B, the accuracy of M A on B, and the accuracy of M B on A could be very different. Obviously, simply applying the symmetric JS-divergence to the model selection problem may be problematic. While there exist asymmetric measurements of two probability distributions, such as Kullback-Leibler (KL) divergence, there doesn't exist efficient LSH families for these metrics. To address the problem, we propose to split a dataset into a number of partitions and compute the JS-LSH for each partition, so that each dataset is associated with multiple LSH signatures. Thus we propose a new metric, called adaptivity, based on the number of equivalent LSH signatures shared by two datasets and the size of the target dataset, which indicates the portion of samples in the target dataset that have been seen by the model.
Another problem is that before we can apply the adaptivity measurement for fast nearest neighbor search, we need first determine the overlapping feature space between the source domain and the target domain, because the features in the source domain may be very different from the target domain. It is straightforward to use MinHash [35] , another LSH technique based on Jaccard similarity, to find all of the shared features between two datasets. However, because the overlapping space can only be determined at the query time, there is no way to pre-compute the JS-LSH signatures. To address the problem, we propose to use a compressed and indexed probability distribution to represent each model's training dataset by encoding occurrences of feature values falling into each hash bin, so that the storage overhead and runtime JS-LSH computation time can be significantly reduced without losing the effectiveness.
Our main contributions are summarized as following: (1) As far as to our knowledge, we are the first to systematically explore the problem of finding related models for serving a target domain by comparing various metrics.
(2) We propose an adaptivity metric and an end-to-end system, called as ModelHub, to automate the process of finding related models for serving based on dynamic computation over the features shared by the source and target domains using LSH techniques.
(3) We conduct extensive experiments to compare the effectiveness of the proposed system to alternative solutions.
2 Background 2.1 Jensen-Shannon (JS) Divergence JS-divergence [21] is a measurement of the similarity of two probability distributions, which is a symmetric metric derived from the asymmetric Kullback-Leibler (KL) divergence [18] .
Let P and Q be two probability distributions associated with a common sample space Ω, and let M = (P + Q)/2. The JS-divergence is defined by:
Here, D KL denotes the Kullback-Leibler divergence, which is defined as following for discrete distributions:
and as following for continuous distributions:
In this work, we mainly consider to leverage JSdivergence to select models for serving. First, JS-divergence is a widely used similarity metric for probability distributions [19] . Second, it is easier to find LSH schemes for JSdivergence, compared to other similarity measurements of probability distributions [23] . While other metrics such as Maximum Mean Discrepancy (MMD) could measure the domain adaptivity more accurately, it requires an optimization process and significantly higher computational costs, as illustrated in Tab. 1.
2.2 Locality Sensitive Hashing (LSH) LSH was developed for general approximate nearest neighbor search problem [16] . It requires a family of LSH functions, each of which is a hash function whose collision probability increases with the similarity of the inputs. The (r 1 , r 2 , p 1 , p 2 )sensitive LSH family is formally defined in Definition. 1.
LSH is first proposed by Indyk and et al [16] for measuring the Hamming distance in a d-dimensional Euclidean space, which requires the data to be vectors with fixed dimensions. MinHash [6] is a widely used family of hash functions for Jaccard similarity. SimHash is an LSH scheme for Cosine distance [8] . Both of MinHash and SimHash are only applicable to high-dimensional binary vectors or sets of values (without fixed dimensions), and MinHash is usually considered to be more computationally efficient than SimHash [35] . However none of these popular LSH schemes are applicable to our problem where each dataset is a variable number of high-dimensional vectors.
As mentioned, the LSH schemes for probability distributions are recently studied [10, 23] . S2JSD-LSH [23] provides LSH functions for a measurement that approximates the square root of two times the JS-divergence. Unfortunately, their LSH design doesn't provide any bound on the actual JS-divergence. Then Chen et al. [10] propose a new LSH scheme for the generalized JS-divergence through the approximation of the squared Hellinger distance, which is proved to be bounded with the actual JS-divergence and thus used in this work as JS-LSH, as defined in Eq. 2.4:
where P is a probability distribution in the sample space Ω, a ∼ N (0, I) is a |Ω|-dimensional standard normal random vector, · represents the inner product operation, b is a random variable uniformly distributed on [0, r], and r is a positive real number. This approximation is proved to be lower bounded by a factor 0.69 for the JS-divergence [10] . 
and q j (0 ≤ j < nt) are partitions that have equivalent sizes (except for the last residue partition), given a threshold t, we can join D s and D t to identify all pairs in form of (p i , q j ), so that D JS (p i , q j ) ≤ t. We denote the total number of pairs that satisfy above condition as num matches. Then we can derive a new metric to measure the adaptivity of the models trained in the source domain to the target domain, denoted as: adaptivity(D s , D t ) = num matches nt .
We divide the problem of selecting a model for reuse in two sub-problems. The first subproblem is to obtain the overlapping features of the training data (i.e. source domain) and the query data (i.e. target domain). The second sub-problem is to measure the adaptivity over the overlapping feature space. The two sub-problems are formulated as following.
DEFINITION 3. Suppose we have a database of n pretrained models (i.e., source tasks in a source domain), rep-
Given a query q that has k q features, denoted as F q = {f 1 , ..., f kq }, and two thresholds t 1 , t 2 ∈ [0, 1], the database should return a set of relevant models, denoted as M q ⊂ M, so that
DEFINITION 4. Supposing each model M i ∈ M has a source domain represented as D i . Given a query that has a target domain D q , as well as a threshold t adaptivity or t JS , depending on which metric is used, the database should return a set of relevant models, denoted as M q ⊂ M,
Here, D i and D q are defined over the overlapped feature space as defined in Def. 3.
We propose ModelHub as an end-to-end solution to address the above two problems. ModelHub is a model sharing platform, which requires that for each model, following information must be provided: (1) A MinHash signature for each feature in the training data. MinHash is a widely used technique to efficiently search nearest neighbors based on the Jaccard similarity. For a feature that contains continuous numerical values, we first quantize the values into a number of bins based on the range and distribution of data, to improve the effectiveness of Jaccard similarity estimation for such features [29] .
(2) A compressed data sketch for each partition of the training dataset, which can be used to easily derive the probability distribution over any subset of features in this partition. This structure is used to derive the JS-LSH signatures for efficiently measuring JS-divergence in the dynamic overlapping feature space shared by the training dataset of this model (i.e. the source domain) and the querying dataset (i.e. the target domain). Most training datasets are multi-dimensional, and to compute the multi-variate probability distribution of a multi-dimensional dataset is difficult [27] . To solve the problem, we first flatten a multi-dimensional dataset into a single-dimensional dataset [10] and then create a set of histogram bins over the flattened dataset. Finally, we create an index, each entry contains a feature ID followed by the feature's occurrences in each bin, as illustrated in Fig. 2 . All partitions across all datasets have equivalent size m. Based on these information, the system can efficiently compute the adaptivity based on Def. 2, without uploading the training dataset. The process is depicted as following.
Step 1. Given a query dataset, we need first determine all models that have significant overlaps in feature space with the query dataset using the MinHash signatures. (Sec. 3.4) Step 2. For each of the models returned from Step 1, we use adaptivity to select the best model. We compute the JS-LSH signatures over the shared features for each partition, store the signatures of the larger dataset that has more partitions to hash tables, and then use the signatures of the smaller dataset to look up in the hash tables to determine the number of similar partitions. Then we estimate the adaptivity of the source domain and the target domain, as defined in Def. 2 and Def. 4.(Sec. 3.5)
The search of the overlapping features of a source dataset and the target dataset are based on MinHash [6] , a widely used locality sensitive hashing technique for Jaccard similarity. The search process contains an offline and an online stage. We first describe the offline stage. First, for each model, we expand each feature into a vector of values based on its succinct representation of the training data, by replicating the value associated with each bin by the number of its occurrences. Then for each feature vector, we will create L minhash MinHash signatures corresponding to L minhash bands. Each band is associated with K minhash MinHash functions, and each signature is a concatenation of K minhash MinHash values produced by the band's functions. A hash table is created for each band, so that for each model, each of the L minhash signatures is stored to the corresponding hash table.
Then at the online stage, a model search request regarding a target dataset is issued. The target dataset's MinHash signatures will be computed for each feature on each band using the aforementioned approach. Then for each feature, the signature of each band will be used to query the corresponding hash table to find out all models that have a matching signature. Finally, models having a significant portion of features overlapping with the target dataset, as defined in Def. 3, will be identified and returned.
In this section, we mainly describe how the adaptivity metric is computed over the identified overlapping feature space at runtime. First, for each partition in the training dataset of a model M i , we expand the succinct representation into a one-dimensional dataset that concatenates all expanded feature vectors. Then for each partition's dataset, we create L jslsh bands, and each band is associated with K jslsh hash functions based on Eq. 2.4, we create a JS-LSH signature of length K jslsh by concatenating values computed by these hash functions. Each band is constructed with a hash table and each signature is stored into the corresponding band's hash table.
Then, we do the same for the target dataset to obtain L jslsh signatures for each band in each partition, which are used to query the corresponding hash table to find all models, of which a partition of the training data has a matching signature in the same band. Based on the matches, we can compute the adaptivity as defined in Def. 2. Finally, we will select the models whose adaptivity with the target dataset passes a threshold t adaptivity as described in Def. 4. The computation of JS-divergence is a special case of the above process where the number of partitions is set to 1.
We evaluate our proposed methodology using four workloads. 1. Activity Recognition. Human activity recognition (HAR), is to predict the activities (e.g. walking, sitting, running, lying) based on data collected from multiple sensors attached to human body. HAR is a hot research topic in the pervasive computing area, and has been widely applied to indoor localization, sleep state detection, smart home sensing, and virtual reality [4] . In this work, we use three public activity recognition datasets, including OPPORTUNITY [9] , PAMAP2 [26] , and UCI DSADS [5] . Each dataset is extracted with 81 features [28] . The OPPORTUNITY dataset is collected from four human subjects executing various activities with sensors attached to more than five body parts. The PAMAP2 dataset is collected from nine subjects performing 18 activities with sensors attached to three body parts. The UCI DSADS dataset is collected from eight subjects wearing sensors on five body parts. We create 162 tables by sampling these datasets, so that each table represents samples collected from a body part for specific subject. Then we apply our approach to a series of scenarios where models are trained on each of these tables, and given a target dataset collected from a subject on a specific body part, we want to select a model to achieve the best accuracy on the target dataset. 2. Entity Matching (EM). Entity matching is to tell whether two tuples are referring to the same entity [7, 14, 15, 20, 33] . We mainly apply DeepMatcher [24] , which is an EM tool based on deep learning, to four datasets 1 : Walmart-Amazon, Abt-Buy, DBLP-Scholar, DBLP-ACM; and 11 smaller datasets from the Magellan Data Repository [11] 2 . Each task contains training and testing samples collected from two different datasets. For example, IMDB-TMD is to match movie tuples collected from IMDB and TMD respectively. Each EM task may have different features, and some tasks share a significant portion of common features. We focus on the model selection scenarios where a dataset is used for query, and a set of models are trained for the EM tasks on the rest of the datasets as candidates, and then we try to select a candidate model to serve the query dataset. 3. Image Recognition. To create five image datasets with distinct probability distributions, we randomly sample images from the Cifar-10 dataset without replacement. Cifar-10 is a collection of images with labels of ten classes, each containing 5, 000 images. Then we make four of the subsets skewed by adding 5000 images of the fourth class to the second and the fourth subset; 5000 images of the second class to the third subset; 5000 images of the eighth class to the third subset. These five datasets are called as Balanced, Skewed-1, Skewed-2, Skewed-3, Skewed-4 correspondingly. To evaluate the effectiveness of our proposed metrics for the image recognition scenario, we train ResNet56v1 model on each of the subsets respectively, and then perform five experiments of searching for the best model to be reused on each of the five datasets. 4. Natural Language Processing (NLP). We are mainly interested in two types of NLP tasks. The first task is to identify whether sentence pairs have equivalent semantic meanings. For this task, we train models on three different datasets: Microsoft Research Paraphrase Corpus (MRPC) that includes 3, 549 samples; Quora Question Pairs (QQP) that consists of 363, 192 samples; and Paraphrase Adversaries from Word Scrambling (PAWS) which has 49, 401 samples. The second task is about natural language inference (NLI), which is to identify the textual entailment relationship [22] between sentence pairs. Similar to the first task, we train models on three different datasets: Recognizing Textual Entailment (RTE) that has 2, 490 samples; Question NLI, which contains 510, 711 samples; and the SCITAIL dataset including 5, 302 samples, which is an entailment dataset created from multiple-choice science exams and web sentences. We train models for these tasks using the same pre-trained BERT base model 3 , denoted as uncased L-12 H-768 A-12, which contains 12 layers and 110 millions of parameters. Then for each task, we use one of the three datasets as the target dataset, and try to choose the best model to serve on the target dataset.
In these experiments, we mainly compare our proposed adaptivity metric (as defined in Def. 2) to other alternatives, including (1) JS-divergence (a special case of adaptivity when each dataset has only one partition), which is computed using the JS-LSH for JSdivergence; (2) L2-distance, which is to get the center of the overlapping features for the source and target datasets, and then compute the L2-LSH for Euclidean distance [16] ;
(3) source accuracy, which is the testing accuracy of the candidate model on the source dataset.
To compare the effectiveness of these metrics, we compute the Pearson correlation coefficient values to show the impact of various metrics, including the adaptivity, the JSdivergence, the L2-distance, and the source accuracy, to the target accuracy (i.e. the prediction accuracy of the source model on the target dataset). In most of the cases, JSdivergence and L2-distance have the negative relationships with the target accuracy, so their Pearson correlation coefficient values are often negative. In addition, we also evaluate and compare the error rate for each metric, while the top1error and top2-error are defined as the number of wrong predictions in identifying the best model or one of the top two models to the total predictions.
We first compare the accuracy and latency of our proposed approach based on LSH for JS-divergence to a baseline approach that computes the JSdivergences between the target dataset and each of the source datasets directly without using LSH techniques. The results are illustrated in Fig. 3 , in which each bar represents a test case that uses one table as the query (i.e. target dataset), and the rest of the tables as the sources. In this experiment, for each test, we assume the source datasets that have the JS-divergence with the query dataset smaller than 0.1 compose the ground truth. We observe that using LSH can significantly accelerate the overall latency required for JSdivergence comparison, and achieve 5× speedup on average, while the precision of our proposed approach is 100% and recall is above 93%, which are both acceptable results. We further evaluate how hyperparameters, such as r (as in Eq. 2.4), the number of concatenated hash functions (i.e., K l2hash ) of each band, the number of bands (i.e., L l2hash ), and the number of hash bins, will affect the accuracy of the JS-divergence computed using LSH compared to the baseline, which are illustrated in Fig. 4 . The comparison of Pearson correlation coefficient values of various metrics, including the adaptivity, the JSdivergence, the L2-distance, and the source accuracy, to the target accuracy are illustrated in Tab. 2. It shows that our proposed adaptivity metric can achieve better performance. Also among the four metrics, the source accuracy exhibits the least relevance with the target accuracy, which demonstrates our assumption that "It's the best only when it fits you most", and indicates that the similarity between the source and the target plays a more important role in determining model adaptivity.
We also compute the top-1 and top-2 error rates, as illustrated in Tab. 3. It shows that all of the metrics including adaptivity, JS-divergence, and L2-distance can serve as a metric for finding related models with zero top-2 errors in our test cases. In addition, adaptivity and L2-distance have better top-1 error rate than JS-divergence.
In this experiment, different from activity recognition, most attributes contain text-based values. We represent the training dataset of each entity matching task as a bag of words over a shared dictionary for computing the JS-divergence and adaptivity. We compare the Pearson correlation coefficient values of the JS-divergence metric, the adaptivity metric, and source accuracy, to the target accuracy for each EM task, as illustrated in Tab. 4. We also compare the overall accuracy in terms of top1-error and top2-error for all fifteen tasks, as illustrated in Tab. 5. The results show that the adaptivity metric outperforms other metrics in selecting the model to serve with the best accuracy. We evaluate and compare the effectiveness of adaptivity, JS-divergence, L2-distance, and source accuracy for searching the best model to serve on a target dataset. The Pearson correlation coefficient of each metric to the target accuracy in each experiment is illustrated in Tab. 6. The top-1 and top-2 error rate for searching the best model for each experiment is illustrated in Tab. 9.
For this experiment, as mentioned in Sec. 4.1, because each task involves merely three datasets, a model search scenario for a target dataset only requires to compare two datasets. Therefore, instead of computing the Pearson coefficient for each search scenario, we choose to compute for each task that contains three search scenarios. For the same reason, we only consider top-1 error for this experiment, which is counted over all six search scenarios across the two tasks.
The results are illustrated in Tab. 8 and Tab. 9, which show that while adaptivity has less correlation with the target accuracy compared to JS-divergence, it can more effectively predict the best model for serving with zero error rate for all six search scenarios. The source accuracy performs much worse than other metrics.
One thing to note is that the computation of adaptivity is more complicated than JSdivergence and takes more time. For most of above experiments, we choose the partition size of each dataset between 300 to 800. For the NLP experiment, when the source dataset and the target dataset has a significant size discrepancy, we choose the size of the smaller dataset to be the partition size, so that the smaller dataset has only one partition. Then we compare the latency of computing JS-divergence and adaptivity by using different partition sizes and for different sizes of source and target datasets. The results are illustrated in Fig. 5 , which illustrates that when partition size is around 500, the computational overhead for adaptivity is 1.7 − 3× of JS-divergence. In recent, numerous works are proposed to address open data discovery problems, including automatically discover table unionability [25] and joinability [34, 35] , and related tables [32] . Most of these works are trying to identify all similar features using LSH techniques based on Jaccard similarity or variants. While these works are helpful to this study in identifying the overlapping feature space, they are not di-rectly applicable in selecting related models, because the existence of a significant portion of shared features between the source and target datasets doesn't mean the probability distribution of the feature space of the two datasets are similar. Zamir and et al [31] propose a computational approach to find the transferable relationships, abstracted as taskonomy among the different computation vision tasks, e.g. depth estimation, edge detection, point matching and etc., so that some tasks can be trained using other tasks' output and thus require less training data and supervision budget. Their work is focused on the adaptivity from a task's output domain to another task's input domain. In contrast, our work is focused on the adaptivity of tasks' input domains. Also while their work is limited to computer vision, our work is targeting at a more generalized scenario. Kornblith and et al [17] study the relationship between the ImageNet model architectures such as ResNet, MobileNet, Inception-ResNet, etc., and the transfer learning performance. They observe that transfer learning based on finetune techniques (i.e., just tune the last two layers) even using a "better" model architecture may not achieve "better" accuracy. This means in regard of the effectiveness of transfer learning, the divergence of features between the source and target domains is more important than the difference of model architectures. Their observation indicates that our work may be applicable to find related models for transfer learning.