Current research has introduced new automatic hyperparameter optimization strategies that are able to accelerate this optimization process and outperform manual and grid or random search in terms of time and prediction accuracy. Currently, meta-learning methods that transfer knowledge from previous experiments to a new experiment arouse particular interest among researchers because it allows to improve the hyperparameter optimization. In this work we further improve the initialization techniques for sequential model-based optimization, the current state of the art hyperparameter optimization framework. Instead of using a static similarity prediction between data sets, we use the few evaluations on the new data sets to create new features. These features allow a better prediction of the data set similarity. Furthermore, we propose a technique that is inspired by active learning. In contrast to the current state of the art, it does not greedily choose the best hyperparameter conguration but considers that a time budget is available. Therefore, the rst evaluations on the new data set are used for learning a better prediction function for predicting the similarity between data sets such that we are able to prot from this in future evaluations. We empirically compare the distance function by applying it in the scenario of the initialization of SMBO by meta-learning. Our two proposed approaches are compared against three competitor methods on one meta-data set with respect to the average rank between these methods and show that they are able to outperform them.
Most machine learning algorithms depend on hyperparameters and their optimization is an important part of machine learning techniques applied in practice.
Automatic hyperparameter tuning is catching more and more attention by the machine learning community for two simple but important reasons. Firstly, the omnipresence of hyperparameters aects the whole community such that everyone is aected by the time-consuming task of optimizing hyperparameters either by manually tuning them or by applying a grid search. Secondly, in many cases the nal hyperparameter congurations decides whether an algorithm is state of the art or just moderate such that the task of hyperparameter optimization is as important as developing new models [2,4,13,17,20]. Furthermore, hyperparameter optimization has shown to be able to also automatically perform algorithm and preprocessing selection by considering this as a further hyperparameter [20].
Sequential model-based optimization (SMBO) [9] is the current state of the art for hyperparameter optimization and has proven to outperform alternatives such as grid search or random search [17,20,2]. Recent research try to improve the SMBO framework by applying meta-learning on the hyperparameter optimization problem. The key concept of meta-learning is to transfer knowledge gained for an algorithm on past experiments on dierent data sets to new experiments. Currently, two dierent, orthogonal ways of transferring this knowledge exist. One possibility is to initialize SMBO by using hyperparameter congurations that have been best on previous experiments [5,6]. Another possibility is to use surrogate models that are able to learn across data sets [1,19,23].
We improve the former strategy by using an adaptive initialization strategy.
We predict the similarity between data sets by using meta-features and features that express the knowledge gathered about the new data set so far. Having a more accurate approximation of the similarity between data sets, we are able to provide a better initialization. We provide empirical evidence that the new features provide better initializations in two dierent experiments. Furthermore, we propose an initialization strategy that is based on the active learning idea. We try to evaluate hyperparameter congurations that are nonoptimal for the short term but promise better results than choosing greedily the hyperparameter conguration that will provide the best result in expectation.
To the best of our knowledge, we are the rst that propose this idea in context of hyperparameter optimization for SMBO.
Initializing hyperparameter optimization through meta-learning was proven to be eective [5,7,15,6]. Reif et al. [15] suggests to choose those hyperparameter congurations for a new data set that were best on a similar data set in the context of evolutionary parameter optimization. Here, the similarity was dened through the distance among meta-features, descriptive data set features.
Recently, Feurer et al. [5] followed their lead and proposed the same initialization for sequential model-based optimization (SMBO), the current state of the art hyperparameter optimization framework. Later, they extended their work by learning a regression model on the meta-features that predicts the similarity between data sets [6].
Learning a surrogate model, the component in the SMBO framework that tries to predict the performance for a specic hyperparameter conguration on a data set, that is not only learned on knowledge of the new data set but additionally across knowledge from experiments on other data sets [1,19,23,16] is another option to transfer knowledge as well as pruning [22]. This idea is related but orthogonal to our work and can benet from a good initialization and is no replacement for a good initialization strategy.
We propose to add features based on the performance of an algorithm on a data set for a specic hyperparameter conguration. Pfahringer et al. [12] propose to use landmark features. These features are estimated by evaluating simple algorithms on the data sets of the past and new experiment. In comparison to our features, these features are no by-product of the optimization process but have to be computed and hence need additional time. Even though these are simple algorithms, these features are problem-dependent (classication, regression, ranking, structured prediction all need their own landmark features). Furthermore, simple classiers such as nearest neighbors as proposed by the authors can become very time-consuming for large data sets which are those data sets we are interested in.
Relative landmarks proposed by Leite et al. [10] are not and cannot be used as meta-features. They are used within the hyperparameter optimization strategy that is used instead of SMBO but are similar in that way that they are also given as a by-product and are computed using the relationship between hyperparameter congurations on each data set.
In this section the hyperparameter optimization problem is formally dened. For the sake of completeness, also the sequential model-based optimization framework is presented.
A machine learning algorithm A λ is a mapping A λ : D → M where D is the set of all data sets, M is the space of all models and λ ∈ Λ is the chosen hyperparameter conguration with Λ = Λ 1 × . . . × Λ P being the P-dimensional hyperparameter space. The learning algorithm estimates a model M λ ∈ M that minimizes the objective function that linearly combines the loss function L and the regularization term R:
Then, the task of hyperparameter optimization is nding the hyperparameter conguration λ * that minimizes the loss function on the validation data set i.e.
Exhaustive hyperparameter search methods such as grid search are becoming more and more expensive. Data sets are growing, models are getting more complex and have high-dimensional hyperparameter spaces Sequential model-based optimization (SMBO) [9] is a black-box optimization framework that replaces the time-consuming function f to evaluate with a cheap-to-evaluate surrogate function Ψ that approximates f . With the help of an acquisition function such as expected improvement [9], sequentially new points are chosen such that a balance between exploitation and exploration is met and f is optimized. In our scenario, evaluating f is equivalent to learning a machine learning algorithm on some training data for a given hyperparameter conguration and estimate the models performance on a hold-out data set.
Algorithm 1 outlines the SMBO framework. It starts with an observation history H that equals the empty set in cases where no knowledge from past experiments is used [2,8,17] or is non-empty in cases where past experiments are used [1,19,23] or SMBO has been initialized [5,6]. First, the surrogate model Ψ is tted to H where Ψ can be any regression model. Since the acquisition function a usually needs some certainty about the prediction, common choices are Gaussian processes [1,17,19,23] or ensembles such as random forests [8]. The acquisition function chooses the next candidate to evaluate. A common choice for the acquisition function is expected improvement [9] but further acquisition functions exist such as probability of improvement [9], the conditional entropy of the minimizer [21] or a multi-armed bandit based criterion [18]. The evaluated candidate is nally added to the set of observations. After T -many SMBO iterations, the best currently found hyperparameter conguration is returned.
Input: Hyperparameter space Λ, observation history H, number of iterations T , acquisition function a, surrogate model Ψ . Output: Best hyperparameter conguration found.
1
Recent initialization techniques for sequential model-based optimization compute a static initialization hyperparameter conguration sequence [5,6]. The advantage of this idea is that during the initialization there is no time overhead for computing the next hyperparameter conguration. The disadvantage is that knowledge gained during the initialization about the new data set is not used for further initialization queries. Hence, we propose to use an adaptive initialization technique. Firstly, we propose to add some additional meta-features generated from this knowledge, which follows the idea of landmark features [12] and relative landmarks [10], respectively. Secondly, we apply the idea of active learning and try to choose the hyperparameter congurations that will allow to learn a precise ranking of data sets with respect to their similarity to the new data set.
Feurer et al. [5] propose to improve the SMBO framework by an initialization strategy as shown in Algorithm 2. The idea is to use the hyperparameter congurations that have been best on other data sets. Those hyperparameter congurations are ranked with respect to the predicted similarity to the new data set D new for which the best hyperparameter conguration needs to be found. The true distance function d : D × D → R between data sets is unknown such that Feurer et al. [5] propose to approximate it by d (m i , m j ) = m i − m j p where m i is the vector of meta-features of data set D i . In their extended work [6], they propose to use a random forest to learn d using training instances of the form (m i , m j ) T , d (D i , D j ) . This initialization does not consider the performance of the hyperparameters congurations already evaluated on the new data set.
We propose to keep Feurer's initialization strategy [6] untouched and only add additional meta-features that capture the information gained on the new data set. Meta-features as dened in Equation 3 are added to the set of metafeatures for all hyperparameter congurations λ k , λ l that are evaluated on the new data set. The symbol ⊕ denotes an exclusive or. An additional dierence is that now after each step the meta-features and the model d needs to be updated
We make here the assumption that the same set of hyperparameter congurations were evaluated across all training data sets. If this is not the case, this problem can be overcome by approximating the respective value by learning surrogate models for the training data sets as well. Since for these data sets much information is available, the prediction will be reliable enough. For simplicity, we assume that the former is the case.
The target d can be any similarity measure that reects the true similarity between data sets. Feurer et al. [6] propose to use the Spearman correlation coecient while we are using the number of discordant pairs in our experiments, i.e.
where Λ is the set of hyperparameter congurations observed on the training data sets. This change will have no inuence on the prediction quality for the traditional meta-features but is better suited for the proposed landmark features in Equation 3.
Input: Hyperparameter space Λ, observation history H, number of iterations
We propose to extend the method from the last section by investing few initialization steps by carefully selecting hyperparameter congurations that will lead to good additional meta-features and provide a better prediction function d. An additional meta-feature is useful if the resulting regression model d predicts the distances of the training data sets to the new data set such that the ordering with respect to the predicted distances reects the ordering with respect to the true distances. If I is the number of initialization steps and K < I is the number of steps to choose additional meta-features, then the K hyperparameter congurations need to be chosen such that the precision at I − K with respect to the ordering is optimized. The precision at n is dened as prec@n := |{n closest data sets to Dnew wrt. d}∩{n closest data sets to Dnew wrt. d}| n
Algorithm 3 presents the method we used to nd the best rst K hyperparameter congurations. In a leave-one-out cross-validation over all training data sets D the pair of hyperparameter congurations (λ j , λ k ) is sought that achieves the best precision at I − K on average (Lines 1 to 7). Since testing all dierent combinations of K dierent hyperparameter congurations is too expensive, only the best pair is searched. The remaining K − 2 hyperparameter congurations are greedily added to the nal set of initial hyperparameter congurations Λ active as described in Lines 8 to 15. The hyperparameter conguration is added to Λ active that performs best on average with all hyperparameter congurations chosen so far. After choosing K hyperparameter congurations as described in Algorithm 3, the remaining I − K hyperparameter congurations are chosen as described in Section 4.1. The time needed for computing the rst K hyperparameter highly depends on the size of Λ. [5,15]. Instead of choosing I training data sets at random, they are chosen with respect to the similarity between the meta-features listed in Table 1. Then, like for RBI, the best hyperparameter congurations on these data sets are chosen for initialization.
Predictive Best Initialization (PBI) Feurer et al. [6] propose to learn the distance between data sets using a regression model based on the meta-features. These predicted distances are used to nd the most similar data sets to the new data set and like before, the best hyperparameter congurations on these data sets are chosen for initialization.
Adaptive Predictive Best Initialization (aPBI) This is our extension to PBI presented in Section 4.1 that adapts to the new data set during initialization by including the features dened in Equation 3.
Active Adaptive Predictive Best Initialization (aaPBI) Active Adaptive Predictive Best Initialization is described in Section 4.2 and extends aPBI by using the rst K steps to choose hyperparameter congurations that will result in promising meta-features. After the rst K iterations, it behaves equivalent to aPBI.
Meta-features are supposed to be discriminative for a data set and can be estimated without evaluating f . Many surrogate models [1,19,23] and initialization strategies [5,15] use them to predict the similarity between data sets. For the experiments, the meta-features listed in Table 1 are used. For an in-depth explanation we refer the reader to [1,11].
For creating the two meta-data sets, 50 classication data sets from the UCI repository are chosen at random. All instances are merged in cases there were already train/test splits, shued and split into 80% train and 20% test. A support vector machine (SVM) [3] was used to create the meta-data set. The SVM was trained using three dierent kernels (linear, polynomial and Gaussian) and the labels of the meta-instances were estimated by evaluating the trained model on the test split. The total hyperparameter dimension is six, three dimensions for indicator variables that indicates which kernel was chosen, one for the trade-o parameter C, one for the width γ of the Gaussian kernel and one for the degree of the polynomial kernel d. We evaluated all methods in a leave-one-out cross-validation per data set.
All data sets but one are used for training and the data set not used for training is the new data set. The results reported are the average over 100 repetitions.
Due to the randomness, we used 1,000 repetitions whenever RBI was used. q q q q q q q q q q 2.0 Number of Initial Hyperparameter Configurations Average Rank q q q q q q q q q q 0.1 Number of Initial Hyperparameter Configurations Average Normalized MCR q RBI NBI PBI aPBI aaPBI Fig. 1. Five dierent tuning strategies are compared. Our strategy aPBI is able to outperform the state of the art. Our second strategy aaPBI is executed under the assumption that it has 10 initial steps. The rst steps are used for active learning and hence the bad results in the beginning are not surprising.
Comparison to Other Initialization Strategies For all our experiments 10 initialization steps are used, I = 10. In Figure 1 the dierent initialization strategies are compared with respect to the average rank in the left plot. Our initialization strategy aPBI benets from the new, adaptive features and is able to outperform the other initialization strategies. Our second strategy aaPBI uses three active learning steps, K = 3. This explains the behavior in the beginning.
After these initial steps it is able to catch up and nally surpass PBI but it is not as good as aPBI. Furthermore, a distance function learned on the metafeatures (PBI) provides better results than a xed distance function (NBI) which conrms the results by Feurer et al. [6]. All initialization strategies are able to outperform RBI which conrms that the meta-features contain information that concludes information about the similarity between data sets. The right plot shows the average misclassication (MCR) rate where the MCR is scaled to 0 and 1 for each data set.
Comparison with Respect to the Long Term Eect To have a look at the long term eect of the initialization strategies, we compare the dierent initialization strategies in the SMBO framework using two common surrogate models. One is a Gaussian process with a squared exponential kernel with automatic relevance determination [17]. The kernel parameters are estimated by maximizing the marginal likelihood on the meta-training set [14]. The second is a random forest [8]. Again, aPBI provides strictly better results than PBI for both surrogate models and outperforms any other initialization strategy for the Gaussian process. Our alternative strategy aaPBI performs mediocre for the Gaussian process but good for the random forest.
q qq q q q qqqqq qq q q qq qqqq qq q q qq qqqqqq qqqqqqq qq q qqq qq q qqq qqqq qqqq Gaussian Process q q q q qq q q qqq qq q q q q q qq q qq qq qq q qq q qqqqq q qq qqqqqq q q q q q q q qqq q q q qq 2.5
Fig. 2. The eect of the initialization strategies on the further optimization process in the SMBO framework using a Gaussian process (left) and a random forest (right) as a surrogate model is investigated. Our initialization strategy aPBI seems to be strictly better than PBI while aaPBI performs especially well for the random forest in the later phase.
Predicting the similarity between data sets is an important topic for hyperparameter optimization since it allows to successfully transfer knowledge from past experiments to a new experiment. We have presented an easy way of achieving an adaptive initialization strategy by adding a new kind of landmark features.
We have shown for two popular surrogate models that these new features improve over the same strategy without these features. Finally, we introduced a new idea that in contrast to the current methods considers that there is a limit of evaluations. It tries to exploit this knowledge by applying a guided exploitation at rst that will lead to worse decisions for the short term but will deliver better results when the end of the initialization is reached. Unfortunately, the results for this method are not fully convincing but we believe that it can be a good idea to choose hyperparameter congurations in a smarter way but always assuming that the next hyperparameter conguration chosen is the last one.
In this work we were able to provide a more accurate prediction of the similarity between data sets and used this knowledge to improve the initialization.
Since not only initialization strategies but also surrogate models rely on an exact similarity prediction, we plan to investigate the impact on these models. For example Yogatama and Mann [23] use a kernel that measures the distance between data sets by using the p-norm between meta-features of data sets only. A better distance function may help to improve the prediction and will help to improve the SMBO beyond the initialization.
Acknowledgments. The authors gratefully acknowledge the co-funding of their work by the German Research Foundation (Deutsche Forschungsgesellschaft) under grant SCHM 2583/6-1.